How to Forget the Past Without Repeating It.

Jeffrey F. Naughton, Raghu Ramakrishnan: How to Forget the Past Without Repeating It. VLDB 1990: 278-289

@inproceedings{DBLP:conf/vldb/NaughtonR90,
  author    = {Jeffrey F. Naughton and
               Raghu Ramakrishnan},
  editor    = {Dennis McLeod and
               Ron Sacks-Davis and
               Hans-J{\"o}rg Schek},
  title     = {How to Forget the Past Without Repeating It},
  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     = {278-289},
  ee        = {db/conf/vldb/NaughtonR90.html},
  crossref  = {DBLP:conf/vldb/90},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Bottom-up evaluation of deductive database programs has the advantage that it avoids repeated computation by storing all intermediate results and replacing recomputation by table lookup. However, in general, storing all intermediate results for the duration of a computation wastes space. In this paper we propose an evaluation scheme that avoids recomputation, yet under fairly general conditions at any given time stores only a small subset ofthe facts generated. The results constitute a significant first step in compile-time garbage collection for bottom-up evaluation of deductive database programs.

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.

Online Paper

Download PDF file (www.vldb.org, Darmstadt, Germany)
Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/vldb8997 or /cdrom

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

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

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

References

[Ban85]: ...
[Bir80]: Richard S. Bird: Tabulation Techniques for Recursive Programs. ACM Comput. Surv. 12(4): 403-417(1980)
[BMSU86]: François Bancilhon, David Maier, Yehoshua Sagiv, Jeffrey D. Ullman: Magic Sets and Other Strange Ways to Implement Logic Programs. PODS 1986: 1-15
[BR87]: Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. PODS 1987: 269-284
[Coh83]: Norman H. Cohen: Eliminating Redundant Recursive Calls. ACM Trans. Program. Lang. Syst. 5(3): 265-299(1983)
[Hil76]: ...
[Hir75]: Daniel S. Hirschberg: A Linear Space Algorithm for Computing Maximal Common Subsequences. Commun. ACM 18(6): 341-343(1975)
[MR90]: Michael J. Maher, Raghu Ramakrishnan: Déjà Vu in Fixpoints of Logic Programs. NACLP 1989: 963-980
[NRSU89]: Jeffrey F. Naughton, Raghu Ramakrishnan, Yehoshua Sagiv, Jeffrey D. Ullman: Argument Reduction by Factoring. VLDB 1989: 173-182
[Ram88]: Raghu Ramakrishnan: Magic Templates: A Spellbinding Approach to Logic Programs. ICLP/SLP 1988: 140-159
[RBK88]: Raghu Ramakrishnan, Catriel Beeri, Ravi Krishnamurthy: Optimizing Existential Datalog Queries. PODS 1988: 89-102