GATE CSE 1998 | Question: 2.19

Question

Which of the following query transformations (i.e., replacing the l.h.s. expression by the r.h.s expression) is incorrect? R1 and R2 are relations, C1 and C2 are selection conditions and A1 and A2 are attributes of R1.

• A. $\sigma_{C_1} \left(\sigma_{C_2}\left(R_1\right)\right) \to \sigma_{C_2} \left(\sigma_{C_1}\left(R_1\right)\right)$
• B. $\sigma_{C_1} \left(\pi_{A_1}\left(R_1\right)\right) \to \pi_{A_1} \left(\sigma_{C_1}\left(R_1\right)\right)$
• C. $\sigma_{C_1} \left(R_1 \cup R_2\right) \to  \sigma_{C_1}\left(R_1\right) \cup \sigma_{C_1} \left(R_2\right)$
• D. $\pi_{A_1} \left(\sigma_{C_1}\left(R_1\right)\right) \to \sigma_{C_1} \left(\pi_{A_1}\left(R_1\right)\right)$

Comments

@nishant_magarde read the arjun sir comment in the below answer 

---

here b and d both are incorrect .can any one explain it

---

some points

1. question asking whether replacing lhs exp with rhs exp is fine or not
2. If we are assuming c1 is applied on a1 for option B then the same should hold for option D also. (In option D the range is reduced early but still the condition is same)
3. Take a table and take two conditions, one works on a1 and the other doesn’t.. see for yourself.
   
   both B and D are wrong. (basically equivalent) 

Answer 1

D) if the selection condition is on attribute $A2$,  then we cannot replace it by RHS as there will not be any attribute $A2$ due to projection of $A1$ only.

Comments

what if in b option i have condition c1 for both a1 and a2 ??

---

It is asked if LHS can be replaced by RHS , so basically does RHS able to produce same ROWS and COLUMNS that LHS can PRODUCE ?

 

-> In option (b) , in LHS , we first TAKE OUT a column A1 and then apply condition  C1 on THAT column .

So it is guaranteed that condition is applied on A1.

Thus we get Column A1 and some Rows in answer according to condition C1.

 

Now in RHS we apply SAME  condition C1 on WHOLE TABLE .

Whole Table will definitely contain Column A1.

And then we keep only Column A1,and eliminate Rest , same as lhs.

 

 

-> In option (b), it is inverse of option (b).

LHS = First Condition c1 Is Applied on Whole table. They Have Not Mentioned that condition is applied on which column. Lets assume its applies on A2. Thus we get some rows.

Now Projection applied on A1. Thus we get column A1 and rows(which satisfy c1) in OUTPUT.

 

But In RHS , they are Projecting column A1 and applying same PREVIOUS Condition C1 which we assumed is applied on A2.

But because we projected only A1 from table we cant apply condition on A2 (bcoz it doesnt exist) . ERROR.

 

ITS JUST THE ORDER THAT MATTERS HERE AND WHETHER RHS CAN PRODUCE SAME OUTPUT AS LHS IN ALL CASES.

---

Is not option A and B is exactly same?

the only difference between A and B is, LHS of A is in RHS of B, and LHS of B is in RHS of A.

 

Then how D is the answer but B is not?

Answer 2

actually in (b) option for validity of L.H.S condition c1 must be applied on attribute a1 and same condition will be applicable  after projection will give  same answer

but in option (d) for validity condition may be any thing because selection is being here first suppose if selection is based on any other attribute other than a1 then in RHS after projection how can we apply same condition because attribute other than a1 are not present there

am i right sir

Comments

if the option (d) comes first then (b) , then (b) would have been wrong?!

 

how is so??

---

Other way to look at this question is like just check if number of attributes available for select operator is same in both LHS and RHS. If projection is being done before selection, attributes available for selection are less and hence the option d.

why B is correct then? Using above logic in LHS of B suppose select operator getting attribute A,B for comparison then in RHS it is getting superset of attributes which will yield same result.

---

as u stated for D that "first suppose if selection is based on any other attribute other than a1 then in RHS after projection how can we apply same condition"

This can happen with RHS of III also. Isn't it?

Answer 3

a) & c) are correct!  only b) & d) we need to look deep :

Actually, we are assuming here that LHS to be specific and trying to transform the same meaning to RHS. So in b) LHS specifically selects attribute A1 then applies condition C1 so interchanging them in RHS will do no harm.

But in d) we are keeping projections options open by applying first C1 then A1 but in RHS we are restricting by projecting only A1 then C1 so it's not safe.  

For RHS in d) C1 may have been related to other attributes but since they will not be present then the query might return empty but in LHS we are keeping options and not restricting.

Thus answer d

Comments

Other way to look at this question is like just check if number of attributes available for select operator is same in both LHS and RHS. If projection is being done before selection, attributes available for selection are less and hence the option d.

why B is correct then? Using above logic in LHS of B suppose select operator getting attribute A,B for comparison then in RHS it is getting superset of attributes which will yeild same result.

Answer 4

Let the relation R be

A	B	C
1	x	a
2	y	b
3	z	c

Let the condition be  πA(σ ("A=2" and "C = b" (R))), it will fetch the result as "2". On the other hand the condition  (σ ("A=2" and "C = b" (πA (R)))), it will fetch nothing.

Therefore, option D is false.

 

Comments

This is the best answer with example. @Arjun do mark it useful.