Engineering Polynomial-Time Solutions for Automatic Web Service Composition

Web Service Composition (WSC) is the task of creating some new functionality over a repository of independent resources, Web Services in particular. Services are described by their input and output parameters that are matched if they have the same textual name in service definition for the classic, simplified version of WSC. The problem requires finding an ordered list of services such that all input parameters are available starting from the initially user known parameters and revealing all user required parameters. In this paper we propose a proven efficient polynomial-time solution to Automatic WSC combined with a heuristic for shortening the solution length: the number of Web Services in the composition. The algorithm is tested against several benchmarks of tests and is compared with previous solutions that use AI Planning, revealing tremendous improvements. Two benchmarks are well-known in WSC literature but due to lack of high run time variations over their tests, a new benchmark is created with a special designed generator described in the paper. The new tests reveal more meaningful information.