On distributed processibility of datalog queries by decomposing databases

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