Armstrong's axioms

Armstrong's axioms are a set of references (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 [math]\displaystyle{ F^{+} }[/math]) when applied to that set (denoted as [math]\displaystyle{ F }[/math]). They are also complete in that repeated application of these rules will generate all functional dependencies in the closure [math]\displaystyle{ F^+ }[/math]. More formally, let [math]\displaystyle{ \langle R(U), F \rangle }[/math] denote a relational scheme over the set of attributes [math]\displaystyle{ U }[/math] with a set of functional dependencies [math]\displaystyle{ F }[/math]. We say that a functional dependency [math]\displaystyle{ f }[/math] is logically implied by [math]\displaystyle{ F }[/math], and denote it with [math]\displaystyle{ F \models f }[/math] if and only if for every instance [math]\displaystyle{ r }[/math] of [math]\displaystyle{ R }[/math] that satisfies the functional dependencies in [math]\displaystyle{ F }[/math], [math]\displaystyle{ r }[/math] also satisfies [math]\displaystyle{ f }[/math]. We denote by [math]\displaystyle{ F^{+} }[/math] the set of all functional dependencies that are logically implied by [math]\displaystyle{ F }[/math].

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

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

[math]\displaystyle{ F^{*}_{A} \subseteq F^{+} }[/math]

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

[math]\displaystyle{ F^{+} \subseteq F^{*}_{A} }[/math]

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

Axioms (primary rules)

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

Axiom of reflexivity

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

If [math]\displaystyle{ Y \subseteq X }[/math] then [math]\displaystyle{ X \to Y }[/math].

Axiom of augmentation

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

If [math]\displaystyle{ X \to Y }[/math], then [math]\displaystyle{ X Z \to Y Z }[/math] for any [math]\displaystyle{ Z }[/math].

Axiom of transitivity

If [math]\displaystyle{ X }[/math] holds [math]\displaystyle{ Y }[/math] and [math]\displaystyle{ Y }[/math] holds [math]\displaystyle{ Z }[/math], then [math]\displaystyle{ X }[/math] holds [math]\displaystyle{ Z }[/math].

If [math]\displaystyle{ X \to Y }[/math] and [math]\displaystyle{ Y \to Z }[/math], then [math]\displaystyle{ X \to Z }[/math].

Additional rules (Secondary Rules)

These rules can be derived from the above axioms.

Decomposition

If [math]\displaystyle{ X \to Y Z }[/math] then [math]\displaystyle{ X \to Y }[/math] and [math]\displaystyle{ X \to Z }[/math].

Proof

1. [math]\displaystyle{ X \to Y Z }[/math]	(Given)
2. [math]\displaystyle{ Y Z \to Y }[/math]	(Reflexivity)
3. [math]\displaystyle{ X \to Y }[/math]	(Transitivity of 1 & 2)

Composition

If [math]\displaystyle{ X \to Y }[/math] and [math]\displaystyle{ A \to B }[/math] then [math]\displaystyle{ X A \to Y B }[/math].

Proof

1. [math]\displaystyle{ X \to Y }[/math]	(Given)
2. [math]\displaystyle{ A \to B }[/math]	(Given)
3. [math]\displaystyle{ X A \to Y A }[/math]	(Augmentation of 1 & A)
4. [math]\displaystyle{ X A \to Y }[/math]	(Decomposition of 3)
5. [math]\displaystyle{ X A \to X B }[/math]	(Augmentation 2 & X)
6. [math]\displaystyle{ X A \to B }[/math]	(Decomposition of 5)
7. [math]\displaystyle{ X A \to Y B }[/math]	(Union 4 & 6)

Union

If [math]\displaystyle{ X \to Y }[/math] and [math]\displaystyle{ X \to Z }[/math] then [math]\displaystyle{ X \to YZ }[/math].

Proof

1. [math]\displaystyle{ X \to Y }[/math]	(Given)
2. [math]\displaystyle{ X \to Z }[/math]	(Given)
3. [math]\displaystyle{ X \to X Z }[/math]	(Augmentation of 2 & X)
4. [math]\displaystyle{ X Z \to Y Z }[/math]	(Augmentation of 1 & Z)
5. [math]\displaystyle{ X \to Y Z }[/math]	(Transitivity of 3 and 4)

Pseudo transitivity

If [math]\displaystyle{ X \to Y }[/math] and [math]\displaystyle{ Y Z \to W }[/math] then [math]\displaystyle{ X Z\to W }[/math].

Proof

1. [math]\displaystyle{ X \to Y }[/math]	(Given)
2. [math]\displaystyle{ Y Z \to W }[/math]	(Given)
3. [math]\displaystyle{ X Z \to Y Z }[/math]	(Augmentation of 1 & Z)
4. [math]\displaystyle{ X Z \to W }[/math]	(Transitivity of 3 and 2)

Self determination

[math]\displaystyle{ I \to I }[/math] for any [math]\displaystyle{ I }[/math]. This follows directly from the axiom of reflexivity.

Extensivity

The following property is a special case of augmentation when [math]\displaystyle{ Z=X }[/math].

If [math]\displaystyle{ X \to Y }[/math], then [math]\displaystyle{ X \to X Y }[/math].

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

Proof

1. [math]\displaystyle{ X Z \to X }[/math]	(Reflexivity)
2. [math]\displaystyle{ X \to Y }[/math]	(Given)
3. [math]\displaystyle{ X Z \to Y }[/math]	(Transitivity of 1 & 2)
4. [math]\displaystyle{ X Z \to X Y Z }[/math]	(Extensivity of 3)
5. [math]\displaystyle{ X Y Z \to Y Z }[/math]	(Reflexivity)
6. [math]\displaystyle{ X Z \to Y Z }[/math]	(Transitivity of 4 & 5)

Armstrong relation

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

External links

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