DROPS

Document

DOI: 10.4230/LIPIcs.ECOOP.2026.12

Language-Integrated Recursive Queries

Authors: Anna Herlihy, Amir Shaikhha, Anastasia Ailamaki, and Martin Odersky

Published in: LIPIcs, Volume 372, 40th European Conference on Object-Oriented Programming (ECOOP 2026)

Abstract

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.

Cite as

Anna Herlihy, Amir Shaikhha, Anastasia Ailamaki, and Martin Odersky. Language-Integrated Recursive Queries. In 40th European Conference on Object-Oriented Programming (ECOOP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 372, pp. 12:1-12:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{herlihy_et_al:LIPIcs.ECOOP.2026.12,
  author =	{Herlihy, Anna and Shaikhha, Amir and Ailamaki, Anastasia and Odersky, Martin},
  title =	{{Language-Integrated Recursive Queries}},
  booktitle =	{40th European Conference on Object-Oriented Programming (ECOOP 2026)},
  pages =	{12:1--12:30},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-423-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{372},
  editor =	{Krebbers, Robbert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2026.12},
  URN =		{urn:nbn:de:0030-drops-261086},
  doi =		{10.4230/LIPIcs.ECOOP.2026.12},
  annote =	{Keywords: Language-integrated query, embedded DSL, SQL, Scala, fixpoint, Datalog}
}

Document

Artifact

DOI: 10.4230/DARTS.12.1.9

Language-Integrated Recursive Queries (Artifact)

Authors: Anna Herlihy, Amir Shaikhha, Anastasia Ailamaki, and Martin Odersky

Published in: DARTS, Volume 12, Issue 1, Special Issue of the 40th European Conference on Object-Oriented Programming (ECOOP 2026)

Abstract

This artifact accompanies the paper "Language-Integrated Recursive Queries," which introduces λ_RQL, a calculus that derives properties of embedded recursive queries from the host-language type system, and TyQL, its Scala 3 implementation. The artifact provides Docker image that runs the 16-query Recursive Query Benchmark (RQB) via JMH and produces CSV files containing the benchmark results.

Cite as

Anna Herlihy, Amir Shaikhha, Anastasia Ailamaki, and Martin Odersky. Language-Integrated Recursive Queries (Artifact). In Special Issue of the 40th European Conference on Object-Oriented Programming (ECOOP 2026). Dagstuhl Artifacts Series (DARTS), Volume 12, Issue 1, pp. 9:1-9:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@Article{herlihy_et_al:DARTS.12.1.9,
  author =	{Herlihy, Anna and Shaikhha, Amir and Ailamaki, Anastasia and Odersky, Martin},
  title =	{{Language-Integrated Recursive Queries (Artifact)}},
  pages =	{9:1--9:6},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2026},
  volume =	{12},
  number =	{1},
  editor =	{Herlihy, Anna and Shaikhha, Amir and Ailamaki, Anastasia and Odersky, Martin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DARTS.12.1.9},
  URN =		{urn:nbn:de:0030-drops-261463},
  doi =		{10.4230/DARTS.12.1.9},
  annote =	{Keywords: Language-Integrated Query, Embedded DSL, SQL, Scala, Fixpoint, Datalog}
}

Search Results

Documents authored by Herlihy, Anna

Language-Integrated Recursive Queries

Abstract

Cite as

Language-Integrated Recursive Queries (Artifact)

Abstract

Cite as

Thanks for your feedback!

Could not send message