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

Detecting Redundant Tuples During Query Evaluation.

Surajit Chaudhuri: Detecting Redundant Tuples During Query Evaluation. PODS 1991: 115-126
@inproceedings{DBLP:conf/pods/Chaudhuri91,
  author    = {Surajit Chaudhuri},
  title     = {Detecting Redundant Tuples During Query Evaluation},
  booktitle = {Proceedings of the Tenth ACM SIGACT-SIGMOD-SIGART Symposium on
               Principles of Database Systems, May 29-31, 1991, Denver, Colorado},
  publisher = {ACM Press},
  year      = {1991},
  isbn      = {0-89791-430-9},
  pages     = {115-126},
  ee        = {http://doi.acm.org/10.1145/113413.113424, db/conf/pods/Chaudhuri91.html},
  crossref  = {DBLP:conf/pods/91},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We introduce a new approach to optimization of logic programs. We show that by using simple runtime tests, we can detect redundant tuples during bottom-up evaluation of logic programs. We can exploit such redundancy in many ways, e.g., we can reduce the number of duplicates that are generated. We identify data independent properties of the program that can be used for efficient runtime tests. We analyze two such properties of a predicate, emptiness and used-at-most-once. In summary, the paper illustrates how the synergy between the properties of the program and selective runtime information can be used for optimization.

Copyright © 1991 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 ...

Printed Edition

Proceedings of the Tenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 29-31, 1991, Denver, Colorado. ACM Press 1991, ISBN 0-89791-430-9
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 984 KB]

References

[BeRa87]
Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. PODS 1987: 269-284 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Hel89]
A. Richard Helm: On the Dedection and Elimination of Redundant Derivations during Bottom-up Execution. NACLP 1989: 945-962 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Kan88]
...
[MaRa]
Michael J. Maher, Raghu Ramakrishnan: Déjà Vu in Fixpoints of Logic Programs. NACLP 1989: 963-980 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Nau89]
Jeffrey F. Naughton: Data Independent Recursion in Deductive Databases. J. Comput. Syst. Sci. 38(2): 259-289(1989) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[NaRa90]
Jeffrey F. Naughton, Raghu Ramakrishnan: How to Forget the Past Without Repeating It. VLDB 1990: 278-289 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[PePo82]
...
[RSUV89]
Raghu Ramakrishnan, Yehoshua Sagiv, Jeffrey D. Ullman, Moshe Y. Vardi: Proof-Tree Transformation Theorems and Their Applications. PODS 1989: 172-181 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sag87]
Yehoshua Sagiv: Optimizing Datalog Programs. PODS 1987: 349-362 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sar88]
Yatin P. Saraiya: Linearizing Nonlinear Recursions in Polynomial Time. PODS 1989: 182-189 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ull88]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ull89]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Var88]
Moshe Y. Vardi: Decidability and Undecidability Results for Boundedness of Linear Recursive Queries. PODS 1988: 341-351 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Referenced by

  1. Surajit Chaudhuri: Finding Nonrecursive Envelopes for Datalog Predicates. PODS 1993: 135-146

Copyright © Mon Nov 2 21:04:15 2009 by Michael Ley (ley@uni-trier.de)