Efficient Incremental Evaluation of Queries with Aggregation

Abstract

We present a technique for efficiently evaluating queries on programs with monotonic aggregation, a class of programs defined by Ross and Sagiv. Our technique consists of the following components: incremental computation of aggregate functions, incremental fixpoint evaluation of monotonic programs and Magic Sets transformation of monotonic programs. We also present a formalization of the notion of incremental computation of aggregate functions on a multiset, and upper and lower bounds for incremental computation of a variety of aggregate functions. We describe a proof-theoretic reformulation of the monotonic semantics in terms of computations, following the approach of Beeri et al.; this reformulation greatly simplifies the task of proving the correctness of our optimizations. 1 Introduction There has been a lot of recent work in the literature on defining the semantics of complex database queries involving aggregate functions. Early work assumed some form of stratification of predic...