Tuple Relational Calculus: short notes (Database Management Systems)

Introduction

Tuple relational calculus (TRC) is a declarative query language: a query states the property that answer tuples must satisfy and says nothing about how to compute them. A TRC query has the form $\{ t \mid P(t) \}$ , "the set of tuples $t$ for which the formula $P$ is true", where $P$ is a formula of first-order logic over the database.

Relational algebra and safe TRC have exactly the same expressive power (Codd's theorem), so every algebra expression has a calculus equivalent and the other way round. The two basic tasks are to say what a given TRC expression returns, or which of several expressions expresses an English query. The points that need most care are the placement of quantifiers, writing $\wedge$ where $\Rightarrow$ is needed under $\forall$ , and safety.

Prerequisites

Relational Algebra: the operators whose meaning TRC must reproduce, especially division.
First-Order Logic: quantifiers, free and bound variables, negating nested quantifiers.

Core concepts

Tuple variables range over tuples. A formula is built from atoms:

Atom	Meaning
$t \in R$	$t$ is a tuple of relation $R$
$t.A \;\theta\; s.B$	comparison of two attribute values, $\theta \in \{=, \neq, <, \leq, >, \geq\}$
$t.A \;\theta\; c$	comparison with a constant

Formulas combine atoms with $\neg$ , $\wedge$ , $\vee$ , $\Rightarrow$ and the quantifiers $\exists s \in R\,(P)$ and $\forall s \in R\,(P)$ . The bounded forms abbreviate $\exists s\,(s \in R \wedge P)$ and $\forall s\,(s \in R \Rightarrow P)$ .

Free and bound variables. A variable is bound inside the scope of a quantifier on it and free otherwise. In $\{ t \mid P(t) \}$ , $t$ must be the only free variable of $P$ .

Equivalences used constantly.

$\forall s\,(P) \equiv \neg \exists s\,(\neg P)$ and $\exists s\,(P) \equiv \neg \forall s\,(\neg P)$ .
$P \Rightarrow Q \equiv \neg P \vee Q$ .
$\exists$ distributes over $\vee$ ; $\forall$ distributes over $\wedge$ ; neither distributes over the other connective.

Safety

The formula $\{ t \mid \neg (t \in R) \}$ describes every tuple that is not in $R$ , over all possible values, an infinite set. Here safe requires domain independence: for every database instance, evaluating the formula over any ambient domain containing its active domain gives the same answer, whose values lie in that active domain. The domain of the formula, $\text{dom}(P)$ , comprises values in its mentioned relations plus its constants. An output-value bound alone is insufficient: unbounded quantifiers can change truth when the ambient domain grows. Syntactically range-restricted formulas bound output attributes to relation values/constants and bound quantified variables correctly, providing a sufficient safe fragment. Only safe expressions are allowed; safe TRC is exactly as expressive as relational algebra.

How it works: reading an expression

Read a TRC expression from the outside in:

The target tuple $t$ and what it must belong to (its schema comes from the attributes used on it).
Each $\exists$ is "there is some row such that"; each $\forall s \in R$ is "for every row of $R$ ".
Translate the inner comparison last.

Translation table.

Relational algebra	Tuple relational calculus
$\sigma_{A = 5}(R)$	$\{ t \mid t \in R \wedge t.A = 5 \}$
$\pi_A(R)$	$\{ t \mid \exists r \in R\,(t.A = r.A) \}$
$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.B = S.B} S$ projected on $A, C$	$\{ t \mid \exists r \in R\, \exists s \in S\,(r.B = s.B \wedge t.A = r.A \wedge t.C = s.C) \}$
$R(X, Y) \div S(Y)$	$\{ t \mid \exists r \in R\,(t.X = r.X) \wedge \forall s \in S\, \exists r_2 \in R\,(r_2.X = t.X \wedge r_2.Y = s.Y) \}$

Algorithms and pseudocode

For the syntactically range-restricted fragment taught here, with all quantified variables bounded to relations and output attributes range-bound, evaluate by brute force over the domain of the formula. Do not apply this algorithm to arbitrary formulas merely because their current output lies in the active domain:

Text

EVAL-TRC({t | P(t)})
  D <- dom(P)                          // values in mentioned relations plus constants
  answer <- empty set
  for each tuple t over D with the target attributes
      if P(t) is true, evaluating
           exists s in R (Q) as: some row s of R makes Q true
           forall s in R (Q) as: every row s of R makes Q true
      then add t to answer
  return answer

For this bounded fragment, time is exponential in the nesting depth of quantifiers (each quantifier loops over a relation), polynomial in the data for a fixed query.

Mathematical explanation

Why $\forall$ needs $\Rightarrow$ . An unbounded $\forall s\,(s \in S \wedge Q)$ asserts that every tuple $s$ whatever is in $S$ , which is false as soon as the domain has a tuple outside $S$ . The intended "every $s$ of $S$ satisfies $Q$ " is $\forall s\,(s \in S \Rightarrow Q)$ , which is true for tuples outside $S$ vacuously. Dually, $\exists s\,(s \in S \Rightarrow Q)$ is almost always true (any $s$ outside $S$ satisfies it), so $\exists$ pairs with $\wedge$ .

Why safety matters. $\{ t \mid \neg (t \in R) \}$ over the domain of $R$ alone is the complement of $R$ within that domain; over any larger domain the answer grows. An expression whose answer depends on the domain chosen is not a well-defined query, and domain-independent safety rules it out. Even an active-domain-bounded output can be unsafe: for unary R={1}, the query {t in R | forall s (s in R)} returns {1} over domain {1} but nothing over {1,2}; the unbounded quantifier is the problem.

Why $\exists$ does not distribute over $\wedge$ . $\exists x\,(P(x) \wedge Q(x))$ needs one witness for both; $\exists x\,P(x) \wedge \exists x\,Q(x)$ allows two different witnesses. The second is weaker.

Worked examples

All examples use Enrolled(sid, cid) = $\{(s_1, c_1), (s_1, c_2), (s_1, c_3), (s_2, c_1), (s_2, c_3), (s_3, c_2), (s_3, c_3), (s_4, c_1), (s_4, c_2), (s_4, c_3)\}$ and Req(cid) = $\{c_1, c_3\}$ from Relational Algebra.

Example 1: selection and projection. $\{ t \mid \exists e \in \text{Enrolled}\,(e.cid = c_2 \wedge t.sid = e.sid) \}$ returns the students enrolled in $c_2$ : $\{s_1, s_3, s_4\}$ .

Example 2: division. $\{ t \mid \exists e \in \text{Enrolled}\,(t.sid = e.sid) \wedge \forall q \in \text{Req}\, \exists e_2 \in \text{Enrolled}\,(e_2.sid = t.sid \wedge e_2.cid = q.cid) \}$ returns the students enrolled in every required course: $\{s_1, s_2, s_4\}$ , the same as $\text{Enrolled} \div \text{Req}$ .

Example 3: the $\wedge$ trap. Replace the bounded $\forall q \in \text{Req}$ by $\forall q\,(q \in \text{Req} \wedge \ldots)$ with $q$ ranging over the course values of the domain, $\{c_1, c_2, c_3\}$ . The tuple with $q.cid = c_2$ is not in Req, so the body is false for it and the answer is empty.

Example 4: negation. $\{ t \mid \exists e \in \text{Enrolled}\,(t.sid = e.sid) \wedge \neg \exists e_2 \in \text{Enrolled}\,(e_2.sid = t.sid \wedge e_2.cid = c_1) \}$ returns students not enrolled in $c_1$ : $\{s_3\}$ .

Example 5: an unsafe query. $\{t\mid\neg(t\in\text{Enrolled})\}$ . Use the same global untyped active domain as EVAL-TRC and Example 7: its 4 student and 3 course values give $|D|=7$ , hence $7^2=49$ two-field tuples, of which 10 belong to Enrolled. The active-domain complement contains 39 tuples, including ill-typed pairs; it is not just the two missing student-course enrolments. Adding one new global value gives $8^2-7^2=15$ additional pairs. Over an unrestricted domain, the complement can be infinite: this illustrates why the query is unsafe.

Example 6: maximum. For $R(A) = \{3, 7, 5\}$ , $\{ t \mid t \in R \wedge \neg \exists s \in R\,(s.A > t.A) \}$ returns $\{7\}$ . Changing $>$ to $\geq$ returns the empty set, because every $t$ has $s = t$ with $s.A \geq t.A$ .

Example 7: division by double negation, and the empty divisor. Rewrite $\forall q \in \text{Req}\, P$ as $\neg \exists q \in \text{Req}\, \neg P$ :

\{ t \mid \exists e \in \text{Enrolled}\,(t.sid = e.sid) \wedge \neg \exists q \in \text{Req}\, \neg \exists e_2 \in \text{Enrolled}\,(e_2.sid = t.sid \wedge e_2.cid = q.cid) \}

Read it from the inside: "there is no required course $q$ for which there is no enrolment of $t$ in $q$ ".

With Req $= \{c_1, c_3\}$ : $s_3$ fails (no enrolment in $c_1$ ); the answer is $\{s_1, s_2, s_4\}$ , the same as Example 2 and the algebra division.
With Req empty: $\exists q \in \text{Req}$ is false for every $t$ , so the body is true and every enrolled student qualifies: $\{s_1, s_2, s_3, s_4\}$ . This matches $R \div \emptyset = \pi_X(R)$ .
Drop the range condition $\exists e \in \text{Enrolled}\,(t.sid = e.sid)$ and keep Req empty: now the body is true for every value $t$ of the domain, including the course names, so the answer is all 7 values $s_1, \ldots, s_4, c_1, c_2, c_3$ . The expression is unsafe; the range condition is what keeps it safe. With Req $= \{c_1, c_3\}$ the same expression happens to return $\{s_1, s_2, s_4\}$ , which hides the problem.

The SQL form is the double NOT EXISTS of SQL Subqueries and Views, and it gives the same two answers on these tables.

Important properties and observations

Codd's theorem. Safe TRC, safe domain relational calculus and relational algebra (the six basic operators) are equally expressive.
TRC has set semantics like the algebra; SQL's duplicates and aggregates are outside it.
Every query needs a "range" for $t$ . Without a conjunct such as $t \in R$ or $\exists r \in R\,(t.A = r.A)$ , $t$ is unrestricted and the query is usually unsafe.
Negation turns quantifiers. $\neg \forall s \in S\,(P) \equiv \exists s \in S\,(\neg P)$ : "not every required course" means "some required course missing".
Strict versus non-strict comparisons change answers at the boundary, as in Example 6.

Related material. Domain relational calculus uses variables over attribute values instead of tuples, for example $\{ \langle x \rangle \mid \exists y\,(\langle x, y \rangle \in \text{Enrolled} \wedge y = c_2) \}$ ; its safety condition and expressive power match TRC.

Common misconceptions.

" $\forall s\,(s \in S \wedge P)$ means every $s$ in $S$ satisfies $P$ ." It means every tuple is in $S$ and satisfies $P$ , almost always false.
"Any first-order formula is a valid query." Only safe ones.
" $\neg \exists$ and $\exists \neg$ are the same." They are not: "no row satisfies" versus "some row fails".

GATE examination perspective

What does the expression return? Evaluate on the given instance, quantifier by quantifier.
Which expression means "for all"? Look for $\forall$ paired with $\Rightarrow$ (or a bounded $\forall$ ), or the double negation $\neg \exists \ldots \neg \exists$ .
Equivalence to algebra. Match a TRC expression with the algebra expression (division, difference, join and projection).
Safety. Identify the unsafe expression among options: a negated membership with no positive range for $t$ .

Summary

A TRC query $\{ t \mid P(t) \}$ returns the tuples satisfying a first-order formula; $t$ is its only free variable.
Atoms: $t \in R$ , $t.A \;\theta\; s.B$ , $t.A \;\theta\; c$ .
Bounded $\exists s \in R$ means $\exists s\,(s \in R \wedge \ldots)$ ; bounded $\forall s \in R$ means $\forall s\,(s \in R \Rightarrow \ldots)$ .
$\forall$ goes with $\Rightarrow$ , $\exists$ goes with $\wedge$ .
Division in TRC is $\forall$ over the divisor with an $\exists$ inside.
Safe expressions take every answer value from the domain of the formula; $\{ t \mid \neg (t \in R) \}$ is unsafe.
Safe TRC equals relational algebra in expressive power (Codd's theorem).
$\exists$ distributes over $\vee$ , $\forall$ over $\wedge$ , and not the other way round.

Relational Algebra: prerequisite; every TRC query here has an algebra equivalent.
First-Order Logic: prerequisite; quantifier rules and negation.

Tuple Relational Calculus

Introduction

Prerequisites

Core concepts

Safety

How it works: reading an expression

Algorithms and pseudocode

Mathematical explanation

Worked examples

Important properties and observations

GATE examination perspective

Summary

Sources

Next steps

Introduction

Prerequisites

Core concepts

Safety

How it works: reading an expression

Algorithms and pseudocode

Mathematical explanation

Worked examples

Important properties and observations

GATE examination perspective

Summary

Related topics

Sources

Next steps