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

Efficient Evaluation of Right-, Left-, and Mult-Lineare Rules.

Jeffrey F. Naughton, Raghu Ramakrishnan, Yehoshua Sagiv, Jeffrey D. Ullman: Efficient Evaluation of Right-, Left-, and Mult-Lineare Rules. SIGMOD Conference 1989: 235-242
@inproceedings{DBLP:conf/sigmod/NaughtonRSU89,
  author    = {Jeffrey F. Naughton and
               Raghu Ramakrishnan and
               Yehoshua Sagiv and
               Jeffrey D. Ullman},
  editor    = {James Clifford and
               Bruce G. Lindsay and
               David Maier},
  title     = {Efficient Evaluation of Right-, Left-, and Mult-Lineare Rules},
  booktitle = {Proceedings of the 1989 ACM SIGMOD International Conference on
               Management of Data, Portland, Oregon, May 31 - June 2, 1989},
  publisher = {ACM Press},
  year      = {1989},
  pages     = {235-242},
  ee        = {http://doi.acm.org/10.1145/67544.66948, db/conf/sigmod/NaughtonRSU89.html},
  crossref  = {DBLP:conf/sigmod/89},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

We present an algorithm for the efficient evaluation of a useful subset of recursive queries. Like the magic sets transformation, the algorithm consists of a rewriting phase followed by semi-naive bottom-up evaluation of the resulting rules. We prove that on a wide range of recursions, this algorithm achieves a factor of O(n) speedup over magic sets. Intuitively, the transformations in this algorithm achieve their performance by reducing the arity of the recursive predicates in the transformed rules.

Copyright © 1989 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

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

James Clifford, Bruce G. Lindsay, David Maier (Eds.): Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data, Portland, Oregon, May 31 - June 2, 1989. ACM Press 1989 BibTeX , SIGMOD Record 18(2), June 1989
Contents

Online Edition: ACM Digital Library

References

[Agr87]
Rakesh Agrawal: Alpha: An Extension of Relational Algebra to Express a Class of Recursive Queries. ICDE 1987: 580-590 BibTeX
[AU79]
Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 BibTeX
[BMSU86]
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
[BR86]
...
[BR87]
Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. PODS 1987: 269-284 BibTeX
[Cha81]
Chin-Liang Chang: On Evaluation of Queries Containing Derived Relations in a Relational Data Base. Advances in Data Base Theory 1979: 235-260 BibTeX
[HN84]
Lawrence J. Henschen, Shamim A. Naqvi: On compiling queries in recursive first-order databases. J. ACM 31(1): 47-85(1984) BibTeX
[HN88]
Ramsey W. Haddad, Jeffrey F. Naughton: Counting Methods for Cyclic Relations. PODS 1988: 333-340 BibTeX
[KL86]
...
[Nau87]
Jeffrey F. Naughton: One-Sided Recursions. PODS 1987: 340-348 BibTeX
[Nau88]
Jeffrey F. Naughton: Compiling Separable Recursions. SIGMOD Conference 1988: 312-319 BibTeX
[RHDM86]
Arnon Rosenthal, Sandra Heiler, Umeshwar Dayal, Frank Manola: Traversal Recursion: A Practical Approach to Supporting Recursive Applications. SIGMOD Conference 1986: 166-176 BibTeX
[Sag88]
...
[SZ86]
Domenico Saccà, Carlo Zaniolo: The Generalized Counting Method for Recursive Logic Queries. ICDT 1986: 31-53 BibTeX
[Vie86]
Laurent Vieille: Recursive Axioms in Deductive Databases: The Query/Subquery Approach. Expert Database Conf. 1986: 253-267 BibTeX

Referenced by

  1. Sergio Greco: Binding Propagation in Disjunctive Databases. VLDB 1998: 287-298
  2. Kenneth A. Ross: Tail Recursion Elimination in Deductive Databases. ACM Trans. Database Syst. 21(2): 208-237(1996)
  3. Divesh Srivastava, S. Sudarshan, Raghu Ramakrishnan, Jeffrey F. Naughton: Space Optimization in Deductive Databases. ACM Trans. Database Syst. 20(4): 472-516(1995)
  4. Laks V. S. Lakshmanan, Rokia Missaoui: Pushing Semantics Inside Recursion: A General Framework for Semantic Optimization of Recursive Queries. ICDE 1995: 211-220
  5. Sergio Greco, Luigi Palopoli, Eugenio Spadafora: DatalogA: Array Manipulations in a Deductive Database Language. DASFAA 1995: 180-188
  6. Wenyu Lu, Dik Lun Lee, Jiawei Han: A Study on the Structure of Linear Recursion. IEEE Trans. Knowl. Data Eng. 6(5): 723-737(1994)
  7. Keh-Chang Guh, Clement T. Yu: Efficient Query Processing for a Subset of Linear Recursive Binary Rules. IEEE Trans. Knowl. Data Eng. 6(5): 842-849(1994)
  8. Shaul Dar, Raghu Ramakrishnan: A Performance Study of Transitive Closure Algorithms. SIGMOD Conference 1994: 454-465
  9. Surajit Chaudhuri, Moshe Y. Vardi: On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs. PODS 1994: 107-116
  10. Shaul Dar, Rakesh Agrawal: Extending SQL with Generalized Transitive Closure Functionality. IEEE Trans. Knowl. Data Eng. 5(5): 799-812(1993)
  11. Sergio Greco: Optimization of Chain Queries. DASFAA 1993: 261-268
  12. Keh-Chang Guh, Clement T. Yu: Efficient Management of Materialized Generalized Transitive Closure in Centralized and Parallel Environments. IEEE Trans. Knowl. Data Eng. 4(4): 371-381(1992)
  13. Håkan Jakobsson: On Tree-Based Techniques for Query Evaluation. PODS 1992: 380-392
  14. Surajit Chaudhuri, Moshe Y. Vardi: On the Equivalence of Recursive and Nonrecursive Datalog Programs. PODS 1992: 55-66
  15. Håkan Jakobsson: On Materializing Views and On-Line Queries. ICDT 1992: 407-420
  16. Jiawei Han: Compilation-Based List Processing in Deductive Databases. EDBT 1992: 104-119
  17. Sergio Greco, Carlo Zaniolo: Optimization of Linear Logic Programs Using Counting Methods. EDBT 1992: 72-87
  18. Guido Moerkotte, Peter C. Lockemann: Reactive Consistency Control In Deductive Databases. ACM Trans. Database Syst. 16(4): 670-702(1991)
  19. Kenneth A. Ross: Modular Acyclicity and Tail Recursion in Logic Programs. PODS 1991: 92-101
  20. Inderpal Singh Mumick, Hamid Pirahesh: Overbound and Right-Linear Queries. PODS 1991: 127-141
  21. Wenceslas Fernandez de la Vega, Vangelis Th. Paschos, A. N. Staylopatis: On the Mean Execution Time of Recursive Definitions on Relational Databases. MFDBS 1991: 119-133
  22. Jayen Vaghani, Kotagiri Ramamohanarao, David B. Kemp, Zoltan Somogyi, Peter J. Stuckey: Design Overview of the Aditi Deductive Database System. ICDE 1991: 240-247
  23. Keh-Chang Guh, Chengyu Sun, Clement T. Yu: Real Time Retrieval and Update of Materialized Transitive Closure. ICDE 1991: 690-697
  24. Kotagiri Ramamohanarao: The Aditi Deductive Database System (Extented Abstract). DASFAA 1991: 201-208
  25. Peter T. Wood: Factoring Augmented Regular Chain Programs. VLDB 1990: 255-263
  26. David B. Kemp, Kotagiri Ramamohanarao, Zoltan Somogyi: Right-, left- and multi-linear rule transformations that maintain context information. VLDB 1990: 380-391
  27. Mihalis Yannakakis: Graph-Theoretic Methods in Database Theory. PODS 1990: 230-242
  28. Jeffrey F. Naughton, Raghu Ramakrishnan, Yehoshua Sagiv, Jeffrey D. Ullman: Argument Reduction by Factoring. VLDB 1989: 173-182
  29. Richard J. Lipton, Jeffrey F. Naughton: Estimating the Size of Generalized Transitive Closures. VLDB 1989: 165-171
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:39:58 2009