Ryan Wisnesky (Harvard University)

A Monadic Query Language

Jeudi 6 octobre 2011, 11h salle 1D23

Abstract: Recent interest in general-purpose "cloud-scale" or "internet-scale" data processing has led to the development of a new class of declarative "cloud-query languages" such as MapReduce, DryadLINQ, and CloudHaskell which go beyond the traditional relational/SQL model in expressive power. Although these languages vary in the kinds of queries and collections they support, it is well-known that large fragments of these languages can be formalized in a uniform way using monads (to model collections), comprehensions (to model queries), setoids over polynomial datatypes (to model data), and folds (to model computation). Despite the theoretical attractiveness of this approach, significant open problems have hindered the development of a standard model of cloud-query languages.

In this talk I describe MQL, a new query language and compiler designed to be just such a standard model. MQL's principled foundation gives it capabilities beyond those found in current cloud-query languages, such as the ability to re-write queries into a normal form using data integrity constraints, fuse folds using monad-specific information, and emit verification conditions at compile time. At a theoretical level, MQL embeds Tannen's Calculus of Collections and Aggregates into a system of higher-rank, qualified types and provides an equational theory for comprehensions over idempotent monad algebras suitable for further study of topics at the intersection of relational database theory and programming language theory.