the quality of the optimal plans.  The quality achieved by PbR is comparable with that value.

In fact it is slightly better which may be due to the relatively small number of problems tested (25 per block size) or to skew in our random problem generator. Interestingly the plans found by IPP are actually of low quality. This is due to the fact that IPP produces shortest parallel plans. That means that the plans can be constructed in the fewest time steps, but IPP may introduce more actions in each time step than are required.

In summary, the experiments in this and the previous sections show that across a variety of domains PbR scales to large problems while still producing high-quality plans.

![0_image_0.png](0_image_0.png)

## 4.4 Query Planning

Query Planning is a problem of considerable practical importance.  It is central to traditional database and mediator systems. In this section we present some results in distributed query planning to highlight the use of PbR in a domain with a complex cost function. A detailed description of query planning, including a novel query processing algorithm for mediators based on PbR, and a more extensive experimental analysis appear in (Ambite & Knoblock, 2000; Ambite, 1998).

Query planning involves generating a plan that efficiently computes a user query from the relevant information sources. This plan is composed of data retrieval actions at distributed information sources and data manipulation operations, such as those of the relational algebra: join, selection, union, etc. The specification of the operators for query planning and the encoding of information goals that we are using was first introduced by Knoblock (1996). A sample information goal is shown in Figure 27. This goal asks to send to the output device of the mediator all the names of airports in Tunisia.  Two sample operators are shown in Figure 28. The retrieve operator executes a query at a remote information source and transports the data to the mediator, provided that the source is in operation ( source-available ) and that the source is capable of processing the query
(source-acceptable-query). The join operator takes two subqueries, whi are available locally at the mediator, and combines them using some conditions to produce the joined query.