Databases
Since Codd introduced the relational database model and functional dependencies [Codd 1970], the semantics of relationships between the attributes of a database has been extensively studied by many computer scientists. In this chapter we introduce an appl
- PDF / 1,890,933 Bytes
- 17 Pages / 439.364 x 666.137 pts Page_size
- 42 Downloads / 217 Views
Relation Algebras Roger D. Maddux
The contemporary theory of relation algebras is a direct outgrowth of the nineteenth century calculus of relations. After a few examples illustrating the calculus of relations (the most widely applied part of the subject), this chapter touches upon some topics in the algebraic theory of relation algebras: basic definitions, examples, constructions, elementary arithmetical theory, general algebraic results, representation theorems with applications, and connections with logic, including Tarski's formalization of set theory without variables.
2.1
The calculus of binary relations
The calculus of relations was invented and developed by De Morgan, Peirce, and Schroder. The study of binary relations and various binary and unary operations on binary relations was started by Augustus De Morgan in [De Morgan 1856) and [De Morgan 1864), who did so in order to expand the compass of classical Aristotelian syllogistic reasoning. Following the example set by George Boole in [Boole 1847), Charles Sanders Peirce created algebraic formalisms out of De Morgan's ideas in [Peirce 1870), [Peirce 1880), [Peirce 1883), [Peirce 1885), and other papers, including some first published only recently in [Peirce 1984). He invented calculi for properties, binary relations, ternary relations, and relations of higher ranks, including many operations (and notations for operations) on relations of various ranks. Peirce's "Note B" of 1883 [Peirce 1883) lays out a single formalism, based exclusively on binary relations, with a few dozen of its laws. This algebraic system was extensively developed and applied by F. W. K. Ernst Schroder in his classic 649-page book [Schroder 1895), Vorlesungen tiber die Algebra der Logik (exacte Logik), Volume 3, "Algebra und Logik der Relative", part I, published in Leipzig in 1895. A fragment of the Peirce-Schroder calculus of binary relations was axiomatized by Alfred Tarski [Tarski 1941). One of Tarski's axioms is not an equation, and the class of algebras satisfying his axioms is not closed under the formation of direct products, so it is not a variety. The variety of relation algebras is the class of algebras that satisfy all but the offending axiom. A definition of relation algebras first appeared in [Jonsson, Tarski 1948), followed shortly thereafter by equivalent definitions in [Chin, Tarski 1951) and [Jonsson, Tarski 1952J. An equational axC. Brink et al. (eds.), Relational Methods in Computer Science © Springer-Verlag/Wien 1997
Chapter 2. Relation Algebras
23
iomatization of relation algebras is given in the next section. In this section we give a few examples illustrating uses of the calculus of binary relations. Consider a universe of discourse U with typical elements a, b, c, etc. Following De Morgan [De Morgan 1864], we let the capital letters L, M, N, etc., denote binary relations over U. We signify that a is in the relation L to b by writing aLb, and that the two relations Land M are the same by writing L = M. Let I be the identity relation On U and let V = U x
Data Loading...
