CSC 426 Chapter 14, Fall 2011

Chapter 14 Introduction to Normalization Using Functional and Multivalued Dependencies Chapter 14 Outline  Informal Design Guidelines for Relation Schemas  Functional Dependencies  Normal Forms Based on Primary Keys  General Definitions of Second and Third Normal Forms  Boyce-Codd Normal Form Introduction  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 or top-down Informal Design Guidelines for Relation Schemas  Measures of quality  Making sure attribute semantics are clear  Reducing redundant information in tuples  Reducing NULL values in tuples  Disallowing possibility of generating spurious tuples 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 14.3 Guideline 1 (cont’d.) 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 Guideline 2  Design base relation schemas so that no update anomalies are present in the relations  If any anomalies are present:  Note them clearly  Make sure that the programs that update the database will operate correctly Staff and DistributionCenter tables with StaffDistributionCenter table 13 NULL Values in Tuples  May group many attributes together into a “fat” relation  Can end up with many NULLs  Problems with NULLs  Wasted storage space  Problems understanding meaning Guideline 3  Avoid placing attributes in a base relation whose values may frequently be NULL  If NULLs are unavoidable:  Make sure that they apply in exceptional cases only, not to a majority of tuples Guideline 4  Design relation schemas to be joined with equality conditions on attributes that are appropriately related  Guarantees that no spurious tuples are generated  Avoid relations that contain matching attributes that are not (foreign key, primary key) combinations Summary and Discussion of Design Guidelines  Anomalies cause redundant work to be done  Waste of storage space due to NULLs  Difficulty of performing operations and joins due to NULL values  Generation of invalid and spurious data during joins Functional Dependencies  Formal tool for analysis of relational schemas  Enables us to detect and describe some of the above-mentioned problems in precise terms  Theory of functional dependency Definition of Functional Dependency  Constraint between two sets of attributes from the database  Property of semantics or meaning of the attributes  Legal relation states  Satisfy the functional dependency constraints Definition of Functional Dependency (cont’d.)  Given a populated relation  Cannot determine which FDs hold and which do not  Unless meaning of and relationships among attributes known  Can state that FD does not hold if there are tuples that show violation of such an FD Normal Forms Based on Primary Keys  Normalization process  Approaches for relational schema design  Perform a conceptual schema design using a conceptual model then map conceptual design into a set of relations  Design relations based on external knowledge derived from existing implementation of files or forms or reports Normalization of Relations  Takes a relation schema through a series of tests  Certify whether it satisfies a certain normal form  Proceeds in a top-down fashion  Normal form tests Normalization of Relations (cont’d.)  Properties that the relational schemas should have:  Nonadditive join property • Extremely critical  Dependency preservation property • Desirable but sometimes sacrificed for other factors Practical Use of Normal Forms  Normalization carried out in practice  Resulting designs are of high quality and meet the desirable properties stated previously  Pays particular attention to normalization only up to 3NF, BCNF, or at most 4NF  Do not need to normalize to the highest possible normal form Definitions of Keys and Attributes Participating in Keys  Definition of superkey and key  Candidate key  If more than one key in a relation schema • One is primary key • Others are secondary keys First Normal Form  Part of the formal definition of a relation in the basic (flat) relational model  Only attribute values permitted are single atomic (or indivisible) values  Techniques to achieve first normal form  Remove attribute and place in separate relation  Expand the key  Use several atomic attributes First Normal Form (cont’d.)  Does not allow nested relations  Each tuple can have a relation within it  To change to 1NF:  Remove nested relation attributes into a new relation  Propagate the primary key into it  Unnest relation into a set of 1NF relations First normal form (1NF)  Only 1NF is critical in creating appropriate tables for relational databases. All subsequent normal forms are optional.  A table in which the intersection of every column and record contains only one value. 31 DistributionCenter table is not in 1NF 32 Converting DistributionCenter table to 1NF 33 Second Normal Form  Based on concept of full functional dependency  Versus partial dependency  Second normalize into a number of 2NF relations  Nonprime attributes are associated only with part of primary key on which they are fully functionally dependent Third Normal Form  Based on concept of transitive dependency  Problematic FD  Left-hand side is part of primary key  Left-hand side is a nonkey attribute Second normal form (2NF)  A table that is in 1NF and in which the values of each non-primary-key column are determined by the values in all the columns that make up the primary key.  To assess whether a table breaks 2NF form requires identification of the primary key and functional dependencies associated with that table.  2NF only applies to tables with composite primary keys. 36 Functional dependency  Describes the relationship between columns in a table and indicates how columns relate to one another.  For example, consider a table with columns a and b, where b is functionally dependent on a (denoted a → b). If we know the value of a, we find only one value of b in all the records that has this value of a, at any moment in time. However, for a given value of b there may be several different values of a. 37 Second normal form (2NF)  Formal definition of 2NF is a table that is in 1NF and every non-primary-key column is fully functional dependent on the primary key.  Full functional dependency indicates that if a and b are columns of a table, b is fully determined by a, if b is not determined by any subset of a. If b is determined by a subset of a, this is referred to as a partial dependency.  Identification of partial dependencies on the primary key is evidence that a table is breaking 2NF and may suffer from update anomalies. 38 TempStaffAllocation table is not in 2NF 39 Converting TempStaffAllocation table to 2NF 40 Third normal form (3NF)  A table that is in 1NF and 2NF and in which the values in all non-primary-key column can be determined from only the primary key column(s) and no other columns.  The formal definition of 3NF is a table that is in 1NF and 2NF and in which no non- primary-key column is transitively dependent on the primary key. 41 Third normal form (3NF)  A transitive dependency describes a relationship between columns a, b, and c. If a determines b (a b) and b determines c (b → → c), then c is transitively dependent on a via b (provided that b or c does not determine a).  Identification of transitive dependencies on the primary key is evidence that a table is breaking 3NF and may suffer from update anomalies. 42 The StaffDistributionCenter table is not in 3NF 43 Converting StaffDistributionCenter table to 3NF 44 General Definitions of Second and Third Normal Forms More examples Summary  Informal guidelines for good design  Functional dependency  Basic tool for analyzing relational schemas  Normalization:  1NF, 2NF, 3NF,