Set vs Bag Semantics

## Sets and bags A set is an unordered collection where an element is present or absent - 'present twice' is not expressible. A bag (multiset) is also unordered, but each element carries a multiplicity: how many copies it holds. As bags, {a, a, b} and {a, b} are different collections; as sets they are the same. ## The model uses sets Codd defined a relation as a set of tuples drawn from attribute domains. Three things follow. First, duplicate tuples cannot exist, so every relation has at least one candidate key - in the worst case all attributes together. Second, there is no row order and no row identity beyond the values themselves: you address a tuple only by its values. Third, the algebra is closed over sets - projecting a relation onto some attributes yields a relation, which means duplicate rows produced by dropping columns simply disappear. ## SQL chose bags SQL tables and query results are bags. There are three reasons. (1) Cost: eliminating duplicates requires comparing every row against every other, which in practice means sorting or hashing the entire intermediate result. Doing that after each projection would be a permanent tax paid mostly for nothing. (2) Information: duplicates are the raw material of aggregation. If projecting 'amount' out of an orders table collapsed equal amounts, summing or averaging them would be impossible. (3) Reality: a table with no key constraint physically can contain identical rows, and engines identify rows by a physical address (row id, tuple id), not by value - so the storage layer is a bag regardless. Concretely, SQL operators are multiset operators: a scan returns each stored row once, a filter removes rows but never merges them, a projection keeps multiplicity, a join produces one output row per matching pair (multiplying multiplicities), and a concatenating union adds them. Only an explicit duplicate-eliminating request, a set-flavoured union, or grouping converts a bag back into a set. ## Where the difference bites **Result size.** Projecting to fewer columns never shrinks a bag, so 'select just the customer id' from a million-row order table still returns a million rows, not one per customer. **Aggregate correctness.** Counting rows is not counting entities. If a row has been duplicated by a join, sums and averages are inflated, and averages are skewed in a way that no scaling factor fixes. **Result comparison.** Two queries are equivalent only if they produce the same multiset. Test assertions and data-diff tooling that compare 'the same rows' while ignoring counts will pass on genuinely different results. **Optimization.** A rewrite that is valid over sets may change multiplicities, so the optimizer must reason about duplicate preservation, not just membership. ## Getting set semantics back The robust way is a declared key or unique constraint: it makes the table a set by construction, is enforced on every write, and lets the planner prove that a duplicate-elimination step is unnecessary and remove it. The per-query way is explicit duplicate elimination, which is correct but pays sort or hash cost on every read and often hides a fan-out bug rather than fixing it. Practical rule: give every table a key, treat a required duplicate-removal step as a signal to investigate, and always know whether you are counting rows or counting entities.