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

An Amateur's Introduction to Recursive Query Processing Strategies.

François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52
@inproceedings{DBLP:conf/sigmod/BancilhonR86,
  author    = {Fran\c{c}ois Bancilhon and
               Raghu Ramakrishnan},
  editor    = {Carlo Zaniolo},
  title     = {An Amateur's Introduction to Recursive Query Processing Strategies},
  booktitle = {Proceedings of the 1986 ACM SIGMOD International Conference on
               Management of Data, Washington, D.C., May 28-30, 1986},
  publisher = {ACM Press},
  year      = {1986},
  pages     = {16-52},
  ee        = {http://doi.acm.org/10.1145/16894.16859, db/conf/sigmod/BancilhonR86.html},
  crossref  = {DBLP:conf/sigmod/86},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

This paper surveys and compares various strategies for processing logic queries in relational databases. The survey and comparison is limited to the case of Horn Clauses with evaluable predicates but without function symbols. The paper is organized in three parts. In the first part, we introduce the main concepts and definitions. In the second, we describe the various strategies. For each strategy, we give its main characteristics, its application range and a detailed description. We also give an example of a query evaluation. The third part of the paper compares the strategies on performance grounds. We first present a set of sample rules and queries which are used for the performance comparisons, and then we characterize the data. Finally, we give an analytical solution for each query/rule system. Cost curves are plotted for specific configurations of the data.

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

Printed Edition

Carlo Zaniolo (Ed.): Proceedings of the 1986 ACM SIGMOD International Conference on Management of Data, Washington, D.C., May 28-30, 1986. ACM Press 1986 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML, SIGMOD Record 15(2)
Contents

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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Aho and Ullman 79]
Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Apt and Van Emden 82]
Krzysztof R. Apt, Maarten H. van Emden: Contributions to the Theory of Logic Programming. J. ACM 29(3): 841-862(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Bancilhon 85]
...
[Bancilhon 85a]
...
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Bancilhon et al. 86a]
...
[Bancilhon and Ramakrishnan 86]
...
[Bayer 85]
...
[Chang 81]
Chin-Liang Chang: On Evaluation of Queries Containing Derived Relations in a Relational Data Base. Advances in Data Base Theory 1979: 235-260 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Dayal et al. 85]
...
[Delobel 86]
...
[Dietrich and Warren 85]
...
[Gallaire et al. 84]
...
[Gardarin and Maindreville 85]
Georges Gardarin, Christophe de Maindreville: Evaluation of Database Recursive Logic Programs as Recurrent Function Series. SIGMOD Conference 1986: 177-186 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Han and Lu 86]
Jiawei Han, Hongjun Lu: Some Performance Results on Recursive Query Processing in Relational Database Systems. ICDE 1986: 533-541 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Henschen and Naqvi 84]
Lawrence J. Henschen, Shamim A. Naqvi: On compiling queries in recursive first-order databases. J. ACM 31(1): 47-85(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Kifer and Lozinskii 85]
...
[Laskowski 84]
...
[Lozinskii 83]
...
[Lozinskii 85]
...
[Lozinskii 85a]
...
[Marque-Pucheu 83]
...
[Marque-Pucheu et al. 84]
...
[McKay and Shapiro 81]
...
[Morris et al. 86]
Katherine A. Morris, Jeffrey D. Ullman, Allen Van Gelder: Design Overview of the NAIL! System. ICLP 1986: 554-568 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Naqvi and Fishman 81]
...
[Naqvi and Henschen 83]
...
[Reiter 78]
...
[Rohmer and Lescoeur 85]
...
[Rosenthal et al. 85]
...
[Sacca and Zaniolo 86a]
Domenico Saccà, Carlo Zaniolo: On the Implementation of a Simple Class of Logic Queries for Databases. PODS 1986: 16-23 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sacca and Zaniolo 86b]
...
[Sagiv and Ullman 84]
...
[Shapiro and McKay 80]
Stuart C. Shapiro, Donald P. McKay: Inference with Recursive Rules. AAAI 1980: 151-153 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Shapiro at al. 82]
...
[Tarski 55]
...
[Ullman 85]
Jeffrey D. Ullman: Implementation of Logical Query Languages for Databases. ACM Trans. Database Syst. 10(3): 289-321(1985) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ullman and Van Gelder 85]
...
[Van Emden and Kowalski 76]
Maarten H. van Emden, Robert A. Kowalski: The Semantics of Predicate Logic as a Programming Language. J. ACM 23(4): 733-742(1976) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Valduriez and Boral 86]
Patrick Valduriez, Haran Boral: Evaluation of Recursive Queries Using Join Indices. Expert Database Conf. 1986: 271-293 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Vieille 85]
...
[Vieille 86]
Laurent Vieille: Recursive Axioms in Deductive Databases: The Query/Subquery Approach. Expert Database Conf. 1986: 253-267 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Zaniolo 85]
Carlo Zaniolo: The Representation and Deductive Retrieval of Complex Objects. VLDB 1985: 458-469 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Zaniolo 86]
Carlo Zaniolo: Safety and Compilation of Non-recursive Horn Clauses. Expert Database Conf. 1986: 237-252 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Home | Conferences | Journals | Series | FAQ — Search: Faceted | Complete | Author
Copyright © Thu Dec 24 17:06:20 2009 by Michael Ley (ley@uni-trier.de)