𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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


Computational Power in Query Languages
✍ Davis, Henry W.; Winslow, Leon E. πŸ“‚ Article πŸ“… 1982 πŸ› Society for Industrial and Applied Mathematics 🌐 English βš– 935 KB
Reachability and connectivity queries in
✍ Michael Benedikt; Martin Grohe; Leonid Libkin; Luc Segoufin πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 401 KB

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