GATE CSE 2008 | Question: 68

Question

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)$

• A. Only I and II
• B. Only I and III
• C. Only I, II and III
• D. Only I, III and IV

Comments

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

---

here  2 is not equivalent here one counter example: if R contain tuple like (1,2)  and s contain tuple like (1,3)

so natural join will thorugh out  .but if you look at query b then it will select p which is 1 and it will give in output as 1

which is not equivalent.

Answer 1

(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\}$

Comments

@samarpita @gatecse  then what is normal join ??

---

@abir_banerjee Natural join is a join based on common columns in the tables. 

---

Representation of set 

Answer 2

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. 

Comments

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

---

short and beautiful explanation

Answer 3

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

​​​​​​Thanks for your time.

Comments

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

Answer 4

(D)
In I, Ps from natural join of R and S are selected.
In III, all Ps from intersection of (P, Q) pairs present in R and S.
IV is also equivalent to III because (R – (R – S)) = R ∩ S.
II is not equivalent as it may also include Ps where Qs are not same in R and S.