Processing time-constrained aggregate queries in CASE-DB

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.

REFERENCES

• 1: Robert K. Abbott , Hector Garcia-Molina, Scheduling Real-time Transactions: a Performance Evaluation, Proceedings of the 14th International Conference on Very Large Data Bases, p.1-12, August 29-September 01, 1988
• 2: R. Abbott , H. Garcia-Molina, Scheduling real-time transactions with disk resident data, Proceedings of the 15th international conference on Very large data bases, p.385-395, July 1989, Amsterdam, The Netherlands
• 3: Alejandro P. Buchmann , Dennis R. McCarthy , M. Hsu , Umeshwar Dayal, Time-Critical Database Scheduling: A Framework For Integrating Real-Time Scheduling and Concurrency Control, Proceedings of the Fifth International Conference on Data Engineering, p.470-480, February 06-10, 1989
• 4: Gunter von Bultzingsloewen , Klaus R. Dittrich, Kardamom—a dataflow database machine for real-time applications, ACM SIGMOD Record, v.17 n.1, p.44-50, March, 1988 [doi>10.1145/44203.44207]
• 5: M. J. Carey , R. Jauhari , M. Livny, Priority in DBMS resource scheduling, Proceedings of the 15th international conference on Very large data bases, p.397-410, July 1989, Amsterdam, The Netherlands
• 6: COCHR~N, W.G. Samphng Technlques. Third Ed John Wiley & Sons, 1977.
• 7: CHRISTODOULAKIS, S. Estimating record selectivitms. Inf. Syst. 8, 2 (June 1983), 105-115.
• 8: CHRISTODOULAKIS, S. On the estmmtlon and use of selectivitles m database performance evaluation. Tech. Rep. CS-89-24, Univ. of Waterloo, June 1989.
• 9: U. Dayal , B. Blaustein , A. Buchmann , U. Chakravarthy , M. Hsu , R. Ledin , D. McCarthy , A. Rosenthal , S. Sarin , M. J. Carey , M. Livny , R. Jauhari, The HiPAC project: combining active databases and timing constraints, ACM SIGMOD Record, v.17 n.1, p.51-70, March, 1988 [doi>10.1145/44203.44208]
• 10: GOODMAN, L.A. On the estimation of the number of classes in a population. Ann. Math Stat. 20, (1949), 572-574.
• 11: Wen-Chi Hou , Gultekin Ozsoyoglu , Baldeo K. Taneja, Statistical estimators for relational algebra expressions, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.276-287, March 1988, Austin, Texas, United States [doi>10.1145/308386.308455]
• 12: Wen-Chi Hou , Gultekin Ozsoyoglu, Relational aggregate query processing techniques for real-time databases, 1989
• 13: Wen-Chi Hou , Gultekin Ozsoyoglu, Statistical estimators for aggregate relational algebra queries, ACM Transactions on Database Systems (TODS), v.16 n.4, p.600-654, Dec. 1991 [doi>10.1145/115302.115300]
• 14: Jiandong Huang , John A. Stankovic , Don Towsley , Krithi Ramamritham, Experimental Evaluation of Real-Time Transaction Processing, University of Massachusetts, Amherst, MA, 1989
• 15: R. A. Johnson , D. W. Wichern, Applied multivariate statistical analysis, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 16: Kwei-Jay Lin , Ming-Ju Lin, Enhancing availability in distributed real-time databases, ACM SIGMOD Record, v.17 n.1, p.34-43, March, 1988 [doi>10.1145/44203.44206]
• 17: Dennis McCarthy , Umeshwar Dayal, The architecture of an active database management system, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.215-224, June 1989, Portland, Oregon, United States
• 18: Michael V. Mannino , Paicheng Chu , Thomas Sager, Statistical profile estimation in database systems, ACM Computing Surveys (CSUR), v.20 n.3, p.191-221, Sept. 1988 [doi>10.1145/62061.62063]
• 19: Jacob Paul Morgenstein, Computer based management information systems embodying answer accuracy as a user parameter, 1981
• 20: M. Muralikrishna , David J. DeWitt, Equi-depth multidimensional histograms, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.28-36, June 01-03, 1988, Chicago, Illinois, United States
• 21: Gregory Piatetsky-Shapiro , Charles Connell, Accurate estimation of the number of tuples satisfying a condition, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 22: Frank Olken , Doron Rotem, Simple Random Sampling from Relational Databases, Proceedings of the 12th International Conference on Very Large Data Bases, p.160-169, August 25-28, 1986
• 23: F. Olken , D. Rotem, Random sampling from B+ trees, Proceedings of the 15th international conference on Very large data bases, p.269-277, July 1989, Amsterdam, The Netherlands
• 24: Frank Olken , Doron Rotem , Ping Xu, Random sampling from hash files, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.375-386, May 23-26, 1990, Atlantic City, New Jersey, United States
• 25: Ross, S.M. Introduction to Probability Models. 2nd Ed., Academic Press, 1980.
• 26: Neil C. Rowe, Antisampling for estimation: an overview, IEEE Transactions on Software Engineering, v.11 n.10, p.1081-1091, Oct. 1985 [doi>10.1109/TSE.1985.231855]
• 27: P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
• 28: Mukesh Singhal, Issues and approaches to design of real-time database systems, ACM SIGMOD Record, v.17 n.1, p.19-33, March, 1988 [doi>10.1145/44203.44205]
• 29: SCHEAFFER, R., MENDENHALL, W., AND OTT, L. Elementary survey sampling. 3rd Ed., Duxbury Press, 1986.
• 30: John A. Stankovic , Wei Zhao, On real-time transactions, ACM SIGMOD Record, v.17 n.1, p.4-18, March, 1988 [doi>10.1145/44203.44204]
• 31: SUKHATME, P.V. Sampling Theory of Surveys Application. Third Ed., New Delhi, India and Iowa State Univ. Press, Ames, Iowa, 1984.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Statistical computing

  H. Information Systems
  H.2 DATABASE MANAGEMENT

  J. Computer Applications
  J.7 COMPUTERS IN OTHER SYSTEMS
      Subjects: Real time

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
estimation, relational algebra, risk of overspending, sampling, selectivity, time constraints