Consider the relation "enrolled(student, course)" in which (student, course)…
2006
Consider the relation "enrolled(student, course)" in which (student, course) is the primary key, and the relation "paid(student, amount)" where student is the primary key. Assume no null values and no foreign keys or integrity constraints. Given the following four queries:
Query1: select student from enrolled where
student in (select student from paid)
Query2: select student from paid where
student in (select student from enrolled)
Query3: select E.student from enrolled E, paid P
where E.student = P.student
Query4: select student from paid where exists
(select * from enrolled where enrolled.student
= paid.student) Which one of the following statements is correct?
- A.
All queries return identical row sets for any database
- B.
Query2 and Query4 return identical row sets for all databases but there exist databases for which Query1 and Query2 return different row sets.
- C.
There exist databases for which Query3 returns strictly fewer rows than Query2
- D.
There exist databases for which Query4 will encounter an integrity violation at runtime.
Attempted by 72 students.
Show answer & explanation
Correct answer: B
Answer: Query2 and Query4 return identical row sets for all databases; Query1 and Query3 are equivalent to each other but can differ from Query2/Query4 in row multiplicity.
Key facts:
paid.student is a primary key, so each student appears at most once in the paid relation.
enrolled has primary key (student, course), so the same student can appear in multiple enrolled rows (one per course).
Why Query2 and Query4 are equivalent:
Both queries return students from paid for whom there exists at least one matching row in enrolled. Because paid.student is unique, each matching student appears at most once in the result of either query, so the two return identical row sets.
Why Query1 and Query3 are equivalent to each other (and may differ from Query2/Query4):
Query1 selects student from enrolled when that student appears in paid; it outputs one row per enrolled row that has a matching paid student.
Query3 performs an inner join on student; since paid has at most one row per student, each enrolled row that matches a paid student produces exactly one joined row. Thus Query3 also outputs one row per enrolled row that has a matching paid row.
Therefore Query1 and Query3 produce the same multiset of rows; they can contain duplicates when a student is enrolled in multiple courses, while Query2 and Query4 will contain each matching student at most once.
Concrete example to illustrate the difference:
enrolled = {(Alice, Math), (Alice, CS)}
paid = {(Alice, 100)}
Query1 and Query3 return: Alice, Alice (two rows).
Query2 and Query4 return: Alice (one row).
Conclusion: The correct statement is that Query2 and Query4 return identical row sets for all databases, but there exist databases for which Query1 and Query2 return different row sets (because of duplicate rows coming from enrolled).