Show that the relation schemas produced by Algorithm 16.6 are in 3NF."
Alogorithm 16.6
1. Find a minimal cover G for F (use Algorithm 16.2).
2. For each left-hand-side X of a functional dependency that appears in G, create a relation schema in D with attributes {X∪{A1 }∪{A2} ...∪{Ak} },where X→A1, X→A2, ..., X→Ak are the only dependencies in G with X as left-
hand-side (X is the key of this relation).
3. If none of the relation schemas in D contains a key of R, then create one more relation schema in D that contains attributes that form a key of R.
4. Eliminate redundant relations from the resulting set of relations in the relational database schema. A relation R is considered redundant if R is a projection of another relation S in the schema; alternately, R is subsumed by S.
Step 3 of Algorithm 16.6 involves identifying a key K of R. Algorithm 16.2(a) can be used to identify a key K of R based on the set of given functional dependencies F. Notice that the set of functional dependencies used to determine a key in Algorithm 16.2(a) could be either F or G, since they are equivalent.
Algorithm 16.2. Finding a Minimal Cover F for a Set of Functional Dependencies E
Input: A set of functional dependencies E.
1. Set F := E.
2. Replace each functional dependency X→{A1, A2, ..., An} in F by the n functional dependencies X→A1, X→A2, ..., X→An
.
3. For each functional dependency X→A in F for each attribute B that is an element of X if { {F- {X→A} } ∪{ (X- {B} ) →A} } is equivalent to F then replace X→A with (X- {B} ) →A in F.
4. For each remaining functional dependency X→A in F if {F- {X→A} } is equivalent to F, then remove X→A from F.
We illustrate the above algorithm with the following: Let the given set of FDs be E : {B→A, D→A, AB→D}. We have to find the minimal cover of E.
¦All above dependencies are in canonical form (that is, they have only one attribute on the right-hand side), so we have completed step 1 of Algorithm 16.2 and can proceed to step 2. In step 2 we need to determine if AB→D has any redundant attribute on the left-hand side; that is, can it be replaced by B→D or A→D?
Elmasri, Ramez; Navathe, Shamkant (2011-01-11). Fundamentals of Database Systems (6th Edition) (Page 561). Addison-Wesley. Kindle Edition.