Flexible and scalable cost-based query planning in mediators: A transformational approach

The Internet provides access to a wealth of information. For any given topic or application domain there are a variety of available information sources. However, current systems, such as search engines or topic directories in the World Wide Web, offer only very limited capabilities for locating, combining, and organizing information. Mediators, systems that provide integrated access and database-like query capabilities to information distributed over heterogeneous sources, are critical to realize the full potential of meaningful access to networked information. Query planning, the task of generating a cost-efficient plan that computes a user query from the relevant information sources, is central to mediator systems. However, query planning is a computationally hard problem due to the large number of possible sources and possible orderings on the operations to process the data. Moreover, the choice of sources, data processing operations, and their ordering, strongly affects the plan cost. In this paper, we present an approach to query planning in mediators based on a general planning paradigm called Planning by Rewriting (PbR) (Ambite and Knoblock, 1997). Our work yields several contributions. First, our PbR-based query planner combines both the selection of the sources and the ordering of the operations into a single search space in which to optimize the plan quality. Second, by using local search techniques our planner explores the combined search space efficiently and produces high-quality plans. Third, because our query planner is an instantiation of a domain-independent framework it is very flexible and can be extended in a principled way. Fourth, our planner has an anytime behavior. Finally, we provide empirical results showing that our PbR-based query planner compares favorably on scalability and plan quality over previous approaches, which include both classical AI planning and dynamic-programming query optimization techniques. (C) 2000 Elsevier Science B.V. All rights reserved.