7,171 views

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

The Chase Test is called as Matrix method, I guess.
Thanks sir

@Deepak Poonia sir ,@gatecse

What I think:

PQST is key.

In D2 :

PQST is not present i.e. key is not preserved. So it will be lossy.

In D1:

(PQST)     is key , so no problem.

(PTX)      P->X, so PT->X because PT is super key and it can be joined with (PQST).

(QY)     Q-Y , i.e. Q is key for this table.

(YZW)  Y->ZW i.e Y is key for this table.

in D1 key is present in every decompostion, so it can be joined with (PQST).

So option A is correct.

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 :

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

Best !!

Thank you so much Sir for this wonderful explanation! Have lost all faith over successive combination method :) Chase Algorithm is the fastest and  the best way for checking lossless/lossy decomposition.

Also Sir, is there any formal proof as to why the "Successively Joining" method fails and why "Chase algorithm" works? Like why some spurious tuples detected by "Successively Joining" method may not be spurious at all, rending the decomposition to be actually lossless which can be determined only by "Chase Algorithm" ?

@Deepak Poonia sir, thank you so much for clarification of concepts, such a detailed and wonderful explanation🙏

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.

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. The Correct answer should be A.

Because D1 is lossless and D2 is lossy decomposition.

Yeah I understood why, thanks for the explanation. The definition says that the common attribute set has to belong to $F^+$. That means it can also be a superkey.

So, should we also check in SK for common attributes among relations to prove lossless decomposition?

I have solved all questions till now by only considering CK, it came out to be the right answer.

Though we can use Chase Algorithm, I am asking for binary decompositions.

@ankit3009 Yeah common attribute of the relations which you want to join must be a CK or a SK in either of the relation or both then that join will be lossless join in binary decomposition.