Answering queries in relational databases

ABSTRACT

This paper concerns query answering in relational databases. We assume a universe U of attributes and a set of values associated with each attribute. A database scheme is a given collection R = {1, 2, ..., n} of subsets of U, called relation schemes. A query in R is any subset of U. We call "context" any joinable subset of R. An unambiguous context is one in which a query receives the same answer independently of the subcontext used for the computation. A formal treatment of unambiguous contexts is presented and it is shown that they provide a suitable basis for discussing the universal relation assumption, the relationship uniqueness assumption, maximal objects, and other related concepts.

REFERENCES

• 1: A. V. Aho , Y. Sagiv , J. D. Ullman, Efficient optimization of a class of relational expressions, ACM Transactions on Database Systems (TODS), v.4 n.4, p.435-454, Dec. 1979 [doi>10.1145/320107.320112]
• 2: Paolo Atzeni , D. Stott Parker, Jr., Assumptions in relational database theory, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588113]
• 3: Ausiello G., D'Atri A., Moscarini M., "Minimal coverings of acyclic database schemata", Proc. Workshop on Logical Bases for Data Bases, Toulouse, December 1982.
• 4: Catriel Beeri , Ronald Fagin , David Maier , Alberto Mendelzon , Jeffrey Ullman , Mihalis Yannakakis, Properties of acyclic database schemes, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.355-362, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802489]
• 5: Beeri C., Fagin R., Maier D., Yannakakis M., "On the desirability of acyclic database schemes", Research Report RJ3131, IBM San Jose, California, May 1981, to appear on J. ACM.
• 6: Fagin R., "Types of acyclicity for hypergraphs and relational database schemes", Research Report RJ3330, IBM, San Jose, California, September 1982, to appear on J. ACM.
• 7: Ronald Fagin , Alberto O. Mendelzon , Jeffrey D. Ullman, A simplied universal relation assumption and its properties, ACM Transactions on Database Systems (TODS), v.7 n.3, p.343-360, Sept. 1982 [doi>10.1145/319732.319735]
• 8: Korth H.F., Ullman J.D., "SYSTEM/U:A database system based on the Universal Relation Assumption", Proc. XP1 Conf., Stony Brook, New York, June 1980.
• 9: Maier D., Ullman J.D., "Maximal objects and the semantics of Universal Relation database", Technical Report 80-016, Stanford University, California, November 1980.
• 10: Osborn S.L., "Towards a Universal Relation interface", Proc. Conf. on Very Large Data Bases, Rio de Janeiro, Brasil, pp. 52--60, Oct. 1979.
• 11: Rissanen J., "Theory of joins for relational databases", Proc. Seventh Symp. on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, Springer-Verlag, pp. 537--551, 1978.