Correlated subqueries; for-all in SQL; tracing a query on a table instance

0 · Recall Warm-up

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

1. What does cgpa > ALL (empty) evaluate to? from Lesson 3.3.8
2. Write "for all" with two negations in TRC. from Lesson 3.2.2
3. After WHERE, which clause filters groups? from Lesson 3.3.5

1 · The Hook

"Students whose CGPA is above their own department's average." The inner query must know which department the outer student is in, so it cannot run once: it runs once per outer row. These correlated subqueries express "for all" in SQL (NOT EXISTS … NOT EXISTS) and are the kind of query GATE asks you to trace row by row.

2 · Predict First

SELECT S.name FROM STUDENT S WHERE S.cgpa > (SELECT AVG(T.cgpa) FROM STUDENT T WHERE T.dept = S.dept); Who is returned?

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

3 · Core Concept

Predict First — the answer

CS average = (9.1 + 8.4) / 2 = 8.75 → Asha (9.1) qualifies, Chirag does not, Esha (NULL) gives UNKNOWN. EE average = 7.8 → Bhavin is not greater. ME average = 6.9 → Diya is not greater. Answer: Asha.

Correlated subquery

A subquery is correlated if it refers to a column of the outer query (S.dept above). Conceptually, the outer query takes one row at a time, substitutes its values into the subquery, evaluates the subquery, and tests the condition.

Uncorrelated subqueries can run once; correlated ones are re-evaluated per outer row (optimisers often rewrite them as joins).

EXISTS patterns

• Some: students who took a 4-credit course:

SELECT S.name FROM STUDENT S
WHERE EXISTS (SELECT * FROM ENROLL E JOIN COURSE C ON E.cid = C.cid
              WHERE E.roll = S.roll AND C.credits = 4);        -- Asha, Bhavin, Chirag

• None: students who took no course:

SELECT S.name FROM STUDENT S
WHERE NOT EXISTS (SELECT * FROM ENROLL E WHERE E.roll = S.roll); -- Esha

For all: double NOT EXISTS

"Students who took every CS course" = "students for whom there is no CS course that they have not taken":

SELECT S.name FROM STUDENT S
WHERE NOT EXISTS (
    SELECT * FROM COURSE C
    WHERE C.dept = 'CS'
      AND NOT EXISTS (SELECT * FROM ENROLL E
                      WHERE E.roll = S.roll AND E.cid = C.cid));

Result: Asha, Chirag. It is the TRC formula ¬∃c (cond ∧ ¬∃e …) of Lesson 3.2.2 written in SQL.

Alternative with counting:

SELECT E.roll FROM ENROLL E JOIN COURSE C ON E.cid = C.cid
WHERE C.dept = 'CS'
GROUP BY E.roll
HAVING COUNT(DISTINCT E.cid) = (SELECT COUNT(*) FROM COURSE WHERE dept = 'CS');   -- 1, 3

Edge case: if there are no CS courses, the NOT EXISTS version returns every student (vacuous truth); the counting version returns nobody (no rows to group). GATE has asked exactly this difference.

Tracing a correlated query: top-k

SELECT S1.name FROM STUDENT S1
WHERE (SELECT COUNT(*) FROM STUDENT S2 WHERE S2.cgpa > S1.cgpa) < 2;

"Students with fewer than 2 students above them" = top 2. Trace: Asha 0 above ✓; Chirag 1 above ✓; Bhavin 2 ✗; Diya 3 ✗; Esha: S2.cgpa > NULL is UNKNOWN for every S2, so COUNT(*) = 0 < 2 ✓. Result: Asha, Chirag, Esha. NULL rows sneak into "top-k" queries.

Tracing method

For each outer row: write its values; run the inner query on paper with those values; evaluate the outer condition. Make a small table: outer row | inner result | condition | kept?

4 · Visual

WHERE S.cgpa > (SELECT AVG(T.cgpa) FROM STUDENT T WHERE T.dept = S.dept)

outer row S      inner: AVG over S.dept      condition        kept?
Asha   CS 9.1    CS: 8.75                    9.1 > 8.75  T    yes
Bhavin EE 7.8    EE: 7.8                     7.8 > 7.8   F    no
Chirag CS 8.4    CS: 8.75                    8.4 > 8.75  F    no
Diya   ME 6.9    ME: 6.9                     6.9 > 6.9   F    no
Esha   CS NULL   CS: 8.75                    NULL > 8.75 U    no

5 · Worked Examples

Example 1 Easy

Rewrite "students who took no course" with LEFT JOIN instead of NOT EXISTS.

Solution

SELECT S.name FROM STUDENT S LEFT JOIN ENROLL E ON S.roll = E.roll WHERE E.roll IS NULL; → Esha.

Example 2 Medium

SELECT C.title FROM COURSE C WHERE NOT EXISTS (SELECT * FROM STUDENT S WHERE S.dept = 'CS' AND NOT EXISTS (SELECT * FROM ENROLL E WHERE E.roll = S.roll AND E.cid = C.cid)); What does it return?

Solution

"Courses taken by every CS student." CS students are 1, 3 and 5 (Esha). Esha took nothing, so no course is taken by every CS student: empty result. (Without Esha it would be DBMS and Networks.)

Example 3 GATE

SELECT E1.roll FROM ENROLL E1 WHERE E1.grade = 'A' AND NOT EXISTS (SELECT * FROM ENROLL E2 WHERE E2.roll = E1.roll AND E2.grade <> 'A'); Which rolls?

Solution

"Students with an A who have no non-A grade." Roll 1 has a B (C2) → no. Roll 3 has a B (C1) → no. Empty result.

8 · Connect the Dots

Lesson 3.3.8 used independent subqueries; this lesson tied them to the outer row and expressed "for all". Last SQL lesson next: views and WITH to name intermediate results.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · MCQ · 2 mark(s) — Correlated

SELECT S.name FROM STUDENT S WHERE S.cgpa >= (SELECT AVG(T.cgpa) FROM STUDENT T WHERE T.dept = S.dept); returns:

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

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

How many names does this return? SELECT S.name FROM STUDENT S WHERE NOT EXISTS (SELECT * FROM COURSE C WHERE C.credits = 3 AND NOT EXISTS (SELECT * FROM ENROLL E WHERE E.roll = S.roll AND E.cid = C.cid));

Numerical answer: ________

Q3 · NAT · 2 mark(s) — Top-k trace

How many rows: SELECT S1.name FROM STUDENT S1 WHERE (SELECT COUNT(*) FROM STUDENT S2 WHERE S2.cgpa < S1.cgpa) >= 2;

Numerical answer: ________

Q4 · MCQ · 1 mark(s) — Vacuous

If COURSE has no ME-department courses, "students who took every ME course" written with double NOT EXISTS returns:

1. (A) no students
2. (B) only students with enrolments
3. (C) an error
4. (D) every student

Q5 · NAT · 1 mark(s) — NOT EXISTS

How many students satisfy NOT EXISTS (SELECT * FROM ENROLL E WHERE E.roll = S.roll AND E.grade = 'A')?

Numerical answer: ________

11 · Concept Ledger

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

correlated subqueryper-row evaluationdouble NOT EXISTS (for all in SQL)COUNT-based divisiontop-k querytracing table