IAE Academy

GATE 2018 CS Q.41: solution and answer

GATE 2018 · CSQ.41 · 2 marks · MCQ

Consider the relations r(A, B) and s(B, C), where s.B is a primary key and r.B is a foreign key referencing s.B. Consider the query

Q: r ⋈ (σ_{B<5}(s))

Let LOJ denote the natural left outer-join operation. Assume that r and s contain no null values.

Which one of the following queries is NOT equivalent to Q?

  1. (A)

    σ_{B<5}(r ⋈ s)

  2. (B)

    σ_{B<5}(r LOJ s)

  3. (C)

    r LOJ (σ_{B<5}(s))

  4. (D)

    σ_{B<5}(r) LOJ s

See the question in the paper

Answer and solution

ANSWER

Option (C) is not equivalent to Q.

Official answer: CSource: Official answer key, GATE 2018 CS (IIT Guwahati)

  1. Since is a primary key and is a foreign key referencing it, with no nulls, every tuple of matches exactly one tuple of .

  2. So returns exactly the tuples of with , each extended by its value from .

  3. (A) : every tuple joins with its tuple, and the selection keeps those with . This equals .

  4. (B) : no tuple is left unmatched, so no padding occurs and . After the selection it equals .

  5. (D) : each remaining tuple still has its match in , so no padding occurs. The result is the tuples of with extended by , which is .

  6. (C) : a tuple of with finds no partner in the filtered , so the outer join keeps it with . The result has extra tuples, so it differs from .

  7. Example: and . Then , but (C) returns .

KEY IDEA

With a foreign key to a primary key, every tuple of r has exactly one match in s. A selection on s before an outer join removes matches and creates null-padded rows, while a selection on the joined result or on r alone removes whole rows.

WATCH OUT FOR

Assuming the outer join is harmless in (C) because of the foreign key. The key guarantees a match in s, but not in the filtered s, so tuples of r with B at least 5 survive with a null C.

From the GATE 2018 CS paper. Every question of this paper · Download the full paper · All 13 Relational algebra questions, with notes

More Relational algebra questions