Relations as Sets: Why the Relational Model Excludes Duplicate Rows

A table that contains two identical rows is not a relation. That statement is stronger than it looks: it is not a rule about how data should be stored, but a consequence of the definition of the object the model is built from. Everything else in relational theory — keys, functional dependencies, normalization, the algebraic identities that query optimizers rely on — depends on relations being sets. SQL departs from this in one specific way, and the departure is the source of a large fraction of the surprises in everyday query writing.

A relation is a subset of a Cartesian product

Fix a finite set of attribute names A = {a1, …, an} and, for each attribute a in that set, a domain dom(a) — the set of values a may take. A tuple over A is a function that assigns to each attribute a value from its domain. A relation R over A is a set of such tuples.

Two consequences follow immediately from the word “set”. First, membership is decided by value: a tuple is in R or it is not, and there is no notion of a tuple appearing twice. Second, a set has no order, so neither the tuples nor the attributes carry a position. The names A1, …, An are what identify columns; the ordering of rows is not part of the value at all.

The size vocabulary is worth fixing, because the rest of the theory uses it. The number of attributes is the degree of the relation; the number of tuples is its cardinality. A relation of degree n over domains of sizes d1, …, dn is drawn from a Cartesian product of size d1 × … × dn, so its cardinality cannot exceed that product. For a boolean-valued attribute the domain has two elements, and a relation of degree n over such domains is a subset of 2^n possible tuples — that is, an element of the power set of the product. The set-of-subsets structure is exactly why the model is called relational rather than tabular.

Because a tuple is identified by its values, the phrase “duplicate row” is a contradiction in terms. If two rows agree on every attribute they are the same tuple, and a set contains it once. A relation is therefore a canonical representation of a fact: the same collection of facts has exactly one relational value, no matter what order the facts arrived in or how they are laid out on disk.

What SQL kept, and the one thing it changed

SQL tables are not relations. A table in SQL is a bag of rows: duplicate rows are permitted, and the language removes them only when asked. Three constructs make the difference visible.

SELECT without DISTINCT preserves duplicates, including duplicates introduced by a join. UNION ALL concatenates bags, while UNION eliminates duplicates. Aggregates distinguish the two readings: COUNT(*) counts rows, COUNT(DISTINCT x) counts distinct values of x, and AVG(x) averages over rows, so a duplicated row shifts the mean.

-- Bag semantics: the same order line counted once per matching shipment
SELECT o.id, COUNT(*) AS shipment_rows
FROM orders AS o
JOIN shipments AS s ON s.order_id = o.id
GROUP BY o.id;

-- Set semantics on the projected columns: one row per distinct (id, date)
SELECT DISTINCT o.id, s.ship_date
FROM orders AS o
JOIN shipments AS s ON s.order_id = o.id;

The second query is not a rewrite of the first. DISTINCT applies to the projected column list, so it collapses rows that agree on (id, ship_date) even when they differ in columns that were not selected. Duplicate elimination happens after projection, which is precisely the point at which the algebra would have eliminated duplicates implicitly.

SQL also keeps the no-order property. A table has no row order, and a query result has no order unless the statement says so with ORDER BY. A cursor opened over a query without an ordering clause returns rows in an order the implementation chooses, and that order may change between executions as plans or physical layout change. Code that depends on insertion order without naming an ordering column is relying on an unspecified property.

Projection is where duplicates would appear

In the relational algebra, projection takes a relation and a subset of its attributes and returns the relation consisting of those tuples restricted to the subset. If two tuples agreed on every attribute, they were one tuple; after restriction they may still differ on the dropped attributes but coincide on the kept ones. The result is a set, so the coinciding tuples merge.

This is the operator that makes duplicate elimination semantically necessary rather than optional. It is also the operator whose cost is easiest to underestimate. Eliminating duplicates from n tuples requires either sorting on the projected columns — O(n log n) comparisons, with external merge once the sort exceeds available memory — or building a hash table keyed by the projected values, O(n) expected time and memory proportional to the number of distinct results.

The memory figure is not small. Ten million tuples of roughly 100 bytes occupy about a gigabyte before any per-tuple overhead; a hash table holding the distinct keys at a 50% load factor needs on the order of one and a half to two gigabytes including bucket arrays and pointers, and spills to disk if it does not fit. Sorting has a comparable worst case but degrades more gracefully, because runs can be written out and merged. This is the concrete reason SQL chose bags: in the algebra duplicate elimination is free by definition, while in an implementation it costs a full pass and a large transient allocation, and many queries do not need the guarantee.

The design constraint behind value-based identity

Codd’s stated goal was data independence: applications should be insulated from how tuples are physically stored, and the model should describe data in terms of values rather than addresses. Sets deliver that directly. A relation has no hidden identity field, no row pointer, no insertion counter; a tuple is nothing but its attribute values.

The alternative design is a bag of records with physical or synthetic identifiers. That design makes duplicate rows meaningful — two records can carry the same values and still be different records — and it buys cheaper writes, since an append never has to check whether an equal tuple already exists. The price is that every algebraic identity has to be restated with multiplicities. Join is not idempotent on bags: joining a relation with itself multiplies tuple counts. Union is not idempotent either. Optimizers that reason about bags must track cardinality multipliers through every operator, and equivalence proofs become arithmetic over multiplicities rather than set membership.

Set semantics also gives a clean definition of query equivalence: two expressions are equivalent when they produce the same set of tuples for every database instance. That definition is what makes the algebraic rewrite rules — associativity and commutativity of join, pushing selection through projection, distributivity of join over union — provable rather than merely plausible. Under bag semantics the same rules hold only with side conditions on multiplicity, and a rewrite that ignores them changes results.

Keys are what replace row identity

With no row identifier, the only way to refer to a specific tuple is to describe it by values. A superkey is a set of attributes K such that no two tuples of the relation agree on all attributes in K. A candidate key is a superkey that is minimal: no proper subset of it is a superkey. One candidate key is chosen as the primary key, and the choice is a schema decision rather than a mathematical one.

The full attribute set is always a superkey, trivially, because no two distinct tuples agree on every attribute. A relation may therefore have no candidate key smaller than itself, and the model does not require one. SQL’s PRIMARY KEY does require it, which is a constraint the language adds rather than one the model implies.

Keys are the mechanism by which the model expresses relationships without pointers. A foreign key is a set of attributes whose values must appear as a key value in another relation; the reference is resolved by value comparison, not by an address. This is why referential integrity can be checked by an index lookup and why the same logical relationship survives a physical reorganization of either relation. The derivation of candidate keys from a set of declared dependencies is a separate mechanical procedure, covered in attribute closure and candidate keys, and the enforcement side of value-based references is treated in referential integrity and foreign key actions.

Where the distinction changes results

Three places in ordinary SQL work show the bag/set split directly.

Aggregating an aggregate is the classic error. Averaging per-group averages gives each group equal weight, while averaging over all rows weights groups by size; the two agree only when every group has the same cardinality. The query is well-formed under both readings and wrong under one of them.

IN and EXISTS are equivalent under set semantics when the subquery projects a key, and can differ under bags when the subquery projects a non-key column and the outer predicate is negated. The negated forms also interact with nulls, which is a separate matter taken up in nulls and three-valued logic.

Optimizer rewrites assume set semantics and then add multiplicity bookkeeping. Pushing a DISTINCT below a join is valid only when the join cannot multiply rows, which is the case when the join attributes form a key on one side. A rewrite engine that treats DISTINCT as freely movable will change cardinalities, and with them the cost estimates that drive plan choice.

The practical reading is that the relational model describes values, and SQL describes computations over bags of rows that are usually, but not always, sets. Knowing which of the two a given expression operates on is the difference between a query that means what it says and one that happens to return the right answer on the current data.