Armstrong's axioms

Armstrong's axioms are a set of axioms (or, more precisely, inference rules) used to infer all the functional dependencies on a relational database. They were developed by William W. Armstrong on his paper. The axioms are sound in that they generate only functional dependencies in the closure of a set of functional dependencies (denoted as F⁺) when applied to that set (denoted as F). They are also complete in that repeated application of these rules will generate all functional dependencies in the closure F⁺.

More formally, let <R( U), F> denote a relational scheme over the set of attributes U with a set of functional dependencies F. We say that a functional dependency f is logically implied by F,and denote it with $F \models f$ if and only if for every instance r of R that satisfies the functional dependencies in F, r also satisfies f. We denote by F ⁺ the set of all functional dependencies that are logically implied by F.

Furthermore, with respect to a set of inference rules A, we say that a functional dependency f is derivable from the functional dependencies in F by the set of inference rules A, and we denote it by $F \vdash _{A} f$ if and only if f is obtainable by means of repeatedly applying the inference rules in A to functional dependencies in F. We denote by $F^{*}_{A}$ the set of all functional dependencies that are derivable from F by inference rules in A.

Then, a set of inference rules A is sound if and only if the following holds:

$F^{*}_{A} \subseteq F^{+}$

that is to say, we cannot derive by means of A functional dependencies that are not logically implied by F. The set of inference rules A is said to be complete if the following holds:

$F^{+} \subseteq F^{*}_{A}$

more simply put, we are able to derive by A all the functional dependencies that are logically implied by F.

Axioms

Let R(U) be a relation scheme over the set of attributes U. Henceforth we will denote by letters X, Y, Z any subset of U and, for short, the union of two sets of attributes X and Y by XY instead of the usual $X \cup Y$

Axiom of reflexivity

If $Y \subseteq X$, then $X \to Y$

Axiom of augmentation

If $X \to Y$, then $XZ \to YZ$ for any Z

Axiom of transitivity

If $X \to Y$ and $Y \to Z$ , then $X \to Z$

Additional 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$

Pseudo Transitivity

If $A \to B$ and $BC \to D$ then $AC \to D$

External links

• UMBC CMSC 461 Spring '99
• CS345 Lecture Notes from Stanford University