Armstrong’s axioms – Wikipedia

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.^[1] The axioms are sound in generating only functional dependencies in the closure of a set of functional dependencies (denoted as

${displaystyle F^{+}}$

) when applied to that set (denoted as

${displaystyle F}$

). They are also complete in that repeated application of these rules will generate all functional dependencies in the closure

${displaystyle F^{+}}$

.

More formally, let

${displaystyle langle R(U),Frangle }$

denote a relational scheme over the set of attributes

${displaystyle U}$

with a set of functional dependencies

${displaystyle F}$

. We say that a functional dependency

${displaystyle f}$

is logically implied by

${displaystyle F}$

, and denote it with

${displaystyle Fmodels f}$

if and only if for every instance

${displaystyle r}$

of

${displaystyle R}$

that satisfies the functional dependencies in

${displaystyle F}$

,

${displaystyle r}$

also satisfies

${displaystyle f}$

. We denote by

${displaystyle F^{+}}$

the set of all functional dependencies that are logically implied by

${displaystyle F}$

.

Furthermore, with respect to a set of inference rules

${displaystyle A}$

, we say that a functional dependency

${displaystyle f}$

is derivable from the functional dependencies in

${displaystyle F}$

by the set of inference rules

${displaystyle A}$

, and we denote it by

${displaystyle Fvdash _{A}f}$

if and only if

${displaystyle f}$

is obtainable by means of repeatedly applying the inference rules in

${displaystyle A}$

to functional dependencies in

${displaystyle F}$

. We denote by

${displaystyle F_{A}^{*}}$

the set of all functional dependencies that are derivable from

${displaystyle F}$

by inference rules in

${displaystyle A}$

.

Then, a set of inference rules

${displaystyle A}$

is sound if and only if the following holds:

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

that is to say, we cannot derive by means of

${displaystyle A}$

functional dependencies that are not logically implied by

${displaystyle F}$

.
The set of inference rules

${displaystyle A}$

is said to be complete if the following holds:

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

more simply put, we are able to derive by

${displaystyle A}$

all the functional dependencies that are logically implied by

${displaystyle F}$

.

Axioms (primary rules)[edit]

Let

${displaystyle R(U)}$

be a relation scheme over the set of attributes

${displaystyle U}$

. Henceforth we will denote by letters

${displaystyle X}$

,

${displaystyle Y}$

,

${displaystyle Z}$

any subset of

${displaystyle U}$

and, for short, the union of two sets of attributes

${displaystyle X}$

and

${displaystyle Y}$

by

${displaystyle XY}$

instead of the usual

${displaystyle Xcup Y}$

; this notation is rather standard in database theory when dealing with sets of attributes.

Axiom of reflexivity[edit]

If

${displaystyle X}$

is a set of attributes and

${displaystyle Y}$

is a subset of

${displaystyle X}$

, then

${displaystyle X}$

holds

${displaystyle Y}$

. Hereby,

${displaystyle X}$

holds

${displaystyle Y}$

[

${displaystyle Xto Y}$

] means that

${displaystyle X}$

functionally determines

${displaystyle Y}$

.

If

${displaystyle Ysubseteq X}$

then

${displaystyle Xto Y}$

.

Axiom of augmentation[edit]

If

${displaystyle X}$

holds

${displaystyle Y}$

and

${displaystyle Z}$

is a set of attributes, then

${displaystyle XZ}$

holds

${displaystyle YZ}$

. It means that attribute in dependencies does not change the basic dependencies.

If

${displaystyle Xto Y}$

, then

${displaystyle XZto YZ}$

for any

${displaystyle Z}$

.

Axiom of transitivity[edit]

If

${displaystyle X}$

holds

${displaystyle Y}$

and

${displaystyle Y}$

holds

${displaystyle Z}$

, then

${displaystyle X}$

holds

${displaystyle Z}$

.

If

${displaystyle Xto Y}$

and

${displaystyle Yto Z}$

, then

${displaystyle Xto Z}$

.

Additional rules (Secondary Rules)[edit]

These rules can be derived from the above axioms.

Decomposition[edit]

If

${displaystyle Xto YZ}$

then

${displaystyle Xto Y}$

and

${displaystyle Xto Z}$

.

Proof[edit]

1. ${displaystyle Xto YZ}$	(Given)
2. ${displaystyle YZto Y}$	(Reflexivity)
3. ${displaystyle Xto Y}$	(Transitivity of 1 & 2)

Composition[edit]

If

${displaystyle Xto Y}$

and

${displaystyle Ato B}$

then

${displaystyle XAto YB}$

.

Proof[edit]

Union (Notation)[edit]

If

${displaystyle Xto Y}$

and

${displaystyle Xto Z}$

then

${displaystyle Xto YZ}$

.

Proof[edit]

Pseudo transitivity[edit]

If

${displaystyle Xto Y}$

and

${displaystyle YZto W}$

then

${displaystyle XZto W}$

.

Proof[edit]

1. ${displaystyle Xto Y}$	(Given)
2. ${displaystyle YZto W}$	(Given)
3. ${displaystyle XZto YZ}$	(Augmentation of 1 & Z)
4. ${displaystyle XZto W}$	(Transitivity of 3 and 2)

Self determination[edit]

${displaystyle Ito I}$

for any

${displaystyle I}$

. This follows directly from the axiom of reflexivity.

Extensivity[edit]

The following property is a special case of augmentation when

${displaystyle Z=X}$

.

If

${displaystyle Xto Y}$

, then

${displaystyle Xto XY}$

.

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

Proof[edit]

Armstrong relation[edit]

Given a set of functional dependencies

${displaystyle F}$

, an Armstrong relation is a relation which satisfies all the functional dependencies in the closure

${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]

References[edit]

External links[edit]