Next: Fourth Normal Form (4NF) Up: Normalization Using Multivalued Dependencies Previous: Multivalued Dependencies

## 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 D denote a set of functional and multivalued dependencies.
• The closure of D is the set of all functional and multivalued dependencies logically implied by D.
• We can compute from D 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. An example of multivalued transitivity rule is as follows. and . Thus we have , where .

An example of coalescence rule is as follows. If we have , and , then we have .

4. Let's do an example:
• Let R=(A,B,C,G,H,I) be a relation schema.
• 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.
5. We can simplify calculating , the closure of D 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.
6. An example will help:

Let R=(A,B,C,G,H,I) with the set of dependencies:

```

```

We list some members of :

• : since , complementation rule implies that , and R - B - A = CGHI.
• : Since and , multivalued transitivity rule implies that .

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

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

Next: Fourth Normal Form (4NF) Up: Normalization Using Multivalued Dependencies Previous: Multivalued Dependencies

Osmar Zaiane
Thu Jun 18 12:56:34 PDT 1998