Volume 14, 2002

University of Bialystok

Copyright (c) 2002 Association of Mizar Users

**William W. Armstrong**- Dendronic Decisions Ltd, Edmonton
**Yatsuka Nakamura**- Shinshu University, Nagano
**Piotr Rudnicki**- University of Alberta, Edmonton

- 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.

- Preliminaries
- The Relational Model of Data
- Dependency Structures
- Full Families of Dependencies
- Maximal Elements of Full Families
- Saturated Subsets of Attributes
- Justification of the Axioms
- Structure of the Family of Candidate Keys
- Applications

- [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.

[ Download a postscript version, MML identifier index, Mizar home page]