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

CREATORAnna Herlihy, Amir Shaikhha, Anastasia Ailamaki, Martin Odersky
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE189 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-02443

Browse the full library · About the Tower of Babel