Space Optimization in the Bottom-Up Evaluation of Logic Programs

Summary: Space optimization in bottom-up logic-program evaluation via discarding no-longer-needed facts. Three components: propagate all derivations per fact, detect duplicate derivations, and order evaluation to minimize fact lifetimes; shows how combining methods yields a complete, more general solution than prior work. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2577
Venue: SIGMOD
Year: 1991
Pagerank: 5.5684407e-05
Overall Rank: 7,679 | 47.32%
DOI: 10.1145/115790.115798

Incoming Non-self Citations Over Time

Authors

1. S. Sudarshan (University of Wisconsin)
2. Divesh Srivastava (University of Wisconsin)
3. Raghu Ramakrishnan (University of Wisconsin)
4. Jeffrey F. Naughton (University of Wisconsin)

BibTeX Citation

@inproceedings{sudarshan_sigmod91,
        title = {{Space Optimization in the Bottom-Up Evaluation of Logic Programs}},
        author = {Sudarshan, S. and Srivastava, Divesh and Ramakrishnan, Raghu and Naughton, Jeffrey F.},
        series = {{SIGMOD} '91},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/115790.115798},
        url = {https://dl.acm.org/doi/10.1145/115790.115798},
        year = {1991}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,520	Context-Sensitive Program Analysis as Database Queries	2005	PODS	6.6472658e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
7,680	Rule Ordering in Bottom-Up Fixpoint Evaluation of Logic Programs	1990	VLDB	5.5684407e-05
8,296	How to Forget the Past Without Repeating It	1990	VLDB	5.4574671e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,634	Translation and Optimization of Logic Queries: The Algebraic Approach	1986	VLDB
2	7,886	Polynomial-time program transformations in deductive databases	1990	PODS
3	7,824	Termination Detection in Logic Programs using Argument Sizes* (Extended Abstract)	1991	PODS
4	11,135	Query Optimization by Quantifier Elimination	2024	PODS
5	13,099	Structural Query Optimization — A Uniform Framework For Semantic Query Optimization In Deductive Databases	1991	PODS
6	11,838	Compiling Existential-Positive Queries to Bounded-Variable Fragments	2019	PODS
7	7,680	Rule Ordering in Bottom-Up Fixpoint Evaluation of Logic Programs	1990	VLDB
8	6,729	Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries	1990	VLDB
9	8,296	How to Forget the Past Without Repeating It	1990	VLDB
10	13,100	Detecting Redundant Tuples During Query Evaluation	1991	PODS