Gateforum DBMS

Question

Comments

option A) is correct

both of the decomposition {(BD),(ABC)} and {(BD),(ADC)} are lossless and dependency preserving.

---

c is given as solution

---

how {(BD) , (ADC)} is dependency preserving ?

---

AB and AD are candidate keys so yeah :| i missed that

---

 G.K.T not preserved

---

so it should be a option right ?

---

check options once again

---

dependencies in {(BD) , (ADC)} are $B->D,D->B,AD->C$............(i)

now, you think how $AB->C$ is preserved, it is actually preserved but not directly.

take closer of $AB$ using dependencies of (i).

$AB^+->ABDC$, now see, $AB->C$ is covered and hence preserved

---

still unclear,

dependencies in {(BD) , (ADC)} are B−>D, D−>B, AD−>C

how AB---->C is preserved

is this what you are saying that D-->B so AB⁺---->ABCD?

---

yes, exactly.

---

ok thank you :)

---

AB->C is not preserved because B is not part of the R2(ADC).

Only after we join R1(BD), r2(ADC) ,we get AB->C

---

i always end up marking wrong answer in these questions where there is indirect dependency

---

So what is the ans then? Is it 'a' or 'c'? According to joshi_nitish is should be 'a' I suppose and that given in solution is 'c'

---

Given FD's:

B->D

D->B

AB->C

Decomposition: {R1(B,D) , R2(A,D,C)}

---

What fd's will hold on R2??

A -> something

D -> something

C -> something

AD -> something

AC -> something

DC -> something

ADC -> something

---

Now let's replace "something" by proper values that we get from fd's.

A -> A

D -> DB

C -> C

AD -> ADBC

AC -> AC

DC -> DBC

ADC -> ADCB

---

Now filter out fd's that include only those attributes that are present in our decomposed relation R2(A,D,C)

A -> A

D -> D

C -> C

AD -> ADC

AC -> AC

DC -> DC

ADC -> ADC

---

Excluding trivial fd's we get:

AD -> C

---

Now we have found fd's that hold on R2.

Can we deduce AB - > C from these fd's??

(NO!).

---

---

Likewise deduce fd's for R1.

Can we deduce AB - > C from these fd's that hold on R1??

(NO!).

---

---

---

@Higgs

what you finally wants to say, is {R1(B,D) , R2(A,D,C)} is dependency preserving or not?

---

he wants to say it is not dependency preserving

---

then he is wrong.

---

Please elaborate your veiwpoint.

---

@Higgs @Mk Utkarsh

tell me about dependency preserving decomposition

---

I'm already very confused but according to my understanding after decomposition we should somehow deduce the dependencies mentioned before decomposition

---

Ya I have the same understanding. So according to me also 'C' should be the ans. But joshi_nitish's explanation has created doubts in my understanding of the concept :P

---

see, 

let you decompose original relation R(FD's set as F) into R1(FD's set as F1) and R2(FD's set as F2), now,

the decomposition is dependency preserving, iff  $F1^+\cup F2^+=F^+$

---

now that after his explanation i think both have preserved dependencies after decomposition because i just checked another question of the same type

---

Both are FD preserving !

---

wait i am posting another question based on this concept

---

Please refer the fd's that I have found, aren't they equivalent to $F_{2}^{^{+}}$ ??

i.e.

R2(A,D,C)

A -> A

D -> D

C -> C

AD -> ADC

AC -> AC

DC -> DC

ADC -> ADC

---

Why isn't anyone replying??

A healthy discussion is going on and it can help in clearing doubt of the future readers as well.

---

If we decompose a relation R into relations R1 and R2, All dependencies of R either must be a part of R1 or R2 or must be derivable from combination of FD’s of R1 and R2.
by combination of R1 and R2 we can derive AB----->C

---

@Higgs see the definition of FD preservation. First, we take the union of F1 and F2 then keen closure.
See this pdf for detail. http://old.sztaki.hu/~fodroczi/dbs/dep-pres-own.pdf

---

Let me present my case from another viewpoint:

Suppose we have R(ABCD) and fd AB->C on this table.

Each time tuples are inserted in R, it is checked whether this fd is satisfied or not.

If yes, then tuple is inserted.

---

Now suppose we decompose this R(ABCD) into two relations: R1(BD), R2(ADC)

(Now also AB->C must hold.)

 After decomposition, how can we check AB->C holds or not??
                           --- We need to join these two relations and then check.

                                  (Can you devise any other method??)

This is the whole point of dependency preservation that after decomposition, whether you can verfiy that the fd's are satisfied or not without performing join on the decomposed tables.

 

---

i don't think we have to use JOIN specifically just need to do union of FD's. like from SQL viewpoint we can use AB and uniquely identify C right? it doesn't matter if tables are different because B-->D and D--->B

---

I think I need to revisit my concepts. Thanks everyone.

Future comments are welcome.

---

Update: If you are reading this discussion then please note that what others have pointed out is absolutely correct.

i.e. dependencies are preserved in both decompositions.

---

Actually, I was simply checking whether $F_{1}^+ \ U\  F_{2}^+ = F^{+}\ or\ not.$

But the correct approach is $(F_{1}^+ \ U\  F_{2}^+) ^{+}= F^{+}$

i.e. We take the union of F1 and F2  and then keen closure.

---

Thankyou @joshi_nitish, @Hemant, @Mk.

Answer 1

Answer must be 'A'.... As in option B dependency is preserved....

Comments

How is dependency preserved in second option can you please explain as  from ADC decomposition AB -) C can't be derived

---

In this we have to check whether the dependency is preserved or not for decomposition ADC..... So take the dependency AB - >C and check using polynomial time algorithm ( it is an algo used to find out whether dependency is preserved or not...)..... Then u will get your answer