32

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!

as2d3
  • 802
  • 2
  • 10
  • 27
raphnguyen
  • 3,565
  • 18
  • 56
  • 74
  • 1
    Did you read all those questions about BCNF in the sidebar? – Mike Sherrill 'Cat Recall' Feb 27 '13 at 01:51
  • I read through one example which seems to help with the decomposition. I think I understand that part okay, but I'm still a bit confused as to when you are completely done decomposing. Is it when your relations no longer include all of the attributes within the closure of one of your functional dependencies? – raphnguyen Feb 27 '13 at 02:16
  • A relation is in BCNF when every "arrow" in every functional dependency is an "arrow" out of a candidate key. – Mike Sherrill 'Cat Recall' Feb 27 '13 at 02:22
  • I updated my original post to show how I am going about the decomposition. In this problem, are the resulting relations the candidate keys (AB, CD, ACE)? I'm trying to visualize your last statement, but I'm having a hard time understanding what you mean. – raphnguyen Feb 27 '13 at 02:29
  • In {AB}, A is a candidate key. The only FD is A->B. Every arrow in every FD in {AB} is an arrow out of the candidate key A. So {AB} is, at the very least, in BCNF. – Mike Sherrill 'Cat Recall' Feb 27 '13 at 03:28
  • And likewise, in {CD} C is a candidate key. The only FD is C->D where every arrow in every FD in {CD} is an arrow out of the candidate key C. Since there are no FDs in {ACE} is ACE its own candidate key since it is in BCNF? – raphnguyen Feb 27 '13 at 03:43
  • {ACE} is in *at least* BCNF, because the only FD is a trivial FD. (ACE->ACE) See [Wikipedia](http://en.wikipedia.org/wiki/Boyce%E2%80%93Codd_normal_form) – Mike Sherrill 'Cat Recall' Feb 27 '13 at 04:30
  • The comment by MikeSherrill'CatRecall' should say, every functional dependency in a canonical closure. – philipxy Mar 08 '20 at 19:52

2 Answers2

124

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.

Sebastian Nielsen
  • 3,835
  • 5
  • 27
  • 43
xlm
  • 6,854
  • 14
  • 53
  • 55
  • 1
    Remember that you need to store the functional dependencies along the `R` because you need to analyse a tuple `(R', Σ')` in every iteration. So `S` should general look like this: `S = [(R_1, Σ_1); (R_2, Σ_2); ...; (R_n, Σ_n)}`. I also recommend to update the `R'` this way `R' = X(R' - Y)`. – mhellmeier Feb 22 '18 at 22:20
  • Perhaps i misunderstand your algorithm but it seems to me that it has an infinity loop. Lets says we have relation ABCDEFGHJ. Then we have a fd saying AC =>H. Per your algorithm we change S to contain S={ABCDEFGJ, ACH}. But right now we have just replaced one R out of BCNF with another so per your algorithm we make another iteration and S becomes S={ABCDEFGJ, AC, ACH} Once again we have replaced one R out of BCNF with another so we make another iteration and S becomes S={ABCDEFGJ, AC, AC, ACH}. This we can continue doing until the oblivion. – Nulle Jun 09 '18 at 08:47
  • If the only FD is AC->H, then then ABCDEFGHJ isn't in BCNF. Thus you reduce it to ACH, ABCDEFGJ. ACH is in BCNF (all determinants are superkey) and so is ABCDEFGJ (no FDs) so you're done/no infinite loop. You can't pick AC since all relations are in BCNF. If you're still not sure please ask a new SO question. – xlm Jun 12 '18 at 00:59
  • @xlm Here we do need to check for all the FD's in F+ where F is the set of dependencies holding on the original relation R right? – rohit_r Feb 27 '20 at 07:10
0

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.

User
  • 117
  • 1
  • 3
  • 1
    We do not normalize to a NF by going through lower NFs; that can prevent good decompositions in the final NF from being found. – philipxy Mar 08 '20 at 19:57