Processing Aggregate Relational Queries with Hard Time Constraints.

@inproceedings{DBLP:conf/sigmod/HouOT89,
  author    = {Wen-Chi Hou and
               Gultekin {\"O}zsoyoglu and
               Baldeo K. Taneja},
  editor    = {James Clifford and
               Bruce G. Lindsay and
               David Maier},
  title     = {Processing Aggregate Relational Queries with Hard Time Constraints},
  booktitle = {Proceedings of the 1989 ACM SIGMOD International Conference on
               Management of Data, Portland, Oregon, May 31 - June 2, 1989},
  publisher = {ACM Press},
  year      = {1989},
  pages     = {68-77},
  ee        = {http://doi.acm.org/10.1145/67544.66933, db/conf/sigmod/HouOT89.html},
  crossref  = {DBLP:conf/sigmod/89},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We consider those database environments in which queries have strict timing constraints, and develop a timeconstrained query evaluation methodology. For aggregate relational algebra queries, we describe a time constrained query evaluation algorithm. The algorithm, which is implemented in our prototype DBMS, iteratively samples from input relations, and evaluates the associated estimators developed in our previous work, until a stopping criterion (e.g., a time quota or a desired error range) is satisfied.

To determine sample sizes at each stage of the iteration (so that the time quota will not be overspent) we need to have (a) accurate sample selectivity estimations of the RA operators in the query, (b) precise time cost formulas, and (c) good time-control strategies. To estimate the sample selectivities of RA operators, we use a run- time sample selectivity estimation and improvement approach which is flexible. For query time estimations, we use time-cost formulas which are adaptive and precise. To use the time quota efficiently, we propose statistical and heuristic time-control strategies to control the risk of overspending the time quota. Preliminary evaluation of the implemented prototype is also presented.

Copyright © 1989 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 Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

• 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/smod7592 or /cdrom

• 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

[AbGM 88]

Robert K. Abbott, Hector Garcia-Molina: Scheduling Real-time Transactions. SIGMOD Record 17(1): 71-81(1988)

[Coch 77]

William G. Cochran: Sampling Techniques, 3rd Edition. John Wiley 1977, ISBN 0-471-16240-X

[Chri 83]

Stavros Christodoulakis: Estimating record selectivities. Inf. Syst. 8(2): 105-115(1983)

[DFHO 86]

...

[Good 49]

...

[HoOT 88]

Wen-Chi Hou, Gultekin Özsoyoglu, Baldeo K. Taneja: Statistical Estimators for Relational Algebra Expressions. PODS 1988: 276-287

[HoOT 88a]

...

[HouO 88]

...

[JoWi 82]

...

[Liu 68]

...

[MuDe 88]

M. Muralikrishna, David J. DeWitt: Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries. SIGMOD Conference 1988: 28-36

[PSCo 84]

Gregory Piatetsky-Shapiro, Charles Connell: Accurate Estimation of the Number of Tuples Satisfying a Condition. SIGMOD Conference 1984: 256-276

[OzHO 88]

...

[Rowe 85]

Neil C. Rowe: Antisampling for Estimation: An Overview. IEEE Trans. Software Eng. 11(10): 1081-1091(1985)

[SACL 79]

Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price: Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979: 23-34

Referenced by

1. Moses Charikar, Surajit Chaudhuri, Rajeev Motwani, Vivek R. Narasayya: Towards Estimation Error Guarantees for Distinct Values. PODS 2000: 268-279
2. Kian-Lee Tan, Cheng Hian Goh, Beng Chin Ooi: Online Feedback for Nested Aggregate Queries with Multi-Threading. VLDB 1999: 18-29
3. Peter J. Haas, Joseph M. Hellerstein: Ripple Joins for Online Aggregation. SIGMOD Conference 1999: 287-298
4. Surajit Chaudhuri, Rajeev Motwani, Vivek R. Narasayya: Random Sampling for Histogram Construction: How much is enough? SIGMOD Conference 1998: 436-447
5. Daniel Barbará, William DuMouchel, Christos Faloutsos, Peter J. Haas, Joseph M. Hellerstein, Yannis E. Ioannidis, H. V. Jagadish, Theodore Johnson, Raymond T. Ng, Viswanath Poosala, Kenneth A. Ross, Kenneth C. Sevcik: The New Jersey Data Reduction Report. IEEE Data Eng. Bull. 20(4): 3-45(1997)
6. Joseph M. Hellerstein, Peter J. Haas, Helen J. Wang: Online Aggregation. SIGMOD Conference 1997: 171-182
7. Krithi Ramamritham, Panos K. Chrysanthis: A Taxonomy of Correctness Criteria in Database Applications. VLDB J. 5(1): 85-97(1996)
8. Nabil I. Hachem, Chenye Bao, Steve Taylor: Approximate Query Answering In Numerical Databases. SSDBM 1996: 63-73
9. Sumit Ganguly, Phillip B. Gibbons, Yossi Matias, Abraham Silberschatz: Bifocal Sampling for Skew-Resistant Join Size Estimation. SIGMOD Conference 1996: 271-281
10. Gultekin Özsoyoglu, Sujatha Guru Swamy, Kaizheng Du, Wen-Chi Hou: Time-Constrained Query Processing in CASE-DB. IEEE Trans. Knowl. Data Eng. 7(6): 865-884(1995)
11. Peter J. Haas, Jeffrey F. Naughton, S. Seshadri, Lynne Stokes: Sampling-Based Estimation of the Number of Distinct Values of an Attribute. VLDB 1995: 311-322
12. Peter J. Haas, Jeffrey F. Naughton, Arun N. Swami: On the Relative Cost of Sampling for Join Selectivity Estimation. PODS 1994: 14-24
13. Richard T. Snodgrass, Santiago Gomez, L. Edwin McKenzie: Aggregates in the Temporal Query Language TQuel. IEEE Trans. Knowl. Data Eng. 5(5): 826-842(1993)
14. Thomas D. C. Little, Arif Ghafoor: Interval-Based Conceptual Models for Time-Dependent Multimedia Data. IEEE Trans. Knowl. Data Eng. 5(4): 551-563(1993)
15. Wei Sun, Yibei Ling, Naphtali Rishe, Yi Deng: An Instant and Accurate Estimation Method for Joins and Selection in a Retrieval-Intensive Environment. SIGMOD Conference 1993: 79-88
16. Peter J. Haas, Jeffrey F. Naughton, S. Seshadri, Arun N. Swami: Fixed-Precision Estimation of Join Selectivity. PODS 1993: 190-201
17. Frank Olken, Doron Rotem: Sampling from Spatial Databases. ICDE 1993: 199-208
18. Gennady Antoshenkov: Random Sampling from Pseudo-Ranked B+ Trees. VLDB 1992: 375-382
19. Peter J. Haas, Arun N. Swami: Sequential Sampling Procedures for Query Size Estimation. SIGMOD Conference 1992: 341-350
20. Gultekin Özsoyoglu, Kaizheng Du, Sujatha Guru Swamy, Wen-Chi Hou: Processing Real-Time, Non-Aggregate Queries with Time-Constraints in CASE-DB. ICDE 1992: 410-417
21. Frank Olken, Doron Rotem: Maintenance of Materialized Views of Sampling Queries. ICDE 1992: 632-641
22. S. Seshadri, Jeffrey F. Naughton: Sampling Issues in Parallel Database Systems. EDBT 1992: 328-343
23. Wen-Chi Hou, Gultekin Özsoyoglu: Statistical Estimators for Aggregate Relational Algebra Queries. ACM Trans. Database Syst. 16(4): 600-654(1991)
24. Thomas D. C. Little, C. Y. Roger Chen, C. S. Chang, P. Bruce Berra: Multimedia Synchronization. IEEE Data Eng. Bull. 14(3): 26-35(1991)
25. Wen-Chi Hou, Gultekin Özsoyoglu, Erdogan Dogdu: Error-Constraint COUNT Query Evaluation in Relational Databases. SIGMOD Conference 1991: 278-287
26. Gultekin Özsoyoglu, Wen-Chi Hou, Adegbemiga Ola: Database Systems for Programmable Logic Controllers. SSDBM 1990: 183-199
27. Frank Olken, Doron Rotem: Random Sampling from Database Files: A Survey. SSDBM 1990: 92-111
28. Frank Olken, Doron Rotem, Ping Xu: Random Sampling from Hash Files. SIGMOD Conference 1990: 375-386
29. Richard J. Lipton, Jeffrey F. Naughton, Donovan A. Schneider: Practical Selectivity Estimation through Adaptive Sampling. SIGMOD Conference 1990: 1-11
30. Jeffrey F. Naughton, S. Seshadri: On Estimating the Size of Projections. ICDT 1990: 499-513

Last update Fri May 25 08:38:30 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page