- Multivalued dependency occurs when two attributes in a table are independent of each other but, both depend on a third attribute.
- A multivalued dependency consists of at least two attributes that are dependent on a third attribute that's why it always requires at least three attributes
- Functional dependencies rule out certain tuples from appearing
in a relation.
If A
B, then we cannot have two tuples with the same A value but different B 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 R be a relation schema, and let
and
.
The multivalued dependency
holds on R if in any legal relation r(R), for all pairs of tuples
and
in r such that
, there exist tuples
and
in r such that:
Theory of Multivalued Dependencies
-
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.
- Reflexivity rule: if
-
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.
- Multivalued union rule: if
-
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,
.
-
0 comments:
Post a Comment
Note: only a member of this blog may post a comment.