Rule Ordering in Bottom-Up Fixpoint Evaluation of Logic Programs

Logic programs can be evaluated bottom-up by repeatedly applying all rules, in "iterations ", until the fixpoint is reached. However, it is often desirable---and in some cases, e.g. programs with stratified negation, even necessary to guarantee the semantics---to apply the rules in some order. We present two algorithms that apply rules in a specified order without repeating inferences. One of them (GSN) is capable of dealing with a wide range of rule orderings but with a little more overhead than the well-known semi-naive algorithm (which we call BSN). The other (PSN) handles a smaller class of rule orderings, but with no overheads beyond those in BSN. We also demonstrate that by choosing a good ordering, we can reduce the number of rule applications (and thus joins). We present a theoretical analysis of rule orderings and identify orderings that minimize the number of rule applications (for all possible instances of the base relations) with respect to a class of orderings called fair ..