Database(12) -- Fourth Normal Form

Fourth Normal Form

• A relation R is in fourth normal form (4NF) if whenever

A1A2…An –>-> B1B2…Bm

is a nontrivial MVD, {A1,A2,…,An} is a superkey.

Decomposition into Fourth Normal Form

Algorithm 3.33:

INPUT: A relation R0 with a set of functional and multivalued dependencies S0.

OUTPUT: A decomposition of R0 into relations all of which are in 4NF. The decomposition has the lossless-join property.

METHOD: Do the following steps, with R = R0 and S = S0:

1. Find a 4NF violation in R, say A1A2…An –>-> B1B2…Bm, where {A1,A2,…,An} is not a superkey. Note this MVD could be a true MVD is S, or it could be derived from the corresponding FD A1A2…An -> B1B2…Bm in S, since every FD is an MVD. If there is none, return; R by itself is a suitable decomposition.

2. If there is such a 4NF violation, break the schema for the relation R that has the 4NF violation into two schemas:

a) R1, whose schema is A’s and the B’s.

b) R2, whose schema is the A’s and all attributes of R that are not among the A’s or B’s.

1. Find the FD’s and MVD’s that hold in R1 and R2. Recursively decompose R1 and R2 with respect to their projected dependencies.

Relationships Among Normal Forms

4NF ⊆ BCNF ⊆ 3NF

An Algorithm for Discovering MVD’s

X –>-> Y tells us that if we find two rows of the tableau that agree in X, then we can form two new tuples by swapping all their components in the attributes of Y; the resulting two tuples must also be in the relation, and therefore in the tableau.

• Whenever there is an MVD X –>-> Y, and any FD whose right side is a (not necessarily proper) subset of Y, say Z, then X -> Z.

For example, for relation R(A,B,C,D) with MVD A –>-> BC and FD D -> C. We claim that A -> C.