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}
}

Document

DOI: 10.4230/DagRep.1.8.1

Information Management in the Cloud (Dagstuhl Seminar 11321)

Authors: Anastasia Ailamaki, Michael J. Carey, Donald Kossman, Steve Loughran, and Volker Markl

Published in: Dagstuhl Reports, Volume 1, Issue 8 (2011)

Abstract

Cloud computing is emerging as a new paradigm for highly scalable, fault-tolerant, and adaptable computing on large clusters of off-the-shelf computers. Cloud architectures strive to massively parallelize complex processing tasks through a computational model motivated by functional programming. They provide highly available storage and compute capacity through distribution and redundancy. Most importantly, Cloud architectures adapt to changing requirements by dynamically provisioning new (virtualized) compute or storage nodes. Economies of scale enable cloud providers to provide compute and storage powers to a multitude of users. On the infrastructure side, such a model has been pioneered by Amazon with EC2, whereas software as a service on cloud infrastructures with multi-tenancy has been pioneered by Salesforce.com. The Dagstuhl Seminar 11321 ``Information Management in the Cloud'' brought together a diverse set of researchers and practitioners with a broad range of expertise. The purpose of this seminar was to consider and to discuss causes, opportunities, and solutions for technologies, and architectures that enable cloud information management. The scope ranged from web-scale log file analysis using cluster computing techniques to dynamic provisioning of resources in data centers, covering topics from the areas of analytical and transactional processing, parallelization of large scale data and compute intensive operations as well as implementation techniques for fault tolerance.

Cite as

Anastasia Ailamaki, Michael J. Carey, Donald Kossman, Steve Loughran, and Volker Markl. Information Management in the Cloud (Dagstuhl Seminar 11321). In Dagstuhl Reports, Volume 1, Issue 8, pp. 1-28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@Article{ailamaki_et_al:DagRep.1.8.1,
  author =	{Ailamaki, Anastasia and Carey, Michael J. and Kossman, Donald and Loughran, Steve and Markl, Volker},
  title =	{{Information Management in the Cloud (Dagstuhl Seminar 11321)}},
  pages =	{1--28},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2011},
  volume =	{1},
  number =	{8},
  editor =	{Ailamaki, Anastasia and Carey, Michael J. and Kossman, Donald and Loughran, Steve and Markl, Volker},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.1.8.1},
  URN =		{urn:nbn:de:0030-drops-33109},
  doi =		{10.4230/DagRep.1.8.1},
  annote =	{Keywords: Cloud Technologies, Information Management, Distributed Systems, Parallel Databases}
}

Search Results

Documents authored by Ailamaki, Anastasia

Language-Integrated Recursive Queries

Abstract

Cite as

Language-Integrated Recursive Queries (Artifact)

Abstract

Cite as

Information Management in the Cloud (Dagstuhl Seminar 11321)

Abstract

Cite as

Thanks for your feedback!

Could not send message