Armstrong's axioms explained

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

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 (primary rules)

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 [<math>X \to Y</math>] 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

1. X \to Y Z	(Given)
2. Y Z \to Y	(Reflexivity)
3. X \to Y	(Transitivity of 1 & 2)

Composition

If

X \to Y and A \to B then X A \to Y B .

Proof

1. X \to Y	(Given)
2. A \to B	(Given)
3. X A \to Y A	(Augmentation of 1 & A)
4. X A \to Y	(Decomposition of 3)
5. X A \to X B	(Augmentation of 2 & X)
6. X A \to B	(Decomposition of 5)
7. X A \to Y B	(Union 4 & 6)

Union

If

X \to Y and X \to Z then X \to YZ .

Proof

1. X \to Y	(Given)
2. X \to Z	(Given)
3. X \to X Z	(Augmentation of 2 & X)
4. X Z \to Y Z	(Augmentation of 1 & Z)
5. X \to Y Z	(Transitivity of 3 and 4)

Pseudo transitivity

If

X \to Y and Y Z \to W then X Z\to W .

Proof

1. X \to Y	(Given)
2. Y Z \to W	(Given)
3. X Z \to Y Z	(Augmentation of 1 & Z)
4. XZ \to W	(Transitivity of 3 and 2)

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

1. X Z \to X	(Reflexivity)
2. X \to Y	(Given)
3. X Z \to Y	(Transitivity of 1 & 2)
4. X Z \to X Y Z	(Extensivity of 3)
5. X Y Z \to Y Z	(Reflexivity)
6. X Z \to Y Z	(Transitivity of 4 & 5)

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]

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 . 10.1145/2422.322414 . Journal of the ACM . 10.1.1.68.9320 . 31 . 30–46 . https://web.archive.org/web/20180723025708/https://researcher.watson.ibm.com/researcher/files/us-fagin/jacm84.pdf . 2018-07-23 .

External links

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