Viability of Recursive SQL Functions

DSpace Repository

Show simple item record

dc.contributor.advisor Grust, Torsten (Prof. Dr.)
dc.contributor.author Duta, Christian
dc.date.accessioned 2023-04-18T08:17:18Z
dc.date.available 2023-04-18T08:17:18Z
dc.date.issued 2022-04-18
dc.identifier.uri http://hdl.handle.net/10900/139262
dc.identifier.uri http://nbn-resolving.de/urn:nbn:de:bsz:21-dspace-1392626 de_DE
dc.identifier.uri http://dx.doi.org/10.15496/publikation-80609
dc.description.abstract The inclusion of recursive common table expressions (recursive CTEs) in the SQL:1999 standard enabled the developer to implement complex in-database computations, e.g., graph algorithms and others. However, their awkward syntax and rigid fixed- point evaluation method requires highly-specialized expert knowledge in SQL to implement complex computations. This sets the bar quite high for developers to consider implementing such queries. We propose an alternative way to implement complex in-database computations, which we call functional-style SQL UDFs. UDFs implemented in functional-style allow recursive self-invocation inside their own function body. In this publication, we measure the viability of functional-style UDFs from two angles: readability and runtime performance. To measure the readability of functional-style UDFs, we conducted a user study in 2020. We presented the participants with tasks from the following topics: - Choose the correct implementations of the algorithms for the fibonacci numbers and greatest common divisor formulated in functional-style and recursive CTE. - Describe and evaluate two unknown UDFs. One is formulated in functional-style and the other as a recursive CTE. - Implement the 0-1 Knapsack algorithm based on its textbook style formulation in either functional-style or recursive CTE formulation. Each participant is then graded based on the score and time needed. In Chapter 2, we present the user study results and compare how well the participants handle these functional-style UDFs compared to recursive CTEs. We discuss if functional- style UDFs can help improve readability for such complex queries. Besides readability, developers are also interested in the runtime performance of functional-style UDFs. We find that some RDBMSs such as PostgreSQL, Oracle, Microsoft SQL Server, MySQL and SQLite have trouble handling functional-style UDFs as-is. Performance issues, strict recursion depth limitations, or even outright denying evaluation of functional-style UDFs are the main issues we encountered. In Chapter 4, we describe a SQL-to-SQL compiler which accepts functional-style UDFs, as defined in Chapter 3. The compiler produces standard SQL:1999 recursive CTEs, which replaces the function body of functional-style UDFs so that it no longer exhibits recursive self-invocations. The compiled function body evaluates in a two-phased fashion that (1) constructs a call graph top-down and then (2) traverses the call graph bottom-up until its root node is reached and the result is returned. Indeed, the compiler does not rely on intrusive changes to the underlying database engine. Furthermore, this two-phased approach enables optimizations (call sharing, ref- erence counting, linear- and tail-recursion detection, memoization, batching) through small tweaks and improvements to the compiler, which we describe in Chapter 5. We also measure the execution times of various algorithms before and after compilation and discuss the results. We find the runtime performance a developer experiences when compiling functional-style UDFs can improve which is supported by the experiments. en
dc.language.iso en de_DE
dc.publisher Universität Tübingen de_DE
dc.rights ubt-podok de_DE
dc.rights.uri http://tobias-lib.uni-tuebingen.de/doku/lic_mit_pod.php?la=de de_DE
dc.subject.classification Compiler , SQL , Rekursion , Relationale Datenbank , Funktionale Programmierung , Program Slicing , Lineare Rekursion de_DE
dc.subject.ddc 004 de_DE
dc.subject.other Endrekursion de_DE
dc.subject.other Tail Recursion en
dc.title Viability of Recursive SQL Functions en
dc.type PhDThesis de_DE
dcterms.dateAccepted 2023-04-05
utue.publikation.fachbereich Informatik de_DE
utue.publikation.fakultaet 7 Mathematisch-Naturwissenschaftliche Fakultät de_DE
utue.publikation.noppn yes de_DE

Dateien:

This item appears in the following Collection(s)

Show simple item record