Edinburgh Research Explorer

Using Powerdomains to Generalize Relational Databases

Research output: Contribution to journalArticle

Related Edinburgh Organisations

Open Access permissions

Open

Documents

Original languageEnglish
Pages (from-to)23-55
Number of pages33
JournalTheoretical Computer Science
Volume91
Issue number1
DOIs
Publication statusPublished - 1991

Abstract

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.

Download statistics

No data available

ID: 10624838