ACM SIGMOD Anthology TODS dblp.uni-trier.de

Space Optimization in Deductive Databases.

Divesh Srivastava, S. Sudarshan, Raghu Ramakrishnan, Jeffrey F. Naughton: Space Optimization in Deductive Databases. ACM Trans. Database Syst. 20(4): 472-516(1995)
@article{DBLP:journals/tods/SrivastavaSRN95,
  author    = {Divesh Srivastava and
               S. Sudarshan and
               Raghu Ramakrishnan and
               Jeffrey F. Naughton},
  title     = {Space Optimization in Deductive Databases},
  journal   = {ACM Trans. Database Syst.},
  volume    = {20},
  number    = {4},
  year      = {1995},
  pages     = {472-516},
  ee        = {http://doi.acm.org/10.1145/219035.219056, db/journals/tods/SrivastavaSRN95.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

In the bottom-up evaluation of logic programs and recursively defined views on databases, all generated facts are usually assumed to be stored until the end of the evaluation. Discarding facts during the evaluation, however, can considerably improve the efficiency of the evaluation: the space needed to evaluate the program, the I/O costs, the costs of maintaining and accessing indices, and the cost of eliminating duplicates may all be reduced. 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. We show that every such space optimization method has certain components, the first to ensure soundness and completeness, the second to avoid redundancy (i.e., repetition of derivations), and the third to reduce "fact lifetimes" (i.e., the time period for which each fact must be retained during evaluation). We present new techniques based on providing bounds on the number of derivations and uses of facts, and using monotonicity constraints for each of the first two components, and provide novel synchronization techniques for the third component of a space optimization method. We describe how techniques for each of the three components can be combined in practice to obtain a space optimization method for a program. Our results are also of importance in applications such as sequence querying, and in active databases where triggers are defined over multiple "events."

Copyright © 1995 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.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 2, TODS 1991-1995, TKDE 1989-1992" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

Online Edition: ACM Digital Library

[Abstract, Index Terms and Review]
[Full Text in PDF Format, 3146 KB]

References

[Balbin and Ramamohanarao 1987]
Isaac Balbin, Kotagiri Ramamohanarao: A Generalization of the Differential Approach to Recursive Query Evaluation. J. Log. Program. 4(3): 259-262(1987) BibTeX
[Bancilhon 1985]
...
[Beeri and Ramakrishnan 1991]
Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. J. Log. Program. 10(1/2/3&4): 255-299(1991) BibTeX
[Debray and Warren 1989]
Saumya K. Debray, David Scott Warren: Functional Computations in Logic Programs. ACM Trans. Program. Lang. Syst. 11(3): 451-481(1989) BibTeX
[Gehani et al. 1992]
Narain H. Gehani, H. V. Jagadish, Oded Shmueli: Composite Event Specification in Active Databases: Model & Implementation. VLDB 1992: 327-338 BibTeX
[Hirschberg 1975]
Daniel S. Hirschberg: A Linear Space Algorithm for Computing Maximal Common Subsequences. Commun. ACM 18(6): 341-343(1975) BibTeX
[Jagadish et al. 1992]
...
[Kemp et al. 1990]
David B. Kemp, Kotagiri Ramamohanarao, Zoltan Somogyi: Right-, left- and multi-linear rule transformations that maintain context information. VLDB 1990: 380-391 BibTeX
[Krishnamurthy et al. 1988]
Ravi Krishnamurthy, Raghu Ramakrishnan, Oded Shmueli: A Framework for Testing Safety and Effective Computability of Extended Datalog (Extended Abstract). SIGMOD Conference 1988: 154-163 BibTeX
[Lloyd 1987]
John W. Lloyd: Foundations of Logic Programming, 2nd Edition. Springer 1987, ISBN 3-540-18199-7
BibTeX
[Maher and Ramakrishnan 1989]
Michael J. Maher, Raghu Ramakrishnan: Déjà Vu in Fixpoints of Logic Programs. NACLP 1989: 963-980 BibTeX
[Naughton and Ramakrishnan 1994]
Jeffrey F. Naughton, Raghu Ramakrishnan: How to Forget the Past Without Repeating It. J. ACM 41(6): 1151-1177(1994) BibTeX
[Naughton et al. 1989]
Jeffrey F. Naughton, Raghu Ramakrishnan, Yehoshua Sagiv, Jeffrey D. Ullman: Efficient Evaluation of Right-, Left-, and Mult-Lineare Rules. SIGMOD Conference 1989: 235-242 BibTeX
[Ramakrishnan 1988]
Raghu Ramakrishnan: Magic Templates: A Spellbinding Approach to Logic Programs. ICLP/SLP 1988: 140-159 BibTeX
[Ramakrishnan et al. 1988]
Raghu Ramakrishnan, Catriel Beeri, Ravi Krishnamurthy: Optimizing Existential Datalog Queries. PODS 1988: 89-102 BibTeX
[Ramakrishnan et al. 1994]
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) BibTeX
[Roth et al. 1993]
William G. Roth, Raghu Ramakrishnan, Praveen Seshadri: MIMSY: A System for Analyzing Time Series Data in the Stock Market Domain. Workshop on Programming with Logic Databases (Informal Proceedings), ILPS 1993: 33-43 BibTeX
[Seshadri et al. 1994]
Praveen Seshadri, Miron Livny, Raghu Ramakrishnan: Sequence Query Processing. SIGMOD Conference 1994: 430-441 BibTeX
[Shmueli 1987]
Oded Shmueli: Decidability and Expressiveness of Logic Queries. PODS 1987: 237-249 BibTeX
[Srivastava et al. 1991]
...
[Tsur et al. 1990]
Shalom Tsur, Frank Olken, Dalit Naor: Deductive Databases for Genomic Mapping (Extended Abstract). Workshop on Deductive Databases 1990: 0- BibTeX
[Ullman 1989-1]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX
[Ullman 1989-2]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Tue Jun 24 18:39:18 2008