Anna Herlihy

We introduce Raqlet, a source-to-source compilation framework that addresses the fragmentation of recursive querying engines spanning relational (recursive SQL), graph (Cypher, GQL), and deductive (Datalog) systems. Recent standards such as SQL:2023's SQL/PGQ and the GQL standard provide a common foundation for querying graph data within relational and graph databases; however, real-world support remains inconsistent across systems. Raqlet bridges this gap by translating recursive queries across paradigms through leveraging intermediate representations (IRs) grounded in well-defined semantics; it translates Cypher or SQL/PGQ to PGIR (inspired by Cypher), then into DLIR (inspired by Datalog), and finally to SQIR (inspired by recursive SQL). Raqlet provides a shared semantic basis that can serve as a golden reference implementation for language standards, while supporting static analysis and transformations (e.g., magic-set transformation) for performance tuning. Our vision is to make Raqlet a robust platform that enables rapid cross-paradigm prototyping, portable recursive queries, and formal reasoning about recursion even when targeting diverse query execution engines.

Implementing concurrent data structures is challenging and requires a deep understanding of concurrency concepts and careful design to ensure correctness, performance, and scalability. Further, composing operations on two or more concurrent data structures often requires a synchronization wrapper to ensure the operations are applied together atomically, resulting in serialization and, thereby, giving up the performance benefit of the individual data structures. DBMS provides generalized concurrency control (CC) and is a good fit for implementing concurrent data structures. However, DBMSs are over-generalized for this use case, which fails to match the performance of specialized implementations. This paper makes the case for the Declarative Concurrent Data Structures (DCDS) framework for automatically generating concurrent data structures from a serial specification. In DCDS, users declare the attributes and methods needed for their desired data structure through an embedded DSL at design time. DCDS automatically injects CC at build-time, generating a concurrent intermediate representation (IR) compiled into machine code. A declarative interface for designing data structure enables efficient composability through co-optimizing component structures; optimizations are applied to both the composed serial specification and the generated concurrent IR. We realize the DCDS framework in our prototype system Rosti and experimentally show that data structures declared in Rosti can be efficiently composed by co-optimizing their logical functionality and the generated CC protocol. Our evaluation shows that composing a map and a list to create an LRU container can benefit up to 2X performance scalability in Rosti compared to an open-source library. We demonstrate the applicability of DCDS as an in-process OLTP by comparing it with in-memory DBMS, Proteus, and showing up to 2X performance gains.