Controlling the Search in Bottom-Up Evaluation

Abstract

Bottom-up evaluation of queries on deductive databases has many advantages over an evaluation scheme such as Prolog. It is sound and complete with respect to the declarative semantics of least Herbrand models for positive Horn clause programs. In particular, it is able to avoid infinite loops by detecting repeated (possibly cyclic) subgoals. Further, in many database applications, it is more efficient than Prolog due to its set-orientedness. However, the completely set-oriented, breadth-first search strategy of bottomup evaluation has certain disadvantages. For example, to evaluate several classes of programs with negation (or aggregation), it is necessary to order the inferences; in essence, we must evaluate all answers to a negative subgoal before making an inference that depends upon the negative subgoal. A completely breadth-first search strategy ([14]) would have to maintain a lot of redundant subgoal dependency information to achieve this. We present a technique to order the use ...