Rule ordering in bottom-up fixpoint evaluation of logic programs.
Raghu Ramakrishnan, Divesh Srivastava and S. Sudarshan.
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.
An important property of a fixpoint evaluation algorithm is
that it does not repeat inferences; we say that such algorithms
have the semi-naive property. The semi-naive algorithms in
the literature do not address the issue of how to apply rules
in a specified order while retaining the semi-naive property.
We present two algorithms; one (GSN) is capable of dealing
with a wide range of rule orderings but with a little more
overhead than the usual semi-naive algorithm (which we call
BSN). The other (OSN, and a variant, PSN) handles a smaller
class of rule orderings, but with no overheads beyond those
in BSN. This smaller class is sufficiently powerful to
enforce the ordering required to implement stratified programs.
We demonstrate that rule orderings can offer another important
benefit: by choosing a good ordering, we can reduce the number
of rule applications (and thus joins). We present a
theoretical analysis of rule orderings. In particular, we
identify a class of orderings, called cycle-preserving 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 orderings. We also show that while
non-fair orderings may do a little better on some data sets,
they can do much worse on others; this suggests that it is
advisable to consider only fair orderings in the absence of
additional information that could guide the choice of a
non-fair ordering.
We conclude by presenting performance results that bear out
our theoretical analyses.