A strategy to develop adaptive and interactive query brokers

ABSTRACT

This paper focuses on the software architecture and components for supporting core adaptive and interactive query processing. The architecture permits the reuse of most of the existing adaptation techniques and facilitates the development of new ones. Developers will use it to program adaptable and interactive query evaluators, called Query Brokers. Three adaptability levels are considered: (i) static adaptability, achieved at query broker building time, (ii) personalization, achieved for each (user) query having specific needs, and (iii) dynamic adaptability, achieved during query evaluation.

The paper first proposes to leverage on the large amount of work done on query processing through a set of component interfaces, abstracting functions of brokers. Then, along with these abstractions, it presents our partial implementation of the main components for optimization mechanisms and observation, notification and rule management useful for dynamic adaptation. This partial implementation defines a toolbox facilitating the instantiation phase of a Query Broker development.

REFERENCES

• 1: Laurent Amsaleg , Michael J. Franklin , Anthony Tomasic , Tolga Urhan, Scrambling query plans to cope with unexpected delays, Proceedings of the fourth international conference on on Parallel and distributed information systems, p.208-219, December 18-20, 1996, Miami Beach, Florida, United States
• 2: Ron Avnur , Joseph M. Hellerstein, Eddies: continuously adaptive query processing, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.261-272, May 15-18, 2000, Dallas, Texas, United States
• 3: Brian Babcock , Chris Olston, Distributed top-k monitoring, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872764]
• 4: Philippe Bonnet. Prise en compte des sources de données indisponibles dans les systèmes de médiation. PhD thesis, Université de Savoie, 1999.
• 5: Françoise Fabret, Dynamic Query Scheduling in Data Integration Systems, Proceedings of the 16th International Conference on Data Engineering, p.425, February 28-March 03, 2000
• 6: Michael J. Carey , Donald Kossmann, On saying “Enough already!” in SQL, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.219-230, May 11-15, 1997, Tucson, Arizona, United States
• 7: Michael J. Carey , Donald Kossmann, Reducing the Braking Distance of an SQL Query Engine, Proceedings of the 24rd International Conference on Very Large Data Bases, p.158-169, August 24-27, 1998
• 8: Richard L. Cole , Goetz Graefe, Optimization of dynamic query evaluation plans, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.150-160, May 24-27, 1994, Minneapolis, Minnesota, United States
• 9: Ch. Collet and the members of The Mediagrid Project. Towards a mediation system framework for transparent access to largeley distributed sources. In Proceedings of the International Conference on Semantics of a Networked world (sematics for Grid databases), Paris, France, June 2004.
• 10: Ch. Collet and T-T. Vu. QBF: a Query Broker Framework for Adaptable Query Evaluation. In Proceedings of the Sixth International Conference on Flexible Query Answering Systems (FQAS), Lyon, France, June 2004.
• 11: Ruxandra Domenig , Klaus R. Dittrich, An overview and classification of mediated query systems, ACM SIGMOD Record, v.28 n.3, p.63-72, Sept. 1999 [doi>10.1145/333607.333615]
• 12: Goetz Graefe, Query evaluation techniques for large databases, ACM Computing Surveys (CSUR), v.25 n.2, p.73-169, June 1993 [doi>10.1145/152610.152611]
• 13: Goetz Graefe , David J. DeWitt, The EXODUS optimizer generator, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.160-172, May 27-29, 1987, San Francisco, California, United States
• 14: 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
• 15: G. Graefe , K. Ward, Dynamic query evaluation plans, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.358-366, June 1989, Portland, Oregon, United States
• 16: Peter J. Haas , Joseph M. Hellerstein, Ripple joins for online aggregation, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.287-298, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 17: Yannis E. Ioannidis , Raymond T. Ng , Kyuseok Shim , Timos K. Sellis, Parametric Query Optimization, Proceedings of the 18th International Conference on Very Large Data Bases, p.103-114, August 23-27, 1992
• 18: Zachary G. Ives , Alon Y. Halevy , Daniel S. Weld, Adapting to source properties in processing data integration queries, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007613]
• 19: Zachary G. Ives , Daniela Florescu , Marc Friedman , Alon Levy , Daniel S. Weld, An adaptive query execution system for data integration, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.299-310, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 20: Navin Kabra , David J. DeWitt, Efficient mid-query re-optimization of sub-optimal query execution plans, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.106-117, June 01-04, 1998, Seattle, Washington, United States
• 21: Navin Kabra , David J. DeWitt, OPT++ : an object-oriented implementation for extensible database query optimization, The VLDB Journal — The International Journal on Very Large Data Bases, v.8 n.1, p.55-78, April 1999 [doi>10.1007/s007780050074]
• 22: Georgia Koutrika , Yannis Ioannidis, Personalization of Queries in Database Systems, Proceedings of the 20th International Conference on Data Engineering, p.597, March 30-April 02, 2004
• 23: Georgia Koutrika , Yannis Ioannidis, Personalized Queries under a Generalized Preference Model, Proceedings of the 21st International Conference on Data Engineering, p.841-852, April 05-08, 2005 [doi>10.1109/ICDE.2005.106]
• 24: Rosana S. G. Lanzelotte , Patrick Valduriez, Extending the Search Strategy in a Query Optimizer, Proceedings of the 17th International Conference on Very Large Data Bases, p.363-373, September 03-06, 1991
• 25: Mavis K. Lee , Johann Christoph Freytag , Guy M. Lohman, Implementing an Interpreter for Functional Rules in a Query Optimizer, Proceedings of the 14th International Conference on Very Large Data Bases, p.218-229, August 29-September 01, 1988
• 26: William J. McKenna , Louis Burger , Chi Hoang , Melissa Truong, EROC: A Toolkit for Building NEATO Query Optimizers, Proceedings of the 22th International Conference on Very Large Data Bases, p.111-121, September 03-06, 1996
• 27: Hamid Pirahesh , Joseph M. Hellerstein , Waqar Hasan, Extensible/rule based query rewrite optimization in Starburst, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.39-48, June 02-05, 1992, San Diego, California, United States
• 28: Vijayshankar Raman , Joseph M. Hellerstein, Partial results for online query processing, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564723]
• 29: Vijayshankar Raman , Bhaskaran Raman , Joseph M. Hellerstein, Online Dynamic Reordering for Interactive Data Processing, Proceedings of the 25th International Conference on Very Large Data Bases, p.709-720, September 07-10, 1999
• 30: Carlo Sartiani , Antonio Albano, Yet Another Query Algebra For XML Data, Proceedings of the 2002 International Symposium on Database Engineering & Applications, p.106-115, July 17-19, 2002
• 31: Tolga Urhan , Michael J. Franklin, Dynamic Pipeline Scheduling for Improving Interactive Query Performance, Proceedings of the 27th International Conference on Very Large Data Bases, p.501-510, September 11-14, 2001
• 32: Tolga Urhan , Michael J. Franklin , Laurent Amsaleg, Cost-based query scrambling for initial delays, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.130-141, June 01-04, 1998, Seattle, Washington, United States
• 33: Tuyet-Trinh Vu. Une approche pour la construction d'évaluateurs adaptables de requêtes. PhD thesis, Institut National Politechnique de Grenoble, France, 2005.
• 34: Tuyet-Trinh Vu , Christine Collet, Adaptable Query Evaluation Using QBF, Proceedings of the International Database Engineering and Applications Symposium, p.265-270, July 07-09, 2004 [doi>10.1109/IDEAS.2004.7]
• 35: Gio Wiederhold, Mediators in the Architecture of Future Information Systems, Computer, v.25 n.3, p.38-49, March 1992 [doi>10.1109/2.121508]
• 36: Annita N. Wilschut , Peter M. G. Apers, Dataflow query execution in a parallel main-memory environment, Proceedings of the first international conference on Parallel and distributed information systems, p.68-77, December 1991, Miami, Florida, United States

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

General Terms:
Design, Performance

Keywords:
adaptable query evaluation, personalized query evaluation, query evaluation framework