Data Partition and Parallel Evaluation of Datalog Programs.

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)
  author    = {Weining Zhang and
               Ke Wang and
               Siu-Cheung Chau},
  title     = {Data Partition and Parallel Evaluation of Datalog Programs},
  journal   = {IEEE Trans. Knowl. Data Eng.},
  volume    = {7},
  number    = {1},
  year      = {1995},
  pages     = {163-176},
  ee        = {db/journals/tkde/ZhangWC95.html},
  bibsource = {DBLP,}


Parallel bottom-up evaluation provides an alternative for the efficient evaluation of logic programs. Existing parallel evaluation strategies are neither effective nor efficient in determining the data to be transmitted among processors. In this paper, we propose a different strategy, for general Datalog programs, that is based on the partitioning of data rather than that of rule instantiations. The partition and processing schemes defined in this paper are more general than those in existing strategies. A parallel evaluation algorithm is given based on the semi-naive bottom-up evaluation. A notion of potential usefulness is recognized as a data transmission criterion to reduce, both effectively and efficiently, the amount of data transmitted. Heuristics and algorithms are proposed for designing the partition and processing schemes for a given program. Results from an experiment show that the strategy proposed in this paper has many promising features.

Copyright © 1995 by The Institute of Electrical and Electronic Engineers, Inc. (IEEE). Abstract used with permission.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 3, TKDE 1993-1995" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX


François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52 BibTeX
Jean-Pierre Cheiney, Christophe de Maindreville: A Parallel Strategy for Transitive Closure usind Double Hash-Based Clustering. VLDB 1990: 347-358 BibTeX
Simona Rabinovici-Cohen, Ouri Wolfson: Why a Single Parallelization Strategy in not Enough in Knowledge Bases. PODS 1989: 200-216 BibTeX
Saumya K. Debray, Nai-Wei Lin: Static Estimation of Query Sizes in Horn Programs. ICDT 1990: 514-528 BibTeX
Guozhu Dong: On Distributed Processibility of Datalog Queries by Decomposing Databases. SIGMOD Conference 1989: 26-35 BibTeX
Sumit Ganguly, Abraham Silberschatz, Shalom Tsur: A Framework for the Parallel Processing of Datalog Queries. SIGMOD Conference 1990: 143-152 BibTeX
John W. Lloyd: Foundations of Logic Programming, 2nd Edition. Springer 1987, ISBN 3-540-18199-7
Jürgen Seib, Georg Lausen: Parallelizing Datalog Programs by Generalized Pivoting. PODS 1991: 241-251 BibTeX
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX
Joel L. Wolf, Daniel M. Dias, Philip S. Yu, John Turek: An Effective Algorithm for Parallelizing Hash Joins in the Presence of Data Skew. ICDE 1991: 200-209 BibTeX
Ouri Wolfson, Weining Zhang, Harish Butani, Akira Kawaguchi, Kui W. Mok: A Methodology for Evaluating Parallel Graph Algorithms and Its Application to Single Source Reachability. PDIS 1993: 243-250 BibTeX
Ouri Wolfson, Abraham Silberschatz: Distributed Processing of Logic Programs. SIGMOD Conference 1988: 329-336 BibTeX
Ouri Wolfson, Aya Ozeri: A New Paradigm for Parallel and Distributed Rule-Processing. SIGMOD Conference 1990: 133-142 BibTeX
Ouri Wolfson: Sharing the Load of Logic-Program Evaluation. DPDS 1988: 46-55 BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
IEEE Transactions on Data and Knowledge Engineering: Copyright © by IEEE,
Joint ACM SIGMOD / IEEE Computer Society Anthology: Copyright © by ACM ( and IEEE, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sun May 17 00:28:15 2009