Some Implications of Armstrong’s Axioms
From Armstrong’s Axioms, we can prove a number of rules of implication among FDs.
Given a table T, and sets of attributes, W,X,Y,Z⊆Head(T), the following rules are observed.
- Union Rule
- If
X→Y and X→Z, then X→YZ.
Proof. By Augmentation Rule, we find X→Z ≡ XY→YZ and X→Y ≡ XX→XY ≡ X→XY, where the symbol ≡ means “equivalent to.”
According to Transitivity Rule, X→XY, and XY→YZ, we have X→YZ.
- Decomposition Rule
- If
X→YZ, then X→Y and X→Z.
Proof. The FD YZ→Y is found by inclusion, and X→YZ, YZ→Y implies X→Y by transitivity.
Similarly, X→Z.
- Pseudotransitivity Rule
- If
X→Y and WY→Z, then XW→Z.
Proof.
By Augmentation Rule, we find X→Y ≡ XW→WY.
According to Transitivity Rule, XW→WY, and WY→Z, we have XW→Z.
- Set Accumulation Rule
- If
X→YZ and Z→W, then X→YZW.
Proof.
Assume (a) X→YZ and (b) Z→W.
By Augmentation Rule and (b), we have YZZ→YZW ≡ (c) YZ→YZW.
According to Transivity Rule, (a), and (c), we find X→YZW
Note that all valid rules of implication among FDs can be derived from Armstrong’s Axioms; that is, no other rule of implication can be added to increase the effectiveness of Armstrong’s Axioms.