Adaptable query optimization and evaluation in temporal middleware

ABSTRACT

Time-referenced data are pervasive in most real-world databases. Recent advances in temporal query languages show that such database applications may benefit substantially from built-in temporal support in the DBMS. To achieve this, temporal query optimization and evaluation mechanisms must be provided, either within the DBMS proper or as a source level translation from temporal queries to conventional SQL. This paper proposes a new approach: using a middleware component on top of a conventional DBMS. This component accepts temporal SQL statements and produces a corresponding query plan consisting of algebraic as well as regular SQL parts. The algebraic parts are processed by the middleware, while the SQL parts are processed by the DBMS. The middleware uses performance feedback from the DBMS to adapt its partitioning of subsequent queries into middleware and DBMS parts. The paper describes the architecture and implementation of the temporal middleware component, termed TANGO, which is based on the Volcano extensible query optimizer and the XXL query processing library. Experiments with the system demonstrate the utility of the middleware's internal processing capability and its cost-based mechanism for apportioning the processing between the middleware and the underlying DBMS.

REFERENCES

• 1: Jochen van den Bercken , Jens-Peter Dittrich , Bernhard Seeger, javax.XXL: a prototype for a library of query processing algorithms, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.588, May 15-18, 2000, Dallas, Texas, United States
• 2: Michael H. Böhlen, Temporal database system implementations, ACM SIGMOD Record, v.24 n.4, p.53-60, Dec. 1995 [doi>10.1145/219713.219758]
• 3: M. H. Bohlen. The Tiger Temporal Database System. URL: <www.cs.auc.dk/tigeradm/>(current as of February 23, 2001).
• 4: Weimin Du , Ravi Krishnamurthy , Ming-Chien Shan, Query Optimization in a Heterogeneous DBMS, Proceedings of the 18th International Conference on Very Large Data Bases, p.277-291, August 23-27, 1992
• 5: Ramez Elmasri , Shamkant B. Navathe, Fundamentals of database systems (2nd ed.), Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1994
• 6: O. Etzion, S. Jajodia, and S. Sripada (eds.). Temporal Databases: Research and Practice. LNCS 1399. Springer-Verlag (1998).
• 7: J. A. G. Gendrano, R. Shah, R. T. Snodgrass, and J. Yang. University Information System (UIS) Dataset. TIMECENTER CD-1, September, 1998.
• 8: Goetz Graefe , William J. McKenna, The Volcano Optimizer Generator: Extensibility and Efficient Search, Proceedings of the Ninth International Conference on Data Engineering, p.209-218, April 19-23, 1993
• 9: Himawan Gunadhi , Arie Segev, A framework for query optimization in temporal databases, Proceedings of the fifth international conference on Statistical and scientific database management, p.131-147, March 1990, Charlotte, North Carolina, United States
• 10: W. H. Inmon, Building the data warehouse (2nd ed.), John Wiley & Sons, Inc., New York, NY, 1996
• 11: Matthias Jarke , Jurgen Koch, Query Optimization in Database Systems, ACM Computing Surveys (CSUR), v.16 n.2, p.111-152, June 1984 [doi>10.1145/356924.356928]
• 12: Christian S. Jensen , Richard Thomas Snodgrass, Temporal Data Management, IEEE Transactions on Knowledge and Data Engineering, v.11 n.1, p.36-44, January 1999 [doi>10.1109/69.755613]
• 13: Nick Kline , Richard Thomas Snodgrass, Computing Temporal Aggregates, Proceedings of the Eleventh International Conference on Data Engineering, p.222-231, March 06-10, 1995
• 14: T. Y. C. Leung and R. R. Muntz. Stream Processing: Temporal Query Processing and Optimization. In Temporal Databases: Theory, Design, and Implementation, A. U. Tansel et al. (eds.), Benjamin/Cummings, pp. 329-355 (1993).
• 15: M. Tamer Özsu , Patrick Valduriez, Principles of distributed database systems (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1999
• 16: Mary Tork Roth , Peter M. Schwarz, Don't Scrap It, Wrap It! A Wrapper Architecture for Legacy Data Sources, Proceedings of the 23rd International Conference on Very Large Data Bases, p.266-275, August 25-29, 1997
• 17: Arie Segev , Himawan Gunadhi , Rakesh Chandra , J. George Shanthikumar, Selectivity estimation of temporal data manipulations, Information Sciences: an International Journal, v.74 n.1-2, p.111-149, Oct. 15, 1993 [doi>10.1016/0020-0255(93)90130-E]
• 18: Inga Sitzmann , Peter J. Stuckey, Improving Temporal Joins Using Histograms, Proceedings of the 11th International Conference on Database and Expert Systems Applications, p.488-498, September 04-08, 2000
• 19: Query Plans for Conventional and Temporal Queries Involving Duplicates and Ordering, Proceedings of the 16th International Conference on Data Engineering, p.547, February 28-March 03, 2000
• 20: G. Slivinskas, C. S. Jensen, and R. T. Snodgrass. Adaptable Query Optimization and Evaluation in Temporal Middleware. TIMECENTER Technical Report TR-56, URL: <www.cs.auc.dk/TimeCenter/>(2001).
• 21: Richard Thomas Snodgrass, Developing time-oriented database applications in SQL, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 22: K. Torp , C. S. Jensen , Richard Thomas Snodgrass, Stratum Approaches to Temporal DBMS Implementation, Proceedings of the 1998 International Symposium on Database Engineering & Applications, p.4, July 08-10, 1998
• 23: Kristian Torp , Christian S. Jensen , Richard Thomas Snodgrass, Effective timestamping in databases, The VLDB Journal — The International Journal on Very Large Data Bases, v.8 n.3-4, p.267-288, February 2000 [doi>10.1007/s007780050008]
• 24: Costas Vassilakis, An optimisation scheme for coalesce/valid time selection operator sequences, ACM SIGMOD Record, v.29 n.1, p.38-43, March 2000 [doi>10.1145/344788.344803]
• 25: Costas Vassilakis , Nikos Lorentzos , Panagiotis Georgiadis, Implementation of transaction and concurrency control support in a temporal DBMS, Information Systems, v.23 n.5, p.335-350, July 1998 [doi>10.1016/S0306-4379(98)00015-5]
• 26: Gio Wiederhold, Mediation in information systems, ACM Computing Surveys (CSUR), v.27 n.2, p.265-267, June 1995 [doi>10.1145/210376.210390]
• 27: Jun Yang , Huacheng C. Ying , Jennifer Widom, TIP: a temporal extension to Informix, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.596, May 15-18, 2000, Dallas, Texas, United States
• 28: Clement T. Yu , Weiyi Meng, Principles of database query processing for advanced applications, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Design, Languages, Management, Measurement, Performance, Theory