The revenge of the JD
Published 1 January 1983
David Maier, Jeffrey D. Ullman, Moshe Y. Vardi
Citations11
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
If the user's view is the representative instance, then the ability to answer queries about the universal relation, by applying relational algebra to the actual database, is equivalent to a "boundedness" condition on the dependencies of the database scheme.
Abstract
Manifestations of the "universal relation assumption" can be seen either as definitions of a one-relation user view of data, or as algorithms for answering queries about arbitrary sets of attributes. In this paper we explore equivalences between these two points of view. We show that if the user's view is the representative instance, then our ability to answer queries about the universal relation, by applying relational algebra to the actual database, is equivalent to a "boundedness" condition on the dependencies of the database scheme. Further, whenever this condition holds, there is a finite union of lossless tableau mappings that produces the desired relation.
Keywords
Computer Science
ACM Transactions on Database SystemsTesting implications of data dependencies
582 Citations1979David Maier, Alberto O. Mendelzon +1 more
The chase operates on tableaux similar to those of Aho, Sagiv, and Ullman so it is possible to test implication of join dependencies and functional dependencies by a set of dependencies.
Very Large Data BasesAlgorithms for acyclic database schemes
495 Citations1981Mihalis Yannakakis
The purpose in this paper is to describe efficient algorithms in this setting for various problems, such as computing projections, minimizing joins, inferring dependencies, and testing for dependency satisfaction.
ACM Transactions on Database SystemsSynthesizing third normal form relations from functional dependencies
449 Citations1976Philip A. Bernstein
An effective procedure for performing a relational scheme synthesis is presented and the schema that results from this procedure is proved to be in Codd's third normal form and to contain the fewest possible number of relations.
ACM Transactions on Database SystemsThe theory of joins in relational databases
423 Citations1979A. V. Aho, Catriel Beeri +1 more
An efficient algorithm to determine whether the join of several relations is semantically meaningful (lossless) and an efficient algorithm to determine whether a set of relations has a subset with a lossy join are given.
ACM Transactions on Database SystemsA simplied universal relation assumption and its properties
301 Citations1982Ronald Fagin, Alberto O. Mendelzon +1 more
This work proposes a simpler method of describing the real world, where constraints are given by functional dependencies and a single join dependency, and characterize in terms of hypergraphs those multivalued dependencies that are the consequence of a given join dependency.
ACM Transactions on Database SystemsEfficient optimization of a class of relational expressions
217 Citations1979A. V. Aho, Yehoshua Sagiv +1 more
The difficulty of optimizing queries based on the relational algebra operations select, project, and join is discussed, and a polynomial time algorithm exists to optimize tableaux that correspond to an important subclass of queries.
ACM Transactions on Database SystemsMaximal objects and the semantics of universal relation databases
150 Citations1983David Maier, Jeffrey D. Ullman
This work proposes a concept called maximal objects, which modifies the universal relation concept in exactly those situations where it appears to go awry—when the underlying relational structure has “cycles.”
Can we use the universal instance assumption without using nulls?
94 Citations1981Yehoshua Sagiv
It is claimed that the representative instance of [Ho1, Va3] is a correct representation of the data stored in a database even when the relations of the database are not the projections of a single universal instance.
Efficient optimization of a class of relational expressions
93 Citations1978Alfred V. Aho, Yehoshua Sagiv +1 more
The optimization problem is shown to be NP-complete, but a polynomial time algorithm can be given to optimize tableaux that correspond to an important subclass of expressions.
The U. R. strikes back
74 Citations1982Jeffrey D. Ullman
This paper taxonomize the varieties of ideas that are sometimes called the "universal relation assumption" and considers some of the arguments pro and con.
ACM Transactions on Database SystemsDatabase states and their tableaux
65 Citations1984Alberto O. Mendelzon
This work proposes the set of all weak instances for a state as an embodiment of the information represented by the state and characterize states that have the same set of weak instances by the equivalence of their associated tableaux.
Journal of the ACMTemplate Dependencies
62 Citations1982Fereidoon Sadri, Jeffrey D. Ullman
A more general class of dependencies, called "template dependencies," is detrmed in this paper, and a complete axiomatizatton for embedded multivalued dependencies is given.
Horn clauses and database dependencies (Extended Abstract)
50 Citations1980Ronald Fagin
The purpose of this paper is to help bring order to the chaos by presenting certain mathematical properties shared by all of these dependencies by introducing the concept of “faithfulness”, and showing that IDs and EIDs are faithful, whereas slight variations are not necessarily faithful.
Toward logical data independence
46 Citations1982David Maier, David Rozenshtein +3 more
The goal is a powerful, yet concise, query language with natural semantics, where a user need not be concerned with how the data has been partitioned into various relations in a relational database.
Specifying connections for a universal relation scheme database
36 Citations1982David Maier, David S. Warren
This work uses the notion of object to give a database designer the ability to control how connections in the database are to be made and shows how semantic considerations that follow naturally from the unique connection assumption constrain how objects and the underlying base relations must be syntactically related.
Journal of the ACMFinitely Specifiable Implicational Dependency Families
30 Citations1984Richard Hull
The collection de familles de dependances d'implication specifiable de maniere finie n'est pas bloquee sous les dependances de jointure ou de projection.
A universal relation database system implemented via the network model
29 Citations1982Sharon McCure Kuck, Yehoshua Sagiv
A network schema design algorithm that uses a well-designed relational schema as input and shows how to map the representative instance to the network database.
Towards A Universal Relation Interface
28 Citations1979Sylvia L. Osborn
It is shown that it is possible to automatically generate all valid answers to a query on a relational data base such that the user need not be aware of the relations used to form the answer, but can express queries simply in terms of attribute names.
ACM Transactions on Database SystemsConstruction of relations in relational databases
11 Citations1980Eliezer L. Lozinskii
This work focuses upon sequences of join operations which losslessly produce a relation required by a query which provides a basis for the presented algorithms that construct an efficient join procedure.
Satisfying database states
10 Citations1982Marc H. Graham
This work gives a formalization of the universal scheme assumption which differs from that of Fagin et.
Notions of dependency satisfaction
8 Citations1982Marc H. Graham, Alberto O. Mendelzon
It is argued that neither approach is the correct one, but rather that they correspond to different policies on constraint enforcement, and each one is appropriate in different circumstances.