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.00010176128
Overall Rank: 1,571 | 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,181	Relational Transducers for Electronic Commerce	1998	PODS	0.00011599434
1,758	Modular Stratification and Magic Sets for DATALOG Programs with Negation	1990	PODS	9.6999549e-05
3,856	Right-, left- and multi-linear rule transformations that maintain context information	1990	VLDB	6.9565167e-05
4,286	On Preservation under Homomorphisms and Unions of Conjunctive Queries	2004	PODS	6.6689702e-05
4,639	Context-Sensitive Program Analysis as Database Queries	2005	PODS	6.4750159e-05
6,149	More Efficient Datalog Queries: Subsumptive Tabling Beats Magic Sets	2011	SIGMOD	5.8557417e-05
6,894	Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries	1990	VLDB	5.6384137e-05
7,622	Modular Acyclicity and Tail Recursion in Logic Programs	1991	PODS	5.4663379e-05
13,420	Implementing Deductive Databases by Linear Programming	1992	PODS	4.9605343e-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
351	A Message Passing Framework for Logical Query Evaluation	1986	SIGMOD	0.00020181666
353	On the Power of Magic	1987	PODS	0.0002014941

Semantically Similar Papers

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