Relational Calculus

Origin. E. F. Codd, "A relational model of data for large shared data banks" (1970) and "Relational completeness of data base sublanguages" (1972), where the calculus and the theorem relating it to the algebra both appear. Lacroix and Pirotte (1977) gave the domain variant. The founding result of database theory, and the reason SQL looks like logic and runs like algebra.

Models. First-order logic over a database schema. Where relational algebra says how to compute an answer — project, then join, then select — the calculus says what the answer is: the set of tuples satisfying a formula. Codd's theorem says the two express exactly the same queries, which is why a declarative language can have a procedural implementation, and why query optimization is possible at all.

Formalism.

Tuple relational calculus (TRC): { t | φ(t) } Variables range over tuples. t[A] projects attribute A. { t | R(t) ∧ t[age] > 30 } ∃, ∀, ∧, ∨, ¬ over tuple variables.

Domain relational calculus (DRC): { ⟨x₁, ..., xₙ⟩ | φ(x₁, ..., xₙ) } Variables range over attribute domains, not tuples. { ⟨n, a⟩ | R(n, a) ∧ a > 30 } QBE is DRC with a visual syntax.

Safety — the necessary restriction: { t | ¬R(t) } is infinite: the complement of a finite relation in an infinite domain. A query is safe if its answer is finite and depends only on the database, not the domain. Safety is undecidable in general; the syntactic range-restricted fragment is decidable and suffices.

Codd's theorem (relational completeness): Relational algebra ≡ safe TRC ≡ safe DRC. Each translates into the others effectively. "Relationally complete" means: at least as expressive as the algebra. SQL is.

What it cannot express: Transitive closure — reachability is not first-order (Aho–Ullman 1979). Hence Datalog, hence SQL's recursive WITH, hence the fixed-point extensions. Counting and aggregation also need extensions.

Relation to FOL: The calculus is first-order logic with the schema as signature, plus safety. Database theory is finite model theory with a query language attached — which is why Fagin's theorem and the 0-1 laws are database results too.

Symbols.

Symbol	Unicode	Name	Meaning
{ t \| φ(t) }	—	TRC query	Tuples satisfying φ
{ ⟨x̄⟩ \| φ(x̄) }	—	DRC query	Domain tuples satisfying φ
t[A]	—	Projection	Attribute A of tuple t
≡	U+2261	Equivalence	Codd's theorem
π, σ, ⋈	U+03C0	Algebra operators	Project, select, join

Metatheory. Codd's theorem is the reason the field exists: a declarative query language and a procedural one are interchangeable, so a user can state what they want and a system can decide how to get it — every query optimizer is that theorem in operation. Safety is the price and the interesting part: unrestricted the calculus is not domain-independent, and the undecidability of safety is what forces the syntactic range-restriction that every real language implements. The inexpressibility of transitive closure is the field's other founding negative result, and Datalog, recursive SQL, and the whole fixed-point-logic literature are responses to it.

Applies to. Query languages and their equivalence. SQL's semantics — SELECT is TRC, and the execution plan is the algebra. Query optimization, which is Codd's translation run backwards. Descriptive complexity, where the calculus is the first-order fragment. Finite model theory, of which database theory is an application.

Limitations. Safety is undecidable, so every implementation ships a syntactic approximation and rejects queries that are safe but not range-restricted. No transitive closure, no counting, no aggregation — all of which real queries need, and all of which are extensions that break the equivalence with the algebra. And the calculus assumes the closed-world assumption and a fixed schema; nulls, which every real database has, have no clean first-order treatment, which is why SQL's three-valued nulls are a known mess.