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

Download PDF file (www.vldb.org, Darmstadt, Germany)
Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

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

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
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/vldb8997 or /cdrom

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

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
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

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

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)
[3]: Isaac Balbin, Kotagiri Ramamohanarao: A Generalization of the Differential Approach to Recursive Query Evaluation. J. Log. Program. 4(3): 259-262(1987)
[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
[6]: ...
[7]: Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. PODS 1987: 269-284
[8]: Jiawei Han, Ling Liu: Processing Multiple Linear Recursions. NACLP 1989: 816-830
[9]: David B. Kemp, Kotagiri Ramamohanarao, Isaac Balbin, Krishnamurthy Meenakshi: Propagating Constraints in Recusive Deduction Databases. NACLP 1989: 981-998
[10]: ...
[11]: Jean-Marc Kerisit, Jean-Marc Pugin: Efficient Query Answering on Stratified Databases. FGCS 1988: 719-726
[12]: Jeffrey F. Naughton, Raghu Ramakrishnan, Yehoshua Sagiv, Jeffrey D. Ullman: Argument Reduction by Factoring. VLDB 1989: 173-182
[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
[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)
[16]: Domenico Saccà, Carlo Zaniolo: The Generalized Counting Method for Recursive Logic Queries. ICDT 1986: 31-53
[17]: Domenico Saccà, Carlo Zaniolo: Magic Counting Methods. SIGMOD Conference 1987: 49-59
[18]: Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents
[19]: Jeffrey D. Ullman: Bottom-Up Beats Top-Down for Datalog. PODS 1989: 140-149
[20]: ...