Multivalued dependency

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In database theory, multivalued dependency is a full constraint between two sets of attributes in a relation.

In contrast to the functional dependency, the multivalued dependency requires that certain tuples be present in a relation. Therefore, a multivalued dependency is a special case of tuple-generating dependency. The multivalued dependency plays a role in the 4NF database normalization.

A multivalued dependency is a special case of a join dependency, with only two sets of values involved, i.e. it is a 2-ary join dependency.

Formal definition[edit]

The formal definition is given as follows. [1]

Let R be a relational schema and let \alpha \subseteq R and \beta \subseteq R (subsets). The multivalued dependency
\alpha \twoheadrightarrow \beta
(which can be read as  \alpha multidetermines  \beta ) holds on R if, in any legal relation r(R), for all pairs of tuples t _1 and t _2 in r such that t _1[\alpha]=t _2[\alpha], there exist tuples t _3 and t _4 in r such that
t _1[\alpha] = t _2 [\alpha] = t _3 [\alpha] = t _4 [\alpha]
t _3[\beta] = t _1 [\beta]
t _3[R - \beta] = t _2 [R - \beta]
t _4[\beta] = t _2 [\beta]
t _4[R - \beta] = t _1 [R - \beta]

In more simple words the above condition can be expressed as follows: if we denote by (x,y,z) the tuple having values for \alpha, \beta, R - \alpha - \beta collectively equal to x, y, z, correspondingly, then whenever the tuples (a,b,c) and (a,d,e) exist in r, the tuples (a,b,e) and (a,d,c) should also exist in r.

Example[edit]

Consider this example of a database of teaching courses, the books recommended for the course, and the lecturers who will be teaching the course:

Course Book Lecturer
AHA Silberschatz John D
AHA Nederpelt William M
AHA Silberschatz William M
AHA Nederpelt John D
AHA Silberschatz Christian G
AHA Nederpelt Christian G
OSO Silberschatz John D
OSO Silberschatz William M

Because the lecturers attached to the course and the books attached to the course are independent of each other, this database design has a multivalued dependency; if we were to add a new book to the AHA course, we would have to add one record for each of the lecturers on that course, and vice versa.
Put formally, there are two multivalued dependencies in this relation: {course} \twoheadrightarrow {book} and equivalently {course} \twoheadrightarrow {lecturer}.
Databases with multivalued dependencies thus exhibit redundancy. In database normalization, fourth normal form requires that either every multivalued dependency X \twoheadrightarrow Y is trivial or for every nontrivial multivalued dependency X \twoheadrightarrow Y, X is a superkey.

Interesting properties[edit]

  • If \alpha \twoheadrightarrow \beta, Then \alpha \twoheadrightarrow R - \beta
  • If \alpha \twoheadrightarrow \beta and \gamma \subseteq \delta, Then \alpha \delta \twoheadrightarrow \beta \gamma
  • If \alpha \twoheadrightarrow \beta and \beta \twoheadrightarrow \gamma, then \alpha \twoheadrightarrow \gamma - \beta

The following also involve functional dependencies:

  • If \alpha \rightarrow \beta, then \alpha \twoheadrightarrow \beta
  • If \alpha \twoheadrightarrow \beta and \beta \rightarrow \gamma, then \alpha \twoheadrightarrow \gamma - \beta

The above rules are sound and complete.

  • A decomposition of R into (XY) and (XR − Y) is a lossless-join decomposition if and only if X \twoheadrightarrow Y holds in R.
  • Every FD is an MVD because if X \rightarrow Y, then swapping Y's between tuples that agree on X doesn't create new tuples.
  • Splitting Doesn’t Hold. Like FD’s, we cannot generally split the left side of an MVD.But unlike FD’s, we cannot split the right side either, sometimes you have to leave several attributes on the right side.
  • Closureof a set of MVDs is the set of all MVDs that can be inferred using the following rules(Armstrong's axioms):
    • Complementation: If X \twoheadrightarrow Y, then X \twoheadrightarrow R - (X \cup Y)
    • Augmentation: If X \twoheadrightarrow Y and Z \subseteq W, then XW \twoheadrightarrow YZ
    • Transitive: If X \twoheadrightarrow Y and Y \twoheadrightarrow Z, then X \twoheadrightarrow Z \subseteq Y
    • Replication: If X \rightarrow Y, then X \twoheadrightarrow Y
    • Coalescence: If X \twoheadrightarrow  Y and \exist W s.t. W \cap Y = \empty , W \rightarrow Z, and Z \subseteq Y, then X \rightarrow Z

Definitions[edit]

full constraint
A constraint which expresses something about all attributes in a database. (In contrast to an embedded constraint.) That a multivalued dependency is a full constraint follows from its definition,as where it says something about the attributes R - \beta.
tuple-generating dependency
A dependency which explicitly requires certain tuples to be present in the relation.
trivial multivalued dependency 1
A multivalued dependency which involves all the attributes of a relation i.e.R = \alpha \cup \beta. A trivial multivalued dependency implies, for tuples t _1 and t _2, tuples t _3 and t _4 which are equal to t _1 and t _2.
trivial multivalued dependency 2
A multivalued dependency for which \beta \subseteq \alpha.

References[edit]

  1. ^ Silberschatz, Abraham; Korth, Sudarshan (2006). Database System Concepts (5th ed.). McGraw-Hill. p. 295. ISBN 0-07-124476-X. 

External links[edit]