GATE IT 2008 | Question: 61

Question

Let $R (A, B, C, D)$ be a relational schema with the following functional dependencies :
$A → B$, $B → C$, $C → D$ and $D → B$. The decomposition of $R$ into $(A, B), (B, C), (B, D)$

• A. gives a lossless join, and is dependency preserving
• B. gives a lossless join, but is not dependency preserving
• C. does not give a lossless join, but is dependency preserving
• D. does not give a lossless join and is not dependency preserving

Comments

Kuljeet Shan

Yes it is applicable here !!

---

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

NOTE :

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

Detailed Video Solution with Correct Method

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 

The Chase Algorithm is the Correct and time saving method for Non-Binary Decomposition related questions. 

Refer the following Playlist for Chase Algorithm and other variations related to Decompositions.

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

---

 

 Applied this Rule !!

 

 

For lossless   

 must be true

if  no common attribute in R1 and R2, therefore lossy join will be there

For Lossy

https://www2.cs.sfu.ca/CourseCentral/354/zaiane/material/notes/Chapter7/node8.html#SECTION00731200000000000000

Answer 1

Option A.

$(A,B)$ $(B,C)$ $-$ common attribute is $B$ and due to $B\to C$, $B$ is a key for $(B,C)$ and hence $ABC$ can be losslessly decomposed into $(A,B)$ and $(B,C)$.

$(A, B, C) (B, D)$, common attribute is $B$ and $B\to D$ is a FD (via $B\to C, C\to D$), and hence, $B$ is a key for $(B, D).$ So, decomposition of $(A, B, C, D)$ into $(A, B, C) (B, D)$ is lossless.

Thus the given decomposition is lossless.

The given decomposition is also dependency preserving as the dependencies $A\to B$ is present in $(A, B), B\to C$ is present in $(B, C), D\to B$ is present in $(B, D)$ and $C\to D$ is indirectly present via $C\to B$ in $(B, C)$ and $B\to D$ in $(B, D).$

http://www.sztaki.hu/~fodroczi/dbs/dep-pres-own.pdf

Comments

How does C→B in (B,C) and B→D in (B,D), are the dependencies not the other way round ?

---

in R(BC) B->C and C->B ,

in R(CD) C->D and D->B both are there .

---

We are dividing R into (A, B), (B, C), (B, D) and our original dependencies are A → B, B → C, C → D,  and D → B

In (B, C) =  from C → D,  and D → B we can arrive at C → B

In (D, B) = From  B → C and C → D we can derive B→ D

Answer 2

Answer is a i.e. dependancy preserved and lossless decompostion.

Comments

GOOD ANSWER......

---

did by same method , i just missed out C -> D

---

@Yedilmaagemore|

Visited same question again on same date ,something suprisngly amazing to me...

Answer 3

B is a key in all the decomposed relations, hence lossless.

Now, let's see if it is FD preserving or not. We directly get $A→B, B→C  $ and $D→B.$
Can we get $C→D$ back?

In the relation $R(B,C)$ we directly get $B→C$ but from the original FDs we can infer that the FD $C→B$ would also hold here.

Hence, if we take this $C→B$ and fuse it with $B→D$ (also implied) we get $C→D$ back.

So, FD preserving.

 

PS: Don't find the closure of every attribute in the exam, it's heavily time consuming. Just try to derive what's required.

 

Option A.

Answer 4

BEST ANSWER

R(A, B, C,D)

A----->B

B----->C

C----->D

D----->B

R1(A,B)                         R2(B,C)                           R3(B,D)

A----->B                         B----->C                          D----->B

                                     C----->B                           B----->D

 

Check Lossless Condition

R1         Intersection   R2  =  B  (Which is SK of R2)       So     R1R2(ABC)

R1R2    Intersection   R3  =  B  (Which is SK of R3)

So Lossless Satisfied.

--------------------------------------

Check Dependency preserving

Since in R1, R2 and R3  dependecy given : 

A----->B        B----->C     C----->B         B----->D        D----->B

all Dependency preserved according to original schema given : A----->B  ,      B----->C    , C----->D   According to (C---->B----D)       ,   D----->B

Answer is a (dependancy preserved and lossless decompostion)

                                                            

Answer 5

The answer is A.

 

Best way to understand is to study about Closure. The way C --> D is preserved is by through  B --> C and D --> B, by concluding that these dependencies give C --> B. When we conclude this, R3(B,D) relation can be also be written as R3(C,D) which itself makes the dependency clear.