Real query engines evaluate bag (multiset) algebra rather than the set algebra of the textbook. Which algebraic laws stop holding once duplicates are preserved, and how does that constrain the rewrites an optimizer is allowed to perform?

## Why engines are not set machines The textbook relational model defines a relation as a **set** of tuples: no duplicates, ever. Real systems do not work this way, and the reasons are not laziness. 1. **Aggregation requires multiplicity.** `SUM(amount)` over a projected column is wrong if equal amounts collapsed. Any algebra containing aggregation must preserve duplicates in its intermediates. 2. **Duplicate elimination is expensive.** It requires sorting or hashing the entire intermediate — a blocking, memory-consuming operation. Doing it after every projection would be catastrophic, and it is unnecessary in most contexts. 3. **Pipelining.** Bag operators can stream tuple-at-a-time. Set semantics would force a materialisation barrier everywhere. So real algebra is **bag algebra**, and duplicate elimination becomes an explicit operator (`delta`, or grouping with no aggregates) that the optimizer places deliberately. ## The operators as count arithmetic Model a bag as a function from tuples to non-negative integers. Then: - **Selection**: keeps the count of qualifying tuples, zero for the rest. - **Projection**: the count of an output tuple is the **sum** of the counts of all input tuples that project onto it. No elimination. - **Bag union**: counts **add**. `{a:1} UNION {a:1} = {a:2}`. - **Bag intersection**: counts take the **minimum**. - **Bag difference**: counts **subtract, floored at zero**. - **Product/join**: the count of a joined tuple is the **product** of the two input counts. - **Duplicate elimination**: every non-zero count becomes one. Every law you want to check reduces to arithmetic on these counts, which makes verification mechanical: write both sides as count expressions and see whether they agree for all non-negative integers. ## Laws that fail **Idempotence of union.** For sets, `R UNION R = R`. For bags, counts double. This is the headline failure and the one to lead with. **Absorption.** `R UNION (R INTERSECT S) = R` holds for sets. For bags the left side has count `r + min(r, s)`, not `r`. **Difference identities.** Set identities such as `R - (S UNION T) = (R - S) - T` need re-derivation under floored subtraction; some survive, some do not, and each must be checked rather than assumed. **Projection as a dedup.** In set algebra `pi A (R)` implicitly removes duplicates, and many textbook rewrites lean on that. In bag algebra it does not, so a rewrite that silently assumed post-projection uniqueness is unsound. **Semi-join versus join equivalence.** `R JOIN S` restricted back to `R`'s attributes equals `R SEMIJOIN S` only under set semantics. Under bags, the join multiplies `R`'s rows by the number of matches in `S`, while the semi-join preserves `R`'s original counts. This is the practical form in which the failure bites — the rewrite from an existential subquery to an inner join is unsound in bag algebra without a dedup or a uniqueness guarantee on the probe side. ## Laws that survive Enough survives that optimization is still possible: - Commutativity and associativity of bag union, bag intersection, product and inner join — counts add or multiply, and both operations are commutative and associative. - Predicate pushdown through joins and products: filtering never alters the counts of surviving tuples. - Projection pushdown, **provided** you keep every attribute needed above, and provided you accept that pushing a projection does not reduce cardinality. - Join reordering for inner joins, since multiplication is commutative and associative. Note the asymmetry: the surviving laws are exactly the ones that treat counts as an opaque multiplicative or additive factor, and the failing ones are exactly those that assumed a count of one. ## The design principle: multiplicity-insensitive contexts The useful way to hold all of this is not as a list of laws but as a single question the optimizer must answer at every node: **does anything above this point observe multiplicity?** Contexts that are multiplicity-**insensitive** — where duplicates may be freely introduced or removed: - Under an existential test: only presence matters. - Under `MIN`, `MAX`, or `COUNT(DISTINCT ...)`. - Under an explicit distinct or a grouping on the relevant attributes. - Under a set-semantics union or intersection. Contexts that are multiplicity-**sensitive**: - `COUNT(*)`, `SUM`, `AVG` — the entire point is the multiplicity. - A duplicate-preserving union. - The final result set returned to the client. - Anything feeding a `LIMIT`, where extra rows change which rows are returned. A sound optimizer propagates this property downward, and it is the licence for its two most valuable duplicate-related rewrites: pulling a dedup **up** (defer expensive work) or pushing it **down** (shrink an intermediate early, e.g. dedup the probe side of a join so it cannot fan out). Neither is valid without the analysis. Alongside it, engines track **functional dependencies and uniqueness**: if the join key is a key of the inner relation, the join cannot fan out, so the join-versus-semi-join distinction collapses and the rewrite becomes safe without any dedup at all. Uniqueness inference is therefore not a nicety — it is what unlocks the rewrites bag semantics otherwise forbid. ## Consequences for people writing queries - A union that adds counts and a union that dedups are different operators with different costs; picking the deduplicating one by default is a common and expensive habit, and picking the additive one carelessly is a correctness bug. - Joining on a non-unique attribute inflates every downstream aggregate. The failure mode is a plausible-looking number, not an error. - Adding an explicit distinct to "fix" inflated results usually masks a fan-out that should have been a semi-join, and it converts a streaming plan into a blocking one. ## Interview framing Define bags as counts, give three or four laws that fail with the count arithmetic that explains why, name what survives, and then land on the multiplicity-insensitivity principle plus uniqueness inference as the two things that actually govern which rewrites are legal. That is the principal-level answer.