Multivalued Dependencies .


20 views
Uploaded on:
Description
Multivalued Dependencies. Fourth Normal Form. Source: Slides by Jeffrey Ullman. Definition of MVD.
Transcripts
Slide 1

Multivalued Dependencies Fourth Normal Form Source: Slides by Jeffrey Ullman

Slide 2

Definition of MVD A multivalued reliance (MVD) on R , X - >- > Y , says that if two tuples of R concur on every one of the qualities of X , then their segments in Y might be swapped, and the outcome will be two tuples that are additionally in the connection. i.e., for every estimation of X , the estimations of Y are free of the estimations of R - X - Y .

Slide 3

Example Consumers(name, addr, telephones, candiesLiked) A buyer\'s telephones are free of the confections they like. name->- >phones and name - >- >candiesLiked . Along these lines, each of a customer\'s telephones shows up with each of the confections they like in all blends. This reiteration is not at all like FD repetition. name->addr is the main FD.

Slide 4

sue a p2 b1 sue a p1 b2 Then these tuples should likewise be in the connection . Tuples Implied by name->- >phones If we have tuples: name addr phones candiesLiked sue a p1 b1 sue a p2 b2

Slide 5

Picture of MVD X - >- > Y X Y others break even with trade

Slide 6

MVD Rules Every FD is a MVD ( advancement ). On the off chance that X - > Y , then swapping Y \'s between two tuples that concur on X doesn\'t change the tuples. In this way, the "new" tuples are clearly in the connection, and we know X - >- > Y . Complementation : If X - >- > Y , and Z is the various qualities, then X - >- > Z .

Slide 7

Splitting Doesn\'t Hold Like FD\'s, we can\'t for the most part split the left half of a MVD. In any case, not at all like FD\'s, we can\'t part the right side either - in some cases you need to leave a few properties on the right side.

Slide 8

Example Consumers(name, areaCode, telephone, candiesLiked, manf) A purchaser can have a few telephones, with the number isolated amongst areaCode and telephone (last 7 digits). A customer can like a few confections, each with its own particular maker.

Slide 9

Example, Continued Since the areaCode-telephone mixes for a purchaser are autonomous of the candiesLiked-manf mixes, we expect that the accompanying MVD\'s hold: name - >- > areaCode telephone name - >- > candiesLiked manf

Slide 10

Example Data Here is conceivable information fulfilling these MVD\'s: name areaCode phone candiesLiked manf Sue 650 555-1111 Twizzlers Hershey Sue 650 555-1111 Smarties Nestle Sue 415 555-9999 Twizzlers Hershey Sue 415 555-9999 Smarties Nestle But we can\'t swap territory codes or telephones independent from anyone else. That is, neither name->- >areaCode nor name->- >phone holds for this connection.

Slide 11

Fourth Normal Form The excess that originates from MVD\'s is not removable by putting the database pattern in BCNF. There is a more grounded ordinary frame, called 4NF, that (instinctively) regards MVD\'s as FD\'s with regards to decay, however not when deciding keys of the connection.

Slide 12

4NF Definition A connection R is in 4NF if: at whatever point X - >- > Y is a nontrivial MVD, then X is a superkey. Nontrivial MVD implies that: Y is not a subset of X , and X and Y are not, together, every one of the qualities. Take note of that the meaning of "superkey" still relies on upon FD\'s as it were.

Slide 13

BCNF Versus 4NF Remember that each FD X - > Y is additionally a MVD, X - >- > Y . In this way, if R is in 4NF, it is positively in BCNF. Since any BCNF infringement is a 4NF infringement (after transformation to a MVD). Be that as it may, R could be in BCNF and not 4NF, in light of the fact that MVD\'s are "undetectable" to BCNF.

Slide 14

Decomposition and 4NF If X - >- > Y is a 4NF infringement for connection R , we can break down R utilizing an indistinguishable strategy from for BCNF. XY is one of the disintegrated relations. Everything except Y – X is the other.

Slide 15

Example Consumers( name , addr, telephones , candiesLiked ) FD: name - > addr MVD\'s: name - >- > telephones name - >- > candiesLiked Key is {name, telephones, candiesLiked} . All conditions damage 4NF.

Slide 16

Example, Continued Decompose utilizing name - > addr : Consumers1( name , addr) In 4NF; just reliance is name - > addr . Consumers2( name , telephones , candiesLiked ) Not in 4NF. MVD\'s name - >- > telephones and name - >- > candiesLiked apply. No FD\'s, so each of the three characteristics shape the key.

Slide 17

Example: Decompose Consumers2 Either MVD name - >- > telephones or name - >- > candiesLiked instructs us to decay to: Consumers3( name , telephones ) Consumers4( name , candiesLiked )

Slide 18

Normal Form Comparisons 4NF  BCNF  3NF

Recommended
View more...