Loading...
Please wait, while we are loading the content...
Learning Eecient Query Processing Strategies
| Content Provider | Semantic Scholar |
|---|---|
| Author | Greiner, S. P. |
| Copyright Year | 1992 |
| 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 nd an answer, averaged over its anticipated set of queries. This cost depends on the qp's strategy, which speciies 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 rst monitors the qp's operations over a set of queries, observing how often each path of rules leads to a suucient 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. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.cs.toronto.edu/~greiner/PAPERS/qp.ps |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
