The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+30 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
asked in Databases by Veteran (52.1k points)
edited by | 4.3k 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

+54 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\}$
answered by Active (3.3k points)
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>}
+26 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. 

answered by Junior (747 points)
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 ....
+1 vote

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

​​​​​​Thanks for your time.

answered by Junior (667 points)

@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 ?


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
49,814 questions
54,518 answers
75,288 users