Multivalued Dependency

A multivalued dependency MVD exists in a relation when one attribute in a table uniquely determines another attribute, independently of all other attributes.

Definition

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

Formally, in a relation R(X, Y, Z), we say X →→ Y (X multidetermines Y) if:

For every pair of tuples t1 and t2 in R such that t1[X] = t2[X],
there exist tuples t3 and t4 in R 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]

In simpler terms: X →→ Y means the set of Y values associated with a given X value is independent of the Z values.

Intuitive Understanding

Teacher	Subject	Hobby
Alice	DBMS	Painting
Alice	DBMS	Chess
Alice	OS	Painting

Every combination of Subject and Hobby for a given Teacher MUST appear — this causes massive redundancy.

Trivial vs. Non-Trivial MVD

Trivial MVD

X →→ Y is trivial if:

Y ⊆ X, OR
X ∪ Y = all attributes of R

Trivial MVDs are always satisfied and do not cause problems.

Non-Trivial MVD

X →→ Y is non-trivial if Y is neither a subset of X nor does X ∪ Y cover all attributes. These cause redundancy and 4NF violations.

MVD vs. FD

Functional Dependency (FD)

X → Y means: for a given X, there is EXACTLY ONE Y value.

Example: StudentID → StudentName

Multivalued Dependency (MVD)

X →→ Y means: for a given X, there is a SET OF Y values,

independent of other attributes.

Example: Teacher →→ Subject

Every FD is also an MVD (but not vice versa)

If X → Y, then X →→ Y (trivially, since the set has one element)

Why MVDs Cause Problems

Code exampleWoHoTech

  TeacherSubject(Teacher, Subject, Hobby):

  Alice teaches DBMS and OS.
  Alice's hobbies are Painting and Chess.
  Adding a new subject (e.g., Networks) requires adding 2 new rows:
    (Alice, Networks, Painting)
    (Alice, Networks, Chess)
  ← Cannot add subject without duplicating ALL hobby combinations

  DELETE anomaly: Removing (Alice, DBMS, Painting) might accidentally
  remove data if not all combinations are present.

Complementation Rule

If X →→ Y in R(X, Y, Z), then X →→ Z also holds.

MVDs always come in pairs — if X independently determines Y, it also independently determines the rest (Z).

Teacher →→ Subject ⟹ Teacher →→ Hobby (in TeacherSubject(Teacher, Subject, Hobby))

Rules for MVDs (Extended Armstrong's Axioms)

Complementation: If X →→ Y, then X →→ Z (where Z = R − X − Y)
Augmentation: If X →→ Y and W ⊇ Z, then WX →→ YZ
Transitivity: If X →→ Y and Y →→ Z, then X →→ Z − Y
Replication (FD to MVD): If X → Y, then X →→ Y
Coalescence: If X →→ Y, Z ⊆ Y, W ∩ Y = ∅, W → Z, then X → Z

Decomposing to Remove MVDs (→ 4NF)

Before (violates 4NF due to non-trivial MVD)

TeacherSubject(Teacher, Subject, Hobby)

Teacher →→ Subject

Teacher →→ Hobby

Decompose into two relations

TeacherSubjects(Teacher, Subject) ← captures Teacher →→ Subject

TeacherHobbies(Teacher, Hobby) ← captures Teacher →→ Hobby

Now

+----------+-----------+ +----------+-----------+

+----------+-----------+ +----------+-----------+

+----------+-----------+ +----------+-----------+

No redundancy ✓

Definition

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

Formally, in a relation R(X, Y, Z), we say X →→ Y (X multidetermines Y) if:

For every pair of tuples t1 and t2 in R such that t1[X] = t2[X],
there exist tuples t3 and t4 in R 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]

In simpler terms: X →→ Y means the set of Y values associated with a given X value is independent of the Z values.

Intuitive Understanding

Teacher	Subject	Hobby
Alice	DBMS	Painting
Alice	DBMS	Chess
Alice	OS	Painting

Every combination of Subject and Hobby for a given Teacher MUST appear — this causes massive redundancy.

Trivial vs. Non-Trivial MVD

Trivial MVD

X →→ Y is trivial if:

Y ⊆ X, OR
X ∪ Y = all attributes of R

Trivial MVDs are always satisfied and do not cause problems.

Non-Trivial MVD

X →→ Y is non-trivial if Y is neither a subset of X nor does X ∪ Y cover all attributes. These cause redundancy and 4NF violations.

MVD vs. FD

Functional Dependency (FD)

X → Y means: for a given X, there is EXACTLY ONE Y value.

Example: StudentID → StudentName

Multivalued Dependency (MVD)

X →→ Y means: for a given X, there is a SET OF Y values,

independent of other attributes.

Example: Teacher →→ Subject

Every FD is also an MVD (but not vice versa)

If X → Y, then X →→ Y (trivially, since the set has one element)

Why MVDs Cause Problems

Code exampleWoHoTech

  TeacherSubject(Teacher, Subject, Hobby):

  Alice teaches DBMS and OS.
  Alice's hobbies are Painting and Chess.
  Adding a new subject (e.g., Networks) requires adding 2 new rows:
    (Alice, Networks, Painting)
    (Alice, Networks, Chess)
  ← Cannot add subject without duplicating ALL hobby combinations

  DELETE anomaly: Removing (Alice, DBMS, Painting) might accidentally
  remove data if not all combinations are present.

Complementation Rule

If X →→ Y in R(X, Y, Z), then X →→ Z also holds.

MVDs always come in pairs — if X independently determines Y, it also independently determines the rest (Z).

Teacher →→ Subject ⟹ Teacher →→ Hobby (in TeacherSubject(Teacher, Subject, Hobby))

Rules for MVDs (Extended Armstrong's Axioms)

Complementation: If X →→ Y, then X →→ Z (where Z = R − X − Y)
Augmentation: If X →→ Y and W ⊇ Z, then WX →→ YZ
Transitivity: If X →→ Y and Y →→ Z, then X →→ Z − Y
Replication (FD to MVD): If X → Y, then X →→ Y
Coalescence: If X →→ Y, Z ⊆ Y, W ∩ Y = ∅, W → Z, then X → Z

Decomposing to Remove MVDs (→ 4NF)

Before (violates 4NF due to non-trivial MVD)

TeacherSubject(Teacher, Subject, Hobby)

Teacher →→ Subject

Teacher →→ Hobby

Decompose into two relations

TeacherSubjects(Teacher, Subject) ← captures Teacher →→ Subject

TeacherHobbies(Teacher, Hobby) ← captures Teacher →→ Hobby

Now

+----------+-----------+ +----------+-----------+

+----------+-----------+ +----------+-----------+

+----------+-----------+ +----------+-----------+

No redundancy ✓

Multivalued Dependency

Definition

Intuitive Understanding

Trivial vs. Non-Trivial MVD

Trivial MVD

Non-Trivial MVD

MVD vs. FD

Functional Dependency (FD)

Multivalued Dependency (MVD)

Every FD is also an MVD (but not vice versa)

Why MVDs Cause Problems

Complementation Rule

Rules for MVDs (Extended Armstrong's Axioms)

Decomposing to Remove MVDs (→ 4NF)

Before (violates 4NF due to non-trivial MVD)

Decompose into two relations

Now

Continue learning this concept

Multivalued Dependency

Definition

Intuitive Understanding

Trivial vs. Non-Trivial MVD

Trivial MVD

Non-Trivial MVD

MVD vs. FD

Functional Dependency (FD)

Multivalued Dependency (MVD)

Every FD is also an MVD (but not vice versa)

Why MVDs Cause Problems

Complementation Rule

Rules for MVDs (Extended Armstrong's Axioms)

Decomposing to Remove MVDs (→ 4NF)

Before (violates 4NF due to non-trivial MVD)

Decompose into two relations

Now

Continue learning this concept