I looked in Decomposing a relation into BCNF answers and tried it on my homework, but i don't get the correct answers, so i ask for help in BCNF decomposition
Consider R=(ABCDEG)
& F={BG->CD, G->A, CD->AE, C->AG, A->D}
.
I start pick A->D
.
Now i got S=(AD), R'=(ABCEG).
I pick G->A
.
Now i got S=(AD,AG) R'=(BCEG)
.
I pick C->G
.
Now i think i need to get S=(AD,AG,CG)
and R'=(BCE)
, But the answer in the end is (AD,AG,CGE,BC)
.what went wrong? or perhaps, a better algorithm?
To convert a relation R
and a set of functional dependencies(FD's
) into 3NF
you can use Bernstein's Synthesis. To apply Bernstein's Synthesis -
FD's
is a minimal coverFD
and make it its own sub-schema.For example in your case:
R = {A,B,C,D,E,G}
FD's = {BG->CD,G->A,CD->AE,C->AG,A->D}
First we check whether the FD's
is a minimal cover (singleton right-hand side , no extraneous left-hand side attribute, no redundant FD)
D
from LHS of CD->A
and CD->E
since D
is an extraneous attribute here (As we can get D
from C
since C->A and A->D). So we now have {BG->C, BG->D, G->A, C->A, C->E, C->G, A->D}Second we make each FD
its own sub-schema. So now we have - (the keys for each relation are in bold)
R1={B,G,C}
R2={G,A}
R3={C,E}
R4={C,G}
R5={A,D}
Third we see if any of the sub-schemas can be combined. We see that R3 and R4 can be combined as they have the same key. So now we have -
S1 = {B,G,C}
S2 = {A,G}
S3 = {C,E,G}
S4 = {A,D}
This is in 3NF. Now to check for BCNF we check if any of these relations (S1,S2,S3,S4) violate the conditions of BCNF (i.e. for every functional dependency X->Y
the left hand side (X
) has to be a superkey) . In this case none of these violate BCNF and hence it is also decomposed to BCNF.
Note My final answer above is (AD,AG,CGE,BCG)
. The solution you expect is (AD,AG,CGE,BC)
but that's wrong. The last relation here (S1) should also have the G
attribute as shown above.