Functional Dependencies and Relational Schema DesignDecompositions in GeneralIncorrect DecompositionNormal FormsBoyce-Codd Normal FormExampleDecompose it into BCNFWhat About This?BCNF DecompositionExample DecompositionCorrect DecompositionsDecomposition Based on BCNF is Necessarily Lossless3NF: A Problem with BCNFSo What’s the Problem?Solution: 3rd Normal Form (3NF)Multi-valued DependenciesDefinition of Multi-valued DependecyDefinition of MVDs ContinuedRules for MVDs4th Normal Form (4NF)Confused by Normal Forms ?Functional Dependencies and Relational Schema DesignDecompositions in GeneralA , A , … A 1 2 nLet R be a relation with attributes Create two relations R1 and R2 with attributes B , B , … B 1 2 mC , C , … C 1 2 lSuch that:B , B , … B 1 2 mC , C , … C 1 2 l A , A , … A 1 2 nAnd -- R1 is the projection of R on -- R2 is the projection of R on B , B , … B 1 2 mC , C , … C 1 2 lIncorrect 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 informationName Price CategoryGizmo 19.99 GadgetOneClick 24.99 CameraDoubleClick 29.99 CameraDecompose on : Name, Category and Price, CategoryNormal 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: A relation R is in BCNF if and only if: Whenever there is a nontrivial dependency for R , it is the case that { } a super-key for R. A , A , … A 1 2 nBA , A , … A 1 2 nIn English (though a bit vague): Whenever a set of attributes of R is determining another attribute, should determine all the attributes of R.ExampleName SSN Phone NumberFred 123-321-99 (201) 555-1234Fred 123-321-99 (206) 572-4312Joe 909-438-44 (908) 464-0028Joe 909-438-44 (212) 555-4000What are the dependencies?SSN NameWhat are the keys?Is it in BCNF?Decompose it into BCNFSSN Name123-321-99 Fred909-438-44 JoeSSN Phone Number123-321-99 (201) 555-1234123-321-99 (206) 572-4312909-438-44 (908) 464-0028909-438-44 (212) 555-4000SSN NameWhat About This?Name Price CategoryGizmo $19.99 gadgetsOneClick $24.99 cameraName Price, CategoryBCNF 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:Find a 2-attribute relation that isnot in BCNF.Continue untilthere are noBCNF violationsleft.Example Decomposition Name SSN Age EyeColor PhoneNumberFunctional dependencies: SSN Name, Age, Eye ColorWhat if we also had an attribute Draft-worthy, and the FD: Age Draft-worthyPerson:BNCF: Person1(SSN, Name, Age, EyeColor), Person2(SSN, PhoneNumber)Correct Decompositions A decomposition is lossless if we can recover: R(A,B,C) { R1(A,B) , R2(A,C) } R’(A,B,C) = R(A,B,C)R’ is in general larger than R. Must ensure R’ = RDecomposeRecoverDecomposition Based on BCNF is Necessarily Lossless R(A, B, C), A CBCNF: R1(A,B), R2(A,C)Some tuple (a,b,c) in R (a,b’,c’) also in R decomposes into (a,b) in R1 (a,b’) also in R1 and (a,c) in R2 (a,c’) also in R2Recover tuples in R: (a,b,c), (a,b,c’), (a,b’,c), (a,b’,c’) also in R ?Can (a,b,c’) be a bogus tuple? What about (a,b’,c’) ?3NF: 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.Multi-valued Dependencies SSN Phone Number Course 123-321-99 (206) 572-4312 CSE-444 123-321-99 (206) 572-4312 CSE-341123-321-99 (206) 432-8954 CSE-444123-321-99 (206) 432-8954 CSE-341The multi-valued dependencies are: SSN Phone Number SSN CourseDefinition of Multi-valued DependecyGiven R(A1,…,An,B1,…,Bm,C1,…,Cp)the MVD A1,…,An B1,…,Bm holds if:for any values of A1,…,An the “set of values” of B1,…,Bm is “independent” of those of C1,…CpGiven R(A1,…,An,B1,…,Bm,C1,…,Cp)the MVD A1,…,An B1,…,Bm holds if:for any values of A1,…,An the “set of values” of B1,…,Bm is “independent” of those of C1,…CpDefinition of MVDs ContinuedEquivalently: the decomposition intoR1(A1,…,An,B1,…,Bm), R2(A1,…,An,C1,…,Cp)is losslessNote: an MVD A1,…,An B1,…,BmImplicitly talks about “the other” attributes C1,…CpRules for MVDsIf
View Full Document
Unlocking...