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

A Message Passing Framework for Logical Query Evaluation.

Allen Van Gelder: A Message Passing Framework for Logical Query Evaluation. SIGMOD Conference 1986: 155-165
@inproceedings{DBLP:conf/sigmod/Gelder86,
  author    = {Allen Van Gelder},
  editor    = {Carlo Zaniolo},
  title     = {A Message Passing Framework for Logical Query Evaluation},
  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     = {155-165},
  ee        = {http://doi.acm.org/10.1145/16894.16870, db/conf/sigmod/Gelder86.html},
  crossref  = {DBLP:conf/sigmod/86},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

We formulate the problem of query evaluation over a relational database (EDB) supplemented by function-free Horn clause rules (IDB) as a system of cooperating processes communicating by message passing. Shared memory is not required, making this approach suitable for distributed systems. This modularization offers flexibility of implementation and opportunities to use existing operating system features to enhance performance, as well as providing a step toward practical parallel implementation. The technique is based on top-down construction of a rule/goal graph followed by a mixed top-down and bottom-up evaluation strategy employing "sideways information passing" to restrict the computation to relevant, or at least potentially relevant, portions of intermediate relations. Termination is guaranteed, but the termination conditions are global in general, and their distributed asynchronous detection requires care. We describe an efficient protocol to accomplish this. We describe a greedy information passing strategy and introduce the monotone flow property for rules. We discuss the relation of these concepts to acyclic database schemas and qual trees.

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 ... BibTeX

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 BibTeX , SIGMOD Record 15(2)
Contents

Online Edition: ACM Digital Library

References

[AU79]
Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 BibTeX
[BFM*81]
Catriel Beeri, Ronald Fagin, David Maier, Alberto O. Mendelzon, Jeffrey D. Ullman, Mihalis Yannakakis: Properties of Acyclic Database Schemes. STOC 1981: 355-362 BibTeX
[HN84]
Lawrence J. Henschen, Shamim A. Naqvi: On compiling queries in recursive first-order databases. J. ACM 31(1): 47-85(1984) BibTeX
[Loz85]
Eliezer L. Lozinskii: Evaluating Queries in Deductive Databases by Generating. IJCAI 1985: 173-177 BibTeX
[MS81]
...
[Por85]
...
[Rei78]
Raymond Reiter: On Closed World Data Bases. Logic and Data Bases 1977: 55-76 BibTeX
[Sag83]
Yehoshua Sagiv: A Characterization of Globally Consistent Databases and Their Correct Access Paths. ACM Trans. Database Syst. 8(2): 266-286(1983) BibTeX
[Ull82]
Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX
[Ull84]
...
[Var82]
Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146 BibTeX
[VEK76]
Maarten H. van Emden, Robert A. Kowalski: The Semantics of Predicate Logic as a Programming Language. J. ACM 23(4): 733-742(1976) BibTeX
[Vie85]
...
[Wal81]
...
[Yan81]
Mihalis Yannakakis: Algorithms for Acyclic Database Schemes. VLDB 1981: 82-94 BibTeX

Referenced by

  1. Sérgio Lifschitz, Victor Vianu: A Probabilistic View of Datalog Parallelization. ICDT 1995: 294-307
  2. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
  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. 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)
  5. Wolfgang Nejdl, Stefano Ceri, Gio Wiederhold: Evaluating Recursive Queries in Distributed Databases. IEEE Trans. Knowl. Data Eng. 5(1): 104-121(1993)
  6. Keh-Chang Guh, Clement T. Yu: Efficient Management of Materialized Generalized Transitive Closure in Centralized and Parallel Environments. IEEE Trans. Knowl. Data Eng. 4(4): 371-381(1992)
  7. Keh-Chang Guh, Chengyu Sun, Clement T. Yu: Real Time Retrieval and Update of Materialized Transitive Closure. ICDE 1991: 690-697
  8. Allen Van Gelder: Deriving Constraints Among Argument Sizes in Logic Programs. PODS 1990: 47-60
  9. Seppo Sippu, Eljas Soisalon-Soininen: Multiple SIP Strategies and Bottom-Up Adorning in Logic Query Optimization. ICDT 1990: 485-498
  10. Guy Hulin: Parallel Processing of Recursive Queries in Distributed Architectures. VLDB 1989: 87-96
  11. Jeffrey D. Ullman: Bottom-Up Beats Top-Down for Datalog. PODS 1989: 140-149
  12. Runping Qi, Wolfgang Bibel: A Framework for the Parallel Evaluation of Recursive Queries in Deductive Databases. DASFAA 1989: 301-309
  13. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
  14. Christophe de Maindreville, Eric Simon: Modelling Non Deterministic Queries and Updates in Deductive Databases. VLDB 1988: 395-406
  15. Eliezer L. Lozinskii: Computing Facts in Non-Horn Deductive Systems. VLDB 1988: 273-279
  16. Kyu-Young Whang, Shamkant B. Navathe: An Extended Disjunctive Normal Form Approach for Optimizing Recursive Logic Queries in Loosely Coupled Environments. VLDB 1987: 275-287
  17. Yehoshua Sagiv: Optimizing Datalog Programs. PODS 1987: 349-362
  18. Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. PODS 1987: 269-284
  19. François Bancilhon, David Maier, Yehoshua Sagiv, Jeffrey D. Ullman: Magic Sets and Other Strange Ways to Implement Logic Programs. PODS 1986: 1-15
  20. Domenico Saccà, Carlo Zaniolo: The Generalized Counting Method for Recursive Logic Queries. ICDT 1986: 31-53
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:39:45 2009