Learning Efficient Query Processing Strategies
Full Text:
qp.ps 
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 the 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, ie, 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.
Citation
R. Greiner.
"Learning Efficient Query Processing Strategies".
Principles of Database Systems (PODS), San Diego, pp 33-46, June 1992.
| Keywords: |
machine learning, database, PALO |
| Category: |
In Conference |
BibTeX
@incollection{Greiner:PODS92,
author = {Russ Greiner},
title = {Learning Efficient Query Processing Strategies},
Pages = {33-46},
booktitle = {Principles of Database Systems (PODS)},
year = 1992,
}Last Updated: November 19, 2019
Submitted by Sabina P 
