Aggregate Operators in Constraint Query Languages
β Scribed by Michael Benedikt; Leonid Libkin
- Book ID
- 102587334
- Publisher
- Elsevier Science
- Year
- 2002
- Tongue
- English
- Weight
- 236 KB
- Volume
- 64
- Category
- Article
- ISSN
- 0022-0000
No coin nor oath required. For personal study only.
β¦ Synopsis
We investigate the problem of how to extend constraint query languages with aggregate operators. We deal with standard relational aggregation, and also with aggregates specific to spatial data, such as volume. We study several approaches, including the addition of a new class of approximate aggregate operators which allow an error tolerance in the computation. We show how techniques of M. Karpinski and A. Macintyre (in ''Structures in Logic and Computer Science: A Selection of Essays in Honor of A. Ehrenfeucht,'' Springer Lecture Notes on Computer Science 1261, pp. 162-173, Springer-Verlag, Berlin, 1997) and P. Koiran (in ''FOCS '95, based on VC-dimension can be used to give languages with approximation operators, but also show that these languages have a number of shortcomings. We then give a set of results showing that it is impossible to get constraint-based languages that admit definable aggregation operators, both for exact operators and for approximate ones. These results are quite robust, in that they show that closure under aggregation is problematic even when the class of functions permitted in constraints is expanded. This motivates a different approach to the aggregation problem. We introduce a language FO+Poly+Sum, which permits standard discrete aggregation operators to be applied to the outputs of range-restricted constraint queries. We show that this language has a number of attractive closure and expressivity properties, and that it can compute volumes of linear-constraint databases.
π SIMILAR VOLUMES
It is known that standard query languages for constraint databases lack the power to express connectivity properties. Such properties are important in the context of geographical databases, where one naturally wishes to ask queries about connectivity (What are the connected components of a given set