Ordered structures for parallel rule-based computations

Abstract

In this paper we present an effective strategy to compute a partial order relation among the literals of a query given by a conjuction of first order literals. This ordering expresses sufficient conditions in order for the subgoals of the query were independent each one to the others and hence they can be evaluated in parallel. To represent the partial ordering so that an efficient strategy to join partial solutions from the subgoals can be obtained, we introduce a structure named the Data Flow Lattice. The problem of determining the optimum partial ordering is proved to be NP-hard, therefore we propose an heuristic algorithm that requires polynomial time in the number of literals and variables of the query. We add also an illustrative example of the algorithm performance.

Keywords:

• Parallel Logic Programming
• Independent and Parallelism
• Data Flow Lattice

C.R. Categories:

• B.2.1
• D.1.6
• E.1