Multivalued DependencySlide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Multivalued DependenciesExampleMVD RulesSplitting Doesn’t Hold4NFSlide 35Slide 36Multivalued Dependencies (cont)Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Slide 51Theory of Multivalued DependenciesSlide 53Theory of Multivalued Dependencies (cont)Multivalued DependencyProf. Sin-Min LeeDepartment of Computer Science1NF2NF3NFBCNF4NF5NFfunctional dependenciesmultivalueddependenciesjoindependenciesHIGHER NORMAL FORMSMaryC++ ReadingTennisCyclingJennyC++ MusicDatabasesJohnPascal MusicDatabases JoggingJavaSTUDENT MODULE HOBBYSTUDENT learns MODULESTUDENT enjoys HOBBYJohn learns Pascal Databases JavaMary learns C++ Jenny learns C++ Databases John enjoys Music Jogging Mary enjoys Reading Tennis Cycling Jenny enjoys MusicSTUDENT MODULE HOBBYJohn Pascal MusicJohn Pascal JoggingJohn Databases MusicJohn Databases JoggingJohn Java MusicJohn Java JoggingMary C++ ReadingMary C++ TennisMary C++ CyclingJenny C++ MusicJenny Databases MusicPROFILEmultivalued dependency X Y holds in R if:whenever two tuples of R agree in value of X,their image sets in R(X,Y) are the same;X, Y, Z - pairwise disjoint subsets of R (X,Y,Z)STUDENT MODULESTUDENT HOBBYmutually independentPROFILE is in BCNF but exhibitsredundancy and I, D ad U anomaliesFourth Normal FormR(X, Y, Z) is in 4NF if,whenever a multivalued dependency XY holds for R,so does the functional dependency XA for all attributes A in RR is in 4NFx1x2…xny1y2…ynz1z2…znX Y Z if then fd mvdpreventing conjunction of unrelated facts4NF: every MVD is FDS TUDENT MODULE S TUDENT HOBBYJohn Pasc al John MusicJohn Databases John JoggingJohn Java Mary ReadingMary C++ Mary TennisJenny C++ Mary CyclingJenny Databases Jenny MusicPROFILELEISUREACADEMICMultivalued DependenciesThe multivalued dependency X Y holds in a relation R if whenever we have two tuples of R that agree in all the attributes of X, then we can swap their Y components and get two new tuples that are also in R.X Y othersExampleDrinkers(name, addr, phones, beersLiked) with MVD Name phones. If Drinkers has the two tuples:name addr phones beersLiked sue a p1 b1sue a p2 b2it must also have the same tuples with phones components swapped: name addr phones beersLiked sue a p2 b1sue a p1 b2Note: we must check this condition for all pairs of tuples that agree on name, not just one pair.MVD Rules1.Every FD is an MVD.–Because if X Y, then swapping Y’s between tuples that agree on X doesn’t create new tuples.–Example, in Drinkers: name addr.2.Complementation: if X Y, then X Z, where Z is all attributes not in X or Y.–Example: since name phonesholds in Drinkers, so doesname addr beersLiked.Splitting Doesn’t HoldSometimes you need to have several attributes on the right of an MVD. For example:Drinkers(name, areaCode, phones, beersLiked, beerManf)name areaCode phones beersLiked beerManfSue 831 555-1111 Bud A.B.Sue 831 555-1111 Wicked Ale Pete’sSue 408 555-9999 Bud A.B.Sue 408 555-9999 Wicked Ale Pete’s• name areaCode phones holds, but neither name areaCode nor name phones do.4NFEliminate redundancy due to multiplicative effect of MVD’s.•Roughly: treat MVD’s as FD's for decomposition, but not for finding keys.•Formally: R is in Fourth Normal Form if whenever MVDX Y is nontrivial (Y is not a subset of X, and X Y is not all attributes), then X is a superkey.–Remember, X Y implies X Y, so 4NF is more stringentthan BCNF.•Decompose R, using4NF violation X Y,into XY and X (R—Y).R Y XExampleDrinkers(name, addr, phones, beersLiked)•FD: name addr•Nontrivial MVD’s: name phones andname beersLiked.•Only key: {name, phones, beersLiked}•All three dependencies above violate 4NF.•Successive decomposition yields 4NF relations:D1(name, addr)D2(name, phones)D3(name, beersLiked)Multivalued Dependencies•Multivalued dependencies are referred to as tuple-generating dependencies.•Let R be a relation schema and let R and R. The multivalued dependency is holds on R if, in any legal relation r( R ), for all pairs of tuples t1 and t2 in r such that t1[] = t2[ ], there exist tuples t3 and t4 in r such thatMultivalued Dependencies (cont)•t1[ ] = t2[ ] = t3[ ] = t4[ ]t3[ ] = t1[ ]t3[ R - ] = t2[ R - ]t4[ ] = t2[ ]t4[ R - ] = t1[ R - ]•The multivalued dependency says that the relationship between and is independent of the relationship between and R - .Multivalued Dependencies (cont)•If the multivalued dependency is satisfied by all relations on schema R, then is a trivial multivalued dependency on schema R. •Thus, is trivial if or = RTabular representation of R - - t1 a1…ai ai+1…aj aj+1…ant2 a1…ai bi+1…bj bj+1…bnt3 a1…ai ai+1…aj bj+1…bnt4 a1…ai bi+1…bj aj+1…anExample: Here is an example of multivalued dependencies given R(A B C D). Show that A BD we can rearrange the table to R(A B D C).A B C D1 2 3 12 1 4 12 1 2 12 1 2 23 1 3 14 2 3 13 2 3 22 1 4 2A B D C1 2 1 32 1 1 42 1 1 22 1 2 23 1 1 34 2 1 33 2 2 32 1 2 4Example (Cont.): Perform each test to check if A BD.t1 = r53 1 1 3t2 = r73 2 2 3t3 = r53 1 1 3t4 = r73 2 2 3t1 = r22 1 1 4t2 = r32 1 1 2t3 = r32 1 1 2t4 = r22 1 1 4t1 = r22 1 1 4t2 = r82 1 2 4t3 = r22 1 1 4t4 = r82 1 2 4t1 = r22 1 1 4t2 = r42 1 2 2t3 = r32 1 1 2t4 = r82 1 2 4Example (Cont.): Perform each test to check if A BD.t1 = r32 1 1 2t2 = r42 1 2 2t3 = r32 1 1 2t4 = r42 1 2 2t1 = r32 1 1 2t2 = r82 1 2 4t3 = r22 1 1 4t4 = r42 1 2 2t1 = r42 1 2 2t2 = r82 1 2 4t3 = r82 1 2 4t4 = r42 1 2 2Each test is satisfied, so A BD is true!!!Multivalued Dependencies (cont)•To illustrate the difference between functional and multivalued dependencies, we consider again the BC-schema. Graph 1loan-number customer-name customer-street customer-cityL-23
View Full Document