- Armstrong's axioms
Armstrong's axioms are a set of
axiom s (or, more precisely,inference rule s) used to infer all the functional dependencies on arelational database . They were developed byWilliam W. Armstrong on his paper "Dependency Structures of Data Base Relationships " published in1974 . 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 all the functional dependencies that are logically implied by F.
Axioms
Let R(U) be a primitive 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 X supseteq Y, then X o Y
Axiom of augmentation
If X o Y, then XZ o YZ for any Z
Axiom of transitivity
If X o Y and Y o Z , then X o Z
Additional rules
Union
If X o Y and X o Z then X o YZ
Decomposition
If X o YZ, then X o Y and X o Z
Pseudo Transitivity
If A o B and CB o D then AC o D
External links
* [http://www-db.stanford.edu/~ullman/cs345notes/slides01-1.ps CS345 Lecture Notes from Stanford University]
Wikimedia Foundation. 2010.