Use your "back" button to get out
Procedure for decomposing relations to 3NF
In class we used the following procedure (which is more formally presented in
the book):
1. Put all attributes into one relation.Example: R(A,B,C,D,E,F,G)
2. Find the key of the relation. When using A,B,C you have to be given some
functional dependencies (FDs) to work with. If you have some sensible
attribute names, you may infer some FDs or you may be given some.
Suppose in our example, AB -> C, B -> DE, E -> FG
What is the key or R? It's not going to be B or A because we have no way to
produce FD that will by X -> AB. Likely, you will use the largest left-hand-
side given and try to show {X}+
Here, you start with AB and try to show AB -> R
AB -> C (given)
AB -> ABC (reflexive rule)
AB -> ABCDE (transitive because AB -> B and B -> DE)
AB -> ABCDEFG (transitive because AB -> E, E -> FG).
If the AB does not produce AB -> R, then augment AB with the most likely next
candidate and try to show the new, larger lhs is a key.
3. Having found the key, decompose the relation
R (A,B,C,D,E,F,G)
remove partial dependencies. You have AB -> C and B -> DE which decomposes
into:
R1 (B, D, E) (B is key - sorry I can't underline on the web)
R2 (A, B, C, F, G) (AB is key)
remove transitive dependencies
Since E -> FG, and we have R1 (B, D, E), we can move the FG to R1 from R2 to
give:
R1 (B, D, E, F, G) (B is key)
R2 (A, B, C). (AB is key, AB now in 3NF)
Now, R2 is in 3NF, but R1 is not because B -> E and E -> FG, so you decompose
R1:
R1 (B, D, E) (B is key)
R2 (A, B, C) (AB is key)
R3 (E, F, G) (E is key)
All are now in 3NF and will produce a lossless join. We will show an
algorithm in the next chapter that will show that this decomposition is
lossless.
Copyright .. Richard Earp .. November 1996
Use the "back" button on your browser to get out