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

Overbound and Right-Linear Queries.

Inderpal Singh Mumick, Hamid Pirahesh: Overbound and Right-Linear Queries. PODS 1991: 127-141
@inproceedings{DBLP:conf/pods/MumickP91,
  author    = {Inderpal Singh Mumick and
               Hamid Pirahesh},
  title     = {Overbound and Right-Linear Queries},
  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     = {127-141},
  ee        = {http://doi.acm.org/10.1145/113413.113425, db/conf/pods/MumickP91.html},
  crossref  = {DBLP:conf/pods/91},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We study the optimization of a useful subclass of linear recursive queries. In addition to the general purpose magic-sets transformation, special optimization techniques, such as the right-linear and context right-linear transformation have been proposed for such programs. These, and in fact most optimization techniques for database queries are based on the idea of full sips, where all available predicates are passed into a subgoal. This is widely believed to be a sound heuristic. However, we use partial sips, that do not pass all predicates into a subgoal, to develop an optimization algorithm for a class of linear queries and show that our algorithm is better than the previously known techniques. We syntactically identify a class of programs for which partial sips are always preferable to full sips. The result provokes thought on the utility of partial sips, and will hopefully lead to more research in the area.

The right-linear and context righ-linear transformations, where applicable, are alternatives to the magic-sets transformation. In the presence of alternative optimization, we need a way to choose between them. Given a program, can we choose one technique over another, confident that we are not discarding a good evaluation strategy? For example, it has been shown that, where applicable, the right-linear transformation always performs better than magic-sets. However the above question has been left unanswered for many of the proposed optimizations for special forms of recursion. We study the problem for one class of optimization techniques, comparing the context right-linear and magic-sets transformations.

Finally, we observe that right-linear and left-linear programs can be viewed as duals of each other. Every righ-]inear program can be written as an equivalent left-linear program, and vice versa.

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, 1500 KB]

References

[AU79]
Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BR88]
...
[HCL+90]
Laura M. Haas, Walter Chang, Guy M. Lohman, John McPherson, Paul F. Wilms, George Lapis, Bruce G. Lindsay, Hamid Pirahesh, Michael J. Carey, Eugene J. Shekita: Starburst Mid-Flight: As the Dust Clears. IEEE Trans. Knowl. Data Eng. 2(1): 143-160(1990) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Jak91]
Håkan Jakobsson: Mixed-Approach Algorithms for Transitive Closure. PODS 1991: 199-205 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KRS90]
David B. Kemp, Kotagiri Ramamohanarao, Zoltan Somogyi: Right-, left- and multi-linear rule transformations that maintain context information. VLDB 1990: 380-391 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[MFPR90]
Inderpal Singh Mumick, Sheldon J. Finkelstein, Hamid Pirahesh, Raghu Ramakrishnan: Magic is Relevant. SIGMOD Conference 1990: 247-258 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[MNS+87]
Katherine A. Morris, Jeffrey F. Naughton, Yatin P. Saraiya, Jeffrey D. Ullman, Allen Van Gelder: YAWN! (Yet Another Window on NAIL!). IEEE Data Eng. Bull. 10(4): 28-43(1987) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[MP91]
...
[NRSU89a]
Jeffrey F. Naughton, Raghu Ramakrishnan, Yehoshua Sagiv, Jeffrey D. Ullman: Efficient Evaluation of Right-, Left-, and Mult-Lineare Rules. SIGMOD Conference 1989: 235-242 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[NRSU89b]
Jeffrey F. Naughton, Raghu Ramakrishnan, Yehoshua Sagiv, Jeffrey D. Ullman: Argument Reduction by Factoring. VLDB 1989: 173-182 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ros91]
Kenneth A. Ross: Modular Acyclicity and Tail Recursion in Logic Programs. PODS 1991: 92-101 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
[UVG88]
Jeffrey D. Ullman, Allen Van Gelder: Parallel Complexity of Logical Query Programs. Algorithmica 3: 5-42(1988) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Yan90]
Mihalis Yannakakis: Graph-Theoretic Methods in Database Theory. PODS 1990: 230-242 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Fri Mar 12 17:19:56 2010 by Michael Ley (ley@uni-trier.de)