Parallel and distributed processing of rules by data-reduction

Author

Wolfson, Ouri ; Ozeri, Aya

Author_Institution

Dept. of Comput. Sci., Columbia Univ., New York, NY, USA

Volume

5

Issue

3

fYear

1993

fDate

6/1/1993 12:00:00 AM

Firstpage

523

Lastpage

530

Abstract

The parallel evaluation of datalog rule programs, mainly by processors that are interconnected by a communication network, is discussed. Data-reduction, a paradigm for the parallel evaluation of a datalog program, is introduced. Parallelization is accomplished by partitioning the rule-instantiations among the processors. After presenting the paradigm, its implementation with seminaive evaluation, its communication overhead, and its application to stratified-negation datalog programs are discussed. It is proven that decomposability, a related concept introduced in previous works, is undecidable

Keywords

distributed databases; knowledge based systems; logic programming; communication network; communication overhead; data-reduction; datalog rule programs; decomposability; distributed processing of rules; parallel processing of rules; rule-instantiations; seminaive evaluation; stratified-negation datalog programs; Communication networks; Computer science; Concurrent computing; Costs; Distributed processing; Indexes; Logic programming; Parallel processing; Relational databases; Transaction databases;

fLanguage

English

Journal_Title

Knowledge and Data Engineering, IEEE Transactions on

Publisher

ieee

ISSN

1041-4347

Type

jour

DOI

10.1109/69.224203

Filename

224203