On Distributed Processibility of Datalog Queries by Decomposing Databases

Document Type

Conference Proceeding

Publication Date

6-1989

Find in a Library

Catalog Record

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 identify two kinds of distributed-processible programs according 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 size. 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.

Comments

Presented at the ACM SIGMOD International Conference on Management of Data, Portland, OR, June 1989.

Link to Full Text

Catalog Record

Share

COinS