Question:medium
Consider a relational database schema with two relations \(R(P, Q)\) and \(S(X, Y)\).
Let \(E = \{\langle u \rangle \mid \exists v\, \exists w\; \langle u, v \rangle \in R \wedge \langle v, w \rangle \in S\}\) be a tuple relational calculus expression.
Which one of the following relational algebraic expressions is equivalent to \(E\)?
Consider a relational database schema with two relations \(R(P, Q)\) and \(S(X, Y)\).
Let \(E = \{\langle u \rangle \mid \exists v\, \exists w\; \langle u, v \rangle \in R \wedge \langle v, w \rangle \in S\}\) be a tuple relational calculus expression.
Which one of the following relational algebraic expressions is equivalent to \(E\)?
Let \(E = \{\langle u \rangle \mid \exists v\, \exists w\; \langle u, v \rangle \in R \wedge \langle v, w \rangle \in S\}\) be a tuple relational calculus expression.
Which one of the following relational algebraic expressions is equivalent to \(E\)?
Show Hint
Match each shared/free variable in the tuple calculus to the attribute position it occupies in R and S, then translate the shared existential variable into an equi-join condition before projecting.
Updated On: Jul 22, 2026
- \(\Pi_P(R \bowtie_{R.P = S.X} S)\)
- \(\Pi_P(S \bowtie_{S.X = R.Q} R)\)
- \(\Pi_P(R \bowtie_{R.P = S.Y} S)\)
- \(\Pi_P(S \bowtie_{S.Y = R.Q} R)\)
Show Solution
The Correct Option is B
Solution and Explanation
Step 1: Understand the given expression.
The expression is \[ E=\{u \mid \exists v\,((u,v)\in R \land \exists w\,((v,w)\in S))\} \] This means that a value u will be included in the result if there exists a value v such that:
Step 2: Identify the common attribute.
Relation R(P,Q) contains tuples of the form \((u,v)\), where:
Step 3: Perform the join.
Joining R and S on the condition \(R.Q=S.X\) keeps only those tuples where the second attribute of R matches the first attribute of S. The join operation is \[ S \bowtie_{S.X=R.Q} R \] This ensures that every selected tuple satisfies the condition given in the set expression.
Step 4: Apply projection.
The expression asks for the set of all values u. Since u corresponds to attribute P of relation R, we project only attribute P from the joined relation. Hence, \[ \Pi_P\left(S \bowtie_{S.X=R.Q} R\right) \]
Step 5: Compare with the given options.
Final Answer: \[ \boxed{\Pi_P\left(S \bowtie_{S.X=R.Q} R\right)} \] Correct Option: (B)
The expression is \[ E=\{u \mid \exists v\,((u,v)\in R \land \exists w\,((v,w)\in S))\} \] This means that a value u will be included in the result if there exists a value v such that:
- \((u,v)\) is a tuple in relation R, and
- there exists some value w for which \((v,w)\) is a tuple in relation S.
Step 2: Identify the common attribute.
Relation R(P,Q) contains tuples of the form \((u,v)\), where:
- \(u\) corresponds to attribute P.
- \(v\) corresponds to attribute Q.
- \(v\) corresponds to attribute X.
- \(w\) corresponds to attribute Y.
Step 3: Perform the join.
Joining R and S on the condition \(R.Q=S.X\) keeps only those tuples where the second attribute of R matches the first attribute of S. The join operation is \[ S \bowtie_{S.X=R.Q} R \] This ensures that every selected tuple satisfies the condition given in the set expression.
Step 4: Apply projection.
The expression asks for the set of all values u. Since u corresponds to attribute P of relation R, we project only attribute P from the joined relation. Hence, \[ \Pi_P\left(S \bowtie_{S.X=R.Q} R\right) \]
Step 5: Compare with the given options.
- Option (A): Joins on \(R.P=S.X\), which compares the wrong attributes.
- Option (B): Joins on \(S.X=R.Q\), which correctly matches the common value \(v\).
- Option (C): Joins on \(R.P=S.Y\), which is incorrect.
- Option (D): Joins on \(S.Y=R.Q\), which is also incorrect.
Final Answer: \[ \boxed{\Pi_P\left(S \bowtie_{S.X=R.Q} R\right)} \] Correct Option: (B)
Was this answer helpful?
2
Questions Asked in GATE CS exam
A database has 25,000 fixed-length records of 100 bytes (primary key 15 bytes). The data file is block-aligned so each record is fully contained within a block. The file is indexed by a primary index file, also block-aligned and ordered. Block size is 1024 bytes and a block pointer is 5 bytes. Each index entry stores the block’s anchor key (15 bytes) and a pointer (5 bytes). Binary search on an index file of \(b\) blocks needs \(\lceil \log_2 b \rceil\) block accesses in the worst case. Given a key, the number of block accesses required to identify the data file block that may contain the record, in the worst case, is ____________.
- GATE CS - 2023
- Database Management Systems