Let R and S be relational schemes such that R = {a, b, c} and S = {c}. Now consider the following queries on the database:
1. Pi_{R-S}(R) - Pi_{R-S}(Pi_{R-S}(R) x S - R)
2. { t | t in Pi_{R-S}(R) AND NOT (exists u)(u in S AND NOT (tu in R)) }
Which of the above queries are equivalent?
A. 1 and 2
B. 1 only
C. 2 only
D. 2 and 3 and 4
GATE 2009 · Databases · Relational Calculus · medium
Answer: A. 1 and 2
Identify Query 1 as relational division in RA: Query 1: Pi_{R-S}(R) - Pi_{R-S}(Pi_{R-S}(R) x S - R)
With R-S = {a,b} and S = {c}:
- Pi_{a,b}(R): all (a,b) pairs appearing in R
- Pi_{a,b}(R) x S: all combinations of (a,b) pairs with c values in S
- Pi_{a,b}(R) x S - R: combinations where (a,b,c) does NOT exist in R (missing pairs)
- Pi_{a,b}(Pi_{a,b}(R) x S - R): (a,b) pairs that are missing at least one c from S
- Subtracting: (a,b) pairs that are NOT missing any c — i.e., paired with ALL c in S
This is exactly R ÷ S.
Identify Query 2 as relational division in TRC: Query 2: { t | t in Pi_{R-S}(R) AND NOT (exists u)(u in S AND NOT (tu in R)) }
Rewriting: 't is an (a,b) pair from R, and there does NOT exist a c value in S such that (a,b,c) is not in R'
Equivalently: 'for every c in S, (a,b,c) is in R'
This is the standard TRC formula for R ÷ S.
Both Query 1 and Query 2 compute R ÷ S, so they are equivalent.