Controlling the search in bottom-up evaluation. Raghu Ramakrishnan, Divesh Srivastava and S. Sudarshan. 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 bottom-up 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 would have to maintain a lot of redundant subgoal dependency information to achieve this. We present a technique to order the use of generated subgoals, that is a hybrid between pure breadth-first and pure depth-first search. The technique, called Ordered_Search, is able to maintain subgoal dependency information efficiently, while being able to detect repeated subgoals, and avoid infinite loops. Also, the technique avoids repeated computation and is complete for DATALOG. We demonstrate the power of Ordered_Search through two applications. First, we show that it can be used to evaluate programs with left-to-right modularly stratified negation and aggregation more efficiently than with any previously known bottom-up technique. Second, we illustrate its use for optimizing single-answer queries for linear programs.