Tuple relational calculus

Why it exists

Relational algebra says how to compute an answer (a sequence of operators). The relational calculus says what the answer is: a logical condition that the tuples of the answer must satisfy. SQL is based on this declarative idea. GATE asks: what does this calculus expression return, write a query in calculus, which expressions are safe, translate between algebra and calculus.

Prerequisites

You need relational algebra (relational algebra) and first-order logic with quantifiers (the logic course).

Precise definitions

A tuple variable $t$ takes tuples as values. The range of a variable is given by an atom $R(t)$ or $t \in R$.

Atoms:

• $R(t)$ (or $t \in R$): $t$ is a tuple of relation $R$;
• $t.A \,\theta\, s.B$ or $t.A \,\theta\, c$, where $\theta \in \{=, \ne, <, \le, >, \ge\}$ and $c$ is a constant.

Formulas are built from atoms with $\wedge, \vee, \neg, \Rightarrow$ and the quantifiers $\exists t\,(P)$ ("there is a tuple $t$ such that $P$") and $\forall t\,(P)$ ("for every tuple $t$, $P$"). The rule $\Rightarrow$: $P \Rightarrow Q \equiv \neg P \vee Q$. The quantifiers are related by $\forall t\,(P) \equiv \neg\exists t\,(\neg P)$.

A variable is bound if a quantifier introduces it, otherwise free. A query has the form

$\{\, t \mid P(t) \,\}$

where $t$ is the only free variable of the formula $P$. The answer is the set of all tuples $t$ for which $P(t)$ is true. To keep the answer finite the formula must be safe (see below).

How it works

Reading calculus queries

The four queries run on the sample database (their answers were computed by evaluating the formula tuple by tuple, and each was compared with the SQL query on a real engine):

1. $\{t \mid t \in \text{Student} \wedge t.\text{dept} = \text{'CS'}\}$: a plain selection.
2. $\{t \mid \exists s \in \text{Student}\ \exists e \in \text{Enrolled}\ (s.\text{sid} = e.\text{sid} \wedge e.\text{cid} = \text{'C1'} \wedge t.\text{sname} = s.\text{sname})\}$: the result tuple $t$ has a single attribute sname; the quantified variables stand for the joined tuples.
3. $\{t \mid t \in \text{Student} \wedge \neg\exists e \in \text{Enrolled}\,(e.\text{sid} = t.\text{sid})\}$: negation of an existential quantifier gives "no such tuple".
4. $\{t \mid t \in \text{Student} \wedge \forall c \in \text{Teaches}\,(c.\text{iid} \ne 10 \vee \exists e \in \text{Enrolled}\,(e.\text{sid} = t.\text{sid} \wedge e.\text{cid} = c.\text{cid}))\}$: the universal quantifier expresses "for all courses taught by instructor 10, the student is enrolled" (the part $c.\text{iid} \ne 10 \vee \ldots$ is the implication "if $c$ is taught by 10 then ...").

Algebra to calculus

Every operator of relational algebra has a calculus counterpart (each was checked by evaluating the formula for all candidate tuples over a small domain and comparing with the operator):

Differences in style: calculus has no order of operations, no intermediate relations and expresses "not" and "for all" directly; algebra needs set difference and division for them.

Safety

Consider $\{t \mid \neg(t \in R)\}$. If $R$ has two tuples, the answer is "every possible tuple except those two": its size depends on how many values the attributes may take. With values from $1..k$ the answer has $k^2 - 2$ tuples:

An expression is safe if it produces only tuples whose values come from the database (or the query), so the answer is finite and does not depend on the domain. Typical unsafe expressions: a lone negation $\neg R(t)$, a disjunction in which the two branches do not restrict the same variables, a free variable that is not bounded by a positive range atom. The practical rule: every free variable and every quantified variable must be bounded by a positive atom $R(t)$.

Codd's theorem (quoted): the relational algebra and the safe tuple relational calculus have the same expressive power. Equivalent statements: every algebra query can be written as a safe calculus formula (the table above), and every safe calculus formula can be translated to algebra (with product, selection, projection, difference and division as needed). A language with this power is called relationally complete; SQL is relationally complete (and stronger: it has aggregates and arithmetic).

The domain relational calculus

In the domain calculus variables range over attribute values instead of tuples: $\{\langle a, b \rangle \mid \langle a, b, c \rangle \in R \wedge c > 5\}$. It is equivalent in power to the tuple calculus (restricted to safe expressions). It is treated, together with safety, in domain calculus and safety.

Worked examples

Cheat box

Traps and GATE patterns

Connections

SQL queries with EXISTS, NOT EXISTS and IN are calculus in disguise (nested queries, SQL basics); the algebra is the operational counterpart (relational algebra).

PYQs

Consider a relational database schema with two
relations R(P, Q) and S(X, Y)
Let E= {⟨u⟩|∃v∃w⟨u, v⟩∈R∧⟨v, w⟩∈S} be a
tuple relational calculus expression.
Which one of the following relational algebraic
expressions is equivalent to E ?

Consider two relations describing teams and players in
a sports league: teams (tid,tname): tid, tname are
team-id and team-name, respectively.players(pid,
pname,tid): pid, pname, and tid denote player-id,
playername and the team-id of the player, respectively.
Which ONE of the following tuple relational calculus
queries returns the name of the players who play for the
team having name as 'MI'?

Consider a database that has the relation schemas
EMP(Empld,
EmpName,
Deptld)
and
DEPT(DeptName, Deptld). Note that the Deptldcan  be
permitted to a NULL in the relation EMP. Consider the
following queries on the database expressed in tuple
relational calculus.

(I) {t|∃u ε EMP(t[EmpName) = u[EmpName] Λ ∀

         ∨ε DEPT(t[Deptld] ≠ V[Deptld]))}

(II) {t|∃u ε EMP(t[EmpName) = u[EmpName] Λ ∃∨ ε
DEPT(t[Deptld] ≠V[Deptld]))}

(III) {t|∃u ε EMP(t[EmpNmae) = u[EmpName] Λ ∃∨ ε
DEPT(t[Deptld] =V[Deptld]))}

Which of the above queries are safe?

Consider the following relation schema

Students(rollno:integer, sname: string)

Courses(courseno:integer,cname: string)

Registration (rollno: integer, courseno: integer, percent:
real)

Which of the following queries are equivalent to this query
in English?

"Find the distinct names of all students who score more
than 90% in the course numbered 107".

(I)  SELECT DISTINCT S.sname

FROM Students as S, Registration as R

WHERE R.rollno = S. rollno AND R.courseno = 107 AND
R.percent> 90

(II) πsname(σcourseno= 107 Λ percent> 90 (Registration ⋈Students))

(III) {T|∃S ε Students, ∃R ε Registration (S.rollno =
R.rollno Λ R.courseno = 107 Λ R.percent> 90 Λ T.sname
= S.sname)}

(IV) {<SN>|∃SR∃RP(<SR,SN>∈Students∧<SR,107,RP>∈
Registration∧ RP>90)}

Let R and S be relational schemes such that R = {a, b,
c} and S = {c}. Now consider the following queries on
the database:
         1  πR-S(r) -πR-S(πR-S(r) × s-πR-S,S(r))

         2. {t|t∈πR-S(r) ∧∀u∈s(∃v∈r(u= v[S] ∧t=
v[R-S]))}

        3. {t|t∈πR-S(r) ∧∀v∈r(∃u∈s(u= v[S] ∧t=
v[R-S]))}

4. Select R.a, R.b

  From R, S
 Where R.c = S.c

Which of the above queries are equivalent?

Which of the following tuple relational calculus
expression(s) is/are equivalent to ∀t ∈ r (P(t))?

I. ¬∃t ∈ r (P(t))
 II. ∃t ∉ r (P(t))
 III. ¬∃t ∈ r (¬P(t))
 IV. ∃t ∉ r (¬P(t))

Consider the following relational schema:

• Student(school-id, sch-roll-no, sname, saddress)
 • School(school-id, sch-name, sch-address, sch-phone)
 • Enrolment(school-id, sch-roll-no, erollno, examname)
 • ExamResult(erollno, examname, marks)

Consider the following tuple relational calculus query.

DATABASE MANAGEMENT  SYSTEM

{ t | ∃E ∈ Enrolment ( t = E.school-id ∧
 |{ x | x ∈ Enrolment ∧x.school-id = t ∧
 (∃B ∈ExamResult ( B.erollno =
x.erollno∧B.examname = x.examname∧B.marks> 35 ))
}| ÷ |{ x | x ∈ Enrolment ∧x.school-id = t }| * 100 > 35
) }

If a student needs to score more than 35 marks to pass
an exam, what does the query return?

Consider the relation employee(name, sex,
supervisorName) with name as the key.
supervisorName gives the name of the supervisor of the
employee under consideration. What does the following
Tuple Relational Calculus query produce?

 {e.name | employee(e) ∧ }

(∀x) [ ¬employee(x) ∨x.supervisorName ≠ e.name
∨x.sex = "male" ] }

Which of the following relational query languages have
the same expressive power?
1. Relational algebra
2. Tuple relational calculus restricted to safe
Expressions
3. Domain relational calculus restricted to safe
expressions

Self-check

Revision card

References