Learning efficient query processing strategies

ABSTRACT

A query processor QP uses the rules in a rule base to reduce a given query to a series of attempted retrievals from a database of facts. The Qp's expected cost is the average time it requires to find an answer, averaged over its anticipated set of queries. This cost depends on Qp's strategy, which specifies the order in which it considers the possible rules and retrievals. This paper provides two related learning algorithms, PIB and PAO, for improving the QP's strategy, i.e., for producing new strategies with lower expected costs. Each algorithm first monitors the Qp's operations over a set of queries, observing how often each path of rules leads to a sufficient set of successful retrievals, and then uses these statistics to suggest a new strategy. PIB hill-climbs to strategies that are, with high probability, successively better; and PAO produces a new strategy that probably is approximately optimal. We describe how to implement both learning systems unobtrusively, discuss their inherent time and space complexities, and use methods from mathematical statistics to prove their correctness. We also discuss additional applications of these approaches to several other database tasks.

REFERENCES

• AV88: Serge Abiteboul , Victor Vianu, Procedural and declarative database update languages, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.240-250, March 1988, Austin, Texas, United States [doi>10.1145/308386.308448]
• BD88: Mark Boddy , Thomas Dean, Solving Time-Dependent Planning Problems, Brown University, Providence, RI, 1989
• Bol85: B. Bollob~s. Random Graphs. Academic Press, 1985.
• BR86: 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
• CG91: William W. Cohen , Russell Greiner , Dale Schuurmans, Probabilistic hill-climbing, Proceedings of the workshop on Computational learning theory and natural learning systems (vol. 2) : intersections between theory and experiment: intersections between theory and experiment, p.171-181, July 1994, Berkeley, California, United States
• Che52: Herman Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the sums of observations. Annals of Mathematical Statistics, 23:493-507, 1952.
• DB88: Thomas Dean and Mark Boddy. An analysis of time-dependent planning. In AAAI- 88, pages 49-54, August 1988.
• DeJ88: Gerald DeJong. AAAI workshop on Explanation-Based Learning. Sponsored by AAAI, 1988.
• Des90: Bipin C. Desai, An introduction to database systems, West Publishing Co., St. Paul, MN, 1990
• GJ92: Russell Greiner and Igor Juri~iea. EBL system8 that (almost) alway# improve performance. Technical report, Siemens Corporate Research, 1992.
• GO91: Russell Greiner and Pekka Orponen. Probably approximately optimal derivation strategies. In J.A. Allen, R. Fikes, and E. Sandewall, editors, Principles of Knowledge Representation and Reasoning: Proceedings of the Second International Conference, San Mateo, CA#, April 1991. Morgan Kaufmann.
• GO92: Russell Greiner and Pekka Orponen. Probably approximately optimal satisfieing strategies. Technical report, Siemens Corporate Research, 1992.
• Gre91: Russell Greiner, Finding optimal derivation in redundant knowledge bases, Artificial Intelligence, v.50 n.1, p.95-115, June 1991 [doi>10.1016/0004-3702(91)90092-X]
• HC76: Michael Hammer , Arvola Chan, Index selection in a self-adaptive data base management system, Proceedings of the 1976 ACM SIGMOD international conference on Management of data, June 02-04, 1976, Washington, D.C.
• LK82: Averill M. Law , W. David Kelton, Simulation Modeling and Analysis, McGraw-Hill Higher Education, 1997
• LN90: Richard J. Lipton , Jeffrey F. Naughton, Query size estimation by adaptive sampling (extended abstract), Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.40-46, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298540]
• LNR86: John E. Laird , Paul S. Rosenbloom , Allen Newell, Chunking in Soar: The Anatomy of a General Learning Mechanism, Machine Learning, v.1 n.1, p.11-46 [doi>10.1023/A:1022639103969]
• LNR87: John E. Laird , Allen Newell , Paul S. Rosenbloom, SOAR: an architecture for general intelligence, Artificial Intelligence, v.33 n.1, p.1-64, Sept. 1987 [doi>10.1016/0004-3702(87)90050-6]
• LV89: A. Lefebvre and L. Vieille. On Deductive Query Evaluation in the DedGin* System. In Proceedings of the 1st International Conference on Deductive and Object-Oriented Dalabases, pages 225-244, Kyoto, Japan, 1989.
• MCK+89: S. Minton , J. G. Carbonell , C. A. Knoblock , D. R. Kuokka , O. Etzioni, Explanation-based learning: a problem solving perspective, Artificial Intelligence, v.40 n.1-3, p.63-118, Sep. 1989 [doi>10.1016/0004-3702(89)90047-7]
• MKKC86: Tom M. Mitchell , Richard M. Keller , Smadar T. Kedar-Cabelli, Explanation-Based Generalization: A Unifying View, Machine Learning, v.1 n.1, p.47-80 [doi>10.1023/A:1022691120807]
• Nil80: N. J. Nilsson, Principles of artificial intelligence, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1980
• OG90: Pekka Orponen , Russell Greiner, On the sample complexity of finding good search strategies, Proceedings of the third annual workshop on Computational learning theory, p.352-358, August 06-08, 1990, Rochester, New York, United States
• RBK88: Raghu Ramakrishnan , Catriel Beeri , Ravi Krishnamurthy, Optimizing existential datalog queries, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.89-102, March 1988, Austin, Texas, United States [doi>10.1145/308386.308420]
• SAC+79: P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
• SK75: H.A. Simon and j. B. Kadane. Optimal problem-solving search: All-or-none solutions. Artificial Intelligence, 6:235-247, 1975.
• Smi89: David F. Smith, Controlling backward inference, Artificial Intelligence, v.39 n.2, p.145-208, June 1989 [doi>10.1016/0004-3702(89)90025-8]
• Ull89: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• Val84: L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]
• Vie89: L. Vielle, Recursive query processing: the power of logic, Theoretical Computer Science, v.69 n.1, p.1-53, Dec. 5, 1989 [doi>10.1016/0304-3975(89)90088-1]
• Zan88: Carlo Zaniolo. Design and Implementation of a Logic Based Language for Data Intensive Applications. In Proceedings of the 5th International Conference on Logzc Programming, 1988.

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages

          Nouns: Datalog

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Algorithms, Theory