An Optimal and Complete Algorithm for Automatic Web Service Composition

An Optimal and Complete Algorithm for Automatic Web Service Composition

Pablo Rodriguez-Mier (University of Santiago de Compostela, Spain), Manuel Mucientes (University of Santiago de Compostela, Spain), Juan C. Vidal (University of Santiago de Compostela, Spain) and Manuel Lama (University of Santiago de Compostela, Spain)
Copyright: © 2012 |Pages: 20
DOI: 10.4018/jwsr.2012040101
OnDemand PDF Download:
No Current Special Offers


The ability of web services to build and integrate loosely-coupled systems has attracted a great deal of attention from researchers in the field of the automatic web service composition. The combination of different web services to build complex systems can be carried out using different control structures to coordinate the execution flow and, therefore, finding the optimal combination of web services represents a non-trivial search effort. Furthermore, the time restrictions together with the growing number of available services complicate further the composition problem. In this paper the authors present an optimal and complete algorithm which finds all valid compositions from the point of view of the semantic input-output message structure matching. Given a request, a service dependency graph which represents a suboptimal solution is dynamically generated. Then, the solution is improved using a backward heuristic search based on the A* algorithm which finds all the possible solutions with different number of services and runpath. Moreover, in order to improve the scalability of our approach, a set of dynamic optimization techniques have been included. The proposal has been validated using eight different repositories from the Web Service Challenge 2008, obtaining all optimal solutions with minimal overhead.
Article Preview

1. Introduction

Nowadays, Service-Oriented Architectures (SOA) (Papazoglou & Georgakopoulos, 2003) are gaining importance because of the ability to build interoperable services that can be shared over a network within multiple platforms. Thus, companies are starting to apply this principle to their business, allowing them to remain cost effective, flexible and competitive. Applications in SOA are built based on services consumed by clients that are not concerned with the underlying implementation. Specifically, web services are the preferred standard-based way to realize SOA.

Web Services are self-contained modular applications described by a collection of operations that are network-accessible through standardized web protocols, and whose features are defined using a standard XML-based language (Alonso, Casati, Kuno, & Machiraju, 2004). One of the advantages of web services is to enable greater and easier integration and interoperability among systems and applications through web service composition. This advantage allows web services to be combined by connecting their inputs and ouputs to create larger services (composite services) whose execution is orchestrated by a set of control structures defined in composition languages like WS-BPEL (Weerawarana, Curbera, Leymann, Storey, & Ferguson, 2005; Rouached, Fdhila, & Godart, 2010). Thus, the goal of web service composition is to construct new services from existing web services in order to satisfy a request (basically a set of provided inputs and a set of wanted outputs by the client) which cannot be solved by a single web service. The matching between inputs and outputs can either be done syntactically, using the information described in WSDL (Christensen, Curbera, Meredith, & Weerawarana, 2001), or semantically, using semantic markup languages like OWL-S (Burstein et al., 2004) or WSMO (de Bruijn et al., 2005).

The automatic composition problem may seem trivial problem when there are a limited number of services in a single-service architecture. However, the problem increases in complexity when the goal is to obtain optimal compositions over large web service repositories using different control structures to manage the composition flow. In fact, the web service composition problem can be reduced to the boolean satisfiability problem, i.e., the problem is NP-complete and therefore it cannot be solved in polynomial time (Lee & Kumara, 2005).

Research in this field has grown rapidly in recent years. Some approaches (Hoffmann, Bertoli, & Pistore, 2007; Sirin, Parsia, Wu, Hendler, & Nau, 2004; Klusch, Gerber, & Schmidt, 2005; Pistore, Barbon, Bertoli, Shaparau, & Traverso, 2004; Xu, Chen, & Reiff-Marganiec, 2011) treat the service composition as an artificial intelligence (AI) planning problem, where a sequence of actions lead from a initial state (inputs and preconditions) to a goal state (required outputs). These techniques work well when the repository size is relatively small and the number of constraints is high. However, most of these proposals have some drawbacks: high complexity, high computational cost and inability to maximize the parallel execution of web services.

Complete Article List

Search this Journal:
Open Access Articles
Volume 18: 4 Issues (2021): 1 Released, 3 Forthcoming
Volume 17: 4 Issues (2020)
Volume 16: 4 Issues (2019)
Volume 15: 4 Issues (2018)
Volume 14: 4 Issues (2017)
Volume 13: 4 Issues (2016)
Volume 12: 4 Issues (2015)
Volume 11: 4 Issues (2014)
Volume 10: 4 Issues (2013)
Volume 9: 4 Issues (2012)
Volume 8: 4 Issues (2011)
Volume 7: 4 Issues (2010)
Volume 6: 4 Issues (2009)
Volume 5: 4 Issues (2008)
Volume 4: 4 Issues (2007)
Volume 3: 4 Issues (2006)
Volume 2: 4 Issues (2005)
Volume 1: 4 Issues (2004)
View Complete Journal Contents Listing