[PL Seminar] Talk: Fritz Henglein
2009.09.09 |
| Date | Mon Sep 14 |
| Time | 13:15 — 14:15 |
| Location | DI-Ada-018 |
Title: Generic discrimination and lazy productsfor filter-map-product queries
Time and place: 14.9.09, 13:15-14:00 in Ada-018
Speaker: Fritz Henglein, DIKU
Abstract:
We introduce the notion of equivalence discriminator, which par-
titions a list of values according toa user-speci?ed equivalence relation on
keys the values are associated with, while preserving full representation
independence of the keys. We show how discriminators can
be de?ned generically, purely functionally, and efficiently (worst-case
linear time) on top of the basic multiset discrimination
algorithm of Cai and Paige (1995).
Combined with a lazy representation of products and unions, we show
how discriminative joins provide an efficient implementationof
filter-map-product queries, generalizations of the core relational
algebra operations of selection, projection and (equi)join. The
techniques subsume most of the optimization techniques based
on relational algebra equalities, without a query preprocessing phase.
Full source code in the functional programming language
Haskell, extended with Generalized Algebraic
Data Types (GADTS), will be shown. GADTs are used to represent sets
(relations), projections, predicates and a domain-specific language
forequivalence relations in a type-safe manner.
Host: Klaus Ostermann