Back to papers
Optimizing Recursive Queries with Program Synthesis
Summary: Optimizing recursive queries via program synthesis; introduces the FGH-rule to rewrite recursive programs for faster evaluation. Leverages a program synthesizer, an SMT solver, and an equality saturation system; achieves up to four orders of magnitude speedups on three Datalog systems.
(summarized by gpt-5-nano on Feb 09 2026)
- Paper ID
- 6283
- Venue
- SIGMOD
- Year
- 2022
- Pagerank
- 4.7531793e-05
- Overall Rank
- 7,338 | 49.01%
- DOI
-
10.1145/3514221.3517827
Incoming Non-self Citations Over Time
Incoming Citations (Sorted by Pagerank)
Showing 7 of 7 citing papers.
Outgoing Citations (Sorted by Pagerank)
Showing 19 of 19 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.00099936325 |
| 31 |
Provenance Semirings |
2007 |
PODS |
0.00078516827 |
| 82 |
Answering Queries Using Views (Extended Abstract) |
1995 |
PODS |
0.00054430106 |
| 728 |
Optimizing Queries Using Materialized Views: A Practical, Scalable Solution |
2001 |
SIGMOD |
0.00017459654 |
| 1,056 |
Cosette: An Automated Prover for SQL |
2017 |
CIDR |
0.00014391317 |
| 1,423 |
Magic is Relevant |
1990 |
SIGMOD |
0.00012047765 |
| 2,398 |
Physical Data Independence, Constraints, and Optimization with Universal Plans |
1999 |
VLDB |
8.8871067e-05 |
| 2,912 |
Convergence of Datalog over (Pre-) Semirings |
2022 |
PODS |
7.9261665e-05 |
| 2,922 |
RaSQL: Greater Power and Performance for Big Data Analytics with Recursive-aggregate-SQL on Spark |
2019 |
SIGMOD |
7.897179e-05 |
| 3,207 |
Big Data Analytics with Datalog Queries on Spark |
2016 |
SIGMOD |
7.3847098e-05 |
| 3,452 |
Minimum and Maximum Predicates in Logic Programming |
1991 |
PODS |
7.0792604e-05 |
| 4,198 |
Implementation of Magic-sets in a Relational Database System |
1994 |
SIGMOD |
6.361961e-05 |
| 4,650 |
A Chase Too Far? |
2000 |
SIGMOD |
6.0169723e-05 |
| 4,694 |
Asynchronous and Fault-Tolerant Recursive Datalog Evaluation in Shared-Nothing Engines |
2015 |
VLDB |
5.985448e-05 |
| 5,497 |
SPORES: Sum-Product Optimization via Relational Equality Saturation for Large Scale Linear Algebra |
2020 |
VLDB |
5.4741034e-05 |
| 5,629 |
Datalog and Emerging Applications: An Interactive Tutorial |
2011 |
SIGMOD |
5.4018902e-05 |
| 5,716 |
Datalog Unchained |
2021 |
PODS |
5.3569788e-05 |
| 6,276 |
Scaling-Up In-Memory Datalog Processing: Observations and Techniques |
2019 |
VLDB |
5.1265189e-05 |
| 6,736 |
Data Migration using Datalog Program Synthesis |
2020 |
VLDB |
4.9417961e-05 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 2,887 |
Semantic Query Optimization in Datalog Programs (Extended Abstract) |
1995 |
PODS |
7.9640219e-05 |
| 6,550 |
Rule-Based Translation of Relational Queries into Iterative Programs |
1986 |
SIGMOD |
5.0113524e-05 |
| 5,267 |
On the Optimization of Recursive Relational Queries: Application to Graph Queries |
2020 |
SIGMOD |
5.5930569e-05 |
| 6,412 |
Optimizing Existential Datalog Queries |
1988 |
PODS |
5.0668361e-05 |
| 1,552 |
Evaluation Of Database Recursive Logic Programs As Recurrent Function Series |
1986 |
SIGMOD |
0.00011393892 |
| 6,234 |
Inherent Complexity of Recursive Queries (Extended Abstract) |
1999 |
PODS |
5.1387584e-05 |
| 12,931 |
Semigroup techniques in recursive query optimization |
1990 |
PODS |
4.1905499e-05 |
| 11,056 |
Efficient Enumeration of Recursive Plans in Transformation-based Query Optimizers |
2024 |
VLDB |
4.1905499e-05 |
| 9,813 |
Optimizing Nested Recursive Queries |
2024 |
SIGMOD |
4.2742278e-05 |
| 12,914 |
Structural Query Optimization — A Uniform Framework For Semantic Query Optimization In Deductive Databases |
1991 |
PODS |
4.1905499e-05 |