Armstrong's Axioms for Functional Dependencies
Armstrong's Axioms are foundational inference rules for functional dependencies (FDs) in relational database systems. The three primary axioms are Reflexivity, Augmentation, and Transitivity. The Union rule states: If $X \rightarrow Y$ and $X \rightarrow Z$, then $X \rightarrow YZ$. The question asks for the axioms necessary and sufficient to prove that the Union rule is implied by the basic three.
Proving the Union Rule
The Union rule can be proven using Augmentation and Transitivity. These two axioms provide the necessary mechanisms to derive new dependencies from existing ones, forming the basis for this proof.
Proof Steps:
- Given FDs: $X \rightarrow Y$ and $X \rightarrow Z$.
- Apply Augmentation: Using the Augmentation rule on $X \rightarrow Z$ with attribute set $Y$, we derive $XY \rightarrow YZ$.
- Apply Transitivity: We now have $X \rightarrow Y$ (given) and $XY \rightarrow YZ$ (derived). The Transitivity axiom ($A \rightarrow B$ and $B \rightarrow C$ implies $A \rightarrow C$) allows us to chain dependencies. By considering $X \rightarrow Y$ and $XY \rightarrow YZ$, Transitivity connects these to yield $X \rightarrow YZ$. The necessary link $X \rightarrow XY$ is implicitly handled in this derivation context.
Augmentation extends dependencies, and Transitivity chains them, making them sufficient for deriving the Union rule.
Conclusion
The combination of Augmentation and Transitivity is both necessary and sufficient for proving the Union rule.
