Efficient Evaluation of Aggregates on Bulk Types

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.