Article Preview
Top1. 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.