Armstrong's Axioms

William W. Armstrong

Dendronic Decisions Ltd, Edmonton

Yatsuka Nakamura

Shinshu University, Nagano

Piotr Rudnicki

University of Alberta, Edmonton

Summary.

We present a formalization of the seminal paper by W.~W.~Armstrong~[1] on functional dependencies in relational data bases. The paper is formalized in its entirety including examples and applications. The formalization was done with a routine effort albeit some new notions were defined which simplified formulation of some theorems and proofs.\par The definitive reference to the theory of relational databases is~[16], where saturated sets are called closed sets. Armstrong's ``axioms'' for functional dependencies are still widely taught at all levels of database design, see for instance~[14].

This work has been supported by NSERC Grant OGP9207 and Shinshu Endowment Fund.

MML Identifier: ARMSTRNG

Contents (PDF format)

1. Preliminaries
2. The Relational Model of Data
3. Dependency Structures
4. Full Families of Dependencies
5. Maximal Elements of Full Families
6. Saturated Subsets of Attributes
7. Justification of the Axioms
8. Structure of the Family of Candidate Keys
9. Applications

Bibliography

[1] W. W. Armstrong. \em Dependency Structures of Data Base Relationships. Information Processing 74, North Holland, 1974.

[2] Grzegorz Bancerek. Cardinal numbers. Journal of Formalized Mathematics, 1, 1989.

[3] Grzegorz Bancerek. The fundamental properties of natural numbers. Journal of Formalized Mathematics, 1, 1989.

[4] Grzegorz Bancerek. K\"onig's theorem. Journal of Formalized Mathematics, 2, 1990.

[5] Grzegorz Bancerek and Krzysztof Hryniewiecki. Segments of natural numbers and finite sequences. Journal of Formalized Mathematics, 1, 1989.

[6] Czeslaw Bylinski. Functions and their basic properties. Journal of Formalized Mathematics, 1, 1989.

[7] Czeslaw Bylinski. Functions from a set to a set. Journal of Formalized Mathematics, 1, 1989.

[8] Czeslaw Bylinski. Partial functions. Journal of Formalized Mathematics, 1, 1989.

[9] Czeslaw Bylinski. Some basic properties of sets. Journal of Formalized Mathematics, 1, 1989.

[10] Czeslaw Bylinski. Finite sequences and tuples of elements of a non-empty sets. Journal of Formalized Mathematics, 2, 1990.

[11] Czeslaw Bylinski. The modification of a function by a function and the iteration of the composition of a function. Journal of Formalized Mathematics, 2, 1990.

[12] Agata Darmochwal. Finite sets. Journal of Formalized Mathematics, 1, 1989.

[13] Agata Darmochwal. The Euclidean space. Journal of Formalized Mathematics, 3, 1991.

[14] Ramez Elmasri and Shamkant B. Navathe. \em Fundamentals of Database Systems. Addison-Wesley, 2000.

[15] Adam Grabowski. Auxiliary and approximating relations. Journal of Formalized Mathematics, 8, 1996.

[16] David Maier. \em The Theory of Relational Databases. Computer Science Press, Rockville, 1983.

[17] Robert Milewski. Binary arithmetics. Binary sequences. Journal of Formalized Mathematics, 10, 1998.

[18] Takaya Nishiyama and Yasuho Mizuhara. Binary arithmetics. Journal of Formalized Mathematics, 5, 1993.

[19] Beata Padlewska. Families of sets. Journal of Formalized Mathematics, 1, 1989.

[20] Konrad Raczkowski and Andrzej Nedzusiak. Series. Journal of Formalized Mathematics, 3, 1991.

[21] Alexander Yu. Shibakov and Andrzej Trybulec. The Cantor set. Journal of Formalized Mathematics, 7, 1995.

[22] Andrzej Trybulec. Tarski Grothendieck set theory. Journal of Formalized Mathematics, Axiomatics, 1989.

[23] Andrzej Trybulec. Tuples, projections and Cartesian products. Journal of Formalized Mathematics, 1, 1989.

[24] Andrzej Trybulec. Many-sorted sets. Journal of Formalized Mathematics, 5, 1993.

[25] Andrzej Trybulec. Subsets of real numbers. Journal of Formalized Mathematics, Addenda, 2003.

[26] Andrzej Trybulec and Agata Darmochwal. Boolean domains. Journal of Formalized Mathematics, 1, 1989.

[27] Wojciech A. Trybulec. Partially ordered sets. Journal of Formalized Mathematics, 1, 1989.

[28] Wojciech A. Trybulec. Pigeon hole principle. Journal of Formalized Mathematics, 2, 1990.

[29] Zinaida Trybulec. Properties of subsets. Journal of Formalized Mathematics, 1, 1989.

[30] Edmund Woronowicz. Relations and their basic properties. Journal of Formalized Mathematics, 1, 1989.

[31] Edmund Woronowicz. Relations defined on sets. Journal of Formalized Mathematics, 1, 1989.

[32] Edmund Woronowicz. Many-argument relations. Journal of Formalized Mathematics, 2, 1990.

[33] Edmund Woronowicz and Anna Zalewska. Properties of binary relations. Journal of Formalized Mathematics, 1, 1989.