Dark Mode

7,171 views

21 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?

- $D_1$ is a lossless decomposition, but $D_2$ is a lossy decomposition
- $D_1$ is a lossy decomposition, but $D_2$ is a lossless decomposition
- Both $D_1$ and $D_2$ are lossless decompositions
- Both $D_1$ and $D_2$ are lossy decompositions

@Deepak Poonia sir ,@gatecse

please check this

What I think:

**PQST** is key.

**In D2 :**

** PQST** is not present i.e.

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

0

28 votes

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 :

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

Thank you so much @Deepak Poonia 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" ?

1

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

1

10 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(__PT__X) 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.**

0 votes

0

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.

Please help @adad20. @Vishal_kumar98

0

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

1