Multivalued Dependencies

1. • Functional dependencies rule out certain tuples from appearing in a relation.
   • If A B, then we cannot have two tuples with the same value but different values.

   • Multivalued dependencies do not rule out the existence of certain tuples.
   • Instead, they require that other tuples of a certain form be present in the relation.
   • Let be a relation scheme, and let and .
   • The multivalued dependency

     

     holds on if in any legal relation , for all pairs of tuples and in such that , there exist tuples and in such that:

     

2. Figure 6.1 (textbook 6.10) shows a tabular representation of this. It looks horrendously complicated, but is really rather simple. We'll see some extra examples in class as well.

    
   Figure 6.1:   Tabular representation of .
   

   • Intuitively, says that the relationship between and is independent of the relationship between and .
   • If the multivalued dependency is satisfied by all relations on scheme , then we say it is a trivial multivalued dependency on scheme .
   • Thus is trivial if or .
3. Look at the example relation bc relation in Figure 6.2 (textbook 6.11).

    
   Figure 6.2:   Relation bc, an example of redundancy in a BCNF relation.
   

   • We must repeat the loan number once for each address a customer has.
   • We must repeat the address once for each loan the customer has.
   • This repetition is pointless, as the relationship between a customer and a loan is independent of the relationship between a customer and his or her address.
   • If a customer, say ``Smith'', has loan number 23, we want all of Smith's addresses to be associated with that loan.
   • Thus the relation of Figure 6.3 (textbook 6.12) is illegal.
   • If we look at our definition of multivalued dependency, we see that we want the multivalued dependency

     

     to hold on BC-scheme.

    
   Figure 6.3:   An illegal bc relation.
   

4. Note that if a relation fails to satisfy a given multivalued dependency, we can construct a relation that does satisfy the multivalued dependency by adding tuples to .