Lehrstuhl für Datenbanksysteme (Database Systems Chair)

News

• 2012-01-09: The video of the Bringing Back Monad Comprehensions talk given at Haskell Symposium 2011 in Tokyo is now available.
• 2011-11-18: DSH is available for download on Hackage!
• 2011-06-01: Our Haskell Symposium 2011 paper entitled as Bringing Back Monad Comprehensions got accepted for publication.
• 2011-04-18: Our work on Ferry wins the Peter Landin Prize 2011 for the best paper at IFL 2010. Thank you, folks.

DSH — Database-Supported Haskell

Database-Supported Haskell, DSH for short, is a Haskell library for database-supported program execution. Using the DSH library, a relational database management system (RDBMS) can be used as a coprocessor for the Haskell programming language, especially for those program fragments that carry out data-intensive and data-parallel computations. Rather than embedding a relational language into Haskell, DSH turns idiomatic Haskell programs into SQL queries.

We present Habitat, a declarative observational debugger for SQL. Habitat facilitates true language-level (not: plan-level) debugging of, probably flawed, SQL queries that yield unexpected results. Users may mark arbitrary SQL subexpressions—ranging from literals, over fragments of predicates, to entire subquery blocks—to observe whether these evaluate as expected.

From the marked SQL text, Habitat’s algebraic compiler derives a new query whose result represents the values of the desired observations. These observations are generated by the target SQL database host itself. Prior data extraction or extra debugging middleware is not required.

Habitat merges multiple observations into a single (nested) tabular display, letting a user explore the relationship of various observations. Filter predicates furthermore ease the interpretation of large results.

Join graphs in databases

SQL query optimizers strive to produce query plans whose primary components are join graphs—bundles of relations interconnected by join predicates—while a secondary, peripheral plan tail performs further filtering, grouping, and sorting. Plans of this particular type are subject to effective optimization strategies that, taking into account the available indexes and applicable join methods, derive equivalent join trees, ideally with a left-deep profile to enable pipelining. For more than 30 years now, relational query processing infrastructure has been tuned to excel at the evaluation of plans of this shape.

The approach

Based on the loop lifting compilation scheme, we compile XQuery queries into logical algebra plans. Both the compositional language and compilation scheme lead to stacked plans whose shapes differ considerably from the ideal join graph + plan tail. Instead, join operators occur in sections distributed all over the plan. A similar distribution can be observed for the blocking operators δ and ρ (duplicate elimination and row ranking). This is quite unlike the algebraic plans produced by SQL SELECT-FROM-WHERE block compilation.

The omnipresence of blocking operators obstructs join operator movement and planning and leads industrial-strength optimizers, e.g., IBM DB2 UDB V9, to execute the plan in stages that read and then again materialize temporary tables.

Here, we propose a plan rewriting procedure that derives join graphs from the initial plans. The resulting plan may be expressed as a single SELECT-DISTINCT-FROM-WHERE-ORDERBY block to be submitted for execution by an off-the-shelf RDBMS. The database system then evaluates this query over a schema-oblivious tabular encoding of XML documents to compute the encoding of the resulting XML node sequence (which may then be serialized to yield the expected XML text). Alternatively the isolated join graph plans represent the input for ROX: Run-time Optimization of XQueries.