Armstrong's axioms

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

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 $Y \subseteq X$ then $X \to Y$

Axiom of augmentation

If $X \to Y$, then $X Z \to Y Z$ for any $Z$

Axiom of transitivity

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

Additional rules

These rules can be derived from above axioms.

Union

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

Decomposition

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

Pseudo transitivity

If $X \to Y$ and $YZ \to W$ then $XZ\to 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.^[2]

External links

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

References

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" (PDF). Journal of the ACM 31: 30–46. doi:10.1145/2422.322414.