Rahul Sharma

Armstrong's axioms

Updated on
Share on FacebookTweet on TwitterShare on LinkedIn

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 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

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 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 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 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 + F A

more simply put, we are able to derive by A all the functional dependencies that are logically implied by F .

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 X Y instead of the usual X Y ; this notation is rather standard in database theory when dealing with sets of attributes.

Axiom of reflexivity

If Y X then X Y

Axiom of augmentation

If X Y , then X Z Y Z for any Z

Axiom of transitivity

If X Y and Y Z , then X Z

Additional rules

These rules can be derived from the above axioms.

Union (Notation)

If X Y and X Z then X Y Z

Decomposition

If X Y Z then X Y and X Z

Pseudo transitivity

If X Y and Y Z W then X Z W

Armstrong relation

Given a set of functional dependencies F , an Armstrong relation is a relation which satisfies all the functional dependencies in the closure F + 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.

References

Armstrong's axioms Wikipedia


Similar Topics
Strange Factories
Bai Chunli
Nathaniel Mayfield
Topics