Relational Database Design Algorithms and Further Dependencies

Chapter 16

Relational Database Design Algorithms and Further Dependencies

_Chapter 15 presented a top-down relational design technique and related concepts used extensively in commercial database design projects today. The procedure involves designing an ER or EER conceptual schema, then mapping it to the relational model by a procedure such as the one described in Chapter 9. Primary keys are assigned to each relation based on known functional dependencies. In the subsequent process, which may be called relational design by analysis, initially designed relations from the above procedure—or those inherited from previous files, forms, and other sources—are analyzed to detect undesirable functional dependencies. These dependencies are removed by the successive normalization procedure that we described in Section 15.3 along with definitions of related normal forms, which are successively better states of design of individual relations. In Section 15.3 we assumed that primary keys were assigned to individual relations; in Section 15.4 a more general treatment of normalization was presented where all candidate keys are considered for each relation, and Section 15.5 discussed a further normal form called BCNF. Then in Sections 15.6 and 15.7 we discussed two more types of dependencies—multivalued dependencies and join dependencies—that can also cause redundancies and showed how they can be eliminated with further normalization.

In this chapter we use the theory of normal forms and functional, multivalued, and join dependencies developed in the last chapter and build upon it while maintaining three different thrusts. First, we discuss the concept of inferring new functional dependencies from a given set and discuss notions including cover, minimal cover, and equivalence. Conceptually, we need to capture the semantics of attibutes within a relation completely and succinctly, and the minimal cover allows us to do it. Second, we discuss the desirable properties of nonadditive (lossless) joins and preservation of functional dependencies. A general algorithm to test for nonadditivity of joins among a set of relations is presented. Third, we present an approach to relational design by synthesis of functional dependencies. This is a bottom-up approach to design that presupposes that the known functional dependencies among sets of attributes in the Universe of Discourse (UoD) have been given as input. We present algorithms to achieve the desirable normal forms, namely 3NF and BCNF, and achieve one or both of the desirable properties of nonadditivity of joins and functional dependency preservation. Although the synthesis approach is theoretically appealing as a formal approach, it has not been used in practice for large database design projects because of the difficulty of providing all possible functional dependencies up front before the design can be attempted. Alternately, with the approach presented in Chapter 15, successive decompositions and ongoing refinements to design become more manageable and may evolve over time. The final goal of this chapter is to discuss further the multivalued dependency (MVD) concept we introduced in Chapter 15 and briefly point out other types of dependencies that have been identified.

In Section 16.1 we discuss the rules of inference for functional dependencies and use them to define the concepts of a cover, equivalence, and minimal cover among functional dependencies. In Section 16.2, first we describe the two desirable properties of decompositions, namely, the dependency preservation property and the nonadditive (or lossless) join property, which are both used by the design algorithms to achieve desirable decompositions. It is important to note that it is insufficient to test the relation schemas independently of one another for compliance with higher normal forms like 2NF, 3NF, and BCNF. The resulting relations must collectively satisfy these two additional properties to qualify as a good design. Section 16.3 is devoted to the development of relational design algorithms that start off with one giant relation schema called the universal relation, which is a hypothetical relation containing all the attributes. This relation is decomposed (or in other words, the given functional dependencies are synthesized) into relations that satisfy a certain normal form like 3NF or BCNF and also meet one or both of the desirable properties.

In Section 16.5 we discuss the multivalued dependency (MVD) concept further by applying the notions of inference, and equivalence to MVDs. Finally, in Section 16.6 we complete the discussion on dependencies among data by introducing inclusion dependencies and template dependencies. Inclusion dependencies can represent referential integrity constraints and class/subclass constraints across relations. Template dependencies are a way of representing any generalized constraint on attributes. We also describe some situations where a procedure or function is needed to state and verify a functional dependency among attributes. Then we briefly discuss domain-key normal form (DKNF), which is considered the most general normal form. Section 16.7 summarizes this chapter.

It is possible to skip some or all of Sections 16.3, 16.4, and 16.5 in an introductory database course.