2026-07-21T01:00:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26108 2026-06-25T08:57:48Z ddc:004 open_access

Language-Integrated Recursive Queries Herlihy, Anna Shaikhha, Amir Ailamaki, Anastasia Odersky, Martin Language-integrated query embedded DSL SQL Scala fixpoint Datalog Performance-critical applications, including large-scale program analyses, graph analyses, and distributed system analyses, rely on fixed-point computations. The introduction of recursion using the WITH RECURSIVE keyword in SQL:1999 extended the ability of relational database systems to handle fixed-point computations, unlocking significant performance advantages by allowing computation to move closer to the data. Yet, with recursion, SQL becomes a Turing-complete programming language with new correctness and safety risks. Full SQL lacks a fixed semantics, as the SQL specification is written in natural language with ambiguities that database vendors resolve in divergent ways. As a result, reasoning about the correctness of recursive SQL programs must rely on isolated, composable properties of queries rather than wrestling a unified formal model out of a language with notoriously inconsistent implementations across systems. To address these challenges, we propose a calculus, λ_RQL, that derives properties from embedded recursive queries using the host-language type system and, depending on the database backend, rejects queries that may lead to the three classes of recursive query errors: runtime database exceptions, incorrect results, and nontermination. Queries that respect all properties are guaranteed to find the minimal fixed point in a finite number of steps. We introduce TyQL, a practical implementation in Scala for safe, recursive language-integrated query. TyQL uses modern type system features of Scala 3, namely Named-Tuples and type-level pattern matching, to ensure query portability and safety. TyQL shows no performance penalty compared to SQL queries expressed as embedded strings while enabling a three-order-of-magnitude speedup over non-recursive SQL. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anna Herlihy and Amir Shaikhha and Anastasia Ailamaki and Martin Odersky 2026 Is Part Of LIPIcs, Volume 372, 40th European Conference on Object-Oriented Programming (ECOOP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ECOOP.2026.12 urn:nbn:de:0030-drops-261086 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2026.12 eng https://creativecommons.org/licenses/by/4.0/legalcode