GATE CS 2018 Q41 — Relational Model: Relational Algebra

The query $Q = r \bowtie (\sigma_{B < 5}(s))$ returns only those tuples from $r$ and $s$ where the join attribute $B < 5$. Any tuple in $r$ with $B \ge 5$ is completely excluded from the result.

Let us analyze why Option C is NOT equivalent to $Q$:

• In $r \text{ LOJ } (\sigma_{B < 5}(s))$, the right relation $\sigma_{B < 5}(s)$ contains only tuples with $B < 5$.
• For any tuple in $r$ with $B \ge 5$, there is no matching tuple in the right relation.
• Since it is a Left Outer Join (LOJ), these unmatched tuples from $r$ (where $B \ge 5$) are still preserved in the final output, padded with $\text{NULL}$ for attribute $C$.
• Thus, the result of Option C contains tuples with $B \ge 5$, whereas $Q$ does not.

For the other options, since $r.B$ is a foreign key referencing the primary key $s.B$ and there are no nulls, every tuple in $r$ has a unique matching tuple in $s$. Therefore, $r \text{ LOJ } s \equiv r \bowtie s$. This makes options A, B, and D equivalent to $Q$:

• A: $\sigma_{B < 5}(r \bowtie s) \equiv r \bowtie \sigma_{B < 5}(s)$ (Standard selection push-down).
• B: $\sigma_{B < 5}(r \text{ LOJ } s) \equiv \sigma_{B < 5}(r \bowtie s) \equiv Q$.
• D: $\sigma_{B < 5}(r) \text{ LOJ } s \equiv \sigma_{B < 5}(r) \bowtie s \equiv r \bowtie \sigma_{B < 5}(s) \equiv Q$.