ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Right-, left- and multi-linear rule transformations that maintain context information.

David B. Kemp, Kotagiri Ramamohanarao, Zoltan Somogyi: Right-, left- and multi-linear rule transformations that maintain context information. VLDB 1990: 380-391
@inproceedings{DBLP:conf/vldb/KempRS90,
  author    = {David B. Kemp and
               Kotagiri Ramamohanarao and
               Zoltan Somogyi},
  editor    = {Dennis McLeod and
               Ron Sacks-Davis and
               Hans-J{\"o}rg Schek},
  title     = {Right-, left- and multi-linear rule transformations that maintain
               context information},
  booktitle = {16th International Conference on Very Large Data Bases, August
               13-16, 1990, Brisbane, Queensland, Australia, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1990},
  isbn      = {1-55860-149-X},
  pages     = {380-391},
  ee        = {db/conf/vldb/KempRS90.html},
  crossref  = {DBLP:conf/vldb/90},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We present an algorithm that takes recursive rules, predicates and queries belonging to a particular class and transforms them into rules, predicates and queries that allow efficient bottom-up computation of answers. This work extends the work presented in "Eficient evaluation of right-, left-,and multi-linear rules" by J. Naughton, R. Ramakrishnan, Y. Sagiv, and J. Ullman. Our transformation can handle calls whose input arguments are not manifest constants but are computed by other calls in the query, and it can handle predicates containing pseudo-left-linear rules together with right-linear and/or multi-linear rules. The first of those properties allows us to apply our algorithm effectively to calls that occur in the bodies of rules as well as in queries. Experimental results indicate that our algorithm can achieve considerable speedups over previous methods.

Copyright © 1990 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.


Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Dennis McLeod, Ron Sacks-Davis, Hans-Jörg Schek (Eds.): 16th International Conference on Very Large Data Bases, August 13-16, 1990, Brisbane, Queensland, Australia, Proceedings. Morgan Kaufmann 1990, ISBN 1-55860-149-X
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[1]
...
[2]
Isaac Balbin, Graeme S. Port, Kotagiri Ramamohanarao, Krishnamurthy Meenakshi: Efficient Bottom-UP Computation of Queries on Stratified Databases. J. Log. Program. 11(3&4): 295-344(1991) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[3]
Isaac Balbin, Kotagiri Ramamohanarao: A Generalization of the Differential Approach to Recursive Query Evaluation. J. Log. Program. 4(3): 259-262(1987) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[4]
...
[5]
François Bancilhon, David Maier, Yehoshua Sagiv, Jeffrey D. Ullman: Magic Sets and Other Strange Ways to Implement Logic Programs. PODS 1986: 1-15 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[6]
...
[7]
Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. PODS 1987: 269-284 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[8]
Jiawei Han, Ling Liu: Processing Multiple Linear Recursions. NACLP 1989: 816-830 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[9]
David B. Kemp, Kotagiri Ramamohanarao, Isaac Balbin, Krishnamurthy Meenakshi: Propagating Constraints in Recusive Deduction Databases. NACLP 1989: 981-998 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[10]
...
[11]
Jean-Marc Kerisit, Jean-Marc Pugin: Efficient Query Answering on Stratified Databases. FGCS 1988: 719-726 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[12]
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
[13]
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
[14]
...
[15]
J. Rohmer, R. Lescoeur, Jean-Marc Kerisit: The Alexander Method - A Technique for The Processing of Recursive Axioms in Deductive Databases. New Generation Comput. 4(3): 273-285(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[16]
Domenico Saccà, Carlo Zaniolo: The Generalized Counting Method for Recursive Logic Queries. ICDT 1986: 31-53 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[17]
Domenico Saccà, Carlo Zaniolo: Magic Counting Methods. SIGMOD Conference 1987: 49-59 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[18]
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
[19]
Jeffrey D. Ullman: Bottom-Up Beats Top-Down for Datalog. PODS 1989: 140-149 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[20]
...

Copyright © Tue Mar 16 02:22:01 2010 by Michael Ley (ley@uni-trier.de)