BCNF decomposition algorithm explanation

问题:

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?

回答1:

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 -

• First we make sure the given set of FD's is a minimal cover
• Second we take each FD and make it its own sub-schema.
• Third we try to combine those sub-schemas

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)

• Singleton RHS: So we can write our FD's as { BG->C, BG->D, G->A, CD->A, CD->E, C->A, C->G, A->D}.
• No extraneous LHS attribute: We can remove 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}
• No redundant FD's: We note that there are a lot of redundant dependencies here. Removing them we have {BG->C, G->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)

R₁={B,G,C}
R₂={G,A}
R₃={C,E}
R₄={C,G}
R₅={A,D}

Third we see if any of the sub-schemas can be combined. We see that R₃ and R₄ can be combined as they have the same key. So now we have -

S₁ = {B,G,C}
S₂ = {A,G}
S₃ = {C,E,G}
S₄ = {A,D}

This is in 3NF. Now to check for BCNF we check if any of these relations (S₁,S₂,S₃,S₄) 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 (S₁) should also have the G attribute as shown above.

回答2:

Give input: A relation R0 with set (Minimal) of FD's S0.

Output : A decomposition of R into a collection of relations, all of which are in BCNF

Algo: R <- R0, and S <- S0 Repeat till R is in BCNF. If there is a FD X -> Y that violates BCNF condition. Compute {X}+ , and choose {X}+ as one relation as R1, and another R2 as {(R - X + ) U X} Map FD set S on R1 and R2 (determine FDs on R1 and R2). Recursively repeat the algo on R1 and R2.

Rule: 1.Should be attribute preserving. 2.Should be lossless 3.Should be FD preserving

Example: R(xyz) FD xy -> z; key : xy z-> y;

Solve: z-> y violet the BCNF condition.

So decompose relation R {z}+= yz; R1(yz) where key is z and R2(xz) key is x