Question

Consider a relational database schema with two relations 𝑅(𝑃, 𝑄) and 𝑆(𝑋, 𝑌).
Let 𝐸 = {⟨𝑢⟩∣∃𝑣 ∃𝑤 ⟨𝑢, 𝑣⟩∈𝑅 ∧ ⟨𝑣, 𝑤⟩ ∈𝑆} be a tuple relational calculus
expression.
Which one of the following relational algebraic expressions is equivalent to 𝐸 ?

• A. 𝛱𝑃(𝑅⋈𝑅.𝑃=𝑆.𝑋𝑆)
• B. 𝛱𝑃(𝑆⋈𝑆.𝑋=𝑅.𝑄𝑅)
• C. 𝛱𝑃(𝑅⋈𝑅.𝑃=𝑆.𝑌𝑆)
• D. 𝛱𝑃(𝑆⋈𝑆.𝑌=𝑅.𝑄𝑅)

Hint:

Notice that the variable \(v\) plays the role of attribute \(Q\) in \(R\) and attribute \(X\) in \(S\); since it is the same variable in both, the join condition must be \(R.Q = S.X\), then project on \(P\).

Answer 1

The Correct Option is B

Step 1: Interpret the schema and the tuple variables. \(R(P, Q)\) means every tuple \(\langle u, v \rangle \in R\) has \(u\) as the value of attribute \(P\) and \(v\) as the value of attribute \(Q\). \(S(X, Y)\) means every tuple \(\langle v, w \rangle \in S\) has \(v\) as the value of attribute \(X\) and \(w\) as the value of attribute \(Y\).
Step 2: The given expression is \[E = \{ \langle u \rangle \mid \exists v\, \exists w\; \langle u, v \rangle \in R \land \langle v, w \rangle \in S \}\] Here \(v\) is shared between the two conditions. In \(R\), \(v\) is the value of \(Q\); in \(S\), \(v\) is the value of \(X\). So requiring the same \(v\) to satisfy both membership conditions is exactly the join condition \(R.Q = S.X\).
Step 3: The variable \(w\) is existentially quantified with no other constraint, so it only requires that a matching tuple exist in \(S\); it does not restrict which \(Y\) value is used. The final output is just \(u\), which is the \(P\) value of \(R\).
Step 4: So \(E\) is equivalent to joining \(R\) and \(S\) on \(R.Q = S.X\), then projecting on \(P\): \[E = \Pi_{P}\big(R \bowtie_{R.Q = S.X} S\big)\]
Step 5: Since the natural join (theta join) is commutative, \(R \bowtie_{R.Q=S.X} S = S \bowtie_{S.X=R.Q} R\). This matches option (B): \(\Pi_{P}\big(S \bowtie_{S.X = R.Q} R\big)\).
Step 6: Checking the distractors confirms why they fail: option (A) wrongly joins on \(R.P = S.X\) (should be \(R.Q\)); option (C) wrongly joins on \(R.P = S.Y\); option (D) wrongly joins on \(S.Y = R.Q\) (should be \(S.X\)). None of these preserve the meaning of the shared variable \(v\).
Final Answer: \[\boxed{\text{Option (B): } \Pi_{P}\big(S \bowtie_{S.X = R.Q} R\big)}\]