Evaluating logical queries by means of communicating processes

A framework has been proposed for evaluating queries in a deductive database system. The framework is based on modeling the intentional database rules and the extensional database relations by using a special class of petri nets called predicate/transition nets. A system of communicating processes is then derived from the predicate/transition net model. Thus, parallel query evaluation becomes the issue of how concurrent processes compute intermediate relations based on the given extensional database relations, communicate and synchronize with each other through message passing to produce the evaluation result. In the framework, the AND/OR parallelisms are exploited with the augmentation of the heuristics of maximizing the bound arguments and utilizing the sideways information passing to restrict the computation to generating those portions of intermediate relations that are relevant to the query. The research results have indicated that the framework is sound and complete and lends itself to a parallel implementation