Database Research Group

WSI – Database Systems Research Group

A Ferry-Based Query Backend for the Links Programming Language


This thesis describes the implementation of a Ferry-based query backend for the Links programming language. In Links, queries are seamlessly embedded into the language: Queries formulated in a subset of the language are translated into single SQL queries. Links uses static checks to ensure that a type-correct query expression can be translated into an equivalent SQL query and allows abstraction over parts of a query. The queryizable subset of Links is, however, severely limited in terms of supported functions and the data type (limited to bags of flat records) of queries. The thesis begins with a description of the query facility and criticizes the limited functionality of the queryizable Links subset.

The Ferry framework deals with the compilation of pure, declarative languages based on list comprehensions into SQL queries. It provides features that Links queries are lacking: query results involving nested lists and computed by a small, statically bounded number of SQL queries, ordered lists semantics and a larger number of supported functions. The thesis first reviews the compilation technique of the FERRY framework and adapts it to the specifics of Links. The queryizable subset of Links is higher-order and allows to treat functions as first-class values. To keep this property in the new query backend, the thesis extends the Ferry framework to deal with first-class functions. To make a larger part of a functional programmer’s toolset available in queries, the framework is also extended to handle variants.

In a second step, the thesis describes the architecture of a query backend that embeds this algebraic compilation into the L INKS compiler. This involves changes to the typing mechanisms that statically check LINKS expressions for queryizability and query-specific optimizations. The benefits of the new query backend are demonstrated with the help of a number of example queries. For simple queries, compact and idiomatic SQL code is generated. For more complex queries, the relocation of computations to a database leads to a substantial performce gain.

In summary, the new backend considerably extends the queryizable subset of Links and makes more database functionality available and at the same time keeps the safe, statically checked and compositional integration of queries.


Diplomarbeit (PDF)

Assigned to: Alexander Ulrich