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.
The following set of inference rules is sound and complete.
The first three rules are Armstrong's axioms from Chapter 5.
Reflexivity rule: if is a set of attributes and
, then holds.
Augmentation rule: if holds, and
is a set of attributes,
then holds.
Transitivity rule: if holds, and
holds, then holds.
Complementation rule: if holds, then
holds.
Multivalued augmentation rule: if holds,
and and , then
holds.
Multivalued transitivity rule: if holds,
and holds, then holds.
Replication rule: if holds, then
.
Coalescence rule: if holds, and
, and there is
a such that and
and ,
then holds.
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 .
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.
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.
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, .