DBMS Notes
A multivalued dependency (MVD) exists in a relation when one attribute uniquely determines a set of values for another attribute, independently of all other...
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
| Aspect | Functional Dependency (X→Y) | Multivalued Dependency (X→→Y) |
|---|---|---|
| Determines | Exactly one Y value per X | A SET of Y values per X |
| Independence | Not about independence | Y values independent of Z values |
| Redundancy type | Same value repeated | All combinations forced |
| Normal form | BCNF addresses FDs | 4NF addresses MVDs |
| Notation | X → Y (single arrow) | X →→ Y (double arrow) |
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:
| Scenario | MVD |
|---|---|
| Employee has independent skills and certifications | EmpID →→ Skill, EmpID →→ Certification |
| Course has multiple textbooks and multiple TAs | CourseID →→ Textbook, CourseID →→ TA |
| Product available in multiple colors and sizes | ProductID →→ Color, ProductID →→ Size |
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:
| Original | TeacherInfo(Teacher, Subject, Hobby) |
| MVD | Teacher -->> Subject (Teacher is not a superkey) |
| Adding "Networks" for Alice | ONE insert into TeacherSubject |
| Adding "Swimming" for Alice | ONE insert into TeacherHobby |
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
| Rule | Statement |
|---|---|
| Complementation | If X →→ Y then X →→ (R - X - Y) |
| Augmentation | If X →→ Y and W ⊇ Z, then XW →→ YZ |
| Transitivity | If X →→ Y and Y →→ Z, then X →→ (Z - Y) |
| Replication | If X → Y then X →→ Y (every FD implies MVD) |
| Coalescence | If X →→ Y and Z ⊆ Y and W ∩ Y = ∅ and W → Z, then X → Z |
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
Continue the lesson path