Processing Time-Constrained Aggregate Queries in CASE-DB.

@article{DBLP:journals/tods/HouO93,
  author    = {Wen-Chi Hou and
               Gultekin {\"O}zsoyoglu},
  title     = {Processing Time-Constrained Aggregate Queries in CASE-DB},
  journal   = {ACM Trans. Database Syst.},
  volume    = {18},
  number    = {2},
  year      = {1993},
  pages     = {224-261},
  ee        = {http://doi.acm.org/10.1145/151634.151636, db/journals/tods/HouO93.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

In this paper, we present an algorithm to strictly control the time to process an estimator for an aggregate relational query. The algorithm implemented in a prototype database management system, called CASE-DB, iteratively samples from input relations, and evaluates the associated estimator until the time quota expires.

In order to estimate the time cost of a query, CASE-DB uses adaptive time cost formulas. The formulas are adaptive in that the parameters of the formulas can be adjusted at runtime to better fit the characteristics of a query. To control the use of time quota, CASE-DB adopts the one-at-a-time-interval time control strategy to make a tradeoff between the risks of overspending and the overhead, finally, experimental evaluation of the methodology is presented.

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

Joint ACM SIGMOD / IEEE Computer Society 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 CD and click on the path of your mount point:
  /Anthology/An3-2 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/aDVD2 or /dvd

Online Edition: ACM Digital Library

References

[1]

Robert K. Abbott, Hector Garcia-Molina: Scheduling Real-time Transactions: a Performance Evaluation. VLDB 1988: 1-12 BibTeX

[2]

Robert K. Abbott, Hector Garcia-Molina: Scheduling Real-Time Transactions with Disk Resident Data. VLDB 1989: 385-396 BibTeX

[3]

Alejandro P. Buchmann, Dennis R. McCarthy, Meichun Hsu, Umeshwar Dayal: Time-Critical Database Scheduling: A Framework For Integrating Real-Time Scheduling and Concurrency Control. ICDE 1989: 470-480 BibTeX

[4]

Günter von Bültzingsloewen, Klaus R. Dittrich, Cirano Iochpe, Rolf-Peter Liedtke, Peter C. Lockemann, Michael Schryro: KARDAMOM - A Dataflow Database Machine For Real-Time Applications. SIGMOD Record 17(1): 44-50(1988) BibTeX

[5]

Michael J. Carey, Rajiv Jauhari, Miron Livny: Priority in DBMS Resource Scheduling. VLDB 1989: 397-410 BibTeX

[6]

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

[7]

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

[8]

...

[9]

Umeshwar Dayal, Barbara T. Blaustein, Alejandro P. Buchmann, Upen S. Chakravarthy, Meichun Hsu, R. Ledin, Dennis R. McCarthy, Arnon Rosenthal, Sunil K. Sarin, Michael J. Carey, Miron Livny, Rajiv Jauhari: The HiPAC Project: Combining Active Databases and Timing Constraints. SIGMOD Record 17(1): 51-70(1988) BibTeX

[10]

...

[11]

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

[12]

...

[13]

Wen-Chi Hou, Gultekin Özsoyoglu: Statistical Estimators for Aggregate Relational Algebra Queries. ACM Trans. Database Syst. 16(4): 600-654(1991) BibTeX

[14]

...

[15]

...

[16]

Kwei-Jay Lin, Ming-Ju Lin: Enhancing Availability in Distributed Real-Time Databases. SIGMOD Record 17(1): 34-43(1988) BibTeX

[17]

Dennis R. McCarthy, Umeshwar Dayal: The Architecture Of An Active Data Base Management System. SIGMOD Conference 1989: 215-224 BibTeX

[18]

Michael V. Mannino, Paicheng Chu, Thomas Sager: Statistical Profile Estimation in Database Systems. ACM Comput. Surv. 20(3): 191-221(1988) BibTeX

[19]

...

[20]

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

[21]

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

[22]

Frank Olken, Doron Rotem: Simple Random Sampling from Relational Databases. VLDB 1986: 160-169 BibTeX

[23]

Frank Olken, Doron Rotem: Random Sampling from B+ Trees. VLDB 1989: 269-277 BibTeX

[24]

Frank Olken, Doron Rotem, Ping Xu: Random Sampling from Hash Files. SIGMOD Conference 1990: 375-386 BibTeX

[25]

...

[26]

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

[27]

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 BibTeX

[28]

Mukesh Singhal: Issues and Approaches to Design of Real-Time Database Systems. SIGMOD Record 17(1): 19-33(1988) BibTeX

[29]

...

[30]

John A. Stankovic, Wei Zhao: On Real-Time Transactions. SIGMOD Record 17(1): 4-18(1988) BibTeX

[31]

...

Referenced by

1. Wen-Chi Hou: Extraction and Applications of Statistical Relationships in Relational Databases. IEEE Trans. Knowl. Data Eng. 8(6): 939-945(1996)
2. Nevzat Hurkan Balkir, Eser Sükan, Gultekin Özsoyoglu, Z. Meral Özsoyoglu: VISUAL: A Graphical Icon-Based Query Language. ICDE 1996: 524-533
3. Gultekin Özsoyoglu, Richard T. Snodgrass: Temporal and Real-Time Databases: A Survey. IEEE Trans. Knowl. Data Eng. 7(4): 513-532(1995)
4. 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)
5. Wen-Chi Hou, Zhongyang Zhang: Enhancing Database Correctness: a Statistical Approach. SIGMOD Conference 1995: 223-232
6. Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993)