dblp.uni-trier.de www.dagstuhl.de www.uni-trier.de

On Distributed Processibility of Datalog Queries by Decomposing Databases.

Guozhu Dong: On Distributed Processibility of Datalog Queries by Decomposing Databases. SIGMOD Conference 1989: 26-35
@inproceedings{DBLP:conf/sigmod/Dong89,
  author    = {Guozhu Dong},
  editor    = {James Clifford and
               Bruce G. Lindsay and
               David Maier},
  title     = {On Distributed Processibility of Datalog Queries by Decomposing
               Databases},
  booktitle = {Proceedings of the 1989 ACM SIGMOD International Conference on
               Management of Data, Portland, Oregon, May 31 - June 2, 1989},
  publisher = {ACM Press},
  year      = {1989},
  pages     = {26-35},
  ee        = {http://doi.acm.org/10.1145/67544.66929},
  crossref  = {DBLP:conf/sigmod/89},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We consider distributed or parallel processing of datalog queries. We address this issue by decomposing databases into a number of subdatabases such that the computation of a program on a database can be achieved by unioning its independent evaluations on the subdatabases. More specifically, we identity two kinds of distributed-processible programs accorcing to the properties of database decomposition. (i) A program is disjoint distributive if it is distributed processible over a decomposition consisting of subdatabases with disjoint domains. A characterization of such programs is given in terms of an easily decidable syntactic property called connectivity. (ii) A program is bounded distributive if it is distributed processible over a decomposition consisting of subdatabases with a fixed rise. Three interesting characterizations of such a program are presented, the first by bounded recursion, the second by equivalence to a 1-bounded-recursive program, and the third by constant parallel complexity.

Copyright © 1989 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

James Clifford, Bruce G. Lindsay, David Maier (Eds.): Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data, Portland, Oregon, May 31 - June 2, 1989. ACM Press 1989 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML, SIGMOD Record 18(2), June 1989
Contents

Online Edition: ACM Digital Library


References

[AHU]
Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BaRa]
François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CoKa]
Stavros S. Cosmadakis, Paris C. Kanellakis: Parallel Evaluation of Recursive Rule Queries. PODS 1986: 280-293 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CoWo]
Simona Rabinovici-Cohen, Ouri Wolfson: Why a Single Parallelization Strategy in not Enough in Knowledge Bases. PODS 1989: 200-216 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Dong]
Guozhu Dong, Seymour Ginsburg: On the Decomposition of Datalog Program Mappings. Theor. Comput. Sci. 76(1): 143-177(1990) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Dong1]
...
[Even]
...
[GMSV]
Haim Gaifman, Harry G. Mairson, Yehoshua Sagiv, Moshe Y. Vardi: Undecidable Optimization Problems for Database Logic Programs. LICS 1987: 106-115 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ioan]
Yannis E. Ioannidis: A Time Bound on the Materialization of some Recursively Defined Views. VLDB 1985: 219-226 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ll]
John W. Lloyd: Foundations of Logic Programming, 1st Edition. Springer 1984, ISBN 3-540-13299-6
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Naug]
Jeffrey F. Naughton: Data Independent Recursion in Deductive Databases. PODS 1986: 267-279 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[NaSa]
Jeffrey F. Naughton, Yehoshua Sagiv: A Decidable Class of Bounded Recursions. PODS 1987: 227-236 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sagi]
Yehoshua Sagiv: Optimizing Datalog Programs. PODS 1987: 349-362 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[UlVG]
Jeffrey D. Ullman, Allen Van Gelder: Parallel Complexity of Logical Query Programs. Algorithmica 3: 5-42(1988) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Vard]
Moshe Y. Vardi: Decidability and Undecidability Results for Boundedness of Linear Recursive Queries. PODS 1988: 341-351 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[WoSi]
Ouri Wolfson, Abraham Silberschatz: Distributed Processing of Logic Programs. SIGMOD Conference 1988: 329-336 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Wolf]
Ouri Wolfson: Sharing the Load of Logic-Program Evaluation. DPDS 1988: 46-55 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Last update Tue Sep 18 00:25:03 2012 CET by the DBLP TeamThis material is Open Data Data released under the ODC-BY 1.0 license — See also our legal information page