Efficient Evaluation of Aggregates on Bulk Types

Sophie Cluet, Guido Moerkotte

           A new method for efficiently evaluating queries with aggregate
           functions is presented. More specifically, we introduce a
           class of aggregate queries where traditional query evaluation
           strategies in general require $O(n^2)$ time and space in the
           size of the (at most two) input relations. For this class
           of aggregate queries our approach needs at most $O(n\log n)$
           time and linear space.  Further, our approach deals not only
           with relations but with general bulk types like sets, bags,
           and lists.