Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-28T19:46:26.460Z Has data issue: false hasContentIssue false

A categorical approach to database semantics

Published online by Cambridge University Press:  04 March 2009

Kenneth Baclawski
Affiliation:
Northeastern University, College of Computer Science, Boston, Massachusetts 02115
Dan Simovici
Affiliation:
University of Massachusetts at Boston, Department of Mathematics and Computer Science, Boston, Massachusetts 02125
William White
Affiliation:
Intermetrics, Inc., Cambridge, Massachusetts

Abstract

We propose a formalization of standard database management systems using topos theory. In this treatment, all constructions take place within an ambient topos, which thereby serves as the ‘universe of discourse’. A database schema is defined using objects and morphisms in the ambient topos. A database state for a given schema involves not only the ambient topos but also an internal category within the topos. This approach neatly separates the schema from the state data by placing them in distinct category structures. It is shown that database states can either be regarded syntactically as objects in an external topos or semantically as morphisms in an internal slice category. A number of operations are introduced that correspond to operations used in standard database systems. Extraction selects some of the tables, attributes and domains of a database state. The squeeze operation performs an ‘elimination of duplicates’, which can be combined with extraction to obtain an operation called ‘projection’ in standard relational database systems. A join operation is defined, which generalizes the relational join operation and can be used for the cartesian product and selection operations. Finally, ‘boolean’ operations of intersection, union and difference are introduced and related to the other operations.

Type
Research Article
Copyright
Copyright © Cambridge University Press 1994

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Asperti, A. and Longo, G. (1991) Categories, Types, and Structures, The MIT Press, Cambridge, MA.Google Scholar
Barr, M. and Wells, C. (1990) Category Theory for Computing Science, Prentice-Hall, Englewood Cliffs, NJ.Google Scholar
Freyd, P. (1972) Aspects of topoi. Bull. Australian Math. Soc. 7 176.CrossRefGoogle Scholar
Goldblatt, R. (1979) Topoi - The Categorical Analysis of Logic, North-Holland, Amsterdam.Google Scholar
Hughes, J. G. (1988) Database Technology, a software engineering approach, Prentice-Hall, New York.Google Scholar
Johnstone, P. (1977) Topos Theory, Academic Press, London.Google Scholar
Mac Lane, S. (1971) Categories for the Working Mathematician, Springer-Verlag, Berlin.CrossRefGoogle Scholar
Thomas, S. J. and Fisher, P. C. (1986) Nested relational structures. In: Kanellakis, P. C. (ed.) Advances in Computing Research 3 269308.Google Scholar
Ullman, J. D. (1988) Principles of Database and Knowledge-Base Systems, vol. 1, Computer Science Press, Rockville, Maryland.Google Scholar
Vossen, G. (1991) Data Models, Database Languages and Database Management Systems, Addison Wesley, Reading, MA.Google Scholar