Efficient evaluation of queries in a mediator for WebSources

ABSTRACT

We consider an architecture of mediators and wrappers for Internet accessible WebSources of limited query capability. Each call to a source is a WebSource Implementation (WSI) and it is associated with both a capability and (a possibly dynamic) cost. The multiplicity of WSIs with varying costs and capabilities increases the complexity of a traditional optimizer that must assign WSIs for each remote relation in the query while generating an (optimal) plan. We present a two-phase Web Query Optimizer (WQO). In a pre-optimization phase, the WQO selects one or more WSIs for a pre-plan; a pre-plan represents a space of query evaluation plans (plans) based on this choice of WSIs. The WQO uses cost-based heuristics to evaluate the choice of WSI assignment in the pre-plan and to choose a good pre-plan. The WQO uses the pre-plan to drive the extended relational optimizer to obtain the best plan for a pre-plan. A prototype of the WQO has been developed. We compare the effectiveness of the WQO, i.e., its ability to efficiently search a large space of plans and obtain a low cost plan, in comparison to a traditional optimizer. We also validate the cost-based heuristics by experimental evaluation of queries in the noisy Internet environment.

REFERENCES

• 1: S. Adali , K. S. Candan , Y. Papakonstantinou , V. S. Subrahmanian, Query caching and optimization in distributed mediator systems, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.137-146, June 04-06, 1996, Montreal, Quebec, Canada
• 2: Laurent Amsaleg , Michael J. Franklin , Anthony Tomasic, Dynamic Query Operator Scheduling for Wide-Area Remote Access, Distributed and Parallel Databases, v.6 n.3, p.217-246, July 1998 [doi>10.1023/A:1008646115473]
• 3: 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
• 4: L. Bright, J.-R. Gruser, L. Raschid, and M. E. Vidal. A wrapper generation toolkit to specify and construct wrappers for webaccesible data sources (websources). Journal of Computer Systems Special Issue on Semantics in the WWW, 14(2):83-98, 1999.
• 5: L. Bright and L. Raschid. Cost modeling of wrappers for web accesible data sources (websources). http://www.umiacs.umd.edu/labs/CLIP/DARPA/ww97.html. (under review), 1998.
• 6: Surajit Chaudhuri , Kyuseok Shim, Query Optimization in the Presence of Foreign Functions, Proceedings of the 19th International Conference on Very Large Data Bases, p.529-542, August 24-27, 1993
• 7: Jianjun Chen , David J. DeWitt , Feng Tian , Yuan Wang, NiagaraCQ: a scalable continuous query system for Internet databases, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.379-390, May 15-18, 2000, Dallas, Texas, United States
• 8: 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
• 9: B. Eckman, A. Kosky, and L. Laroco. Extending traditional query-based integration approaches for functional characterization of post-genomic data. BioInformatics, 17(7):587-601, 2001.
• 10: Barbara A. Eckman , Zoé Lacroix , Louiqa Raschid, Optimized Seamless Integration of Biomolecular Data, Proceedings of the 2nd IEEE International Symposium on Bioinformatics and Bioengineering, p.23, March 04-06, 2001
• 11: Daniela Florescu , Alon Levy , Ioana Manolescu , Dan Suciu, Query optimization in the presence of limited access patterns, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.311-322, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 12: Capability-Sensitive Query Processing on Internet Sources, Proceedings of the 15th International Conference on Data Engineering, p.50, March 23-26, 1999
• 13: Georges Gardarin , Sofiane Gannouni , Béatrice Finance , Peter Fankhausera , Wolfgang Klas , Dominique Pastrea , Régis Legoff , Antonis Ramfos, IRO-DB: a distributed system federating object and relational databases, Object-oriented multidatabase systems: a solution for advanced applications, Prentice Hall International (UK) Ltd., Hertfordshire, UK, 1995
• 14: Roy Goldman , Jennifer Widom, WSQ/DSQ: a practical approach for combined querying of databases and the Web, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.285-296, May 15-18, 2000, Dallas, Texas, United States
• 15: Jean-Robert Gruser , Louiqa Raschid , Vladimir Zadorozhny , Tao Zhan, Learning response time for WebSources using query feedback and application in query optimization, The VLDB Journal — The International Journal on Very Large Data Bases, v.9 n.1, p.18-37, March 2000 [doi>10.1007/s007780050081]
• 16: Laura M. Haas , Donald Kossmann , Edward L. Wimmers , Jun Yang, Optimizing Queries Across Diverse Data Sources, Proceedings of the 23rd International Conference on Very Large Data Bases, p.276-285, August 25-29, 1997
• 17: L. M. Haas , P. M. Schwarz , P. Kodali , E. Kotlar , J. E. Rice , W. C. Swope, DiscoveryLink: a system for integrated access to life sciences data sources, IBM Systems Journal, v.40 n.2, p.489-511, February 2001
• 18: 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
• 19: J. Hellerstein et al. Adaptive query processing: Technology in evolution. IEEE Data Engineering Bulletin, 2000.
• 20: Y. E. Ioannidis , Younkyung Kang, Randomized algorithms for optimizing large join queries, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.312-321, May 23-26, 1990, Atlantic City, New Jersey, United States
• 21: 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
• 22: Z. Ives, A. Levy, D. Weld, D. Florescu, and M. Friedman. Adaptive query processing for internet applications. IEEE Data Engineering Bulletin, 23(2):19-26, 2000.
• 23: Alon Y. Levy , Anand Rajaraman , Joann J. Ordille, Querying Heterogeneous Information Sources Using Source Descriptions, Proceedings of the 22th International Conference on Very Large Data Bases, p.251-262, September 03-06, 1996
• 24: C. Li and E. Chang. Query planning with limited source capabilities. Proceedings of ICDE, 2000.
• 25: Chen Li , Edward Y. Chang, On Answering Queries in the Presence of Limited Access Patterns, Proceedings of the 8th International Conference on Database Theory, p.219-233, January 04-06, 2001
• 26: ACM Digital Library. http://www.acm.org/dl/Search.html.
• 27: Mary Tork Roth , Fatma Ozcan , Laura M. Haas, Cost Models DO Matter: Providing Cost Information for Diverse Data Sources in a Federated System, Proceedings of the 25th International Conference on Very Large Data Bases, p.599-610, September 07-10, 1999
• 28: Hubert Naacke , Georges Gardarin , Anthony Tomasic, Leveraging Mediator Cost Models with Heterogeneous Data Sources, Proceedings of the Fourteenth International Conference on Data Engineering, p.351-360, February 23-27, 1998
• 29: Bureau of Labor Statistics. http://stats.bls.gov.
• 30: Yannis Papakonstantinou , Ashish Gupta , Laura Haas, Capabilities-based query rewriting in mediator systems, Proceedings of the fourth international conference on on Parallel and distributed information systems, p.170-183, December 18-20, 1996, Miami Beach, Florida, United States
• 31: Praveen Seshadri , Miron Livny , Raghu Ramakrishnan, The Case for Enhanced Abstract Data Types, Proceedings of the 23rd International Conference on Very Large Data Bases, p.66-75, August 25-29, 1997
• 32: P. Selinger, M. Astrahan, D. Chamberlin, R. Lorie, and T. Price. Access path selection in a relational database management system. 1979.
• 33: Scaling heterogeneous databases and the design of Disco, Proceedings of the 16th International Conference on Distributed Computing Systems (ICDCS '96), p.449, May 27-30, 1996
• 34: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 35: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 36: T. Urhan and M. Franklin. Xjoin: A reactively-scheduled pipelined join operator. IEEE Data Engineering Bulletin, 23(2):27-33, 2000.
• 37: 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
• 38: 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
• 39: Vasilis Vassalos , Yannis Papakonstantinou, Describing and Using Query Capabilities of Heterogeneous Sources, Proceedings of the 23rd International Conference on Very Large Data Bases, p.256-265, August 25-29, 1997
• 40: V. Vassalos and Y. Papakonstantinou. Using knowledge of redundancy for query optimization in mediators. Proceedings of the AAAI Symposium on AI and Data Integration, 1998.
• 41: M. E. Vidal. A Mediator for Scaling up to Multiple WebSources. PhD thesis, University Simon Bolivar, 2000.
• 42: M. E. Vidal, L. Raschid, and V. Zadorozhny. Decision support model for pre-plans. In preparation, 2001.
• 43: Ramana Yerneni , Chen Li , Jeffrey D. Ullman , Hector Garcia-Molina, Optimizing Large Join Queries in Mediation Systems, Proceeding of the 7th International Conference on Database Theory, p.348-364, January 10-12, 1999
• 44: Vladimir Zadorozhny , Louiqa Raschid , Tao Zhan , Laura Bright, Validating an Access Cost Model for Wide Area Applications, Proceedings of the 9th International Conference on Cooperative Information Systems, p.371-385, September 05-07, 2001

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software

          Nouns: World Wide Web (WWW)
      H.3.5 On-line Information Services
          Subjects: Web-based services

General Terms:
Algorithms, Documentation, Theory