!" #Chris Irwin Davis, Ph.D. !Email: [email protected] Phone: (972) 883-3574 Office: ECSS 4.705Chapter 15: Functional Dependencies and NormalizationCS-6360 Database Design!" #Chapter 15 Outline1) 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-down6!" #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.8Informal 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 tuples10!" #A Simplified COMPANY Schema11!" #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 design12!" #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.313!" #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 §Modification15!" #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
View Full Document
Unlocking...