retagged by
13,051 views
27 votes
27 votes

Consider the relation $R(P,Q,S,T,X,Y,Z,W)$ with the following functional dependencies.

$$PQ\rightarrow X;\quad P\rightarrow YX;\quad Q\rightarrow Y; \quad Y\rightarrow ZW$$

Consider the decomposition of the relation $R$ into the constituent relations according to the following two decomposition schemes.

  • $D_1:\quad R=[(P,Q,S,T);\;(P,T,X);\;(Q,Y);\;(Y,Z,W)]$
  • $D_2:\quad R=[(P,Q,S);\;(T,X);\;(Q,Y);\;(Y,Z,W)]$

Which one of the following options is correct?

  1. $D_1$ is a lossless decomposition, but $D_2$ is a lossy decomposition
  2. $D_1$ is a lossy decomposition, but $D_2$ is a lossless decomposition
  3. Both $D_1$ and $D_2$ are lossless decompositions
  4. Both $D_1$ and $D_2$ are lossy decompositions
retagged by

5 Answers

48 votes
48 votes

The Detailed Video Solution to this question can be found in the following link : https://youtu.be/HrggFKi-awQ 

Chase Algorithm aka tableau method is Correct and Time saving method for Non-Binary Decomposition related questions. 

Decomposition $D_1 :$

First Create a Table, whose columns are attributes, and rows are the sub-relations. Fill the cells with $a-entry$ if the subrelation contains the corresponding attribute.

Now, since we got a Row with all cells containing $a-entries,$ hence, Decomposition $D_1$ is Lossless.

Decomposition $D_2 :$

Since, there is No more changes possible in the table, and there is No row with all $a-entries,$ So, Decomposition $D_2$ is Lossy.

NOTE :

The video solution to this question can be found in the following link :

https://youtu.be/HrggFKi-awQ

The method of “Successively Joining Two Sub-relations at a time in lossless manner” is $\color{Red}{\text{WRONG}}$ way of solving questions related to Non-binary decompositions. Yet, most students apply this wrong method only.

One Example to show that this “Successively Joining Two Sub-relations” method is wrong can found in below link :

https://youtu.be/oldYIleT7YI 

Chase Algorithm aka tableau method is Correct and Time saving method for Non-Binary Decomposition related questions. 

Refer this Playlist for Chase Algorithm and other variations related to Decompositions:

Decomposition Complete Playlist | The Chase Test for Non-Binary Lossless Join Decomposition 

edited by
12 votes
12 votes

Given:

Relation     →      R(P,Q,S,T,X,Y,Z,W)

FDs           →       PQ→X;P→YX;Q→Y;Y→ZW

Firstly find candidate key for relation using closure method.

Since P,Q,S and T can’t derive from given dependencies. So they must be necessarily on the Determinant side.

Lets check for sufficient condition:

(PQST)ᐩ = {P,Q,S,T,Y,Z,W} means PQST is candidate key in R.

Main condition for lossless join of two Relations X  and Y →  there must be some Z = X∩Y such that Z  is a CK either in X or Y.

Given: Decompositions → 

D1:R=[(P,QS,T);(P,T,X);(Q,Y);(Y,Z,W)]

R1(PQST) is CK of given R. 

R2(PTX) has  FD : {P->X} so PT is CK.

R3(QY) has FD: {Q → Y} so Q is CK

R4(YZW) has FD : {Y→ ZW} so Y is CK.

R1 and R2 can be join without loss since R1∩R2=(PT) which is a CK in R2.

Now we have R5(PQSTX) with CK={PQST}.

R3 and R4 can be joined without loss since R3∩R4=(Y) which is CK in R4.

Now we have R6(QYZW) with CK={Q}

R5∩R6 = {Q} which is a CK in R6 So R5 and R6 can joined into R without any loss.

So D1 is LOSSLESS.

 

D2:R=[(P,Q,S);(T,X);(Q,Y);(Y,Z,W)]

R1(PQS) satisfy no FD.

R2(TX) satisfy no FD.

R3(QY) has FD: {Q → Y} so Q is CK

R4(YZW) has FD : {Y→ ZW} so Y is CK.

We can clearly see that R2 has no common attribute with any other relations, hereonly we can say that decomposition is lossless.

Since R1∩R2=Ø so can’t combine without loss.

R3 and R4 can be joined without loss since R3∩R4=(Y) which is CK in R4.

Now we have R5(QYZW) with CK={Q}

Since R1∩R5={Q} which is CK in R5 so can combine R1 and R5.

Now we new relation R6(PQSYZW).

Still R2∩R6=Ø so can’t combine without loss.

So D2 is LOSSY.

The correct Answer is A. D1 is a lossless decomposition, but D2 is a lossy decomposition.

 

1 votes
1 votes

Condition for:-

Lossless Decomposition: 

  1. R1 U R2 U R3….. = R (i.e all attribute present in decomposed relation) 
  2. R1⋈R2 = R  (Use if relation given)  OR   While combining relation common attribute should be Super key (SK) of at least one relation.   

 

 

 

 

edited by
0 votes
0 votes

The Correct answer should be A.

Because D1 is lossless and D2 is lossy decomposition.

 

Answer:

Related questions

16 votes
16 votes
4 answers
1