|
|
|
@inproceedings{DBLP:conf/vldb/RamakrishnanSS90,
author = {Raghu Ramakrishnan and
Divesh Srivastava and
S. Sudarshan},
editor = {Dennis McLeod and
Ron Sacks-Davis and
Hans-J{\"o}rg Schek},
title = {Rule Ordering in Bottom-Up Fixpoint Evaluation of Logic Programs},
booktitle = {16th International Conference on Very Large Data Bases, August
13-16, 1990, Brisbane, Queensland, Australia, Proceedings},
publisher = {Morgan Kaufmann},
year = {1990},
isbn = {1-55860-149-X},
pages = {359-371},
ee = {db/conf/vldb/RamakrishnanSS90.html},
crossref = {DBLP:conf/vldb/90},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
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 toapply 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 thusjoins). 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 datasets, 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.
Copyright © 1990 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.