Decomposition into Fourth Normal Form

Decomposition into Fourth Normal Form

The 4NF decomposition algorithm is quite similar to the BCNF decomposition algorithm. We find a 4NF violation, say , where  {A1, A2, . . . , An} is not a superkey. Note this MVD could be a true MVD, or it could be derived from the equivalent FD A1A2 . . .  An → B1B2 . . . Bm, since every FD is a MVD. Then we break the schema for the relation R that has the 4NF violation into two schemas:

1. The A's and the B's.

2. The A's and all attributes of R that are not among the A's or B's.

Example : Let us continue "Fourth Normal Form" example. We observed that

   

was a 4NF violation. The decomposition rule above tells us to replace the five-attribute schema by one schema that has only the three attributes in the above MVD and another schema that consists of the left side, name, plus the attributes that do not appear in the MVD. These attributes are title and year, so the following two schemas

Projecting Multivalued Dependencies

    {name, street, city}
    {name, title, year}

are the result of the decomposition. In each schema there are no nontrivial multivalued (or functional) dependencies, so they are in 4NF. Note that in the relation with schema {name, street, city}, the MVD:

   

is trivial since it includes all attributes. Similarly, in the relation with schema {name, title, year}, the MVD:
       
   

is trivial. Should one or both schemas of the decomposition not be in 4NF, we would have had to decompose the non-4NF schema(s).

As for the BCNF decomposition, each decomposition step leaves us with schemas that have strictly fewer attributes than we started with, so finally we get to schemas that need not be decomposed further; that is, they are in 4NF. In addition, the argument justifying the decomposition that we gave in "Recovering Information from a Decomposition" carries over to MVDs as well. When we decompose a relation because of a MVD , this dependency is sufficient to justify the claim that we can reconstruct the original relation from the relations of the decomposition.


Tags