Using Powerdomains to Generalize Relational Databases

Peter Buneman, Achim Jung, Atsushi Ohori

Research output: Contribution to journalArticlepeer-review


Much of relational algebra and the underlying principles of relational database design have a simple representation in the theory of domains that is traditionally used in the denotational semantics of programming languages. By investigating the possible orderings on powerdomains that are well known in the study of nondeterminism and concurrency it is possible to show that many of the ideas in relational databases apply to structures that are much more general than relations. This also suggests a method of representing database objects as typed objects in programming languages.

In this paper we show how operations such as natural join and projection—which are fundamental to relational database design—can be generalized, and we use this generalized framework to give characterizations of several relational database concepts including functional dependencies and universal relations. All of these have a simple-minded semantics in terms of the underlying domains, which can be thought of as domains of partial descriptions of “real-world” objects. We also discuss the applicability of relational database theory to nonrelational structures such as records with variants, higher-order relations, recursive structures and other ordered spaces.
Original languageEnglish
Pages (from-to)23-55
Number of pages33
JournalTheoretical Computer Science
Issue number1
Publication statusPublished - 1991


Dive into the research topics of 'Using Powerdomains to Generalize Relational Databases'. Together they form a unique fingerprint.

Cite this