Query optimization over Web Services

Conference Paper

Web services are becoming a standard method of sharing data and functionality among loosely-coupled systems. We propose a general-purpose Web Service Management System (WSMS) that enables querying multiple web services in a transparent and integrated fashion. This paper tackles a first basic WSMS problem: query optimization for Select-Project-Join queries spanning multiple web services. Our main result is an algorithm for arranging a query's web service calls into a pipelined execution plan that optimally exploits parallelism among web services to minimize the query's total running time. Surprisingly, the optimal plan can be found in polynomial time even in the presence of arbitrary precedence constraints among web services, in contrast to traditional query optimization where the analogous problem is NP-hard. We also giye 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. Copyright 2006 VLDB Endowment, ACM.

Duke Authors

Cited Authors

  • Srivastava, U; Munagala, K; Widom, J; Motwani, R

Published Date

  • January 1, 2006

Published In

  • Vldb 2006 Proceedings of the 32nd International Conference on Very Large Data Bases

Start / End Page

  • 355 - 366

International Standard Book Number 10 (ISBN-10)

  • 1595933859

International Standard Book Number 13 (ISBN-13)

  • 9781595933850

Citation Source

  • Scopus