Digital Symposium Collection 2000  

 
 
 
 
 
 

 


















Exact and Approximate Aggregation in Constraint Query

Michael Benedikt and Leonid Libkin

  View Paper (PDF)     View Slides (PDF)  

Return to Database Theory Sampler

Abstract
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 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. We also show, using techniques from machine learning, that a small extension of FO + POLY + SUM can probabilistically find approximations of volumes for polynomial-constraint databases.


References

Note: References link to DBLP on the Web.

[1]
Serge Abiteboul , Richard Hull , Victor Vianu : Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
Contents
[2]
Serge Abiteboul , Victor Vianu : Datalog Extensions for Database Queries and Updates. JCSS 43(1) : 62-124(1991)
[3]
...
[4]
...
[5]
Michael Benedikt , Guozhu Dong , Leonid Libkin , Limsoon Wong : Relational Expressive Power of Constraint Query Languages. JACM 45(1) : 1-34(1998)
[6]
Michael Benedikt , Leonid Libkin : Languages for Relational Databases over Interpreted Structures. PODS 1997 : 87-98
[7]
Michael Benedikt , Leonid Libkin : Safe Constraint Queries. PODS 1998 : 99-108
[8]
...
[9]
...
[10]
Anselm Blumer , Andrzej Ehrenfeucht , David Haussler , Manfred K. Warmuth : Learnability and the Vapnik-Chervonenkis Dimension. JACM 36(4) : 929-965(1989)
[11]
Jan Chomicki , Dina Q. Goldin , Gabriel M. Kuper : Variable Independence and Aggregation Closure. PODS 1996 : 40-48
[12]
Jan Chomicki , Gabriel M. Kuper : Measuring Infinite Relations. PODS 1995 : 78-85
[13]
Larry Denenberg , Yuri Gurevich , Saharon Shelah : Definability by Constant-Depth Polynomial-Size Circuits. Information and Control 70(2/3) : 216-240(1986)
[14]
M. E. Dyer , Alan M. Frieze : On the Complexity of Computing the Volume of a Polyhedron. SIAM J. Comput. 17(5) : 967-974(1988)
[15]
Martin Dyer , Alan M. Frieze , Ravi Kannan : A Random Polynomial Time Algorithm for Approximating the Volume of Convex Bodies. JACM 38(1) : 1-17(1991)
[16]
Phillip B. Gibbons , Yossi Matias : New Sampling-Based Summary Statistics for Improving Approximate Query Answers. SIGMOD Conference 1998 : 331-342
[17]
Paul W. Goldberg , Mark Jerrum : Bounding the Vapnik-Chervonenkis Dimension of Concept Classes Parameterized by Real Numbers. Machine Learning 18(2-3) : 131-148(1995)
[18]
...
[19]
Stéphane Grumbach , Jianwen Su : Finitely Representable Databases. JCSS 55(2) : 273-298(1997)
[20]
Stéphane Grumbach , Jianwen Su : Queries with Arithmetical Constraints. TCS 173(1) : 151-181(1997)
[21]
Stéphane Grumbach , Maurizio Rafanelli , Leonardo Tininini : Querying Aggregate Data. PODS 1999 : 174-184
[22]
Joseph M. Hellerstein , Peter J. Haas , Helen Wang : Online Aggregation. SIGMOD Conference 1997 : 171-182
[23]
Paris C. Kanellakis , Gabriel M. Kuper , Peter Z. Revesz : Constraint Query Languages. JCSS 51(1) : 26-52(1995)
[24]
Marek Karpinski , Angus Macintyre : Approximating the Volume of General Pfaffian Bodies. Structures in Logic and Computer Science 1997 : 162-173
[25]
...
[26]
Pascal Koiran : Approximating the Volume of Definable Sets. FOCS 1995 : 134-141
[27]
Gabriel M. Kuper : Aggregation in Constraint Databases. PPCP 1993 : 166-173
[28]
...
[29]
Shamim A. Naqvi , Shalom Tsur : A Logical Language for Data and Knowledge Bases. Computer Science Press 1989, ISBN 0-7167-8200-6
[30]
Christos H. Papadimitriou , Dan Suciu , Victor Vianu : Topological Queries in Spatial Databases. PODS 1996 : 81-92
[31]
Christos H. Papadimitriou , Mihalis Yannakakis : On Limited Nondeterminism and the Complexity of the V-C Dimension. JCSS 53(2) : 161-170(1996)
[32]
Jan Paredaens , Jan Van den Bussche , Dirk Van Gucht : First-order Queries on Finite Structures over the Reals. LICS 1995 : 79-87
[33]
...
[34]
...
[35]
Luc Segoufin , Victor Vianu : Querying Spatial Databases via Topological Invariants. PODS 1998 : 89-98
[36]
...
[37]
...
[38]
Luc Vandeurzen , Marc Gyssens , Dirk Van Gucht : An Expressive Language for Linear Spatial Database Queries. PODS 1998 : 109-118
[39]
...
[40]
...

Referenced by

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

BIBTEX

@inproceedings{DBLP:conf/pods/BenediktL99,
  author    = {Michael Benedikt and
                Leonid Libkin},
   title     = {Exact and Approximate Aggregation in Constraint Query},
   booktitle = {Proceedings of the Eighteenth ACM SIGACT-SIGMOD-SIGART Symposium
                on Principles of Database Systems, May 31 - June 2, 1999, Philadelphia,
                Pennsylvania},
   publisher = {ACM Press},
   year      = {1999},
   isbn      = {1-58113-062-7},
   pages     = {102-113},
   crossref  = {DBLP:conf/pods/99},
   bibsource = {DBLP, http://dblp.uni-trier.de} } },


























Copyright(C) 2000 ACM