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.




      “Dreams will get you nowhere,    
      a good kick in the pants will take you a long way.”    
      — Baltasar Gracian