Write programs that implement Algorithms 15.4 and 15.5.

Algorithm 15.4 Relational Synthesis into 3NF with Dependency Preservation and Nonadditive Join Property
Input: A universal relation R and a set of functional dependencies F on the attributes of R.

1. Find a minimal cover G for F (use Algorithm 15.2).

Algorithm 15.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 → {A₁, A₂, … , A_n} in F by the n functional dependencies X →A₁, X →A₂, … , X → A_n. (*This places the FDs in a canonical form for subsequent testing*)

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.
(*This constitutes removal of an extraneous attribute B contained in the left-hand side X of a functional dependency X → A when possible*)

4. For each remaining functional dependency X → A in F if {F − {X → A} } is equivalent to F, then remove X → A from F. (*This constitutes removal of a redundant functional dependency X → A from F when possible*)

2. For each left-hand-side X of a functional dependency that appears in G, create a relation schema in D with attributes {X ∪ {A₁} ∪ {A₂} … ∪ {A_k} }, where X → A₁, X → A₂, … , X → A_k 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. (Algorithm 15.2(a) may be used to find a key.)

Algorithm 15.2(a). Finding a Key K for R Given a Set F of Functional Dependencies
Input: A relation R and a set of functional dependencies F on the attributes of R.

1. Set K := R.
2. For each attribute A in K {compute (K − A)⁺ with respect to F; if (K − A)⁺ contains all the attributes in R, then set K := K − {A} };

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.⁷

Algorithms 15.5

Relational Decomposition into BCNF with Nonadditive  Join Property
Input: A universal relation R and a set of functional dependencies F on the attributes of R.

1. Set D := {R} ;
2. While there is a relation schema Q in D that is not in BCNF do

{
choose a relation schema Q in D that is not in BCNF; find a functional dependency X → Y in Q that violates BCNF; replace Q in D by two relation schemas (Q − Y) and (X ∪ Y);
} ;