Multivalued dependency
Encyclopedia
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 tuple
s 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.
In more simple words the above condition can be expressed as follows: if we denote by
the tuple having values for 
collectively equal to 
correspondingly, then whenever the tuples 
and 
exist in 
, the tuples 
and 
should also exist in 
.
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}
{book} and equivalently {course} 
{lecturer}.
Databases with multivalued dependencies thus exhibit redundancy. In database normalization
, fourth normal form
requires that either every multivalued dependency X
Y is trivial or for every nontrivial multivalued dependency X 
Y, X is a superkey
.
The following also involve functional dependencies
:
The above rules are sound and complete.
.
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.
. A trivial multivalued dependency implies, for tuples 
and 
, tuples 
and 
which are equal to 
and 
.
trivial multivalued dependency 2: A multivalued dependency for which
.
Database theory
Database theory encapsulates a broad range of topics related to the study and research of the theoretical realm of databases and database management systems....
, multivalued dependency
Dependency theory (database theory)
Dependency theory is a subfield of database theory which studies implication and optimization problems related to logical constraints, commonly called dependencies, on databases....
is a full constraint between two sets of attributes in a relation
Relation (database)
In relational model:A relation value, which is assigned to a certain relation variable, is time-varying. By using a Data Definition Language , it is able to define relation variables.The following is an example of a heading which consists of three attributes....
.
In contrast to the functional dependency
Functional dependency
A functional dependency is a constraint between two sets of attributes in a relation from a database.Given a relation R, a set of attributes X in R is said to functionally determine another attribute Y, also in R, if, and only if, each X value is associated with precisely one Y value...
, the multivalued dependency requires that certain tuple
Tuple
In mathematics and computer science, a tuple is an ordered list of elements. In set theory, an n-tuple is a sequence of n elements, where n is a positive integer. There is also one 0-tuple, an empty sequence. An n-tuple is defined inductively using the construction of an ordered pair...
s 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.
Formal definition
The formal definition is given as follows.
Letbe a relation schema and let
and
(subsets). The multivalued dependency
(which can be read asmultidetermines
) holds on
if, in any legal relation
, for all pairs of tuples
and
in
such that
, there exist tuples
and
in
such that
In more simple words the above condition can be expressed as follows: if we denote by
the tuple having values for collectively equal to correspondingly, then whenever the tuples and exist in , the tuples and should also exist in .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:| 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}
{book} and equivalently {course} {lecturer}.Databases with multivalued dependencies thus exhibit redundancy. In database normalization
Database normalization
In the design of a relational database management system , the process of organizing data to minimize redundancy is called normalization. The goal of database normalization is to decompose relations with anomalies in order to produce smaller, well-structured relations...
, fourth normal form
Fourth normal form
Fourth normal form is a normal form used in database normalization. Introduced by Ronald Fagin in 1977, 4NF is the next level of normalization after Boyce–Codd normal form . Whereas the second, third, and Boyce–Codd normal forms are concerned with functional dependencies, 4NF is concerned with a...
requires that either every multivalued dependency X
Y is trivial or for every nontrivial multivalued dependency X Y, X is a superkeySuperkey
A superkey is defined in the relational model of database organization as a set of attributes of a relation variable for which it holds that in all relations assigned to that variable, there are no two distinct tuples that have the same values for the attributes in this set...
.
Interesting properties
- If
, Then 
- If
and 
, Then 
- If
and 
, then 
The following also involve functional dependencies
Functional dependency
A functional dependency is a constraint between two sets of attributes in a relation from a database.Given a relation R, a set of attributes X in R is said to functionally determine another attribute Y, also in R, if, and only if, each X value is associated with precisely one Y value...
:
- If
, then 
- If
and 
, then 
The above rules are sound and complete.
- A decomposition of R into (X, Y) and (X, R − Y) is a lossless-join decompositionLossless-Join DecompositionCan also be called Nonadditive.If you decompose a relation R into relations R_1 and R_2 you will guarantee a Lossless-Join if R_1⋈R_2 = R.Let R be a relation schema.Let F be a set of functional dependencies on R.Let R_1 and R_2 form a decomposition of R....
if and only if X
Y holds in R.
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.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.
. A trivial multivalued dependency implies, for tuples and , tuples and which are equal to and .trivial multivalued dependency 2: A multivalued dependency for which
.External links
- Multivalued dependencies and a new Normal form for Relational Databases (PDF) - Ronald Fagin, IBM Research Lab