Overbound and Right-Linear Queries.

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

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Online Edition: ACM Digital Library

References

[AU79]

Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 BibTeX

[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) BibTeX

[Jak91]

Håkan Jakobsson: Mixed-Approach Algorithms for Transitive Closure. PODS 1991: 199-205 BibTeX

[KRS90]

David B. Kemp, Kotagiri Ramamohanarao, Zoltan Somogyi: Right-, left- and multi-linear rule transformations that maintain context information. VLDB 1990: 380-391 BibTeX

[MFPR90]

Inderpal Singh Mumick, Sheldon J. Finkelstein, Hamid Pirahesh, Raghu Ramakrishnan: Magic is Relevant. SIGMOD Conference 1990: 247-258 BibTeX

[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) BibTeX

[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 BibTeX

[NRSU89b]

Jeffrey F. Naughton, Raghu Ramakrishnan, Yehoshua Sagiv, Jeffrey D. Ullman: Argument Reduction by Factoring. VLDB 1989: 173-182 BibTeX

[Ros91]

Kenneth A. Ross: Modular Acyclicity and Tail Recursion in Logic Programs. PODS 1991: 92-101 BibTeX

[Ull88]

Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents 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

[UVG88]

Jeffrey D. Ullman, Allen Van Gelder: Parallel Complexity of Logical Query Programs. Algorithmica 3: 5-42(1988) BibTeX

[Yan90]

Mihalis Yannakakis: Graph-Theoretic Methods in Database Theory. PODS 1990: 230-242 BibTeX

Referenced by

1. Kenneth A. Ross: Tail Recursion Elimination in Deductive Databases. ACM Trans. Database Syst. 21(2): 208-237(1996)
2. Shaul Dar, Raghu Ramakrishnan: A Performance Study of Transitive Closure Algorithms. SIGMOD Conference 1994: 454-465
3. Surajit Chaudhuri, Moshe Y. Vardi: On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs. PODS 1994: 107-116
4. Shaul Dar, Rakesh Agrawal: Extending SQL with Generalized Transitive Closure Functionality. IEEE Trans. Knowl. Data Eng. 5(5): 799-812(1993)
5. Håkan Jakobsson: On Tree-Based Techniques for Query Evaluation. PODS 1992: 380-392
6. Surajit Chaudhuri, Moshe Y. Vardi: On the Equivalence of Recursive and Nonrecursive Datalog Programs. PODS 1992: 55-66
7. Håkan Jakobsson: On Materializing Views and On-Line Queries. ICDT 1992: 407-420
8. Kenneth A. Ross: Modular Acyclicity and Tail Recursion in Logic Programs. PODS 1991: 92-101