9

I am trying to figure out the correct steps in performing a BCNF decomposition. I found this example, but I do not understand how to perform the correct steps.

Schema = (A,B,C,D,E,F,G,H) FD's + {A -> CGH, AD->C, DE->F, G->G}

Could someone show the correct steps?

Mike
  • 99
  • 1
  • 1
  • 3
  • Did you find this example on your homework assignment? – Marcelo Cantos Dec 06 '10 at 16:08
  • No it was in the textbook, but not answered of course. I'm trying to find more examples, to help me on the final. – Mike Dec 06 '10 at 16:28
  • Looks like homework. Try reviewing the following [slide show](http://www.comp.nus.edu.sg/~lingtw/rm.pdf). If you follow it, you should be able to complete the exercise. – NealB Dec 06 '10 at 16:40
  • 3
    First it is not homework. Secondly, I've looked up numerous slide shows but they don't show how to actually do a BCNF decomposition. I know it is in BCNF for. And if the slide show does show it, it is an easy example so it does not help me – Mike Dec 06 '10 at 16:50
  • I'll just go to my instructor's office and get help on the subject – Mike Dec 06 '10 at 16:50

1 Answers1

11

Determine a minimal cover using your FD's:

{A -> C, A -> G, A -> H, 
 B -> nothing, 
 C -> nothing,
 D -> nothing,
 E -> nothing,
 F -> nothing
 G -> nothing
 H -> nothing
 DE -> F}

Note AD -> C drops out because A alone determines C which implies D is redundant in the FD (see Armstrong's Axioms - Augmentation).

3NF and BCNF definitions relate to dependencies about compund keys. The only compound key you have here is DE. Neither D or E participate in any other non-null FD's so eliminating transitive dependencies and ensuring that dependent attributes rely on the 'key, the whole key, and nothing but the key' is not an issue here.

Break into relations so that the FD left hand side is the key and the right hand sides are the non-key dependent attributes of that key:

[Key(A), C, G, H]
[Key(D, E), F]

Now eliminate these attributes from the cover, whatever is left are standalone relations.

[Key(B)]

This should be in 3NF/BCNF

NealB
  • 16,670
  • 2
  • 39
  • 60
  • For AD -> C, I don't understand how the Augmentation Rule applies. However, I do believe it is removed because it is a partial key dependency, which is not allowed in 2NF. – Alex W Dec 04 '12 at 04:53
  • 1
    @Alex W Good point. If `A -> C` then `AD -> CD` is true by augmentation. Through decomposition we can derive `AD -> C`. But the choice of preserving `A -> C` or `AD -> C` is determined by rules for constructing a minimal cover from a given set of FD's. Removal of `D` from the LHS of the FD's does not prevent `C` from being determined in F+, consequently, "redundancy" is the real basis for dropping it. – NealB Dec 04 '12 at 20:40
  • I am getting decomposed relations as R1(DEF), R2(ACGH) and R3(ABDE). I don't understand how B can be the candidate key. I got ABDE as the key for the above relation. – Josh Aug 10 '14 at 02:54