Range nesting: a fast method to evaluate quantified queries

ABSTRACT

Database queries explicitly containing existential and universal quantification become increasingly important in a number of areas such as integrity checking, interaction of databases and AI systems, heterogeneous databases, and statistical databases. Using a concept of range nesting in relational calculus expressions, the paper describes evaluation algorithms and transformation methods for an important class of quantified relational calculus queries called perfect expressions. This class includes well-known classes of "easy" queries such as tree queries (with free and existentially quantified variables only), and complacent (disconnected) queries.

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: Philip A. Bernstein , Dah-Ming W. Chiu, Using Semi-Joins to Solve Relational Queries, Journal of the ACM (JACM), v.28 n.1, p.25-40, Jan. 1981 [doi>10.1145/322234.322238]
• 3: BERN81b Bernstein, P.A., Goodman, N. "The Power of Inequality Semijoins", Inform. Systems 6 (1981), 255--265.
• 4: Philip A. Bernstein , Barbara T. Blaustein, Fast methods for testing quantified relational calculus assertions, Proceedings of the 1982 ACM SIGMOD international conference on Management of data, June 02-04, 1982, Orlando, Florida [doi>10.1145/582353.582361]
• 5: Ashok K. Chandra , Philip M. Merlin, Optimal implementation of conjunctive queries in relational data bases, Proceedings of the ninth annual ACM symposium on Theory of computing, p.77-90, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803397]
• 6: CLAU80 Clausen, S.E. "Optimizing the Evaluation of Calculus Expressions in a Relational Database System", Inform. Systems 5 (1980), 41--54.
• 7: CODD72 Codd, E,F. "Relational Completeness of Data Base Sublanguages", in Courant Computer Science Symposia, New York, Prentice Hall 1972.
• 8: Umeshwar Dayal , Nathan Goodman, Query optimization for CODASYL database systems, Proceedings of the 1982 ACM SIGMOD international conference on Management of data, June 02-04, 1982, Orlando, Florida [doi>10.1145/582353.582380]
• 9: HALL76 Hall, P.A.V. "Optimization of Single Expressions in a Relational Data Base System", IBM J. Res. Develop. 20 (1976), 244--257.
• 10: JARK81 Jarke, M., Schmidt, J.W. "Evaluation of First-Order Relational Expressions", Technical Report 78, Universitaet Hamburg, Fachbereich Informatik, June 1981.
• 11: Matthias Jarke , Joachim W. Schmidt, Query processing strategies in the PASCAL/R relational database management system, Proceedings of the 1982 ACM SIGMOD international conference on Management of data, June 02-04, 1982, Orlando, Florida [doi>10.1145/582353.582402]
• 12: JARK82b Jarke, M., Koch, J., Mall, M., Schmidt, J.W. "Query Optimization Research in the Database Programming Languages (DBPL) Project", Database Engineering 5, 3 (1982), 11--14.
• 13: Won Kim, On optimizing an SQL-like nested query, ACM Transactions on Database Systems (TODS), v.7 n.3, p.443-469, Sept. 1982 [doi>10.1145/319732.319745]
• 14: Anthony Klug, Access paths in the "Abe" statistical query facility, Proceedings of the 1982 ACM SIGMOD international conference on Management of data, June 02-04, 1982, Orlando, Florida [doi>10.1145/582353.582382]
• 15: N. J. Nilsson, Principles of artificial intelligence, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1980
• 16: PALE72 Palermo, F.P. "A Data Base Search Problem", Proc 4th Comp. and Inform. Sc. Symp., Miami Beach, 1972, 67--101.
• 17: ROSE80 Rosenkrantz, D.J., Hunt, M.B. "Processing Conjunctive Predicates and Queries", Proc. 6th VLDB, Montreal, 1980, 64--74.
• 18: Joachim W. Schmidt, Some high level language constructs for data of type relation, ACM Transactions on Database Systems (TODS), v.2 n.3, p.247-261, Sept. 1977 [doi>10.1145/320557.320568]
• 19: SCHM82 Schmidt, J.W., Mall, M., Koch, J., Jarke, M. "Database Programming Languages", Proc. Database Interface Workshop, Philadelphia, October 1982.
• 20: SHMU81 Shmueli, O. "The Fundamental Role of Tree Schemas in Relational Query Processing", PhD thesis, Harvard 1981.
• 21: John Miles Smith , Philip Yen-Tang Chang, Optimizing the performance of a relational algebra database interface, Communications of the ACM, v.18 n.10, p.568-579, Oct. 1975 [doi>10.1145/361020.361025]
• 22: Patrick Valduriez, Semi-join algorithms for multiprocessor systems, Proceedings of the 1982 ACM SIGMOD international conference on Management of data, June 02-04, 1982, Orlando, Florida [doi>10.1145/582353.582396]
• 23: Eugene Wong , Karel Youssefi, Decomposition—a strategy for query processing, ACM Transactions on Database Systems (TODS), v.1 n.3, p.223-241, Sept. 1976 [doi>10.1145/320473.320479]