RULE ORDERING IN BOTTOM-UP FIXPOINT EVALUATION OF LOGIC PROGRAMS

Logic programs can be evaluated bottom-up by repeatedly applying all r ules, in ''iterations,'' until the fixpoint is reached. However, it is often desirable-and, in some cases, e.g., programs with stratified ne gation, it is even necessary to guarantee the semantics-to apply the r ules in some order. We present two algorithms that apply rules in a sp ecified order without repeating inferences. One of them (GSN) is capab le of dealing with a wide range of rule orderings, but with a little m ore overhead than the well-known seminaive algorithm (which we call BS N). The other (PSN) handles a smaller class of rule orderings, but wit h no overheads beyond those in BSN. We also demonstrate that by choosi ng a good ordering, we can reduce the number of rule applications (and thus the number of joins). We present a theoretical analysis of rule orderings and identify orderings that minimize the number of rule appl ications (for all possible instances of the base relations) with respe ct to a class of orderings called fair orderings. We also show that th ough nonfair orderings may do a little better on some data sets, they can do much worse on others. The analysis is supplemented by performan ce results.