database-normalizationfunctional-dependencies3nfdatabase-theory

# 3NF Normalisation Question, can I use a derived FD to determine a relation is not in 3NF?

I have the following question:

Consider relation R(A, B, C, D, E, F, H) with the following functional dependencies:

A --> D, AE --> H, DF --> BC, E --> C, H --> E

Consider three relational schema R1(A, D), R2(E, C), and R3(A, B, E, F, H). They form a decomposition for R.

(a) Do the original functional dependencies apply in R1, R2, and R3?

My attempt:

(a) The original functional dependencies apply in R1, R2, and R3 as long as the relation contains the attributes in the functional dependencies.

(b) No. Keys in R3 = {AEF, AFH}. From {AF}+ = {ABCDF} in R, in R3 {AF}+ = {ABF}. Hence we can form a functional dependency AF --> B, and the LHS of this functional dependency does not contain a key. The RHS also does not contain only key attributes.

The solution provided did not address (a) directly, and stated that the decomposition is in 3NF because the original FDs do not violate 3NF. Would like to know what I did wrongly here. Thank you!

Solution

• In the following I assume that the dependencies given are a cover of the dependencies of `R`.

(a) Do the original functional dependencies apply in R1, R2, and R3?

When one decomposes a relation, not necessarily the dependencies of a cover applies to the decomposed relations. This happens when a decomposed relation does non contains all the attributes of a dependency. For instance, in your example, `DF -> BC` does not hold in any of `R1`, `R2`, `R3`, since the attributes `DFBC` are not all present in a single relation (we know that functional dependencies are meaningful only inside a relation).

This not necessarily means that the decomposition suffers from a “loss of dependency”, since the definition is more complex: A decomposition of a relation schema R with attributes A and cover of dependencies F preserves the dependencies if and only if the union of the projections of the dependencies of F over the decomposed relation is a cover of F.

In Ullman, Principles of Database Systems, Computer Science Press, 1983, an algorithm is shown to compute the closure of the union of the projection of a set of dependency over a decomposition. In your particular case, by applying that algorithm we can find that the dependency `DF -> BC` is actually lost.

(b) Is this decomposition in 3NF?

Here you answer is correct, since the third decomposed relation is not in 3NF. As you have correctly pointed out, the candidate keys for this relation are `{AEF, AFH}`, while in the relation the dependency `AF -> B` hold, and this is a dependency that violates the 3NF since `AF` is not a superkey and `B` is not a prime attribute.