DOC PREVIEW
SJSU CS 157A - 25SpCS157AL18Multivalued Dependency

This preview shows page 1-2-3-4-25-26-27-51-52-53-54 out of 54 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 54 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 54 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 54 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 54 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 54 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 54 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 54 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 54 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 54 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 54 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 54 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 54 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 XY holds for R,so does the functional dependency XA 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

SJSU CS 157A - 25SpCS157AL18Multivalued Dependency

Documents in this Course
SQL

SQL

18 pages

Lecture

Lecture

44 pages

Chapter 1

Chapter 1

56 pages

E-R Model

E-R Model

16 pages

Lecture

Lecture

48 pages

SQL

SQL

15 pages

SQL

SQL

26 pages

Lossless

Lossless

26 pages

SQL

SQL

16 pages

Final 3

Final 3

90 pages

Lecture 3

Lecture 3

22 pages

SQL

SQL

25 pages

Load more
Download 25SpCS157AL18Multivalued Dependency
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view 25SpCS157AL18Multivalued Dependency and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view 25SpCS157AL18Multivalued Dependency 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?