GATE CS 2008 Q68 — Relational Model: Relational Algebra

To find the equivalent queries, let us analyze each expression based on the schema where the common attributes between $R$ and $S$ are $P$ and $Q$:

• Query I: $\Pi_P (R \bowtie S)$
  Since the common attributes of $R$ and $S$ are $P$ and $Q$, the natural join $R \bowtie S$ performs an equality match on both $P$ and $Q$. Thus, the $(P, Q)$ pairs in the join are exactly those present in both relations. Projecting this result on $P$ yields the $P$-values of the common $(P, Q)$ pairs.
• Query III: $\Pi_P (\Pi_{P, Q} (R) \cap \Pi_{P,Q} (S))$
  This expression explicitly finds the intersection of the $(P, Q)$ pairs from both relations and then projects the result on $P$. This is semantically identical to Query I. Thus, I $\equiv$ III.
• Query IV: $\Pi_P (\Pi_{P, Q} (R) - (\Pi_{P,Q} (R) - \Pi_{P,Q} (S)))$
  Using the set-theoretic identity $A - (A - B) = A \cap B$, we can simplify the inner expression: $$\Pi_{P, Q} (R) - (\Pi_{P,Q} (R) - \Pi_{P,Q} (S)) = \Pi_{P, Q} (R) \cap \Pi_{P,Q} (S)$$ Applying the outer projection $\Pi_P$ makes this query identical to Query III. Thus, I $\equiv$ III $\equiv$ IV.
• Query II: $\Pi_P (R) \bowtie \Pi_P(S)$
  This performs a join only on the attribute $P$. For example, if $R = \{(1, 2)\}$ and $S = \{(1, 3)\}$, then $\Pi_P(R) \bowtie \Pi_P(S) = \{1\}$, but $R \bowtie S = \emptyset$ (and thus $\Pi_P(R \bowtie S) = \emptyset$). Hence, Query II is not equivalent to the others.

Therefore, only queries I, III, and IV are equivalent.