Multivalued Dependencies - Learning Module

Loading content...

0/241

MVD Axioms

Reasoning About Multivalued Dependencies

Just as Armstrong's axioms provide a sound and complete basis for reasoning about functional dependencies, there exists an axiomatic system for multivalued dependencies. However, the MVD axiom system is more complex because it must handle:

MVDs alone — Inference rules for deriving new MVDs from existing MVDs
FDs alone — The familiar Armstrong's axioms still apply
MVD-FD interactions — Rules that derive MVDs from FDs and vice versa

Mastering these axioms enables you to compute the complete set of dependencies implied by a given set, which is essential for normalization and schema design.

What You Will Learn

By the end of this page, you will understand the complete axiomatic system for MVDs, including the complementation, augmentation, and transitivity rules specific to MVDs. You'll also master the critical interaction rules between FDs and MVDs, and understand soundness and completeness of the extended axiom system.

The Need for MVD Axioms

Why Do We Need Axioms for MVDs?

When designing databases, we start with a set of known dependencies (based on business rules, domain knowledge, etc.). But this initial set may logically imply additional dependencies that aren't immediately obvious.

Example Problem:

Given:

R(A, B, C, D, E)
A →→ BC (employees' skills and departments are independent)
C → D (each skill requires a specific tool)

Question: Does A →→ B hold? Does A →→ D hold?

To answer such questions systematically, we need inference rules that allow us to derive new dependencies from given ones.

The Closure Problem:

Given a set of FDs and MVDs, the closure (or cover) is the set of ALL dependencies logically implied. Computing this closure requires a complete set of axioms.

Historical Context

The axiom system for MVDs was developed primarily by Beeri, Fagin, and Howard in the late 1970s. They extended Armstrong's axioms to handle multivalued dependencies and proved the resulting system is sound and complete—meaning it can derive exactly the dependencies that are logically implied, no more and no less.

Core MVD Axioms

The following axioms govern inference for multivalued dependencies alone (not involving FDs):

Axiom M1: MVD Complementation

If X →→ Y, then X →→ (R - X - Y)

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

Example: In R(A, B, C, D), if A →→ BC holds, then A →→ D also holds.

Axiom M2: MVD Augmentation

If X →→ Y and W ⊇ Z, then XW →→ YZ

More specifically: If X →→ Y holds, then for any W, XW →→ Y also holds.

Interpretation: Adding attributes to the determinant preserves the MVD.

Example: If A →→ B holds, then AC →→ B also holds.

Axiom M3: MVD Transitivity

If X →→ Y and Y →→ Z, then X →→ (Z - Y)

Interpretation: MVD transitivity works differently from FD transitivity. We derive the "difference" Z - Y, not just Z.

Example: If A →→ B and B →→ C, then A →→ (C - B). If B and C are disjoint, then A →→ C.

Core MVD Axioms Summary
Axiom	Name	Rule	Intuition
M1	Complementation	X →→ Y ⟹ X →→ (R-X-Y)	Independence is symmetric
M2	Augmentation	X →→ Y ⟹ XW →→ Y	Adding LHS preserves MVD
M3	Transitivity	X →→ Y, Y →→ Z ⟹ X →→ (Z-Y)	Chain rule with difference

MVD Transitivity Is Different!

Unlike FD transitivity (X → Y, Y → Z ⟹ X → Z), MVD transitivity produces (Z - Y), not Z directly. This is a common source of errors. The subtraction accounts for the set-based nature of MVDs.

FD-MVD Interaction Rules

The most important rules are those that connect functional dependencies with multivalued dependencies:

Rule I1: FD Implies MVD (Replication Rule)

If X → Y, then X →→ Y

Interpretation: Every functional dependency is also a multivalued dependency. FDs are a special case of MVDs.

Proof Sketch: If X → Y, then for each X value there's exactly one Y value. The "set" of Y values for each X has size 1, trivially forming a Cartesian product with Z values.

Rule I2: MVD Coalescence

If X →→ Y and there exists W such that:
  (a) W ∩ Y = ∅ (W and Y are disjoint)
  (b) W → Z
  (c) Z ⊆ Y
Then X → Z

Interpretation: Under specific conditions, an MVD can "collapse" into an FD. This happens when a portion of Y is functionally determined by attributes outside Y.

This rule is more subtle and applies in special circumstances.

Applying FD Implies MVDFrom FD to MVD conversion

Input

Given: R(EmpID, Name, DeptID, Skill)
FD: EmpID → Name (each employee has one name)

Apply Rule I1:
EmpID → Name implies EmpID →→ Name

Output

Result: EmpID →→ Name

This means the employee's name is "independent" of 
other attributes (DeptID, Skill) given EmpID.

But this is a special independence: there's only ONE 
name value per EmpID, so the "Cartesian product" with 
other attributes is trivially formed.

Rule I3: MVD Union

If X →→ Y and X →→ Z, then X →→ YZ

Interpretation: If Y and Z are both independent of the rest given X, then their union is also independent of the rest.

Rule I4: MVD Decomposition (Intersection Rule)

If X →→ Y and X →→ Z, then:
  X →→ (Y ∩ Z)
  X →→ (Y - Z)
  X →→ (Z - Y)

Interpretation: From two MVDs with the same LHS, we can derive MVDs for intersection and differences.

These derived rules combine basic axioms and are useful shortcuts.

The Complete Axiom System

Combining Armstrong's axioms for FDs with the MVD axioms gives us the complete system:

Armstrong's Axioms (for FDs):

Reflexivity: If Y ⊆ X, then X → Y
Augmentation: If X → Y, then XZ → YZ
Transitivity: If X → Y and Y → Z, then X → Z

MVD Axioms:

Complementation: If X →→ Y, then X →→ (R - X - Y)
Augmentation: If X →→ Y, then XZ →→ Y
Transitivity: If X →→ Y and Y →→ Z, then X →→ (Z - Y)

Interaction Axiom:

Replication: If X → Y, then X →→ Y

Additional Derived Rules (Coalescence):

If X →→ Y, Z ⊆ Y, W ∩ Y = ∅, and W → Z, then X → Z

Sound and Complete

This axiom system is SOUND (every derivable dependency is valid) and COMPLETE (every valid dependency can be derived). This was proven by Beeri, Fagin, and Howard. It means these axioms capture ALL the logical relationships between FDs and MVDs.

Complete Axiom System Reference
	Name	Type	Rule
A1	Reflexivity	FD	Y ⊆ X ⟹ X → Y
A2	Augmentation	FD	X → Y ⟹ XZ → YZ
A3	Transitivity	FD	X → Y, Y → Z ⟹ X → Z
M1	Complementation	MVD	X →→ Y ⟹ X →→ (R-X-Y)
M2	Augmentation	MVD	X →→ Y ⟹ XZ →→ Y
M3	Transitivity	MVD	X →→ Y, Y →→ Z ⟹ X →→ (Z-Y)
I1	Replication	FD→MVD	X → Y ⟹ X →→ Y
I2	Coalescence	MVD→FD	(conditions) ⟹ X → Z

Applying MVD Axioms: Worked Examples

Let's work through examples to see the axioms in action.

Example 1: Using Complementation

Complementation Example
Relation: R(A, B, C, D)
Given: A →→ B
 
Apply Complementation (M1):
  R - A - B = {C, D}
  Therefore: A →→ CD
 
Both MVDs are equivalent - stating one implies the other.

Example 2: Using MVD Transitivity

MVD Transitivity Example
Relation: R(A, B, C, D, E)
Given: 
  A →→ BC  (A multi-determines BC)
  BC →→ D (BC multi-determines D)
 
Apply MVD Transitivity (M3):
  X = A, Y = BC, Z = D
  X →→ (Z - Y) = A →→ (D - BC)
  
Since D and BC are disjoint (D - BC = D):
  Result: A →→ D
 
Verification: Given A, the set of D values is 
independent of the remaining attributes (B, C, E).

Example 3: Using Replication with Other Rules

Combined FD and MVD Derivation
Relation: R(A, B, C, D, E)
Given:
  A → B        (FD)
  A →→ CD      (MVD)
 
Step 1: Apply Replication (I1) to A → B:
  A →→ B
 
Step 2: We now have:
  A →→ B
  A →→ CD
 
Step 3: Apply MVD Union (derived rule):
  A →→ BCD
 
Step 4: Apply Complementation to A →→ BCD:
  A →→ (R - A - BCD) = A →→ E
 
Result: From the original dependencies, we derived A →→ E

Derivation Strategies

When deriving new dependencies: (1) Convert FDs to MVDs using Replication when helpful, (2) Use Complementation to explore 'the other side', (3) Apply Transitivity carefully, remembering Z - Y, (4) Consider Union and Decomposition for combining/splitting MVDs.

Computing MVD Closure

The closure of a set of dependencies D, written D⁺, is the set of all FDs and MVDs that can be derived from D using the axiom system.

Dependency Basis:

For attribute set X, the dependency basis of X with respect to D, written DEP(X), is defined as:

DEP(X) = {Y₁, Y₂, ..., Yₖ}

where:

Each Yᵢ is a maximal set such that X →→ Yᵢ
The Yᵢ partition R - X
X →→ Y holds iff Y is a union of some Yᵢ sets

Algorithm for DEP(X):

The dependency basis can be computed, but the algorithm is more complex than attribute closure for FDs. It involves:

Starting with initial partitions based on given MVDs
Iteratively refining partitions based on FD and MVD interactions
Continuing until no more refinement is possible

Simple Dependency Basis ExampleComputing DEP(A) in a simple case

Input

Relation: R(A, B, C, D)
Dependencies: A →→ B

Initial: R - A = {B, C, D}

From A →→ B:
  - B is one part of the partition
  - By complementation, A →→ CD
  - CD is the other part

DEP(A) = {{B}, {C, D}}

Output

From DEP(A), we can derive:
  A →→ B        (one partition element)
  A →→ CD       (other partition element)
  A →→ BCD      (union = R - A, trivial)
  
Any MVD A →→ Y holds iff Y is:
  B, CD, BCD, or ∅

Complexity Considerations:

Unlike FD closure computation (polynomial time), computing the full MVD closure can be exponential in the worst case. This is because:

The number of possible MVDs is exponential in the number of attributes
MVD interactions are more complex than FD interactions
Partition refinement can produce many intermediate states

In practice, we often work with specific queries ("does X →→ Y follow from D?") rather than computing the entire closure.

Testing MVD Implication

A practical question: Given dependencies D, does D imply X →→ Y?

Approach 1: Dependency Basis

Compute DEP(X) and check if Y is a union of partition elements.

Approach 2: Chase Algorithm

The chase algorithm is a powerful technique for testing implication. It works by:

Creating a tablaux (a special table with variables)
Applying dependencies to "equate" variables
Checking if the target dependency is satisfied

The chase handles both FDs and MVDs uniformly.

Chase Algorithm Sketch for MVD
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
CHASE_MVD_TEST(R, D, X →→ Y):
    # Create initial tableau with two rows
    # Row 1: distinguished variables for X ∪ Y
    # Row 2: same X variables, different Y variables
    
    Initialize tableau T with two rows t1, t2:
      t1[A] = a_i for all attributes
      t2[X] = t1[X]  # Same X values
      t2[Y] = different variables
      t2[Z] = different variables where Z = R - X - Y
    
    Repeat until no change:
      For each FD X' → Y' in D:
        If two rows agree on X', make them agree on Y'
      
      For each MVD X' →→ Y' in D:
        For rows r1, r2 agreeing on X':
          Create row r3 with:
            r3[X'] = r1[X']
            r3[Y'] = r1[Y']
            r3[R-X'-Y'] = r2[R-X'-Y']
          Add r3 if not already present
    
    # X →→ Y holds if the tableau exhibits 
    # the required tuple-swapping property

Practical Testing

For exam or interview purposes, the most practical approach is often: (1) Apply axioms manually for small cases, (2) Use complementation to simplify, (3) Check if the MVD is trivial first (Y ⊆ X or XY = R), (4) For complex cases, use the dependency basis method.

Special Properties and Important Theorems

Several important theorems govern the behavior of MVDs:

Theorem 1: FDs are Special MVDs

Every FD X → Y implies X →→ Y. The set of FDs is a "subset" of the set of MVDs (in terms of constraints imposed).

Theorem 2: MVD Complementation Pairing

MVDs always come in complementary pairs: X →→ Y holds if and only if X →→ (R - X - Y) holds. You cannot have one without the other.

Theorem 3: Lossless Join

If X →→ Y holds in R, then R = π_{XY}(R) ⋈ π_{X(R-Y)}(R). Every MVD guarantees a specific lossless decomposition.

Theorem 4: Embedded MVDs Behavior

An MVD X →→ Y may hold in relation R but not in a projection π_U(R) where U ⊂ R. MVDs are not always preserved under projection.

Theorem 5: No Union Rule for MVD LHS

Unlike FDs where X → Y and Y → Z gives X → Z (transitivity), MVDs don't have a simple union rule for combining the left-hand sides.

Key Theorems Reference
Theorem	Statement	Implication
FD ⊂ MVD	X → Y ⟹ X →→ Y	Every FD is also an MVD
Complementary Pair	X →→ Y ⟺ X →→ (R-X-Y)	MVDs come in pairs
Lossless Join	X →→ Y ⟹ lossless decomp	Every MVD allows decomposition
Context Sensitivity	MVD in R ⇏ MVD in π(R)	Projection may lose MVDs

MVD Transitivity Trap

Remember: X →→ Y and Y →→ Z does NOT imply X →→ Z directly. It implies X →→ (Z - Y). If Y and Z overlap, the result may be different from what you expect. Always compute the set difference carefully.

Summary: MVD Axioms

We've covered the complete axiomatic system for multivalued dependencies. Let's consolidate the key concepts:

Key Takeaways

•Three core MVD axioms — Complementation (M1), Augmentation (M2), and Transitivity (M3) form the basis for MVD inference.
•Replication rule bridges FDs and MVDs — Every functional dependency X → Y implies the multivalued dependency X →→ Y.
•MVD Transitivity is different — X →→ Y and Y →→ Z gives X →→ (Z - Y), not X →→ Z. The set difference is critical.
•Sound and complete system — The combined axiom system (Armstrong's + MVD + Interaction) can derive exactly all implied dependencies.
•Dependency basis — For attribute set X, DEP(X) partitions R - X according to MVDs, enabling efficient implication testing.
•Practical application — Use axioms to determine what dependencies hold, guiding normalization to 4NF and beyond.

Module Complete:

Congratulations! You've now completed the comprehensive study of Multivalued Dependencies. You understand:

What MVDs are and why they matter (Page 1)
The notation system for expressing MVDs (Page 2)
The deep concept of independence underlying MVDs (Page 3)
Trivial vs. non-trivial MVDs (Page 4)
The axiomatic system for reasoning about MVDs (Page 5)

This knowledge prepares you for Fourth Normal Form (4NF), which specifically addresses the redundancy caused by non-trivial multivalued dependencies.

Module Complete

You now have a complete understanding of multivalued dependencies—from definition through axiomatics. This knowledge is essential for advanced normalization (4NF, 5NF) and for understanding the full theory of relational database design. The next module explores Fourth Normal Form, where we apply MVD theory to eliminate the specific redundancy that MVDs cause.

MVD Axioms

Reasoning About Multivalued Dependencies

MVDs alone — Inference rules for deriving new MVDs from existing MVDs
FDs alone — The familiar Armstrong's axioms still apply
MVD-FD interactions — Rules that derive MVDs from FDs and vice versa

Mastering these axioms enables you to compute the complete set of dependencies implied by a given set, which is essential for normalization and schema design.

What You Will Learn

The Need for MVD Axioms

Why Do We Need Axioms for MVDs?

Example Problem:

Given:

R(A, B, C, D, E)
A →→ BC (employees' skills and departments are independent)
C → D (each skill requires a specific tool)

Question: Does A →→ B hold? Does A →→ D hold?

To answer such questions systematically, we need inference rules that allow us to derive new dependencies from given ones.

The Closure Problem:

Given a set of FDs and MVDs, the closure (or cover) is the set of ALL dependencies logically implied. Computing this closure requires a complete set of axioms.

Historical Context

Core MVD Axioms

The following axioms govern inference for multivalued dependencies alone (not involving FDs):

Axiom M1: MVD Complementation

If X →→ Y, then X →→ (R - X - Y)

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

Example: In R(A, B, C, D), if A →→ BC holds, then A →→ D also holds.

Axiom M2: MVD Augmentation

If X →→ Y and W ⊇ Z, then XW →→ YZ

More specifically: If X →→ Y holds, then for any W, XW →→ Y also holds.

Interpretation: Adding attributes to the determinant preserves the MVD.

Example: If A →→ B holds, then AC →→ B also holds.

Axiom M3: MVD Transitivity

If X →→ Y and Y →→ Z, then X →→ (Z - Y)

Interpretation: MVD transitivity works differently from FD transitivity. We derive the "difference" Z - Y, not just Z.

Example: If A →→ B and B →→ C, then A →→ (C - B). If B and C are disjoint, then A →→ C.

Core MVD Axioms Summary
Axiom	Name	Rule	Intuition
M1	Complementation	X →→ Y ⟹ X →→ (R-X-Y)	Independence is symmetric
M2	Augmentation	X →→ Y ⟹ XW →→ Y	Adding LHS preserves MVD
M3	Transitivity	X →→ Y, Y →→ Z ⟹ X →→ (Z-Y)	Chain rule with difference

MVD Transitivity Is Different!

Unlike FD transitivity (X → Y, Y → Z ⟹ X → Z), MVD transitivity produces (Z - Y), not Z directly. This is a common source of errors. The subtraction accounts for the set-based nature of MVDs.

FD-MVD Interaction Rules

The most important rules are those that connect functional dependencies with multivalued dependencies:

Rule I1: FD Implies MVD (Replication Rule)

If X → Y, then X →→ Y

Interpretation: Every functional dependency is also a multivalued dependency. FDs are a special case of MVDs.

Proof Sketch: If X → Y, then for each X value there's exactly one Y value. The "set" of Y values for each X has size 1, trivially forming a Cartesian product with Z values.

Rule I2: MVD Coalescence

If X →→ Y and there exists W such that:
  (a) W ∩ Y = ∅ (W and Y are disjoint)
  (b) W → Z
  (c) Z ⊆ Y
Then X → Z

Interpretation: Under specific conditions, an MVD can "collapse" into an FD. This happens when a portion of Y is functionally determined by attributes outside Y.

This rule is more subtle and applies in special circumstances.

Applying FD Implies MVDFrom FD to MVD conversion

Input

Given: R(EmpID, Name, DeptID, Skill)
FD: EmpID → Name (each employee has one name)

Apply Rule I1:
EmpID → Name implies EmpID →→ Name

Output

Result: EmpID →→ Name

This means the employee's name is "independent" of 
other attributes (DeptID, Skill) given EmpID.

But this is a special independence: there's only ONE 
name value per EmpID, so the "Cartesian product" with 
other attributes is trivially formed.

Rule I3: MVD Union

If X →→ Y and X →→ Z, then X →→ YZ

Interpretation: If Y and Z are both independent of the rest given X, then their union is also independent of the rest.

Rule I4: MVD Decomposition (Intersection Rule)

If X →→ Y and X →→ Z, then:
  X →→ (Y ∩ Z)
  X →→ (Y - Z)
  X →→ (Z - Y)

Interpretation: From two MVDs with the same LHS, we can derive MVDs for intersection and differences.

These derived rules combine basic axioms and are useful shortcuts.

The Complete Axiom System

Combining Armstrong's axioms for FDs with the MVD axioms gives us the complete system:

Armstrong's Axioms (for FDs):

Reflexivity: If Y ⊆ X, then X → Y
Augmentation: If X → Y, then XZ → YZ
Transitivity: If X → Y and Y → Z, then X → Z

MVD Axioms:

Complementation: If X →→ Y, then X →→ (R - X - Y)
Augmentation: If X →→ Y, then XZ →→ Y
Transitivity: If X →→ Y and Y →→ Z, then X →→ (Z - Y)

Interaction Axiom:

Replication: If X → Y, then X →→ Y

Additional Derived Rules (Coalescence):

If X →→ Y, Z ⊆ Y, W ∩ Y = ∅, and W → Z, then X → Z

Sound and Complete

Complete Axiom System Reference
	Name	Type	Rule
A1	Reflexivity	FD	Y ⊆ X ⟹ X → Y
A2	Augmentation	FD	X → Y ⟹ XZ → YZ
A3	Transitivity	FD	X → Y, Y → Z ⟹ X → Z
M1	Complementation	MVD	X →→ Y ⟹ X →→ (R-X-Y)
M2	Augmentation	MVD	X →→ Y ⟹ XZ →→ Y
M3	Transitivity	MVD	X →→ Y, Y →→ Z ⟹ X →→ (Z-Y)
I1	Replication	FD→MVD	X → Y ⟹ X →→ Y
I2	Coalescence	MVD→FD	(conditions) ⟹ X → Z

Applying MVD Axioms: Worked Examples

Let's work through examples to see the axioms in action.

Example 1: Using Complementation

Complementation Example
Relation: R(A, B, C, D)
Given: A →→ B
 
Apply Complementation (M1):
  R - A - B = {C, D}
  Therefore: A →→ CD
 
Both MVDs are equivalent - stating one implies the other.

Example 2: Using MVD Transitivity

MVD Transitivity Example
Relation: R(A, B, C, D, E)
Given: 
  A →→ BC  (A multi-determines BC)
  BC →→ D (BC multi-determines D)
 
Apply MVD Transitivity (M3):
  X = A, Y = BC, Z = D
  X →→ (Z - Y) = A →→ (D - BC)
  
Since D and BC are disjoint (D - BC = D):
  Result: A →→ D
 
Verification: Given A, the set of D values is 
independent of the remaining attributes (B, C, E).

Example 3: Using Replication with Other Rules

Combined FD and MVD Derivation
Relation: R(A, B, C, D, E)
Given:
  A → B        (FD)
  A →→ CD      (MVD)
 
Step 1: Apply Replication (I1) to A → B:
  A →→ B
 
Step 2: We now have:
  A →→ B
  A →→ CD
 
Step 3: Apply MVD Union (derived rule):
  A →→ BCD
 
Step 4: Apply Complementation to A →→ BCD:
  A →→ (R - A - BCD) = A →→ E
 
Result: From the original dependencies, we derived A →→ E

Derivation Strategies

Computing MVD Closure

The closure of a set of dependencies D, written D⁺, is the set of all FDs and MVDs that can be derived from D using the axiom system.

Dependency Basis:

For attribute set X, the dependency basis of X with respect to D, written DEP(X), is defined as:

DEP(X) = {Y₁, Y₂, ..., Yₖ}

where:

Each Yᵢ is a maximal set such that X →→ Yᵢ
The Yᵢ partition R - X
X →→ Y holds iff Y is a union of some Yᵢ sets

Algorithm for DEP(X):

The dependency basis can be computed, but the algorithm is more complex than attribute closure for FDs. It involves:

Starting with initial partitions based on given MVDs
Iteratively refining partitions based on FD and MVD interactions
Continuing until no more refinement is possible

Simple Dependency Basis ExampleComputing DEP(A) in a simple case

Input

Relation: R(A, B, C, D)
Dependencies: A →→ B

Initial: R - A = {B, C, D}

From A →→ B:
  - B is one part of the partition
  - By complementation, A →→ CD
  - CD is the other part

DEP(A) = {{B}, {C, D}}

Output

From DEP(A), we can derive:
  A →→ B        (one partition element)
  A →→ CD       (other partition element)
  A →→ BCD      (union = R - A, trivial)
  
Any MVD A →→ Y holds iff Y is:
  B, CD, BCD, or ∅

Complexity Considerations:

Unlike FD closure computation (polynomial time), computing the full MVD closure can be exponential in the worst case. This is because:

The number of possible MVDs is exponential in the number of attributes
MVD interactions are more complex than FD interactions
Partition refinement can produce many intermediate states

In practice, we often work with specific queries ("does X →→ Y follow from D?") rather than computing the entire closure.

Testing MVD Implication

A practical question: Given dependencies D, does D imply X →→ Y?

Approach 1: Dependency Basis

Compute DEP(X) and check if Y is a union of partition elements.

Approach 2: Chase Algorithm

The chase algorithm is a powerful technique for testing implication. It works by:

Creating a tablaux (a special table with variables)
Applying dependencies to "equate" variables
Checking if the target dependency is satisfied

The chase handles both FDs and MVDs uniformly.

Chase Algorithm Sketch for MVD
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
CHASE_MVD_TEST(R, D, X →→ Y):
    # Create initial tableau with two rows
    # Row 1: distinguished variables for X ∪ Y
    # Row 2: same X variables, different Y variables
    
    Initialize tableau T with two rows t1, t2:
      t1[A] = a_i for all attributes
      t2[X] = t1[X]  # Same X values
      t2[Y] = different variables
      t2[Z] = different variables where Z = R - X - Y
    
    Repeat until no change:
      For each FD X' → Y' in D:
        If two rows agree on X', make them agree on Y'
      
      For each MVD X' →→ Y' in D:
        For rows r1, r2 agreeing on X':
          Create row r3 with:
            r3[X'] = r1[X']
            r3[Y'] = r1[Y']
            r3[R-X'-Y'] = r2[R-X'-Y']
          Add r3 if not already present
    
    # X →→ Y holds if the tableau exhibits 
    # the required tuple-swapping property

Practical Testing

Special Properties and Important Theorems

Several important theorems govern the behavior of MVDs:

Theorem 1: FDs are Special MVDs

Every FD X → Y implies X →→ Y. The set of FDs is a "subset" of the set of MVDs (in terms of constraints imposed).

Theorem 2: MVD Complementation Pairing

MVDs always come in complementary pairs: X →→ Y holds if and only if X →→ (R - X - Y) holds. You cannot have one without the other.

Theorem 3: Lossless Join

If X →→ Y holds in R, then R = π_{XY}(R) ⋈ π_{X(R-Y)}(R). Every MVD guarantees a specific lossless decomposition.

Theorem 4: Embedded MVDs Behavior

An MVD X →→ Y may hold in relation R but not in a projection π_U(R) where U ⊂ R. MVDs are not always preserved under projection.

Theorem 5: No Union Rule for MVD LHS

Unlike FDs where X → Y and Y → Z gives X → Z (transitivity), MVDs don't have a simple union rule for combining the left-hand sides.

Key Theorems Reference
Theorem	Statement	Implication
FD ⊂ MVD	X → Y ⟹ X →→ Y	Every FD is also an MVD
Complementary Pair	X →→ Y ⟺ X →→ (R-X-Y)	MVDs come in pairs
Lossless Join	X →→ Y ⟹ lossless decomp	Every MVD allows decomposition
Context Sensitivity	MVD in R ⇏ MVD in π(R)	Projection may lose MVDs

MVD Transitivity Trap

Summary: MVD Axioms

We've covered the complete axiomatic system for multivalued dependencies. Let's consolidate the key concepts:

Key Takeaways

•Three core MVD axioms — Complementation (M1), Augmentation (M2), and Transitivity (M3) form the basis for MVD inference.
•Replication rule bridges FDs and MVDs — Every functional dependency X → Y implies the multivalued dependency X →→ Y.
•MVD Transitivity is different — X →→ Y and Y →→ Z gives X →→ (Z - Y), not X →→ Z. The set difference is critical.
•Sound and complete system — The combined axiom system (Armstrong's + MVD + Interaction) can derive exactly all implied dependencies.
•Dependency basis — For attribute set X, DEP(X) partitions R - X according to MVDs, enabling efficient implication testing.
•Practical application — Use axioms to determine what dependencies hold, guiding normalization to 4NF and beyond.

Module Complete:

Congratulations! You've now completed the comprehensive study of Multivalued Dependencies. You understand:

What MVDs are and why they matter (Page 1)
The notation system for expressing MVDs (Page 2)
The deep concept of independence underlying MVDs (Page 3)
Trivial vs. non-trivial MVDs (Page 4)
The axiomatic system for reasoning about MVDs (Page 5)

This knowledge prepares you for Fourth Normal Form (4NF), which specifically addresses the redundancy caused by non-trivial multivalued dependencies.

Module Complete