List comprehensions are a widely used programming construct, in languages such as Haskell and Python and in technologies such as Microsoft's LINQ. They generalize from lists to arbitrary monads, yielding a convenient notation for expressing database queries. The monad structure both explains and provides a reasonable execution plan for the selection and projection operations of relational algebra, but does neither for the join operation. We show how some generalisations of the comprehension notation - which accommodate heterogeneous collections, grouping, and merging - can be used to provide an explanation and a reasonable implementation for relational joins.
Jeremy Gibbons is Professor of Computing at the University of Oxford, where he is director of the part-time professional master's programme in software engineering. His research interests are in patterns in functional programming, in reasoning about programs, in generic programming, and in embedded domain-specific languages.
This talk is organized by the Business Informatics Group at the Faculty of Informatics, the Austrian Computer Society and the Center for Computer Science.