Decomposing a relation into BCNF

问题:

I'm having trouble establishing when a relation is in Boyce-Codd Normal Form and how to decompose it info BCNF if it is not. Given this example:

R(A, C, B, D, E) with functional dependencies: A -> B, C -> D

How do I go about decomposing it?

The steps I've taken are:

A+ = AB  
C+ = CD  
R1 = A+ = **AB**  
R2 = ACDE (since elements of C+ still exist, continue decomposing)  
R3 = C+ = **CD**  

R4 = ACE (no FD closures reside in this relation)

So now I know that ACE will compose the whole relation, but the answer for the decomposition is: AB, CD, ACE.

I suppose I'm struggling with how to properly decompose a relation into BCNF form and how to tell when you're done. Would really appreciate anyone who can walk me through their thought process when solving these problems. Thanks!

回答1:

Although the question is old, the other questions/answers don't seem to provide a very clear step-by-step general answer on determining and decomposing relations to BCNF.

1. Determine BCNF:
For relation R to be in BCNF, all the functional dependencies (FDs) that hold in R need to satisfy property that the determinants X are all superkeys of R. i.e. if X->Y holds in R, then X must be a superkey of R to be in BCNF.

In your case, it can be shown that the only candidate key (minimal superkey) is ACE. Thus both FDs: A->B and C->D are violating BCNF as both A and C are not superkeys or R.

2. Decompose R into BCNF form:
If R is not in BCNF, we decompose R into a set of relations S that are in BCNF.
This can be accomplished with a very simple algorithm:

Initialize S = {R}
While S has a relation R' that is not in BCNF do:   
   Pick a FD: X->Y that holds in R' and violates BCNF
   Add the relation XY to S
   Update R' = R'-Y
Return S

In your case the iterative steps are as follows:

S = {ABCDE}       // Intialization S = {R}
S = {ACDE, AB}    // Pick FD: A->B which violates BCNF
S = {ACE, AB, CD} // Pick FD: C->D which violates BCNF
// Return S as all relations are in BCNF

Thus R(A,B,C,D,E) is decomposed into a set of relations: R1(A,C,E), R2(A,B) and R3(C,D) that satisfies BCNF.

Note also that in this case, functional dependency is preserved but normalization to BCNF does not guarantee this.

I hope this helps.

回答2:

1NF -> 2NF -> 3NF -> BCNF

According to given FD set "ACE" forms the key. Clearly R(A,B,C,D,E) is not in 2NF. 2NF decomposition gives R1(A,B) , R2(C,D) and R3(A,C,E). this decomposition decomposed relations are in 3NF and also in BCNF.