1.Give an algorithm for testing whether a relation scheme is in BCNF. The algorithm should be polynomial in the size of the set of given FDs. (The ‘size’ is the sum over all FDs of the number of attributes that appear in the FD.) Is there a polynomial algorithm for testing whether a relation scheme is in 3NF?

2.Prove these statements:

1. If a relation scheme is in BCNF and at least one of its keys consists of a single attribute, it is also in 4NF.

2. If a relation scheme is in 3NF and each key has a single attribute, it is also in 5NF.

3.Prove that, if R has only one key, it is in BCNF if and only if it is in 3NF.

4.Prove that the 3NF synthesis algorithm produces a lossless-join de-composition of the relation containing all the original attributes.

5.Prove that the optimization of the algorithm for lossless-join, dependency-preserving decomposition into 3NF relations (Section 19.6.2) is correct.

6.Consider a scheme R with FDs F that is decomposed into schemes with attributes X and Y. Show that this is dependency-preserving if F ⊆ (FX ∪FY )+.

7.Consider a relation R with attributes ABCDE. Let the following FDs be given: A → BC, BC → E, and E → DA. Similarly, let S be a relation with attributes ABCDE and let the following FDs be given: A → BC, B → E, and E → DA. (Only the second dependency di?ers from those that hold over R.) You do not know whether or which other (join) dependencies hold. 

1. Is R in BCNF? 

2. Is R in 4NF? 

3. Is R in 5NF? 

4. Is S in BCNF? 

5. Is S in 4NF? 

6. Is S in 5NF?

8.Prove that Armstrong’s Axioms are sound and complete for FD in-ference. That is, show that repeated application of these axioms on a set F of FDs produces exactly the dependencies in F+.

9.Let us say that an FD X → Y is simple if Y is a single attribute. 

1. Replace the FD AB → CD by the smallest equivalent collection of simple FDs. 

2. Prove that every FD X → Y in a set of FDs F can be replaced by a set of simple FDs such that F+ is equal to the closure of the new set of FDs.

10.Prove that the algorithm shown in Figure 19.4 correctly computes the attribute closure of the input attribute set X.