Lecture 11: Functional DependenciesOutlineRelational Schema DesignRelation DecompositionSlide 5Decompositions in GeneralIncorrect DecompositionSlide 8Normal FormsBoyce-Codd Normal FormExampleDecompose it into BCNFSummary of BCNF DecompositionExample DecompositionOther ExampleCorrect DecompositionsSlide 173NF: A Problem with BCNFSo What’s the Problem?Solution: 3rd Normal Form (3NF)Relational AlgebraSlide 221. Union and 2. DifferenceWhat about Intersection ?3. SelectionPowerPoint Presentation4. ProjectionSlide 285. Cartesian ProductSlide 30Slide 31RenamingRenaming ExampleNatural JoinSlide 35Slide 36Slide 37Theta JoinEq-joinSemijoinSemijoins in Distributed DatabasesComplex RA ExpressionsOperations on BagsFinally: RA has Limitations !Lecture 11:Functional DependenciesJanuary 31st, 2003Outline•Relational decomposition•Normal forms •Begin relational algebraRelational Schema DesignAnomalies:• Redundancy = repeat data• Update anomalies = Fred moves to “Bellvue”• Deletion anomalies = Fred drops all phone numbers:what is his city ?Recall set attributes (persons with several phones):SSN Name, City, but not SSN PhoneNumberName SSN PhoneNumber CityFred 123-45-6789 206-555-1234 SeattleFred 123-45-6789 206-555-6543 SeattleJoe 987-65-4321 908-555-2121 WestfieldJoe 987-65-4321 908-555-1234 WestfieldRelation DecompositionBreak the relation into two:Name SSN CityFred 123-45-6789 SeattleJoe 987-65-4321 WestfieldSSN PhoneNumber123-45-6789 206-555-1234123-45-6789 206-555-6543987-65-4321 908-555-2121987-65-4321 908-555-1234Relational Schema DesignPersonbuysProductnameprice name ssnConceptual Model:Relational Model:plus FD’sNormalization:Eliminates anomaliesDecompositions in GeneralR(A1, ..., An) Create two relations R1(B1, ..., Bm) and R2(C1, ..., Cp)such that: B1, ..., Bm C1, ..., Cp = A1, ..., Anand:R1 = projection of R on B1, ..., Bm R2 = projection of R on C1, ..., CpIncorrect Decomposition•Sometimes it is incorrect:Name Price CategoryGizmo 19.99 GadgetOneClick 24.99 CameraDoubleClick 29.99 CameraDecompose on : Name, Category and Price, CategoryIncorrect DecompositionName CategoryGizmo GadgetOneClick CameraDoubleClick CameraPrice Category19.99 Gadget24.99 Camera29.99 CameraName Price CategoryGizmo 19.99 GadgetOneClick 24.99 CameraOneClick 29.99 CameraDoubleClick 24.99 CameraDoubleClick 29.99 CameraWhen we put it back:Cannot recover informationNormal FormsFirst Normal Form = all attributes are atomicSecond Normal Form (2NF) = old and obsoleteThird Normal Form (3NF) = this lectureBoyce Codd Normal Form (BCNF) = this lectureOthers...Boyce-Codd Normal FormA simple condition for removing anomalies from relations:In English (though a bit vague): Whenever a set of attributes of R is determining another attribute, should determine all the attributes of R.A relation R is in BCNF if: Whenever there is a nontrivial dependency A1, ..., An B in R , {A1, ..., An} is a key for RA relation R is in BCNF if: Whenever there is a nontrivial dependency A1, ..., An B in R , {A1, ..., An} is a key for RExampleWhat are the dependencies?SSN Name, CityWhat are the keys?{SSN, PhoneNumber}Is it in BCNF?Name SSN PhoneNumber CityFred 123-45-6789 206-555-1234 SeattleFred 123-45-6789 206-555-6543 SeattleJoe 987-65-4321 908-555-2121 WestfieldJoe 987-65-4321 908-555-1234 WestfieldDecompose it into BCNFName SSN CityFred 123-45-6789 SeattleJoe 987-65-4321 WestfieldSSN PhoneNumber123-45-6789 206-555-1234123-45-6789 206-555-6543987-65-4321 908-555-2121987-65-4321 908-555-1234SSN Name, CitySummary of BCNF DecompositionFind a dependency that violates the BCNF condition:A , A , … A 1 2 nB , B , … B 1 2 mA’sOthersB’sR1 R2Heuristics: choose B , B , … B “as large as possible”1 2 mDecompose:Is there a 2-attribute relation that isnot in BCNF ?Continue untilthere are noBCNF violationsleft.Example Decomposition Person(name, SSN, age, hairColor, phoneNumber)SSN name, ageage hairColorDecompose in BCNF (in class):Step 1: find all keysStep 2: now decomposeOther Example•R(A,B,C,D) A B, B C•Keys: •Violations of BCNF:Correct Decompositions A decomposition is lossless if we can recover: R(A,B,C) R1(A,B) R2(A,C) R’(A,B,C) should be the same as R(A,B,C)R’ is in general larger than R. Must ensure R’ = RDecomposeRecoverCorrect Decompositions•Given R(A,B,C) s.t. AB, the decomposition into R1(A,B), R2(A,C) is lossless3NF: A Problem with BCNFUnit Company ProductUnit CompanyUnit ProductFD’s: Unit Company; Company, Product UnitSo, there is a BCNF violation, and we decompose.Unit CompanyNo FDsSo What’s the Problem?Unit Company ProductUnit Company Unit ProductGalaga99 UW Galaga99 databasesBingo UW Bingo databasesNo problem so far. All local FD’s are satisfied.Let’s put all the data back into a single table again:Galaga99 UW databasesBingo UW databasesViolates the dependency: company, product -> unit!Solution: 3rd Normal Form (3NF)A simple condition for removing anomalies from relations:A relation R is in 3rd normal form if :Whenever there is a nontrivial dependency A1, A2, ..., An Bfor R , then {A1, A2, ..., An } a super-key for R, or B is part of a key. A relation R is in 3rd normal form if :Whenever there is a nontrivial dependency A1, A2, ..., An Bfor R , then {A1, A2, ..., An } a super-key for R, or B is part of a key.Relational Algebra•Formalism for creating new relations from existing ones•Its place in the big picture:DeclartivequerylanguageDeclartivequerylanguageAlgebraAlgebraImplementationImplementationSQL,relational calculusRelational algebraRelational bag algebraRelational Algebra•Five operators:–Union: –Difference: -–Selection:–Projection: –Cartesian Product: •Derived or auxiliary operators:–Intersection, complement–Joins (natural,equi-join, theta join, semi-join)–Renaming:1. Union and 2. Difference•R1 R2•Example: –ActiveEmployees RetiredEmployees•R1 – R2•Example:–AllEmployees -- RetiredEmployeesWhat about Intersection ?•It is a derived operator•R1 R2
View Full Document
Unlocking...