10 - 1 Copyright © 2012 Robinson College of Business, Georgia State University David S. McDonald Director of Emerging Technologies Tel: 404-413-7368; e-mail: [email protected] CIS 8040 - Normalization Relation Normalization Outline Why Normalization? Functional Dependencies. First, Second, and Third Normal Forms. Boyce/Codd Normal Form. Fourth and Fifth Normal Forms. No loss Decomposition. Summary10 - 2 Copyright © 2012 Robinson College of Business, Georgia State University David S. McDonald Director of Emerging Technologies Tel: 404-413-7368; e-mail: [email protected] Why Normalization?  An ill-structured relation contains redundant data  Data redundancy causes modification anomalies:  Insertion anomalies -- Suppose we want to enter SCUBA as an activity that costs $100, we can’t until a student signs up for it  Update anomalies -- If we change the price of swimming for student 150, there is no guarantee that student 200 will pay the new price  Deletion anomalies -- If we delete Student 100, we lose not only the fact that he/she is a skier, but also the fact that skiing costs $200  Normalization is the process used to remove modification anomalies SID Activity Fee 100 Skiing 200 150 Swimming 50 175 Squash 50 200 Swimming 50 ACTIVITY How can this table be changed to fix these problems??? Why Normalization... SID s1 s1 s1 s2 s2 s3 s3 s3 Name Joseph Joseph Joseph Alice Alice Tom Tom Tom Grade A B A A A B B A Course# CIS8110 CIS8120 CIS8140 CIS8110 CIS8140 CIS8110 CIS8140 CIS8680 Text b1 b2 b5 b1 b5 b1 b5 b1 Major CIS CIS CIS CS CS Acct Acct Acct Dept CIS CIS CIS MCS MCS Acct Acct Acct Is there any redundant data? Insertion anomalies? Update anomalies? Deletion anomalies? Course10 - 3 Copyright © 2012 Robinson College of Business, Georgia State University David S. McDonald Director of Emerging Technologies Tel: 404-413-7368; e-mail: [email protected] Functional Dependencies Given two attributes, X and Y, of a relation R, Y is functionally dependent on X iff each X value must always occur with the same Y value in R. R.X --> R.Y or X --> Y List all FDs in the Course relation: Functional Dependencies...  X is called the determinant of Y.  X and Y may be composite.  Dependency relationships change with attribute semantics.  X and Y could be mutually dependent on each other. Husband --> Wife, Wife --> Husband, Husband <--> Wife  X may or may not be the key attribute of R.  A Y value can occur in more than one tuple in R. Course# --> Text10 - 4 Copyright © 2012 Robinson College of Business, Georgia State University David S. McDonald Director of Emerging Technologies Tel: 404-413-7368; e-mail: [email protected] Fully Functional Dependencies  A fully functional dependence ( FFD ) exists between attributes X and Y if Y is not functional dependent on any proper subset of X. ( SID, Course# ) --> Name? ( SID, Course# ) --> Grade? ( SID, Name ) --> Major? ( SID, Name ) --> SID? Note that if X is not composite, then X --> Y is always a FFD.  By default, the term FD refers to FFD Transitively Functional Dependencies Given attributes X, Y, and Z of a relation R, Z is transitively dependent on X iff X --> Y and Y --> Z. Given SID --> Dept and Dept --> College SID -->? Given SID --> Major and Major --> Dept, SID --> ?10 - 5 Copyright © 2012 Robinson College of Business, Georgia State University David S. McDonald Director of Emerging Technologies Tel: 404-413-7368; e-mail: [email protected] Graphical Representation SID Name Major Dept Course# Text Grade Primary Key Course (SID, Name, Grade, Course#, Text, Major, Dept) First Normal Form (1NF) A relation R is in 1NF iff all attribute domains contain atomic values only. A relation in 1NF has modification anomalies Part# WHouse# QTY WAddress INVENTORY (Part#, WHouse#, WAddress, QTY)10 - 6 Copyright © 2012 Robinson College of Business, Georgia State University David S. McDonald Director of Emerging Technologies Tel: 404-413-7368; e-mail: [email protected] Second Normal Form (2NF) A relation is in 2NF iff R is in 1NF and every non key attribute is fully dependent on the primary key (i.e. has no partial functional dependencies).  The term, non key attribute, refers to any attribute that does not belong to any candidate key. Part# WHouse# QTY WAddress INVENTORY (Part#, WHouse#, WAddress, QTY) Modification Anomalies in 2NF 2NF relations have modification anomalies:  Redundant Information?  Update anomalies?  Insertion anomalies?  Deletion anomalies? Which FD causes the redundant data? Part# WHouse# WAddress QTY 123 4 Atlanta 10 456 5 Birmingham 6 456 2 Columbus 10 123 7 Oakland 8 235 4 Atlanta 2 INVENTORY10 - 7 Copyright © 2012 Robinson College of Business, Georgia State University David S. McDonald Director of Emerging Technologies Tel: 404-413-7368; e-mail: [email protected] Third Normal Form (3NF) A relation R is in 3NF iff R is in 2NF and every non key attribute is non transitively dependent on the primary key. Student (SID, Name, Major, Dept) Discussion: If a relation does not have any non-key attribute, would it automatically be in 3NF? LOCATION (Employee, Department, Location)  Redundant Information?  Update anomalies?  Insertion anomalies?  Deletion anomalies?  All determinants? Modification Anomalies in 3NF Location Employee Department10 - 8 Copyright © 2012 Robinson College of Business, Georgia State University David S. McDonald Director of Emerging Technologies Tel: 404-413-7368; e-mail: [email protected] Boyce/Codd Normal Forms (BCNF) A relation R is in BCNF iff every determinant is a candidate key. BCNF is applied to a relation R if 1. Those candidate keys are composite, and 2. The candidate keys are overlapped, ADVISE (Student, Major, Advisor) Can you normalize? STUDENT ADVISOR MAJOR BCNF Example Advise For the ADVISE table, StudentId and major are the primary key.. But there are two candidate keys: StudentId and Major or StudentId and Advisor. If : StudentId and Major is the PK it determines Advisor; If