Armstrong Axioms

The term Armstrong axioms refers to the sound and complete set of inference rules or axioms, introduced by William W. Armstrong [2], that is used to test logical implication of functional dependencies.

Given a relation schema R[U] and a set of functional dependencies Σ over attributes in U, a functional dependency f is logically implied by Σ, denoted by Σ⊧f, if for every instance I of R satisfying all functional dependencies in Σ, I satisfies f. The set of all functional dependencies implied by Σ is called the closure of Σ, denoted by Σ⁺.

Armstrong axioms consist of the following three rules:

• Reflexivity: If Y ⊆ X, then X → Y.

• Augmentation: If X → Y , then XZ → YZ.

• Transitivity: If X → Y and Y → Z, then X → Z.

Note that in the above rules XZ refers to the union of two attribute sets X and Z. Armstrong axioms are sound and complete: a functional dependency f is derivable from a set of functional dependencies Σ by applying the axioms if and only if Σ⊧f (refer to [1]...

Authors and Affiliations

1. University of British Columbia, Vancouver, BC, Canada

   Solmaz Kolahi

Corresponding author

Correspondence to Solmaz Kolahi .

Editors and Affiliations

1. Georgia Institute of Technology College of Computing, Atlanta, GA, USA

   Ling Liu

2. University of Waterloo School of Computer Science, Waterloo, ON, Canada

   M. Tamer Özsu

1. School of Informatics, University of Edinburgh, Edinburgh, Scotland, UK

   Leonid Libkin

Reprints and permissions

© 2018 Springer Science+Business Media, LLC, part of Springer Nature

Policies and ethics