More Efficient Datalog Queries: Subsumptive Tabling Beats Magic Sets

Summary: Subsumptive tabling enables high reuse in top-down evaluation, beating magic-sets bottom-up for Datalog queries. Subsumptive demand transformation makes bottom-up mimic top-down; subsumption optimization boosts reuse, validated on ontology benchmarks. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h4a80e83249606801
Venue: SIGMOD
Year: 2011
Pagerank: 5.8779512e-05
Overall Rank: 6,131 | 58.78%
DOI: 10.1145/1989323.1989393

Incoming Non-self Citations Over Time

Authors

1. K. Tuncay Tekle (LogicBlox; State University of New York at Stony Brook)
2. Yanhong A. Liu (State University of New York at Stony Brook)

BibTeX Citation

@inproceedings{tekle_sigmod11,
        title = {{More Efficient Datalog Queries: Subsumptive Tabling Beats Magic Sets}},
        author = {Tekle, K. Tuncay and Liu, Yanhong A.},
        series = {{SIGMOD} '11},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1989323.1989393},
        url = {https://dl.acm.org/doi/10.1145/1989323.1989393},
        year = {2011}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,050	On the Optimization of Recursive Relational Queries: Application to Graph Queries	2020	SIGMOD	6.2976106e-05
7,271	Efficient Identification of Implicit Facts in Incomplete OWL2-EL Knowledge Bases	2014	VLDB	5.5694935e-05
10,034	Materializing Knowledge Bases via Trigger Graphs	2021	VLDB	5.0925155e-05
10,334	Efficient Enumeration of Recursive Plans in Transformation-based Query Optimizers	2024	VLDB	5.0254535e-05
11,760	Scalable Reasoning on Document Stores via Instance-Aware Query Rewriting	2023	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
317	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.00021220438
328	Declarative Information Extraction Using Datalog with Embedded Extraction Predicates	2007	VLDB	0.00020928928
1,566	Bottom-Up Beats Top-Down For Datalog	1989	PODS	0.00010214543
2,923	Semantic Query Optimization in Datalog Programs (Extended Abstract)	1995	PODS	7.8518874e-05
7,225	Adding Magic to an Optimising Datalog Compiler	2008	SIGMOD	5.5810777e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,566	Bottom-Up Beats Top-Down For Datalog	1989	PODS
2	6,741	Inherent Complexity of Recursive Queries (Extended Abstract)	1999	PODS
3	7,088	On the Expected Size of Recursive Datalog Queries	1991	PODS
4	6,429	Evaluating Datalog over Semirings: A Grounding-based Approach	2024	PODS
5	7,225	Adding Magic to an Optimising Datalog Compiler	2008	SIGMOD
6	13,389	Structural Query Optimization — A Uniform Framework For Semantic Query Optimization In Deductive Databases	1991	PODS
7	9,266	Efficiently Ordering Subgoals with Access Constraints [Extended Abstract]	2006	PODS
8	6,871	Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries	1990	VLDB
9	2,537	A General Datalog-Based Framework for Tractable Query Answering over Ontologies	2009	PODS
10	1,979	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD