3.2.1 · TRC syntax, tuple variables, free vs bound variables

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

What does R ÷ S return? from Lesson 3.1.5
Write the RA expression for the maximum of A in R. from Lesson 3.1.6
What is a free (unquantified) variable in "∃x P(x, y)"? from Lesson 0.2.3

1 · The Hook

Relational algebra is a recipe: "select, then join, then project". Relational calculus is an order: "give me every student such that …". You describe the answer in logic, and the DBMS works out the steps. SQL's WHERE clause is closer to calculus than to algebra, and GATE asks you to read calculus formulas and say what they return.

2 · Predict First

What does this return? { t | t ∈ STUDENT ∧ t.cgpa > 8 }

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

Predict First — the answer

Every STUDENT tuple whose CGPA is above 8: (1, Asha, CS, 9.1) and (3, Chirag, CS, 8.4). It is the same as σcgpa > 8(STUDENT).

Tuple relational calculus (TRC)

A TRC query has the form { t | P(t) }: "the set of all tuples t for which the formula P(t) is true". t is a tuple variable: it stands for one tuple at a time.

Atoms (smallest formulas)

t ∈ R: t is a tuple of relation R (sets t's range).
t.A op s.B: compare attribute A of t with attribute B of s; op ∈ {=, ≠, <, ≤, >, ≥}.
t.A op c: compare with a constant.

Building formulas

From atoms with ∧, ∨, ¬, ⇒ (implication) and the quantifiers ∃s (…) and ∀s (…) of Lesson 0.2.3. Ranges are usually written inside: ∃s ∈ R (P) means ∃s (s ∈ R ∧ P), and ∀s ∈ R (P) means ∀s (s ∈ R ⇒ P).

Free and bound variables

A variable is bound if it is introduced by ∃ or ∀; otherwise it is free.
In { t | P(t) }, the only free variable must be t, the result variable. Every other variable must be bound.
In { t | t ∈ STUDENT ∧ ∃e ∈ ENROLL (e.roll = t.roll) }, t is free and e is bound.

Picking attributes (projection)

Two styles exist:

Target list: { t.name | t ∈ STUDENT ∧ t.dept = 'CS' } returns names only.
Result-tuple style: { t | ∃s ∈ STUDENT (s.dept = 'CS' ∧ t.name = s.name) }: t is a new one-attribute tuple whose name equals some CS student's name.

Both return {Asha, Chirag}. GATE questions use either style; read what the free variable is equal to.

RA ↔ TRC, first steps

RA	TRC
σc(R)	{ t \| t ∈ R ∧ c(t) }
πA(R)	{ t.A \| t ∈ R }
R ∪ S	{ t \| t ∈ R ∨ t ∈ S }
R − S	{ t \| t ∈ R ∧ ¬(t ∈ S) }

Joins and division need quantifiers: the next lesson.

4 · Visual

{ t.name | t ∈ STUDENT  ∧  t.cgpa > 8 }
  ------   -----------     -----------
  output   range of t      condition on t
           (free var)

t runs over every STUDENT tuple:
  Asha   9.1  > 8 ?  TRUE   -> output Asha
  Bhavin 7.8  > 8 ?  FALSE
  Chirag 8.4  > 8 ?  TRUE   -> output Chirag
  Diya   6.9  > 8 ?  FALSE

5 · Worked Examples

Example 1 Easy

Write in TRC: all courses with 4 credits.

Solution

{ c | c ∈ COURSE ∧ c.credits = 4 } → (C1, DBMS, CS, 4), (C3, Circuits, EE, 4).

Example 2 Medium

In { t | t ∈ ENROLL ∧ ∃s ∈ STUDENT (s.roll = t.roll ∧ s.dept = 'EE') }, which variables are free and bound, and what is returned?

Solution

t is free, s is bound. Returned: enrolments of EE students: (2, C3, B).

Example 3 GATE

Which is not a valid TRC query? (A) { t | t ∈ R ∧ t.A > 5 } (B) { t | ∃s ∈ R (s.A = t.A) } (C) { t | t ∈ R ∧ s.A = 3 } (D) { t.B | t ∈ R }

Solution

(C): s is free but is not the result variable and is not bound by any quantifier, so the formula has no meaning.

6 · GATE Traps

Only the result variable may be free; any other free variable makes the query invalid.
∃s ∈ R (P) is shorthand for ∃s (s ∈ R ∧ P); ∀s ∈ R (P) is ∀s (s ∈ R ⇒ P). The connectives differ (∧ vs ⇒).
{ t | P } returns tuples, not truth values.
t.A refers to one attribute of one tuple; t alone is the whole tuple.

7 · Memory Hook

"Calculus says WHAT, algebra says HOW." And: "One free bird (t); every other bird is caged by ∃ or ∀."

8 · Connect the Dots

Chapter 3.1 described queries as operator recipes; this lesson described them as logical conditions on a tuple variable. Next: the quantifiers do the heavy lifting: ∃ gives joins, ∀ gives division, and ¬∃ gives "none".

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · MCQ · 1 mark(s) — Reading TRC

{ t | t ∈ STUDENT ∧ t.dept = 'ME' } returns:

(A) (4, Diya, ME, 6.9)
(B) the department ME
(C) nothing
(D) all students

Q2 · MCQ · 1 mark(s) — Variables

In { t | t ∈ R ∧ ∃u ∈ S (u.B = t.B) }:

(A) t is free and u is bound
(B) both are bound
(C) t is bound and u is free
(D) t and u are both free

Q3 · NAT · 1 mark(s) — Evaluate

How many tuples does { t | t ∈ ENROLL ∧ t.grade = 'A' } return?

Numerical answer: ________

Q4 · MSQ · 2 mark(s) — Equivalence

Which TRC queries are equivalent to σcredits = 3(COURSE)?

(A) { c | c ∈ COURSE ∧ ¬(c.credits ≠ 3) }
(B) { c | c ∈ COURSE ∨ c.credits = 3 }
(C) { c | c ∈ COURSE ∧ c.credits = 3 }
(D) { c | c ∈ COURSE ∧ c.credits ≥ 3 ∧ c.credits ≤ 3 }

Q5 · MCQ · 1 mark(s) — Validity

Which formula is a valid TRC query?

(A) { t | s ∈ R }
(B) { t | t ∈ R ∧ t.A = 1 }
(C) { t | t ∈ R ∧ u.A = t.A }
(D) { t | u ∈ R }

10 · Rule Card

TRC query: { t | P(t) }; t is the only free variable.
Atoms: t ∈ R; t.A op s.B; t.A op c.
∃s ∈ R (P) ≡ ∃s (s ∈ R ∧ P); ∀s ∈ R (P) ≡ ∀s (s ∈ R ⇒ P).
Bound = introduced by a quantifier; free = otherwise.
σ ↔ condition; π ↔ t.A target or t.A = s.A; ∪ ↔ ∨; − ↔ ∧ ¬.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

relational calculustuple relational calculus (TRC)tuple variableatomfree variablebound variablerange (t ∈ R)target list t.A

12 · Answer Vault

Reveal answers when you’re ready

Recall Warm-up

The X-values of R paired with every tuple of S.
πA(R) − πR1.A(σR1.A < R2.A(ρR1(R) × ρR2(R))).
y; x is bound by ∃.