Let R and S be relational schemes such that R={a,b,c} and S={c}. Now consider…

2009

Let R and S be relational schemes such that R={a,b,c} and S={c}. Now consider the following queries on the database:

gateqa
IV) SELECT R.a, R.b
       FROM R,S
            WHERE R.c=S.c

Which of the above queries are equivalent?

  1. A.

    I and II

  2. B.

    I and III

  3. C.

    II and IV

  4. D.

    III and IV

Attempted by 49 students.

Show answer & explanation

Correct answer: A

Answer: Queries I and II are equivalent.

  • Interpretation of Query I and Query II: Both specify the set of (a,b) values from relation R for which there exists a tuple in S with the same c value. Formally they capture:

    {(a,b) | ∃r ∈ R, ∃s ∈ S such that r.c = s.c and (a,b) = (r.a,r.b)}.

  • Therefore Query I and Query II produce the same result under standard set-based relational-algebra semantics (duplicates are not preserved).

  • Why Query III differs: Query III uses a universal condition (division-like semantics). It returns (a,b) pairs that are associated with every c value in S. That is a strictly stronger requirement than "there exists a matching S tuple," so Query III is not equivalent to I/II.

  • Why Query IV differs in general: The SQL query SELECT R.a, R.b FROM R,S WHERE R.c = S.c returns the join-projection. Under set semantics this matches I/II, but SQL without DISTINCT uses bag semantics and can produce duplicate (a,b) rows if an R tuple matches multiple S tuples (or if S contains duplicates). Thus Query IV is not guaranteed to be equivalent to the set-based expressions I and II unless we assume S has no duplicates or we add DISTINCT to the SQL.

Summary: Only Query I and Query II are equivalent under the usual set-based interpretation of relational-algebra expressions. Query III enforces an "all c in S" condition (division), and Query IV may differ because of SQL's bag semantics (duplicates) unless DISTINCT or duplicate-free S is assumed.

Explore the full course: Gate Guidance By Sanchit Sir