# Write programs that implement Algorithms 15.4 and 15.5. Algorithm 15.4 Relational Synthesis into 3NF with Dependency Preservation

## Question:

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_{1}, A_{2}, … , A_{n}} in F by the n functional dependencies X →A_{1}, X →A_{2}, … , 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_{1}} ∪ {A_{2}} … ∪ {A_{k}} }, where X → A_{1}, X → A_{2}, … , 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.^{7}

**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);

} ;

## Step by Step Answer:

**Related Book For**

## Fundamentals Of Database Systems

**ISBN:** 9780133970777

7th Edition

**Authors:** Ramez Elmasri, Shamkant Navathe