Tuple Relational Calculus

Declarative queries in tuple relational calculus — tuple variables, atoms, connectives and quantifiers, free and bound variables, translating between calculus and algebra (selection, projection, join, difference, division), expressing "for all" with negated existentials, safety, domain relational calculus in brief, and Codd's theorem on expressive equivalence.

Declarative vs procedural

Relational algebra describes how to compute a result (a sequence of operations). Relational calculus describes what the result must satisfy, in first-order logic; SQL's WHERE EXISTS / NOT EXISTS style is calculus in disguise.

Tuple relational calculus (TRC)

A query has the form

\{\,t \mid P(t)\,\} \quad\text{or}\quad \{\,t.A_1, \dots, t.A_k \mid P(t)\,\},

the set of tuples $t$ (or chosen attributes of them) for which the formula $P$ is true.

Atoms:

$t \in R$ — $t$ is a tuple of relation $R$ ;
$t.A \;\theta\; s.B$ or $t.A \;\theta\; c$ with $\theta \in \{=, \ne, <, \le, >, \ge\}$ .

Formulas combine atoms with $\wedge, \vee, \neg, \Rightarrow$ and the quantifiers $\exists s\,(\dots)$ and $\forall s\,(\dots)$ .

A variable is bound if it is quantified, free otherwise; the result variables are the free ones.

Translating between algebra and calculus

Algebra	Tuple relational calculus
$\sigma_{c}(R)$	$\{t \mid t \in R \wedge c(t)\}$
$\pi_{A}(R)$	$\{t.A \mid t \in R\}$
$R \cup S$	$\{t \mid t \in R \vee t \in S\}$
$R - S$	$\{t \mid t \in R \wedge \neg(t \in S)\}$
$R \bowtie_{R.a = S.a} S$	$\{\langle r, s\rangle \mid r \in R \wedge s \in S \wedge r.a = s.a\}$
semi-join ("has a match")	$\{t \mid t \in R \wedge \exists s\,(s \in S \wedge s.a = t.a)\}$
anti-join ("has no match")	$\{t \mid t \in R \wedge \neg\exists s\,(s \in S \wedge s.a = t.a)\}$
$R \div S$	$\{t.x \mid t \in R \wedge \forall s\,(s \in S \Rightarrow \exists u\,(u \in R \wedge u.x = t.x \wedge u.y = s.y))\}$

Universal quantifiers

$\forall s\,(s \in S \Rightarrow P(s))$ means "every tuple of $S$ satisfies $P$ "; it is equivalent to $\neg\exists s\,(s \in S \wedge \neg P(s))$ . "For all" questions (division, "enrolled in every course", "greater than all salaries") use it.

Safety

An expression is safe if its result is guaranteed to be finite and to contain only values appearing in the database (its active domain). Unsafe examples: $\{t \mid \neg(t \in R)\}$ (infinitely many tuples), $\{t \mid t.a > 5\}$ (no relation restricts $t$ ). Practical rule: every free variable must be bound to a relation by a positive atom $t \in R$ .

Codd's theorem: relational algebra, safe tuple relational calculus and safe domain relational calculus have exactly the same expressive power ("relational completeness"). None can express recursive queries such as transitive closure (ancestors of a node) — SQL adds WITH RECURSIVE for that.

Domain relational calculus (DRC) in brief

Variables range over values:

\{\,\langle n, d\rangle \mid \exists i\,\exists s\,(\langle i, n, d, s\rangle \in \text{Emp} \wedge s > 50000)\,\}

returns names and departments of employees earning over 50000. DRC underlies Query-by-Example interfaces.