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

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

References

[1]
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
[2]
Jean-Pierre Cheiney, Christophe de Maindreville: A Parallel Strategy for Transitive Closure usind Double Hash-Based Clustering. VLDB 1990: 347-358 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[3]
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
[4]
Saumya K. Debray, Nai-Wei Lin: Static Estimation of Query Sizes in Horn Programs. ICDT 1990: 514-528 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[5]
Guozhu Dong: On Distributed Processibility of Datalog Queries by Decomposing Databases. SIGMOD Conference 1989: 26-35 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[6]
Sumit Ganguly, Abraham Silberschatz, Shalom Tsur: A Framework for the Parallel Processing of Datalog Queries. SIGMOD Conference 1990: 143-152 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[7]
John W. Lloyd: Foundations of Logic Programming, 2nd Edition. Springer 1987, ISBN 3-540-18199-7
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[8]
Jürgen Seib, Georg Lausen: Parallelizing Datalog Programs by Generalized Pivoting. PODS 1991: 241-251 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[9]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[12]
Ouri Wolfson, Abraham Silberschatz: Distributed Processing of Logic Programs. SIGMOD Conference 1988: 329-336 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[13]
Ouri Wolfson, Aya Ozeri: A New Paradigm for Parallel and Distributed Rule-Processing. SIGMOD Conference 1990: 133-142 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[14]
Ouri Wolfson: Sharing the Load of Logic-Program Evaluation. DPDS 1988: 46-55 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[15]
...

Copyright © Mon Nov 2 21:58:01 2009 by Michael Ley (ley@uni-trier.de)