Chinese Journal of Computers   Full Text
Title	Analyzing Compatibility and Similarity of Web Service Processes
Authors	LI Xi-Tong FAN Yu-Shun
Address	(Department of Automation, Tsinghua University, Beijing 100084)
Year	2009
Issue	No.12(2429—2437)
Abstract &   Background	Abstract Service composition and substitution are key research issues in Service-Oriented Computing(SOC). Among them, analyzing compatibility and similarity of Web service processes are two closely-related issues and of great importance. This paper models Web service processes using Colored Petri nets (CPN) and presents the definitions of correctness and compatibility of Web service processes. Then, the notion of well-structuredness of Web services is developed. The paper proves that all reachable final markings of a composite service composed by well-structured services are correct. Based on the compatibility analysis, the paper develops the definition of similarity of Web service processes in order to investigate service substitution. It is concluded that substituting a service in a composition can be performed independent of the context as long as the new service is similar to the substituted one. There is thus no need to verify the substituted service composition again. The paper develops an algorithm for verifying similarity between two services. The results and algorithm are used to improve the existing methods of service composition verification and service substitution. Keywords Web service; service composition; service substitution; compatibility; similarity Background Service Oriented Computing (SOC) is a new computing paradigm in the area of software engineering and architecture. Service composition and substitution are key research issues in SOC, among which analyzing compatibility and similarity of Web service processes are two closely-related issues and of great importance to both the academia and industry. A few approaches have been developed to verify the correctness of service composition, but their notions of compatibility and similarity of Web service processes are not well-defined. Particularly, the relationship between compatibility and similarity lacks of sufficient research, rendering existing techniques of service substitution very costly and time-consuming. The authors’ research work focuses on modeling and analyzing Web service processes based on Colored Petri nets (CPN). The authors present the definitions of correctness and compatibility of Web service processes. In order to alleviate the compatibility verification, the authors develop the notion of well-structuredness of Web services and prove that all reachable final markings of a composite service composed by well-structured services are correct. Based on the above results of compatibility analysis, the authors explore the definition of similarity of Web service processes with the purpose to improve the existing methods of service substitution. The results conclude that substituting a service in a composition can be performed independent of other partners in the composition, as long as the new service is similar to the substituted one. Therefore, it is no need to verify the substituted service composition again. The authors develop an algorithm for automatically verifying similarity between two services. The results and algorithm concluded in the research can be used to improve the existing methods and develop more efficient techniques for service composition verification and service substitution. This work is supported by the National Natural Science Foundation of China under grant No.60674080 and No.60704027, and the National High Technology Research and Development Program (863 Program) of China under grant No.2007AA04Z150.