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. 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 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. The analysis is supplemented
by performance results.