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 [1]. 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 
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 
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 
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:
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:
more simply put, we are able to derive by A all the functional dependencies that are logically implied by F.
Contents |
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 
Axiom of reflexivity
If 
, then 
Axiom of augmentation
If , then 
for any Z
Axiom of transitivity
If and 
, then 
Additional rules
Union
If and then 
Decomposition
If , then and
Pseudo Transitivity
If 
and 
then 
External links
References
- ^ William Ward Armstrong: Dependency Structures of Data Base Relationships, page 580-583. IFIP Congress, 1974.
|
||||||||||||||||||||
|
||||||||
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
