next up previous contents
Next: Restricted Or-Parallelism: Up: Or-parallelism Previous: Or-parallelism

Independent Or-Parallelism:

this fashion of or-parallelism arises whenever the different alternatives in a parallel choice-point are independent of each others--i.e., no two alternatives belonging to a choice-point access the same conditional variables. The most common instance of independent or-parallelism occurs when the query which originates or-parallelism is ground, i.e. it does not contain any unbound variable.

Independent or-parallelism has the advantage of not requiring any change to the environment representation scheme adopted in standard sequential implementations. The amount of effort required to design a system exploiting independent or-parallelism is minimal, and guarantees a very high level of efficiency (overhead is limited). On the other hand, its applicability is quite limited (typical example queries with all ground arguments).

Another example of independent or-parallelism comes from the area of deductive databases. One of the most commonly used approaches to parallelization of Datalog programsgif is based on the concept of Decomposability [121, 120]. The notion can be synthesized as follows: given the set of all possible derivable ground atoms tex2html_wrap_inline1080 gif and the Extensional database E, the program is decomposable if there exists a partition tex2html_wrap_inline1086 of tex2html_wrap_inline1080 such that, if tex2html_wrap_inline1090 and tex2html_wrap_inline1092 can be proved from the program, then the derivation tree of g contains only atoms from tex2html_wrap_inline1096 . This notion allows partitioning of the database between different processors, with the guarantee that the computation of a query can be carried on in a processor without the need of any communication. This form of parallelism can be seen as another instance of the independent or-parallel model.

Tue Mar 19 14:37:09 MST 1996