Title

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.

Catalog Record

Share

COinS