The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+24 votes

Let R and S be two relations with the following schema

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

$S(\underline{P}, \underline{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 (68.8k points) | 2.2k 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 !!

2 Answers

+36 votes
Best answer
(d) i, iii, iv

iv) is 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", ``q3"\right\rangle \\ \left\langle``2", ``def", ``q1", ``q2", ``q3"\right\rangle \right\}$

Now, consider the given queries:

i. $R \bowtie S$ gives

$\left\{\left\langle``1", ``abc", ``p1", ``p2", ``p3", ``q1", ``q2", ``q3" \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", ``bc" \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 Loyal (3.4k points)
selected 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?
+14 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 (775 points)
Absolutely Correct.

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

32,330 questions
39,146 answers
36,501 users