dblp.uni-trier.de www.dagstuhl.de www.uni-trier.de

Rule Ordering in Bottom-Up Fixpoint Evaluation of Logic Programs.

Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan: Rule Ordering in Bottom-Up Fixpoint Evaluation of Logic Programs. VLDB 1990: 359-371
@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        = {http://www.vldb.org/conf/1990/P359.PDF},
  crossref  = {DBLP:conf/vldb/90},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

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.


Printed Edition

Dennis McLeod, Ron Sacks-Davis, Hans-Jörg Schek (Eds.): 16th International Conference on Very Large Data Bases, August 13-16, 1990, Brisbane, Queensland, Australia, Proceedings. Morgan Kaufmann 1990, ISBN 1-55860-149-X
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Journal Version

Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan: Rule Ordering in Bottom-Up Fixpoint Evaluation of Logic Programs. IEEE Trans. Knowl. Data Eng. 6(4): 501-517(1994) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[B85]
...
[BR87]
Isaac Balbin, Kotagiri Ramamohanarao: A Generalization of the Differential Approach to Recursive Query Evaluation. J. Log. Program. 4(3): 259-262(1987) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BPRM]
Isaac Balbin, Graeme S. Port, Kotagiri Ramamohanarao, Krishnamurthy Meenakshi: Efficient Bottom-UP Computation of Queries on Stratified Databases. J. Log. Program. 11(3&4): 295-344(1991) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BRSS89]
...
[H87]
Richard Helm: Inductive and Deductive Control of Logic Programs. ICLP 1987: 488-512 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[H88]
...
[KIC89]
Robert Kabler, Yannis E. Ioannidis, Michael J. Carey: Performance evaluation of algorithms for transitive closure. Inf. Syst. 17(5): 415-441(1992) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KNSS89]
Juhani Kuittinen, Otto Nurmi, Seppo Sippu, Eljas Soisalon-Soininen: Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries. VLDB 1990: 372-379 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Last update Mon Sep 17 22:00:48 2012 CET by the DBLP TeamThis material is Open Data Data released under the ODC-BY 1.0 license — See also our legal information page