1Lectures 8 and 9:Database DesignFriday, October 12and Monday, October 15, 20062Announcements/Reminders• Homework 1: solutions are posted• Homework 2: posted (due Wed. Oct. 24)• Project Phase 1 due Wednesday3Outline• The relational data model: 3.1• Functional dependencies: 3.44The Relational Data Model• Main idea: store data in relations (= tables)• What kind of tables ?– Flat tables = First Normal Form– No anomalies = Boyce Codd Normal Form5First Normal Form (1NF)• A database schema is in First Normal Form if all tables are flat3.9Carol3.7Bob3.8AliceCoursesGPANameOSDBMathOSDBOSMathStudent3.9Carol3.7Bob3.8AliceGPANameStudentCourseOSDBMathOSCarolOSAliceDBBobAliceCarolAliceStudent CourseDBMathMathTakesCourseMay needto add keys6Relational Schema DesignPersonbuysProductnameprice name ssnConceptual Model:Relational Model:plus FD’sNormalization:Eliminates anomalies7Data AnomaliesWhen a database is poorly designed we get anomalies:Redundancy: data is repeatedUpdated anomalies: need to change in several placesDelete anomalies: may lose data when we don’t want8Relational Schema DesignAnomalies:• Redundancy = repeat data• Update anomalies = Fred moves to “Bellevue”• Deletion anomalies = Joe deletes his phone number:what is his city ?Recall set attributes (persons with several phones):Westfield908-555-2121987-65-4321JoeSeattle206-555-6543123-45-6789FredSeattle206-555-1234123-45-6789FredCityPhoneNumberSSNNameOne person may have multiple phones, but lives in only one city9Relation DecompositionBreak the relation into two:Westfield987-65-4321JoeSeattle123-45-6789FredCitySSNName908-555-2121987-65-4321206-555-6543123-45-6789206-555-1234123-45-6789PhoneNumberSSNAnomalies have gone:• No more repeated data• Easy to move Fred to “Bellevue” (how ?)• Easy to delete all Joe’s phone number (how ?)Westfield908-555-2121987-65-4321JoeSeattle206-555-6543123-45-6789FredSeattle206-555-1234123-45-6789FredCityPhoneNumberSSNName10Relational Schema Design(or Logical Design)Main idea:• Start with some relational schema• Find out its functional dependencies• Use them to design a better relational schema11Functional Dependencies• A form of constraint– hence, part of the schema• Finding them is part of the database design• Also used in normalizing the relations12Functional 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, …, Bm13When Does an FD HoldDefinition: A1, ..., Am B1, ..., Bn holds in R if:∀t, t’ ∈ R, (t.A1=t’.A1 ∧ ... ∧ t.Am=t’.Am ⇒ t.B1=t’.B1 ∧ ... ∧ t.Bn=t’.Bn )Bm...B1Am...A1if t, t’ agree here then t, t’ agree herett’R14ExamplesEmpID Name, Phone, PositionPosition Phonebut not Phone PositionAn FD holds, or does not hold on an instance:Lawyer1234MaryE9999Salesrep9876SmithE1111Salesrep9876MikeE3542Clerk1234SmithE0045PositionPhoneNameEmpID15ExamplePosition PhoneLawyer1234MaryE9999Salesrep9876 ←SmithE1111Salesrep9876 ←MikeE3542Clerk1234SmithE0045PositionPhoneNameEmpID16ExampleLawyer1234 →MaryE9999Salesrep9876SmithE1111Salesrep9876MikeE3542Clerk1234 →SmithE0045PositionPhoneNameEmpIDbut not Phone Position17ExampleFD’s are constraints:• On some instances they hold• On others they don’t99ToysGreenGadgetTweaker49ToysGreenGadgetGizmopricedepartmentcolorcategorynameDoes this instance satisfy all the FDs ?name colorcategory departmentcolor, category pricename colorcategory departmentcolor, category price18Example59Office-supp.GreenStationaryGizmo99ToysBlackGadgetTweaker49ToysGreenGadgetGizmopricedepartmentcolorcategorynameWhat about this one ?name colorcategory departmentcolor, category pricename colorcategory departmentcolor, category price19An Interesting ObservationIf all these FDs are true:name colorcategory departmentcolor, category pricename colorcategory departmentcolor, category priceThen this FD also holds:name, category pricename, category priceWhy ??20Goal: Find ALL Functional Dependencies• Anomalies occur when certain “bad” FDs hold• We know some of the FDs• Need to find all FDs, then look for the bad ones21Armstrong’s Rules (1/3)Is equivalent toSplitting ruleand Combing ruleBm...B1Am...A1A1, 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 Bm22Armstrong’s Rules (1/3)Trivial RuleWhy ?Am…A1where i = 1, 2, ..., nA1, A2, …, An AiA1, A2, …, An Ai23Armstrong’s Rules (1/3)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, …, Cp24...C1CpBm…B1Am…A125Example (continued)Start from the following FDs:Infer the following FDs:1. name color2. category department3. color, category price1. name color2. category department3. color, category price8. name, category price7. name, category color, category6. name, category category5. name, category color4. name, category nameWhich Ruledid we apply ?Inferred FD26Example (continued)Answers:Transitivity on 3, 78. name, category priceSplit/combine on 5, 67. name, category color, categoryTrivial rule6. name, category categoryTransitivity on 4, 15. name, category colorTrivial rule4. name, category nameWhich Ruledid we apply ?Inferred FD1. name color2. category department3. color, category price1. name color2. category department3. color, category priceTHIS IS TOO HARD ! Let’s see an easier way.27Closure of a set of AttributesGiven a set of attributes A1, …, AnThe closure, {A1, …, An}+= the set of attributes Bs.t. A1, …, An BGiven a set of attributes A1, …, AnThe closure, {A1, …, An}+= the set of attributes Bs.t. A1, …, An Bname colorcategory departmentcolor, category pricename colorcategory departmentcolor, category priceExample:Closures:name+= {name, color}{name, category}+= {name, category, color, department, price}color+= {color}28Closure AlgorithmX={A1, …,
View Full Document
Unlocking...