Lossless DecompositionFirst Normal Form (1NF)Example.Functional DependenciesSlide 5ExamplesIn GeneralInference Rules for FD’sInference Rules for FD’s (continued)Problem: Finding FDsFind All FDsComputing KeysExamples of KeysRelational Schema Design (or Logical Schema Design)Data AnomaliesRelational Schema DesignSlide 17Slide 18Example (continued)How to Compute Meaning - Armstrong’s inference rulesSlide 21Another ExampleAnother RuleProblem: infer ALL FDsSlide 25Closure of a set of AttributesClosure AlgorithmExampleUsing Closure to Infer ALL FDsRelation DecompositionSlide 31Decompositions in GeneralDecompositionIncorrect DecompositionSlide 35Normal FormsBoyce-Codd Normal FormBCNF Decomposition AlgorithmSlide 39Decompose it into BCNFSummary of BCNF DecompositionExample DecompositionOther ExampleLossless DecompositionsSlide 453NF: A Problem with BCNFSo What’s the Problem?Solution: 3rd Normal Form (3NF)How to Compute Meaning -the meaning of a set of FDs, F+How to Compute Meaning when do sets of FDs mean the same?How to Compute Meaning - minimal cover of a set of FDsHow to guarantee lossless joinsHow to guarantee preservation of FDs3NF that is not BCNFMajor Results in Normalization TheoryLossy decomposition (more example)Lossy decompositionSlide 58Slide 59Example (con’t)Example (con’t)Slide 62Slide 63Slide 64Lossless DecompositionProf. Sin-Min LeeDepartment of Computer ScienceSan Jose State UniversityFirst Normal Form (1NF)•A database schema is in First Normal Form if all tables are flatName GPA CoursesAlice 3.8Bob 3.7Carol 3.9MathDBOSDBOSMathOSStudentName GPAAlice 3.8Bob 3.7Carol 3.9StudentCourseMathDBOSStudent CourseAlice MathCarol MathAlice DBBob DBAlice OSCarol OSTakesCourseMay needto add keysExample. •customer(name,addr,memberno) Determinants are: –name,addr -> memberno Candidate key–memberno -> name,addr Candidate key –customer in BCNF •hire(memberno,serial,date) Determinants are:–serial,date -> memberno Candidate key–hire in BCNF •Therefore the relations are also now in BCNF.Functional Dependencies•A form of constraint–hence, part of the schema•Finding them is part of the database design•Also used in normalizing the relations•Warning: this is the most abstract, and “hardest” part of the course.Functional DependenciesDefinition: If two tuples agree on the attributes then they must also agree on the attributesFormally: A1, A2, …, An B1, B2, …, BmA1, A2, …, An B1, B2, …, BmA1, A2, …, AnA1, A2, …, AnB1, B2, …, BmB1, B2, …, BmExamples•EmpID Name, Phone, Position•Position Phone•but Phone PositionEmpID Name Phone PositionE0045 Smith 1234 ClerkE1847 John 9876 SalesrepE1111 Smith 9876 SalesrepE9999 Mary 1234 LawyerIn General•To check A B, erase all other columns•check if the remaining relation is many-one (called functional in mathematics)… A … B X1 Y1 X2 Y2 … …Inference Rules for FD’sIs equivalent toSplitting rule and Combining ruleA1 ... Am B1 ... BmA1, A2, …, An B1, B2, …, BmA1, A2, …, An B1, B2, …, BmA1, A2, …, An B1A1, A2, …, An B2 . . . . .A1, A2, …, An BmA1, A2, …, An B1A1, A2, …, An B2 . . . . .A1, A2, …, An BmInference Rules for FD’s(continued)Trivial RuleWhy ?A1…Amwhere i = 1, 2, ..., nA1, A2, …, An AiA1, A2, …, An AiProblem: Finding FDs•Approach 1: During Database Design–Designer derives them from real-world knowledge of users–Problem: knowledge might not be available•Approach 2: From a Database Instance–Analyze given database instance and find all FD’s satisfied by that instance–Useful if designers don’t get enough information from users–Problem: FDs might be artifical for the given instanceFind All FDsStudent Dept Course RoomAlice CSE C++ 020Bob CSE C++ 020Alice EE HW 040Carol CSE DB 045Dan CSE Java 050Elsa CSE DB 045Frank EE Circuits 020Do all FDsmake sensein practice ?Computing Keys•Compute X+ for all sets X•If X+ = all attributes, then X is a key•List only the minimal keysNote: there can be many minimal keys !•Example: R(A,B,C), ABC, BCAMinimal keys: AB and BCExamples of Keys•Product(name, price, category, color)name, category pricecategory colorKeys are: {name, category} and all supersets•Enrollment(student, address, course, room, time)student addressroom, time coursestudent, course room, timeKeys are:Relational Schema Design(or Logical Schema Design)Main idea:•Start with some relational schema•Find out its FD’s•Use them to design a better relational schemaData AnomaliesWhen a database is poorly designed we get anomalies:Redundancy: data is repeatedUpdate anomalies: need to change in several placesDelete anomalies: may lose data when we don’t wantRelational Schema DesignAnomalies:• Redundancy = repeat data• Update anomalies = Fred moves to “Bellevue”• Deletion anomalies = Joe deletes his phone number:what is his city ?Example: Persons with several phonesSSN Name, CitySSN Name, CityName SSN PhoneNumber CityFred 123-45-6789 206-555-1234 SeattleFred 123-45-6789 206-555-6543 SeattleJoe 987-65-4321 908-555-2121 Westfieldbut not SSN PhoneNumberInference Rules for FD’s(continued)Transitive Closure RuleIfandthenWhy ?A1, A2, …, An B1, B2, …, BmA1, A2, …, An B1, B2, …, BmB1, B2, …, Bm C1, C2, …, CpB1, B2, …, Bm C1, C2, …, CpA1, A2, …, An C1, C2, …, CpA1, A2, …, An C1, C2, …, CpA1…AmB1…BmC1...CpExample (continued)Start from the following FDs:Infer the following FDs:1. name color2. category department3. color, category price1. name color2. category department3. color, category priceInferred FDWhich Ruledid we apply ?4. name, category name5. name, category color6. name, category category7. name, category color, category8. name, category priceHow to Compute Meaning- Armstrong’s inference rulesRules of the computation:–reflexivity: if YX, then XY–Augmentation: if X Y, then WXWY–Transitivity: if XY and YZ, then XZDerived rules:–Union: if XY and XZ, the XYZ–Decomposition: if XYZ, then X Y and XZ–Pseudotransitivity: if XY and WYZ, then XWZArmstrong’s Axioms:–sound–completeExample (continued)Answers:Inferred FDWhich Ruledid we apply ?4. name, category nameTrivial rule5. name, category
View Full Document
Unlocking...