Multivalued Dependency

Definition

A multivalued dependency (MVD) exists in a relation when one attribute uniquely determines a set of values for another attribute, independently of all other attributes in the relation.

Formally, in a relation R(X, Y, Z), we say X →→ Y (X multidetermines Y) if: for every pair of tuples t1 and t2 that agree on X, there must exist tuples t3 and t4 such that:

• t3[X] = t4[X] = t1[X] = t2[X]
• t3[Y] = t1[Y] and t3[Z] = t2[Z]
• t4[Y] = t2[Y] and t4[Z] = t1[Z]

Intuitive meaning: X →→ Y means the set of Y values associated with a given X value is completely independent of the Z values (where Z = R - X - Y). Every combination of Y-values and Z-values must appear for each X value.

MVD vs. FD — Key Differences

Important: Every FD is also an MVD (X→Y implies X→→Y), but not vice versa.

Trivial vs. Non-Trivial MVD

Trivial MVD

An MVD X →→ Y is trivial if:

• Y ⊆ X (Y is a subset of X), OR
• X ∪ Y = all attributes of R (Y covers everything else)

Trivial MVDs always hold and do not cause redundancy.

Non-Trivial MVD

If neither condition above holds, the MVD is non-trivial and may cause 4NF violations.

Complementation Rule

If X →→ Y holds in R(X, Y, Z), then X →→ Z also holds (where Z = R - X - Y). MVDs always come in pairs:

Detecting MVDs in Practice

MVDs are detected from business semantics, not from data inspection:

Test: Ask yourself — "If I add a new value for one attribute, must I replicate rows for all values of another attribute?" If yes, you have an MVD.

Problems Caused by MVDs

Insertion Anomaly

Deletion Anomaly

Update Anomaly

4NF Decomposition to Eliminate MVDs

When a non-trivial MVD X →→ Y exists and X is not a superkey, decompose:

MVDs and Lossless Join

The decomposition R(X, Y, Z) into R1(X, Y) and R2(X, Z) is lossless if and only if X →→ Y (or equivalently X →→ Z) holds. This is the Fagin's theorem:

This guarantees that the join of the two decomposed tables produces exactly the original data — no spurious tuples are generated.

Inference Rules for MVDs

Summary

• MVDs capture independence between sets of values associated with the same key
• They cause redundancy by forcing all combinations to appear
• Non-trivial MVDs where the determinant is not a superkey violate 4NF
• Decomposition into separate tables for each independent fact eliminates the redundancy
• Every FD is an MVD, but MVDs are strictly more general
• Understanding MVDs is essential for achieving 4NF and designing minimal-redundancy schemas