ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Semantic Complexity of Classes of Relational Queries and Query Independent Data Partitioning.

Shaibal Roy: Semantic Complexity of Classes of Relational Queries and Query Independent Data Partitioning. PODS 1991: 259-267
@inproceedings{DBLP:conf/pods/Roy91,
  author    = {Shaibal Roy},
  title     = {Semantic Complexity of Classes of Relational Queries and Query
               Independent Data Partitioning},
  booktitle = {Proceedings of the Tenth ACM SIGACT-SIGMOD-SIGART Symposium on
               Principles of Database Systems, May 29-31, 1991, Denver, Colorado},
  publisher = {ACM Press},
  year      = {1991},
  isbn      = {0-89791-430-9},
  pages     = {259-267},
  ee        = {http://doi.acm.org/10.1145/113413.113437, db/conf/pods/Roy91.html},
  crossref  = {DBLP:conf/pods/91},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

We introduce a measure of the semantic complexity of classes of selection queries in relational databases. This measure allows us to extend certain probabilistic bounds hitherto provable only for individual queries to an entire class of queries. Two applications follow immediately from well known results in the theory of uniform convergence. The first addresses the issue of using a single set of random samples to estimate selectivities of an entire class of queries. The second application finds a small set of tuples such that all expensive queries in our class are represented in the sample. The issue of horizontal partitioning of relations in a parallel relational database is addressed. It is shown that for any class of queries having finite complexity, any partitioning scheme satisfying a certain query independent combinatorial constraint has the property that for every query in this class the workload is distributed evenly among all partitions. A common family of hash functions is shown to satisfy this constraint.

Copyright © 1991 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.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Tenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 29-31, 1991, Denver, Colorado. ACM Press 1991, ISBN 0-89791-430-9
Contents BibTeX

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 770 KB]

References

[AGA90]
Khaled A. S. Abdel-Ghaffar, Amr El Abbadi: Optimal Disk Allocation for Partial Match Queries. ACM Trans. Database Syst. 18(1): 132-156(1993) BibTeX
[AST90]
...
[BEHW89]
Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, Manfred K. Warmuth: Learnability and the Vapnik-Chervonenkis dimension. J. ACM 36(4): 929-965(1989) BibTeX
[Che52]
...
[CLR90]
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest: Introduction to Algorithms. The MIT Press and McGraw-Hill Book Company 1989, ISBN 0-262-03141-8,0-07-013143-0
BibTeX
[CW79]
Larry Carter, Mark N. Wegman: Universal Classes of Hash Functions. J. Comput. Syst. Sci. 18(2): 143-154(1979) BibTeX
[DGS+90]
David J. DeWitt, Shahram Ghandeharizadeh, Donovan A. Schneider, Allan Bricker, Hui-I Hsiao, Rick Rasmussen: The Gamma Database Machine Project. IEEE Trans. Knowl. Data Eng. 2(1): 44-62(1990) BibTeX
[Dud84]
...
[FKS84]
Michael L. Fredman, János Komlós, Endre Szemerédi: Storing a Sparse Table with 0(1) Worst Case Access Time. J. ACM 31(3): 538-544(1984) BibTeX
[FM89]
Christos Faloutsos, Dimitris N. Metaxas: Declustering Using Error Correcting Codes. PODS 1989: 253-258 BibTeX
[Gha90]
...
[Gro88]
The Tandem Performance Group: A Benchmark of NonStop SQL on the Debit Credit Transaction (Invited Paper). SIGMOD Conference 1988: 337-341 BibTeX
[HW87]
...
[KP88]
Myoung-Ho Kim, Sakti Pramanik: Optimal File Distribution For Partial Match Retrieval. SIGMOD Conference 1988: 173-182 BibTeX
[KU86]
Anna R. Karlin, Eli Upfal: Parallel Hashing-An Efficient Implementation of Shared Memory (Preliminary Version). STOC 1986: 160-168 BibTeX
[P+85]
...
[SIG88]
Haran Boral, Per-Åke Larson (Eds.): Proceedings of the 1988 ACM SIGMOD International Conference on Management of Data, Chicago, Illinois, June 1-3, 1988. ACM Press 1988
Contents BibTeX
[Ter85]
...
[Vap82]
...
[VC71]
...

Referenced by

  1. Jyrki Kivinen, Heikki Mannila: The Power of Sampling in Knowledge Discovery. PODS 1994: 77-85
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:34:04 2009