ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Online Feedback for Nested Aggregate Queries with Multi-Threading.

Kian-Lee Tan, Cheng Hian Goh, Beng Chin Ooi: Online Feedback for Nested Aggregate Queries with Multi-Threading. VLDB 1999: 18-29
@inproceedings{DBLP:conf/vldb/TanGO99,
  author    = {Kian-Lee Tan and
               Cheng Hian Goh and
               Beng Chin Ooi},
  editor    = {Malcolm P. Atkinson and
               Maria E. Orlowska and
               Patrick Valduriez and
               Stanley B. Zdonik and
               Michael L. Brodie},
  title     = {Online Feedback for Nested Aggregate Queries with Multi-Threading},
  booktitle = {VLDB'99, Proceedings of 25th International Conference on Very
               Large Data Bases, September 7-10, 1999, Edinburgh, Scotland,
               UK},
  publisher = {Morgan Kaufmann},
  year      = {1999},
  isbn      = {1-55860-615-7},
  pages     = {18-29},
  ee        = {db/conf/vldb/TanGO99.html},
  crossref  = {DBLP:conf/vldb/99},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

In the paper, we study the progressive evaluation of nested queries with aggregates (i.e., the inner query block is an aggregate query), where users are provided progressively with (approximate) answers as the inner block is evaluated. We propose an incremental evaluation strategy to present answers that are certainly in the final answer space first, before presenting those whose validity may be affected as the inner query aggregates are refined. We also propose a multithreaded model in evaluating such queries: the outer query is assigned to a thread, and the inner query is assigned to another thread. The time-sliced across the two subqueries is nondeterministic in the sense that the user controls the relative rate at which these subqueries are being evaluated. We implemented a prototype system using JAVA, and evaluated our system. Our results show the effectiveness of the proposed mechanisms in providing online feedback that reduce the initial waiting time of users significantly without sacrificing on the quality of the answers.

Copyright © 1999 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.


Online Paper

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Malcolm P. Atkinson, Maria E. Orlowska, Patrick Valduriez, Stanley B. Zdonik, Michael L. Brodie (Eds.): VLDB'99, Proceedings of 25th International Conference on Very Large Data Bases, September 7-10, 1999, Edinburgh, Scotland, UK. Morgan Kaufmann 1999, ISBN 1-55860-615-7
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[1]
Roberto J. Bayardo Jr., Daniel P. Miranker: Processing Queries for First Few Answers. CIKM 1996: 45-52 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[2]
Umeshwar Dayal: Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers. VLDB 1987: 197-208 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[3]
Richard A. Ganski, Harry K. T. Wong: Optimization of Nested SQL Queries Revisited. SIGMOD Conference 1987: 23-33 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[4]
Peter J. Haas: Large-Sample and Deterministic Confidence Intervals for Online Aggregation. SSDBM 1997: 51-63 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[5]
Peter J. Haas, Joseph M. Hellerstein: Ripple Joins for Online Aggregation. SIGMOD Conference 1999: 287-298 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[6]
Peter J. Haas, Jeffrey F. Naughton, S. Seshadri, Arun N. Swami: Selectivity and Cost Estimation for Joins Based on Random Sampling. J. Comput. Syst. Sci. 52(3): 550-569(1996) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[7]
Joseph M. Hellerstein, Peter J. Haas, Helen J. Wang: Online Aggregation. SIGMOD Conference 1997: 171-182 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[8]
Wen-Chi Hou, Gultekin Özsoyoglu, Baldeo K. Taneja: Statistical Estimators for Relational Algebra Expressions. PODS 1988: 276-287 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[9]
Wen-Chi Hou, Gultekin Özsoyoglu, Baldeo K. Taneja: Processing Aggregate Relational Queries with Hard Time Constraints. SIGMOD Conference 1989: 68-77 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[10]
Won Kim: On Optimizing an SQL-like Nested Query. ACM Trans. Database Syst. 7(3): 443-469(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[11]
Richard J. Lipton, Jeffrey F. Naughton, Donovan A. Schneider, S. Seshadri: Efficient Sampling Strategies for Relational Database Operations. Theor. Comput. Sci. 116(1&2): 195-226(1993) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[12]
Guy M. Lohman, Dean Daniels, Laura M. Haas, Ruth Kistler, Patricia G. Selinger: Optimization of Nested Queries in a Distributed Relational Database. VLDB 1984: 403-415 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[13]
Frank Olken: Random Sampling from Databases. Ph.D. thesis, University of California at Berkeley LBL Technical Report 1993
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[14]
Kian-Lee Tan, Cheng Hian Goh, Beng Chin Ooi: On Getting Some Answers Quickly, and Perhaps More Later. ICDE 1999: 32-39 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[15]
Annita N. Wilschut, Peter M. G. Apers: Dataflow Query Execution in a Parallel Main-Memory Environment. PDIS 1991: 68-77 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Fri Mar 12 17:22:57 2010 by Michael Ley (ley@uni-trier.de)