Accession Number : ADA324622

Title :   The Equivalence of Universal Relation Definitions.

Corporate Author : STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Ullman, Jeffrey D. ; Vardi, Moshe Y. ; Maier, David

PDF Url : ADA324622

Report Date : OCT 1982

Pagination or Media Count : 28

Abstract : The universal relation model aims at achieving complete access path independence by relieving the user of the need for logical navigation among relations. It assumes that for every set of attributes there is a basic relationship that the user has in mind. Two fundamentally different approaches to the universal relation model have been taken. The first approach sees the universal relation as a user view, about which he poses queries. Specifically, a representative instance is constructed, and queries are answered based on its non-null part. The second approach sees the model as having query-processing capabilities that relieve the user of the need to specify the logical access path. The relationship between the user's view and the computation answering a query is a central issue that systems supporting a universal view of data must handle. We introduce lossless and monotone expressions and show that the representative instance construction has these properties. Also, every lossless monotone expression produces a result that is a subset of what the representative instance produces. We show that the existence of any first-order formula to simulate the representative instance is equivalent to a boundedness condition on the dependencies defining the database scheme. In addition, whenever there is a first-order formula to simulate the representative instance, then we can do so with an expression of simple form: the union of tableau mappings. We close with a discussion of some of the problems with the representative instance approach that suggest better universal relation models may be possible.

Descriptors :   *DATA BASES, OPTIMIZATION, DATA MANAGEMENT, COMPUTER COMMUNICATIONS, COMPUTER LOGIC.

Subject Categories : Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE