Armstrong's axioms

From Wikipedia, the free encyclopedia

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.^[1] The axioms are sound in generating only functional dependencies in the closure of a set of functional dependencies (denoted as ${\displaystyle F^{+}}${\displaystyle F^{+}}) when applied to that set (denoted as ${\displaystyle F}${\displaystyle F}). They are also complete in that repeated application of these rules will generate all functional dependencies in the closure ${\displaystyle F^{+}}${\displaystyle F^{+}}.

More formally, let ${\displaystyle \langle R(U),F\rangle }${\displaystyle \langle R(U),F\rangle } denote a relational scheme over the set of attributes ${\displaystyle U}${\displaystyle U} with a set of functional dependencies ${\displaystyle F}${\displaystyle F}. We say that a functional dependency ${\displaystyle f}${\displaystyle f} is logically implied by ${\displaystyle F}${\displaystyle F}, and denote it with ${\displaystyle F\models f}${\displaystyle F\models f} if and only if for every instance ${\displaystyle r}${\displaystyle r} of ${\displaystyle R}${\displaystyle R} that satisfies the functional dependencies in ${\displaystyle F}${\displaystyle F}, ${\displaystyle r}${\displaystyle r} also satisfies ${\displaystyle f}${\displaystyle f}. We denote by ${\displaystyle F^{+}}${\displaystyle F^{+}} the set of all functional dependencies that are logically implied by ${\displaystyle F}${\displaystyle F}.

Furthermore, with respect to a set of inference rules ${\displaystyle A}${\displaystyle A}, we say that a functional dependency ${\displaystyle f}${\displaystyle f} is derivable from the functional dependencies in ${\displaystyle F}${\displaystyle F} by the set of inference rules ${\displaystyle A}${\displaystyle A}, and we denote it by ${\displaystyle F\vdash _{A}f}${\displaystyle F\vdash _{A}f} if and only if ${\displaystyle f}${\displaystyle f} is obtainable by means of repeatedly applying the inference rules in ${\displaystyle A}${\displaystyle A} to functional dependencies in ${\displaystyle F}${\displaystyle F}. We denote by ${\displaystyle F_{A}^{*}}${\displaystyle F_{A}^{*}} the set of all functional dependencies that are derivable from ${\displaystyle F}${\displaystyle F} by inference rules in ${\displaystyle A}${\displaystyle A}.

Then, a set of inference rules ${\displaystyle A}${\displaystyle A} is sound if and only if the following holds:

${\displaystyle F_{A}^{*}\subseteq F^{+}}${\displaystyle F_{A}^{*}\subseteq F^{+}}

that is to say, we cannot derive by means of ${\displaystyle A}${\displaystyle A} functional dependencies that are not logically implied by ${\displaystyle F}${\displaystyle F}. The set of inference rules ${\displaystyle A}${\displaystyle A} is said to be complete if the following holds:

${\displaystyle F^{+}\subseteq F_{A}^{*}}${\displaystyle F^{+}\subseteq F_{A}^{*}}

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

Let ${\displaystyle R(U)}${\displaystyle R(U)} be a relation scheme over the set of attributes ${\displaystyle U}${\displaystyle U}. Henceforth we will denote by letters ${\displaystyle X}${\displaystyle X}, ${\displaystyle Y}${\displaystyle Y}, ${\displaystyle Z}${\displaystyle Z} any subset of ${\displaystyle U}${\displaystyle U} and, for short, the union of two sets of attributes ${\displaystyle X}${\displaystyle X} and ${\displaystyle Y}${\displaystyle Y} by ${\displaystyle XY}${\displaystyle XY} instead of the usual ${\displaystyle X\cup Y}${\displaystyle X\cup Y}; this notation is rather standard in database theory when dealing with sets of attributes.

If ${\displaystyle X}${\displaystyle X} is a set of attributes and ${\displaystyle Y}${\displaystyle Y} is a subset of ${\displaystyle X}${\displaystyle X}, then ${\displaystyle X}${\displaystyle X} holds ${\displaystyle Y}${\displaystyle Y}. Hereby, ${\displaystyle X}${\displaystyle X} holds ${\displaystyle Y}${\displaystyle Y} [${\displaystyle X\to Y}${\displaystyle X\to Y}] means that ${\displaystyle X}${\displaystyle X} functionally determines ${\displaystyle Y}${\displaystyle Y}.

If ${\displaystyle Y\subseteq X}${\displaystyle Y\subseteq X} then ${\displaystyle X\to Y}${\displaystyle X\to Y}.

If ${\displaystyle X}${\displaystyle X} holds ${\displaystyle Y}${\displaystyle Y} and ${\displaystyle Z}${\displaystyle Z} is a set of attributes, then ${\displaystyle XZ}${\displaystyle XZ} holds ${\displaystyle YZ}${\displaystyle YZ}. It means that attribute in dependencies does not change the basic dependencies.

If ${\displaystyle X\to Y}${\displaystyle X\to Y}, then ${\displaystyle XZ\to YZ}${\displaystyle XZ\to YZ} for any ${\displaystyle Z}${\displaystyle Z}.

If ${\displaystyle X}${\displaystyle X} holds ${\displaystyle Y}${\displaystyle Y} and ${\displaystyle Y}${\displaystyle Y} holds ${\displaystyle Z}${\displaystyle Z}, then ${\displaystyle X}${\displaystyle X} holds ${\displaystyle Z}${\displaystyle Z}.

If ${\displaystyle X\to Y}${\displaystyle X\to Y} and ${\displaystyle Y\to Z}${\displaystyle Y\to Z}, then ${\displaystyle X\to Z}${\displaystyle X\to Z}.

These rules can be derived from the above axioms.

If ${\displaystyle X\to YZ}${\displaystyle X\to YZ} then ${\displaystyle X\to Y}${\displaystyle X\to Y} and ${\displaystyle X\to Z}${\displaystyle X\to Z}.

If ${\displaystyle X\to Y}${\displaystyle X\to Y} and ${\displaystyle A\to B}${\displaystyle A\to B} then ${\displaystyle XA\to YB}${\displaystyle XA\to YB}.

If ${\displaystyle X\to Y}${\displaystyle X\to Y} and ${\displaystyle X\to Z}${\displaystyle X\to Z} then ${\displaystyle X\to YZ}${\displaystyle X\to YZ}.

If ${\displaystyle X\to Y}${\displaystyle X\to Y} and ${\displaystyle YZ\to W}${\displaystyle YZ\to W} then ${\displaystyle XZ\to W}${\displaystyle XZ\to W}.

${\displaystyle I\to I}${\displaystyle I\to I} for any ${\displaystyle I}${\displaystyle I}. This follows directly from the axiom of reflexivity.

The following property is a special case of augmentation when ${\displaystyle Z=X}${\displaystyle Z=X}.

If ${\displaystyle X\to Y}${\displaystyle X\to Y}, then ${\displaystyle X\to XY}${\displaystyle X\to XY}.

Extensivity can replace augmentation as axiom in the sense that augmentation can be proved from extensivity together with the other axioms.

Given a set of functional dependencies ${\displaystyle F}${\displaystyle F}, an Armstrong relation is a relation which satisfies all the functional dependencies in the closure ${\displaystyle F^{+}}${\displaystyle 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]

• UMBC CMSC 461 Spring '99
• CS345 Lecture Notes from Stanford University

Retrieved from "https://en.wikipedia.org/w/index.php?title=Armstrong%27s_axioms&oldid=1261382843"

Categories:

• Database normalization
• Data modeling
• Database management systems