|
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, |
