Theory of Multivalued Dependencies

1. We will need to compute all the multivalued dependencies that are logically implied by a given set of multivalued dependencies.
   • Let denote a set of functional and multivalued dependencies.
   • The closure of is the set of all functional and multivalued dependencies logically implied by .
   • We can compute from using the formal definitions, but it is easier to use a set of inference rules.
2. The following set of inference rules is sound and complete. The first three rules are Armstrong's axioms from Chapter 5.
   1. Reflexivity rule: if is a set of attributes and , then holds.

   2. Augmentation rule: if holds, and is a set of attributes, then holds.

   3. Transitivity rule: if holds, and holds, then holds.

   4. Complementation rule: if holds, then holds.

   5. Multivalued augmentation rule: if holds, and and , then holds.

   6. Multivalued transitivity rule: if holds, and holds, then holds.

   7. Replication rule: if holds, then .

   8. Coalescence rule: if holds, and , and there is a such that and and , then holds.
3. Let's do an example:
   • Let be a relation scheme.
   • Suppose holds.
   • The definition of multivalued dependencies implies that if , then there exists tuples and such that:

     

   • The complementation rule states that if then .
   • Tuples and satisfy if we simply change the subscripts.
4. We can simplify calculating , the closure of by using the following rules, derivable from the previous ones:
   • Multivalued union rule: if holds and holds, then holds.
   • Intersection rule: if holds and holds, then holds.
   • Difference rule: if holds and holds, then holds and holds.
5. An example will help:

   Let with the set of dependencies:

   

   We list some members of :

   • : since , complementation rule implies that , and .
   • : Since and , multivalued transitivity rule implies that .

   • : coalescence rule can be applied. holds, and and , so we can satisfy the coalescence rule with being , being , being , and being . We conclude that .

   • : now we know that and . By the difference rule, .