Tuple Relational Calculus

The last lesson ended wondering whether you could describe the rows you want instead of computing them step by step — and yes, you can. Think how you order coffee. Recipe style: “grind 18 grams, brew at 93°C for 28 seconds, pour 36 grams of milk on top.” Or declarative — naming the result and saying nothing at all about the steps: “a cappuccino, please.” Both get you the same drink.

Relational algebra was the recipe; tuple relational calculus (TRC) is the menu — you describe what you want and leave the steps to the database. That “describe, don’t compute” idea is exactly why SQL feels the way it does: SQL is the declarative style made practical, so getting comfortable reading TRC is really practising the mindset behind every query you will ever write.

Every TRC query says one thing: give me every row that passes this test. Written out, that is the entire notation —

{ t  |  predicate(t) }

Read it: “the set of all tuples t such that the predicate holds.” A predicate is just a true-or-false test applied to a tuple. It is built from the logical connectives ∧ (and), ∨ (or), ¬ (not) and from two quantifiers — symbols that say how many rows have to satisfy something: ∃ (“there exists at least one”) and ∀ (“for every”). Both range over tuples drawn from relations.

Those two quantifiers are the part most people have to read twice, and the reason is that English hides how differently they behave. ∃ e ∈ Enroll (…) is satisfied the moment one Enroll row works — it is a search that can stop early. ∀ c ∈ Course (…) is satisfied only if no Course row fails — it is a check that has to run to the end. Find-me-one versus survive-them-all. Whenever a TRC line stops making sense, ask first which of those two it is.

RA vs TRC — the same query, two styles

Read the TRC side carefully. There is an output tuple variable t — the thing being described — and the predicate introduces two more tuple variables: s, ranging over the rows of Student, and e, ranging over the rows of Enroll.

The rest of the line constrains those three. t.name = s.name says the output’s name is some Student’s name; s.id = e.sid says that Student is the one named in the Enroll row; e.cid = "CS101" pins the Enroll row to the course we care about. The set of all t.name that survive those three conditions is the answer — the same set of names the RA expression on the left produces.

Worked example — names of students in CS101

Schemas: Student(id, name), Enroll(sid, cid). Return names of students enrolled in CS101.

TRC:

{ t.name | ∃ s ∈ Student, ∃ e ∈ Enroll
           ( t.name = s.name ∧ s.id = e.sid ∧ e.cid = "CS101" ) }

RA:

π_name( Student ⋈ σ_cid="CS101" (Enroll) )

Both walk through the same logical join: a Student row with an Enroll row whose cid is CS101. RA names the steps; TRC names the constraints. Codd’s theorem guarantees they have the same expressive power for safe queries — queries whose answer is guaranteed to be a finite set — so anything one can compute, so can the other.

A “for all” in TRC

What about “students enrolled in EVERY course”? In words: keep a student only if you can point to an enrolment row for that student in each course on the books. TRC writes that with the ∀ quantifier directly:

{ s.name | ∃ s ∈ Student
           ( ∀ c ∈ Course
             ( ∃ e ∈ Enroll ( e.sid = s.id ∧ e.cid = c.cid ) ) ) }

Read it: a student s such that for every course c, there exists an Enroll row matching s.id to that c.cid.

Try it on a handful of rows. Say Course = {CS101, CS102} and Enroll = {(1, CS101), (1, CS102), (2, CS101)}. For student 1, both courses find a matching Enroll row, so the ∀ holds and student 1 is returned. For student 2, course CS102 finds nothing, the ∀ fails, and student 2 is dropped. One missing row is enough to disqualify — that is ∀ behaving exactly as advertised.

This is the same shape as relational division A ÷ B from the previous lesson — ∀ is the hallmark of for-all queries, in either notation, and TRC simply writes the quantifier out loud.

How GATE asks this

The pattern is always the same MCQ: an expression like { t.x | ∃ r ∈ R (…) } is given and four English sentences are options. You translate by reading the introduction of each tuple variable, the joining predicates between attributes, and any equality with a constant. The right English sentence is usually a one-liner.

A question to carry forward

TRC shows the declarative idea in its purest, most mathematical form — quantifiers, predicates, set braces. But you would never hand a colleague { t.name | ∃ s ∈ Student … } and call it a query. The world settled instead on a friendlier dialect of this very idea, one dressed in English-like keywords: SELECT, FROM, WHERE, GROUP BY. Here is the thread onward: how does that practical declarative language — SQL — actually compute a result by hand, and how do you trace a query with grouping and aggregation down to the exact rows and numbers it returns?

In one breath

• TRC is declarative — say what tuples you want, not how to compute them. RA is the recipe; TRC is the menu.
• Form: { t | predicate(t) } — “all tuples t where the predicate holds,” using ∧ ∨ ¬ and the quantifiers ∃ (exists) and ∀ (for all) over tuples of relations.
• RA ≡ TRC in expressive power for safe queries (Codd’s theorem) — same answers, different style. ∀ in TRC = division in RA (both encode “for-all”).
• Variables are tuples: always dot into attributes (s.name, never bare name).
• Safe queries only — a pure complement like ¬ s.name = "Asha" over an infinite domain is unsafe and excluded.

Practice