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
- 6282
- Venue
- SIGMOD
- Year
- 2022
- Pagerank
- 4.7576316e-05
- Overall Rank
- 7,342 | 48.93%
- 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.0010066783 |
| 31 |
Provenance Semirings |
2007 |
PODS |
0.0007857786 |
| 82 |
Answering Queries Using Views (Extended Abstract) |
1995 |
PODS |
0.00054402763 |
| 731 |
Optimizing Queries Using Materialized Views: A Practical, Scalable Solution |
2001 |
SIGMOD |
0.00017468889 |
| 1,057 |
Cosette: An Automated Prover for SQL |
2017 |
CIDR |
0.0001439886 |
| 1,423 |
Magic is Relevant |
1990 |
SIGMOD |
0.00012054867 |
| 2,401 |
Physical Data Independence, Constraints, and Optimization with Universal Plans |
1999 |
VLDB |
8.8954126e-05 |
| 2,907 |
Convergence of Datalog over (Pre-) Semirings |
2022 |
PODS |
7.933806e-05 |
| 2,919 |
RaSQL: Greater Power and Performance for Big Data Analytics with Recursive-aggregate-SQL on Spark |
2019 |
SIGMOD |
7.9047279e-05 |
| 3,200 |
Big Data Analytics with Datalog Queries on Spark |
2016 |
SIGMOD |
7.3912411e-05 |
| 3,446 |
Minimum and Maximum Predicates in Logic Programming |
1991 |
PODS |
7.0861064e-05 |
| 4,199 |
Implementation of Magic-sets in a Relational Database System |
1994 |
SIGMOD |
6.3662839e-05 |
| 4,654 |
A Chase Too Far? |
2000 |
SIGMOD |
6.022356e-05 |
| 4,696 |
Asynchronous and Fault-Tolerant Recursive Datalog Evaluation in Shared-Nothing Engines |
2015 |
VLDB |
5.9911301e-05 |
| 5,487 |
SPORES: Sum-Product Optimization via Relational Equality Saturation for Large Scale Linear Algebra |
2020 |
VLDB |
5.4791501e-05 |
| 5,620 |
Datalog and Emerging Applications: An Interactive Tutorial |
2011 |
SIGMOD |
5.407079e-05 |
| 5,705 |
Datalog Unchained |
2021 |
PODS |
5.3621239e-05 |
| 6,276 |
Scaling-Up In-Memory Datalog Processing: Observations and Techniques |
2019 |
VLDB |
5.1314426e-05 |
| 6,758 |
Data Migration using Datalog Program Synthesis |
2020 |
VLDB |
4.937199e-05 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 2,877 |
Semantic Query Optimization in Datalog Programs (Extended Abstract) |
1995 |
PODS |
7.9715251e-05 |
| 6,554 |
Rule-Based Translation of Relational Queries into Iterative Programs |
1986 |
SIGMOD |
5.0155947e-05 |
| 5,259 |
On the Optimization of Recursive Relational Queries: Application to Graph Queries |
2020 |
SIGMOD |
5.5984356e-05 |
| 6,417 |
Optimizing Existential Datalog Queries |
1988 |
PODS |
5.0717071e-05 |
| 1,529 |
Evaluation Of Database Recursive Logic Programs As Recurrent Function Series |
1986 |
SIGMOD |
0.00011496686 |
| 6,236 |
Inherent Complexity of Recursive Queries (Extended Abstract) |
1999 |
PODS |
5.1436959e-05 |
| 12,921 |
Semigroup techniques in recursive query optimization |
1990 |
PODS |
4.1945683e-05 |
| 11,053 |
Efficient Enumeration of Recursive Plans in Transformation-based Query Optimizers |
2024 |
VLDB |
4.1945683e-05 |
| 9,814 |
Optimizing Nested Recursive Queries |
2024 |
SIGMOD |
4.2783272e-05 |
| 12,904 |
Structural Query Optimization — A Uniform Framework For Semantic Query Optimization In Deductive Databases |
1991 |
PODS |
4.1945683e-05 |