Skip to content

Armstrong's axioms

Armstrong's axioms are a set of inference rules used to derive all the functional dependencies on a relation scheme from a given set of functional dependencies.

Axioms

  1. Reflexivity: If \(Y \subseteq X\), then \(X \to Y\).
  2. Augmentation: If \(X \to Y\), then \(XZ \to YZ\) for any \(Z\).
  3. Transitivity: If \(X \to Y\) and \(Y \to Z\), then \(X \to Z\).

Derived rules:

  • Union: If \(X \to Y\) and \(X \to Z\), then \(X \to YZ\).
  • Decomposition: If \(X \to YZ\), then \(X \to Y\) and \(X \to Z\).
  • Pseudotransitivity: If \(X \to Y\) and \(YZ \to W\), then \(XZ \to W\).

Examples

  • \(F = \{A \to B, B \to C\}\): using transitivity, derive \(A \to C\).
  • \(F = \{A \to B, A \to C\}\): using union, derive \(A \to BC\).
  • \(F = \{A \to BC\}\): using decomposition, derive \(A \to B\) and \(A \to C\).
  • \(F = \{A \to B, BC \to D\}\): using pseudotransitivity, derive \(AC \to D\).
  • \(F = \{A \to B\}\): using augmentation with \(C\), derive \(AC \to BC\).
  • \(F = \{AB \to C\}\): using reflexivity, derive \(AB \to A\) and \(AB \to B\).