The Magic of Duplicates and Aggregates

Abstract

We present a formal treatment of multisets (that arise when duplicates are not eliminated) and aggregate operators for deductive and relational databases. We define the semantics rigorously and extend the magic-sets technique to programs containing multisets and aggregates. The work presented here is an important step in demonstrating the applicability of the magic-sets technique for optimizing queries in commercial query languages such as SQL.