Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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!

like image 982
raphnguyen Avatar asked Feb 27 '13 01:02

raphnguyen


People also ask

How do you decompose a relation?

Determine whether the decomposition of R into R1 ( A , B ) , R2 ( B , C ) and R3 ( B , D ) is lossless or lossy. relations. First, divide the given relation into two sub relations. Then, divide the sub relations according to the sub relations given in the question.

Which decomposition is in Boyce Codd Normal Form?

In relational database theory [1-3], a relation is said to be in Boyce-Codd Normal Form (BCNF), if all the determinants in the relation are keys. A set of relations is called a lossless decomposition of a given relation if the join of the relations gives back the original relation.


1 Answers

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.

like image 84
xlm Avatar answered Oct 05 '22 00:10

xlm