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 in his 1974 paper. The axioms are sound in generating only functional dependencies in the closure of a set of functional dependencies (denoted as ) when applied to that set (denoted as ). They are also complete in that repeated application of these rules will generate all functional dependencies in the closure .
More formally, let denote a relational scheme over the set of attributes with a set of functional dependencies . We say that a functional dependency is logically implied by ,and denote it with if and only if for every instance of that satisfies the functional dependencies in , r also satisfies . We denote by the set of all functional dependencies that are logically implied by .
Furthermore, with respect to a set of inference rules , we say that a functional dependency is derivable from the functional dependencies in by the set of inference rules , and we denote it by if and only if is obtainable by means of repeatedly applying the inference rules in to functional dependencies in . We denote by the set of all functional dependencies that are derivable from by inference rules in .
Then, a set of inference rules is sound if and only if the following holds:
that is to say, we cannot derive by means of functional dependencies that are not logically implied by . The set of inference rules is said to be complete if the following holds:
more simply put, we are able to derive by all the functional dependencies that are logically implied by .
- 1 Axioms (Primary Rules)
- 2 Additional rules (Secondary Rules)
- 3 Armstrong relation
- 4 External links
- 5 References
Axioms (Primary Rules)
Let be a relation scheme over the set of attributes . Henceforth we will denote by letters , , any subset of and, for short, the union of two sets of attributes and by instead of the usual ; this notation is rather standard in database theory when dealing with sets of attributes.
Axiom of reflexivity
If is a set of attributes and is a subset of , then holds . Hereby, holds  means that functionally determines .
- If then .
Axiom of augmentation
If holds and is a set of attributes, then holds . It means that attribute in dependencies does not change the basic dependencies.
- If , then for any .
Axiom of transitivity
If holds and holds , then holds .
- If and , then .
Additional rules (Secondary Rules)
These rules can be derived from the above axioms. Useful acronym DCUPS.
If then and .
|3.||(Transitivity of 1 & 2)|
If and then .
|3.||(Augmentation of 1 & A)|
|5.||(Augmentation 2 & X)|
|7.||(Union 4 & 6)|
If and then .
|4.||(Augmentation of 1 & X)|
|5.||(Augmentation of 2 & Y)|
|6.||(Transitivity of 3 & 4)|
|7.||(Transitivity of 4 & 5)|
If and then .
|3.||(Augmentation of 1 & Z)|
|4.||(Transitivity of 3 and 2)|
for any . This follows directly from the axiom of reflexivity.
Given a set of functional dependencies , an Armstrong relation is a relation which satisfies all the functional dependencies in the closure and only those dependencies. Unfortunately, the minimum-size Armstrong relation for a given set of dependencies can have a size which is an exponential function of the number of attributes in the dependencies considered.
- William Ward Armstrong: Dependency Structures of Data Base Relationships, page 580-583. IFIP Congress, 1974.
- Beeri, C.; Dowd, M.; Fagin, R.; Statman, R. (1984). "On the Structure of Armstrong Relations for Functional Dependencies" (PDF). Journal of the ACM. 31: 30–46. doi:10.1145/2422.322414.