Metraipolis › archive › dc_d738f887490a
Logos: Certified Order-Sensitive SQL Rewrites with Mechanized Semantics and LLM Guidance — arXiv:2608.15709
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.15709
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-18T23:35:28.525Z
- SHA-256 of the archived text
51fa62e444cc29496c42dbf2ae0eaf9f320888a64eb313038b894559e2d3d405- Stable URL of this page
https://metraipolis.com/documento/dc_d738f887490a
How to cite
Logos: Certified Order-Sensitive SQL Rewrites with Mechanized Semantics and LLM Guidance — arXiv:2608.15709 — arXiv (en), https://arxiv.org/abs/2608.15709 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d738f887490a (Metraipolis archive dc_d738f887490a, sha256 51fa62e444cc29496c42dbf2ae0eaf9f320888a64eb313038b894559e2d3d405)
BibTeX
@misc{dcd738f887490a,
title = {Logos: Certified Order-Sensitive SQL Rewrites with Mechanized Semantics and LLM Guidance — arXiv:2608.15709},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.15709},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d738f887490a; sha256 51fa62e444cc29496c42dbf2ae0eaf9f320888a64eb313038b894559e2d3d405},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.15709. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
SQL rewrite verification must account for duplicate rows, observable row order, and typed value semantics. Existing verifiers have yet to combine proofs over database instances of arbitrary finite cardinality with an ordered-list semantics for nested, tie-sensitive top-k. Unbounded systems reason primarily over bags or handle ordering through syntax-directed restrictions, whereas bounded systems either support only restricted top-k forms or impose a deterministic ordering rather than retain all legal tie-induced outcomes. Support for typed expression and aggregate semantics, observable runtime errors, and integrity constraints also remains partial. In Rocq, we mechanize a compositional logical semantics for a typed SQL core with order-sensitive operators, capturing all possible ordered lists and observable SQL failures in the supported fragment. To our knowledge, this is the first mechanized SQL semantics to combine nested, tie-sensitive top-k with a closure-based lifting from bag equivalence to ordered-list equivalence, enabling sound reuse of bag-theoretic reasoning while preserving compositionality across order-sensitive and correlated contexts. The formalization further provides executable semantics for PostgreSQL-oriented scalar and aggregate evaluation and an explicit account of integrity constraints. Building on this semantics, we present Logos, an LLM-guided Rocq verifier for unbounded SQL rewrite equivalence. Its agent uses a verified SQL-specific lemma library to construct query-specific Rocq proofs. Our evaluation covers 389 query pairs from Apache Calcite optimizer tests, TPC-H and TPC-DS rewrites, and WeTune's real-application workloads. Logos solves 86.9% of them, compared with 64.0% for SQLSolver, the strongest baseline. Tema degli esploratori: statistica e scienza dei dati (retro-catalogo arXiv: annunci del 2026-08-18 in cs.DB). Categorie arXiv: Databases (cs.DB). Pagina del lavoro: https://arxiv.org/abs/2608.15709 — 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-18T23:02:17.572Z dalla pagina https://arxiv.org/catchup/cs.DB/2026-08-18?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).