Armstrong's axioms

From Wikipedia, the free encyclopedia

Armstrong's axioms are a set of axioms used to infer all the functional dependencies on a relational database. They were developed by William W. Armstrong on his paper Dependency Structures of Data Base Relationships published in 1974. 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+.

Contents

[edit] Axioms

[edit] Axiom of reflexivity

If X \supseteq Y, then X \to Y

[edit] Axiom of augmentation

If X \to Y, then XZ \to YZ for any Z
Where XZ means the collection of all attributes in X and Z.

[edit] Axiom of transitivity

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

[edit] Additional rules

[edit] Union

If X \to Y and X \to Z then X \to YZ

[edit] Decomposition

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


[edit] Pseudo Transitivity

If A \to B and CB \to D then AC \to D

[edit] External links

Retrieved from "http://en.wikipedia.org../../../a/r/m/Armstrong%27s_axioms.html"