Multivalued dependency

From Wikipedia, the free encyclopedia

A 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 also referred to as a tuple-generating dependency. The multivalued dependency plays a role in the 4NF database normalization.

1 Formal definition
2 Example
3 Interesting properties
4 Definitions
5 References
6 External links

[edit] Formal definition

Let $R$ be a relation schema and let $\alpha \subseteq R$ and $\beta \subseteq R$ . The multivalued dependency
$α$ $β$
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 [α] = t 2 [α]$ , there exist tuples $t 3$ and $t 4$ in $r$ such that
$t 1 [α] = t 2 [α] = t 3 [α] = t 4 [α]$
$t 3 [β] = t 1 [β]$
$t 3 [R - β] = t 2 [R - β]$
$t 4 [β] = t 2 [β]$
$t 4 [R - β] = t 1 [R - β]$ ^[1]

[edit] Example

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

Teaching database
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

*Teaching database*
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 in this relation: {course} {book} and equivalently {course} {lecturer}.
Databases with multivalued dependencies thus exhibit redundancy. In database normalization, fourth normal form requires that databases have no multivalued dependencies.

[edit] Interesting properties

If $α$ $β$ , Then $α$ $R - β$
If $α$ $β$ and $\gamma \subseteq \delta$ , Then $αδ$ $βγ$
If $α$ $β$ and If $β$ $γ$ , then $α$ $γ - β$

The following also involve functional dependencies:

If $\alpha \rightarrow \beta$ , then $α$ $β$
If $α$ $β$ and $\beta \rightarrow \gamma$ , then $\alpha \rightarrow \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 if and only if X Y holds in R.

[edit] Definitions

full constraint: A constraint which expresses something about all attributes in a database. (In contrary to an embedded constraint.) That a multivalued dependency is a full constraint follows from its definition, where it says something about the attributes $R - β$ .
tuple-generating dependency: A dependency which explicitly requires certain tuples to be present in the relation.
trivial multivalued dependency: 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$ .