ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Learning Efficient Query Processing Strategies.

Russell Greiner: Learning Efficient Query Processing Strategies. PODS 1992: 33-46
@inproceedings{DBLP:conf/pods/Greiner92,
  author    = {Russell Greiner},
  title     = {Learning Efficient Query Processing Strategies},
  booktitle = {Proceedings of the Eleventh ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, June 2-4, 1992, San Diego,
               California},
  publisher = {ACM Press},
  year      = {1992},
  isbn      = {0-89791-519-4},
  pages     = {33-46},
  ee        = {http://doi.acm.org/10.1145/137097.137106, db/conf/pods/Greiner92.html},
  crossref  = {DBLP:conf/pods/92},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

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 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, 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.

Copyright © 1992 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Eleventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 2-4, 1992, San Diego, California. ACM Press 1992, ISBN 0-89791-519-4
Contents BibTeX

Online Edition: ACM Digital Library

[Abstract and Index Terms]
[Full Text in PDF Format, 1363 KB]

References

[AV88]
Serge Abiteboul, Victor Vianu: Procedural and Declarative Database Update Languages. PODS 1988: 240-250 BibTeX
[BD88]
...
[Bol85]
...
[BR86]
François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52 BibTeX
[CG91]
...
[Che52]
...
[DB88]
Thomas Dean, Mark S. Boddy: An Analysis of Time-Dependent Planning. AAAI 1988: 49-54 BibTeX
[DeJ88]
...
[Des90]
...
[GJ92]
...
[GO91]
Russell Greiner, Pekka Orponen: Probably Approximately Optimal Derivation Strategies. KR 1991: 277-288 BibTeX
[GO92]
...
[Gre91]
Russell Greiner: Finding Optimal Derivation Strategies in Redundant Knowledge Bases. Artif. Intell. 50(1): 95-115(1991) BibTeX
[HC76]
Michael Hammer, Arvola Chan: Index Selection in a Self-Adaptive Data Base Management System. SIGMOD Conference 1976: 1-8 BibTeX
[LK82]
...
[LN90]
Richard J. Lipton, Jeffrey F. Naughton: Query Size Estimation by Adaptive Sampling. PODS 1990: 40-46 BibTeX
[LNR86]
...
[LNR87]
...
[LV89]
Alexandre Lefebvre, Laurent Vieille: On Deductive Query Evaluation in the DedGin* System. DOOD 1989: 123-144 BibTeX
[MCK+89]
Steven Minton, Jaime G. Carbonell, Craig A. Knoblock, Daniel Kuokka, Oren Etzioni, Yolanda Gil: Explanation-Based Learning: A Problem Solving Perspective. Artif. Intell. 40(1-3): 63-118(1989) BibTeX
[MKKC86]
...
[Nil80]
...
[OG90]
...
[RBK88]
Raghu Ramakrishnan, Catriel Beeri, Ravi Krishnamurthy: Optimizing Existential Datalog Queries. PODS 1988: 89-102 BibTeX
[SAC+79]
Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price: Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979: 23-34 BibTeX
[SK75]
...
[Smi89]
David E. Smith: Controlling Backward Inference. Artif. Intell. 39(2): 145-208(1989) BibTeX
[Ull89]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX
[Val84]
Leslie G. Valiant: A Theory of the Learnable. Commun. ACM 27(11): 1134-1142(1984) BibTeX
[Vie89]
Laurent Vieille: Recursive Query Processing: The Power of Logic. Theor. Comput. Sci. 69(1): 1-53(1989) BibTeX
[Zan88]
Carlo Zaniolo: Design and Implementation of a Logic Based Language for Data Intensive Applications. ICLP/SLP 1988: 1666-1687 BibTeX
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:34:05 2009