World's most popular travel blog for travel bloggers.

[Solved]: BCNF Decomposition: Confusion regarding given answer

, , No Comments
Problem Detail: 

I encountered the following question:

Given a relation R(A, B, C, D) with the following functional dependencies:
A -> B, C -> D, B -> C.

The BCNF Decomposition of R is:

A) {(A,B), (C,D), (B,C)}
B) {(A,B), (C,D), (A,C)}
C) {(B,C), (A,D), (A,B)}
D) All of the above

According to my understanding the solution should be D) ALL of the above.
This is because for each schema, the condition for BCNF holds as given by this link: http://www.cs.sfu.ca/CourseCentral/354/jpei/slides/UsingBCNF-3NF.pdf (Page 18)

The other two do not preserve some dependencies but in BCNF decomposition it may happen that the dependencies are not preserved.

However, the answer is given as (A). Please can someone explain? Thanks.

Asked By : Abhishek Bansal

Answered By : akashchandrakar

For the relation R(A, B, C, D) with the following functional dependencies:

1.A -> B 2.C -> D 3.B -> C 

candidate key = A

The correct way to decompose a relation such that it satisfies BCNF property is following.

The FD 2 and 3 are violating the BCNF property(LHS should be key) i.e to convert the relation into BCNF it is needed to be decomposed.

To decompose this find the FD which violates the BCNF property in our case FD 2 and 3 violates.

Seprate out this FD into a different relation i.e our new relation is

R1 = (A,B) with FD A-> B R2 = (B,C,D) with FD B->C and C->D 

Again for the R2 the key is B and FD C->D violates the BCNF property we further split R2 into R12 and R22

R12  = (B,C) with FD B->C R22  = (C,D) with FD C->D 

Now the final obtained relation after decomposition is

R1 = (A,B) with FD A-> B R12  = (B,C) with FD B->C R22  = (C,D) with FD C->D 

The above relations are the only decomposition of R that satisfies BCNF property.

For more insights refer this http://www.cs.toronto.edu/~faye/343/f07/lectures/wk12/moreBCNF.pdf

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33314

0 comments:

Post a Comment

Let us know your responses and feedback