Fourth Normal Form (4NF)

1. We saw that BC-scheme was in BCNF, but still was not an ideal design as it suffered from repetition of information. We had the multivalued dependency cname street ccity, but no non-trivial functional dependencies.

2. We can use the given multivalued dependencies to improve the database design by decomposing it into fourth normal form.

3. A relation scheme is in 4NF with respect to a set of functional and multivalued dependencies if for all multivalued dependencies in of the form , where and , at least one of the following hold:
   • is a trivial multivalued dependency.
   • is a superkey for scheme .
4. A database design is in 4NF if each member of the set of relation schemes is in 4NF.

5. The definition of 4NF differs from the BCNF definition only in the use of multivalued dependencies.
   • Every 4NF scheme is also in BCNF.
   • To see why, note that if a scheme is not in BCNF, there is a non-trivial functional dependency holding on , where is not a superkey.

   • Since implies , by the replication rule, cannot be in 4NF.
6. We have an algorithm similar to the BCNF algorithm for decomposing a scheme into 4NF:

   

7. If we apply this algorithm to BC=scheme:
   • cname loan# is a nontrivial multivalued dependency and cname is not a superkey for the scheme.

   • We then replace BC-scheme by two schemes:

     

   • These two schemes are in 4NF.
8. We can show that our algorithm generates only lossless-join decompositions.
   • Let be a relation scheme and a set of functional and multivalued dependencies on .
   • Let and form a decomposition of .
   • This decomposition is lossless-join if and only if at least one of the following multivalued dependencies is in :

     

   • We saw similar criteria for functional dependencies.
   • This says that for every lossless-join decomposition of into two schemes and , one of the two above dependencies must hold.
   • You can see, by inspecting the algorithm, that this must be the case for every decomposition.
9. Dependency preservation is not as simple to determine as with functional dependencies.
   • Let be a relation scheme.
   • Let be a decomposition of .
   • Let be the set of functional and multivalued dependencies holding on .
   • The restriction of to is the set consisting of:
     • All functional dependencies in that include only attributes of .
     • All multivalued dependencies of the form where and is in .
   • A decomposition of scheme is dependency preserving with respect to a set of functional and multivalued dependencies if for every set of relations such that for all , satisfies , there exists a relation that satisfies and for which for all .
10. What does this formal statement say? It says that a decomposition is dependency preserving if for every set of relations on the decomposition scheme satisfying only the restrictions on there exists a relation on the entire scheme that the decomposed schemes can be derived from, and that also satisfies the functional and multivalued dependencies.

11. We'll do an example using our decomposition algorithm and check the result for dependency preservation.
    • Let .
    • Let D be

      

    • is not in 4NF, as we have and is not a superkey.
    • The algorithm causes us to decompose using this dependency into

      

    • is now in 4NF, but is not.
    • Applying the multivalued dependency (how did we get this?), our algorithm then decomposes into

      

    • is now in 4NF, but is not.
    • Why? As is in (why?) then the restriction of this dependency to gives us .
    • Applying this dependency in our algorithm finally decomposes into

      

    • The algorithm terminates, and our decomposition is and .
12. Let's analyze the result.

     
    Figure 6.4:   Projection of relation onto a 4NF decomposition of .
    

    • This decomposition is not dependency preserving as it fails to preserve .
    • Figure 6.4 (textbook 6.14) shows four relations that may result from projecting a relation onto the four schemes of our decomposition.
    • The restriction of to is and some trivial dependencies.
    • We can see that satisfies as there are no pairs with the same value.
    • Also, satisfies all functional and multivalued dependencies since no two tuples have the same value on any attribute.
    • We can say the same for and .
    • So our decomposed version satisfies all the dependencies in the restriction of .
    • However, there is no relation on that satisfies and decomposes into and .
    • Figure 6.5 (textbook 6.15) shows .
    • Relation does not satisfy .
    • Any relation containing and satisfying must include the tuple .
    • However, includes a tuple that is not in .
    • Thus our decomposition fails to detect a violation of .

     
    Figure 6.5:   A relation that does not satisfy .
    

13. We have seen that if we are given a set of functional and multivalued dependencies, it is best to find a database design that meets the three criteria:
    • 4NF.
    • Dependency Preservation.
    • Lossless-join.
14. If we only have functional dependencies, the first criteria is just BCNF.

15. We cannot always meet all three criteria. When this occurs, we compromise on 4NF, and accept BCNF, or even 3NF if necessary, to ensure dependency preservation.