Princeton University Computer Science Dept.

Computer Science 425 Database Systems Andrea LaPaugh

Spring 2001

To prove:

Let mcF denote the minimal cover of a set of functional dependencies F within a relation R. Suppose we have a set of relations that have been obtained by the decomposition of R using mcF such that all the relations are now in 3NF. If a functional dependency X->A in mcF has been split so that the decomposition is not a dependency preserving decomposition, then the relation with schema XA can be added, and the resulting set of relations will be in 3NF.

Proof: We need to show that relation with schema XA is in 3NF with respect to the projection of mcF on XA.

Now X must be a candidate key for XA (otherwise X->A is not minimal), so X->A does not violate 3NF.
First consider the possibility of another relation Y->A.

• If Y contains A, then Y-> A is trivial and satisfies 3NF
• If Y does not contain A, then the attributes of Y must be a subset of the attributes of X, which means X->A is not minimal. This contradicts the fact that we are using mcF so cannot be true.

Note that in class, I gave the following argument for Y->B when Y does not contain A or B:

• Y is a subset of X. By augmentation and reflexivity, X-B -> B. But then (X-B -> X -> A) shows that X->A is not minimal. This contradicts the fact that we are using mcF and so cannot be true.