The Gateway to Computer Science Excellence
+41 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 by
edited by | 6k views
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

3 Answers

+62 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 .

 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)??
+31 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 ....
+4 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

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,345 questions
60,470 answers
95,272 users