Chris Brink, Wolfram Kahl, Gunther Schmidt (eds)
Advances in Computer Science,
Springer-Verlag Vienna 1997,
ISBN 3-211-82971-7
(.bib)
The calculus of relations has been an important component of the development of logic and algebra since the middle of the nineteenth century, when Augustus De Morgan observed that since a horse is an animal we should be able to infer that the head of a horse is the head of an animal. For this, Aristotelian syllogistic does not suffice: We require relational reasoning.
George Boole, in his Mathematical Analysis of Logic of 1847, initiated the treatment of logic as part of mathematics, specifically as part of algebra. Quite the opposite conviction was put forward early this century by Bertrand Russell and Alfred North Whitehead in their Principia Mathematica (1910 -- 1913): that mathematics was essentially grounded in logic. Logic thus developed in two streams.
On the one hand algebraic logic, in which the calculus of relations played a particularly prominent part, was taken up from Boole by Charles Sanders Peirce, who wished to do for the ``calculus of relatives'' what Boole had done for the calculus of sets. Peirce's work was in turn taken up by Schröder in his Algebra und Logik der Relative of 1895 (the third part of a massive work on the algebra of logic). Schröder's work, however, lay dormant for more than 40 years, until revived by Alfred Tarski in his seminal paper ``On the calculus of binary relations'' of 1941 (actually his presidential address to the Association for Symbolic Logic). Tarski's paper is still often referred to today as the best introduction to the calculus of relations. It gave rise to a whole field of study, that of relation algebras, and more generally Boolean algebras with operators. These formed part of the study of algebraic logic, which in its modern form overlaps with universal algebra, model theory, nonclassical logics, and more recently program semantics and program development.
In the other stream of development, the theory of relations was accorded a key role in Principia Mathematica. This important work defined much of the subsequent development of logic in the 20th century, completely eclipsing for some time the development of algebraic logic. In this stream of development, relational calculus and relational methods appear with the development of universal algebra in the 1930's, and again with model theory from the 1950's onwards. In so far as these disciplines in turn overlapped with the development of category theory, relational methods sometimes appear in this context as well.
It is fair to say that the role of the calculus of relations in the interaction between algebra and logic is by now well understood and appreciated, and that relational methods are part of the toolbox of the mathematician and the logician. Over the past twenty years relational methods have however also become of fundamental importance in computer science. For example, much of the theory of nonclassical logics was used (though sometimes re-invented) in the new so-called program logics. These arose from the realisation that a program may be thought of as an input-output relation over some state space: an accessibility relation, in the sense of modal logic, saying that from a given initial state certain final states are accessible. Not every relation over a state space can be thought of as a program, but any relation can be thought of as a {\em specification} of a program. This point of view, that the calculus of relations is fundamental to programs, was clearly enunciated by the Oxford group of Tony Hoare in an influential paper on ``Laws of programming'' in 1987. Also during the 1980's, much of the equational theory of relation algebras were already being applied to program semantics and program development. For example, the book Relations and Graphs by Schmidt and Ströhlein (in German, 1989; in English, 1993) started from the basis of programs as graphs with Boolean matrices. On the other hand, a topic such as relational databases was an essentially new development, owing little to previous mathematical work on or with relations. Thus computer science, as the new application field for relational methods, has both drawn from and contributed to previous logico/mathematical work; this is a sign of healthy development.
However, the role of relational methods within computer science is not yet as well-known or well-understood as it is in logic and mathematics. It is the aim of this book to help address this situation, by giving an overview of relational methods in computer science. We have not tried to give an exhaustive survey -- indeed, part of what we claim is that the topic is already too large for an exhaustive survey to fit into one volume. We hope, however, that the topics included will suffice to convey an impression of the power and wide-ranging applicability of relational methods.
Just as we have attempted to bring together under one heading various disparate endeavours in using relational methods in computer science, so we have also attempted to bring together the researchers involved. It became clear to us in the early 1990's that a core group of researchers using or working on relational methods was turning up repeatedly at various specialist conferences. It seemed a good idea, therefore, to organise a meeting specifically on relational methods, so as to give all those who developed or used them in some area of computer science a chance to meet and talk across disciplinary boundaries. The outcome of this idea was the International Seminar on Relational Methods in Computer Science (later known as RelMiCS 1), held as Seminar 9403 at Schloß Dagstuhl in the Saarland in January 1994. We gratefully acknowledge the assistance of the Internationales Begegnungs- und Forschungszentrum für Informatik in organising and funding this Seminar. In our preface to the Seminar Report we said:
Since the mid-1970's it has become clear that the calculus of relations is a fundamental conceptual and methodological tool in computer science just as much as in mathematics. A number of seemingly distinct areas of research have in fact this much in common that their concepts and/or techniques come from the calculus of relations. However, it has also become clear that many opportunities for cross-pollination are being lost simply because there was no organised forum of discussion between researchers who, though they use the same concepts and methods, nonetheless perceive themselves as working in different fields.This has become a manifesto of sorts for what is now known as the RelMiCS Group. The idea of producing this book first originated at Dagstuhl, where a number of authors were recruited. Some subsequent organisational work was done from Cape Town and München, but the book only really took shape in Rio de Janeiro: first at a planning session in July 1994, then at the RelMiCS 2 meeting in July 1995. We are pleased to acknowledge our indebtedness to Armando Haeberer for organising these extremely pleasant and productive events. We gratefully acknowledge the financial assistance of CNPq (Conselho Nacional de Desenvolvimento Científico e Tecnológico) for the planning session of July 1994, and of FAPERJ (Fundação de Amparo à Pesquisa do Estado do Rio de Janeiro) and IBM Brazil for RelMiCS 2 in July 1995. It gave us the chance to ``workshop'' the contents of the book so as to increase the homogeneity of notation and terminology that we felt was desirable.The aim of this Dagstuhl Seminar was, therefore, to bring together researchers from various subdisciplines of computer science and mathematics, all of whom use relational methods in their work, and to encourage the creation of an active network continuing after the Seminar to exchange ideas and results.
In consequence, this is a multi-author book. However, though each chapter is written by a different set of authors, it has been our intention that the book should be more than just a collection of papers: it should have unity of style and presentation. In this way we hope that the spirit of bringing together topics and researchers is reflected also in the structure of the book itself.
Chapter 1 sets out the background material needed in the rest of the book, and the notation to be used. The problem of proliferation of different notations and terminology has been an impediment to communication about relational methods between various groups of researchers; it seems justified, therefore, to try, at least in a book like this, for a measure of coherence. After Chapt. 1, which forms the introductory Part I of the book, there are four more parts. Part II deals with current versions of algebras of relations, Part III with applications to logic, Part IV with applications to programming, and Part V with other application areas. For lack of space the Bibliography only contains works actually referred to in the text; a more comprehensive bibliography on the calculus of relations and its applications is available electronically.
Acknowledgements. In the original submissions for this book almost all authors acknowledged an indebtedness to other authors; we cover this by making here a blanket acknowledgement of thanks for mutual cooperation. We personally owe a large debt of thanks to Thomas Ströhlein, who undertook and carried out the arduous task of assembling a bibliography of relational methods based on submissions from several coauthors. The bibliography at the end of this book is a small subset of this comprehensive bibliography. In addition, we gratefully acknowledge work done on the manuscript by Arne Bayer, Thomas Gritzner, and Peter Kempf. We are grateful to Rudolf Albrecht for establishing contact with the publishers. Of course our largest debt is to the authors who actually wrote the book, and who submitted themselves with good grace to the editorial requirements we imposed on them.
With over 30 contributors to this book we believe it possible that some errors may remain; for these we crave the indulgence of the reader, and would be pleased to receive feedback.
Oktober 1996
Chris Brink Wolfram Kahl, Gunther Schmidt University of Cape Town Universität der Bundeswehr München