Loading learning content...
Armstrong's three axioms—reflexivity, augmentation, and transitivity—are sound and complete. They can derive any valid functional dependency. However, some common operations require tedious multi-step derivations with the base axioms alone.
Enter the derived rules: Union, Decomposition, and Pseudotransitivity. These rules are not new axioms—they can be proven from the original three. But they significantly streamline common FD manipulations, making practical analysis more efficient.
Think of derived rules as theorems: once proven, they can be used directly without re-deriving them each time.
By the end of this page, you will understand the Union, Decomposition, and Pseudotransitivity rules—their formal statements, proofs from Armstrong's axioms, and practical applications. You will master a complete toolkit for functional dependency analysis.
The Union Rule allows us to combine multiple functional dependencies with the same left-hand side.
Union Rule:
If X → Y and X → Z, then X → YZ
In plain English: If X determines Y and X determines Z, then X determines the union of Y and Z.
Why Union Is Useful:
Without Union, to show X → ABC from X → A, X → B, X → C, we would need multiple steps of augmentation and transitivity. Union collapses this into a single logical step.
12345678910111213141516171819202122232425262728293031
UNION RULE PROOF Statement: If X → Y and X → Z, then X → YZ Proof using Armstrong's Axioms: STEP 1: X → Y (Given - Premise 1) STEP 2: X → Z (Given - Premise 2) STEP 3: X → XY (Augmentation on Step 1 with Z = X) // X → Y augmented with X gives XX → XY = X → XY STEP 4: XY → YZ (Augmentation on Step 2 with Z = Y) // X → Z augmented with Y gives XY → ZY = XY → YZ STEP 5: X → YZ (Transitivity on Steps 3, 4) // X → XY and XY → YZ implies X → YZ Therefore: X → YZ ∎ ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━Alternative derivation showing the logic more clearly:━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 1. X → Y (Given)2. X → Z (Given)3. XY → YZ (Augmentation: Step 2 + Y)4. X → XY (Augmentation: Step 1 + X, then XX = X) Actually: Augment X → Y with X: XX → YX, i.e., X → XY5. X → YZ (Transitivity: Steps 4, 3)When we write X → {A, B, C}, we often mean X → A ∧ X → B ∧ X → C. The Union Rule formalizes the equivalence: having three separate FDs is the same as having one combined FD with a set-valued right-hand side.
The Decomposition Rule is the inverse of Union—it splits a combined right-hand side into individual FDs.
Decomposition Rule:
If X → YZ, then X → Y and X → Z
In plain English: If X determines the union of Y and Z, then X determines each of them individually.
Why Decomposition Is Useful:
Decomposition allows us to work with simpler, atomic FDs. When analyzing whether a specific attribute is determined by X, we can decompose X → ABC into X → A, X → B, X → C and check individually.
123456789101112131415161718192021222324252627282930313233343536
DECOMPOSITION RULE PROOF Statement: If X → YZ, then X → Y and X → Z Proof using Armstrong's Axioms: ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━Part 1: Prove X → Y━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ STEP 1: X → YZ (Given) STEP 2: YZ → Y (Reflexivity: Y ⊆ YZ) STEP 3: X → Y (Transitivity on Steps 1, 2) ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━Part 2: Prove X → Z━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ STEP 1: X → YZ (Given) STEP 2: YZ → Z (Reflexivity: Z ⊆ YZ) STEP 3: X → Z (Transitivity on Steps 1, 2) Therefore: X → Y and X → Z ∎ ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━Key Insight:━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━Decomposition follows directly from reflexivity (subsets aredetermined by supersets) combined with transitivity. This is why the right-hand side of an FD can always be"broken apart" into individual attributes.A critical misconception: Decomposition does NOT apply to the left-hand side. From AB → C, you CANNOT conclude A → C or B → C. The entire determinant AB is needed; neither A nor B alone may suffice. Only the dependent (right) side can be decomposed.
Union and Decomposition are inverse operations that together establish an important equivalence:
Equivalence Theorem:
X → {A₁, A₂, ..., Aₙ} ⟺ X → A₁ ∧ X → A₂ ∧ ... ∧ X → Aₙ
This means:
The two representations are completely interchangeable.
| Property | Union Rule | Decomposition Rule |
|---|---|---|
| Direction | Combines multiple FDs into one | Splits one FD into multiple |
| Formal Statement | X → Y, X → Z ⟹ X → YZ | X → YZ ⟹ X → Y, X → Z |
| Axioms Used | Augmentation + Transitivity | Reflexivity + Transitivity |
| Common Use | Simplifying FD sets | Analyzing individual attributes |
| Normal Form Analysis | Combining dependent attributes | Checking specific violations |
Practical Implication:
When working with FD sets, choose the representation that makes your analysis easier:
The Pseudotransitivity Rule generalizes transitivity by allowing an "extra" attribute set alongside the intermediate term.
Pseudotransitivity Rule:
If X → Y and WY → Z, then WX → Z
In plain English: If X determines Y, and W together with Y determines Z, then W together with X determines Z.
Understanding Pseudotransitivity:
Ordinary transitivity requires exact matching: X → Y and Y → Z give X → Z.
Pseudotransitivity relaxes this: X → Y and WY → Z give WX → Z.
The "pseudo" prefix indicates that W acts as an additional context that travels through the chain.
1234567891011121314151617181920212223242526272829
PSEUDOTRANSITIVITY RULE PROOF Statement: If X → Y and WY → Z, then WX → Z Proof using Armstrong's Axioms: STEP 1: X → Y (Given - Premise 1) STEP 2: WY → Z (Given - Premise 2) STEP 3: WX → WY (Augmentation on Step 1 with W) // X → Y augmented with W gives WX → WY STEP 4: WX → Z (Transitivity on Steps 3, 2) // WX → WY and WY → Z implies WX → Z Therefore: WX → Z ∎ ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━Intuitive Explanation:━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━The key insight is that X → Y can be "boosted" to WX → WYusing augmentation. This aligns with the left side of WY → Z,allowing transitivity to complete the derivation. Chain visualization: WX → WY → Z └───┘ └──┘ aug. givenPseudotransitivity includes ordinary transitivity as a special case:
Case 1: W = ∅ (Empty Set)
If W = ∅, then:
Pseudotransitivity becomes: X → Y and Y → Z ⟹ X → Z
This is exactly the ordinary Transitivity Rule!
Case 2: W Overlaps with X
If W and X share attributes, the union WX may be simpler than it appears.
Example:
Case 3: Y Overlaps with X
The rule still holds even if Y ⊆ X (making X → Y trivial).
Example:
Every application of transitivity is a special case of pseudotransitivity (with W = ∅). But pseudotransitivity is strictly more general—it handles cases where additional context (W) must travel through the dependency chain.
Let's consolidate all the rules—both Armstrong's original axioms and the derived rules—into a comprehensive reference:
| Rule Name | Type | Statement | Common Use |
|---|---|---|---|
| Reflexivity | Axiom | If Y ⊆ X, then X → Y | Base case; trivial dependencies |
| Augmentation | Axiom | If X → Y, then XZ → YZ | Expanding both sides; alignment |
| Transitivity | Axiom | If X → Y and Y → Z, then X → Z | Chaining dependencies |
| Union | Derived | If X → Y and X → Z, then X → YZ | Combining same-determinant FDs |
| Decomposition | Derived | If X → YZ, then X → Y and X → Z | Splitting for analysis |
| Pseudotransitivity | Derived | If X → Y and WY → Z, then WX → Z | Chaining with context |
This table represents your complete toolkit for FD manipulation. The three axioms are sufficient (by completeness), and the three derived rules add convenience. Master all six, and you can efficiently analyze any functional dependency scenario.
Let's see how the derived rules streamline real-world FD analysis tasks:
Task 1: Finding Attribute Closure Efficiently
Instead of applying axioms step-by-step, use decomposition and union implicitly:
1234567891011121314151617181920212223
EXAMPLE: Compute {A}⁺ under F = {A → BC, B → D, CD → E} WITHOUT derived rules (pure axioms):1. {A}⁺ = {A} (Reflexivity)2. A → BC (Given)3. BC → B, BC → C (Reflexivity: B ⊆ BC, C ⊆ BC)4. A → B, A → C (Transitivity: Steps 2, 3)5. {A}⁺ = {A, B, C}6. B → D (Given)7. A → D (Transitivity: A → B, B → D)8. {A}⁺ = {A, B, C, D}9. CD → E (Given)10. A → CD (Union: A → C, A → D)11. A → E (Transitivity: A → CD, CD → E)12. {A}⁺ = {A, B, C, D, E} WITH derived rules (streamlined):1. {A}⁺ = {A} (Start)2. A → BC applies: {A}⁺ = {A,B,C} (Add B, C)3. B → D applies: {A}⁺ = {A,B,C,D} (Add D by decomposition/union thinking)4. CD → E applies: {A}⁺ = {A,B,C,D,E} (C,D now in closure, add E) Same result, cleaner reasoning!Task 2: Testing FD Equivalence
To show two FD sets F and G are equivalent, derive each FD in G from F and vice versa. Derived rules accelerate both directions:
12345678910111213141516171819202122232425
EXAMPLE: Show F = {A → BC} is equivalent to G = {A → B, A → C} ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━Direction 1: Derive G from F━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━From A → BC (in F): - A → B by Decomposition ✓ - A → C by Decomposition ✓ Both FDs in G are derivable from F. ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━Direction 2: Derive F from G━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━From A → B and A → C (in G): - A → BC by Union ✓ The FD in F is derivable from G. ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━Conclusion: F ≡ G━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━The two FD sets are equivalent. This proof tookseconds with derived rules, vs. multiple axiomapplications without them.The most common error is assuming the left-hand side can be decomposed. Remember: AB → C means A and B TOGETHER determine C. Decomposition only works on the right: A → BC can split into A → B and A → C because A alone determines each. But AB → C cannot split because A alone or B alone may not determine C.
Beyond Union, Decomposition, and Pseudotransitivity, several other useful rules can be derived:
Self-Determination:
X → X (A special case of reflexivity: X ⊆ X)
Accumulation:
If X → YZ and Z → W, then X → YZW
Proof: From X → YZ, we get X → Z (decomposition). From X → Z and Z → W, we get X → W (transitivity). From X → YZ and X → W, we get X → YZW (union).
Projectivity:
If XZ → YZ, then X → Y (when Z are common attributes)
Note: This requires careful application—the condition is that Z appears on BOTH sides.
Composition:
If X → Y and W → Z, then XW → YZ
Proof: Augment X → Y with W: XW → YW. Augment W → Z with Y: YW → YZ. Transitivity: XW → YZ.
| Rule | Statement | Derived From |
|---|---|---|
| Self-Determination | X → X | Reflexivity |
| Accumulation | X → YZ, Z → W ⟹ X → YZW | Decomposition + Transitivity + Union |
| Composition | X → Y, W → Z ⟹ XW → YZ | Augmentation + Transitivity |
In principle, infinitely many "derived rules" could be stated. The practical value diminishes quickly—Union, Decomposition, and Pseudotransitivity cover the most common needs. Know them well, and derive others as needed using the base axioms.
We have explored the derived rules that extend Armstrong's axioms with practical convenience. Let us consolidate the key insights:
Module Complete:
You have now mastered Armstrong's Axioms in their entirety:
This knowledge equips you to analyze any functional dependency scenario, compute attribute closures, find keys, verify equivalence of FD sets, and understand the formal foundations of normalization theory.
Congratulations! You have completed the Armstrong's Axioms module. You now possess a complete understanding of functional dependency inference—from the theoretical foundations to practical application. This knowledge forms the backbone of database normalization and schema design.