J. Cent. South Univ. Technol. (2011) 18: 1169-1177

DOI: 10.1007/s11771-011-0819-y

Automatic Web services composition algorithm based on optimal matching

WANG Jun-li(王俊丽)¹, DING Zhi-jun(丁志军)², HOU Yu-bing(侯玉兵)³

1. Engineering Research Center for Enterprise Digital Technology, Ministry of Education,

Tongji University, Shanghai 200092, China;

2. Key Laboratory of Embedded System and Service Computing, Ministry of Education,

Tongji University, Shanghai 200092, China;

3. Shanghai Branch, China Information Technology Designing and Consulting Institute, Shanghai 200050, China

? Central South University Press and Springer-Verlag Berlin Heidelberg 2011

Abstract: A novel layered method was proposed to solve the problem of Web services composition. In this method, services composition problem was formally transformed into the optimal matching problem of every layer, then optimal matching problem was modeled based on the hypergraph theory, and solved by computing the minimal transversals of the hypergraph. Meanwhile, two optimization algorithms were designed to discard some useless states at the intermediary steps of the composition algorithm. The effectiveness of the composition method was tested by a set of experiments, in addition, an example regarding the travel services composition was also given. The experimental results show that this method not only can automatically generate composition tree whose leaf nodes correspond to services composition solutions, but also has better performance on execution time and solution quality by adopting two proposed optimization algorithms.

Key words: Web services; services composition; optimal matching; hypergraph theory

1 Introduction

Web services were considered as “self-contained, self-describing, modular applications that can be published, located, and invoked across the Web. Once a Web service was deployed, other applications (and other Web services) can discover and invoke the deployed service” [1-2]. Nowadays, a large and rapidly growing number of heterogeneous services are being developed by different organizations to provide various application services over the Internet. Thus, the ability to efficiently select and integrate them is an important step towards the development of Web service applications. In particular, if no single Web service can satisfy the functionality required by the user, there is an opportunity to combine the existing services together in order to fulfill the request. This trend has triggered a considerable number of research efforts on the composition of Web services both in academia and industry [3-5].

To date, the Web services composition is still a highly complex task, and is already beyond human capability to deal with the entire process manually [6-7]. Therefore, building composite Web service with an automated tool is critical. So far, many methods and techniques have been developed for this purpose, in which various formalisms are used such as finite state machines [8], Petri nets [9-10], and graph theory [11-15]. Moreover, these approaches are usually automatic or semi-automatic. Herein, the graph-theory related services composition techniques are mainly focused, whose current research efforts mostly include two important aspects: directed graph and hypergraph.

Recently, many composition techniques have been discussed based on the directed graph. Presented by THAKKAR et al [11], Proteus is an automatic composition system, which uses a forward chaining algorithm to generate an initial composition plan and then a backward optimization method to optimize the plan. OH et al [12] described a best-first graph search algorithm to transform Web services composition issues into a directed graph shortest path problem. Furthermore, LI et al [13] demonstrated a dynamic composition method that first generated a composition graph, utilizing concept relations, and then searched the graph to find a satisfying path. These methods are based on directed graph, which can provide composition solutions for some services composition problems. However, when inputs of a service can be matched with outputs of several services instead of a single service, it is hard for a directed graph to model such problem. Consequently, this type of services composition problem cannot be solved by directed graph based methods.

On the other hand, a hypergraph based composition method can effectively model the problem mentioned above. But until now, a hypergraph-based algorithm proposed by BENATALLAH et al [15] has only been successfully applied to the services matching process by computing hypergraph minimal transversals. For this reason, based on the tackling of the services matching problem [15], a Web services composition method based on hypergraph is proposed in this work.

Next, some substantial differences between the method [15] and the proposed method are discussed. First, the problems they dealt with are different. Namely, one is designed for services matching, and the other is intended for the services composition. During the process of composition, there exist many points where matching between the services is required, such that the matching process is just one component in the composition process. Furthermore, the flexible matching [15] and the optimal matching in this work are also different, that is, the flexible matching between a service request and service advertisements does not require exact matching of parameters, while the optimal matching is based on a complete matching. In this work, the complete matching means that the output set of a services matching should subsume all requested outputs, and a complete matching is called optimal if no subset of the matching is a complete matching. Above all, this work aims to design an automatic services composition method, whereas the method in Ref.[15] focuses on the matching method. Since the matching process is just one internal step of the composition, the proposed method in this work can be taken as an extension of the method in Ref.[15].

2 Web services composition problem

Some basic definitions regarding the Web services composition problem are given. Next, the related background of hypergraph theory is introduced, and also a hypergraph model for optimal services matching problem is constructed. Finally, a scenario of travel services is given to illustrate the optimal services matching and composition problems.

2.1 Basic definitions

To begin with, every service is abstracted as an action independent of its platform and language, and can be described by a set of input and output parameters. Similarly, service request is abstracted and described by its input and output parameters.

Definition 1: A Web service S is defined as a tuple (I(S), O(S)), where I(S) is a set of input parameters of the service S, and O(S) is a set of output parameters of the service S.

Definition 2: A Web service request Q is defined as a tuple (I(Q), O(Q)), where I(Q) is a set of input parameters of the service request Q, and O(Q) is a set of output parameters of the service request Q.

In addition, it should be noted that both the syntactic matching and semantic matching are considered in this work. Therefore, every input or output parameter corresponds to a concept of a domain ontology. Here, the method proposed by PAOLUCCI in Ref.[16] is used to solve the semantic matching between two concepts. Accordingly, the equivalent semantically is defined as follows.

Definition 3: Let a and b be two concepts. If they are the same concepts or equivalent concepts in the domain ontology, they are equivalent semantically, denoted as a≡b.

Given a set of services and a request, the services composition problem can be defined as the process of combining and linking some available services to create a new service which satisfies the given request. As a result, a solution to composition problem consists of a set of selected services that are organized with a certain order. Note that there may be a sequence relation between two selected services. For example, if an input of Service 1 is matched with an output of another Service 2, then Service 2 is called as a direct antecedent service of Service 1. Since the direct antecedent is transitive, the antecedent relation between two services is defined next.

Definition 4: Let Φ={S₁, S₂, …, S_k} be a set of Web services, S_i and S_j be two services in Φ. If there exist iI(S_j), oO(S_i), and i≡o, then S_i is called a direct antecedent service of S_j, denoted as S_i→S_j. Moreover, if there exists a sequence S_k1, S_k2, …, S_kp in Φ, satisfied by S_i→S_k1, S_k1→S_k2, …, S_kp→S_j, then S_i is called an antecedent service of S_j, denoted as S_i→S_j.

In most cases, for a given services composition problem, there may be several solutions that meet the request. Next, a formal definition of a services composition solution is given.

Definition 5: Let Φ={S₁, S₂, …, S_k} be a set of Web services. Q is a service request. Let Ω be a subset of Φ such that: O(Ω)={o| oO(S_j) and S_jΩ}, I(Ω)={i| iI(S_j), iO(Ω) and S_jΩ}. Ω is a services composition solution of the request Q with respect to Φ if the following items hold: (1) I(Q)I(Ω); (2) O(Q) O(Ω); (3) for any S_jΩ, S_j is not antecedent service of itself.

As shown above, there are three necessary conditions for the services composition solution. Specifically, Condition 1 is a constraint to the inputs of Ω which must be included in the inputs of Q. While, Condition 2 is important to guarantee that the solution Ω can meet the request Q. Furthermore, Condition 3 is necessary to guarantee no circle in the solution.

In this definition, it should be specially explained about the input set of Ω, I(Ω), that is, the outputs of Ω are excluded from the set of I(Ω). In this way, antecedent relationship between services in Ω can be effectively used.

2.2 Optimal matching and hypergraph

The optimal matching problem in this work is solved by constructing its corresponding hypergraph and then computing its minimal transversals. Accordingly, some basic definitions related with optimal matching are given. Moreover, a construction method of hypergraph model for this problem is introduced.

Definition 6: Let Q be a service request, Φ a Web service set, and Ψ a subset of Φ, O(Ψ)={o| oO(S_j) and S_jΨ} such that O(Q)O(Ψ), where Ψ is called a complete matching of Q with respect to Φ. Ψ is called a optimal matching of Q with Φ if no subset of Ψ is a complete matching of Q with Φ. The set of the optimal matchings of Q with Φ is called the optimal matching cluster.

Let us recall some necessary definitions regarding hypergraphs and its minimal transversal [15].

Definition 7: A hypergraph H is a pair (V, E), where V is a set of vertices and E is a set of edges, an edge simply being a subset of V.

Definition 8: Let H=(V, E) be a hypergraph. A set WV is a transversal of H if for each eE, W∩e≠?. A transversal W is minimal if no proper subset W′ of W is a transversal. The set of the minimal transversals of a hypergraph H is denoted as T(H).

Next, how to construct a hypergraph model for the optimal matching cluster problem is described.

Definition 9: Let Q be service request, Φ a Web service set, and as a subset of Φ, Ψ is a complete matching, such that for any service S_lΨ, O(Q)∩O(S_l)≠ ?. A hypergraph H_Ψ=(V, E) is built, where Ψ is vertex set, and each edge E_i={S_j｜for any o_iO(Q), if S_jΨ and o_iO(S_j)}.

Clearly, for the optimal matching cluster problem, every complete matching solution corresponds to a transversal of H_Ψ. What’s more, every minimal transversal is an optimal matching solution. Consequently, the optimal matching cluster problem is reduced to the computation of the set of minimal transversals of hypergraph H_Ψ.

2.3 Illustrating example

To clearly illustrate the optimal services matching and composition problem, a scenario of travel services is introduced.

In this case, there is a set of related travel services Φ={S₁, S₂, S₃, S₄, S₅, S₆, S₇, S₈}, and their names, input and output parameters are given in Table 1. In addition, two requests are given in Table 2.

Let us first consider a service request Q₁ in Table 2 and a subset of Φ in Table 1: Ψ={S₃, S₄, S₅, S₆}, where each of them has at least one common output with Q₁. Moreover, it is obvious that all the outputs of Q₁ are subsumed in the output set of Ψ, so that Ψ is a complete services matching of the request Q₁. Then, according to Definition 9, an associated hypergraph H=(V, E) is generated, where vertex set is V={S₃, S₄, S₅, S₆}, and edge set is E={E₁, E₂, E₃}={{S₃},{S₅, S₆},{S₃, S₄, S₅}}. And the hypergraph H is depicted in Fig.1.

Table 1 Example of travel services and their input and output parameters

Table 2 Service requests and their input and output parameters

Fig.1 Hypergraph generated for request Q₁ with respect to Φ

According to Definition 8, the minimal transversals of hypergraph H can be computed as T(H) ={{S₃, S₅}, {S₃, S₆}}. As noted above, T(H) is also the optimal matching cluster of Q₁ with respect to Φ. Furthermore, Ψ′={S₃, S₅} satisfies the three conditions in Definition 5. Therefore, Ψ′ is a services composition solution of Q₁ with respect to Φ. But for Ψ″={S₃, S₆}, the condition I(Q₁)I(Ψ″) does not hold, so Ψ″ is not a composition solution.

Let us take the service request Q₂ in Table 2 as an example. {{S₇}, {S₈}} is the optimal matching cluster of Q₂ with respect to Φ. However, for every service set {S₇} and {S₈}, neither of them hold Condition 1 in Definition 5, so both of them are not the services composition solution. But obviously, a service set {S₃, S₅} is the optimal matching cluster of {S₇}, moreover {S₁, S₂} is the optimal matching cluster of {S₃, S₅}. Consequently, it can be noticed that a combination of these service sets Ω={S₁, S₂, S₃, S₅, S₇} is a services composition solution of Q₂ with respect to Φ.

To sum up, an illustration of how to solve Web services composition problem by stepwise solving optimal matching problem is given in this example. Based on this consideration, an automatic composition algorithm is designed.

3 Automatic layered composition algorithm

3.1 Basic idea

Starting from an initial root node of a layered composition tree corresponding to outputs of the request, the composition algorithm determines all its child nodes by an optimal matching algorithm and two optimization algorithms. Then, every child node is taken as a root node, and the above step is repeated until a composition tree is generated.

Here, with the optimal matching algorithm, a set of optimal matching solutions are obtained by solving minimal transversals of the hypergraph. In addition, a circle checking optimization algorithm is used to avoid the occurrence of circle invocation, while a prune optimization algorithm is used to discard all redundant services.

Let us give a simple explanation of the following important symbols used in the algorithms:

CT represents a composition tree generated by the proposed composition algorithm, whose every node i is labeled by a tuple (M_i, P_i, G_i, U_i) to record some information related with the optimal matching solution and also direct antecedent relation, where M_i is a service set corresponding to an optimal matching solution of M_j, and node j is the father of node i; P_i is a union of M_l, and node l is any node on the path from root node to node i in the CT; G_i is a set of direct antecedent relations between M_i and M_j, and node j is father of node i; U_i is a union of G_l, and node l is any node on the path from root node to node i in the CT.

a and b point to initial and terminated nodes of every layer in the process of generating CT, respectively.

3.2 Service composition algorithm

The proposed composition algorithm is listed in Table 3, which constructs a composition tree CT by stepwise matching. First, the root node of the CT is initialized, and then every layer of CT is generated by one time of iteration execution (lines 5-29). Furthermore, in the iteration process, for every node j, the required inputs for matching are computed. If node j is the root, the required inputs are the outputs of the request. Otherwise, the required inputs are computed by line 7. Moreover, if the required input is empty, then it is indicated that inputs of node j can be matched by inputs of the request. Consequently, the current node j is labeled as a live leaf corresponding to a composition solution (lines 8-9). Otherwise, find out the services which share some common outputs with the required inputs (line 10), and compute the optimal matching solution cluster with these services (line 13). After that, for every optimal matching solution, according to optimization algorithms, judge whether it is reserved or discarded. If the solution is reserved as a child node of the node j, its information of (M_m+k, P_m+k, G_m+k, U_m+k) is recorded (lines 16-23). Repeat the above steps until the composition tree CT is generated finally.

Table 3 Proposed services composition algorithm

3.3 Optimal matching algorithm

As an important step of the proposed composition algorithm, namely the line 13 in Table 3, an optimal matching algorithm is designed to obtain a set of optimal matching solutions by computing minimal transversals of the hypergraph.

A classical algorithm for computing minimal transversals of a hypergraph was presented in Refs.[17-18]. The algorithm is incremental and works in n steps, where n is the number of edges of the hypergraph. Starting from an empty set of transversals, the method first explores each edge of the hypergraph, with one edge in each step. Next, a set of candidate transversals is generated by computing all the possible unions of the candidates generated in the previous step and each vertex in the considered edge. At each step, the non-minimal candidate transversals are pruned [15].

Based on this algorithm, an optimal matching algorithm (OptimalMatch) is given in Table 4, including constructing a hypergraph for the optimal matching problem, computing all the minimal transversals of the hypergraph, and recording antecedent relations between matching services which are useful for the final generation of a composition solution.

Table 4 Optimal matching algorithm—OptimalMatch(S′, S, I(S))

3.4 Optimization algorithms

In the above optimal matching process, multiple optimal matching solutions are generated, but some of them may cause circle or redundance. Therefore, two optimization algorithms are designed to delete those invalid solutions. In addition, the other necessary solutions are reserved as the nodes of new layer in the CT.

When a candidate solution (node i) is judged whether it should be reserved or discarded, firstly it is compared with the existing nodes in current CT. Obviously, circle may occur when node i has common services with one of its ancestor node, while node i will be a redundance if it is included by another existing node in current CT.

In the view of above, for facilitating the discussion of the given node i, the current CT is divided into three separated regions, as shown in Fig.2. Region R1 includes all the nodes on the path from root node to the node i, that is, the ancestor nodes set of node i. Region R2 is the child nodes set of all nodes in R1 except the nodes in R1 and node i. And Region R3 consists of the rest nodes in CT. Next, three different cases are considered regarding three regions.

Fig.2 Three separated regions of composition tree

First, for a node j in Region R1, if its M_j shares several common elements with M_i of the node i, that is, some services are repeated in the path from root node to node i, then circular invocation of services may occur. In this circumstance, whether existing dead lock or not should be judged. Based on antecedent relation set, a circle checking algorithm (CircleChecking) is devised, as shown in Table 5. If there exists a dead lock, the algorithm will return a value to the composition algorithm (corresponding to line 16 in Table 3), and node i is discarded (NodeDelete). Otherwise, node i is reserved but the services occurring again are deleted from M_i (corresponding to line 19 in Table 3), because all antecedent services of these reoccurred services have been recorded in the antecedent relation set of its father node (ElementDelete).

For example, in Fig.3(a) U_l=? and R_k={S₂→S₁, S₃→S₂} are supposed, and the repeated occurrence of service S₂ will not cause circular invocation, so node i are reserved but S₂ is deleted from M_i. While in Fig.3(b) U_l=? and R_k={S₃→S₁, S₂→S₂} are supposed, and it is obvious that there exists a circle, so at this time node i is discarded.

Table 5 Circle checking algorithm—CircleChecking (U_l, R_k)

Fig.3 Two examples in circle checking process: (a) No circular invocation; (b) Circular invocation

Further, to judge whether the node i is redundance, every node j in Region R2 is considered. In this case, if there is a node j in Region R2, and P_iP_j holds, then for every leaf node i′ of node i, there exists a leaf node j′ of node j, such that  Consequently, the node i is a redundance, and should be discarded at the intermediary steps of generating CT. For this purpose, a prune algorithm is given in Table 6.

Table 6 Prune algorithm—Prune (CT, P, Z, j, m)

Finally, for a node k in Region R3, such that P_iP_k, there must exist a node j in Region R2 as the ancestor node of node k, such that P_kP_j. Consequently, P_iP_j holds. According to the above prune algorithm, node i has been discarded compared with node j. So, the nodes in Region R3 do not need to be considered.

To conclude, given a node i, every node in Region R1 should be considered by the circle checking algorithm in Table 5 to judge whether node i would cause dead lock, while on the other hand, every node in Region R2 should be considered by the prune algorithm in Table 6 to judge whether node i is a redundance.

4 Performance evaluation and experiments

4.1 Case study: travel scenario

In the travel services scenario, a service set Φ={S₁, S₂, S₃, S₄, S₅, S₆, S₇, S₈} is given in Table 1, and the request Q₂ is given in Table 2. For this problem, executing steps of composition algorithm are as follows, and a final generated tree CT is shown in Fig.4.

Initialize CT including root node 0, and its labeled information (M_i, P_i, G_i, U_i) is null.

First of all, take outputs of the request Q₂ {TravelReservation} as a required input for matching. According to the optimal matching algorithm in Table 4, optimal matchings of {TravelReservation} are solved, and there are two solutions {S₇} and {S₈}. Then, optimization algorithms are applied to judge whether these two solutions should be reserved. Take {S₇} as an example, the circle checking algorithm compares it with its ancestor node 0. Clearly, there is no common service, and since there is no other node in CT, it is clear that  {S₇} is not a redundance. Therefore, {S₇} is reserved and added in CT as node 1, and also its labeled information (M_i, P_i, G_i, U_i) is recorded. Likewise, {S₈} is also reserved and added in CT as node 2.

Then, take node 1 and node 2 as father nodes, the above steps are repeated. For example, required inputs of {S₇} in node 1 are {TrainTicket, HotelReservation}, then its optimal matchings are obtained through the matching algorithm as {S₃, S₅} and {S₃, S₆}. According to the optimization algorithms, both of them are reserved as node 3 and node 4 in the CT, respectively. In the same way, other nodes in the third layer can be generated.

In the fourth layer, when node 3 is considered, its optimal matchings are {S₁, S₂, S₃} and {S₁, S₂, S₄}. Further, in optimization process, {S₁, S₂, S₃} is found out to include a reoccurred service S₃ but this reoccurred service will not cause circle, so {S₁, S₂} is reserved as M₇ of node 7 where S₃ is deleted. For another optimal matching {S₁, S₂, S₄}, it is obvious that its related service set includes all related services of node 7. Therefore, it is discarded by prune algorithm which is marked with a broken rectangle in Fig.4. In the same way, other nodes in the fourth layer can be generated.

Since all required inputs of nodes 7, 8, 9, and 10 are null, they are labeled as live leafs, finally the algorithm stops. The generated composition tree CT by the proposed services composition algorithm is shown in Fig.4.

According to information labeled on the leaf nodes, obviously, the composition solutions are P₇={S₁, S₂, S₃, S₅, S₇}, P₈={S₁, S₂, S₃, S₆, S₇}, P₉={S₁, S₂, S₄, S₅, S₈}, P₁₀={S₁, S₂, S₄, S₆, S₈}. What’s more, take node 7 as an example, according to U₇={(7,0), (5,7), (1,3), (2,3), (3,5), (3,7)}, its services composition path is shown in Fig.5.

4.2 Experimental results and performance analysis

In order to evaluate the effectiveness and speed of the proposed composition algorithm, several experiments are carried out. Also, the role of the optimization phrase in reducing the number of solutions generated is assessed. The evaluation is done on a notebook with a 1.73 GHz Intel Centrino processor and 512 MB RAM. For all the experiments, the number of available services is varied from 200 to 1 000. Input and output parameters of a Web service are generated randomly with each service up to five inputs and five outputs.

As stated above, there are two optimization techniques adopted in the composition algorithm, i.e., circle checking and prune algorithm. Note that for circle checking there are two possible strategies, such as NodeDelete and ElementDelete. Hence, in the optimization process, there are three strategies: NodeDelete, ElementDelete and Prune. The NodeDelete strategy is required here to guarantee that the algorithm is able to stop when facing cycle in execution process, while the other two strategies are optional.

Therefore, in the following experiments, four flavors of the composition algorithm are tested, as shown in Table 7, and later performance analysis is conducted by comparing these four algorithms. Due to the fact that service parameters are generated randomly, each result is averaged over 50 runs.

Fig.4 Generated composition tree CT for request Q₂

Fig.5 Services composition path with respect to node 7

Table 7 Four flavors of composition algorithm

In the first set of experiments, for all the four algorithms, the execution time of generating a composition tree is compared, as shown in Fig.6. It can be seen that with the number of services increasing, the compute time increases too. Moreover, it is clear that A1 and A3 yield comparable performance, yet A3 is slightly better owing to the strategy of ElementDelete, which can delete some reoccurred services in the intermediate steps. As compared with A1, A2 reduces composition time significantly by using prune algorithm. Furthermore, by adopting these two optimization techniques, A4 has the best performance. It is also noticed that as the number of services increases, A4 shows more performance gain, which indicates its good scalability.

In the second set of experiments, given three composition problems with each comprised of 50, 250 and 500 available services, the impact of these strategies on the quality of the generated composition solution set is assessed by analyzing the properties of final composition tree, such as the number of leaf nodes (NoLN), depth of the tree (DoT) and breadth of the tree (BoT). Here, BoT is the largest number of nodes in a layer of the tree. And the experimental results are listed in Table 8.

By these experiments, it is found out that A1 generates a set of all possible composition solutions. However, it is evident that there are many duplicated solutions, and also some solutions are subsumed by other solutions. From the NoLN column in Table 8, it can be seen that the number of solutions of A3 is slightly less than that of A1. This is due to the fact that some solutions are deleted by ElementDelete. In addition, although A2 largely reduces the number by cutting some branches, it still shares some common solutions. Obviously, A4 has the least number of solutions. From the DoT column, it can be known that ElementDelete strategy in A3 has much more effect on the depth of the composition tree; while from the NoLN column, Prune strategy in A2 has much more impact on breadth of the tree. As a result, by adopting these two strategies, A4 has the best composition performance.

Fig.6 Comparison of execution time for four composition algorithms

Table 8 Comparison of quality of generated solutions

5 Conclusions

1) A hypergraph based automatic services composition algorithm is presented. The algorithm generates a composition tree, whose every leaf nodes correspond to a feasible composition solution.

2) Three major related algorithms are devised to realize the services composition, including a hypergraph based optimal matching algorithm, and two optimization algorithms—CircleChecking algorithm and Prune algorithm.

3) A prototype system is developed to evaluate the composition algorithm and also implement services composition in practice.

References

[1] PRAKASH J, RAJA V. Evaluating Web service composition methods with the help of a business application [J]. International Journal of Engineering Science and Technology, 2010, 2(7): 2931-2935.

[2] MAAMAR Z, SHENG Z, BENATALLAH B. Towards a conversation-driven composition of Web services [J]. Web Intelligence and Agent Systems, 2004, 2(2): 145-150.

[3] MILANOVIC N, MALEK M.Current solutions for Web service composition [J]. IEEE Internet Computing, 2004, 8(6): 51-59.

[4] ARDAGNA D, PERNICI B. Adaptive service composition in flexible processes [J]. IEEE Transaction on Software Engineering, 2007, 33(6): 369-384.

[5] MEDJAHED B, BOUGUETTAYA A.A multilevel composability model for semantic Web services [J]. IEEE Transaction on Knowledge and Data Engineering, 2005, 17(7): 954-968.

[6] LINS F, JUNIOR J, ROSA N. Adaptive web service composition [J]. ACM Sigsoft Software Engineering Notes, 2007, 32(4): 6-14.

[7] YU Qi, LIU Xu-min, BOUGUETTAYA A, MEDJAHED B, Deploying and managing Web services: Issues, solutions, and directions [J]. The International Journal on Very Large Data Bases, 2008, 17(3): 537-572.

[8] BERARDI D, CALVANESE D, GIUSEPPE G D. Automatic composition of e-Services [C]// Proceedings of the First International Conference on Service-Oriented Computing. Trento: Springer, 2003: 43-58.

[9] TAEJONG Y, BUHWAN J, HYUNBO C. A Petri Nets based functional validation for services composition [J]. Expert Systems with Applications: An International Journal, 2010, 37(5): 3768-3776.

[10] DING Zhi-jun, WANG Jun-li, JIANG Chang-jun. An approach for synthesis Petri Nets for modeling and verifying composite Web service [J]. Journal Information Science and Engineering, 2008, 24(5): 1309-1328.

[11] THAKKAR S, KNOBLOCK C A, AMBITE J L, SHAHABI C. Dynamically composing Web services from on-line sources [C]// Proceedings of the AAAI-02 Workshop on Intelligent Service Integration. Edmonton, Alberta, Canada: AAAI Press, 2002: 18-25.

[12] OH S C, ON B W, LARSON E J, Lee D. BF*: Web services discovery and composition as graph search problem [C]// Proceedings of the 2005 IEEE International Conference on e-Technology, e-Commerce and e-Service. Hong Kong, China: IEEE Computer Society, 2005: 784-786.

[13] LI Man, WAND Da-zhi, DU Xiao-yong, WANG Shan. Dynamic composition of Web services based on domain ontology [J]. Chinese Journal of Computers, 2005, 28(4): 644-650. (in Chinese)

[14] Hou Li-shan, Jin Zhi, Wu Bu-dan. Modeling and verifying Web services driven by requirements: An ontology based approach [J]. Science in China (Series E), 2006, 36(10): 1189-1219. (in Chinese)

[15] BENATALLAH B, HACID M, LEGER A. On automating Web services discovery [J]. The International Journal on Very Large Data Bases, 2005, 14(1): 84-96.

[16] PAOLUCCI M, KAWMURA T, PAYNE T, SYCARA K. Semantic matching of Web service capabilities [C]// Proceedings of the International Semantic Web Conference. Sardinia, Italia: Springer Verlag, 2002: 333-347.

[17] EITER T, GOTTLOB G. Identifying the minimal transversals of a hypergraph and related problems [J]. SIAM Journal on Computing, 1995, 24(6): 1278-1304.

[18] BERGE C. Hypergraphs: Combinatorics of finite sets [M]. Amsterdam: North-Holland Elsevier Publication, 1989: 1-268.

(Edited by YANG Bing)

Foundation item: Project(2010CB328101) supported by the National Basic Research Program of China; Project(2009AA01Z401) supported by the National High Technology Research and Development Program of China; Projects(60803032, 90818023) supported by the National Natural Science Foundation of China; Projects(09510701300, 09JC1414200, 09DZ1120403) supported by the Shanghai Science and Technology Commission, China; “Shu Guang” Project(10SG23) supported by Shanghai Municipal Education Commission and Shanghai Education Development Foundation, China; Project(09QA1405800) supported by Shanghai Science and Technology Commission Rising-Star Program, China; Project(NCET-10-0598) supported by Program for New Century Excellent Talents in Chinese University

Received date: 2010-04-30; Accepted date: 2010-10-21

Corresponding author: DING Zhi-jun, Associate Professor, PhD; Tel: +86-21-65982455; E-mail: zhijun-ding@hotmail.com