GATE CS 2014 Set 2 Q54 — Tuple Calculus and SQL

To find the equivalent query, let us analyze the behavior of the original nested query:

select * from R where a in (select S.a from S)

• For each tuple $r \in R$, the query checks if the value $r.a$ exists in the set of values of $S.a$.
• If it exists, the tuple $r$ is selected.
• The number of times a tuple $r$ appears in the output is exactly equal to its original frequency in $R$. The multiplicity of $r.a$ in $S$ has no effect on the output multiplicity.

Now let us evaluate the options:

• Option A: select R.* from R, S where R.a=S.a
  This performs a regular inner join. If a value $r.a$ appears $k$ times in $S$, the tuple $r$ will be duplicated $k$ times in the output. This changes the original multiplicity.
• Option B: select distinct R.* from R,S where R.a=S.a
  The distinct keyword removes all duplicate tuples. If relation $R$ originally contained duplicate tuples, they would be collapsed into a single tuple, which does not match the original query's behavior.
• Option C: select R.* from R,(select distinct a from S) as S1 where R.a=S1.a
  By selecting distinct a from $S$ first, we ensure that each value of $a$ appears at most once in the temporary relation $S1$. Joining $R$ with $S1$ ensures that each matching tuple in $R$ is joined with exactly one tuple from $S1$. Thus, the original multiplicity of tuples in $R$ is perfectly preserved, making it equivalent to the IN subquery.
• Option D: select R.* from R,S where R.a=S.a and is unique R
  This is syntactically invalid in standard SQL and does not preserve the correct semantics.

Therefore, Option C is the correct query.