Armstrong's 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 X \cup Y; this notation is rather standard in database theory when dealing with sets of attributes. Axiom of reflexivity If X is a set of attributes and Y is a subset of X, then X holds Y. Hereby, X holds Y [X \to Y] means that X functionally determines Y. :If Y \subseteq X then X \to Y. Axiom of augmentation If X holds Y and Z is a set of attributes, then X Z holds Y Z. It means that attribute in dependencies does not change the basic dependencies. :If X \to Y, then X Z \to Y Z for any Z. Axiom of transitivity If X holds Y and Y holds Z, then X holds Z. :If X \to Y and Y \to Z, then X \to Z. ==Additional rules (Secondary Rules)==

These rules can be derived from the above axioms. Decomposition If X \to Y Z then X \to Y and X \to Z. Proof Composition If X \to Y and A \to B then X A \to Y B. Proof Union If X \to Y and X \to Z then X \to YZ. Proof Pseudo transitivity If X \to Y and Y Z \to W then X Z\to W. Proof Self determination I \to I for any I. This follows directly from the axiom of reflexivity. Extensivity The following property is a special case of augmentation when Z=X. :If X \to Y, then X \to X Y. Extensivity can replace augmentation as axiom in the sense that augmentation can be proved from extensivity together with the other axioms. Proof ==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. 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==