Armstrongs Axioms - Learning Module

Loading content...

0/241

Augmentation Rule

Expanding Dependencies While Preserving Truth

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.

What You Will Learn

By the end of this page, you will understand the formal definition of the augmentation axiom, its rigorous proof, why it preserves functional dependency validity, and how to apply it in deriving new dependencies. You will see how augmentation combines with reflexivity to enable sophisticated reasoning about attribute relationships.

Formal Definition of Augmentation

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:

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

Applying AugmentationConsider a relation schema R(SSN, Name, DeptID, DeptName) with the functional dependency: **SSN → Name** Applying augmentation with Z = {DeptID}: **{SSN, DeptID} → {Name, DeptID}** This new dependency is guaranteed to hold. If two tuples agree on both SSN and DeptID, they must agree on both Name and DeptID. We can augment again with Z = {DeptName}: **{SSN, DeptID, DeptName} → {Name, DeptID, DeptName}** Augmentation can be applied repeatedly with different attribute sets.

Input

Output

Why Augmentation Holds: The Proof

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. ∎

Intuitive Understanding

Augmentation works because adding Z to both sides adds the same additional constraint. If two tuples must match on X to match on Y, then requiring them to also match on Z doesn't change this relationship—it just adds the (trivial) requirement that they match on Z to conclude they match on Z. The original dependency X → Y does all the "real work."

Visualizing the Augmentation Process

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:

Y follows from X (original dependency)
Z follows from Z (reflexivity)

Augmentation Step-by-Step
Step	Action	Dependency	Justification
1	Start with given FD	A → B	Given
2	Augment with {C}	AC → BC	Augmentation (Z = {C})
3	Augment with {D}	ACD → BCD	Augmentation (Z = {D})
4	Augment with {A}	A → AB	Augmentation (Z = {A}), note: A ∪ A = A
5	Augment with {B}	AB → B	Augmentation (Z = {B}), note: trivial result

Special Cases and Edge Cases

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

Why All Cases Work

The proof of augmentation makes no assumptions about Z's relationship to X or Y. Whether Z overlaps, contains, or is disjoint from X and Y, the logical structure of the proof holds identically. This generality is what makes augmentation so powerful.

Alternative Formulations of Augmentation

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.

Standard Form Advantages

•Symmetric treatment of both sides
•Directly matches the proof structure
•Cleaner for theoretical work
•Armstrong's original presentation

Left-Only Form Advantages

•Often more useful in practice
•Directly grows the determinant
•Common in closure algorithms
•Simpler to apply in derivations

Augmentation in Algorithms

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.

Deriving Dependencies Using Augmentation

Derivation Example

EXAMPLE: Derive ABC → DE from F = {A → D, BC → E}
 
Given:
  F = {A → D, BC → E}
 
Goal:
  Prove ABC → DE
 
Derivation:
 
STEP 1: Start with A → D
        (Given in F)
 
STEP 2: Augment A → D with BC
        Apply: If X → Y, then XZ → YZ (Z = BC)
        Result: ABC → DBC
        
STEP 3: Start with BC → E
        (Given in F)
        
STEP 4: Augment BC → E with AD
        Apply: If X → Y, then XZ → YZ (Z = AD)
        Result: ABCD → ADE
        
STEP 5: From ABC → DBC (Step 2)
        By reflexivity: DBC → D
        By transitivity: ABC → D
        
STEP 6: From BC → E and ABC ⊇ BC
        By left augmentation: ABC → E
        
STEP 7: Combine ABC → D and ABC → E
        By union rule (derived later): ABC → DE ✓
 
The derivation shows ABC → DE follows from F.

Practical Derivation Strategy

When deriving dependencies: (1) Identify which given FDs contribute to the goal's right side. (2) Augment those FDs to have the goal's left side as determinant. (3) Combine the results. Augmentation is the key step that lets us "align" different FDs to work together.

Common Mistakes with Augmentation

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

Common Errors

•Error: Augmenting only the left side with arbitrary Z Wrong: From A → B, conclude AC → B directly by "augmentation" Correct: This is valid, but it's not pure augmentation—it's augmentation (A → B ⟹ AC → BC) plus reflexivity (BC → B) plus transitivity (AC → B). Many textbooks call this "left augmentation" and treat it as a derived rule.
•Error: Augmenting only the right side Wrong: From A → B, conclude A → BC Why it's wrong: This doesn't follow from augmentation alone. It would require knowing A → C separately. You cannot add attributes to the right side without adding them to the left side (or having another FD that gives you those attributes).
•Error: Assuming augmentation works "backwards" Wrong: From AB → BC, conclude A → B Why it's wrong: You cannot remove attributes from an FD using augmentation. Augmentation only adds attributes (or leaves them unchanged). Removing attributes requires different rules or may not be possible.
•Error: Confusing augmentation with union Wrong: From A → B and A → C, conclude A → BC by "augmentation" Correct: This uses the Union Rule (derived from augmentation and transitivity, covered later), not augmentation directly.

Augmentation in Database Design

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.

Augmentation in Design Scenarios
Scenario	Original FD	Augmentation Applied	Design Implication
Adding audit column	EmpID → Salary	EmpID, ModDate → Salary, ModDate	History tracking preserves original constraint
Composite primary key	OrderID → CustomerID	OrderID, LineNum → CustomerID, LineNum	Line items inherit order-level properties
Partitioning	AcctNum → Balance	AcctNum, Region → Balance, Region	Regional partitions maintain local consistency
Caching	ISBN → Title	ISBN, CacheTime → Title, CacheTime	Cache entries with timestamps preserve lookup semantics

Summary: The Augmentation Rule

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

Key Takeaways

•Formal Statement: If X → Y, then XZ → YZ for any attribute set Z. This is Armstrong's augmentation axiom.
•Proof Insight: Augmentation works because matching on XZ requires matching on both X and Z; the original FD handles X → Y, and reflexivity handles Z → Z.
•Generality: Z can be any attribute set—empty, overlapping with X or Y, or completely disjoint. The axiom holds unconditionally.
•Alternative Forms: Left-only augmentation (X → Y ⟹ XZ → Y) is a common derived rule, obtained by combining augmentation with reflexivity and transitivity.
•Cannot Remove Attributes: Augmentation only adds attributes to dependencies. It cannot be used to derive smaller dependencies from larger ones.
•Design Applications: Augmentation explains why superkeys work, helps trace dependency preservation during schema modifications, and supports key analysis.

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.

Page Complete

You now understand the augmentation axiom—its definition, proof, special cases, common errors, and practical applications. This knowledge, combined with reflexivity, prepares you for the transitivity axiom, which completes the set of rules needed to derive all valid functional dependencies.