Project ForgeLet R and S be relational schemes such that R={a,b,c} and S={c}. Now consider the following queries on the database: I. π_(R-S)(r) − π_(R-S)(π_(R-S)(r)×s − π_(R-S,S)(r)). II. {t | t∈π_(R-S)(r) ∧ ∀u∈s(∃v∈r(u=v[s] ∧ t=v[R-S]))}. III. {t | t∈π_(R-S)(r) ∧ ∀v∈r(∃u∈s(u=v[s] ∧ t=v[R-S]))}. IV. Select R.a, R.b from R, S where R.c = S.c. Which of the above queries are equivalent?
- I and II
- BI and III
- CII and IV
- DIII and IV
Explanation
I is exactly the standard relational-algebra division formula r÷s = π_(R-S)(r) − π_(R-S)((π_(R-S)(r)×s) − r). II is exactly the standard tuple-calculus formulation of division (for every tuple u in s, there's a matching v in r agreeing on both the S-part and the R-S-part). Both correctly compute r÷s. III swaps the quantifiers (∀v∈r...∃u∈s instead of ∀u∈s...∃v∈r), which does NOT correctly express division. IV is just a join-projection, unrelated to division. So I and II are the equivalent pair.
Source: GATE CS 2009 (2009)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.