Aggregation and Relevance in Deductive Databases

Abstract

In this paper we present a technique to optimize queries on deductive databases that use aggregate operations such as min, max, and "largest k values." Our approach is based on an extended notion of relevance of facts to queries that takes aggregate operations into account. The approach has two parts: a rewriting part that labels predicates with "aggregate selections," and an evaluation part that makes use of "aggregate selections" to detect that facts are irrelevant and discards them. The rewriting complements standard rewriting algorithms like Magic sets, and the evaluation essentially refines Semi-Naive evaluation. 1 Introduction Recursive queries with aggregation have been considered by several people [BNR + 87, MPR90]. The advantages of a rich language are clear, but unless effective optimization techniques are developed, the performance of specialized systems based on supporting a limited class of queries (for example generalized transitive closure queries) cannot be matched....