Search Results

Documents authored by Odersky, Martin

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/LIPIcs.FSTTCS.2009.2338
Fighting bit Rot with Types (Experience Report: Scala Collections)

Authors: Martin Odersky and Adriaan Moors

Published in: LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)

Abstract
We report on our experiences in redesigning Scala's collection libraries, focussing on the role that type systems play in keeping software architectures coherent over time. Type systems can make software architecture more explicit but, if they are too weak, can also cause code duplication. We show that code duplication can be avoided using two of Scala's type constructions: higher-kinded types and implicit parameters and conversions.
Cite as

Martin Odersky and Adriaan Moors. Fighting bit Rot with Types (Experience Report: Scala Collections). In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 427-451, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{odersky_et_al:LIPIcs.FSTTCS.2009.2338,
  author =	{Odersky, Martin and Moors, Adriaan},
  title =	{{Fighting bit Rot with Types (Experience Report: Scala Collections)}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{427--451},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-13-2},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{4},
  editor =	{Kannan, Ravi and Narayan Kumar, K.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2338},
  URN =		{urn:nbn:de:0030-drops-23386},
  doi =		{10.4230/LIPIcs.FSTTCS.2009.2338},
  annote =	{Keywords: Programming languages, scala, avoiding code duplication, higher-order kinds, type systems, polymorphism, collections library}
}
Document
DOI: 10.4230/DagSemRep.373
Domain-Specific Program Generation (Dagstuhl Seminar 03131)

Authors: Don Batory, Charles Consel, Christian Lengauer, and Martin Odersky

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Don Batory, Charles Consel, Christian Lengauer, and Martin Odersky. Domain-Specific Program Generation (Dagstuhl Seminar 03131). Dagstuhl Seminar Report 373, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2003)

Copy BibTex To Clipboard

@TechReport{batory_et_al:DagSemRep.373,
  author =	{Batory, Don and Consel, Charles and Lengauer, Christian and Odersky, Martin},
  title =	{{Domain-Specific Program Generation (Dagstuhl Seminar 03131)}},
  pages =	{1--8},
  ISSN =	{1619-0203},
  year =	{2003},
  type = 	{Dagstuhl Seminar Report},
  number =	{373},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.373},
  URN =		{urn:nbn:de:0030-drops-152531},
  doi =		{10.4230/DagSemRep.373},
}
Document
DOI: 10.4230/DagSemRep.164
High-Level Concurrent Languages (Dagstuhl Seminar 97041)

Authors: Kohei Honda, Martin Odersky, Benjamin Pierce, Gert Smolla, and Philip Wadler

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Kohei Honda, Martin Odersky, Benjamin Pierce, Gert Smolla, and Philip Wadler. High-Level Concurrent Languages (Dagstuhl Seminar 97041). Dagstuhl Seminar Report 164, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1997)

Copy BibTex To Clipboard

@TechReport{honda_et_al:DagSemRep.164,
  author =	{Honda, Kohei and Odersky, Martin and Pierce, Benjamin and Smolla, Gert and Wadler, Philip},
  title =	{{High-Level Concurrent Languages (Dagstuhl Seminar 97041)}},
  pages =	{1--20},
  ISSN =	{1619-0203},
  year =	{1997},
  type = 	{Dagstuhl Seminar Report},
  number =	{164},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.164},
  URN =		{urn:nbn:de:0030-drops-150514},
  doi =		{10.4230/DagSemRep.164},
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact