A · Compressed recap
TRC writes { t | P(t) }: t is the only free variable; atoms are t ∈ R, t.A op s.B, t.A op c; ∃s ∈ R (P) means ∃s (s ∈ R ∧ P) and ∀s ∈ R (P) means ∀s (s ∈ R ⇒ P). Patterns: join = ∃ with match conditions; none = ¬∃; all = ∀c (cond ⇒ ∃ match) = ¬∃c (cond ∧ ¬∃ match). Wrong forms: ∀ with ∧, ∃ with ⇒.
Safety: every result value must come from the constants and relations of the formula; the free variable must be range-restricted in every branch. Basic RA ≡ safe TRC ≡ safe DRC (Codd); none does aggregation or unbounded recursion; SQL is relationally complete.
B · Merged rule card
3.2.1 TRC syntax, tuple variables, free vs bound variables
- 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; ∪ ↔ ∨; − ↔ ∧ ¬.
3.2.2 Exists and for-all queries; translating between TRC and RA
- Join: ∃ per extra relation with matching conditions.
- None: ¬∃.
- All: ∀c ∈ D (cond ⇒ ∃ match) ≡ ¬∃c ∈ D (cond ∧ ¬∃ match).
- Wrong forms: ∀ with ∧ (too strong), ∃ with ⇒ (vacuously true).
3.2.3 Safe vs unsafe expressions; relational completeness
- dom(P) = constants in P + values in the relations P mentions.
- Safe: all result values in dom(P); the result variable is range-restricted in every branch; ¬ does not restrict.
- Relationally complete = expresses all basic RA.
- Codd: basic RA ≡ safe TRC ≡ safe DRC. None of them does aggregation or unbounded recursion.
- DRC: variables over values; TRC: variables over tuples.
C · Interleaved GATE-style questions
Q1 · MCQ · 1 mark(s) — Free variables
Which TRC query has a variable that is wrongly left free?
- (A) { t | t ∈ R ∧ s.A = t.A }
- (B) { t | t ∈ R ∧ ∃s ∈ S (s.A = t.A) }
- (C) { t.A | t ∈ R }
- (D) { t | t ∈ R ∧ ¬∃s ∈ S (s.A = t.A) }
Q2 · NAT · 1 mark(s) — Evaluate
How many tuples does { c | c ∈ COURSE ∧ c.dept = 'CS' ∧ c.credits < 4 } return?
Numerical answer: ________
Q3 · MCQ · 2 mark(s) — Join
{ c.title | c ∈ COURSE ∧ ∃e ∈ ENROLL (e.cid = c.cid ∧ e.grade = 'C') } returns:
- (A) ∅
- (B) {Circuits, Thermo}
- (C) {Thermo}
- (D) {DBMS}
Q4 · NAT · 2 mark(s) — For all
How many rolls satisfy s ∈ STUDENT ∧ ∀c ∈ COURSE (c.dept = 'EE' ⇒ ∃e ∈ ENROLL (e.roll = s.roll ∧ e.cid = c.cid))?
Numerical answer: ________
Q5 · MCQ · 2 mark(s) — Distractor
On the running data, { s.roll | s ∈ STUDENT ∧ ∀c ∈ COURSE (c.dept = 'CS' ∧ ∃e ∈ ENROLL (e.roll = s.roll ∧ e.cid = c.cid)) } returns:
- (A) ∅
- (B) {1, 3}
- (C) {1}
- (D) all rolls
Q6 · MCQ · 1 mark(s) — Safety
Which is safe?
- (A) { t | ∀s ∈ S (t.A ≠ s.A) }
- (B) { t | t ∈ R ∧ ¬(t ∈ S) }
- (C) { t | t.A = 5 }
- (D) { t | ¬(t ∈ R) }
Q7 · MSQ · 2 mark(s) — Completeness
Which are relationally complete?
- (A) Safe tuple relational calculus
- (B) A language with only σ and π
- (C) Basic relational algebra
- (D) SQL
Q8 · MCQ · 1 mark(s) — Translation
RA difference R − S corresponds in TRC to:
- (A) { t | t ∈ R ∨ t ∈ S }
- (B) { t | ¬(t ∈ R) ∧ t ∈ S }
- (C) { t | t ∈ R ∧ ¬(t ∈ S) }
- (D) { t | t ∈ R ∧ t ∈ S }
D · Answer Vault
Reveal answers when you’re ready
Q1 Answer: (A) · 1 mark(s)
s is neither the result variable nor quantified.
- (B) is wrong: s bound.
- (C) is wrong: Fine.
- (D) is wrong: s bound.
Re-read: Lesson 3.2.1 — TRC syntax, tuple variables, free vs bound variables
Q2 Answer: 1 · 1 mark(s)
C2 only.
Re-read: Lesson 3.2.1 — TRC syntax, tuple variables, free vs bound variables
Q3 Answer: (C) · 2 mark(s)
The only C grade is in C4.
- (A) is wrong: C4 qualifies.
- (B) is wrong: C3 has A and B grades.
- (D) is wrong: No C grade in C1.
Re-read: Lesson 3.2.2 — Exists and for-all queries; translating between TRC and RA
Q4 Answer: 2 · 2 mark(s)
EE courses: {C3}; rolls 1 and 2 took it.
Re-read: Lesson 3.2.2 — Exists and for-all queries; translating between TRC and RA
Q5 Answer: (A) · 2 mark(s)
It requires every course to be a CS course; C3 and C4 are not.
- (B) is wrong: That is the correct "all CS courses" answer with ⇒.
- (C) is wrong: No.
- (D) is wrong: No.
Re-read: Lesson 3.2.2 — Exists and for-all queries; translating between TRC and RA
Q6 Answer: (B) · 1 mark(s)
R restricts t.
- (A) is wrong: Unrestricted.
- (C) is wrong: Other attributes unrestricted.
- (D) is wrong: Unrestricted.
Re-read: Lesson 3.2.3 — Safe vs unsafe expressions; relational completeness
Q7 Answer: (A) (C) (D) · 2 mark(s)
σ and π alone cannot combine relations.
- (B) is wrong: Missing ×, ∪, −.
Re-read: Lesson 3.2.3 — Safe vs unsafe expressions; relational completeness
Q8 Answer: (C) · 1 mark(s)
In R, not in S.
- (A) is wrong: Union.
- (B) is wrong: S − R.
- (D) is wrong: Intersection.
Re-read: Lesson 3.2.2 — Exists and for-all queries; translating between TRC and RA