Part 6 NormalizationCopyright  1971-2002 Thomas P. Sturm Normalization Part 6, Page 2 Normal Form Overview Universe of All DataRelations (normalized / unnormalized1st Normal Form2nd Normal Form3rd Normal FormBoyce-Codd Normal Form (BCNF)4th Normal Form5th Normal Form (PJ/NF)Domain/KeyNormal Form(DK/NF)Copyright  1971-2002 Thomas P. Sturm Normalization Part 6, Page 3 Universe of Relations Any sequential file is a relation Not all relations are “well formed” Normalization provides a set of criteria to evaluate the “well formedness” of a relation Normal form is only one criterion for determining a “good” model In general, a sequential file may have repeating groups Example 1 - suppliers: part suppliers diode (GE, TRW, Mot) bulb (GE, Syl) Implemented as: part supplier1 supplier2 supplier3 diode GE TRW Mot bulb GE SylCopyright  1971-2002 Thomas P. Sturm Normalization Part 6, Page 4 Problem with a Relation Not in First Normal Form Retrieval: • which supplier of a part should be retrieved? • in which order should suppliers be retrieved? Storage: • how many suppliers do you allow for? • which spaces are kept blank, and how? Insert: • to add a supplier, need to retrieve all suppliers, add the new supplier to an empty slot, and replace the record Delete: • to delete a supplier, need to “adjust” the vector (read, move around, erase, re-write) Update: • to update a supplier name, need to retrieve all suppliers, find the one to alter, and re-write entire set of suppliersCopyright  1971-2002 Thomas P. Sturm Normalization Part 6, Page 5 Solution to Repeating Group Problem Eliminate repeating groups by repeating the key Example 1 - suppliers: part supplier diode GE diode TRW diode Mot bulb GE bulb Syl This new table has a different key than the old one. It is part plus supplier.Copyright  1971-2002 Thomas P. Sturm Normalization Part 6, Page 6 First Normal Form All underlying domains contain atomic values only (no vectors / repeating groups) Example 2 - inventory: part # warehouse # wh_address quantity 100 05 Mpls 200 100 08 StPaul 300 200 05 Mpls 250 200 10 Madison 400 300 08 StPaul 350 Update Anomalies: UPDATE • address of warehouse stored in many rows • if address changes, must change all rows DELETE • if the last row for a warehouse is deleted, the address is lost INSERT • to insert a new row, warehouse address must be known The problem occurs because this table is not focused on one primary key - it is “about” two things - warehouses and parts in warehouses.Copyright  1971-2002 Thomas P. Sturm Normalization Part 6, Page 7 Solution to Multiple Focus Problems A relation that is in 1NF but not in a higher normal form has a composite key (more than one attribute in the key) Establish 2 relations via projection Example 2 - inventory: One table about warehouses: warehouse# wh_address 05 Mpls 08 StPaul 10 Madison One table about inventory with a composite key: part# warehouse# quantity 100 05 200 100 08 300 200 05 250 200 10 400 300 08 350 The original table in 1NF can be reconstructed by a joinCopyright  1971-2002 Thomas P. Sturm Normalization Part 6, Page 8 Second Normal Form 1NF + every non-key attribute is fully functionally dependent on the primary key Example 3 - departments: name dept dept_loc smith 402 100 jones 401 200 king 402 100 turner 400 200 olson 401 200 Problem: Functional dependency is transitive • The primary key is name • dept is functionally dependent on name • dept_loc is also functionally dependent on name, but it is transitive because dept functionally determines dept_locCopyright  1971-2002 Thomas P. Sturm Normalization Part 6, Page 9 Problems with 2NF Relations Update Anomalies: UPDATE - location appears many times - if location of a department changes, must fetch and change all rows containing that location DELETE - if the last row for a department is deleted, the department location information is lost INSERT - to insert a new row, department location must be known Solution: Establish 2 relations via projection Example 3 - departments: name dept and dept dept_loc smith 402 400 200 jones 401 401 200 king 402 402 100 turner 400 olson 401Copyright  1971-2002 Thomas P. Sturm Normalization Part 6, Page 10 Third Normal Form 2NF + every non-key attribute is non-transitively functionally dependent on the primary key OR Every non-key attribute is • mutually independent (none is functionally dependent on any of the others) • fully functionally dependent on the primary key OR (Kent) Each attribute in the relation is functionally dependent on the key, the whole key, and nothing but the key A relation that is 2NF but not 3NF • can be split into a collection of 3NF relations by projection • can be reconstructed by joinCopyright  1971-2002 Thomas P. Sturm Normalization Part 6, Page 11 3NF Examples Example 4 - locations: dept# dept_name dept_loc 400 programming 200 401 financial 200 402 academic 100 403 support 300 • dept# and dept_name are candidate keys • dept_loc is the only non-key attribute, and is, by default, non-transitively functionally dependent on the primary key • This table is fine - it is only about departments Example 5 - stock: s# sname p# qty 10 GE 102 1000 10 GE 103 625 10 GE 104 2000 20 TRW 102 500 20 TRW 105 1200 30 Syl 103 1300 • technically in 3NF • qty is the only non-key attribute (like example 1) • candidate keys are (s#, p#) and (sname, p#) • didn't require components of an alternate key to be fully functionally dependent on the primary keyCopyright  1971-2002 Thomas P. Sturm Normalization Part 6, Page 12 Problems with 3NF Relations The problems associated with alternate key components were not recognized in the early formulations of the relational model. Have the same update anomalies as second normal form Solution: Establish 2 relations via projection Example 5 - stock: s# sname and s# p# qty 10 GE 10 102 1000 20 TRW 10 103 625 30 Syl 10 104 2000 20 102 500 20 105 1200 30 103 1300 or [s#, sname] and [sname, p#, qty] Because of this problem, 3NF (as we have described it) is sometimes referred to as “early 3rd Normal Form”Copyright  1971-2002 Thomas P. Sturm Normalization Part