Semantic Web Service Composition based on Graph Search
Author(s): Liana Ţucăr, Paul Diac
Full text: submitted version
Abstract: Abstract. In Web Service Composition, services or APIs from multiple and independent providers are combined to create new functionality. Web Service Challenges have formalized the problem at a series of events where the community competed with various solutions. The composition problem has been incrementally extended adding more expressiveness and since 2006 the semantic aspect was addressed by the use of ontologies for service parameter description. In this paper, we propose a polynomial-time algorithm based on graph search, that solves the 2008 challenge. The algorithm uses a heuristic to address the NP-Hard problem of optimizing the number of services selected. Experimental results show that our solution is a several times faster and generates shorter compositions on all evaluation tests compared with all winning solutions of the competition. Also it is up to 50 times faster and very close to generate shortest compositions on the tests, compared with the solution published in 2011, that generates optimal compositions.
Keywords: Service Composition; Semantic Web Services; Ontologies; Polynomial Time; Graph Search; Heuristic; Dynamic Scoring
Review 1 (by anonymous reviewer)
(RELEVANCE TO ESWC) The community around services is currently focusing on APIs. The matching challenge has not been a topics for almost 10 year now.... The presented work is not directly relevant to ESWC (NOVELTY OF THE PROPOSED SOLUTION) The proposed approach need to be applied to a more suitable use case/application scenario. (CORRECTNESS AND COMPLETENESS OF THE PROPOSED SOLUTION) There are some important details missing. The service formalism are not discussed and there is direct jump only to service inputs and outputs. (EVALUATION OF THE STATE-OF-THE-ART) There is not section on state-of-the-art (DEMONSTRATION AND DISCUSSION OF THE PROPERTIES OF THE PROPOSED APPROACH) some details missing (REPRODUCIBILITY AND GENERALITY OF THE EXPERIMENTAL STUDY) There are no links to the implementation. (OVERALL SCORE) The author present an approach for service matching based on graph search, applied on the Semantic web service matching challenge from 2008. The idea for the algorithm is interesting, however, the application area, in my opinion, is completely unsuitable. There is a reason why we discontinued the matching challenge. The service community has evolved and current problems are much more focused around APIs, syntax and purely textual descriptions, heterogeneity, REST etc. I am not really sure that the presented work would be relevant for the ESWC community. Furthermore, the impact is questionable (the solution is to a problem that was current 10 years ago). My recommendation would be to apply the algorithm in an area that is more current, has more impact potential and would be more exciting for the community. Detailed comments are provided below: 1) Clearly formulate the big picture problem statement and the contributions in the introduction. Currently this comes a bit late 2) Why is a web service defined only by the input and output parameters??? What about the operations? It does not make sense todo compositions if the parameters of inputs and outputs match but the operations are not useful. This is described in a confusing way. Strongly suggest to rephrase the beginning of section 2.2 3) page 4. Why does calling a service not change the station the system? To the contrary, most service definitions, which are widely accepted, prerequisite that there is a change of state of the system/the world. you need to explain what you mean and why that is a valid assumption. Why is this assumption important for the algorithm? 4) Before you jump to the web service parameters you should describe what formalisms you are deadline with. Currently, it looks like you are missing important details 5) Section 3.1 how can you assume that the taxonomy, repository of services and client requests are known? Because of the matching challenge setup? How would you make the approach generally applicable? This is quite a strong assumption, especially the taxonomy part. ----------------- I do appreciate the comments of the authors provided in the rebuttal letter. In fact, the authors raise here new issues regard the position of the work in terms of general scope. I do believe that the presented algorithm has potential, however, I am also convinced that selected use case for applicability is completely unsuitable for demonstrating advantages and potential.
Review 2 (by anonymous reviewer)
(RELEVANCE TO ESWC) Semantic Web Service Composition is a well-related problem for ESWC. (NOVELTY OF THE PROPOSED SOLUTION) The complexity issue is a hard problem. The approach is novel. (CORRECTNESS AND COMPLETENESS OF THE PROPOSED SOLUTION) It seems correct for the authors' proof. (EVALUATION OF THE STATE-OF-THE-ART) It is compared with state-of-art. (DEMONSTRATION AND DISCUSSION OF THE PROPERTIES OF THE PROPOSED APPROACH) It is a very interesting approach. (REPRODUCIBILITY AND GENERALITY OF THE EXPERIMENTAL STUDY) It seems the experiments can be reproduced. (OVERALL SCORE) The paper proposes a way to address the NP-Hard problem of optimizing the number of semantic web services selected for composition. Experimental results show that proposed approach is a several times faster compared with all winning solutions of WSC 2008 challenges.
Review 3 (by anonymous reviewer)
(RELEVANCE TO ESWC) The paper makes emphasis neither in the use of semantics nor in the use of ontologies or any of the Semantic Web stack components (NOVELTY OF THE PROPOSED SOLUTION) The Benchmark used in the paper is from 2008, ten years old. (CORRECTNESS AND COMPLETENESS OF THE PROPOSED SOLUTION) Both the problem and the solution are presented in a good way, although there are small details, especially in the algorithm (See the Overall Evaluation description). (EVALUATION OF THE STATE-OF-THE-ART) No related work is presented (DEMONSTRATION AND DISCUSSION OF THE PROPERTIES OF THE PROPOSED APPROACH) The problem definition and algorithms are well presented. The evaluation shows in a proper way the improvement of the approach compared to the benchmark 2008 (REPRODUCIBILITY AND GENERALITY OF THE EXPERIMENTAL STUDY) They use a Benchmark from 2008 and provide all the algorithms to implement their approach. This gives a good degree of reproducibility. However, the source code mentioned in the paper is not provided. (OVERALL SCORE) The paper presents a new algorithm to solve the problem of automatic Web Service Composition. The algorithm is composed by two main phases: Construction and Reduction Phase. Using a prepossessing phase the algorithm reduces the complexity of the problem from NP-Hard to O(1) time complexity. The algorithm is evaluated against a Benchmark from 2008 getting good results against the winners of challenges of 2008. The following are the strong points of the papers: 1. It provides a good and clear motivation example 2. Definition of the problem is well presented, and the formalization makes the next step clear. 3. The Evaluation is based on concrete Benchmark 2008 making the work easy to reproduce. 4. All the required algorithms are presented so anyone may implement the approach. However, the paper has the following weak points: 1. The paper tackles neither a problem in the semantic web community nor presents how the semantic technology facilities or solves the problem of Web Service composition, this makes the contribution weak for this conference. 2. No related work is present, this is one of the main problems of the paper, and without related work, it is not clear how this approach is different from others. Why was this section not included? 3. Too many global parameters will make hard to parallelize the algorithm. 4. No source code is presented, this would, of course, make even easier to reproduce the evaluation 5. The results of the Algorithm 1 are not used anywhere, am I missing something? 6. In Algorithm 2 Line 7 the function findSolution() should receive parameters right? The work is well presented and it seems the algorithm is a good contribution in solving the Web Service Composition problem. However, my main concern with this paper is that it makes emphasis neither in the use of semantics nor in the use of ontologies or any of the Semantic Web stack components.
Metareview by Ruben Verborgh
The reviewers cite multiple concerns with this submission, especially with regard to the timeliness—and thus relevance—of this research to the ESWC audience. A state of the art section, which can offer an explanation of the limitations of existing solutions and the observed differences in the evaluation, is crucially missing. While your results are good indeed, the novelty, innovativeness, and adequacy of the techniques is less clear. In conclusion, we believe that this submission is not a good fit for the conference.