in Databases edited by
51 votes

Let R and S be two relations with the following schema

$R(\underline{P,Q}, R1, R2, R3)$

$S(\underline{P,Q}, S1, S2)$

where $\left\{P, Q\right\}$ is the key for both schemas. Which of the following queries are equivalent?

  1. $\Pi_P \left(R \bowtie S\right)$

  2. $\Pi_P \left(R\right) \bowtie \Pi_P\left(S\right)$

  3. $\Pi_P \left(\Pi_{P, Q} \left(R\right) \cap \Pi_{P,Q} \left(S\right) \right)$

  4. $\Pi_P \left(\Pi_{P, Q} \left(R\right) - \left(\Pi_{P,Q} \left(R\right) - \Pi_{P,Q} \left(S\right)\right)\right)$

  1. Only I and II
  2. Only I and III
  3. Only I, II and III
  4. Only I, III and IV
in Databases edited by


Query 1,3 and 4 filter the rows based on equality of both P and Q attribute but in Query 2 it is only P.
(y) answer in one line !!
I have only one doubt, Should not P and Q be underlined together instead of being underlined separately?
the best way to check is to look at 2nd & 3rd options carefully you will see that in 3rd one there is intersection of both p&q means in both the tables i.e R.p=S.p & R.q=S.q but in 2nd option ,only R.p=S.p need to be satisfied so 2nd option gets eliminated now check other options all are equivalent.
@AHWAN he also mentioned separately {P,Q} is key for both tables means a compound key (>= 2 attributes) is defined for the tables.
2nd query is differ from rest of all becoz it use only p for filtering. all query are use p and q both atrribute for filtering.
The best approach to filter out the options would be

Since (A n B)=(A-(A-B))

so (III) and(IV) are definitely going to be equal
Shivam this is the reason i think they introduce msq :p

Subscribe to GO Classes for GATE CSE 2022

3 Answers

72 votes
Best answer
(D) i, iii, iv

iv) is the expansion for natural join represented with other operators.

Why ii is not equivalent? Consider the following instances of R and S

$R: \left\{\left\langle``1", ``abc", ``p1", ``p2", ``p3"\right\rangle, \\ \left\langle``2", ``xyz", ``p1", ``p2", ``p3"\right\rangle \right\}$

$ S: \left\{\left\langle``1", ``abc", ``q1", ``q2"\right\rangle \\ \left\langle``2", ``def", ``q1", ``q2"\right\rangle \right\}$

Now, consider the given queries:

i. $R \bowtie S$ gives

$\left\{\left\langle``1", ``abc", ``p1", ``p2", ``p3", ``q1", ``q2" \right\rangle \right\}$

Projecting $P$ gives $\left\{\left\langle ``1" \right\rangle \right\}$

ii. $\pi_P\left(R\right) \bowtie \pi_P\left(S\right)$ gives

$\left\{\left\langle``1" \right\rangle \left\langle ``2" \right\rangle \right\} \bowtie \left\{\left \langle ``1" \right\rangle \left\langle ``2"\right\rangle \right\}$

$=\left\{\left\langle ``1", ``2" \right\rangle \right\}$

iii. $\Pi_P \left(\Pi_{P, Q} \left(R\right) \cap \Pi_{P,Q} \left(S\right) \right)$ gives

$\left\{\left\langle``1", ``abc" \right\rangle, \left\langle ``2", ``xyz" \right\rangle \right\} \cap \left\{\left \langle ``1", ``abc" \right\rangle, \left\langle ``2", ``def" \right \rangle  \right\}\\ = \left\{\left\langle``1", ``abc" \right\rangle \right\}$

Projecting $P$ gives $\left\{\left\langle ``1" \right\rangle \right\}$

iv. $\Pi_P \left(\Pi_{P, Q} \left(R\right) - \left(\Pi_{P,Q} \left(R\right) - \Pi_{P,Q} \left(S\right)\right)\right)$ gives

$\left\{\left\langle``1", ``abc" \right\rangle, \left\langle ``2", ``xyz" \right\rangle \right\} \\- \left( \left\{\left\langle``1", ``abc" \right\rangle, \left\langle ``2", ``xyz" \right\rangle \right\} - \left\{\left\langle``1", ``abc" \right\rangle, \left\langle ``2", ``def" \right\rangle \right\} \right) $

$= \left\{\left\langle``1", ``abc" \right\rangle, \left\langle ``2", ``xyz" \right\rangle \right\} \\- \left\{\left\langle ``2", ``xyz" \right\rangle \right\} \\ =   \left\{\left\langle``1", ``abc" \right\rangle \right\}$

Projecting $P$ gives $\left\{\left\langle ``1" \right\rangle \right\}$
edited by


What is the right answer ?? option c or d ? .In key everywhere it is given as option c .Anyone plz explain
Key everywhere? Answer is D only.
very well explained
ii. πP(R)⋈πP(S)gives



how is this correct?

shouldnt it be{<1,1>,<2,2>}?????? because join will take equality condition.

@arjun Sir is there any associativity for the DIFFERENCE OPERATION ?

(iv)  ΠPP,Q(R)  −  (ΠP,Q(R)  −  ΠP,Q(S))) 

If we first take R-R = null
 then null-S = null

Any meaning in this interpretation ?

2nd query will take values of P whose corresponding Q do not match, like
one tuple in R is (P1, Q1)   (not writing extra attributes)
one tuple in S is (P1, Q2)
in all other queries such P1 won't be there but in 2nd query P1 will appear.
(all queries except 2nd filtering based on P,Q pair.)
what is the meaning of {P,Q} in gate 2008 question(Let R and S be two relations.....)? Either it is composite key or separate primary keys or keys.
Superb Explanation .
reshown by

 Relation R

P Q R1 R2 R3
1 abc p1 p2 p3
2 xyz p1 p2 p3

Relation S

P Q S1 S2  
1 abc q1 q1  
2 xyz q2 q2  


What if in both relation R and S if we take (P,Q) exactly same then in 1) option  π P(R⋈S) we will get {1,2} and which makes this all wrong! 

My question is can we take same values of (P,Q) in both relation R and S, since it's a key in two different tables?

@ Kamal Pratap  May you please pitch in veere?!

@ Rupendra Choudhary  Please you too pitch in brother.

Two queries are equivalent means, on all possible input they will produce the same result. You showed one such input, on which the queries produce same results. Which is not sufficient to say that they will produce same results on all inputs.

However, the answer proposed an input on which the queries are producing different results. Which means that they do not produce same results on all input. Thereby, sufficient to conclude that they are not equivalent.
@Aravind only 4 attributes in S, from where are you adding extra column for adding q3?
how projecting p gives {<1>}
Domain of PQ should be same in both R and S?...If "def" is not in R(Q) then How you have taken "def" in S(Q)??
Shouldn’t the output of second query be {⟨<‘1">,  <‘‘2">} which is 1 and 2 in two different rows ?
Thanks for the explanation with an example.
nice example man, very clean with  the example

NOTICE:   A ∩ B = ( A – ( A – B ) )

Hence (iii) and (iv) are same.

33 votes

Natural join is based on the common columnS of the two tables. 
We have 2 common columns in R and S which are P and Q

Option I: Both P and Q are used while doing the join. i.e both P and Q are used to filter.
Option 2: Q is not used here for filtering. Natural join is done on ( all P's from R and all P's from S ). Clearly different from option 1.

For Option 3 and Option 4, draw a venn diagram and it will be clear that: R-(R-S) = R $\bigcap$ S. And both these options use P and Q as filters. So 1,3 and 4 are equivalent. 
Option D is the answer. 


Absolutely Correct.
how we know that they are using natural join as we denote the Natural join by (*)
because we have common attributes in both the relations...and whenever this is the case join is actually natural join ....
5 votes

Don't get confused once go through this page it's too simple :::)

​​​​​​Thanks for your time.


@Swami patil In your (a) part explanation in above picture, i think it will be 1,2,3 there, because 3 is also common in both P's of your R and S relation. Isn't it ?

Here P, Q in total is a candidate key so,3 is not possible.

Related questions