Metraipolis › archive › dc_0f640ee8b11e
Compiling Linear Datalog to SQL for Program Analysis — arXiv:2609.06301
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.06301
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T15:31:34.501Z
- SHA-256 of the archived text
3befac66af2ff6f514220fe409f253227a2bd70974ed382049fcc83a24f74330- Stable URL of this page
https://metraipolis.com/documento/dc_0f640ee8b11e
How to cite
Compiling Linear Datalog to SQL for Program Analysis — arXiv:2609.06301 — arXiv (en), https://arxiv.org/abs/2609.06301 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_0f640ee8b11e (Metraipolis archive dc_0f640ee8b11e, sha256 3befac66af2ff6f514220fe409f253227a2bd70974ed382049fcc83a24f74330)
BibTeX
@misc{dc0f640ee8b11e,
title = {Compiling Linear Datalog to SQL for Program Analysis — arXiv:2609.06301},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.06301},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_0f640ee8b11e; sha256 3befac66af2ff6f514220fe409f253227a2bd70974ed382049fcc83a24f74330},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.06301. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Datalog is a declarative query language that has proven highly effective for expressing static program analyses. Although Datalog has deep roots in database theory, most recent advances have largely emerged from the programming languages and compiler communities, with systems such as Soufflé. In contrast, modern relational engines have made significant progress in optimizing recursive SQL. This paper revisits the connection between Datalog and relational databases, advocating recursive SQL as a backend for Datalog evaluation. We present a compilation framework that translates Datalog programs, particularly those in the Linear Datalog fragment, into equivalent recursive SQL queries. To bridge the gap between Datalog and SQL, the compiler routes every program through an intermediate language called Midlog. The compiler additionally recovers functional dependencies from the program and exposes them as schema keys, unlocking the engine's standard query optimizations. This approach enables existing database engines to execute a broad class of program analyses, outperforming the Soufflé engine by up to an order of magnitude on the Umbra backend. Umbra achieves a geometric-mean speedup of 5.46$\times$ at 8 threads, whereas DuckDB is competitive with Soufflé single-threaded and is slower at 8 threads (geometric-mean speedup of 0.68$\times$). Furthermore, the generated SQL is portable; it runs on seven database systems without any engine modification. Our results highlight what the relational engines require to fully support Datalog for large-scale program analysis. Tema degli esploratori: statistica e scienza dei dati (retro-catalogo arXiv: annunci del 2026-09-09 in cs.DB). Categorie arXiv: Databases (cs.DB) ; Programming Languages (cs.PL). Pagina del lavoro: https://arxiv.org/abs/2609.06301 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-16T15:12:35.378Z dalla pagina https://arxiv.org/catchup/cs.DB/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).