Exists and for-all queries; translating between TRC and RA

0 · Recall Warm-up

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

1. In { t | P(t) }, which variable may be free? from Lesson 3.2.1
2. How does RA answer "students who took every CS course"? from Lesson 3.1.5
3. What is ¬∀x P(x)? from Lesson 0.2.3

1 · The Hook

In TRC, a join is "there exists a matching tuple", a "none" query is "there does not exist", and a division is "for all … there exists". Three patterns cover nearly every TRC question in GATE. Learn them as sentence templates.

2 · Predict First

Write in words what this returns: { s.name | s ∈ STUDENT ∧ ¬∃e ∈ ENROLL (e.roll = s.roll ∧ e.grade = 'A') }

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

3 · Core Concept

Predict First — the answer

Names of students who have no A grade at all. Asha and Chirag have A grades; {Bhavin, Diya}.

Pattern 1 · Join = ∃

"Names of students who took C1": { s.name | s ∈ STUDENT ∧ ∃e ∈ ENROLL (e.roll = s.roll ∧ e.cid = 'C1') } = {Asha, Chirag}.

Each extra relation in a join adds one ∃ with the matching condition. "Titles of courses taken by Asha": { c.title | c ∈ COURSE ∧ ∃e ∈ ENROLL ∃s ∈ STUDENT (e.cid = c.cid ∧ e.roll = s.roll ∧ s.name = 'Asha') } = {DBMS, Networks, Circuits}.

Pattern 2 · None = ¬∃

"Students who took no course": { s | s ∈ STUDENT ∧ ¬∃e ∈ ENROLL (e.roll = s.roll) }. RA: π(STUDENT) − π(ENROLL).

Pattern 3 · All = ∀ ⇒ ∃

"Rolls of students who took every CS course":

{ s.roll | s ∈ STUDENT ∧ ∀c ∈ COURSE (c.dept = 'CS' ⇒ ∃e ∈ ENROLL (e.roll = s.roll ∧ e.cid = c.cid)) }

Read: "for every course, if it is a CS course then the student has an enrolment in it". Non-CS courses make the implication vacuously true, so only CS courses are checked. Result {1, 3}, matching the division of Lesson 3.1.5.

The same with ¬∃ (no counter-example): { s.roll | s ∈ STUDENT ∧ ¬∃c ∈ COURSE (c.dept = 'CS' ∧ ¬∃e ∈ ENROLL (e.roll = s.roll ∧ e.cid = c.cid)) } "There is no CS course that this student has not taken." This double-negation form is exactly how SQL writes "for all" (Lesson 3.3.9).

Common wrong versions (GATE distractors)

• ∀c ∈ COURSE (c.dept = 'CS' ∧ ∃e …): demands that every course be a CS course; false for everyone here.
• ∃c ∈ COURSE (c.dept = 'CS' ⇒ ∃e …): true as soon as one non-CS course exists; returns everyone.
• ∃c ∈ COURSE (c.dept = 'CS' ∧ ∃e …): "took some CS course" (that is a join, not division).

Translating RA → TRC

4 · Visual

ALL  =  FOR EVERY ... IF ... THEN EXISTS
        ∀c ∈ COURSE ( c.dept='CS'  ⇒  ∃e ∈ ENROLL (e.roll=s.roll ∧ e.cid=c.cid) )

        = NO ... THAT IS ... AND NOT EXISTS
        ¬∃c ∈ COURSE ( c.dept='CS'  ∧  ¬∃e ∈ ENROLL (e.roll=s.roll ∧ e.cid=c.cid) )

        roll 1: CS courses C1 ✓ C2 ✓  -> no counter-example -> IN
        roll 2: C1 ✗                  -> counter-example    -> OUT

5 · Worked Examples

Example 1 Easy

Write in TRC: names of students enrolled in a 4-credit course.

Solution

{ s.name | s ∈ STUDENT ∧ ∃e ∈ ENROLL ∃c ∈ COURSE (e.roll = s.roll ∧ e.cid = c.cid ∧ c.credits = 4) } → C1 or C3 takers: Asha, Bhavin, Chirag.

Example 2 Medium

Write "courses taken by every CS student" in TRC and evaluate.

Solution

{ c.cid | c ∈ COURSE ∧ ∀s ∈ STUDENT (s.dept = 'CS' ⇒ ∃e ∈ ENROLL (e.roll = s.roll ∧ e.cid = c.cid)) }. CS students: 1, 3. Courses both took: C1, C2.

Example 3 GATE

What does { s.roll | s ∈ STUDENT ∧ ∃c ∈ COURSE (c.dept = 'ME' ⇒ ∃e ∈ ENROLL (e.roll = s.roll ∧ e.cid = c.cid)) } return?

Solution

All four rolls. For any student, pick c = C1 (not ME): the implication is vacuously true, so ∃c succeeds. The ⇒ inside ∃ is the classic mistake.

8 · Connect the Dots

Lesson 3.2.1 gave TRC syntax; this lesson gave the three patterns (join, none, all). Next: a formula can describe an infinite answer ("all tuples not in STUDENT"). Such unsafe queries are forbidden, and the safe ones turn out to be exactly as powerful as relational algebra.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · MCQ · 2 mark(s) — Reading

{ s.name | s ∈ STUDENT ∧ ∃e ∈ ENROLL (e.roll = s.roll ∧ e.cid = 'C3') } returns:

1. (A) {Bhavin}
2. (B) {Asha}
3. (C) {Chirag, Diya}
4. (D) {Asha, Bhavin}

Q2 · MCQ · 2 mark(s) — For all

Which TRC formula returns rolls of students who took every 4-credit course?

1. (A) { s.roll | s ∈ STUDENT ∧ ∀c ∈ COURSE (c.credits = 4 ∧ ∃e ∈ ENROLL (e.roll = s.roll ∧ e.cid = c.cid)) }
2. (B) { s.roll | s ∈ STUDENT ∧ ∀c ∈ COURSE (c.credits = 4 ⇒ ∃e ∈ ENROLL (e.roll = s.roll ∧ e.cid = c.cid)) }
3. (C) { s.roll | s ∈ STUDENT ∧ ∃c ∈ COURSE (c.credits = 4 ∧ ∃e ∈ ENROLL (e.roll = s.roll ∧ e.cid = c.cid)) }
4. (D) { s.roll | s ∈ STUDENT ∧ ∃c ∈ COURSE (c.credits = 4 ⇒ ∃e ∈ ENROLL (e.roll = s.roll ∧ e.cid = c.cid)) }

Q3 · NAT · 2 mark(s) — Evaluate

How many tuples does { s.roll | s ∈ STUDENT ∧ ∀c ∈ COURSE (c.credits = 4 ⇒ ∃e ∈ ENROLL (e.roll = s.roll ∧ e.cid = c.cid)) } return on the running data?

Numerical answer: ________

Q4 · NAT · 1 mark(s) — None

How many tuples does { s | s ∈ STUDENT ∧ ¬∃e ∈ ENROLL (e.roll = s.roll ∧ e.grade = 'B') } return?

Numerical answer: ________

Q5 · MSQ · 2 mark(s) — Equivalences

Which are equivalent to "∀c ∈ COURSE (P(c) ⇒ Q(c))"?

1. (A) ¬∃c ∈ COURSE ¬(P(c) ⇒ Q(c))
2. (B) ∀c ∈ COURSE (¬P(c) ∨ Q(c))
3. (C) ¬∃c ∈ COURSE (P(c) ∧ ¬Q(c))
4. (D) ∃c ∈ COURSE (P(c) ∧ Q(c))

11 · Concept Ledger

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

existential query (join in TRC)negated existential (none)universal query (∀ ⇒ ∃)double-negation for-allRA–TRC translation