Rule Ordering in Bottom-Up Fixpoint Evaluation of Logic Programs

Summary: Introduces GSN/OSN/PSN algorithms for ordered bottom-up fixpoint evaluation that retain semi-naive nonredundancy; OSN/PSN support stratified negation without overhead. Proves cycle-preserving fair orderings minimize rule applications, yielding fewer joins experimentally. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 8148
Venue: VLDB
Year: 1990
Pagerank: 5.5684407e-05
Overall Rank: 7,680 | 47.31%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Raghu Ramakrishnan (University of Wisconsin)
2. Divesh Srivastava (University of Wisconsin)
3. S. Sudarshan (University of Wisconsin)

BibTeX Citation

@article{ramakrishnan_vldb90,
        title = {{Rule Ordering in Bottom-Up Fixpoint Evaluation of Logic Programs}},
        author = {Ramakrishnan, Raghu and Srivastava, Divesh and Sudarshan, S.},
        journal = {PVLDB},
        series = {{VLDB} '90},
        pages = {359},
        year = {1990}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,520	Context-Sensitive Program Analysis as Database Queries	2005	PODS	6.6472658e-05
4,975	Implementation of the CORAL Deductive Database System	1993	SIGMOD	6.41738e-05
7,679	Space Optimization in the Bottom-Up Evaluation of Logic Programs	1991	SIGMOD	5.5684407e-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
1,086	New Strategies for Computing the Transitive Closure of a Database Relation	1987	VLDB	0.00012252192
6,729	Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries	1990	VLDB	5.789691e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,297	The Alternating Fixpoint of Logic Programs with Negation (Extended Abstract)	1989	PODS
2	9,326	Extending Logic Programming	1990	SIGMOD
3	6,301	Evaluating Datalog over Semirings: A Grounding-based Approach	2024	PODS
4	4,634	Translation and Optimization of Logic Queries: The Algebraic Approach	1986	VLDB
5	16	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS
6	13,117	Backward chaining evaluation in stratified disjunctive theories	1990	PODS
7	1,714	Modular Stratification and Magic Sets for DATALOG Programs with Negation	1990	PODS
8	1,419	Every Logic Program Has a Natural Stratification And an Iterated Least Fixed Point Model	1989	PODS
9	7,679	Space Optimization in the Bottom-Up Evaluation of Logic Programs	1991	SIGMOD
10	6,729	Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries	1990	VLDB