# An Approach for Composing Services Based on Environment Ontology

Authors: Guangjun Cai; Bin Zhao
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

Service-oriented computing is revolutionizing the modern computing paradigms with its aim to boost software reuse and enable business agility. Under this paradigm, new services are fabricated by composing available services. The problem arises as how to effectively and efficiently compose heterogeneous services facing the high complexity of service composition. Based on environment ontology, this paper introduces a requirement-driven service composition approach. We propose the algorithms to decompose the requirement, the rules to deduct the relation between services, and the algorithm for composing service. The empirical results and the comparison with other services’ composition methodologies show that this approach is feasible and efficient.


---

## Body

## 1. Introduction

Service-oriented computing (SOC) [1], with the standardized, cross-platform and transparency characteristics, can effectively reuse and compose the existing software and system resources. It comes to become a new milestone in distributed system, to be a mainstream computing model in heterogeneous environments, and to improve the competitive advantage in the field of e-commerce [2]. Service composition, as a method to use the existing services and generate new services, is one of the key factors of the success of the service-oriented computing [3].Many institutions and enterprises have been currently engaged in the research of this area, and a series of standard language and method [3, 4] are published. The separation between the service description and the service implement, and the standardization of the service description and the service process provide the foundation to interoperate among services in various platforms. However, there are still many open problems need to be addressed for the reasons that the service is open, dynamic and changeable and that the composition problem with high complexity [4]. We believe that by solving the following problems the efficiency of the service composition can be improved.(i)
Lacking of effective model’s support. Some methods (such as [5]) do not use the model, while others (such as [6]) are based on a service-oriented process model changed with the change of services.(ii)
Few requirements and domain knowledge. Many methods (e.g., [2]) need no constraints on the behaviour of the composition services, and the domain knowledge is generally only used in the detection of match between services (such as [7]).(iii)
Lacking support to the composition of the large-grained or precise services. For example, [8] can only composite the atomic services as a composite object.The environment model completely independent of the service implement provides a basis to acquire a precise and on-demand requirement. Based on it, a requirement driven approach is proposed which with the requirement descriptions and the service descriptions based on environment ontology as inputs. This approach firstly reduces the complexity of the problem through the decomposition of the requirement in order to improve the degree of parallelism of the service composition. Then, the rules to determine the relations between the services are proposed to improve the granularity of the service. Finally, it can present the composition result in the WS-CDL [9].The rest of this paper is structured as follows. In Section2, we introduce environment ontology and a usage scenario and present the environment ontology-based descriptions of some services and requests. Section 3 proposes some algorithms decomposing the requirement, some rules to determine the relations between services, and the method to compose the services. Section 4 presents some implement results and analyse it. After discussing some related work in Section 5, we conclude in Section 6.


## 2. Environment Ontology and the Description Based on Environment Ontology

The idea of environmental modelling originates from requirements engineering. Reference [10] pointed out that the semantics of software systems is in the environment of the software rather than in the software itself. Then, [11] introduces it in service-oriented computing and uses it as the basis to characterize the services and the user requirement.


### 2.1. Environment Ontology

The environment ontology describes the nature of the entity of the service problem, as well as its possible changes, the process of the change, the conditions, and the result of the change. Environment the service entities interact with consists of various environment entities. Environment entities, either concrete or abstract, shared the same semantic with all the relevant service and the user requirements rather than relying on a service or requirement. The top-level concepts are shown in Table1.Table 1
Meanings of the concepts.
Concept
Meaning
Environment entity
Entities which a system will interact with
Causal entity
Entities whose properties include predictable causal relationships among its shared phenomena
Autonomous entity
Entities which can receive or send message autonomously usually consist of people
Symbolic entity
Entities which are a physical representation of data
Attribute
A named variable for characterizing a static property of an entity
Static attribute
Characterize the static properties of the environment entity
Dynamic attribute
Characterize the dynamic properties of the environment entity
Value
Intangible individual entity that exists outside time and space, and is not subject to change
Tree-like hierarchical state machine
A hierarchical state graph for characterizing dynamic properties of a causal entity
Finite state machine
A directed state graph for characterizing  a dynamic property
Divide
Relation between the basic state machine and a state
State
Value of an entity at a given time
Transition
A state change in a state machine represent the relation between two states
Message
The content that is sent or received from one environment entity to another
Command message
Containing the action command
Data message
Message that has no command contains only the parameters
Interaction
Observable shared phenomenon between a system and its environment entity
Message interaction
Interaction that occurs through the messaging
Value interaction
Interaction that occurs through reading or assigning the value of the static attributeThe various types of environmental entities require a different form of the description except for static properties and the interaction. Causal entities have a description of the dynamic properties in the form of the tree-like hierarchical state machines; symbolic entities and autonomous entities are with a data set and a set of events, respectively. Part of the concept is defined as follows.Define 1. Finite state machine (Fsm) describing the changes in one causal entity is a four-tuple 〈States,Trans,init,fin〉, where States is a set of the state; Trans, a set of transitions, is defined as {〈ss,mess,ts〉∣ss,ts∈States,messdenotethemessageset}; Mess, a set of messages, is defined as {〈dir,mes〉|dir=↓∣↑,mesisadatamessagedataoracommandmessageevent}, Finally, init,fin∈States, is the initial state and the target state, respectively.Define 2. Tree-like hierarchical state machine (Hsm), to describe the state change of an individual controllable entity, is a triple 〈Fsms,Divs,rootfsm〉, where Fsms is a set of fsm; Divs={〈s,fsm〉∣s is a state, s∉fsm∧s∈hsm}, where s is called the parent state of fsm; rootfsm∈Fsms.Define 3. The effect of the environment entity denoted Eff, describe the changes of the environmental entity, is defined as Events∣Datas∣Hsm, where Eff≔Events≔{〈dir,event〉∣dir=↓∣↑,eventisacommandmessage} when the entity is an autonomous entity; Eff≔Datas≔{〈dir,data〉∣dir=↓∣↑,dataisadatamessage} when the entity is a symbolic entity; Eff≔Hsm when the entity is a causal entity.Define 4. Environmental entity (EnvEnt) defined as a four-tuple 〈Name,Type,AttrSet,Eff〉, where; Name is the name of the environment entity; Type≔“S”∣“C”∣“A” represents the environment entity, respectively, representing a symbolic entity, the causal entity, and autonomous entity; AttrSet≔{〈attrn,attrv〉∣attrnisanattributenameandattrvisanattributevalue}; Eff describes the change of the environment entity.


### 2.2. Describing the Service Based on Environment Ontology

Define 5. The service description based on environment ontology characterizes the semantics of the services through the physical changes the service causes. It can be defined as 〈name,Ents,Inters,Deps,EntDes,Sers,andFuncs〉, where name is a service name; Ents is a set of the environment entities; Inters is a set of interactions and it is a subset of the messages; Deps={〈se,inter,te〉∣se,te∈Ents is, respectively, the source entity and the target entity; inter∈Inters} is generated by the effect of the service between the environment entities; EntDes≔{e′∣e′ describes part of one environment entity e∈Ents} is the description of the environmental entity under the effect of the service; Sers={ser∣serisaservice} is a set of services; Funcs≔{〈func,ser〉∣func∈Ents∪Hsms∪Fsms∪Trans∪Datas∪Events,ser∈Sers} is a set of functions describing the relation between each functionality and the services provide it.The process of the service description is a process projecting service functionality to the environment entities. The input of the process consists of the Ents, Inters, and the environment ontology; the output of the process consists of Deps and EntDes. The specific algorithm can see [11, 17]. Figure 1 lists the text description and the graphics description of the two ticketing services.The description of the available service based on environment ontology.
(a)
(b)


### 2.3. Describing the Requirement Based on Environment Ontology

Define 6. The requirement description based on environment ontology can be seen as a service description without the service’s implementation. It is defined as a quintuple 〈name,Ents,Inters,Deps,EntDes〉, where the meaning of the elements is the same with that in Define 5.The process to describe the requirement is similar to that which depicts services. There are two results when the requirement is described: the requirement is described with only one option, or description with more than one option. The latter case needs more user constrain. Figure2 presents a specific illustration of the requirement, wherein the text description is presented in (a) and the effect of changes of the ticket in (b).The requirement description based on environment ontology.
(a)
(b)


## 2.1. Environment Ontology

The environment ontology describes the nature of the entity of the service problem, as well as its possible changes, the process of the change, the conditions, and the result of the change. Environment the service entities interact with consists of various environment entities. Environment entities, either concrete or abstract, shared the same semantic with all the relevant service and the user requirements rather than relying on a service or requirement. The top-level concepts are shown in Table1.Table 1
Meanings of the concepts.
Concept
Meaning
Environment entity
Entities which a system will interact with
Causal entity
Entities whose properties include predictable causal relationships among its shared phenomena
Autonomous entity
Entities which can receive or send message autonomously usually consist of people
Symbolic entity
Entities which are a physical representation of data
Attribute
A named variable for characterizing a static property of an entity
Static attribute
Characterize the static properties of the environment entity
Dynamic attribute
Characterize the dynamic properties of the environment entity
Value
Intangible individual entity that exists outside time and space, and is not subject to change
Tree-like hierarchical state machine
A hierarchical state graph for characterizing dynamic properties of a causal entity
Finite state machine
A directed state graph for characterizing  a dynamic property
Divide
Relation between the basic state machine and a state
State
Value of an entity at a given time
Transition
A state change in a state machine represent the relation between two states
Message
The content that is sent or received from one environment entity to another
Command message
Containing the action command
Data message
Message that has no command contains only the parameters
Interaction
Observable shared phenomenon between a system and its environment entity
Message interaction
Interaction that occurs through the messaging
Value interaction
Interaction that occurs through reading or assigning the value of the static attributeThe various types of environmental entities require a different form of the description except for static properties and the interaction. Causal entities have a description of the dynamic properties in the form of the tree-like hierarchical state machines; symbolic entities and autonomous entities are with a data set and a set of events, respectively. Part of the concept is defined as follows.Define 1. Finite state machine (Fsm) describing the changes in one causal entity is a four-tuple 〈States,Trans,init,fin〉, where States is a set of the state; Trans, a set of transitions, is defined as {〈ss,mess,ts〉∣ss,ts∈States,messdenotethemessageset}; Mess, a set of messages, is defined as {〈dir,mes〉|dir=↓∣↑,mesisadatamessagedataoracommandmessageevent}, Finally, init,fin∈States, is the initial state and the target state, respectively.Define 2. Tree-like hierarchical state machine (Hsm), to describe the state change of an individual controllable entity, is a triple 〈Fsms,Divs,rootfsm〉, where Fsms is a set of fsm; Divs={〈s,fsm〉∣s is a state, s∉fsm∧s∈hsm}, where s is called the parent state of fsm; rootfsm∈Fsms.Define 3. The effect of the environment entity denoted Eff, describe the changes of the environmental entity, is defined as Events∣Datas∣Hsm, where Eff≔Events≔{〈dir,event〉∣dir=↓∣↑,eventisacommandmessage} when the entity is an autonomous entity; Eff≔Datas≔{〈dir,data〉∣dir=↓∣↑,dataisadatamessage} when the entity is a symbolic entity; Eff≔Hsm when the entity is a causal entity.Define 4. Environmental entity (EnvEnt) defined as a four-tuple 〈Name,Type,AttrSet,Eff〉, where; Name is the name of the environment entity; Type≔“S”∣“C”∣“A” represents the environment entity, respectively, representing a symbolic entity, the causal entity, and autonomous entity; AttrSet≔{〈attrn,attrv〉∣attrnisanattributenameandattrvisanattributevalue}; Eff describes the change of the environment entity.


## 2.2. Describing the Service Based on Environment Ontology

Define 5. The service description based on environment ontology characterizes the semantics of the services through the physical changes the service causes. It can be defined as 〈name,Ents,Inters,Deps,EntDes,Sers,andFuncs〉, where name is a service name; Ents is a set of the environment entities; Inters is a set of interactions and it is a subset of the messages; Deps={〈se,inter,te〉∣se,te∈Ents is, respectively, the source entity and the target entity; inter∈Inters} is generated by the effect of the service between the environment entities; EntDes≔{e′∣e′ describes part of one environment entity e∈Ents} is the description of the environmental entity under the effect of the service; Sers={ser∣serisaservice} is a set of services; Funcs≔{〈func,ser〉∣func∈Ents∪Hsms∪Fsms∪Trans∪Datas∪Events,ser∈Sers} is a set of functions describing the relation between each functionality and the services provide it.The process of the service description is a process projecting service functionality to the environment entities. The input of the process consists of the Ents, Inters, and the environment ontology; the output of the process consists of Deps and EntDes. The specific algorithm can see [11, 17]. Figure 1 lists the text description and the graphics description of the two ticketing services.The description of the available service based on environment ontology.
(a)
(b)


## 2.3. Describing the Requirement Based on Environment Ontology

Define 6. The requirement description based on environment ontology can be seen as a service description without the service’s implementation. It is defined as a quintuple 〈name,Ents,Inters,Deps,EntDes〉, where the meaning of the elements is the same with that in Define 5.The process to describe the requirement is similar to that which depicts services. There are two results when the requirement is described: the requirement is described with only one option, or description with more than one option. The latter case needs more user constrain. Figure2 presents a specific illustration of the requirement, wherein the text description is presented in (a) and the effect of changes of the ticket in (b).The requirement description based on environment ontology.
(a)
(b)


## 3. Composing the Services Based on Environment Ontology

The task of web service composition is to search appropriate service and to arrange them in an appropriate manner. For the requirements which are depicted in the same level with the composition result, we present a method through decomposing the requirement to search the available service based on the service discovery method in [11]. The task is divided into three parts: decomposing the requirement, determining the relation between the services, and generating the composition service.


### 3.1. Decomposing the Requirement

The nature of the composition problem is that one problem cannot be addressed by a single service. Furthermore, our method is based on a requirement described in a formal detailed determine way. Thus we can acquire a composite service through a way which firstly decomposes the request into various parts and then composes services according to the requirement.


#### 3.1.1. Decomposing the Requirement Involving Multienvironment Entities

In this section, we decompose the requirement among environment entities and do not consider the internal description of the environment entity. The type of dependency among the environment entities can be classified into four classes: no dependence, dependent on the environment entities in one direction, and dependent on a symbol entity or autonomous entity, and dependent on each other. The corresponding decomposition algorithms are shown in Algorithms1, 2, 3, and 4.Algorithm 1:Decomposition algorithm among unrelated environmental entities.
DecByDep(Req, ReqSet) //input Req, output ReqSet
(1) while(Req.Ents≠ ⌀)
(2)e:= get (Req.Ents);
(3)  if(Relate(e) ≠ Req.Ents)//Relate(e) refer to a set include eand the entities depend on e
(4)Sete:= create (Relate(e)); //create a set include the elements in Relate(e)
(5)   ReqSet:= ReqSet∪ create(Sete, Req); //create(Sete, Req) is to acquire a requirement corresponding to the Set
(6)   Req:= Req.Remove(Sete); //Removing a requirement corresponding to the Set fromReq
(7)  end if
(8) end while
(9) ReqSet:= ReqSet∪ Req;Algorithm 2:Decomposition algorithm according to the dependent type between environmental entities.
DecByDepDir(Req, ReqSet)
(1) if(∃e((e∈ Req.Ents)∧∀dep(des ∈ Req.Deps∧(dep.se ≠e∨dep.te ≠e))))
(2)  ReqSet:= create (e, Req);
(3)  ReqSet:= ReqSet∪ DecByDep (Req.Ents-{e});
(4) end ifAlgorithm 3:Decomposition algorithm according to the type of environmental entities.
DecByEntTyp(Req, ReqSet)
(1) if(∃e(e∈ Req.Ents∧(type(e) = A∨type(e) = S)))
(2)  ReqSet:= create(e, Req);
(3)  ReqSet:= ReqSet∪DecByDep(Req.Ents-{e});
(4) end ifAlgorithm 4:Decomposition algorithm among the various environmental entities.
DecByEnt(Req, ReqSet)
(1) for(eache in Req.Ents){ // the number of environmental entities in Req.Ent greater than 1
(2)  ReqSet:= ReqSet∪ create(e, Req);
(3) end forThe elements inReqSet produced by Algorithm 1 have no dependence on other entities. Algorithm 1 satisfies consistency and has order of n2 time complexity where n is the number of entities in the requirement. Algorithm 2 decompose the requirement according to whether the interaction between the entities is in one direction. When multiple environment entities meet the conditions of the decomposition, the consistency can only satisfy all the decompositions with the same order. Its time complexity is the same with Algorithm 1. Algorithm 3 decomposes the requirement according to the type of the entity and has the same consistency and time complexity with Algorithm 2. Algorithm 4 is used when there is only message dependence among different entities. It can meet the consistency and its time complexity is equal to O(n) where n is the number of entities. Taking the requirement in Figure 2(a) as the input to present how to use these algorithms. The decomposition results are listed in Table 2.Table 2
Decomposition result of each step by Algorithms1–4.
Algorithm
Decomposition result
Algorithm1
{infobase, customer}, {hotel, creditcard, ticket, buyer}
Algorithm2
{infobase, customer}, {buyer}, {hotel}, {creditcard, ticket}
Algorithm3
{infobase}, {customer}, {buyer}, {hotel}, {creditcard, ticket}
Algorithm4
{infobase}, {customer}, {buyer}, {hotel}, {creditcard}, {ticket}


#### 3.1.2. Decomposing the Requirement Involving One Environment Entity

This section decomposes the requirement in one environment entity. Autonomous entity or symbolic entity having no constrains on its interaction can be directly divided into individual event or data by Algorithm7, and no further discussion is required. But in a causal entity, which is specified as a tree-like hierarchal state machine, there exists the dependence between a state and a tree-like hierarchal state machine, the dependence between a state and a finite state machine, and the dependence between states. The decomposition algorithms are shown in Algorithms  5, 6, and 7.Algorithm 5:Decomposition algorithm based on the structure of the hsm.
DecByHsmStr(Req, ReqSet) // input Req, which can be represented by a Tree-like hierarchal state machine(thsm), output ReqSet
(1) rootfsm:= GetRootfsm(Req);
(2) for(each subhsm of rootfsm)//subhsm.rootfsm.superstate∈ rootfsm
(3)  ReqSet:= ReqSet∪ create(subhsm, Req);
(4) end for
(5) ReqSet:= ReqSet∪ create(rootfsm, Req);Algorithm 6:Decomposition algorithm based on the key state.
DecByState(Req, ks, ReqSet)// input Req which can be represented by a finite state machine and ks, output ReqSet
(1) if((Req.State-(From(ks)∪ To(ks))) = ⌀) //Req.State is a set of the states in Req
(2)  From(ks):= From(ks)-{ks}; //From(ks) is a set of the states which ks can reach
(3)  To(ks):= To(ks)-{ks}; //To(ks) is a set of the states which can reach ks
(4) end if
(5) Req1 = create(Req.State-(From(ks)∪ To(ks)), Req);
(6) Req2:= create(From(ks)-To(ks), Req);
(7) Req3:= create(To(ks)-From(ks), Req);
(8) Req4:= create(From(ks)∩ To(ks), Req);
(9) ReqSet:= Req1∪ Req2 ∪ Req3 ∪ Req4;Algorithm 7:Decomposition algorithm based on the basic unit of the functionality.
DivByBeha(Req, ReqSet)// input Req which can a autonomous entity, a symbolic entity or afsm, output ReqSet
(1) for(eachb in Req)// b is the basic unit of the functionality, which can be a data, an event or transition
(2)  ReqSet:= create({b}, Req);
(3) end forAlgorithm5 decomposes the requirement containing a single hsm based on the couple between the finite state machines with the same state as an ancestor greater than the couple between the finite state machines with the different state as ancestor. The result of it is a set of the requirement each involving one hsm, and it can be called repeatedly several times until each includes only one fsm. Algorithm 5 satisfies consistency and has the time complexity O(f), where f, less than or equal to the number of fsm in the hsm, is the number of the requirements the decomposition produces.Algorithm6 decomposes the requirement containing a fsm based on the key state into more than one fsm. The key state can be specified by the user, the initial state of fsm, and the termination state of fsm or the parent state of the finite state machine contain one key state. It satisfies consistency and has the time complexity O(m2), where m is the number of states in the fsm.Algorithm7 can be used to decompose the requirement containing a single autonomous entity, a single symbolic entity, or an individual fsm based on the basic functionality unit of the requirement. It satisfies consistency and has the time complexity O(k), where k is the number of the basic functionalities.Taking the requirement in Figure2(b) as the input to present how to use Algorithms 5–7. The decomposition results are listed in Table 3.Table 3
Decomposition result of each step by the decomposition Algorithms5–7.
Algorithm
Inputs
Decomposition result
Algorithm5
Figure2(b)
{salecond}, {discountcond}, {deliverycond}
Algorithm6
Salecond in Figure2(b), ordered
{<available,…,ordered>, <ordered,…,sold>, <available,…,sold>}, {<sold,…,used>}
Algorithm7
Salecond in Figure2(b),
{<available,…,ordered>}, {<ordered,…,sold>}, {<available,…,sold>}, {<sold,…,used>}


### 3.2. Determining the Relations of the Services

The second task of web services composition is to determine the relations among services so that they can collaborate with each other for satisfying the request. To determine the relations among services is to derive the relationship between the various services based on the relations of the functionalities in the requirement description as well as the relations between the functionalities and services. The rules are given in this section in two layers: to determine the relations between the services among multienvironment entities and to determine the relations between services in one environment entity. They will help to use the service in more appropriate granularity, to reduce complexity of the external control flow, and to reduce the number of services in composition services and the communications overhead between the services.


#### 3.2.1. Determine the Service Relations among Multiple Environment Entities

If the requirement involving multienvironment entities needs to be accomplished by several services instead of one available service, we need to identify the relations between the services.Letinter and inters be, respectively, an interaction and a set of the interactions between environment entities and type(inter) the type of inter, whose value could be msg or val. R(inter) and S(inter), respectively, represent the environment entity receiving inter and that sending inter. |inters| and |co(inters)| represent the number of interactions in inters and the number of the messages in inters, respectively. Type(ent) denotes the type of the environment entity ent. Determining the relations between the services involving multienvironment entities are shown in Box 1.Box 1
Rule  1: (|inters|>1) ∧ (type(inters)=val) ∧  ∀inter((inter∈inters)→(R(inter)=ent ∨ S(inter)=ent)) ∧ (|con(inters)|=1) ∧  ∃inter
((inter∈inters) ∧ R(inter)=ent) => constrain(inters,inter) ∧ (R(inter)=ent).
Rule  2: (|inters|>1) ∧ (type(inters)=msg) ∧  ∀inter((inter∈inters)→(R(inter)=ent ∨ S(inter)=ent) ∧ (type(ent)=C)) => constrain
(inters,ent).
Rule  3: (|inters|>1) ∧ (type(inters)=msg) ∧  ∀inter((inter∈inters)→(R(inter)=ent ∨ S(inter)=ent) ∧ (type(Ent)=A)) => constrain
(inters, Ent).
Rule  4: (|inters|>1) ∧ (type(inters)=msg) ∧  ∀inter((inter∈inters)→(R(inter)=ent ∨ S(inter)=ent)) ∧ (type(ent)=S)) ∧ (|con(inters)|
=1)∧  ∃inter((inter∈inters) ∧ R(inter)=ent) => constrain(inters, inter) ∧ (R(inter)=ent).Rule  1 shows that when the multiple value interactions act on the same property of the same environment entity and wherein the received value interaction, the order of the value interactions is subject to the constraints of the received value interaction. Rule  2 shows that when the multiple message interactions act on one causal entity, the order of the message interactions is subject to the constraints of the causal entity. Rule  3 shows that when the multiple message interactions act on one autonomous entity, the order of the message interactions is subject to the constraints of the autonomous entity. Rule  4 shows that when the multiple message interactions act on one symbol entity and wherein one received interaction, the order of the message interactions is subject to the constraints of the received interaction. The time complexity of these rules is up toO(h2), where h is the number of interactions.Back to the example in Figure2(a), there is no interaction set to meet Rules  1 and 4. The result produced by Rule  2 is {〈{〈creditcard,pay,ticket〉,〈ticket,feedback,creditcard〉},ticket〉,〈{〈creditcard,pay,ticket〉, 〈ticket,feedback,credit-ard〉},creditcard〉}. The result produced by Rule  3 is {〈{〈customer,req,infobase〉,〈infobase,resp,customer〉},customer〉}.


#### 3.2.2. Determine the Service Relations in One Environment Entity

The task of this section focused on the causal entity described by the tree-like hierarchical state machine. We need to determine the relations among the functionalities which associate with the services acting on one causal entity. If the relation is between the services, we need to divide the functionality in some time. If the relation is in a service, we need to merge the functionalities into one service. According to the structure of the causal entity, this task can be divided into the transformation between the finite state machine and the transformation in a finite state machine.Lets a state, t and t′ a transition, Pres(s) a set of transitions which ending with s, and Sucs(s) a set of transitions which starting from s. Ser(t) and Sers(fsm), respectively, represent 〈t,ser〉∈funcs and 〈fsm,ser〉∈funcs. |set| indicates the number of elements in the set, such as |Pres(s)| which is the number of the transitions in Pres(s).init(fsm) and fin(fsm), respectively, denote the initial state and the final state of the fsm, and source(t) and target(t) represent the source state and the target state of the transition t. Merge(t,t′) denotes merging the two transitions, merge(t,fsm) denotes merging t and fsm, divide(ser,s) represents dividing the ser by s, divide(ser,fsm)represents dividing the ser on the boundary of fsm, move(ser,b) represents move of the b to the end of ser.(
1) The Transformation between the Finite State Machines. The transformation rules determining the relations of the services acting on a tree-like hierarchical state machine are shown in Box 2.Box 2
Rule  5: <s,fsm>∈Divs ∧ Sers(Pres(s))=(Sers(Sucs(s))) ∧|Sers(Sucs(s))|=1 ∧ (Sers(Sucs(init(fsm))) ≠ Sers(Pres(s)) ∨ Sers (Pres(fin
(fsm)))≠ Sers(Sucs(s))) = > Divide(Sers(Sucs(s)), s).
Rule  6: <s, fsm>∈ Divs ∧ Sers(Sucs(init(fsm))) ≠ Sers(Pres(s)) = > Divide(Sers(Sucs(init(fsm))) ∩ Sers(Pres(s)),fsm);  <s,fsm > ∈ Divs ∧
Sers(Pres(fin(fsm)))≠ Sers(Sucs(s)) => Divide(Sers(Pres (fin (fsm))) ∩ Sers(Sucs(s)), fsm).
Rule  7: <s,fsm >∈ Divs ∧ Sers(Pres(s))=Sers(Sucs(init(fsm))) ∧|Sers(Pres (s))|=1 => Merge(Pres(s), Sucs(init(fsm))); <s,fsm> ∈ Divs ∧
Sers (Sucs(s))=Sers(Pres(fin(fsm)))∧Sers(Sucs(s))|= 1 => Merge (Sucs(s), Pres (fin(fsm))).
Rule  8: Sers(Pres(s)) = Sers(fsm)∧|Sers(Pres(s))|= 1 ∧ ∀fsm(<s, fsm>∈Divs→(Sers(fsm) = Sers(Pres(s)))) => Merge(Pres(s),fsm);
(Sers (Sucs(s)) = Sers(fsm))∧|Sers(Sucs(s))|=1 ∧  ∀fsm(<s,fsm>∈Divs→ (Sers(fsm) = Sers (Sucs(s)))) = > Merge (Sucs(s), fsm).Rules  5 and 6 are used to determine, respectively, whether the service needs to be divided by the parent state of a finite state machine and whether the service acting on several finite state machines needs to be divided by the boundary of the finite state machine. Rules  7 and 8 can be used to merge the services acting on several finite state machines. All the rules of this section can be completed in polynomial timen which equals the number of states plus the number of transitions contained in the relevant fsm.(
2) The Transformation in a Finite State Machine. When a finite state machine associates with several services, we determine the relations between these services. Thus, our task in this section is to conclude the relations between the services according to the relation between transitions and the relation between the transition and the services. Before introducing the transform rules, we give some definitions firstly.Define 7. The branch entry point is denoted as BranchEntry(s)iff(|Sucs(s)|>1)∧(|Pres(s)|=1)∧(s∉To(s)).Define 8. The branch exit point is denoted as BranchEixt(e) if and only if the state e satisfies BranchEntry(b)∧((From(b)-(To(e)∪From(e)))=⌀)∧(∀s(s∈(To(e)∩From(b))→((From(b)-(To(s)∪From(s)))≠⌀))∧(e∉From(e)).The rules are shown in Box3. Rule  9 orients the sequence structure mergers the services in a state which has a single pervious transition and a single successor transition. Rules  10, 11, and 12 orient the choice structure, in which Rules  10 and 11 are used to merge the branches, and the Rule  12 is used to divide the service. Finally, Rules  13 and 14 orient the loop structure, in which Rule  13 is used at the entrance of the loop and Rule  14 is used at the exit of loop when one service acts on both in the loop and outside the loop. All of them belong to the polynomial time complexity class.Box 3
Rule  9: (|Pres(s)|=|Sucs(s)|=1) ∧ (Ser(Pres(s))=Ser(Sucs(s)))) => Merge(Pres(s),Sucs(s)).
Rule  10: BranchEntry(b)∧ BranchExit(e) ∧ (source(t) =source(t′)=b) ∧ (target(t) =target(t′)=e) ∧ (Ser(t)=Ser(t′)) => Merge(t, t′).
Rule  11: BranchEntry(b)∧|Sers(Sucs(b))|=1 => Move(Sers (Sucs(b)), b).
Rule  12: (|Pres(s)|>1 ∨ (|Sucs(s)|>1)) ∧ (Ser(Sucs(s))∩Ser(Pres(s))≠⌀) ∧ (|Sers(Sucs(s))|>1 ∨ (|Ser(Pres(s))|>1)) => Divide
(Ser(Sucs(s))∩Ser(Pres(s)),s).
Rule  13: s∈From(s) ∧ t∈Pres(s) ∧ source(t)∉From(source(t)) ∧ t′∈Pres(s) ∧ source(t′)∈From(source(t′)) ∧ Ser(t)=Ser(t′) => Divide
(Ser (t), s).
Rule  14: s∈From(s) ∧ ((t∈Sucs(s)∧target(t)∈From(target (t))) ∧ (t′∈Sucs(s) ∧ target(t′)∉From(target(t))) ∧ (Ser(t) =Ser(t′)) => Divide
(Ser(t),s).


### 3.3. Generating the Composition Service

The algorithm generating the composition service is shown in Algorithm8. It consists of two main phases. The first phase decomposes the requirement and discovery of the corresponding services in lines 1–11. The discovery process can be accomplished by the method proposed in [11] or some other service discovery or composition method. The second constructs the composition service and adjusts the relation between the services in lines 12–25.Algorithm 8:Composition algorithm based on environment ontology.
Input: Req //the requirement description based on environment ontology
Output: Ser //the composition service
(1) ReqSet:= {Req}; //ReqSet is a set of the requirement needing to be implemented by the services;
(2) while(ReqSet≠ ⌀)
(3)  for(each req in ReqSet)
(4)   ser:= discovery(req, SerSet);
(5)   if(ser≠ ⌀){//discovery(req, SerSet) successes
(6)    LabReq:= LabReq∪ label(req, ser); //label the req using the ser
(7)    continue;
(8)   end if
(9)   ReqSet:= ReqSet∪ dec(req, rule)-{req}; // dec() is used to decomposition the requirement
(10)end for
(11)end while
(12)Ser.{name, Ents, Deps, EntDes}:= req{name, Ents, Deps, EntDes}
(13)determin the Sers and Funcs of the Ser according to the req and LabReq;
(14)for(each ent in LabReq.Ent)
(15) if(ent.type = C&&|Sers(ent)| > 1)
(16)  for(each fsm in rhsm)
(17)    if(|Sers(fsm)| > 1&&hasproced(subFsm(fsm)))
(18)     adjust the Sers and Funcs of the Ser using the rule 9–14;
(19)     adjust the Sers and Funcs of the Ser using the rule 5–8;
(20)    end if
(21)   end for
(22)  end if
(23)  adjust the Sers and Funcs of the Ser using the rule 1–4;
(24)end for
(25)generateCDL(Ser);//generate the description in WS-CDL of the serAs that analyzed in previous part, the time complexity of Algorithms1–7 and the Rules  1–14 belongs a polynomial complexity. In Algorithm 8, the execution number of Algorithms 1–4 does not exceed the number of the environmental entities in the requirement, the execution number of Algorithms 5–7 does not exceed the total number of the basic behaviors, the execution number of the Rules  1–4 does not exceed the total number of the interaction, and the execution number of Rules  5–14 does not exceed the number of states. Thus, Algorithm 8 is a polynomial complexity algorithm. Part of the description of the composition service generated from the requirement in Figure 2 is shown in Figure 3.Figure 3
Part of the description of the composition service.


## 3.1. Decomposing the Requirement

The nature of the composition problem is that one problem cannot be addressed by a single service. Furthermore, our method is based on a requirement described in a formal detailed determine way. Thus we can acquire a composite service through a way which firstly decomposes the request into various parts and then composes services according to the requirement.


### 3.1.1. Decomposing the Requirement Involving Multienvironment Entities

In this section, we decompose the requirement among environment entities and do not consider the internal description of the environment entity. The type of dependency among the environment entities can be classified into four classes: no dependence, dependent on the environment entities in one direction, and dependent on a symbol entity or autonomous entity, and dependent on each other. The corresponding decomposition algorithms are shown in Algorithms1, 2, 3, and 4.Algorithm 1:Decomposition algorithm among unrelated environmental entities.
DecByDep(Req, ReqSet) //input Req, output ReqSet
(1) while(Req.Ents≠ ⌀)
(2)e:= get (Req.Ents);
(3)  if(Relate(e) ≠ Req.Ents)//Relate(e) refer to a set include eand the entities depend on e
(4)Sete:= create (Relate(e)); //create a set include the elements in Relate(e)
(5)   ReqSet:= ReqSet∪ create(Sete, Req); //create(Sete, Req) is to acquire a requirement corresponding to the Set
(6)   Req:= Req.Remove(Sete); //Removing a requirement corresponding to the Set fromReq
(7)  end if
(8) end while
(9) ReqSet:= ReqSet∪ Req;Algorithm 2:Decomposition algorithm according to the dependent type between environmental entities.
DecByDepDir(Req, ReqSet)
(1) if(∃e((e∈ Req.Ents)∧∀dep(des ∈ Req.Deps∧(dep.se ≠e∨dep.te ≠e))))
(2)  ReqSet:= create (e, Req);
(3)  ReqSet:= ReqSet∪ DecByDep (Req.Ents-{e});
(4) end ifAlgorithm 3:Decomposition algorithm according to the type of environmental entities.
DecByEntTyp(Req, ReqSet)
(1) if(∃e(e∈ Req.Ents∧(type(e) = A∨type(e) = S)))
(2)  ReqSet:= create(e, Req);
(3)  ReqSet:= ReqSet∪DecByDep(Req.Ents-{e});
(4) end ifAlgorithm 4:Decomposition algorithm among the various environmental entities.
DecByEnt(Req, ReqSet)
(1) for(eache in Req.Ents){ // the number of environmental entities in Req.Ent greater than 1
(2)  ReqSet:= ReqSet∪ create(e, Req);
(3) end forThe elements inReqSet produced by Algorithm 1 have no dependence on other entities. Algorithm 1 satisfies consistency and has order of n2 time complexity where n is the number of entities in the requirement. Algorithm 2 decompose the requirement according to whether the interaction between the entities is in one direction. When multiple environment entities meet the conditions of the decomposition, the consistency can only satisfy all the decompositions with the same order. Its time complexity is the same with Algorithm 1. Algorithm 3 decomposes the requirement according to the type of the entity and has the same consistency and time complexity with Algorithm 2. Algorithm 4 is used when there is only message dependence among different entities. It can meet the consistency and its time complexity is equal to O(n) where n is the number of entities. Taking the requirement in Figure 2(a) as the input to present how to use these algorithms. The decomposition results are listed in Table 2.Table 2
Decomposition result of each step by Algorithms1–4.
Algorithm
Decomposition result
Algorithm1
{infobase, customer}, {hotel, creditcard, ticket, buyer}
Algorithm2
{infobase, customer}, {buyer}, {hotel}, {creditcard, ticket}
Algorithm3
{infobase}, {customer}, {buyer}, {hotel}, {creditcard, ticket}
Algorithm4
{infobase}, {customer}, {buyer}, {hotel}, {creditcard}, {ticket}


### 3.1.2. Decomposing the Requirement Involving One Environment Entity

This section decomposes the requirement in one environment entity. Autonomous entity or symbolic entity having no constrains on its interaction can be directly divided into individual event or data by Algorithm7, and no further discussion is required. But in a causal entity, which is specified as a tree-like hierarchal state machine, there exists the dependence between a state and a tree-like hierarchal state machine, the dependence between a state and a finite state machine, and the dependence between states. The decomposition algorithms are shown in Algorithms  5, 6, and 7.Algorithm 5:Decomposition algorithm based on the structure of the hsm.
DecByHsmStr(Req, ReqSet) // input Req, which can be represented by a Tree-like hierarchal state machine(thsm), output ReqSet
(1) rootfsm:= GetRootfsm(Req);
(2) for(each subhsm of rootfsm)//subhsm.rootfsm.superstate∈ rootfsm
(3)  ReqSet:= ReqSet∪ create(subhsm, Req);
(4) end for
(5) ReqSet:= ReqSet∪ create(rootfsm, Req);Algorithm 6:Decomposition algorithm based on the key state.
DecByState(Req, ks, ReqSet)// input Req which can be represented by a finite state machine and ks, output ReqSet
(1) if((Req.State-(From(ks)∪ To(ks))) = ⌀) //Req.State is a set of the states in Req
(2)  From(ks):= From(ks)-{ks}; //From(ks) is a set of the states which ks can reach
(3)  To(ks):= To(ks)-{ks}; //To(ks) is a set of the states which can reach ks
(4) end if
(5) Req1 = create(Req.State-(From(ks)∪ To(ks)), Req);
(6) Req2:= create(From(ks)-To(ks), Req);
(7) Req3:= create(To(ks)-From(ks), Req);
(8) Req4:= create(From(ks)∩ To(ks), Req);
(9) ReqSet:= Req1∪ Req2 ∪ Req3 ∪ Req4;Algorithm 7:Decomposition algorithm based on the basic unit of the functionality.
DivByBeha(Req, ReqSet)// input Req which can a autonomous entity, a symbolic entity or afsm, output ReqSet
(1) for(eachb in Req)// b is the basic unit of the functionality, which can be a data, an event or transition
(2)  ReqSet:= create({b}, Req);
(3) end forAlgorithm5 decomposes the requirement containing a single hsm based on the couple between the finite state machines with the same state as an ancestor greater than the couple between the finite state machines with the different state as ancestor. The result of it is a set of the requirement each involving one hsm, and it can be called repeatedly several times until each includes only one fsm. Algorithm 5 satisfies consistency and has the time complexity O(f), where f, less than or equal to the number of fsm in the hsm, is the number of the requirements the decomposition produces.Algorithm6 decomposes the requirement containing a fsm based on the key state into more than one fsm. The key state can be specified by the user, the initial state of fsm, and the termination state of fsm or the parent state of the finite state machine contain one key state. It satisfies consistency and has the time complexity O(m2), where m is the number of states in the fsm.Algorithm7 can be used to decompose the requirement containing a single autonomous entity, a single symbolic entity, or an individual fsm based on the basic functionality unit of the requirement. It satisfies consistency and has the time complexity O(k), where k is the number of the basic functionalities.Taking the requirement in Figure2(b) as the input to present how to use Algorithms 5–7. The decomposition results are listed in Table 3.Table 3
Decomposition result of each step by the decomposition Algorithms5–7.
Algorithm
Inputs
Decomposition result
Algorithm5
Figure2(b)
{salecond}, {discountcond}, {deliverycond}
Algorithm6
Salecond in Figure2(b), ordered
{<available,…,ordered>, <ordered,…,sold>, <available,…,sold>}, {<sold,…,used>}
Algorithm7
Salecond in Figure2(b),
{<available,…,ordered>}, {<ordered,…,sold>}, {<available,…,sold>}, {<sold,…,used>}


## 3.1.1. Decomposing the Requirement Involving Multienvironment Entities

In this section, we decompose the requirement among environment entities and do not consider the internal description of the environment entity. The type of dependency among the environment entities can be classified into four classes: no dependence, dependent on the environment entities in one direction, and dependent on a symbol entity or autonomous entity, and dependent on each other. The corresponding decomposition algorithms are shown in Algorithms1, 2, 3, and 4.Algorithm 1:Decomposition algorithm among unrelated environmental entities.
DecByDep(Req, ReqSet) //input Req, output ReqSet
(1) while(Req.Ents≠ ⌀)
(2)e:= get (Req.Ents);
(3)  if(Relate(e) ≠ Req.Ents)//Relate(e) refer to a set include eand the entities depend on e
(4)Sete:= create (Relate(e)); //create a set include the elements in Relate(e)
(5)   ReqSet:= ReqSet∪ create(Sete, Req); //create(Sete, Req) is to acquire a requirement corresponding to the Set
(6)   Req:= Req.Remove(Sete); //Removing a requirement corresponding to the Set fromReq
(7)  end if
(8) end while
(9) ReqSet:= ReqSet∪ Req;Algorithm 2:Decomposition algorithm according to the dependent type between environmental entities.
DecByDepDir(Req, ReqSet)
(1) if(∃e((e∈ Req.Ents)∧∀dep(des ∈ Req.Deps∧(dep.se ≠e∨dep.te ≠e))))
(2)  ReqSet:= create (e, Req);
(3)  ReqSet:= ReqSet∪ DecByDep (Req.Ents-{e});
(4) end ifAlgorithm 3:Decomposition algorithm according to the type of environmental entities.
DecByEntTyp(Req, ReqSet)
(1) if(∃e(e∈ Req.Ents∧(type(e) = A∨type(e) = S)))
(2)  ReqSet:= create(e, Req);
(3)  ReqSet:= ReqSet∪DecByDep(Req.Ents-{e});
(4) end ifAlgorithm 4:Decomposition algorithm among the various environmental entities.
DecByEnt(Req, ReqSet)
(1) for(eache in Req.Ents){ // the number of environmental entities in Req.Ent greater than 1
(2)  ReqSet:= ReqSet∪ create(e, Req);
(3) end forThe elements inReqSet produced by Algorithm 1 have no dependence on other entities. Algorithm 1 satisfies consistency and has order of n2 time complexity where n is the number of entities in the requirement. Algorithm 2 decompose the requirement according to whether the interaction between the entities is in one direction. When multiple environment entities meet the conditions of the decomposition, the consistency can only satisfy all the decompositions with the same order. Its time complexity is the same with Algorithm 1. Algorithm 3 decomposes the requirement according to the type of the entity and has the same consistency and time complexity with Algorithm 2. Algorithm 4 is used when there is only message dependence among different entities. It can meet the consistency and its time complexity is equal to O(n) where n is the number of entities. Taking the requirement in Figure 2(a) as the input to present how to use these algorithms. The decomposition results are listed in Table 2.Table 2
Decomposition result of each step by Algorithms1–4.
Algorithm
Decomposition result
Algorithm1
{infobase, customer}, {hotel, creditcard, ticket, buyer}
Algorithm2
{infobase, customer}, {buyer}, {hotel}, {creditcard, ticket}
Algorithm3
{infobase}, {customer}, {buyer}, {hotel}, {creditcard, ticket}
Algorithm4
{infobase}, {customer}, {buyer}, {hotel}, {creditcard}, {ticket}


## 3.1.2. Decomposing the Requirement Involving One Environment Entity

This section decomposes the requirement in one environment entity. Autonomous entity or symbolic entity having no constrains on its interaction can be directly divided into individual event or data by Algorithm7, and no further discussion is required. But in a causal entity, which is specified as a tree-like hierarchal state machine, there exists the dependence between a state and a tree-like hierarchal state machine, the dependence between a state and a finite state machine, and the dependence between states. The decomposition algorithms are shown in Algorithms  5, 6, and 7.Algorithm 5:Decomposition algorithm based on the structure of the hsm.
DecByHsmStr(Req, ReqSet) // input Req, which can be represented by a Tree-like hierarchal state machine(thsm), output ReqSet
(1) rootfsm:= GetRootfsm(Req);
(2) for(each subhsm of rootfsm)//subhsm.rootfsm.superstate∈ rootfsm
(3)  ReqSet:= ReqSet∪ create(subhsm, Req);
(4) end for
(5) ReqSet:= ReqSet∪ create(rootfsm, Req);Algorithm 6:Decomposition algorithm based on the key state.
DecByState(Req, ks, ReqSet)// input Req which can be represented by a finite state machine and ks, output ReqSet
(1) if((Req.State-(From(ks)∪ To(ks))) = ⌀) //Req.State is a set of the states in Req
(2)  From(ks):= From(ks)-{ks}; //From(ks) is a set of the states which ks can reach
(3)  To(ks):= To(ks)-{ks}; //To(ks) is a set of the states which can reach ks
(4) end if
(5) Req1 = create(Req.State-(From(ks)∪ To(ks)), Req);
(6) Req2:= create(From(ks)-To(ks), Req);
(7) Req3:= create(To(ks)-From(ks), Req);
(8) Req4:= create(From(ks)∩ To(ks), Req);
(9) ReqSet:= Req1∪ Req2 ∪ Req3 ∪ Req4;Algorithm 7:Decomposition algorithm based on the basic unit of the functionality.
DivByBeha(Req, ReqSet)// input Req which can a autonomous entity, a symbolic entity or afsm, output ReqSet
(1) for(eachb in Req)// b is the basic unit of the functionality, which can be a data, an event or transition
(2)  ReqSet:= create({b}, Req);
(3) end forAlgorithm5 decomposes the requirement containing a single hsm based on the couple between the finite state machines with the same state as an ancestor greater than the couple between the finite state machines with the different state as ancestor. The result of it is a set of the requirement each involving one hsm, and it can be called repeatedly several times until each includes only one fsm. Algorithm 5 satisfies consistency and has the time complexity O(f), where f, less than or equal to the number of fsm in the hsm, is the number of the requirements the decomposition produces.Algorithm6 decomposes the requirement containing a fsm based on the key state into more than one fsm. The key state can be specified by the user, the initial state of fsm, and the termination state of fsm or the parent state of the finite state machine contain one key state. It satisfies consistency and has the time complexity O(m2), where m is the number of states in the fsm.Algorithm7 can be used to decompose the requirement containing a single autonomous entity, a single symbolic entity, or an individual fsm based on the basic functionality unit of the requirement. It satisfies consistency and has the time complexity O(k), where k is the number of the basic functionalities.Taking the requirement in Figure2(b) as the input to present how to use Algorithms 5–7. The decomposition results are listed in Table 3.Table 3
Decomposition result of each step by the decomposition Algorithms5–7.
Algorithm
Inputs
Decomposition result
Algorithm5
Figure2(b)
{salecond}, {discountcond}, {deliverycond}
Algorithm6
Salecond in Figure2(b), ordered
{<available,…,ordered>, <ordered,…,sold>, <available,…,sold>}, {<sold,…,used>}
Algorithm7
Salecond in Figure2(b),
{<available,…,ordered>}, {<ordered,…,sold>}, {<available,…,sold>}, {<sold,…,used>}


## 3.2. Determining the Relations of the Services

The second task of web services composition is to determine the relations among services so that they can collaborate with each other for satisfying the request. To determine the relations among services is to derive the relationship between the various services based on the relations of the functionalities in the requirement description as well as the relations between the functionalities and services. The rules are given in this section in two layers: to determine the relations between the services among multienvironment entities and to determine the relations between services in one environment entity. They will help to use the service in more appropriate granularity, to reduce complexity of the external control flow, and to reduce the number of services in composition services and the communications overhead between the services.


### 3.2.1. Determine the Service Relations among Multiple Environment Entities

If the requirement involving multienvironment entities needs to be accomplished by several services instead of one available service, we need to identify the relations between the services.Letinter and inters be, respectively, an interaction and a set of the interactions between environment entities and type(inter) the type of inter, whose value could be msg or val. R(inter) and S(inter), respectively, represent the environment entity receiving inter and that sending inter. |inters| and |co(inters)| represent the number of interactions in inters and the number of the messages in inters, respectively. Type(ent) denotes the type of the environment entity ent. Determining the relations between the services involving multienvironment entities are shown in Box 1.Box 1
Rule  1: (|inters|>1) ∧ (type(inters)=val) ∧  ∀inter((inter∈inters)→(R(inter)=ent ∨ S(inter)=ent)) ∧ (|con(inters)|=1) ∧  ∃inter
((inter∈inters) ∧ R(inter)=ent) => constrain(inters,inter) ∧ (R(inter)=ent).
Rule  2: (|inters|>1) ∧ (type(inters)=msg) ∧  ∀inter((inter∈inters)→(R(inter)=ent ∨ S(inter)=ent) ∧ (type(ent)=C)) => constrain
(inters,ent).
Rule  3: (|inters|>1) ∧ (type(inters)=msg) ∧  ∀inter((inter∈inters)→(R(inter)=ent ∨ S(inter)=ent) ∧ (type(Ent)=A)) => constrain
(inters, Ent).
Rule  4: (|inters|>1) ∧ (type(inters)=msg) ∧  ∀inter((inter∈inters)→(R(inter)=ent ∨ S(inter)=ent)) ∧ (type(ent)=S)) ∧ (|con(inters)|
=1)∧  ∃inter((inter∈inters) ∧ R(inter)=ent) => constrain(inters, inter) ∧ (R(inter)=ent).Rule  1 shows that when the multiple value interactions act on the same property of the same environment entity and wherein the received value interaction, the order of the value interactions is subject to the constraints of the received value interaction. Rule  2 shows that when the multiple message interactions act on one causal entity, the order of the message interactions is subject to the constraints of the causal entity. Rule  3 shows that when the multiple message interactions act on one autonomous entity, the order of the message interactions is subject to the constraints of the autonomous entity. Rule  4 shows that when the multiple message interactions act on one symbol entity and wherein one received interaction, the order of the message interactions is subject to the constraints of the received interaction. The time complexity of these rules is up toO(h2), where h is the number of interactions.Back to the example in Figure2(a), there is no interaction set to meet Rules  1 and 4. The result produced by Rule  2 is {〈{〈creditcard,pay,ticket〉,〈ticket,feedback,creditcard〉},ticket〉,〈{〈creditcard,pay,ticket〉, 〈ticket,feedback,credit-ard〉},creditcard〉}. The result produced by Rule  3 is {〈{〈customer,req,infobase〉,〈infobase,resp,customer〉},customer〉}.


### 3.2.2. Determine the Service Relations in One Environment Entity

The task of this section focused on the causal entity described by the tree-like hierarchical state machine. We need to determine the relations among the functionalities which associate with the services acting on one causal entity. If the relation is between the services, we need to divide the functionality in some time. If the relation is in a service, we need to merge the functionalities into one service. According to the structure of the causal entity, this task can be divided into the transformation between the finite state machine and the transformation in a finite state machine.Lets a state, t and t′ a transition, Pres(s) a set of transitions which ending with s, and Sucs(s) a set of transitions which starting from s. Ser(t) and Sers(fsm), respectively, represent 〈t,ser〉∈funcs and 〈fsm,ser〉∈funcs. |set| indicates the number of elements in the set, such as |Pres(s)| which is the number of the transitions in Pres(s).init(fsm) and fin(fsm), respectively, denote the initial state and the final state of the fsm, and source(t) and target(t) represent the source state and the target state of the transition t. Merge(t,t′) denotes merging the two transitions, merge(t,fsm) denotes merging t and fsm, divide(ser,s) represents dividing the ser by s, divide(ser,fsm)represents dividing the ser on the boundary of fsm, move(ser,b) represents move of the b to the end of ser.(
1) The Transformation between the Finite State Machines. The transformation rules determining the relations of the services acting on a tree-like hierarchical state machine are shown in Box 2.Box 2
Rule  5: <s,fsm>∈Divs ∧ Sers(Pres(s))=(Sers(Sucs(s))) ∧|Sers(Sucs(s))|=1 ∧ (Sers(Sucs(init(fsm))) ≠ Sers(Pres(s)) ∨ Sers (Pres(fin
(fsm)))≠ Sers(Sucs(s))) = > Divide(Sers(Sucs(s)), s).
Rule  6: <s, fsm>∈ Divs ∧ Sers(Sucs(init(fsm))) ≠ Sers(Pres(s)) = > Divide(Sers(Sucs(init(fsm))) ∩ Sers(Pres(s)),fsm);  <s,fsm > ∈ Divs ∧
Sers(Pres(fin(fsm)))≠ Sers(Sucs(s)) => Divide(Sers(Pres (fin (fsm))) ∩ Sers(Sucs(s)), fsm).
Rule  7: <s,fsm >∈ Divs ∧ Sers(Pres(s))=Sers(Sucs(init(fsm))) ∧|Sers(Pres (s))|=1 => Merge(Pres(s), Sucs(init(fsm))); <s,fsm> ∈ Divs ∧
Sers (Sucs(s))=Sers(Pres(fin(fsm)))∧Sers(Sucs(s))|= 1 => Merge (Sucs(s), Pres (fin(fsm))).
Rule  8: Sers(Pres(s)) = Sers(fsm)∧|Sers(Pres(s))|= 1 ∧ ∀fsm(<s, fsm>∈Divs→(Sers(fsm) = Sers(Pres(s)))) => Merge(Pres(s),fsm);
(Sers (Sucs(s)) = Sers(fsm))∧|Sers(Sucs(s))|=1 ∧  ∀fsm(<s,fsm>∈Divs→ (Sers(fsm) = Sers (Sucs(s)))) = > Merge (Sucs(s), fsm).Rules  5 and 6 are used to determine, respectively, whether the service needs to be divided by the parent state of a finite state machine and whether the service acting on several finite state machines needs to be divided by the boundary of the finite state machine. Rules  7 and 8 can be used to merge the services acting on several finite state machines. All the rules of this section can be completed in polynomial timen which equals the number of states plus the number of transitions contained in the relevant fsm.(
2) The Transformation in a Finite State Machine. When a finite state machine associates with several services, we determine the relations between these services. Thus, our task in this section is to conclude the relations between the services according to the relation between transitions and the relation between the transition and the services. Before introducing the transform rules, we give some definitions firstly.Define 7. The branch entry point is denoted as BranchEntry(s)iff(|Sucs(s)|>1)∧(|Pres(s)|=1)∧(s∉To(s)).Define 8. The branch exit point is denoted as BranchEixt(e) if and only if the state e satisfies BranchEntry(b)∧((From(b)-(To(e)∪From(e)))=⌀)∧(∀s(s∈(To(e)∩From(b))→((From(b)-(To(s)∪From(s)))≠⌀))∧(e∉From(e)).The rules are shown in Box3. Rule  9 orients the sequence structure mergers the services in a state which has a single pervious transition and a single successor transition. Rules  10, 11, and 12 orient the choice structure, in which Rules  10 and 11 are used to merge the branches, and the Rule  12 is used to divide the service. Finally, Rules  13 and 14 orient the loop structure, in which Rule  13 is used at the entrance of the loop and Rule  14 is used at the exit of loop when one service acts on both in the loop and outside the loop. All of them belong to the polynomial time complexity class.Box 3
Rule  9: (|Pres(s)|=|Sucs(s)|=1) ∧ (Ser(Pres(s))=Ser(Sucs(s)))) => Merge(Pres(s),Sucs(s)).
Rule  10: BranchEntry(b)∧ BranchExit(e) ∧ (source(t) =source(t′)=b) ∧ (target(t) =target(t′)=e) ∧ (Ser(t)=Ser(t′)) => Merge(t, t′).
Rule  11: BranchEntry(b)∧|Sers(Sucs(b))|=1 => Move(Sers (Sucs(b)), b).
Rule  12: (|Pres(s)|>1 ∨ (|Sucs(s)|>1)) ∧ (Ser(Sucs(s))∩Ser(Pres(s))≠⌀) ∧ (|Sers(Sucs(s))|>1 ∨ (|Ser(Pres(s))|>1)) => Divide
(Ser(Sucs(s))∩Ser(Pres(s)),s).
Rule  13: s∈From(s) ∧ t∈Pres(s) ∧ source(t)∉From(source(t)) ∧ t′∈Pres(s) ∧ source(t′)∈From(source(t′)) ∧ Ser(t)=Ser(t′) => Divide
(Ser (t), s).
Rule  14: s∈From(s) ∧ ((t∈Sucs(s)∧target(t)∈From(target (t))) ∧ (t′∈Sucs(s) ∧ target(t′)∉From(target(t))) ∧ (Ser(t) =Ser(t′)) => Divide
(Ser(t),s).


## 3.2.1. Determine the Service Relations among Multiple Environment Entities

If the requirement involving multienvironment entities needs to be accomplished by several services instead of one available service, we need to identify the relations between the services.Letinter and inters be, respectively, an interaction and a set of the interactions between environment entities and type(inter) the type of inter, whose value could be msg or val. R(inter) and S(inter), respectively, represent the environment entity receiving inter and that sending inter. |inters| and |co(inters)| represent the number of interactions in inters and the number of the messages in inters, respectively. Type(ent) denotes the type of the environment entity ent. Determining the relations between the services involving multienvironment entities are shown in Box 1.Box 1
Rule  1: (|inters|>1) ∧ (type(inters)=val) ∧  ∀inter((inter∈inters)→(R(inter)=ent ∨ S(inter)=ent)) ∧ (|con(inters)|=1) ∧  ∃inter
((inter∈inters) ∧ R(inter)=ent) => constrain(inters,inter) ∧ (R(inter)=ent).
Rule  2: (|inters|>1) ∧ (type(inters)=msg) ∧  ∀inter((inter∈inters)→(R(inter)=ent ∨ S(inter)=ent) ∧ (type(ent)=C)) => constrain
(inters,ent).
Rule  3: (|inters|>1) ∧ (type(inters)=msg) ∧  ∀inter((inter∈inters)→(R(inter)=ent ∨ S(inter)=ent) ∧ (type(Ent)=A)) => constrain
(inters, Ent).
Rule  4: (|inters|>1) ∧ (type(inters)=msg) ∧  ∀inter((inter∈inters)→(R(inter)=ent ∨ S(inter)=ent)) ∧ (type(ent)=S)) ∧ (|con(inters)|
=1)∧  ∃inter((inter∈inters) ∧ R(inter)=ent) => constrain(inters, inter) ∧ (R(inter)=ent).Rule  1 shows that when the multiple value interactions act on the same property of the same environment entity and wherein the received value interaction, the order of the value interactions is subject to the constraints of the received value interaction. Rule  2 shows that when the multiple message interactions act on one causal entity, the order of the message interactions is subject to the constraints of the causal entity. Rule  3 shows that when the multiple message interactions act on one autonomous entity, the order of the message interactions is subject to the constraints of the autonomous entity. Rule  4 shows that when the multiple message interactions act on one symbol entity and wherein one received interaction, the order of the message interactions is subject to the constraints of the received interaction. The time complexity of these rules is up toO(h2), where h is the number of interactions.Back to the example in Figure2(a), there is no interaction set to meet Rules  1 and 4. The result produced by Rule  2 is {〈{〈creditcard,pay,ticket〉,〈ticket,feedback,creditcard〉},ticket〉,〈{〈creditcard,pay,ticket〉, 〈ticket,feedback,credit-ard〉},creditcard〉}. The result produced by Rule  3 is {〈{〈customer,req,infobase〉,〈infobase,resp,customer〉},customer〉}.


## 3.2.2. Determine the Service Relations in One Environment Entity

The task of this section focused on the causal entity described by the tree-like hierarchical state machine. We need to determine the relations among the functionalities which associate with the services acting on one causal entity. If the relation is between the services, we need to divide the functionality in some time. If the relation is in a service, we need to merge the functionalities into one service. According to the structure of the causal entity, this task can be divided into the transformation between the finite state machine and the transformation in a finite state machine.Lets a state, t and t′ a transition, Pres(s) a set of transitions which ending with s, and Sucs(s) a set of transitions which starting from s. Ser(t) and Sers(fsm), respectively, represent 〈t,ser〉∈funcs and 〈fsm,ser〉∈funcs. |set| indicates the number of elements in the set, such as |Pres(s)| which is the number of the transitions in Pres(s).init(fsm) and fin(fsm), respectively, denote the initial state and the final state of the fsm, and source(t) and target(t) represent the source state and the target state of the transition t. Merge(t,t′) denotes merging the two transitions, merge(t,fsm) denotes merging t and fsm, divide(ser,s) represents dividing the ser by s, divide(ser,fsm)represents dividing the ser on the boundary of fsm, move(ser,b) represents move of the b to the end of ser.(
1) The Transformation between the Finite State Machines. The transformation rules determining the relations of the services acting on a tree-like hierarchical state machine are shown in Box 2.Box 2
Rule  5: <s,fsm>∈Divs ∧ Sers(Pres(s))=(Sers(Sucs(s))) ∧|Sers(Sucs(s))|=1 ∧ (Sers(Sucs(init(fsm))) ≠ Sers(Pres(s)) ∨ Sers (Pres(fin
(fsm)))≠ Sers(Sucs(s))) = > Divide(Sers(Sucs(s)), s).
Rule  6: <s, fsm>∈ Divs ∧ Sers(Sucs(init(fsm))) ≠ Sers(Pres(s)) = > Divide(Sers(Sucs(init(fsm))) ∩ Sers(Pres(s)),fsm);  <s,fsm > ∈ Divs ∧
Sers(Pres(fin(fsm)))≠ Sers(Sucs(s)) => Divide(Sers(Pres (fin (fsm))) ∩ Sers(Sucs(s)), fsm).
Rule  7: <s,fsm >∈ Divs ∧ Sers(Pres(s))=Sers(Sucs(init(fsm))) ∧|Sers(Pres (s))|=1 => Merge(Pres(s), Sucs(init(fsm))); <s,fsm> ∈ Divs ∧
Sers (Sucs(s))=Sers(Pres(fin(fsm)))∧Sers(Sucs(s))|= 1 => Merge (Sucs(s), Pres (fin(fsm))).
Rule  8: Sers(Pres(s)) = Sers(fsm)∧|Sers(Pres(s))|= 1 ∧ ∀fsm(<s, fsm>∈Divs→(Sers(fsm) = Sers(Pres(s)))) => Merge(Pres(s),fsm);
(Sers (Sucs(s)) = Sers(fsm))∧|Sers(Sucs(s))|=1 ∧  ∀fsm(<s,fsm>∈Divs→ (Sers(fsm) = Sers (Sucs(s)))) = > Merge (Sucs(s), fsm).Rules  5 and 6 are used to determine, respectively, whether the service needs to be divided by the parent state of a finite state machine and whether the service acting on several finite state machines needs to be divided by the boundary of the finite state machine. Rules  7 and 8 can be used to merge the services acting on several finite state machines. All the rules of this section can be completed in polynomial timen which equals the number of states plus the number of transitions contained in the relevant fsm.(
2) The Transformation in a Finite State Machine. When a finite state machine associates with several services, we determine the relations between these services. Thus, our task in this section is to conclude the relations between the services according to the relation between transitions and the relation between the transition and the services. Before introducing the transform rules, we give some definitions firstly.Define 7. The branch entry point is denoted as BranchEntry(s)iff(|Sucs(s)|>1)∧(|Pres(s)|=1)∧(s∉To(s)).Define 8. The branch exit point is denoted as BranchEixt(e) if and only if the state e satisfies BranchEntry(b)∧((From(b)-(To(e)∪From(e)))=⌀)∧(∀s(s∈(To(e)∩From(b))→((From(b)-(To(s)∪From(s)))≠⌀))∧(e∉From(e)).The rules are shown in Box3. Rule  9 orients the sequence structure mergers the services in a state which has a single pervious transition and a single successor transition. Rules  10, 11, and 12 orient the choice structure, in which Rules  10 and 11 are used to merge the branches, and the Rule  12 is used to divide the service. Finally, Rules  13 and 14 orient the loop structure, in which Rule  13 is used at the entrance of the loop and Rule  14 is used at the exit of loop when one service acts on both in the loop and outside the loop. All of them belong to the polynomial time complexity class.Box 3
Rule  9: (|Pres(s)|=|Sucs(s)|=1) ∧ (Ser(Pres(s))=Ser(Sucs(s)))) => Merge(Pres(s),Sucs(s)).
Rule  10: BranchEntry(b)∧ BranchExit(e) ∧ (source(t) =source(t′)=b) ∧ (target(t) =target(t′)=e) ∧ (Ser(t)=Ser(t′)) => Merge(t, t′).
Rule  11: BranchEntry(b)∧|Sers(Sucs(b))|=1 => Move(Sers (Sucs(b)), b).
Rule  12: (|Pres(s)|>1 ∨ (|Sucs(s)|>1)) ∧ (Ser(Sucs(s))∩Ser(Pres(s))≠⌀) ∧ (|Sers(Sucs(s))|>1 ∨ (|Ser(Pres(s))|>1)) => Divide
(Ser(Sucs(s))∩Ser(Pres(s)),s).
Rule  13: s∈From(s) ∧ t∈Pres(s) ∧ source(t)∉From(source(t)) ∧ t′∈Pres(s) ∧ source(t′)∈From(source(t′)) ∧ Ser(t)=Ser(t′) => Divide
(Ser (t), s).
Rule  14: s∈From(s) ∧ ((t∈Sucs(s)∧target(t)∈From(target (t))) ∧ (t′∈Sucs(s) ∧ target(t′)∉From(target(t))) ∧ (Ser(t) =Ser(t′)) => Divide
(Ser(t),s).


## 3.3. Generating the Composition Service

The algorithm generating the composition service is shown in Algorithm8. It consists of two main phases. The first phase decomposes the requirement and discovery of the corresponding services in lines 1–11. The discovery process can be accomplished by the method proposed in [11] or some other service discovery or composition method. The second constructs the composition service and adjusts the relation between the services in lines 12–25.Algorithm 8:Composition algorithm based on environment ontology.
Input: Req //the requirement description based on environment ontology
Output: Ser //the composition service
(1) ReqSet:= {Req}; //ReqSet is a set of the requirement needing to be implemented by the services;
(2) while(ReqSet≠ ⌀)
(3)  for(each req in ReqSet)
(4)   ser:= discovery(req, SerSet);
(5)   if(ser≠ ⌀){//discovery(req, SerSet) successes
(6)    LabReq:= LabReq∪ label(req, ser); //label the req using the ser
(7)    continue;
(8)   end if
(9)   ReqSet:= ReqSet∪ dec(req, rule)-{req}; // dec() is used to decomposition the requirement
(10)end for
(11)end while
(12)Ser.{name, Ents, Deps, EntDes}:= req{name, Ents, Deps, EntDes}
(13)determin the Sers and Funcs of the Ser according to the req and LabReq;
(14)for(each ent in LabReq.Ent)
(15) if(ent.type = C&&|Sers(ent)| > 1)
(16)  for(each fsm in rhsm)
(17)    if(|Sers(fsm)| > 1&&hasproced(subFsm(fsm)))
(18)     adjust the Sers and Funcs of the Ser using the rule 9–14;
(19)     adjust the Sers and Funcs of the Ser using the rule 5–8;
(20)    end if
(21)   end for
(22)  end if
(23)  adjust the Sers and Funcs of the Ser using the rule 1–4;
(24)end for
(25)generateCDL(Ser);//generate the description in WS-CDL of the serAs that analyzed in previous part, the time complexity of Algorithms1–7 and the Rules  1–14 belongs a polynomial complexity. In Algorithm 8, the execution number of Algorithms 1–4 does not exceed the number of the environmental entities in the requirement, the execution number of Algorithms 5–7 does not exceed the total number of the basic behaviors, the execution number of the Rules  1–4 does not exceed the total number of the interaction, and the execution number of Rules  5–14 does not exceed the number of states. Thus, Algorithm 8 is a polynomial complexity algorithm. Part of the description of the composition service generated from the requirement in Figure 2 is shown in Figure 3.Figure 3
Part of the description of the composition service.


## 4. The Implementation and Analysis

To achieve the service composition described in this paper, the six modules need to be implemented. The first one is used to refine the request into the requirement based on the environment ontology. The second is used to describe a service based on the environment ontology. The third is to decompose the requirement. The fourth is used to discovery and matching of the service. The fifth is to determine the relationship between the services, and the final is to generate the composition result described in the appropriate manner. The main interface and the composition result of a prototype we implemented in java are shown in Figure4.Figure 4
The main interface and the composition result of a prototype.The required times the algorithms run on our prototype platform are shown in Figure5. It is consistent with our previous analysis. The reasons the proposed method could improve the efficiency of the composition can be concluded as follows.(i)
The first one is the enrichment of the composition knowledge introduced by the description of the requirement and the service based on environment ontology. The former limits the position of the service to be used, while the latter can help to eliminate some paths that are just possible in theory but not allowed by the domain knowledge or the user.(ii)
The second lies in the hierarchal structure. The position and the order to decompose the requirement to some extent determine the location and the priority to composite the services. The decomposition also helps to improve degree of parallelism.(iii)
Thirdly, this approach can support the composition of the composite service and behavior services.The figure of composition time.
(a)
The time to decompose the requirement among environment entities
(b)
The time to decompose the requirement in an environment entity
(c)
The time to transform the service model
(d)
The time to compose servicesBesides these, this work contributes to expand the range of the service description into the problem supporting to introduce the more precise Qos constrain in the future work, and wherein some work can be used to other domains such as the rules determining the relationship between services which can be used for processing control flow.


## 5. Related Work

This section briefly discusses the relationships between our works with the existing service composition approaches. The differences between ours with others are illustrated in Table4, where I, O, P, E, B and “—” denote input, output, precondition, effect, behavior, and unspecified content explicitly, respectively. Instead of focusing on the description of Web services of their own, we give attention to the effects imposed by the services on their environment entities and state that all the capabilities are based on the environment entities, whose characteristics and interconnections are observable and applicable during service discovery and composition. And for the character of requirement decomposition and discovery, the approach can adapt for composing different type services by changing the discovery constrains.Table 4
Comparison of various approaches to service composition.
Approach
Service description
Requirement description
Description object
Service type
Approaches
Others
Complexity
Berardi et al. [12]
Behavior
B
Service
B, A
Behavior equivalence
Single community
Exponential
McIlraith and Son [2]
IOPEB
OE
—
A
Agent
User constrain
—
Bultan et al. [13]
B
B
Conversation
B, A
Behavior equivalence
—
—
Roman et al. [14]
IOPEB
IOPEB
Service, goal
—
Mediator
Domain ontology
Exponential
Maamar et al. [5]
IOB
O
Context
A
Agent
Multilevel context
—
Sirin et al. [8]
IOPE
OE
—
A
Complex service-based decomposition
Complex and simple service
—
Brogi et al. [6]
IOB
O
—
C, A
Graph constructing and coloring
—
Exponential
Arpinar et al. [7]
IO
IO
Domain, service and process
A
Matching and searching
—
—
Liang et al. [15]
Qos
Qos
Service
A
Matching
Constrain
Polynomial
Tao et al. [16]
IO, Qos
IO, Qos
Service, task
A
Decomposition and discovery
Qos
Polynomial
Cai [17, 18]
IOPEB
IOPEB
Environment
A, B, C
Decomposition and transformation
Environment ontology
Polynomial


## 6. Conclusion and Future Work

In order to solve the problems of the service composition efficient in the single problem domain, this paper proposes the methods to generate requirement, to describe the service, and to compose the service based on environment ontology. Compared with the existing efforts in this field, this work advances the state of art in the following aspects.(i)
More efficient composition: the domain knowledge described in environment ontology and the method to decompose the requirement not only can reduce the size of the problem, but also help to improve the degree of parallelism.(ii)
More types of services composition: the method to determine the service relationship according to the problem model not only can support a composition of atomic services but also support the composition of the composite services and the behavior services.(iii)
Optimized composition model: the method adjusting the relation between the services based on the composition structure provides the foundation to schedule localization and optimizes the execution model.In addition, the prototype implementation can generate a composition result described by the WS-CDL. This paper presents an ongoing work for tackling the issue of automatic service composition. Subsequent work will extend the ontology for supporting the service composition in various domains and the multilevel problem. And then we will enhance the service composition procedure for considering the nonfunctional concerns and the correctness of the composite services. Moreover, as stated in [1], the transaction and security must be considered if we would use it in reality. Finally, some other application domains will be researched to use this method.



---

*Source: 521094-2013-12-10.xml*