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

A Framework for the Parallel Evaluation of Recursive Queries in Deductive Databases.

Runping Qi, Wolfgang Bibel: A Framework for the Parallel Evaluation of Recursive Queries in Deductive Databases. DASFAA 1989: 301-309
@inproceedings{DBLP:conf/dasfaa/QiB89,
  author    = {Runping Qi and
               Wolfgang Bibel},
  editor    = {Sukho Lee and
               Hideko S. Kunii and
               Won Kim and
               In Sup Paik and
               Yahiko Kambayashi},
  title     = {A Framework for the Parallel Evaluation of Recursive Queries
               in Deductive Databases},
  booktitle = {International Symposium on Database Systems for Advanced Applications,
               Seoul, Korea, April 10-12, 1989},
  publisher = {Dept. of Computer Science, KAIST, P.O. Box 150, ChongRyang, Seoul,
               131-650, Korea},
  year      = {1989},
  pages     = {301-309},
  ee        = {db/conf/dasfaa/QiB89.html},
  crossref  = {DBLP:conf/dasfaa/89},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

In this paper we present a parallel processing model for the evaluation of recursive queries in Deductive Databases. The model is based on what we call reduced rule dependency graph. For each group of mutually recursive predicates and each possible query mode on those predicates, a process class to compute the answer to the query mode is created by a compiler. The process instantiationa are created dynamicdly by the processes which depend on the results obtained by these process instantiations. In this model three kinds of parallelism are exploited: and-parallelism, pipeline-parallelism and loop-parallelism. Or-parallelism is obtained implicitly by the set-oriented treatment of processes. Because the processes are responsible for a rather elaborate task, the overhead is significantly less than that in the models proposed so far for Horn logic programs. The model also allows optimization techniques to be incorporated as appropriate in a concrete situation.

Copyright © 1989 by The Organizing Commitee of the International Symposium on Database Systems for Advanced Applications. Permission to copy without all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the DASFAA copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Organizing Commitee of the International Symposium on Database Systems for Advanced Applications. To copy otherwise, or to republish, requires a fee and/or special permission from the Organizing Commitee.


ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 2 Issue 2, EDBT, ICDT, MFDBS, DASFAA" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

References

[1]
François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52 BibTeX
[2]
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
[3]
...
[4]
...
[5]
...
[6]
Atsuhiro Goto, Hidehiko Tanaka, Tohru Moto-Oka: Highly Parallel Inference Engine PIE: Goal Rewriting Model and Machine Architecture. New Generation Comput. 2(1): 37-58(1984) BibTeX
[7]
Lawrence J. Henschen, Shamim A. Naqvi: On compiling queries in recursive first-order databases. J. ACM 31(1): 47-85(1984) BibTeX
[8]
Laxmikant V. Kalé: The REDUCE-OR Process Model for Parallel Evaluation of Logic Programs. ICLP 1987: 616-632 BibTeX
[9]
Michael Kifer, Eliezer L. Lozinskii: Filtering Data Flow in Deductive Databases. ICDT 1986: 186-202 BibTeX
[10]
...
[11]
...
[12]
Raghu Ramakrishnan: Magic Templates: A Spellbinding Approach to Logic Programs. ICLP/SLP 1988: 140-159 BibTeX
[13]
Domenico Saccà, Carlo Zaniolo: On the Implementation of a Simple Class of Logic Queries for Databases. PODS 1986: 16-23 BibTeX
[14]
Domenico Saccà, Carlo Zaniolo: The Generalized Counting Method for Recursive Logic Queries. ICDT 1986: 31-53 BibTeX
[15]
Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX
[16]
Jeffrey D. Ullman: Implementation of Logical Query Languages for Databases. ACM Trans. Database Syst. 10(3): 289-321(1985) BibTeX
[17]
Maarten H. van Emden, Robert A. Kowalski: The Semantics of Predicate Logic as a Programming Language. J. ACM 23(4): 733-742(1976) BibTeX
[18]
Allen Van Gelder: A Message Passing Framework for Logical Query Evaluation. SIGMOD Conference 1986: 155-165 BibTeX
[19]
Carlo Zaniolo: Safety and Compilation of Non-recursive Horn Clauses. Expert Database Conf. 1986: 237-252 BibTeX
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:05:14 2009