GATE CS 2004 Q13 — Tuple Calculus and SQL

The question asks which relational algebra expression will necessarily produce an empty relation under the given referential integrity constraint.

We are given:

• $R_1(\underline{A}, B, C)$ with primary key $A$.
• $R_2(\underline{D}, E)$ with primary key $D$.
• $C$ is a foreign key in $R_1$ referencing the primary key $D$ in $R_2$.

By the definition of referential integrity, every value in the foreign key column $C$ of relation instance $r_1$ must exist in the primary key column $D$ of relation instance $r_2$. In terms of relational algebra, this subset relationship is expressed as:

Let us analyze the options based on this set inclusion property:

1. $\Pi_D(r_2) - \Pi_C(r_1)$: Since $\Pi_C(r_1) \subseteq \Pi_D(r_2)$, this expression represents elements in $D$ that are not referenced by $C$. This set can be non-empty if there are primary key values in $r_2$ that have no matching records in $r_1$.
2. $\Pi_C(r_1) - \Pi_D(r_2)$: Since every element in $\Pi_C(r_1)$ must also be in $\Pi_D(r_2)$ (due to the subset constraint $X \subseteq Y \implies X - Y = \emptyset$), subtracting $\Pi_D(r_2)$ from $\Pi_C(r_1)$ will always yield an empty relation.
3. $\Pi_D(r_1 \bowtie_{C \neq D} r_2)$: This performs a theta-join where $C \neq D$. This can easily produce a non-empty relation if there are multiple distinct keys in $r_2$.
4. $\Pi_C(r_1 \bowtie_{C = D} r_2)$: This is an inner join on the foreign key constraint, which yields the set of all referenced values $\Pi_C(r_1)$. This is non-empty as long as $r_1$ contains at least one tuple.

Thus, only option B is guaranteed to be empty under all valid instances.