skip to content

Relational algebra is defined over sets, while a table in a SQL database is a multiset (bag). What practical differences does that create when you translate a projection into a SELECT column list?

level: middleimportance: should knowfreq 48%

answer

  1. algebra = set, SQL table = bag
  2. π ⇒ SELECT DISTINCT, not plain SELECT
  3. duplicates carry information for aggregates
  4. dedup = sort or hash, blocking, can spill
  5. plain keyword = set, ALL variant = bag

basics

~20 s

In set semantics, projecting drops duplicates automatically. SQL tables are bags, so a plain column list keeps every duplicate row and you must add DISTINCT to match the algebra. Duplicate elimination then costs a real sort or hash step.

solid answer

~50 s

The algebra's relations are **sets**: no duplicate tuples. So `π_{city}(customer)` yields each city once, with no extra syntax. SQL relaxed that to **bags** — a table may hold identical rows, and every operator propagates multiplicity — so `SELECT city FROM customer` returns one row per customer. Three practical consequences: 1. **DISTINCT is the missing half of π.** Translating algebra to SQL faithfully means writing `SELECT DISTINCT`; leaving it out is a semantic change, not a stylistic one. 2. **Duplicate elimination is an operator with a cost.** Engines implement it by sorting or hashing, so it can add memory pressure and spill to disk. It should be added because the semantics require it, not sprinkled defensively. 3. **Some algebraic laws weaken.** Set identities like `R ∪ R = R` fail for bags; SQL restores set behaviour explicitly (`UNION` deduplicates, `UNION ALL` does not). Bags were chosen deliberately: duplicates carry information for aggregation (a `SUM` over deduplicated rows is wrong) and forcing distinctness everywhere would be expensive.

code

sql · 8 lines
sql
-- bag: one row per payment, duplicates retained
SELECT amount FROM payment;              -- 500 rows

-- set: the algebra's projection
SELECT DISTINCT amount FROM payment;     -- 37 rows

-- duplicates are information here; DISTINCT would corrupt the total
SELECT SUM(amount) FROM payment;

go deeper

for a junior

Say that the algebra removes duplicates automatically while SQL keeps them, so a faithful projection needs DISTINCT.

for a middle

Explain why SQL chose bags — aggregation needs multiplicity, deduplication costs a sort or hash — and give the plain-keyword-versus-ALL pattern.

for a senior

Discuss implementation cost (sort vs hash, spill risk, when a unique constraint lets the planner drop the step) and the DISTINCT-hiding-a-fan-out anti-pattern.

for a principal

Frame it as choosing the right semantics per result contract and pushing distinctness enforcement into declared keys and pipeline boundaries rather than defensive query-level DISTINCT.

## Two different data models sitting one on top of the other Codd's relational algebra is defined over **relations**: a relation is a *set* of tuples over a heading. Two properties follow — tuples are unordered, and no tuple appears twice. Practical SQL systems implement a slightly different model: a table is a **bag** (multiset), where a tuple may appear with multiplicity greater than one, and operators are defined to propagate multiplicities. This single difference is the source of most of the confusion when people move between textbook algebra and real queries. ## Where it bites: projection In the algebra, `π_X(R)` is *the set of* X-restrictions of R's tuples, so collapsing duplicates is part of the definition — no extra operator, no extra cost in the model. In SQL, the `SELECT` list restricts columns but leaves multiplicity untouched. `SELECT department FROM employee` over 500 employees returns 500 rows. To reproduce π you must write `SELECT DISTINCT department FROM employee`. That is not a formatting preference; the two queries return different values. ## Why SQL chose bags It was not an oversight. - **Aggregation needs multiplicity.** `SELECT SUM(amount) FROM payment` must see every payment. If projection silently deduplicated, two payments of the same amount would collapse and the total would be wrong. Duplicates carry real information the moment you start counting or summing. - **Deduplication is expensive.** Making every intermediate result a set would force a sort or hash at every step. Bags let the engine stream tuples through pipelines without blocking. - **Streaming vs blocking.** A filter or a column trim is pipelined — a tuple arrives, a tuple leaves. Duplicate elimination is *blocking* in the hash case (it must build a table) or requires a sort; either way it introduces memory usage proportional to the number of distinct values and a potential disk spill. ## How duplicate elimination is actually implemented Two standard strategies: - **Sort-based**: sort the projected tuples, then discard adjacent equals. Cost roughly O(n log n), memory bounded by the sort's working set, spills to temp storage when it exceeds the allotted memory. - **Hash-based**: build a hash table keyed by the projected tuple, emitting the first occurrence of each key. Memory scales with the number of *distinct* values, which is why a high-cardinality DISTINCT can be far more expensive than a low-cardinality one. A third, cheapest outcome: **prove it unnecessary**. If the projected list contains a key or unique constraint, distinctness is guaranteed and the operator is removed. If an index already delivers the rows in sorted order on the projected attributes, the sort disappears and only the adjacent-duplicate discard remains. ## Laws that change between sets and bags - **Idempotence of union fails.** `R ∪ R = R` for sets; for bags, `R UNION ALL R` doubles every multiplicity. - **Projection over a disjunction rewrite needs care.** `σ_{p∨q}(R)` rewritten as `σ_p(R) ∪ σ_q(R)` is exact for sets; for bags a tuple satisfying both branches would be emitted twice unless the union deduplicates. - **Difference changes shape.** Set difference is all-or-nothing per tuple; bag difference must decide how to subtract multiplicities. SQL's `EXCEPT` deduplicates, `EXCEPT ALL` subtracts counts. - **Selection is the well-behaved one.** Filtering a bag preserves each surviving tuple's multiplicity, and filtering a set yields a set, so σ needs no reinterpretation at all. SQL's design pattern is consistent: the plain keyword (`UNION`, `INTERSECT`, `EXCEPT`, `DISTINCT`) gives you set semantics, and the `ALL` variant — or the absence of `DISTINCT` — gives you bag semantics. ## How to use this in practice The healthy discipline is to decide, per query, which semantics the *answer* needs. - If the output is a lookup list of categories or a set of identifiers to feed elsewhere, you want set semantics — write DISTINCT and mean it. - If the output feeds counting, summing, or per-row processing, duplicates are data and DISTINCT is a bug. - If DISTINCT is being used to paper over an unintended row multiplication — typically a join fanning out on a non-unique key — the fix is the join, not the deduplication. A DISTINCT bolted on to hide a fan-out both masks the design problem and pays the sort/hash cost forever. That last point is what interviewers usually want to hear: understanding *why* the set/bag distinction exists is what separates "I add DISTINCT until the numbers look right" from "I know which model this result should live in."

  • A report is over-counting after a join, and someone adds DISTINCT and the numbers look right. What would you say in review?
    That DISTINCT is treating a symptom. Over-counting after a join usually means the join key is not unique on one side, so rows fan out; collapsing them afterwards happens to fix a count of distinct entities but will silently corrupt any sum or average over the fanned-out rows. The right fix is to aggregate or filter the many-side to one row per key before joining, or to use a semi-join if you only need existence.
  • Why is duplicate elimination sometimes free and sometimes the most expensive operator in a plan?
    It is free when the engine can prove distinctness — the projected columns include a unique key, or an index already returns rows sorted on those columns so only adjacent duplicates need discarding. It becomes expensive when neither holds and a full sort or hash build is required over many distinct values, since memory scales with the distinct count and exceeding the budget forces a spill to temporary storage.

A set is a guest list — a name is on it or it isn't. A bag is the turnstile count at the door: the same person entering twice matters, and you would be wrong to collapse them when you are counting attendance.

saying these in an interview costs you the question

  • Believing SQL tables are sets and cannot contain duplicate rows.
  • Treating DISTINCT as cosmetic rather than a semantic and cost-bearing change.
  • Adding DISTINCT to hide a join fan-out instead of fixing the join.
  • Claiming duplicates are always noise, ignoring that aggregates depend on multiplicity.
  • Assuming set identities such as R ∪ R = R still hold for bag operators.

context

resolving links…