Armstrong's axioms

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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 1974 paper.[1] 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^+.

More formally, let \langle R(U), F \rangle 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 by A all the functional dependencies that are logically implied by F.

Axioms[edit]

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

Axiom of reflexivity[edit]

If Y \subseteq X, then X \to Y

Axiom of augmentation[edit]

If X \to Y, then XZ \to YZ for any Z

Axiom of transitivity[edit]

If X \to Y and Y \to Z, then X \to Z

Additional rules[edit]

These rules can be derived from above axioms.

Union[edit]

If X \to Y and X \to Z then X \to YZ

Decomposition[edit]

If X \to YZ then  X \to Y and  X \to Z

Pseudo transitivity[edit]

If A \to B and  BC \to D then  AC\to D

Armstrong relation[edit]

Given a set of functional dependencies F, the 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.[2]

External links[edit]

References[edit]

  1. ^ William Ward Armstrong: Dependency Structures of Data Base Relationships, page 580-583. IFIP Congress, 1974.
  2. ^ Beeri, C.; Dowd, M.; Fagin, R.; Statman, R. (1984). "On the Structure of Armstrong Relations for Functional Dependencies". Journal of the ACM 31: 30–46. doi:10.1145/2422.322414.  edit