Reasoning About Multivalued Dependencies

Reasoning About Multivalued Dependencies

There are a many rules about MVD's that are similar to the rules we learned for FD's in "Rules About Functional Dependencies". For instance, MVD's obey

●  The trivial dependencies rule, which says that if MVD

A1A2 . . . .An  B1B2 . . . Bm

holds for some relation, then so does A1A2 . . .  An   C1C2 . . . Ck, where the C's are the B's plus one or more of the A's. On the other hand, we can also remove attributes from the B's if they are among the A's and infer the MVD A1A2 . . .  An   D1D2 . . . Dr, if the D's are those B's that are not among the A's.

●  The transitive rule, which says that if  A1A2 . . .  An   B1B2 . . . Bm and B1B2 . . . Bm   C1C2 . . . Ck hold for some relation, then so does

A1A2 . . . An   C1C2 . . . Ck

However, any C's that are also B's must be deleted from the right side.

On the other hand, MVD's do not obey the splitting part of the splitting/combining rule, as the following example shows.

Example (a) : Consider again the "Multivalued Dependencies" figure, where we observed the MVD:

name   street city

If the splitting rule applied to MVD's, we would expect

name  street

also to be true. This MVD says that each star's street addresses are independent of the other attributes, including city. However, that statement is false. Consider, for instance, the first two tuples of above figure. The hypothetical MVD would allow us to infer that the tuples with the streets interchanged:



were in the relation. But these are not true tuples, because, for example, the home on 5 Locust Ln. is in Malibu, not Hollywood.

However, there are many new rules dealing with MVD's that we can learn. First,

●  Every FD is a MVD. That is, if A1A2 . . . An     B1B2 . . . Bm, then

A1A2 . . . An   B1B2 . . . Bm.

To See why, suppose R is some relation for which the FD

A1A2 . . . An     B1B2 . . . Bm

holds, and suppose t and u are tuples of R that agree on the A's. To show that the MVD A1A2 . . . An   B1B2 . . . Bm holds, we have to show that R also contains a tuple v that agrees with t and u on the A's, with t on the B's, and with u on all other attributes. But v can be u. Surely u agrees with t and u on the A's, because we started by assuming that these two tuples agree on the A's. The FD A1A2 . . . An     B1B2 . . . Bm assures us that u agrees with t on the B's. And of course u agrees with itself on the other attributes. Therefore, whenever a FD holds, the corresponding MVD holds.

Another rule that has no counterpart in the world of FD's is the complementation rule:

●  If A1A2 . . . An   B1B2 . . . Bm is a MVD for relation R, then R also satisfies A1A2 . . .  An   C1C2 . . . Ck, where the C's are all attributes of R not among the A's and B's.

Example (b) : Again consider the relation of "Multivalued Dependencies" figure, for which we asserted the MVD:

name  street city

The complementation rule says that

name  title year

must also hold in this relation, because title and year are the attributes not mentioned in the first MVD. The second MVD intuitively means that each star has a set of movies starred in, which are independent of the star's addresses.


Tags