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, db/conf/sigmod/Dong89.html},
  crossref  = {DBLP:conf/sigmod/89},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

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

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/smod7592 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

BibTeX

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

Referenced by

Weining Zhang, Ke Wang, Siu-Cheung Chau: Data Partition and Parallel Evaluation of Datalog Programs. IEEE Trans. Knowl. Data Eng. 7(1): 163-176(1995)
Ouri Wolfson, Aya Ozeri: Parallel and Distributed Processing of Rules by Data Reduction. IEEE Trans. Knowl. Data Eng. 5(3): 523-530(1993)
Ing-Miin Hsu, Mukesh Singhal, Ming T. Liu: Distributed Rule Processing in Active Databases. ICDE 1992: 106-113
Ouri Wolfson, Hasanat M. Dewan, Salvatore J. Stolfo, Yechiam Yemini: Incremental Evaluation of Rules and its Relationship to Parallelism. SIGMOD Conference 1991: 78-87
Ouri Wolfson, Aya Ozeri: A New Paradigm for Parallel and Distributed Rule-Processing. SIGMOD Conference 1990: 133-142
Sumit Ganguly, Abraham Silberschatz, Shalom Tsur: A Framework for the Parallel Processing of Datalog Queries. SIGMOD Conference 1990: 143-152

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]