Logic-based approach to semantic query optimization

ABSTRACT

The purpose of semantic query optimization is to use semantic knowledge (e.g., integrity constraints) for transforming a query into a form that may be answered more efficiently than the original version. In several previous papers we described and proved the correctness of a method for semantic query optimization in deductive databases couched in first-order logic. This paper consolidates the major results of these papers emphasizing the techniques and their applicability for optimizing relational queries. Additionally, we show how this method subsumes and generalizes earlier work on semantic query optimization. We also indicate how semantic query optimization techniques can be extended to databases that support recursion and integrity constraints that contain disjunction, negation, and recursion.

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: Francois Bancilhon , Raghu Ramakrishnan, An amateur's introduction to recursive query processing strategies, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.16-52, May 28-30, 1986, Washington, D.C., United States
• 3: Upendranath Sharma Chakravarthy, Semantic query optimization in deductive databases. (volumes i and ii) (integrity constraints, intelligent processing, logic), 1985
• 4: U S Chakravarthy , D H Fishman , J Minker, Semantic query optimization in expert systems and database systems, Proceedings from the first international workshop on Expert database systems, p.659-674, January 1986, Kiawah Island, South Carolina, United States
• 5: U. S. Chakravarthy , J. Grant , J. Minker, Foundations of semantic query optimization for deductive databases, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 6: Upen S. Chakravarthy , Jack Minker, Multiple Query Processing in Deductive Databases using Query Graphs, Proceedings of the 12th International Conference on Very Large Data Bases, p.384-391, August 25-28, 1986
• 7: CHAKRAVARTHY, U. S., MINKER, J., AND GRANT, J. Semantic query optimization: additional constraints and control strategies. In Expert Database Systems, L. Kerschberg, Ed., Benjamin/Cummings, Inc., 1987, 345-379.
• 8: Chin-Liang Chang , Richard C. Lee , Richard Char-Tung Lee, Symbolic Logic and Mechanical Theorem Proving, Academic Press, Inc., Orlando, FL, 1997
• 9: Herve Gallaire , Jack Minker , Jean-Marie Nicolas, Logic and Databases: A Deductive Approach, ACM Computing Surveys (CSUR), v.16 n.2, p.153-185, June 1984 [doi>10.1145/356924.356929]
• 10: GRANT, J., AND MINKER, J. Optimization in deductive and conventional relational database systems. In Advances in Data Base Theory, Vol. 1, H. Gallaire, J. Minker, and J. M. Nicolas, Eds., Plenum Press, 1981, 195-234.
• 11: HAMMER, M. M., AND ZDONIK, S.B. Knowledge based query processing. In Proceedings of the Sixth VLDB Conference, 1980, 137-147.
• 12: Matthias Jarke , Jim Clifford , Yannis Vassiliou, An optimizing prolog front-end to a relational query system, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 13: Matthias Jarke , Jurgen Koch, Query Optimization in Database Systems, ACM Computing Surveys (CSUR), v.16 n.2, p.111-152, June 1984 [doi>10.1145/356924.356928]
• 14: Jonathan Jay King, Query optimization by semantic reasoning, 1981
• 15: KING, J. J. QUIST: a system for semantic query optimization in relational databases. In Proceedings of the 7th VLDB Conference, 1981, 510-517.
• 16: KOHLI, M., AND MINKER, J. Intelligent control using integrity constraints. In Proceedings of AAAI, 1983, 202-205.
• 17: Sanggoo Lee , Jiawei Han, Semantic Query Optimization in Recursive Databases, Proceedings of the Fourth International Conference on Data Engineering, p.444-451, February 01-05, 1988
• 18: LOBO, J., AND MINKER, J. A metainterpreter to semantically optimize queries in deductive databases. In Proceedings of the Second International Conference on Expert Database Systems, 1988, 387-420.
• 19: James Robb Mcskimin, The use of semantic information in deductive question-answering systems., 1976
• 20: MCSKIMIN, J. R., AND MINKER, J. The use of a semantic network in a deductive query answering system. In Proceedings of the Fifth IJCAI, 1977, 50-58.
• 21: Jack Minker, Perspectives in deductive databases, Journal of Logic Programming, v.5 n.1, p.33-60, March 1988 [doi>10.1016/0743-1066(88)90006-4 ]
• 22: NAISH, L. The MU-Prolog 3.2 reference manual. Tech. Rep. 85/11, Dept. of Computer Science, Univ. of Melbourne, Australia, 1985.
• 23: REITER, R. Deductive query-answering on relational databases, in Logic and Databases, H. Gaiiaire, and J. Minker, Eds., Plenum Press, 1978, 149-178.
• 24: Timos K. Sellis, Multiple-query optimization, ACM Transactions on Database Systems (TODS), v.13 n.1, p.23-52, March 1988 [doi>10.1145/42201.42203]
• 25: Sreekumar T. Shenoy , Z. Meral Ozsoyoglu, A system for semantic query optimization, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.181-195, May 27-29, 1987, San Francisco, California, United States
• 26: STERLING, L. Meta-interpreters: the flavors of logic programming. In Proceedings of the Workshop on the Foundations of Deductive Databases and Logic Programming (Washington, D.C., 1986), J. Minker, Ed., 1986, 163-175.
• 27: Xu, G.D. Search control in semantic query optimization. Tech. Rep. 83-9, Dept. of Computer Science, Univ. of Massachusetts, Amherst, 1983.
• 28: ZDONIK, S. S., JR. On the use of domain specific knowledge in the processing of database queries. M.S. thesis, Massachusetts Institute of Technology, Cambridge, 1980.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.0 General
          Subjects: Security, integrity, and protection**
      H.2.2 Physical Design
          Subjects: Access methods

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Logic programming
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Plan execution, formation, and generation; Heuristic methods

General Terms:
Algorithms, Design, Performance