ACM SIGMOD Anthology TKDE dblp.uni-trier.de

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)
@article{DBLP:journals/tkde/ZhangWC95,
  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, http://dblp.uni-trier.de}
}
BibTeX

Abstract

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

References

[1]
François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52 BibTeX
[2]
Jean-Pierre Cheiney, Christophe de Maindreville: A Parallel Strategy for Transitive Closure usind Double Hash-Based Clustering. VLDB 1990: 347-358 BibTeX
[3]
Simona Rabinovici-Cohen, Ouri Wolfson: Why a Single Parallelization Strategy in not Enough in Knowledge Bases. PODS 1989: 200-216 BibTeX
[4]
Saumya K. Debray, Nai-Wei Lin: Static Estimation of Query Sizes in Horn Programs. ICDT 1990: 514-528 BibTeX
[5]
Guozhu Dong: On Distributed Processibility of Datalog Queries by Decomposing Databases. SIGMOD Conference 1989: 26-35 BibTeX
[6]
Sumit Ganguly, Abraham Silberschatz, Shalom Tsur: A Framework for the Parallel Processing of Datalog Queries. SIGMOD Conference 1990: 143-152 BibTeX
[7]
John W. Lloyd: Foundations of Logic Programming, 2nd Edition. Springer 1987, ISBN 3-540-18199-7
BibTeX
[8]
Jürgen Seib, Georg Lausen: Parallelizing Datalog Programs by Generalized Pivoting. PODS 1991: 241-251 BibTeX
[9]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX
[10]
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
[11]
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
[12]
Ouri Wolfson, Abraham Silberschatz: Distributed Processing of Logic Programs. SIGMOD Conference 1988: 329-336 BibTeX
[13]
Ouri Wolfson, Aya Ozeri: A New Paradigm for Parallel and Distributed Rule-Processing. SIGMOD Conference 1990: 133-142 BibTeX
[14]
Ouri Wolfson: Sharing the Load of Logic-Program Evaluation. DPDS 1988: 46-55 BibTeX
[15]
...
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 (info@acm.org) and IEEE, Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sun May 17 00:28:15 2009