An Algebraic Theory of Relational Databases

The existing theory of relational databases is based on Codd's relational model of data.1,2 This relational database theory can be considered to be the study of data dependencies (or independencies). * Bell Laboratories. °Copyright 1983, American Telephone & Telegraph Company. Photo reproduction for noncommercial use is permitted without payment of royalty provided that each reproduction is done without alteration and that the Journal reference and copyright notice are included on the first page. The title and abstract, but no other portions, of this paper may be copied or distributed royalty free by computer-based and other information-service systems without further permission. Permission to reproduce or republish any other portion of this paper must be obtained from the Editor. 3159 The theory was initiated by Codd with the introduction of the concept of functional dependency; Codd observed that this concept can be used to design better, normalized, database schemes. The advantage of normalized database schemes is that they remove the possibility of updating anomalies caused by undesirable data dependencies.2-5 In the existing theory of logical database design, functional dependencies are input constraints that must always hold in the relation.6 In the present paper, however, we take a different approach. We assume that for a particular database designer, there exists a (finite) universal relation R[U] for a given set of attributes fi, such that any relation T on 12 is a subset of R[Q].