Language-Integrated Recursive Queries
Anna Herlihy, Amir Shaikhha, Anastasia Ailamaki, Martin Odersky · 2025
Read Language-Integrated Recursive Queries by Anna Herlihy, Amir Shaikhha, Anastasia Ailamaki, Martin Odersky (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-02443.txt.
Description
Recursive queries, which chase chains of links until they settle, are powerful but risky in standard database language. Anna Herlihy and co-authors build a safer way to write them inside a programming language in a 2025 paper.
Their system, TyQL, is written in Scala and checks recursive queries as they are composed. It derives math properties of each query on its own and can reject queries that might crash the database, return wrong results, or loop forever. Typed tuples and type-level pattern checks keep queries portable across backends. Speed matched hand-written database strings, and recursive queries ran about a thousand times faster than non-recursive ones. Safety, it turns out, need not cost performance.
Catalog record
| CREATOR | Anna Herlihy, Amir Shaikhha, Anastasia Ailamaki, Martin Odersky |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 189 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-02443