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

Efficient Evaluation for a Subset of Recursive Queries.

Gösta Grahne, Seppo Sippu, Eljas Soisalon-Soininen: Efficient Evaluation for a Subset of Recursive Queries. PODS 1987: 284-293
@inproceedings{DBLP:conf/pods/GrahneSS87,
  author    = {G{\"o}sta Grahne and
               Seppo Sippu and
               Eljas Soisalon-Soininen},
  title     = {Efficient Evaluation for a Subset of Recursive Queries},
  booktitle = {Proceedings of the Sixth ACM SIGACT-SIGMOD-SIGART Symposium on
               Principles of Database Systems, March 23-25, 1987, San Diego,
               California},
  publisher = {ACM},
  year      = {1987},
  isbn      = {0-89791-223-3},
  pages     = {284-293},
  ee        = {http://doi.acm.org/10.1145/28659.28690, db/conf/pods/GrahneSS87.html},
  crossref  = {DBLP:conf/pods/87},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Well-known results on graph traversal are used to develop a practical, efficient algorithm for evaluating regularly and linearly recursive queries in databases that contain only binary relations. Transformations are given that reduce a subset of regular and linear queries involving n-ary relations (n > 2) to queries involving only binary relations.

Copyright © 1987 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 Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, March 23-25, 1987, San Diego, California. ACM 1987, ISBN 0-89791-223-3
Contents BibTeX

Online Edition: ACM Digital Library

Journal Version

Gösta Grahne, Seppo Sippu, Eljas Soisalon-Soininen: Efficient Evaluation for a Subset of Recursive Queries. J. Log. Program. 10(1/2/3&4): 301-332(1991) BibTeX

References

[1]
Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 BibTeX
[2]
...
[3]
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
[4]
François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52 BibTeX
[5]
...
[6]
Lawrence J. Henschen, Shamim A. Naqvi: On compiling queries in recursive first-order databases. J. ACM 31(1): 47-85(1984) BibTeX
[7]
Harry B. Hunt III, Thomas G. Szymanski, Jeffrey D. Ullman: Operations on Sparse Relations. Commun. ACM 20(3): 171-176(1977) BibTeX
[8]
...
[9]
Michael Kifer, Eliezer L. Lozinskii: Filtering Data Flow in Deductive Databases. ICDT 1986: 186-202 BibTeX
[10]
...
[11]
Eliezer L. Lozinskii: Evaluating Queries in Deductive Databases by Generating. IJCAI 1985: 173-177 BibTeX
[12]
Domenico Saccà, Carlo Zaniolo: The Generalized Counting Method for Recursive Logic Queries. ICDT 1986: 31-53 BibTeX
[13]
...
[14]
Seppo Sippu, Eljas Soisalon-Soininen: On the Use of Relational Expressions in the Design of Efficient Algorithms (Extended Abstract). ICALP 1985: 456-464 BibTeX
[15]
Thomas G. Szymanski, Jeffrey D. Ullman: Evaluating Relational Expressions with Dense and Sparse Arguments. SIAM J. Comput. 6(1): 109-122(1977) BibTeX
[16]
Robert Endre Tarjan: Depth-First Search and Linear Graph Algorithms. SIAM J. Comput. 1(2): 146-160(1972) BibTeX
[17]
Laurent Vieille: Recursive Axioms in Deductive Databases: The Query/Subquery Approach. Expert Database Conf. 1986: 253-267 BibTeX

Referenced by

  1. Peter T. Wood: Magic Factoring of Closure Programs. PODS 1995: 174-183
  2. Keh-Chang Guh, Clement T. Yu: Efficient Query Processing for a Subset of Linear Recursive Binary Rules. IEEE Trans. Knowl. Data Eng. 6(5): 842-849(1994)
  3. Mihalis Yannakakis: Graph-Theoretic Methods in Database Theory. PODS 1990: 230-242
  4. Bin Jiang: A Suitable Algorithm for Computing Partial Transitive Closures in Databases. ICDE 1990: 264-271
  5. Alberto O. Mendelzon, Peter T. Wood: Finding Regular Simple Paths in Graph Databases. VLDB 1989: 185-193
  6. Hussien Aly, Z. Meral Özsoyoglu: Synchronized Counting Method. ICDE 1989: 366-373
  7. Ramsey W. Haddad, Jeffrey F. Naughton: Counting Methods for Cyclic Relations. PODS 1988: 333-340
  8. Seppo Sippu, Eljas Soisalon-Soininen: An Optimization Strategy for Recursive Queries in Logic Databases. ICDE 1988: 470-477
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:52 2009