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

Optimizing Existential Datalog Queries.

Raghu Ramakrishnan, Catriel Beeri, Ravi Krishnamurthy: Optimizing Existential Datalog Queries. PODS 1988: 89-102
@inproceedings{DBLP:conf/pods/RamakrishnanBK88,
  author    = {Raghu Ramakrishnan and
               Catriel Beeri and
               Ravi Krishnamurthy},
  title     = {Optimizing Existential Datalog Queries},
  booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, March 21-23, 1988, Austin,
               Texas},
  publisher = {ACM},
  year      = {1988},
  isbn      = {0-89791-263-2},
  pages     = {89-102},
  ee        = {http://doi.acm.org/10.1145/308386.308420, db/conf/pods/RamakrishnanBK88.html},
  crossref  = {DBLP:conf/pods/88},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

The problem of pushing projections in recursive rules has received little attention. The objective of this paper is to motivate this problem and present some (partial) solutions. We consider programs with function-free rules, also known as Datalog programs. After formally defining existential subqueries, we present a syntactic criterion for detecting them and then consider optimization in three areas. 1) We identify the existential subqueries and make them explicit by rewriting the rules. This, in effect, automatically captures some aspects of Prolog's cut operator that are appropriate to the bottom-up model of computation. 2) We eliminate argument positions in recursive rules by "pushing projections". 3) We observe that "pushing projections" in rules also has the effect of making some rules (even recursive rules) redundant and try to (identify and) discard them.

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

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, March 21-23, 1988, Austin, Texas. ACM 1988, ISBN 0-89791-263-2
Contents BibTeX

Online Edition: ACM Digital Library

References

[Afrati et al. 86]
Foto N. Afrati, Christos H. Papadimitriou, George Papageorgiou, Athena Roussou, Yehoshua Sagiv, Jeffrey D. Ullman: Convergence of Sideways Query Evaluation. PODS 1986: 24-30 BibTeX
[Aho and Ullman 79]
Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 BibTeX
[Bancilhon et al. 86]
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
[Bancilhon and Ramakrishnan 86]
François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52 BibTeX
[Bancilhon and Ramakrishnan 87]
...
[Beeri and Ramakrishnan 87]
Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. PODS 1987: 269-284 BibTeX
[Gaifman 86]
...
[Hopcroft and Ullman 79]
John E. Hopcroft, Jeffrey D. Ullman: Introduction to Automata Theory, Languages and Computation. Addison-Wesley 1979, ISBN 0-201-02988-X
BibTeX
[Lloyd 84]
John W. Lloyd: Foundations of Logic Programming, 1st Edition. Springer 1984, ISBN 3-540-13299-6
BibTeX
[Mendelzon 85]
Alberto O. Mendelzon: Functional Dependencies in Logic Programs. VLDB 1985: 324-330 BibTeX
[Ramakrishnan et al. 87]
Raghu Ramakrishnan, François Bancilhon, Abraham Silberschatz: Safety of Recursive Horn Clauses With Infinite Relations. PODS 1987: 328-339 BibTeX
[Shmueli 87]
Oded Shmueli: Decidability and Expressiveness of Logic Queries. PODS 1987: 237-249 BibTeX
[Ullman 85]
Jeffrey D. Ullman: Implementation of Logical Query Languages for Databases. ACM Trans. Database Syst. 10(3): 289-321(1985) BibTeX
[Zaniolo 86]
Carlo Zaniolo: Safety and Compilation of Non-recursive Horn Clauses. Expert Database Conf. 1986: 237-252 BibTeX

Referenced by

  1. Divesh Srivastava, S. Sudarshan, Raghu Ramakrishnan, Jeffrey F. Naughton: Space Optimization in Deductive Databases. ACM Trans. Database Syst. 20(4): 472-516(1995)
  2. Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan, Praveen Seshadri: The CORAL Deductive System. VLDB J. 3(2): 161-210(1994)
  3. Werner Kießling, Helmut Schmidt, Werner Strauß, Gerhard Dünzinger: DECLARE and SDS: Early Efforts to Commercialize Deductive Database Technology. VLDB J. 3(2): 211-243(1994)
  4. Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan, Praveen Seshadri: Implementation of the CORAL Deductive Database System. SIGMOD Conference 1993: 167-176
  5. Russell Greiner: Learning Efficient Query Processing Strategies. PODS 1992: 33-46
  6. Alberto O. Mendelzon, Peter T. Wood: Functional Dependencies in Horn Clause Queries. ACM Trans. Database Syst. 16(1): 31-55(1991)
  7. Yeh-Heng Sheng: A Non-deterministic Deductive Database Language. SIGMOD Conference 1991: 188-197
  8. Burkhard Freitag, Heribert Schütz, Günther Specht: LOLA - A Logic Language for Deductive Databases and its Implementation. DASFAA 1991: 216-225
  9. Danette Chimenti, Ruben Gamboa, Ravi Krishnamurthy, Shamim A. Naqvi, Shalom Tsur, Carlo Zaniolo: The LDL System Prototype. IEEE Trans. Knowl. Data Eng. 2(1): 76-90(1990)
  10. Jeffrey F. Naughton, Raghu Ramakrishnan: How to Forget the Past Without Repeating It. VLDB 1990: 278-289
  11. Yeh-Heng Sheng: IDLOG: Extending the Expressive Power of Deductive Database Languages. SIGMOD Conference 1990: 54-63
  12. Carlo Zaniolo: Deductive Databases - Theory Meets Practice. EDBT 1990: 1-15
  13. Danette Chimenti, Ruben Gamboa, Ravi Krishnamurthy: Abstract Machine for LDL. EDBT 1990: 153-168
  14. Stefano Ceri, Georg Gottlob, Letizia Tanca: What you Always Wanted to Know About Datalog (And Never Dared to Ask). IEEE Trans. Knowl. Data Eng. 1(1): 146-166(1989)
  15. Jeffrey F. Naughton, Raghu Ramakrishnan, Yehoshua Sagiv, Jeffrey D. Ullman: Argument Reduction by Factoring. VLDB 1989: 173-182
  16. Danette Chimenti, Ruben Gamboa, Ravi Krishnamurthy: Towards on Open Architecture for LDL. VLDB 1989: 195-203
  17. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
  18. Ravi Krishnamurthy, Carlo Zaniolo: Control and Optimization Strategies in the Implementation of LDL. DBPL 1987: 329-345
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:33:53 2009