ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Space Optimization in the Bottom-Up Evaluation of Logic Programs.

S. Sudarshan, Divesh Srivastava, Raghu Ramakrishnan, Jeffrey F. Naughton: Space Optimization in the Bottom-Up Evaluation of Logic Programs. SIGMOD Conference 1991: 68-77
@inproceedings{DBLP:conf/sigmod/SudarshanSRN91,
  author    = {S. Sudarshan and
               Divesh Srivastava and
               Raghu Ramakrishnan and
               Jeffrey F. Naughton},
  editor    = {James Clifford and
               Roger King},
  title     = {Space Optimization in the Bottom-Up Evaluation of Logic Programs},
  booktitle = {Proceedings of the 1991 ACM SIGMOD International Conference on
               Management of Data, Denver, Colorado, May 29-31, 1991},
  publisher = {ACM Press},
  year      = {1991},
  pages     = {68-77},
  ee        = {http://doi.acm.org/10.1145/115790.115798, db/conf/sigmod/SudarshanSRN91.html},
  crossref  = {DBLP:conf/sigmod/91},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

In the bottom-up evaluation of a logic program, all generated facts are usually assumed to be stored until the end of the evaluation. Considerable gains can be achieved by instead discarding facts that are no longer required: the space needed to evaluate the program is reduced, I/O costs may be reduced, and the costs of maintaining and accessing indices, eliminating duplicates etc. are reduced. Thus, discarding facts early could achieve time as well as space improvements.

Given an evaluation method that is sound, complete and does not repeat derivation steps, we consider how facts can be discarded during the evaluation without compromising these properties. Our first contribution is to show that such a space optimization technique has three distinct components. Informally, we must make all derivations that we can with each fact, detect all duplicate derivations of facts and try to order the computation so as to minimize the "life-span" of each fact.

This separation enables us to use different methods for each of the components for different parts of the program. We present several methods for ensuring each of these components. We also briefly describe how to obtain a complete space optimization technique by making a choice of techniques for each component and combining them. Our results apply to a significantly larger class of programs than those considered in [NR90].

Copyright © 1991 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.


ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

James Clifford, Roger King (Eds.): Proceedings of the 1991 ACM SIGMOD International Conference on Management of Data, Denver, Colorado, May 29-31, 1991. ACM Press 1991 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML, SIGMOD Record 20(2), June 1991
Contents

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1070 KB]

References

[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
[Hir75]
Daniel S. Hirschberg: A Linear Space Algorithm for Computing Maximal Common Subsequences. Commun. ACM 18(6): 341-343(1975) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[MR90]
...
[NR90]
Jeffrey F. Naughton, Raghu Ramakrishnan: How to Forget the Past Without Repeating It. VLDB 1990: 278-289 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[RSS90]
Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan: Rule Ordering in Bottom-Up Fixpoint Evaluation of Logic Programs. VLDB 1990: 359-371 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SSRN90]
...
[Ull89]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Fri Mar 12 17:21:29 2010 by Michael Ley (ley@uni-trier.de)