Digital Review

Review - Exact and Approximate Aggregation in Constraint Query.

Victor Vianu: Review - Exact and Approximate Aggregation in Constraint Query. ACM SIGMOD Digital Review 2: (2000) BibTeX


This winner of the PODS'99 best paper award is a technical tour de force that looks at adding spatial aggregate operators, such as volume or continous average, to constraint query languages. It had been known that there is no straightforward way of adding such operators without violating the fundamental closure property of query languages: the output of a query may no longer be representable by the same class of constraints as the input. There appear to be three approaches to the problem: use approximate aggregate operators in place of precise ones, or extend the class of constraints, or only allow application of aggregates to restricted classes of queries. The paper studies these three approaches. The first one has enormous complexity even for small databases; the second one is hopeless as no reasonable class of constraints can define approximate aggregates. The third is the most promising: by adding standard relational aggregates to a language with polynomial constraints, one is able to express volumes of sets defined with linear constraints, which constitute the majority of objects used in spatial applications.

This is not a paper for the faint of heart: if things such as o-minimal structures are not household terms to you, you may need to do some reading before being able to grasp all the technical subtleties. And why not? This may be just the time to do it!

Copyright © 2000 by the author(s). Review published with permission.


Michael Benedikt, Leonid Libkin: Exact and Approximate Aggregation in Constraint Query. PODS 1999: 102-113 BibTeX
Digital Review - DBLP: [Home | Search: Author, Title | Conferences | Journals]
Digital Review: Copyright © by ACM (,
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:57:29 2009