Armstrong's Axioms

The reflexivity axiom tells us what we can conclude from set containment. But database design requires more: we need to combine and expand functional dependencies to discover new relationships. Enter the Augmentation Rule—Armstrong's second axiom.

Augmentation provides a powerful guarantee: if a functional dependency holds, it continues to hold when we add the same attributes to both sides. This principle enables us to build larger, more complex dependencies from simpler ones, forming the basis for many normalization algorithms and proofs.

The augmentation axiom can be stated formally as follows:

Augmentation Axiom (Armstrong's Second Axiom):

If X → Y, then XZ → YZ for any set of attributes Z

In plain English: If X functionally determines Y, then adding any attribute set Z to both X and Y preserves the dependency.

Let us dissect this definition:

• X → Y is an existing functional dependency (our premise)
• Z is any set of attributes from the relation schema (can overlap with X, Y, or neither)
• XZ means the union X ∪ Z (all attributes in X or Z)
• YZ means the union Y ∪ Z
• XZ → YZ is the derived functional dependency (our conclusion)

Important observations:

1. Z can be empty — If Z = ∅, then XZ = X and YZ = Y, giving us X → Y (no change)
2. Z can overlap with X or Y — The union handles duplicates naturally
3. Z can be the entire relation — XZ → YZ would still hold
4. The axiom is unconditional — It applies to any Z whatsoever

Let us prove the augmentation axiom from the definition of functional dependencies.

Proof of Augmentation:

Given: X → Y holds on relation r To Prove: XZ → YZ holds on relation r

Proof:

Recall the definition of a functional dependency:

X → Y holds if for all tuples t₁, t₂ ∈ r: if t₁[X] = t₂[X], then t₁[Y] = t₂[Y]

We need to show: for all t₁, t₂ ∈ r, if t₁[XZ] = t₂[XZ], then t₁[YZ] = t₂[YZ].

Suppose t₁[XZ] = t₂[XZ] for some tuples t₁, t₂ ∈ r.

Since XZ = X ∪ Z, we have:

• t₁[X] = t₂[X] (tuples agree on X)
• t₁[Z] = t₂[Z] (tuples agree on Z)

Since X → Y holds and t₁[X] = t₂[X]:

• t₁[Y] = t₂[Y] (derived from X → Y)

Now we have:

• t₁[Y] = t₂[Y]
• t₁[Z] = t₂[Z]

Therefore:

• t₁[Y ∪ Z] = t₂[Y ∪ Z]
• t₁[YZ] = t₂[YZ]

Conclusion: XZ → YZ holds. ∎

Understanding augmentation becomes clearer when we visualize what's happening to the functional dependency:

Original Dependency: X → Y

┌─────────────────────────────────────────────────┐
│ Tuples that agree on X                          │
│ ┌─────────────────────────────────────────────┐ │
│ │ Must also agree on Y                        │ │
│ │                                             │ │
│ └─────────────────────────────────────────────┘ │
└─────────────────────────────────────────────────┘

Augmented Dependency: XZ → YZ

┌─────────────────────────────────────────────────┐
│ Tuples that agree on X AND Z (more restrictive) │
│ ┌─────────────────────────────────────────────┐ │
│ │ Must also agree on Y AND Z                  │ │
│ │ • Agree on Y (from original X → Y)          │ │
│ │ • Agree on Z (from reflexivity: Z → Z)      │ │
│ └─────────────────────────────────────────────┘ │
└─────────────────────────────────────────────────┘

The left side (XZ) imposes a stronger constraint than X alone—fewer tuple pairs will satisfy it. But for those pairs that do, the right side (YZ) is guaranteed because:

1. Y follows from X (original dependency)
2. Z follows from Z (reflexivity)

Let's examine special cases of augmentation to build complete understanding:

Case 1: Z is the empty set (∅)

If X → Y and Z = ∅, then:

• XZ = X ∪ ∅ = X
• YZ = Y ∪ ∅ = Y
• Result: X → Y (unchanged)

This confirms that augmentation generalizes the identity: with Z = ∅, we recover the original dependency.

Case 2: Z equals X

If X → Y and Z = X, then:

• XZ = X ∪ X = X
• YZ = Y ∪ X = XY
• Result: X → XY

This is a useful form: we can always add the determinant to the dependent side.

Case 3: Z equals Y

If X → Y and Z = Y, then:

• XZ = X ∪ Y = XY
• YZ = Y ∪ Y = Y
• Result: XY → Y

This is a trivial dependency (Y ⊆ XY), so we've derived something we already knew from reflexivity.

Case 4: Z is disjoint from both X and Y

If X → Y and Z ∩ (X ∪ Y) = ∅, then:

• XZ and YZ are proper supersets of X and Y
• Result: XZ → YZ introduces genuinely new attributes to both sides

Different textbooks present augmentation in various equivalent forms. Understanding these alternatives deepens comprehension:

Formulation 1: Standard (Armstrong's Original)

If X → Y, then XZ → YZ

This is the form we've been using—augment both sides by the same Z.

Formulation 2: Left-Side Augmentation Only

If X → Y, then XZ → Y

This appears different but is derivable from the standard form:

• From X → Y, by augmentation: XZ → YZ
• Since Y ⊆ YZ, by reflexivity: YZ → Y
• By transitivity (covered next page): XZ → Y

Formulation 3: Right-Side Using Reflexivity

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

Proof:

• From X → Y (given)
• From Z ⊆ X and reflexivity: X → Z
• Combining: X → YZ (using union rule, derived later)

Why Multiple Formulations Exist:

Different formulations optimize for different proof strategies. Some proofs are shorter with one formulation than another. The key insight is that all formulations are inter-derivable within the complete Armstrong system.

Augmentation plays crucial roles in several database algorithms:

1. Deriving Implied Dependencies

When we need to check if a dependency X → Y is implied by a set of dependencies F, augmentation helps expand existing dependencies to approach the target.

2. Proving Equivalence of FD Sets

To show two FD sets F and G are equivalent, we derive each FD in G from F and vice versa. Augmentation is a key tool in these derivations.

3. Computing Keys

When searching for candidate keys, we often augment existing dependencies to form superkeys, then minimize them.

Students often make errors when applying augmentation. Let's identify and correct them:

Understanding augmentation impacts practical database design in several ways:

Superkey Construction:

If K is a candidate key (K → R), then any superset of K is a superkey:

• From K → R, augment with any Z
• KZ → RZ, but since R contains all attributes, RZ = R
• Therefore KZ → R

This proves that adding attributes to a key always yields a superkey.

Composite Key Analysis:

When analyzing composite keys like {StudentID, CourseID} → Grade:

• Augmenting with Semester: {StudentID, CourseID, Semester} → {Grade, Semester}
• This might reveal that a different composite key is needed if the original was too narrow

Denormalization Decisions:

When considering adding redundant columns to improve query performance, augmentation helps trace which dependencies will still hold after the modification.

We have thoroughly explored the augmentation axiom, the second of Armstrong's three foundational rules. Let us consolidate the key insights:

What's Next:

Reflexivity tells us about set containment. Augmentation tells us how to expand dependencies. But how do we chain dependencies together? If A → B and B → C, can we conclude A → C? The next page introduces the Transitivity Rule, which provides exactly this capability and completes Armstrong's foundational axiom system.