Multivalued Dependencies

By now, you've mastered functional dependencies—the backbone of normalization theory through BCNF. You understand that a functional dependency X → Y means that X values uniquely determine Y values. But what happens when you encounter relationships that FDs simply cannot express?

Consider an employee who speaks multiple languages and has multiple skills. There's no functional dependency between languages and skills—an employee's language capabilities don't determine their skills, and vice versa. Yet these two sets of attributes are independently associated with the employee. If you store this data naively, you'll encounter redundancy that BCNF cannot eliminate.

This is precisely where Multivalued Dependencies (MVDs) enter the picture.

Before diving into MVDs, let's crystallize exactly where functional dependencies fall short. This understanding is crucial because MVDs exist specifically to address a class of redundancy that FDs cannot capture.

Functional dependencies capture determinacy:

When we say X → Y, we assert that given any X value, there is exactly one corresponding Y value. This is a powerful constraint that eliminates certain types of redundancy—if Y is determined by X, storing Y with every occurrence of X would be redundant (hence normalization).

But consider this scenario:

Observe the structure carefully:

Alice has skills {Java, Python} and speaks languages {English, Spanish}. To represent all possible combinations, we need four tuples for Alice. This is the Cartesian product of her skills and languages.

Now ask: What functional dependencies exist here?

• EmpID → EmpName (trivially, an employee has one name)
• But EmpID does NOT determine Skill (Alice has multiple skills)
• And EmpID does NOT determine Language (Alice speaks multiple languages)
• Skill does NOT determine Language (knowing Java doesn't imply speaking English)
• Language does NOT determine Skill (speaking Spanish doesn't imply knowing Python)

There are essentially no non-trivial functional dependencies among {EmpID, Skill, Language}.

Yet there is obvious redundancy! Alice's name is repeated four times. More subtly, the pairing of "Java" with "English" appears, but this pairing has no semantic meaning—Alice knows Java independently of speaking English.

The core insight:

Functional dependencies capture one-to-one or many-to-one relationships. But the relationship between an employee and their skills is one-to-many, and so is the relationship between an employee and their languages. These two one-to-many relationships are independent of each other.

We need a new type of constraint to express: "The set of skills for an employee is independent of the set of languages for that employee."

This constraint is called a Multivalued Dependency.

Let's build intuition before presenting the formal definition.

Informal Statement:

A multivalued dependency X →→ Y (read as "X multi-determines Y" or "Y is multidependent on X") holds in a relation R if, for any given value of X, the set of Y values is determined independently of the values of the remaining attributes R - X - Y.

In our example:

EmpID →→ Skill means: For any given employee, the set of skills is determined by the employee alone, independent of what languages they speak.

EmpID →→ Language means: For any given employee, the set of languages is determined by the employee alone, independent of what skills they have.

Think of it this way:

If you want to know Alice's skills, you only need to know that it's Alice. Her languages are irrelevant to determining her skills—the skills form an independent set associated with Alice.

The Cartesian Product Symptom Explained:

If EmpID →→ Skill holds in our relation, and an employee E001 has skills {Java, Python} and languages {English, Spanish}, then for E001, every skill must pair with every language. The tuples for E001 form the Cartesian product:

{Java, Python} × {English, Spanish} = {(Java, English), (Java, Spanish), (Python, English), (Python, Spanish)}

This is the "signature" of MVDs in data—and exactly the redundancy we want to eliminate.

Now we present the rigorous definition that underlies all MVD theory.

Formal Definition:

Let R be a relation schema with attribute set U. Let X, Y ⊆ U. The multivalued dependency X →→ Y holds in R if and only if:

For any relation instance r of R, whenever two tuples t₁ and t₂ exist in r such that t₁[X] = t₂[X], then there also exist tuples t₃ and t₄ in r such that:

1. t₃[X] = t₄[X] = t₁[X] = t₂[X]
2. t₃[Y] = t₁[Y] and t₃[U - X - Y] = t₂[U - X - Y]
3. t₄[Y] = t₂[Y] and t₄[U - X - Y] = t₁[U - X - Y]

Let Z = U - X - Y (the remaining attributes).

In essence: If we have two tuples that agree on X, we can "swap" their Y and Z values to create two more tuples that must also be in the relation.

Visualizing the Formal Definition:

Consider relation R(X, Y, Z) where X →→ Y holds. Let's say we have these tuples:

Since t₁[X] = t₂[X] = x, the MVD X →→ Y requires that these tuples also exist:

All four tuples must exist. This creates the Cartesian product structure: for each X value, every Y value combines with every Z value.

Applying to Our Example:

With R(EmpID, Skill, Language):

• X = {EmpID}
• Y = {Skill}
• Z = {Language}

If we have:

• t₁ = (E001, Java, English)
• t₂ = (E001, Python, Spanish)

Then EmpID →→ Skill requires:

• t₃ = (E001, Java, Spanish) — Java from t₁, Spanish from t₂
• t₄ = (E001, Python, English) — Python from t₂, English from t₁

And indeed, these tuples exist in our example table, confirming the MVD holds.

Understanding the relationship between MVDs and FDs is crucial for mastering normalization theory. Let's examine this relationship rigorously.

Theorem: Every FD is an MVD

If X → Y holds in relation R, then X →→ Y also holds in R.

Proof:

Assume X → Y holds. Consider any two tuples t₁, t₂ with t₁[X] = t₂[X].

By the functional dependency, t₁[Y] = t₂[Y] (they must have the same Y value).

Now construct t₃ with:

• t₃[X] = t₁[X]
• t₃[Y] = t₁[Y]
• t₃[Z] = t₂[Z] (where Z = U - X - Y)

But since t₁[Y] = t₂[Y], we have t₃[Y] = t₂[Y] as well.

So t₃ = (t₁[X], t₁[Y], t₂[Z]) = (t₂[X], t₂[Y], t₂[Z]) = t₂!

Similarly, t₄ = t₁.

The required tuples already exist (they're just t₁ and t₂ themselves), so the MVD holds. ∎

Example Where MVD Holds But FD Does Not:

In our EmpID →→ Skill example:

• Employee E001 has skills {Java, Python}
• Therefore E001 does NOT functionally determine Skill (there's no single skill value)
• But E001 →→ Skill holds because the set of skills is independent of the set of languages

The MVD expresses something fundamentally different from an FD—it's not about unique determination, but about independent association.

How do you identify when a multivalued dependency holds in a given dataset? Let's develop systematic techniques.

Method 1: The Cartesian Product Test

For each distinct X value, examine the sets of Y values and Z values:

• Collect all distinct Y values associated with that X
• Collect all distinct Z values associated with that X
• Count the tuples for that X value

If the count equals |Y values| × |Z values| for every X value, and all combinations appear, the MVD likely holds.

Method 2: The Missing Tuple Check

Apply the formal MVD definition directly:

1. Find pairs of tuples that agree on X
2. For each such pair, compute the required "swapped" tuples
3. Verify these tuples exist in the relation

If any required tuple is missing, the MVD does NOT hold.

Method 3: Semantic Analysis

Often the most reliable method is to reason about the real-world semantics:

"Are the sets of Y values and Z values for a given X truly independent?"

In our employee example:

• An employee's skills are independent of their languages
• Learning a new language doesn't affect their skills
• Learning a new skill doesn't affect their languages

This semantic independence is the essence of MVDs. If you can articulate why Y and Z vary independently given X, you've identified an MVD.

MVDs aren't just theoretical constructs—they emerge naturally in many real-world data modeling scenarios. Understanding these patterns helps you recognize MVDs in your own designs.

Anti-Pattern: Forcing Non-Independent Attributes Together

A common database design mistake is creating "universal" tables that combine multiple independent multi-valued facts:

BadDesign(EmpID, EmpName, Skill, Language, Certification, Project)

If skills, languages, certifications, and projects are all independent of each other (for a given employee), you have FOUR MVDs:

• EmpID →→ Skill
• EmpID →→ Language
• EmpID →→ Certification
• EmpID →→ Project

The result? For an employee with 3 skills, 2 languages, 4 certifications, and 5 projects, you need 3 × 2 × 4 × 5 = 120 tuples to represent data that semantically requires only 3 + 2 + 4 + 5 = 14 facts.

This is catastrophic redundancy that MVD theory helps us understand and eliminate.

Before we explore MVD axioms in detail (in a later page), let's establish some fundamental properties that distinguish MVDs from FDs.

Property 1: Complementation Rule

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

Interpretation: If Y is independent of the rest (given X), then the rest is independent of Y (given X). Independence is symmetric.

Example: If EmpID →→ Skill holds in R(EmpID, Skill, Language), then EmpID →→ Language automatically holds.

This is not true for FDs: X → Y does NOT imply X → (U - X - Y).

Property 2: MVD in Binary Relations

In a relation with only two attributes R(X, Y), every MVD X →→ Y is trivially satisfied.

Reason: There are no other attributes Z to be independent of.

Property 3: Context Dependence

MVDs are highly context-dependent—they depend on the total set of attributes in the relation. An MVD that holds in R(A, B, C) might not hold if we add attribute D.

Example: EmpID →→ Skill holds in R(EmpID, Skill, Language). But in an expanded relation R(EmpID, Skill, Language, SkillLevel), if SkillLevel is functionally dependent on (EmpID, Skill), the MVD structure changes.

Property 4: Embedded MVDs

We often speak of MVDs holding "embedded" in a subset of attributes. Formally, X →→ Y[R] means the MVD holds when considering only the attributes of schema R. This notation is important when discussing projections.

We've established the foundational understanding of multivalued dependencies. Let's consolidate the key concepts:

What's Next:

Now that you understand what MVDs are and why they matter, the next page explores the notation system for MVDs in depth. We'll examine the X →→ Y notation, discuss conventions for specifying MVDs, and understand how MVDs are written in formal database literature.