# Multivalued dependency

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Multivalued_dependency
> Markdown URL: https://mediated.wiki/source/Multivalued_dependency.md
> Source: https://en.wikipedia.org/wiki/Multivalued_dependency
> Source revision: 1328865150
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Full constraint between two sets of attributes in a relation

In [database theory](/source/Database_theory), a **multivalued [dependency](/source/Dependency_theory_(database_theory))** is a full constraint between two sets of attributes in a [relation](/source/Relation_(database)).

In contrast to the [functional dependency](/source/Functional_dependency), the multivalued dependency requires that certain [tuples](/source/Tuple) be present in a relation. Therefore, a multivalued dependency is a special case of [tuple-generating dependency](/source/Tuple-generating_dependency). The multivalued dependency plays a role in the [4NF database normalization](/source/4NF).

A multivalued dependency is a special case of a [join dependency](/source/Join_dependency), with only two sets of values involved, i.e. it is a binary join dependency.

A multivalued dependency exists when there are at least three [attributes](/source/Attribute_(computing)) (like X,Y and Z) in a [relation](/source/Relation_(database)) and for a value of X there is a well defined set of values of Y and a well defined set of values of Z. However, the set of values of Y is independent of set Z and vice versa.

## Formal definition

The formal definition is as follows:[1]

Let R {\displaystyle R} be a [relation scheme](/source/Relation_scheme) and let α ⊆ R {\displaystyle \alpha \subseteq R} and β ⊆ R {\displaystyle \beta \subseteq R} be sets of attributes. The multivalued dependency α ↠ β {\displaystyle \alpha \twoheadrightarrow \beta } (" α {\displaystyle \alpha } multidetermines β {\displaystyle \beta } ") holds on R {\displaystyle R} if, for any legal relation r ( R ) {\displaystyle r(R)} and all pairs of tuples t 1 {\displaystyle t_{1}} and t 2 {\displaystyle t_{2}} in r {\displaystyle r} such that t 1 [ α ] = t 2 [ α ] {\displaystyle t_{1}[\alpha ]=t_{2}[\alpha ]} , there exist tuples t 3 {\displaystyle t_{3}} and t 4 {\displaystyle t_{4}} in r {\displaystyle r} such that:

t 1 [ α ] = t 2 [ α ] = t 3 [ α ] = t 4 [ α ] t 1 [ β ] = t 3 [ β ] t 2 [ β ] = t 4 [ β ] t 1 [ R − β ] = t 4 [ R − β ] t 2 [ R − β ] = t 3 [ R − β ] {\displaystyle {\begin{matrix}t_{1}[\alpha ]=t_{2}[\alpha ]=t_{3}[\alpha ]=t_{4}[\alpha ]\\t_{1}[\beta ]=t_{3}[\beta ]\\t_{2}[\beta ]=t_{4}[\beta ]\\t_{1}[R-\beta ]=t_{4}[R-\beta ]\\t_{2}[R-\beta ]=t_{3}[R-\beta ]\end{matrix}}}

Informally, if one denotes by ( x , y , z ) {\displaystyle (x,y,z)} the tuple having values for α , {\displaystyle \alpha ,} β , {\displaystyle \beta ,} R − α − β {\displaystyle R-\alpha -\beta } collectively equal to x , {\displaystyle x,} y , {\displaystyle y,} z {\displaystyle z} , then whenever the tuples ( a , b , c ) {\displaystyle (a,b,c)} and ( a , d , e ) {\displaystyle (a,d,e)} exist in r {\displaystyle r} , the tuples ( a , b , e ) {\displaystyle (a,b,e)} and ( a , d , c ) {\displaystyle (a,d,c)} should also exist in r {\displaystyle r} .

The multivalued dependency can be schematically depicted as shown below:

tuple α β R − α − β t 1 a 1 . . a n b 1 . . b m d 1 . . d k t 2 a 1 . . a n c 1 . . c m e 1 . . e k t 3 a 1 . . a n b 1 . . b m e 1 . . e k t 4 a 1 . . a n c 1 . . c m d 1 . . d k {\displaystyle {\begin{matrix}{\text{tuple}}&\alpha &\beta &R-\alpha -\beta \\t_{1}&a_{1}..a_{n}&b_{1}..b_{m}&d_{1}..d_{k}\\t_{2}&a_{1}..a_{n}&c_{1}..c_{m}&e_{1}..e_{k}\\t_{3}&a_{1}..a_{n}&b_{1}..b_{m}&e_{1}..e_{k}\\t_{4}&a_{1}..a_{n}&c_{1}..c_{m}&d_{1}..d_{k}\end{matrix}}}

## Example

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

University courses Course Book Lecturer AHA Silberschatz John D AHA Nederpelt John D AHA Silberschatz William M AHA Nederpelt William M 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} ↠ {\displaystyle \twoheadrightarrow } {book} and equivalently {course} ↠ {\displaystyle \twoheadrightarrow } {lecturer}. Databases with multivalued dependencies thus exhibit redundancy. In [database normalization](/source/Database_normalization), [fourth normal form](/source/Fourth_normal_form) requires that for every nontrivial multivalued dependency *X* ↠ {\displaystyle \twoheadrightarrow } *Y*, *X* is a [superkey](/source/Superkey). A multivalued dependency *X* ↠ {\displaystyle \twoheadrightarrow } *Y* is trivial if *Y* is a subset of *X*, or if X ∪ Y {\displaystyle X\cup Y} is the whole set of attributes of the relation.

## Properties

- If α ↠ β {\displaystyle \alpha \twoheadrightarrow \beta } , Then α ↠ R − β {\displaystyle \alpha \twoheadrightarrow R-\beta }

- If α ↠ β {\displaystyle \alpha \twoheadrightarrow \beta } and γ ⊆ δ {\displaystyle \gamma \subseteq \delta } , Then α δ ↠ β γ {\displaystyle \alpha \delta \twoheadrightarrow \beta \gamma }

- If α ↠ β {\displaystyle \alpha \twoheadrightarrow \beta } and β ↠ γ {\displaystyle \beta \twoheadrightarrow \gamma } , then α ↠ γ − β {\displaystyle \alpha \twoheadrightarrow \gamma -\beta }

The following also involve [functional dependencies](/source/Functional_dependency):

- If α → β {\displaystyle \alpha \rightarrow \beta } , then α ↠ β {\displaystyle \alpha \twoheadrightarrow \beta }

- If α ↠ β {\displaystyle \alpha \twoheadrightarrow \beta } and β → γ {\displaystyle \beta \rightarrow \gamma } , then α ↠ γ − β {\displaystyle \alpha \twoheadrightarrow \gamma -\beta }

The above rules are sound and complete.

- A decomposition of *R* into (*X*, *Y*) and (*X*, *R* − *Y*) is a [lossless-join decomposition](/source/Lossless-join_decomposition) if and only if *X* ↠ {\displaystyle \twoheadrightarrow } *Y* holds in *R*.

- Every **FD** ([functional dependency](/source/Functional_dependency)) is an **MVD** (multivalued dependency) because if X → {\displaystyle \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.

- **Closure** of a set of MVDs is the set of all MVDs that can be inferred using the following rules ([Armstrong's axioms](/source/Armstrong's_axioms)): - *Complementation*: If X ↠ {\displaystyle \twoheadrightarrow } Y, then X ↠ {\displaystyle \twoheadrightarrow } R - Y - *Augmentation*: If X ↠ {\displaystyle \twoheadrightarrow } Y and Z ⊆ {\displaystyle \subseteq } W, then XW ↠ {\displaystyle \twoheadrightarrow } YZ - *Transitivity*: If X ↠ {\displaystyle \twoheadrightarrow } Y and Y ↠ {\displaystyle \twoheadrightarrow } Z, then X ↠ {\displaystyle \twoheadrightarrow } Z - Y - *Replication*: If X → {\displaystyle \rightarrow } Y, then X ↠ {\displaystyle \twoheadrightarrow } Y - *Coalescence*: If X ↠ {\displaystyle \twoheadrightarrow } Y and ∃ {\displaystyle \exists } W s.t. W ∩ {\displaystyle \cap } Y = ∅ {\displaystyle \emptyset } , W → {\displaystyle \rightarrow } Z, and Z ⊆ {\displaystyle \subseteq } Y, then X → {\displaystyle \rightarrow } Z

## Definitions

**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 − β {\displaystyle R-\beta } .

**[Tuple-generating dependency](/source/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 = α ∪ β {\displaystyle R=\alpha \cup \beta } . A trivial multivalued dependency implies, for tuples t 1 {\displaystyle t_{1}} and t 2 {\displaystyle t_{2}} , tuples t 3 {\displaystyle t_{3}} and t 4 {\displaystyle t_{4}} which are equal to t 1 {\displaystyle t_{1}} and t 2 {\displaystyle t_{2}} .

**Trivial multivalued dependency 2**
- A multivalued dependency for which β ⊆ α {\displaystyle \beta \subseteq \alpha } .

## References

1. **[^](#cite_ref-1)** [Silberschatz, Abraham](/source/Abraham_Silberschatz); Korth, Sudarshan (2006). [*Database System Concepts*](https://archive.org/details/databasesystemco00silb_827) (5th ed.). [McGraw-Hill](/source/McGraw-Hill). p. [295](https://archive.org/details/databasesystemco00silb_827/page/n321). [ISBN](/source/ISBN_(identifier)) [0-07-124476-X](https://en.wikipedia.org/wiki/Special:BookSources/0-07-124476-X).

## External links

- [Multivalued dependencies and a new Normal form for Relational Databases](https://web.archive.org/web/20071129092334/http://www.almaden.ibm.com/cs/people/fagin/tods77.pdf) (PDF) - Ronald Fagin, IBM Research Lab

- [On the Structure of Armstrong Relations for Functional Dependencies](http://researcher.ibm.com/researcher/files/us-fagin/jacm84.pdf) (PDF) - CATRIEL BEERI (The Hebrew University), MARTIN DOWD (Rutgers University), RONALD FAGIN (IBM Research Laboratory) AND RICHARD STATMAN (Rutgers University)

- [On a problem of Fagin concerning multivalued dependencies in relational databases](https://web.archive.org/web/20131101111524/http://slink.foiks.org/Articles/TCS06-Fagin.pdf) (PDF) - Sven Hartmann, Massey University

---
Adapted from the Wikipedia article [Multivalued dependency](https://en.wikipedia.org/wiki/Multivalued_dependency) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Multivalued_dependency?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.