Chapter 15 Functional Dependencies and Normalization CS 6360 Database Design Chris Irwin Davis Ph D Email cid021000 utdallas edu Phone 972 883 3574 O ce ECSS 4 705 Chapter 15 Outline 1 Informal Design Guidelines for Relation Schemas 2 Functional Dependencies FD 3 Normal Forms Normal Forms Based on Primary Keys General Definitions of Second and Third Normal Forms Boyce Codd Normal Form Multivalued Dependency and Fourth Normal Form Join Dependencies and Fifth Normal Form 2 Introduction In chapters 3 6 various aspects of the relational model were presented and the languages associated with it Each relational database schema consists of a number of relation schemas and each relation schema consists of a number of attributes So far we have assumed that attributes are grouped to form a relation schema by using the common sense of the database designer or by mapping a database schema design from a conceptual data model such as the ER or Enhanced ER EER data model 3 Introduction These models make the designer identify entity types and relationship types and their respective attributes which leads to a natural and logical grouping of the attributes into relations when the mapping procedures discussed in Chapter 9 are followed However we still need a formal way of analyzing why one grouping of attributes into a relation schema may be better than another While discussing database design in Chapters 7 9 we did not develop any measure of appropriateness or goodness to measure the quality of the design other than the intuition of the designer 4 Introduction Here we discuss some of the theory that has been developed with the goal of Evaluating relational schemas for design quality That is to measure formally why one set of groupings of attributes into relation schemas is better than another 5 Introduction There are two levels at which we can discuss goodness of relation schemas Logical or conceptual level Implementation or physical storage level Approaches to database design Bottom up Top down 6 Logical or Conceptual Level How users interpret the relation schemas and the meaning of their attributes Having good relation schemas at this level enables users to understand clearly the meaning of the data in the relations and hence to formulate their queries correctly 7 Implementation or Physical Storage Level How the tuples in a base relation are stored and updated This level applies only to schemas of base relations which will be physically stored as files whereas at the logical level we are interested in schemas of both base relations and views virtual relations The relational database design theory developed in this chapter applies mainly to base relations although some criteria of appropriateness also apply to views 8 Informal Design Guidelines for Relation Schemas Informal Design Guidelines for Relation Schemas Measures of quality 1 Making sure attribute semantics are clear 2 Reducing redundant information in tuples 3 Reducing NULL values in tuples 4 Disallowing possibility of generating spurious tuples 10 A Simplified COMPANY Schema 11 Imparting Clear Semantics to Attributes in Relations Semantics of a relation Meaning resulting from interpretation of attribute values in a tuple In general the easier it is to explain semantics of relation the better the relation schema will be Indicates better schema design 12 Guideline 1 Design relation schema so that it is easy to explain its meaning Do not combine attributes from multiple entity types and relationship types into a single relation Example of violating Guideline 1 Figure 15 3 13 Guideline 1 cont d 14 Redundant Information in Tuples and Update Anomalies Grouping attributes into relation schemas Significant effect on storage space Storing natural joins of base relations leads to update anomalies Types of update anomalies Insertion Deletion Modification 15 Insertion Anomalies two types To insert a new employee tuple into EMP DEPT we must include either the attribute values for the department that the employee works for or NULLs if the employee does not work for a department as yet For example to insert a new tuple for an employee who works in department number 5 we must enter all the attribute values of department 5 correctly so that they are consistent with the corresponding values for department 5 in other tuples in EMP DEPT In the design of Figure 15 1 we do not have to worry about this consistency problem because we enter only the department number in the employee tuple all other attribute values of department 5 are recorded only once in the database as a single tuple in the DEPARTMENT relation 16 Insertion Anomalies two types It is difficult to insert a new department that has no employees as yet in the EMP DEPT relation The only way to do this is to place NULL values in the attributes for employee This violates the entity integrity for EMP DEPT because Ssn is its primary key Moreover when the first employee is assigned to that department we do not need this tuple with NULL values any more This problem does not occur in the design of Figure 15 1 because a department is entered in the DEPARTMENT relation whether or not any employees work for it and whenever an employee is assigned to that department a corresponding tuple is inserted in EMPLOYEE 17 Deletion Anomalies The problem of deletion anomalies is related to the second insertion anomaly situation just discussed If we delete from EMP DEPT an employee tuple that happens to represent the last employee working for a particular department the information concerning that department is lost from the database This problem does not occur in the database of Figure 15 1 because DEPARTMENT tuples are stored separately 18 Modification Anomalies In EMP DEPT if we change the value of one of the attributes of a particular department say the manager of department 5 we must update the tuples of all employees who work in that department otherwise the database will become inconsistent If we fail to update some tuples the same department will be shown to have two different values for manager in different employee tuples which would be wrong 19 Update Anomalies It is easy to see that these three anomalies are undesirable and cause difficulties to maintain consistency of data as well as require unnecessary updates that can be avoided hence we can state the next guideline as follows 20 Guideline 2 Design base relation schemas so that no update anomalies are present in the relations If any anomalies are