Evaluating Datalog over Semirings: A Grounding-based Approach

Summary: Two-phase framework for Datalog over semirings: grounding to polynomial equations, then least-fixpoint evaluation. Structure-aware grounding minimizes grounding, and efficient fixpoint algorithms cover finite-rank and absorptive totally ordered semirings, with matching lower bounds. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 1921
Venue: PODS
Year: 2024
Pagerank: 5.2415551e-05
Overall Rank: 5,992 | 58.32%
DOI: 10.1145/3651591

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,966	Output-sensitive Conjunctive Query Evaluation	2024	PODS	4.4193184e-05
10,004	Codd's Theorem for Databases over Semirings	2026	PODS	4.1945683e-05
10,284	FlowLog: Efficient and Extensible Datalog via Incrementality	2026	VLDB	4.1945683e-05
10,344	Circuits and Formulas for Datalog over Semirings	2025	PODS	4.1945683e-05
10,357	Rewriting Consistent Answers on Annotated Data	2025	PODS	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
16	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS	0.0010066783
31	Provenance Semirings	2007	PODS	0.0007857786
583	FAQ: Questions Asked Frequently	2016	PODS	0.00019717214
1,037	Querying Graph Databases	2013	PODS	0.00014502493
1,294	Distributed SociaLite: A Datalog-Based Language for Large-Scale Graph Analysis	2013	VLDB	0.00012779484
1,370	Monadic Datalog and the Expressive Power of Languages for Web Information Extraction	2002	PODS	0.00012338027
1,442	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00011956109
2,474	Graph-Theoretic Methods In Database Theory	1990	PODS	8.7135761e-05
2,907	Convergence of Datalog over (Pre-) Semirings	2022	PODS	7.933806e-05
3,024	Secure Yannakakis: Join-Aggregate Queries over Private Data	2021	SIGMOD	7.692511e-05
3,371	On the Enumeration Complexity of Unions of Conjunctive Queries	2019	PODS	7.1696145e-05
5,270	Annotated XML: Queries and Provenance	2008	PODS	5.5963545e-05
6,236	Inherent Complexity of Recursive Queries (Extended Abstract)	1999	PODS	5.1436959e-05
8,995	Efficiently Enumerating Answers to Ontology-Mediated Queries	2022	PODS	4.412512e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,631	Tools for Datalog Boundedness	1991	PODS	6.0347472e-05
13,585	Monadic Datalog over Finite Structures with Bounded Treewidth	2007	PODS	-
8,937	Efficiently Ordering Subgoals with Access Constraints [Extended Abstract]	2006	PODS	4.427232e-05
2,877	Semantic Query Optimization in Datalog Programs (Extended Abstract)	1995	PODS	7.9715251e-05
6,236	Inherent Complexity of Recursive Queries (Extended Abstract)	1999	PODS	5.1436959e-05
7,591	On the First-Order Expressibility of Recursive Queries	1989	PODS	4.702934e-05
10,344	Circuits and Formulas for Datalog over Semirings	2025	PODS	4.1945683e-05
12,904	Structural Query Optimization — A Uniform Framework For Semantic Query Optimization In Deductive Databases	1991	PODS	4.1945683e-05
10,929	Polynomial Time Convergence of the Iterative Evaluation of Datalogo Programs	2024	PODS	4.1945683e-05
2,907	Convergence of Datalog over (Pre-) Semirings	2022	PODS	7.933806e-05