BCNF decomposition step without functional dependencies

database-designnormalizationrelational-theory

I am performing the BCNF decomposition for the relation R = (A, B, C, D, E), that has the set of functional dependencies AB -> C, CD -> A, C -> E, and C -> B.

After checking that the first dependency AB -> C violates the BCNF (by calculating the closure of AB), I split the original relation into two – R1 = (A, B, C) and R2 = (A, B, D, E).

At this point, the functional dependencies associated with R1 are AB -> C and C -> B, so I can see that R1 is in the BCNF. When it comes to R2, I cannot use any of the functional dependencies to verify if there are any violations to the BCNF, as all of them have the C attribute. How can I proceed if I do not have any functional dependencies to check?

Best Answer

When you decompose R(T) to find the BCNF, if the dependency X -> Y violates the BCNF, the decomposition that the classical algorithm requires is not R1(X) and R2(T-X), but R1(X+) and R2(T-(X+ - X)).

So the first decomposition, considering AB → C, should be:

R1(A, B, C, E) (since AB+ = ABCE)
R2(A, B, D) (= {ABCDE - (ABCE - AB))

In R1 the remaining dependencies are AB → C, C → E, C → B, while in R2 there are no (non-trivial) dependencies.

R1 is not in BCNF, since the two dependencies C → E, C → B violates that form (the only candidate keys are AB and AC). So it can be decomposed in R3(B, C, E), with dependencies C → E, C → B, and R4(A, C) (again without non-trivial dependencies).

So the final decomposition is:

R2 < (A B D) ,
{ } >

R3 < (B C E) ,
{ C → E
C → B } >

R4 < (A C) ,
{ } >

Note that the dependencies:

{ C D → A
A B → C }

are not preserved in this normalization.

Finally, note that if, during this process, you get a relation schema without (non-trivial) dependencies, this schema is already normalized, since the only candidate key is formed by all the attributes and there is no dependency that violates the BCNF.

Related Question