Recursive Computation Over Relational Data

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.

Publications

Another Way to Implement Complex Computations: Functional-Style SQL UDF

Christian Duta

Proceedings of the Workshop on Human-In-the-Loop Data Analytics (HILDA 2022), collocated with SIGMOD 2022, Philadelphia, PA, USA, June 2022.

Functional Programming on Top of SQL Engines

Tobias Burghardt • Denis HirnTorsten Grust

Proceedings of the 24th International Symposium on Practical Aspects of Declarative Languages (PADL 2022), Philadelphia, PA, USA, January 2022. https://doi.org/10.1007/978-3-030-94479-7_5.

Functional-Style SQL UDFs With a Capital 'F'

Torsten GrustChristian Duta

Proceedings of the 39th ACM SIGMOD Int’l Conference on Management of Data (SIGMOD 2020), Portland, Oregon, USA, June 2020. Winner of the ACM SIGMOD 2021 Reproducibility Award.