Multivalued Dependency

Multivalued Dependencies is a generalization of Functional Dependencies Concept that significantly helps to design and optimize a Relation Database Structure. Let R(X1...,Xm, Y1...,Yn, Z1...,Zr) is a relation with m + n + r column names. For notational convenience, we can define X for {X1...,Xm}; Y for {Y1...,Yn} and Z for {Z1...,Zn} and the relation is R(X, Y, Z).

Multivalued Dependency is a statement of the form X ®® Y, where X and Y are sets of attributes. Let Z be the set of all the attributes in U (union) that are neither in X nor in Y. The multivalued dependency X ®® Y holds in R if for all r1 and r2 in R, if r1[X] = r2[X], then there are r3 and r4 in R such that r3[X] = r1[X], r3[Y] = r1[Y], and r3[Z] = r2[Z]; and r4[X] = r1[X], r4[y] = r2[Y], and r4[Z] = r1[Z].

Let X ®® Y holds in R if and only if X ®® Y - X holds in R. When the sets X, Y, and Z form a partition of U (union), then it is convenient to write a tuple r of R like (x, y, z), where x, y, and z denote the projections of r onto X, Y, and Z. The alphabet (A, B, C, D,...) is denote single attributes and (...,X, Y, Z) to denote sets of attributes. XY is a union of X and Y attributes. A string of attributes A1, A2, ... An is denotes the set {A1, A2, ..., An}.

The multivalued dependency X ®® Y is said to hold for R(X, Y, Z) if Yxz depends only on x; that is, if Yxz = Yxz' for each x, z, z' such that Yxz and Yxz' are nonempty. Define Yxz to be {y : (x, y, z) ÎR}, Yxz is nonempty IFF x and z appear together in a tuple of R. Multivalued Dependencies provide a necessary and sufficient condition for a relation to be decomposable into two of its projections without loss of information.

An instance, we can decompose R(X, Y, Z) into R1(X, Y) and R2(X, Z) is the set of tuples (x, y, z) where (x, y) is a tuple of R1 and where (x, z) is a tuple of R2. In database, a Project_Employee_Task Entity is defined with {Project_Name, Employee_Name, Task_Name) that can decompose into Project_Employee Entity (Project_Name, Employee_Name} and Project_Task Entity {Project_Name, Task_Name}.

If X and Y are disjoint and if the functional dependency X ® Y holds for a relation R then the multivalued dependency X ®® Y also holds for R. X ®® Y holds for the relation R(X, Y, Z) IFF R is the join of its projections R1(X, Y) and R2(X, Z) based on multivalued dependency theorem.

R(X, Y, Z) is the join of its projections R1(X, Y) and R2(X, Z) IFF the following condition holds, whenever (x, y, z) and (x, y', z') are tuples of R, then (x, y', z) and (x, y, z'). Since the right hand side of the "IFF" in theorem is symmetric in the role of Y and Z, the next proposition is continue immediately that X ®® Y holds for the relation R(X, Y, Z) IFF X ®® Z holds.