RECORD

Recursive Computation Over Relational Data

01/01/2024 to 31/12/2026

Move your computation close to the data! This age-old mantra of the database community asserts that we can expect a SQL query engine with immediate access to the data to perform significantly better than an external processor to which we have to ship the data first. The lore holds up if the computation is query-like and primarily involves filtering, data (re-)combination, grouping, or aggregation.

It is much less clear how complex algorithms that rely on arbitrary iterative control flow or recursion can be efficiently evaluated inside the same SQL engines. With the advent of SQL:1999, contemporary database engines started to support forms of recursion. The associated language constructs, however, exhibit syntactic restrictions, are based on semantics that are tough to grasp for regular developers, or exhibit sobering runtime performance that often render iterative or recursive SQL impractical.

Project RECORD explores compilation and implementation techniques that (1) admit the formulation of iterative and recursive algorithms in a readable, concise (even elegant) fashion and (2) use relational database systems as efficient and scalable runtime environments that perform the computation right next to the data. We adopt established techniques originally developed by the (functional) programming language community, then adapt and bend these ideas so that they apply to recursive SQL functions as well as iterative PL/SQL procedures written in an imperative style. Our focus is on non-invasive approaches that do not turn existing database technology on its head: we thus map functions and procedures to the native, plain SQL recursion constructs already built into off-the-shelf database systems. We take the freedom, however, to apply surgical changes to database kernels where we anticipate that the runtime performance or the systems' space usage can benefit.

There is no shortage of data-intensive problem domains whose need for such in-database computation only ever goes up. RECORD will study the core data structures and algorithms of these domains to test-drive its results and to prove that recursive computation over relational data can indeed be practical and efficient.