On the equivalence and rewriting of aggregate queries (Q1889881)

The paper deals with the problem of aggregate queries involving complex statistical functions. A first-order language with real polynomial arithmetic and aggregate operators (count, iterated sum and multiply) is introduced. The authors show that there is an effective quantitative elimination for formulae with aggregation. The main contribution is the definition of new efficient syntactic criteria to determine whether two aggregate queries are equivalent or not. A new equivalence relation among conjunctive queries is defined, called isomorphism modulo product. This concept is then generalized, and the equivalence with comparison is defined, the cross isomorphic linear expansions are examined, and it is shown that equivalence of some ratio queries reduces to it. Finally, it is shown how these results can be used to solve the view usability problem. The authors consider the problem of the existence of a complete rewriting of a query using only views, and prove that the problem of complete rewriting for bag queries and views is NP-complete. A non-deterministic algorithm is designed, which produces the possible rewriting, and it is shown to be sound and complete with respect to the proposed rewritings. Finally, the authors show another application of the isomorphism modulo product and introduce the rewriting modulo product.