SQL looks like English, but underneath it is algebra: a small set of operators over relations, closed under composition, with equivalence laws a query optimizer exploits exactly the way ordinary algebra simplifies expressions. Knowing the algebra is what turns EXPLAIN plans from runes into readable rewritings of your query. This is the database-theory course companion to Relational Database Fundamentals (ACID, normal forms) and Query Optimization (the practice).
A relation is a set of tuples over named, typed attributes — the theory's version of a table, with two deliberate idealizations SQL relaxes: no duplicate rows (sets, not bags) and no row order. Codd's insight (1970) was data independence: programs address data by name and predicate, never by physical location, freeing storage layout to change under a stable logical interface — the founding contract every index, partition, and optimizer trick lives inside.
Six primitives generate the algebra:
| Operator | Symbol | SQL shadow | Meaning |
|---|---|---|---|
| Selection | \sigma_{p}(R) | WHERE | Keep rows satisfying predicate p |
| Projection | \pi_{A}(R) | SELECT columns | Keep attributes A |
| Cartesian product | R \times S | CROSS JOIN | All row pairs |
| Union | R \cup S | UNION | Set union (compatible schemas) |
| Difference | R - S | EXCEPT | Rows in R not in S |
| Rename | \rho | AS | Rename relation/attributes |
Everything else is derived: join — written R ⋈ S — is a filtered Cartesian product, \sigma_{p}(R \times S), which is exactly how to think about join semantics even though no engine executes it that way; intersection R \cap S = R - (R - S); division ("suppliers who supply all parts") composes from difference and product. Outer joins and aggregation are extensions beyond the classical algebra — as are SQL's bag semantics and NULL, each a pragmatic departure with real semantic consequences (three-valued logic is why NOT IN with NULLs returns nothing and why WHERE x <> y silently drops NULL rows).
A basic block translates mechanically:
SELECT c.name, o.total -- π (projection, last)
FROM customers c JOIN orders o ON c.id = o.cust_id -- ⋈ (join)
WHERE o.total > 100 -- σ (selection)
is π over σ over the join: π(name,total) ( σ(total>100) ( C ⋈ O ) ). Subqueries, EXISTS, and IN translate to joins and semijoins; GROUP BY adds a grouping operator atop the algebra. The translation is the optimizer's first act: parse SQL into an algebraic tree, then rewrite.
The algebra's laws are the optimizer's license:
σ(p)(R ⋈ S) = σ(p)(R) ⋈ S when the predicate touches only R — filter early, join less. The single most important rewrite, and the same idea reappears as predicate pushdown in Parquet scanning.SELECT * genuinely costs.(R ⋈ S) ⋈ T may be reordered freely — the join-order search space the optimizer explores with cardinality estimates, and the reason bad statistics produce bad plans.An EXPLAIN plan is precisely the algebraic tree the optimizer settled on, annotated with physical operator choices (hash vs merge vs nested-loop join) and cost estimates — reading one is reading algebra. When the plan is wrong, the cause is almost always cardinality estimation, and the fix (statistics, rewrites, hints) operates on this tree; the operational side lives in Query Optimization.
A functional dependency X \to Y says X-values determine Y-values; a candidate key is a minimal attribute set determining the whole relation. Armstrong's axioms (reflexivity, augmentation, transitivity) derive all implied dependencies, and the normal forms of database design are statements about which dependencies a well-formed relation may contain — BCNF in one line: every determinant is a candidate key. The algebra closes the loop: normalization decomposes relations by projection, and the losslessness of a decomposition is the guarantee that the natural join reassembles exactly the original — no spurious tuples, no lost ones.
Declarative queries + algebraic rewriting is the most successful optimization story in software: you state what, the engine derives a good how, and fifty years of hardware change hid behind the interface. The same pattern now powers dataframe lazy engines and distributed SQL — Polars' query plans and Spark's Catalyst are relational algebra with new costumes.