« Hiatus | Main | 'Pleasingly, these qualities are also what are needed scientifically' »

Grust & Schreiber's Ferry: Database Queries in a Sensible Language

Last week we had some really cool guys come visit us from Germany: Torsten Grust and Tom Schreiber of Universität Tübingen. I was aware of Grust's work on functional database query languages from some years ago, but was surprised when he emailed us (the Links team) and let us know about their new work with Ferry [1], essentially a nice, first-order, functional programming language which they compile to bundles of SQL queries.

This overlaps a lot with what I've been doing with compiling Links to SQL. I had recently discovered a way of compiling expressions in a pure, non-recursive, higher-order fragment of Links to single SQL queries, given the condition that the source expression has the same type as an SQL query: a multiset of tuples of base type.

What Torsten and Tom have figured out how to do is to compile expressions of nested data type to a small set of queries having flat type, such that you can easily assemble the nested result from the flat queries. This is something I had thought about how to do and hadn't cracked, so I was very pleased when the Tübingen guys turned up with a way to do it. In fact Jan Van den Bussche had figured out a similar encoding (of nested to flat algebra) in 2001 [2], in a purely theoretical setting and with (unordered) sets as the only container type. Torsten and Tom can actually handle unordered bags and ordered lists, which is another big step forward.

Their work and my work overlap, but we each had things that the other didn't have. They had nested data structures and ordered collections (lists), while my compilation works for a higher-order language, where functions are first-class values. Also I'm working in the setting of an impure language with side-effects; we can statically identify database-compilable expressions, which must be pure, by using a type-and-effect analysis. The two systems seem to fit together very well, and we're looking at integrating them.

Torsten, and Tom, and myself, Phil and Sam had a nice visit together in Edinburgh were we pried into the details. Three cheers for collaborative visits!

[1] "Ferry: Database-Supported Program Execution." Torsten Grust, Manuel Mayr, Jan Rittinger, Tom Schreiber. Proc. 28th ACM SIGMOD Int'l Conference on Management of Data (SIGMOD 2009), June 2009. To appear.
[2] "Simulation of the nested relational algebra by the flat relational algebra, with an application to the complexity of evaluating powerset algebra expressions." Jan Van den Bussche. Theoretical Computer Science, 254(1-2). p. 363-377. 2001.