Exact and Approximate Aggregation in Constraint Query.

@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},
  ee        = {http://doi.acm.org/10.1145/303976.303987, db/conf/pods/BenediktL99.html},
  crossref  = {DBLP:conf/pods/99},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Copyright © 1999 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD DiSC

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/DISC001 or /cdrom

ACM SIGMOD Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

Online Edition: ACM Digital Library

References

[1]

Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
Contents BibTeX

[2]

Serge Abiteboul, Victor Vianu: Datalog Extensions for Database Queries and Updates. J. Comput. Syst. Sci. 43(1): 62-124(1991) BibTeX

[3]

...

[4]

...

[5]

Michael Benedikt, Guozhu Dong, Leonid Libkin, Limsoon Wong: Relational Expressive Power of Constraint Query Languages. J. ACM 45(1): 1-34(1998) BibTeX

[6]

Michael Benedikt, Leonid Libkin: Languages for Relational Databases over Interpreted Structures. PODS 1997: 87-98 BibTeX

[7]

Michael Benedikt, Leonid Libkin: Safe Constraint Queries. PODS 1998: 99-108 BibTeX

[8]

...

[9]

...

[10]

Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, Manfred K. Warmuth: Learnability and the Vapnik-Chervonenkis dimension. J. ACM 36(4): 929-965(1989) BibTeX

[11]

Jan Chomicki, Dina Q. Goldin, Gabriel M. Kuper: Variable Independence and Aggregation Closure. PODS 1996: 40-48 BibTeX

[12]

Jan Chomicki, Gabriel M. Kuper: Measuring Infinite Relations. PODS 1995: 78-85 BibTeX

[13]

Larry Denenberg, Yuri Gurevich, Saharon Shelah: Definability by Constant-Depth Polynomial-Size Circuits. Information and Control 70(2/3): 216-240(1986) BibTeX

[14]

Martin E. Dyer, Alan M. Frieze: On the Complexity of Computing the Volume of a Polyhedron. SIAM J. Comput. 17(5): 967-974(1988) BibTeX

[15]

Martin E. Dyer, Alan M. Frieze, Ravi Kannan: A Random Polynomial Time Algorithm for Approximating the Volume of Convex Bodies. J. ACM 38(1): 1-17(1991) BibTeX

[16]

Phillip B. Gibbons, Yossi Matias: New Sampling-Based Summary Statistics for Improving Approximate Query Answers. SIGMOD Conference 1998: 331-342 BibTeX

[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) BibTeX

[18]

...

[19]

Stéphane Grumbach, Jianwen Su: Finitely Representable Databases. J. Comput. Syst. Sci. 55(2): 273-298(1997) BibTeX

[20]

Stéphane Grumbach, Jianwen Su: Queries with Arithmetical Constraints. Theor. Comput. Sci. 173(1): 151-181(1997) BibTeX

[21]

Stéphane Grumbach, Maurizio Rafanelli, Leonardo Tininini: Querying Aggregate Data. PODS 1999: 174-184 BibTeX

[22]

Joseph M. Hellerstein, Peter J. Haas, Helen J. Wang: Online Aggregation. SIGMOD Conference 1997: 171-182 BibTeX

[23]

Paris C. Kanellakis, Gabriel M. Kuper, Peter Z. Revesz: Constraint Query Languages. J. Comput. Syst. Sci. 51(1): 26-52(1995) BibTeX

[24]

Marek Karpinski, Angus Macintyre: Approximating the Volume of General Pfaffian Bodies. Structures in Logic and Computer Science 1997: 162-173 BibTeX

[25]

...

[26]

Pascal Koiran: Approximating the Volume of Definable Sets. FOCS 1995: 134-141 BibTeX

[27]

Gabriel M. Kuper: Aggregation in Constraint Databases. PPCP 1993: 166-173 BibTeX

[28]

...

[29]

Shamim A. Naqvi, Shalom Tsur: A Logical Language for Data and Knowledge Bases. Computer Science Press 1989, ISBN 0-7167-8200-6
BibTeX

[30]

Christos H. Papadimitriou, Dan Suciu, Victor Vianu: Topological Queries in Spatial Databases. PODS 1996: 81-92 BibTeX

[31]

Christos H. Papadimitriou, Mihalis Yannakakis: On Limited Nondeterminism and the Complexity of the V-C Dimension. J. Comput. Syst. Sci. 53(2): 161-170(1996) BibTeX

[32]

Jan Paredaens, Jan Van den Bussche, Dirk Van Gucht: First-order Queries on Finite Structures over the Reals. LICS 1995: 79-87 BibTeX

[33]

...

[34]

...

[35]

Luc Segoufin, Victor Vianu: Querying Spatial Databases via Topological Invariants. PODS 1998: 89-98 BibTeX

[36]

...

[37]

...

[38]

Luc Vandeurzen, Marc Gyssens, Dirk Van Gucht: An Expressive Language for Linear Spatial Database Queries. PODS 1998: 109-118 BibTeX

[39]

...

[40]

...

Referenced by

1. Victor Vianu: Review - Exact and Approximate Aggregation in Constraint Query. ACM SIGMOD Digital Review 2: (2000)
2. Chris Olston, Jennifer Widom: Offering a Precision-Performance Tradeoff for Aggregation Queries over Replicated Data. VLDB 2000: 144-155
3. David Gross, Michel de Rougemont: Uniform Generation in Spatial Constraint Databases and Applications. PODS 2000: 254-259
4. Floris Geerts, Bart Kuijpers: Linear Approximation of Planar Spatial Databases Using Transitive-Closure Logic. PODS 2000: 126-135
5. Leonid Libkin: Some Remarks on Variable Independence, Closure, and Orthographic Dimension in Constraint Databases. SIGMOD Record 28(4): 24-28(1999)