|
|
|
@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}
}
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.
CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...
,
SIGMOD Record 20(2),
June 1991