We present a consistency-based service composition approach, where composition problems are modelled in a generic manner using a generative constraint-based formalism. We show that in our framework concise formal speci cation of service con guration problems is possible. Preliminary results indicate that our approach is scalable and competitive with other state-of-the-art composition systems.
{ We introduce connection components that act as connectors between services.
The explicit representation of connectors provides a uniform interface contract between services and also serves as a means to explicitly model the providerconsumer relationship between services. A connection component also holds a representation of the data values that is passed along the connection. { We introduce explicit components to capture the semantics of complex data objects. This facilitates the uniform handling of service and data components ? This work was partially supported by the Australian Research Council (ARC) under grant DP0988961. n o i tca se icefi Pah p S g ison se opm Pah C Configuration Problem
GCSP Formalism Configurator CSP-Solver Composition
InPNameHomer
QantasQuery BinConn2
BinConn3 PName QantasAirBooking
FlightInfo
BinConn1 OutConfirmation
BookingConf (a) Composition Process
(b) Partial Solution in the con guration, and has the additional bene t that generic constraints can be used to impose global invariants on data structures.
In our extended framework, the service composition problem is posed as a con guration task, where a set of service components and their interconnections are sought in order to satisfy a given goal. The compositions computed in our framework can be synthesised into a form suitable to execute the composed service such as BPEL and OWL-S. We show that concise formal speci cation of service con guration problems is possible. In our framework, GCSPs are synthesised into classic CSPs allowing e cient CSP algorithms to potentially help tune implementations of reasoning tasks. Our formalism is particularly useful in scenarios where the problem size is unknown. Preliminary evaluation shows that GCSPs can quickly nd solutions for large non-trivial problems. 2
Con guration is the process of assembling larger systems from individual
components by extending an initial partial solution representing a goal until all the
requirements are satis ed. A con guration problem is de ned over a so-called
con guration domain [
Variables in C are initially considered inactive, but may be activated by a generic constraint. This can be seen as \expansion" operation, where the CSP is extended with additional variables (and possibly constraints). Only the active variables participate in the solution process, while the inactive variables remain hidden until activated. Hence, a valid con guration is an assignment of values to all active variables in C such that all constraints are satis ed.
We use the following scenario to illustrate our approach, where ights between two speci c cities on a given date are to be purchased. A partial model of service types in our travel domain is shown in Figure 2, including the available service and data types, service interfaces and relationships (modelled as inheritance), and available service instances. In our example T includes, among others, the service types FlightQuery and AirlineTicketBooking, component type BinConn representing connections, and data type BookingCon rmation.
Generic constraints are the primary constructs for expressing the semantics of components and data types in the GCSP formalism. In generic constraints, meta-variables act as placeholders for component variables. Generic constraints can be seen as prototypical constraints on a meta-level that are instantiated into \ordinary" constraints over variables in the CSP.
A generic constraint is a clause of the form A1 ^ : : : ^ Am ) B1 _ : : : _ Bn where the A's and B's are predicates over meta-variables. A generic constraint is consistent if and only if the constraint is satis ed for all bindings of meta-variables to active CSP variables.
Activation constraints are a form of generic constraints that are used to
activate additional CSP variables once new components are introduced into a
con guration. Conceptually, activation constraints govern the \growing" of the
constraint network. Activation constraints are of the form Cv =) C :p 2^ 0
and denote that each component of type (or a sub type) has a property p of
type 0. The properties that have C as their domain are referred to as ports,
while the remaining properties of primitive data type are called attributes. For
example, the activation constraint X vFlightQuery =) X :request 2^C; X :info 2^C:
ensures that for each constraint variable representing a service component of
type FlightQuery (see Figure 2), the port variables X:request and X:inf o are
activated with domain C allowing them to be connected with other components.
Data Flow is captured by distinguished BinConn components that act as
connectors between service components in the con guration. A BinConn component
acts as an interface contract between service components by providing a uniform
interface for the components connected to each port. Here, varying matching
strategies, such as the well-known subsumption match [
Service Semantics are captured by specifying attributes, IO parameters, their types, and relationships between IO parameters in form of generic constraints. For example, \A FlightRequest object is expected through the request port" is modelled as S vFlightQuery ^ S :request=BC =)BC vBinaryConn ^ BC :tout vFlightRequest ^ BC :out=S : Structural Constraints ensure service compositions are sound. In particular, constraints to prohibit the direct connection of two connection components and cyclic data ow paths are required. We de ne a component u to depend on outputs of v, denoted as u v, if a path from an input port of u to a port of v exists in the CSP graph. The integrity constraint used to ensure that all CSP instances are acyclic can then be expressed as the generic constraint C 6 C. Resource constraints are used to express aggregate operations over attributes of multiple components and to impose limits on the number of components in a con guration. For example, the cost constraint in our example is modelled as fS : ight :pricejS vBookingCon rmationg 400 . Resource constraints may also trigger the addition of new components in the con guration. Goal Requirements and User Inputs are modelled using distinguished components: available inputs are modelled as components that supply one available user input; these components are not instantiated by default, but are created by the GCSP solver on demand. Required outputs are also modelled as components; from these components, a partial con guration that represents the goal is created, which must subsequently be completed by the GCSP solver. 3
A Con guration problem for a given con guration domain D = hT ; v; C; P; D; i is de ned as a tuple hV I ; I ; Di, where V I C [ P is the set of initial variables, where P is the set of property variables activated by components in C, and I is a set of constraint instances on V I .
The solution process is illustrated in Figure 1a. Initially, the constraint network R consists of a partial composition hV I ; I i that represents the goal requirements. During the composition process, R is dynamically extended by adding new variables and constraints. After each extension, R represents a standard CSP (without generic constraints); therefore, standard algorithms can be applied to solve the CSP. The CSP R will grow 1. if a type is assigned to a component variable c, fresh variables representing the ports and properties of are introduced to satisfy activation constraints, 2. if a port variable has been chosen for assignment and no existing component is eligible, a new component is added to R, or 3. if a resource constraint cannot be satis ed using the current set of components.
The constraint network R continues to grow until all generic constraints are satis ed. Once all variables have been assigned the solving process terminates and the variable assignments are returned; the components assigned to the variables in the completed network represents a valid con guration. Otherwise, a variable is chosen for assignment and constraints are propagated. If no alternative value assignment remains for a variable, the (G)CSP is inconsistent and a di erent choice for a preceding variable assignment is explored.
To ensure termination of our composition process, we employ an iterative strategy that limits the number of components, where the threshold is iteratively increased until a solution is found.Solving iteratively allows us to limit the e ects of wrong component choice that would otherwise have resulted in inde nite expansion of the CSP.
A partial solution to the example problem is shown in Figure 1b, where the
con guration grows beginning with the goal speci cation (OutCon rmation).
Since the example only involves a few components, it can be solved almost
instantaneously in our framework. To characterise the performance of our framework,
we conducted experiments on a generalised version well-known Producer-Shipper
problem [
We presented a consistency-based service composition approach in which a
service composition problem is treated as a con guration task. We showed that
composition problems can be concisely represented by adopting a declarative,
constraint-based meta model. By translating the service composition problem as
a dynamic con guration task, we overcome the limitations of earlier work where
the structure of a composition must be known a priori [
Since the GCSPs formalism can simultaneously handle constraints on di erent
levels of abstraction, conceptual and instance speci c information can be exploited
for problem speci cation and also in the solving process. Speci c information
derived from service instances has already been applied to synthesise concrete
executable work ows in domains where conceptual information alone is insu
cient to generate precise compositions [
Preliminary evaluation shows that our framework is scalable to non-trivial problems and can solve compositions with hundreds of service instances e ciently. We are currently extending our framework to exploit work ow patterns to ensure interactions with complex ow, for example, synchronisation and exception handling, can be synthesised e ectively. We also plan to leverage earlier work on consistency-based matchmaking into our framework to improve service selection in scenarios where only partial information is available.