A deductive database consists of facts stored in the extensional database and rules representing the intensional database. Because of the difficulty of evaluating rules, many parallel evaluation algorithms for rules have been presented. This paper p...
A deductive database consists of facts stored in the extensional database and rules representing the intensional database. Because of the difficulty of evaluating rules, many parallel evaluation algorithms for rules have been presented. This paper proposes a new paradigm to evaluate linear recursion rules which contain transitive dependency by using a mesh of processors. An evaluation of normalized rules is a computation of the proof-theoretic meaning of a collection of rules. The normalized recursion rule which contains transitive dependency is defined, the existence of an equivalent expression for the rule is proved, a paradigm using transitive closure operations for parallel evaluation of normalized rule based on the equivalent expression is proposed, and the comparative performances of the parallel evaluation algorithms are presented.