Article

Free access

Efficient evaluation of right-, left-, and multi-linear rules

Authors:

J. F. Naughton,

R. Ramakrishnan,

J. D. UllmanAuthors Info & Claims

SIGMOD '89: Proceedings of the 1989 ACM SIGMOD international conference on Management of data

Pages 235 - 242

https://doi.org/10.1145/67544.66948

Published: 01 June 1989 Publication History

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 Ο(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.

References

[1]

Rakesh Agrawal. Alpha: An extension of relational algebra to express a class of recursive queries. In Proceedings of the IEEE Conference on Data Engineering, pages 580-590, Los Angeles, Californaia, February 1987.

Digital Library

[2]

Alfred V. Aho and Jeffrey D. Ullman. Universality of data retrieval languages. In Proceedings of the Sixth A CM Symposium on Principles of Programming Languages, pages 110-120, San Antonio, Texas, 1979.

Digital Library

[3]

Francois Bancilhon, David Maier, Yehoshua Sagiv, and Jeffrey D. Ullman. Magic sets and other strange ways to implement logic programs. In Proceedings of the A CM Symposium on Principles of Database Systems, pages 1-15, Cambridge, Massachusetts, March 1986.

Digital Library

[4]

Francois Bancilhon and Raghu Ramakrishnan. Performance evaluation of data intensive logic programs. In Preprints of Workshop on Foundations of Deductive Databases and Logic Programming, August 1986.

Digital Library

[5]

Catriel Beeri and Raghu Ramakrishnan. On the power of magic. In Proceedings of the A CM Symposium on Principles of Database Systems, pages 269-283, San Diego, California, March 1987.

Digital Library

[6]

C. Chang. On the evaluation of queries containing derived relations in a relational data base. In H. Gallaire, J. Minker, and :I. Nicolas, editors, Advances in Data Base Theory, Volume 1. Plenum Press, 1981.

[7]

Lawrence J. Henschen and Shamim A. Naqvi. On compiling queries in recursive first order databases. JACM, 31(1):47- 85, 1984.

Digital Library

[8]

Ramsey W. Haddad and Jeffrey F. Naughton. Counting methods for cyclic relations. In Proceedings of the A CM Symposium on Principles of Database Systems, pages 333-340, Austin, Texas, March 1988.

Digital Library

[9]

Michael Kifer and Eliezer L. Lozinskii. A framework for an efficient implementation of deductive databases. In Proceedings of the Advanced Database Symposium, Tokyo, Japan, 1986.

[10]

Jeffrey F. Naughton. One sided recursions. In Proceedings of the A CM Symposium on Principles of Database Systems, pages 340-348, San Diego, California, March 1987.

Digital Library

[11]

Jeffrey F. Naughton. Compiling separable recursions. In Proceedings of the SIGMOD International Symposium on Management of Data, pages 312-319, Chicago, Illinois, May 1988.

Digital Library

[12]

Arnon Rosenthal, Sandra Hailer, Umeshwar Dayal, and Frank Manola. Traversal recursion: A practical approach to supporting recursive applications. In Proceedings of the A CM-SIGMOD International Conference on Management of Data, Washington, D.C., June 1986.

Digital Library

[13]

Yehoshua Sagiv. Optimizing datalog programs. In Jack Minker, editor, Foundations of Deductive Databases and Logic Programming, pages 659-698, Los Altos, California, 1988. Morgan Kaufmann.

Digital Library

[14]

Domenico Sacca and Carlo Zaniolo. The generalized counting methods for recursire logic queries. In Proceedings of ~he First International Conference on Database Theory, 1986.

Digital Library

[15]

Laurent Vieille. Recursive axioms in deductive databases: The querysubquery approach. In Proceedings of ~he First International Conference on Exper~ Database Systems, 1986.

Cited By

Fejza AGenevès PLayaïda N(2024)Efficient Enumeration of Recursive Plans in Transformation-Based Query OptimizersProceedings of the VLDB Endowment10.14778/3681954.368198617:11(3095-3108)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.14778/3681954.3681986
Christiansen HMartinenghi D(2006)On Simplification of Database Integrity ConstraintsFundamenta Informaticae10.5555/2369336.236933871:4(371-417)Online publication date: 1-Dec-2006
https://dl.acm.org/doi/10.5555/2369336.2369338
Brisaboa NFariña, ALuaces MParamá J(2006)Chase of recursive queriesProceedings of the 6th international Andrei Ershov memorial conference on Perspectives of systems informatics10.5555/1760700.1760714(112-123)Online publication date: 27-Jun-2006
https://dl.acm.org/doi/10.5555/1760700.1760714
Show More Cited By

Index Terms

Efficient evaluation of right-, left-, and multi-linear rules
1. Information systems
  1. Data management systems
    1. Database management system engines
      1. Database query processing
2. Theory of computation
  1. Formal languages and automata theory
    1. Grammars and context-free languages
  2. Theory and algorithms for application domains
    1. Database theory
      1. Database query processing and optimization (theory)

Recommendations

Efficient evaluation of right-, left-, and multi-linear rules

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 ...
Investigations into a left-structural right-substructural sequent calculus

We study a multiple-succedent sequent calculus with both of the structural rules Left Weakening and Left Contraction but neither of their counterparts on the right, for possible application to the treatment of multiplicative disjunction (fission, `...
Introduction and elimination, left and right

Functional programming language design has been shaped by the framework of natural deduction, in which language constructs are divided into introduction and elimination rules for producers of values. In sequent calculus-based languages, left introduction ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMOD '89: Proceedings of the 1989 ACM SIGMOD international conference on Management of data

June 1989

451 pages

ISBN:0897913175

DOI:10.1145/67544

ACM SIGMOD Record Volume 18, Issue 2
June 1989
442 pages
ISSN:0163-5808
DOI:10.1145/66926
Editors:
James Clifford,
Bruce Lindsay,
David Maier
Issue’s Table of Contents

Copyright © 1989 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1989

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SIGMOD/PODS04

Sponsor:

SIGMOD

SIGMOD/PODS04: International Conference on Management of Data and Symposium on Principles Database and Systems

Oregon, Portland, USA

Acceptance Rates

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

73
Total Citations
View Citations
418
Total Downloads

Downloads (Last 12 months)71
Downloads (Last 6 weeks)11

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Fejza AGenevès PLayaïda N(2024)Efficient Enumeration of Recursive Plans in Transformation-Based Query OptimizersProceedings of the VLDB Endowment10.14778/3681954.368198617:11(3095-3108)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.14778/3681954.3681986
Christiansen HMartinenghi D(2006)On Simplification of Database Integrity ConstraintsFundamenta Informaticae10.5555/2369336.236933871:4(371-417)Online publication date: 1-Dec-2006
https://dl.acm.org/doi/10.5555/2369336.2369338
Brisaboa NFariña, ALuaces MParamá J(2006)Chase of recursive queriesProceedings of the 6th international Andrei Ershov memorial conference on Perspectives of systems informatics10.5555/1760700.1760714(112-123)Online publication date: 27-Jun-2006
https://dl.acm.org/doi/10.5555/1760700.1760714
Christiansen HMartinenghi D(2006)On Simplification of Database Integrity ConstraintsFundamenta Informaticae10.5555/1227517.122751971:4(371-417)Online publication date: 1-Mar-2006
https://dl.acm.org/doi/10.5555/1227517.1227519
Behrend AHaddad HOmicini AWainwright R(2005)Optimizing existential queries in stratifiable deductive databasesProceedings of the 2005 ACM symposium on Applied computing10.1145/1066677.1066821(623-628)Online publication date: 13-Mar-2005
https://dl.acm.org/doi/10.1145/1066677.1066821
Greco SSaccà DZaniolo C(2005)The pushdown method to optimize chain logic programsAutomata, Languages and Programming10.1007/3-540-60084-1_102(523-534)Online publication date: 7-Jun-2005
https://doi.org/10.1007/3-540-60084-1_102
Greco SZaniolo C(2005)Efficient execution of recursive queries through controlled binding propagationMethodologies for Intelligent Systems10.1007/3-540-58495-1_20(193-202)Online publication date: 9-Jun-2005
https://doi.org/10.1007/3-540-58495-1_20
Jakobsson H(2005)On materializing views and on-line queriesDatabase Theory — ICDT '9210.1007/3-540-56039-4_56(407-420)Online publication date: 8-Jun-2005
https://doi.org/10.1007/3-540-56039-4_56
Fernandez de la Vega WPaschos VStafylopatis A(2005)On the mean execution time of recursive definitions on relational databasesMFDBS 9110.1007/3-540-54009-1_9(119-133)Online publication date: 8-Jun-2005
https://doi.org/10.1007/3-540-54009-1_9
Christiansen HMartinenghi D(2005)Incremental integrity checkingProceedings of the 12th international conference on Logic for Programming, Artificial Intelligence, and Reasoning10.1007/11591191_49(712-727)Online publication date: 2-Dec-2005
https://dl.acm.org/doi/10.1007/11591191_49
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents