Relational algebra and rewrite rules

A mathematical set records whether an element exists. A bag also records how many times it occurs. Ordinary SQL SELECT does not remove duplicates unless its semantics request duplicate elimination, such as SELECT DISTINCT. Projecting away a column can therefore leave several equal-looking output rows, each of which still matters to a later count or sum. A rewrite that quietly deduplicates an intermediate result may change the answer even when its displayed distinct values look identical. Start a correctness check with multiplicities, not just a list of possible values.

An inner join combines every qualifying pair of input rows. If one key occurs twice on one side and three times on the other, that key contributes six pairs, assuming every associated predicate is true. A declared uniqueness constraint can justify a stronger bound, but a few sample rows cannot establish uniqueness for future data. Keep the needed join keys and multiplicities when pushing projections down. Dropping a column early is harmless only when no later predicate, ordering, grouping, or requested output requires it and the duplicate behavior remains correct.

A deterministic total predicate that refers only to the left input can be applied before an inner join or after it, with the same qualifying row pairs. This is a useful selection-pushdown rule. Total here means the expression is defined for every relevant input; otherwise, moving evaluation can change which errors occur. SQL functions with volatile behavior or observable side effects add further restrictions. Optimizers use expression properties and language rules, so an algebraic identity should not be treated as permission to manually reorder arbitrary functions that happen to return booleans.

SQL predicates also use a three-valued logic. An ordinary comparison involving NULL generally produces unknown rather than true or false, and WHERE retains only true rows. NULL is not equal to itself under ordinary equality; use the documented null predicates or null-aware comparison when that is the intended meaning. Rewrites involving NOT IN, equality, and missing values need their own proof. It is often clearer to define the application's missing-value meaning first than to discover after optimization that an empty result came from an unexpected NULL.

A left outer join emits unmatched left rows with null-extended right columns. A right-side condition in ON decides whether a match exists; the same condition in WHERE can reject the padded row afterwards. Those are different questions. A null-rejecting right-side WHERE condition can sometimes justify replacing an outer join with an inner join, but preserving the outer join while blindly pushing that condition into its right input is not the same transformation. Write a two-row counterexample before accepting a proposed identity involving a preserved side.

The binomial lab models only the number of rows passing one predicate under an explicit independent equal-probability assumption. Reset, set both p=0.5 and n=20, predict ten expected survivors, then Play or Step. Separately Reset, set both p=0.25 and n=20, predict five, then Play or Step. Playback highlights exact outcomes rather than sampling rows. This instrument has no joins, NULLs, duplicate identities, or rewrite engine. Use it to estimate a potential work reduction only after proving the selection movement legal; it cannot establish equivalence.