101
0/252
Loading content...
Reflexivity grounds us in set containment. Augmentation expands dependencies symmetrically. But the true power of Armstrong's system emerges with the Transitivity Rule—the third and final axiom.
Transitivity allows us to chain dependencies together: if knowing X tells us Y, and knowing Y tells us Z, then knowing X must tell us Z. This seemingly simple principle underlies some of the most important discoveries in functional dependency analysis, including the detection of transitive dependencies that violate Third Normal Form.
By the end of this page, you will understand the formal definition of the transitivity axiom, its rigorous proof, how to apply it in deriving chains of dependencies, its critical role in normalization theory, and common patterns where transitivity reveals hidden data relationships.
The transitivity axiom can be stated formally as follows:
Transitivity Axiom (Armstrong's Third Axiom):
If X → Y and Y → Z, then X → Z
In plain English: If X functionally determines Y, and Y functionally determines Z, then X functionally determines Z.
Let us examine this definition:
Key observations:
Let us prove the transitivity axiom from the definition of functional dependencies.
Proof of Transitivity:
Given:
To Prove: X → Z holds on relation r
Proof:
Recall the definition of a functional dependency:
X → Z holds if for all tuples t₁, t₂ ∈ r: if t₁[X] = t₂[X], then t₁[Z] = t₂[Z]
Take any two tuples t₁, t₂ ∈ r such that t₁[X] = t₂[X].
Since X → Y holds and t₁[X] = t₂[X]:
Since Y → Z holds and t₁[Y] = t₂[Y] (just established):
Therefore, for any t₁, t₂ ∈ r: if t₁[X] = t₂[X], then t₁[Z] = t₂[Z].
Conclusion: X → Z holds. ∎
The proof follows a simple chain: matching on X forces matching on Y (first FD), and matching on Y forces matching on Z (second FD). Therefore, matching on X ultimately forces matching on Z. Y serves as an intermediate "stepping stone" in the reasoning.
Diagrammatic Representation:
t₁[X] = t₂[X]
│
│ (by X → Y)
▼
t₁[Y] = t₂[Y]
│
│ (by Y → Z)
▼
t₁[Z] = t₂[Z]
Conclusion: X → Z
Each arrow represents an application of a functional dependency, and the chain shows how the initial equality on X propagates through Y to reach Z.
Transitivity can be applied repeatedly to form longer chains of functional dependencies. This is essential when analyzing complex dependency structures.
Multi-Step Transitivity:
Given:
We can derive:
| Step | From | Apply Transitivity | Result |
|---|---|---|---|
| 1 | A → B, B → C | A → B, B → C ⟹ A → C | A → C |
| 2 | A → C, C → D | A → C, C → D ⟹ A → D | A → D |
| 3 | A → D, D → E | A → D, D → E ⟹ A → E | A → E |
When we repeatedly apply transitivity until no new dependencies can be derived, we obtain the transitive closure of the dependency set. This is conceptually similar to the attribute closure, but operates on dependencies rather than attributes.
123456789101112131415161718192021222324252627
EXAMPLE: Find all FDs derivable by transitivity from:F = {SSN → EmpID, EmpID → DeptID, DeptID → DeptName, DeptID → ManagerID} Step-by-step derivation: 1. SSN → EmpID (Given)2. EmpID → DeptID (Given)3. DeptID → DeptName (Given)4. DeptID → ManagerID (Given) 5. SSN → DeptID (Transitivity: 1, 2) // SSN → EmpID and EmpID → DeptID ⟹ SSN → DeptID 6. SSN → DeptName (Transitivity: 5, 3) // SSN → DeptID and DeptID → DeptName ⟹ SSN → DeptName 7. SSN → ManagerID (Transitivity: 5, 4) // SSN → DeptID and DeptID → ManagerID ⟹ SSN → ManagerID 8. EmpID → DeptName (Transitivity: 2, 3) // EmpID → DeptID and DeptID → DeptName ⟹ EmpID → DeptName 9. EmpID → ManagerID (Transitivity: 2, 4) // EmpID → DeptID and DeptID → ManagerID ⟹ EmpID → ManagerID Result: We derived 5 new FDs (5-9) using transitivity alone.These reveal hidden relationships in the data model.The transitivity axiom directly connects to one of the most important concepts in database normalization: the transitive dependency violation that defines Third Normal Form (3NF).
Definition: Transitive Dependency
A non-prime attribute A is transitively dependent on a candidate key K if:
In other words, A depends on K through an intermediate non-key attribute B.
Why Transitive Dependencies Are Problematic:
| Anomaly Type | Description | Example |
|---|---|---|
| Update Anomaly | Changing one fact requires multiple row updates | If the dean changes, must update every student in that department |
| Insertion Anomaly | Cannot insert certain facts without unrelated data | Cannot record a new department's dean without enrolling a student |
| Deletion Anomaly | Deleting rows loses unrelated facts | Deleting the last student in a department loses dean information |
When you derive a dependency X → Z via transitivity through Y, ask: Should Z really be stored with X, or should it be in a separate table with Y? If Y is not a key, the schema likely needs decomposition.
The transitivity axiom handles overlapping attribute sets gracefully. Understanding these cases builds deeper intuition.
Case 1: Z overlaps with X
Given: X → Y and Y → XZ (where Z is some attribute set)
By transitivity: X → XZ
This is notable because the conclusion includes X itself. Since X → X is trivially true (reflexivity), the non-trivial part is X → Z.
Case 2: Y overlaps with both X and Z
Given: AB → BC and BC → CD
By transitivity: AB → CD
Note how B appears on both sides of the first FD and is "passed through" in the chain.
Case 3: Y equals Z
Given: X → Y and Y → Y
The second FD is trivial (reflexivity). By transitivity: X → Y (no new information).
Case 4: X equals Y
Given: X → X and X → Z
The first FD is trivial. By transitivity: X → Z (equivalent to the second FD).
123456789101112131415161718192021222324
EXAMPLE: Transitivity with overlapping attributes Given: F = {AB → CD, CD → BE} Derive AB → BE using transitivity: Step 1: AB → CD (Given)Step 2: CD → BE (Given)Step 3: AB → BE (Transitivity on Steps 1, 2) Analysis:- In Step 1, B is on left side- In Step 3, B is also on right side- Transitivity handles this correctly- AB → BE means: AB → B (trivial) and AB → E (non-trivial) The result AB → BE decomposes to:- AB → B (trivial, from reflexivity)- AB → E (non-trivial, genuine new information) Key Insight: Transitivity may produce FDs with overlapping determinants and dependents. We often decompose these to isolate the non-trivial components.The true power of Armstrong's axioms emerges when we combine all three. Together, they form a sound and complete inference system for functional dependencies.
A Complex Derivation:
Given: F = {A → B, B → C, C → D}
Derive: A → BCD
12345678910111213141516171819202122232425262728293031
DERIVATION: From F = {A → B, B → C, C → D}, derive A → BCD STEP 1: A → B (Given) STEP 2: A → C (Transitivity on A → B, B → C) // A → B and B → C implies A → C STEP 3: A → D (Transitivity on A → C, C → D) // A → C and C → D implies A → D STEP 4: A → AB (Augmentation on A → B with Z = A) // A → B augmented with A gives AA → AB = A → AB STEP 5: A → ABC (Augmentation on A → BC variant) // First, from A → B and A → C (steps 1, 2) // Augment A → B with C: AC → BC // But we need A alone on left side... Alternative for STEP 5: // From A → B (step 1) // Augment with A: A → AB (step 4) // From A → C (step 2), augment with AB: A → AC // Wait, this needs the Union rule... Using Union Rule (derived rule, covered next page):STEP 5: A → BC (Union on A → B, A → C)STEP 6: A → BCD (Union on A → BC, A → D) Conclusion: A → BCD ✓ This derivation required all three axioms plus the Union rule!Most practical derivations interleave all three axioms. Reflexivity provides base cases, augmentation aligns left-hand sides, and transitivity chains dependencies together. The derived rules (union, decomposition, pseudotransitivity) streamline common patterns.
Transitivity is conceptually simple but easy to misapply. Let's identify common errors:
Before applying transitivity, verify: Does the right-hand side of FD₁ exactly match the left-hand side of FD₂? If not, you may need decomposition, augmentation, or other rules to align them first.
Beyond theoretical derivations, transitivity appears in practical database scenarios:
1. Query Optimization
If the query optimizer knows:
It can infer A → C and potentially use the A index to answer queries filtering on C.
2. Integrity Constraint Inference
Application code might only explicitly state:
Transitivity reveals: EmployeeID determines DepartmentBudget. This might uncover unintended access patterns or data leakage.
3. Data Warehouse Design
In dimensional modeling:
Transitivity shows: ProductID → DivisionID. This chain is often denormalized into a single Product dimension table for query performance.
4. ETL Validation
When loading data:
Transitivity implies EmployeeID → TimezoneID. The ETL can use this to validate or compute timezone assignments.
| Domain | FD Chain | Derived FD | Practical Use |
|---|---|---|---|
| E-commerce | OrderID → CustomerID → Region | OrderID → Region | Route orders to regional warehouses |
| Healthcare | PatientID → DoctorID → Hospital | PatientID → Hospital | Patient record localization |
| Finance | AccountID → BranchID → BankCode | AccountID → BankCode | Routing number derivation |
| Education | StudentID → AdvisorID → Department | StudentID → Department | Graduation requirement checking |
We have thoroughly explored the transitivity axiom, the third and final of Armstrong's foundational rules. Let us consolidate the key insights:
What's Next:
With all three axioms—reflexivity, augmentation, and transitivity—we now have a complete toolkit for deriving functional dependencies. But how do we know this system is reliable? The next page explores Soundness and Completeness: the mathematical guarantees that Armstrong's axioms derive exactly the valid dependencies—no more, no less.
You now understand the transitivity axiom—its definition, proof, extended chains, connection to normalization, common errors, and practical applications. Combined with reflexivity and augmentation, you have mastered Armstrong's three foundational axioms for functional dependency inference.