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: 859
Venue: PODS
Year: 1989
Pagerank: 0.00010446034
Overall Rank: 1,538 | 89.45%
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,159	Relational Transducers for Electronic Commerce	1998	PODS	0.00011898742
1,714	Modular Stratification and Magic Sets for DATALOG Programs with Negation	1990	PODS	9.9404301e-05
3,767	Right-, left- and multi-linear rule transformations that maintain context information	1990	VLDB	7.1421254e-05
4,184	On Preservation under Homomorphisms and Unions of Conjunctive Queries	2004	PODS	6.8464183e-05
4,520	Context-Sensitive Program Analysis as Database Queries	2005	PODS	6.6472658e-05
6,008	More Efficient Datalog Queries: Subsumptive Tabling Beats Magic Sets	2011	SIGMOD	6.0114207e-05
6,729	Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries	1990	VLDB	5.789691e-05
7,454	Modular Acyclicity and Tail Recursion in Logic Programs	1991	PODS	5.6128072e-05
13,083	Implementing Deductive Databases by Linear Programming	1992	PODS	5.093636e-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
343	A Message Passing Framework for Logical Query Evaluation	1986	SIGMOD	0.00020669253
344	On the Power of Magic	1987	PODS	0.00020659405

Semantically Similar Papers

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