A framework for Automatic Web Service Composition based on service dependency analysis

The practice of composing web services has received an increasing interest with the emerging application development architecture called Service Oriented Architecture (SOA). A web service composition can be done either manually or (semi-) automatically. Doing composition (semi-) automatically minimizes runtime problems that arise due to dynamic nature of runtime environments. However, the implementation of (semi-) automatic composition demands for the automation of a process model or a composition plan generation process. In addition, creating a composite service or applications from component services, that are developed and meant to work independently, causes unavoidable dependencies among the services involved. Consequently, in a composite service development, understanding, analyzing and tracking of such dependencies becomes important. This thesis views the process model generation sub-task of a service composition as a service dependency identifification and analysis problem. In this thesis, we propose a dependency based automatic process model generation methods. For this purpose, the following issues are explored. First, a top layer architecture with a composition engine is developed. The architecture gives a complete picture of dependency based automatic service composition. Second, the process model generation sub-task is formulated as a service dependency identification and analysis problem. Third, a two-stepped method for automatic process model generation, given a set of candidate web service descriptions, is proposed. The first step of the proposed approach deals with the identifification of potential direct and indirect dependencies between abstract services. The direct dependency extraction is done by assuming a semantic I/O matching of service parameters. The extraction of indirect dependency from direct dependency is done using a recursive algorithm derived from the transitive closure property. Alternatively the Warshall algorithm is used. The second step of the proposed approach deals with analysis of dependency information and generation of process model (PM) automatically. To execute this step, we propose two approaches: matrix based and graph based approaches. The matrix based approach utilizes both direct and indirect dependencies. This approach represents dependencies using matrix and takes advantages of a sorting algorithm. The matrix representation facilitates a simplistic mathematical dependency analysis for generating important indicators during automatic process model creation. The process model is generated using a sorting algorithm that uses the analysis result obtained from the dependency matrix as sorting criterion. The graph based approach uses only direct dependency among candidate services. As its name indicates, in this approach the extracted I/O dependencies are represented using a directed graph. A modifified topological sorting algorithm is used for generating a process model that shows the execution order of candidate services. Both of the proposed approaches (matrix and graph based approaches) recognize the existence of cyclic dependencies and provide ways of dealing with them. The resulting process model or composition plan from both approaches has a sequential, concurrent and loop control flows. Finally, the performance of the proposed approaches is studied theoretically as well as experimentally. For the experimental validation and evaluation purpose, the approaches are implemented in a prototype that facilitates the validation and evaluation of the approaches at a larger scale. An extensive experimental performance evaluation is done fifirst on each proposed approach. The two approaches are then compared and their pros and cons under difffferent scenarios are assessed