Home
Isn't this the same as ...?
Resources
Members
Papers

 Query Optimization over Web Services
U. Srivastava, J. Widom, K. Munagala, and R. Motwani
( Abstract 
Full Text )
Web services are becoming a standard method of sharing data and functionality among looselycoupled systems. We propose a generalpurpose Web Service Management System (WSMS) that enables querying multiple web services in a transparent and integrated fashion. In this paper, we consider the problem of query optimization inside a WSMS for SelectProjectJoin queries spanning multiple web services. Our main result is an algorithm for optimally arranging the web services in a query into a pipelined execution plan that minimizes the total running time of the query. We also give an algorithm for determining the optimal granularity of data ``chunks'' to be used for each web service call. Experiments with an initial prototype indicate that our algorithms can lead to significant performance improvement over more straightforward techniques.
 Ordering Pipelined Query Operators with Precedence Constraints
J. Burge, K. Munagala, and U. Srivastava
This paper addresses the general form of the problem introduced in [1]
above.
( Abstract 
Full Text )
We consider the problem of optimally arranging a collection
of query operators into a pipelined execution plan in
the presence of precedence constraints among the operators. The goal of
our optimization is to maximize the rate at which input data items can be processed through the
pipelined plan. We consider two different scenarios: one in
which each operator is fixed to run on a separate machine,
and the other in which all operators run on the same machine. Due to
parallelism in the former scenario, the cost of
a plan is given by the maximum (or bottleneck) cost incurred
by any operator in the plan. In the latter scenario, the cost
of a plan is given by the sum of the costs incurred by the operators
in the plan. These two different cost metrics lead to
fundamentally different optimization problems: Under the
bottleneck cost metric, we give a general, polynomialtime
greedy algorithm that always finds the optimal plan. However, under
the sum cost metric, the problem is much harder:
We show that it is unlikely that any polynomialtime algorithm
can approximate the optimal plan to within a factor smaller than O(n^{θ}), where n
is the number of operators, and θ is some positive constant. Finally, under the sum cost
metric, for the special case when the selectivity of each operator
lies in [e,1e], we give an algorithm that produces a
2approximation to the optimal plan but has running time
exponential in 1/e.
