Symptom

You write:

SELECT name FROM users WHERE age > 30 AND city = 'Berlin';

You did not say whether to scan the table or use an index. You did not say which of the two predicates to apply first. You did not say anything about join order, because there is no join, but if there were you would not have said that either.

Something decides all of it, and gets it right often enough that you have never thought about it. Then one day the plan flips, a query that ran in 40 ms takes 90 seconds, and you discover there was an optimizer in there making choices.

The question underneath: why is this possible at all? In every other part of your system, saying what you want without saying how is a wish rather than a language feature. You cannot write “sort this efficiently” in C and have the compiler pick an algorithm. Why do databases get to be declarative when nothing else is?

Because of a theorem from 1972 that says the declarative language and the procedural language describe exactly the same set of queries.

Statement

Two languages over relations.

Relational algebra is procedural: five primitive operators — selection $\sigma$, projection $\pi$, Cartesian product $\times$, union $\cup$, and difference $-$ — composed into an expression tree. Reading it top-down tells you what to compute and in what order.

Relational calculus is declarative: a first-order logic formula describing which tuples belong in the answer, with no order of operations at all.

Codd’s theorem. Relational algebra and safe relational calculus have exactly the same expressive power. Every query in one has an equivalent in the other, and the translation is effective.

Let $\mathcal{RA}$ be the relational algebra over the five primitive operators and $\mathcal{RC}{\text{safe}}$ be domain-independent relational calculus formulas. Then $\mathcal{RA} \equiv \mathcal{RC}{\text{safe}}$, and both are equivalent to $\mathcal{DRC}$ and $\mathcal{TRC}$ under the safety restriction. The resulting query class is exactly the first-order queries, sometimes written $\mathbf{FO}$, and a language with this expressiveness is called relationally complete.

The word safe carries the load. ${t : \neg R(t)}$ — everything not in $R$ — is a perfectly grammatical calculus formula whose answer is infinite, or at least depends on what domain you assume. Such formulas are excluded. The correspondence is with the domain-independent fragment, whose answers depend only on the data present.

Argument

Why the theorem licenses the optimizer. This is the practical content, and it is worth stating precisely.

You write a declarative formula. It has an algebraic equivalent, guaranteed by the theorem. Algebraic expressions obey equational laws: selection commutes with itself, selection pushes through joins, joins are associative and commutative, projections can be pushed down. So the system may rewrite your query into any equivalent algebraic form and evaluate that instead.

The optimizer is a theorem prover searching an equivalence class, and the theorem is what guarantees the class is non-empty and that the declarative form has a member of it to start from. Without Codd’s theorem, “declarative query language” would be an aspiration with no evaluation strategy behind it.

The rewrite that pays for the whole apparatus. Consider users with 10 million rows joined to orders with 100 million, filtered to one city holding 0.1% of users.

Naive order: compute the join first, producing on the order of 100 million rows, then filter. Pushing the selection down first: filter users to 10,000 rows, then join. The intermediate result drops from $10^8$ to something on the order of $10^5$, a factor of about a thousand in rows materialized, and correspondingly in I/O and memory.

The user wrote neither plan. The user wrote a formula. Selection pushdown is an algebraic identity, $\sigma_p(R \bowtie S) = \sigma_p(R) \bowtie S$ when $p$ mentions only $R$’s attributes, and the optimizer applied it because it is sound by algebra rather than by heuristic.

Join order is where the search actually happens. For $n$ relations the number of distinct join orders is large: the count of binary trees with $n$ labelled leaves is $\frac{(2n-2)!}{(n-1)!}$, which is 2 for $n=2$, 12 for $n=3$, 120 for $n=4$, 1680 for $n=5$, and 17,297,280 for $n=8$. Join ordering is NP-hard, which is why PostgreSQL switches from exhaustive dynamic programming to a genetic algorithm at 12 relations by default (geqo_threshold), and why a query with twenty joins can have a planning time that is itself measurable.

The proof direction that is interesting. Algebra-to-calculus is straightforward: each operator has a direct logical reading, $\sigma$ is conjunction with a predicate, $\times$ is conjunction of two atoms, $-$ is negation, $\pi$ is existential quantification.

Calculus-to-algebra is where safety matters. Quantifiers translate to projection and difference, but a universally quantified or negated subformula ranges over a domain, and the domain must be bounded by something present in the database. The standard construction builds the active domain — the finite set of values actually appearing in the relations — as an algebraic expression, then relativizes every quantifier to it. Safety is exactly the condition making that sound.

Why SQL is not quite this. SQL is relationally complete and then some. It has aggregation (COUNT, SUM, GROUP BY), which first-order logic does not, and recursive CTEs, which are genuinely beyond FO. It also has bag semantics rather than set semantics: duplicates are preserved, so UNION ALL is not the algebra’s $\cup$, and this affects which rewrites are legal. And NULL introduces three-valued logic, so WHERE x = x does not select every row. SQL is a superset of the theorem’s language with a different underlying logic in three places, and each of those places is a well-known source of surprise.

Forbids

Transitive closure in pure relational algebra. “Find all employees reporting transitively to Alice” is not a first-order query. The proof is a standard Ehrenfeucht-Fraïssé or locality argument: FO queries cannot count unboundedly or reach unbounded distances. This is why SQL needed WITH RECURSIVE added in SQL:1999 as a genuine extension rather than sugar.

Counting and aggregation in FO. “Departments with more than five employees” is not expressible. COUNT is an extension.

Evaluating unsafe queries. NOT IN against an unbounded domain has no finite answer. Databases sidestep this by making every query implicitly range over stored relations.

An optimizer that is always right. The equivalences are sound, and choosing among them requires cost estimates from cardinality statistics, which are approximations. Plan regressions are estimation failures, not algebra failures.

Does not forbid

It does not mean all relational languages are equally usable, which is the misreading that makes the theorem sound like a triviality. Equal expressive power says nothing about ergonomics or performance. Datalog expresses recursion that SQL needed thirty years to add; LINQ, Django’s ORM, and jOOQ all target the same expressive class with very different developer experience, and the choice among them is a human-factors decision the theorem is silent on.

It does not mean NoSQL abandoned it. MongoDB’s aggregation pipeline is essentially relational algebra with different syntax; Cassandra’s CQL is deliberately a restricted fragment, forbidding joins and arbitrary WHERE so that every query has a predictable cost. Restricting expressiveness on purpose, to make performance legible, is a defensible design and the theorem is what tells you exactly what was given up.

It does not forbid procedural escape hatches. Stored procedures, UDFs, and window functions all go beyond FO, and databases provide them precisely because some computations are not first-order.

It does not mean the optimizer removes the need to understand plans. Codd’s theorem guarantees an equivalent plan exists; it does not guarantee the optimizer finds the good one. EXPLAIN ANALYZE exists because cardinality estimation is hard, and correlated predicates in particular are routinely misestimated by orders of magnitude.

It does not say the relational model is the only one with this property. The same shape of theorem appears for regexes and finite automata (T039) and across the Chomsky hierarchy (T038): two formalisms, one expressive power, with the declarative one being what humans write and the procedural one being what machines run. That pattern is the reason compilers and optimizers exist at all.

Boundary

  • First-order only. No recursion, no aggregation, no transitive closure. Every practical system extends past this line.
  • Set semantics. SQL’s bags change which identities hold. SELECT DISTINCT is not a cosmetic difference.
  • Two-valued logic. NULL and three-valued logic break several rewrites that are sound in the algebra, and this is a documented source of optimizer bugs across vendors.
  • No cost model. The theorem says an equivalent expression exists, not that you can find the cheapest one. That search is NP-hard.
  • Complexity, for the record. FO query evaluation is in $\mathbf{AC}^0$ in data complexity — the query is fixed, the database grows — which is why relational queries parallelize so well. In combined complexity, where the query is part of the input, it is PSPACE-complete.

The idea to carry: declarative languages are possible exactly where a theorem guarantees a procedural equivalent. SQL is not declarative because someone designed a nice syntax; it is declarative because Codd proved the translation exists, and every query planner since has been an implementation of that proof with a cost model bolted on.