Join Dependencies and Fifth Normal Form

Join Dependencies and Fifth Normal Form

In our discussion so far, we have pointed out the problematic functional dependencies and showed how they were eliminated by a process of repeated binary decomposition to remove them during the process of normalization to achieve 1NF, 2NF, 3NF and BCNF. These binary decompositions must obey the NJB property from Section 16.2.4 that we referenced while discussing the decomposition to achieve BCNF. Achieving 4NF typically involves eliminating MVDs by repeated binary decompositions as well. However, in some cases there may be no nonadditive join decomposition of R into two relation schemas, but there may be a nonadditive join decomposition into more than two relation schemas. Moreover, there may be no functional dependency in R that violates any normal form up to BCNF, and there may be no nontrivial MVD present in R either that violates 4NF. We then resort to another dependency called the join dependency and, if it is present, carry out a multiway decomposition into fifth normal form (5NF). It is important to note that such a dependency is a very peculiar semantic constraint that is very difficult to detect in practice; therefore, normalization into 5NF is very rarely done in practice.

Definition. A join dependency (JD), denoted by JD(R₁, R₂, ..., R_n), specified on relation schema R, specifies a constraint on the states r of R. The constraint states that every legal state r of R should have a nonadditive join decomposition into R₁, R₂, ..., R_n. Hence, for every such r we have

∗ (π_R1(r), π_R2(r), ..., π_Rn(r)) = r

Notice that an MVD is a special case of a JD where n = 2. That is, a JD denoted as JD(R₁, R₂) implies an MVD (R₁ ∩ R₂) →→ (R₁ – R₂) (or, by symmetry, (R₁ ∩ R₂) →→(R₂ – R₁)). A join dependency JD(R₁, R₂, ..., R_n), specified on relation schema R,

is a trivial JD if one of the relation schemas R_i in JD(R₁, R₂, ..., R_n) is equal to R. Such a dependency is called trivial because it has the nonadditive join property for any relation state r of R and thus does not specify any constraint on R. We can now define fifth normal form, which is also called project-join normal form.

Definition. A relation schema R is in fifth normal form (5NF) (or project-join normal form (PJNF)) with respect to a set F of functional, multivalued, and join dependencies if, for every nontrivial join dependency JD(R₁, R₂, ..., R_n) in F⁺ (that is, implied by F),¹⁸ every R_i is a superkey of R.

For an example of a JD, consider once again the SUPPLY all-key relation in Figure 15.15(c). Suppose that the following additional constraint always holds: Whenever a supplier s supplies part p, and a project j uses part p, and the supplier s supplies at least one part to project j, then supplier s will also be supplying part p to project j. This constraint can be restated in other ways and specifies a join dependency JD(R₁, R₂, R₃) among the three projections R₁(Sname, Part_name), R₂(Sname, Proj_name), and R₃(Part_name, Proj_name) of SUPPLY. If this constraint holds, the tuples below the dashed line in Figure 15.15(c) must exist in any legal state of the SUPPLY rela-tion that also contains the tuples above the dashed line. Figure 15.15(d) shows how the SUPPLY relation with the join dependency is decomposed into three relations R₁, R₂, and R₃ that are each in 5NF. Notice that applying a natural join to any two of these relations produces spurious tuples, but applying a natural join to all three together does not. The reader should verify this on the sample relation in Figure 15.15(c) and its projections in Figure 15.15(d). This is because only the JD exists, but no MVDs are specified. Notice, too, that the JD(R₁, R₂, R₃) is specified on all legal relation states, not just on the one shown in Figure 15.15(c).

Discovering JDs in practical databases with hundreds of attributes is next to impos-sible. It can be done only with a great degree of intuition about the data on the part of the designer. Therefore, the current practice of database design pays scant atten-tion to them.