ACM SIGMOD Anthology TODS dblp.uni-trier.de

Tail Recursion Elimination in Deductive Databases.

Kenneth A. Ross: Tail Recursion Elimination in Deductive Databases. ACM Trans. Database Syst. 21(2): 208-237(1996)
@article{DBLP:journals/tods/Ross96,
  author    = {Kenneth A. Ross},
  title     = {Tail Recursion Elimination in Deductive Databases},
  journal   = {ACM Trans. Database Syst.},
  volume    = {21},
  number    = {2},
  year      = {1996},
  pages     = {208-237},
  ee        = {http://doi.acm.org/10.1145/232616.232628, db/journals/tods/Ross96.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

We consider an optimization technique for deductive and relational databases. The optimization technique is an extension of the magic templates rewriting, and it can improve the performance of query evaluation by not materializing the extension of intermediate views. Standard relational techniques, such as unfolding embedded view definitions, do not apply to recursively defined views, and so alternative techniques are necessary. We demonstrate the correctness of our rewriting. We define a class of "nonrepeating" view definitions, and show that for certain queries our rewriting performs at least as well as magic templates on nonrepeating views, and often much better. A syntactically recognizable property, called "weak right-linearity", is proposed. Weak right-linearity is a sufficient condition for nonrepetition and is more general than right-linearity. Our technique gives the same benefits as right-linear evaluation of right-linear views, while applying to a significantly more general class of views.

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

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 4 Issue 1, Books, VLDB-j, TODS, ..." and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

Online Edition: ACM Digital Library

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

References

[Apt and van Emden 1982]
Krzysztof R. Apt, Maarten H. van Emden: Contributions to the Theory of Logic Programming. J. ACM 29(3): 841-862(1982) BibTeX
[Bancilhon et al. 1986]
François Bancilhon, David Maier, Yehoshua Sagiv, Jeffrey D. Ullman: Magic Sets and Other Strange Ways to Implement Logic Programs. PODS 1986: 1-15 BibTeX
[Beeri and Ramakrishnan 1991]
Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. J. Log. Program. 10(1/2/3&4): 255-299(1991) BibTeX
[Bry 1989]
François Bry: Query Evaluation in Recursive Databases: Bottom-up and Top-down Reconciled. DOOD 1989: 25-44 BibTeX
[Chen et al. 1989]
Weidong Chen, Michael Kifer, David Scott Warren: HiLog: A First-Order Semantics for Higher-Order Logic Programming Constructs. NACLP 1989: 1090-1114 BibTeX
[Chen et al. 1993]
Weidong Chen, Michael Kifer, David Scott Warren: HILOG: A Foundation for Higher-Order Logic Programming. J. Log. Program. 15(3): 187-230(1993) BibTeX
[Clark 1979]
...
[Codish et al. 1994]
Michael Codish, Dennis Dams, Eyal Yardeni: Bottom-up Abstract Interpretation of Logic Programs. Theor. Comput. Sci. 124(1): 93-125(1994) BibTeX
[Hill 1974]
...
[Kemp et al. 1990]
David B. Kemp, Kotagiri Ramamohanarao, Zoltan Somogyi: Right-, left- and multi-linear rule transformations that maintain context information. VLDB 1990: 380-391 BibTeX
[Kemp et al. 1992]
David B. Kemp, Peter J. Stuckey, Divesh Srivastava: Query Restricted Bottom-Up Evaluation of Normal Logic Programs. JICSLP 1992: 288-302 BibTeX
[Lloyd 1987]
John W. Lloyd: Foundations of Logic Programming, 2nd Edition. Springer 1987, ISBN 3-540-18199-7
BibTeX
[Morishita 1993]
Shinichi Morishita: An Alternating Fixpoint Tailored to Magic Programs. PODS 1993: 123-134 BibTeX
[Mumick and Pirahesh 1991]
Inderpal Singh Mumick, Hamid Pirahesh: Overbound and Right-Linear Queries. PODS 1991: 127-141 BibTeX
[Naughton et al. 1989a]
Jeffrey F. Naughton, Raghu Ramakrishnan, Yehoshua Sagiv, Jeffrey D. Ullman: Argument Reduction by Factoring. VLDB 1989: 173-182 BibTeX
[Naughton et al. 1989b]
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
[Ramakrishnan 1991]
Raghu Ramakrishnan: Magic Templates: A Spellbinding Approach To Logic Programs. J. Log. Program. 11(3&4): 189-216(1991) BibTeX
[Ramakrishnan et al. 1992]
Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan: Controlling the Search in Bottom-Up Evaluation. JICSLP 1992: 273-287 BibTeX
[Ross 1991]
Kenneth A. Ross: Modular Acyclicity and Tail Recursion in Logic Programs. PODS 1991: 92-101 BibTeX
[Ross 1994]
Kenneth A. Ross: Modular Stratification and Magic Sets for Datalog Programs with Negation. J. ACM 41(6): 1216-1266(1994) BibTeX
[Saccà and Zaniolo 1987]
Domenico Saccà, Carlo Zaniolo: Implementation of Recursive Queries for a Data Language Based on Pure Horn Logic. ICLP 1987: 104-135 BibTeX
[Sethi 1989]
...
[Sudarshan 1992]
S. Sudarshan: Optimizing Bottom-Up Query Evaluation for Deductive Databases. Ph.D. thesis, Univ. of Wisconsin-Madison 1992
BibTeX
[Ullman 1989a]
Jeffrey D. Ullman: Bottom-Up Beats Top-Down for Datalog. PODS 1989: 140-149 BibTeX
[Ullman 1989b-1]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX
[Ullman 1989b-2]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Tue Jun 24 18:39:19 2008