Bottom-Up Beats Top-Down For Datalog

Summary: For any safe Datalog program P1 and any query Q (a predicate with some bound arguments), there exists a safe Datalog program P2 that computes Q’s answers. Semi-naive bottom-up evaluation of P2 takes no more time than top-down evaluation of P1. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h4ecebe16f8e7741f
Venue: PODS
Year: 1989
Pagerank: 0.00010214543
Overall Rank: 1,566 | 89.48%
DOI: 10.1145/73721.73736

Incoming Non-self Citations Over Time

Authors

1. Jeffrey D. Ullman (Stanford University)

BibTeX Citation

@inproceedings{ullman_pods89,
        address = {New York, NY, USA},
        series = {{PODS} '89},
        title = {{BOTTOM-UP BEATS TOP-DOWN FOR DATALOG}},
        url = {https://dl.acm.org/doi/10.1145/73721.73736},
        doi = {10.1145/73721.73736},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Ullman, Jeffrey D.},
        year = {1989}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,176	Relational Transducers for Electronic Commerce	1998	PODS	0.00011643011
1,744	Modular Stratification and Magic Sets for DATALOG Programs with Negation	1990	PODS	9.7353228e-05
3,848	Right-, left- and multi-linear rule transformations that maintain context information	1990	VLDB	6.9827773e-05
4,270	On Preservation under Homomorphisms and Unions of Conjunctive Queries	2004	PODS	6.6941102e-05
4,618	Context-Sensitive Program Analysis as Database Queries	2005	PODS	6.4995364e-05
6,131	More Efficient Datalog Queries: Subsumptive Tabling Beats Magic Sets	2011	SIGMOD	5.8779512e-05
6,871	Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries	1990	VLDB	5.6597986e-05
7,599	Modular Acyclicity and Tail Recursion in Logic Programs	1991	PODS	5.487029e-05
13,373	Implementing Deductive Databases by Linear Programming	1992	PODS	4.9793485e-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
349	A Message Passing Framework for Logical Query Evaluation	1986	SIGMOD	0.00020255174
352	On the Power of Magic	1987	PODS	0.00020223279

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,293	A Framework for the Parallel Processing of Datalog Queries	1990	SIGMOD
2	4,420	On Distributed Processibility of Datalog Queries by Decomposing Databases	1989	SIGMOD
3	6,201	Safety of Datalog Queries over Infinite Databases	1989	PODS
4	11,495	Polynomial Time Convergence of the Iterative Evaluation of Datalogo Programs	2024	PODS
5	6,708	Selective Provenance for Datalog Programs Using Top-K Queries	2015	VLDB
6	10,365	Size Bound-Adorned Datalog	2026	PODS
7	2,630	Convergence of Datalog over (Pre-) Semirings	2022	PODS
8	6,131	More Efficient Datalog Queries: Subsumptive Tabling Beats Magic Sets	2011	SIGMOD
9	6,429	Evaluating Datalog over Semirings: A Grounding-based Approach	2024	PODS
10	6,871	Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries	1990	VLDB