On the equivalence and rewriting of aggregate queries
type: Item
instance of: scholarly article
title: On the equivalence and rewriting of aggregate queries
zbMATH Open document ID: 1066.68035
author: Stéphane Grumbach
author: Maurizio Rafanelli
author: Leonardo Tininini
published in: Acta Informatica
publication date: 2004-12-13T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68P15
Mathematics Subject Classification ID: 03B70
zbMATH DE Number: 2121807
zbMATH Keywords: database queries
zbMATH Keywords: aggregate queries
zbMATH Keywords: conjunctive queries
zbMATH Keywords: equivalence of queries
zbMATH Keywords: isomorphism modulo product
zbMATH Keywords: linear expansion
zbMATH Keywords: aggregate view usability
reviewed by: Marie Duží
MaRDI profile type: Publication
full work available at URL: s00236-004-0101-y
OpenAlex ID: W2049233281
DOI: 10.1007/S00236-004-0101-Y
Recommended article: Equivalences among aggregate queries with negation
Recommended article: Deciding equivalences among conjunctive aggregate queries
Recommended article: Q3740281
Recommended article: Aggregate operators in constraint query languages
Recommended article: Towards an efficient evaluation of recursive aggregates in deductive databases
Recommended article: Q5688928
description: scientific article; zbMATH DE number 2121807