A Web Service Composition Approach Based on Planning Graph and Propositional Logic

A Web Service Composition Approach Based on Planning Graph and Propositional Logic

ShiYang Deng (Shandong University of Science and Technology, Qingdao, China), YuYue Du (Shandong University of Science and technology, Qingdao, China) and Liang Qi (New Jersey Institute of Technology, Newark, USA)
Copyright: © 2019 |Pages: 16
DOI: 10.4018/JOEUC.2019070101
OnDemand PDF Download:
No Current Special Offers


To improve the computational efficiency of web service automatic composition, this article proposes a novel approach based on a planning graph and propositional logic. This approach has a forward searching stage and a backward combination stage: the former stage searches services in a service storage and performs the composition in a hierarchical architecture based on a planning graph, while the latter stage combines them via propositional logic operations. This method can obtain all composite services that contain no redundant services, and the computational complexity can be significantly reduced. Experiments are done to illustrate the effectiveness of the approach.
Article Preview


As self-describing and platform-independent computational elements, Web services are used to support service-oriented architectures, distributed computing and software reuse (Berardi, Cheikh, Giacomo, & Patrizi, 2008). A composite service is defined as a group of services that run in a certain order. It realizes functions that cannot be provided by a single service.

The rapid proliferation and development of services have drastically increased the choices for users, while searching services and composition become tedious and time-consuming. Many approaches and technologies have been proposed and applied to the composition and verification of services, such as Agent (Tong, Cao, Zhang & Li, 2011), workflows (Karakoc, Kardas & Senkul, 2006), Petri nets (Li, Fan, Sheng, Maamar & Zhu, 2011; Tan & Zhou, 2013), and semantic Web (Lecue & Mehandjiev, 2011). However, the aforementioned methods concentrate less on the organization and management of the function-same or similar services. Some researchers gather similar services into groups known service clusters (Nayak & Lee, 2007; Sun & Jiang, 2008; Ma, Chen, Hui & Wu, 2011; Sudha & Thamarai, 2006; Han, Wang & Cui, 2009) or service communities (Benslimane et al, 2007; Maamar et al, 2008; Liu, Huang & Mei, 2007) to improve the efficiency of service discovery and composition. Logic Petri net is introduced to service clusters for modeling indeterminate parameters of services and formalizing deduction of service composition (Deng & DU, 2012; Hu, Du & Yu, 2014; Wu & Du, 2015). These methods aim at improving the efficiency of service composition, but do not consider removing redundant services of the composition.

As a powerful formal model, planning graph (Huang, Wei, Hu & Liu, 2009; Wei, Zhang, Huang, Chen, Hu & Liu, 2010; Deng, Huang, Wu, Yin & Li, 2013) has been used to construct service composition in many research studies. A planning graph is a directed acyclic hierarchical graph with nodes and arcs. There are two types of nodes in a planning graph, as shown in Figure 1: one type is service nodes, which are used to describe services, e.g., s11-s23, and another type is called parameter nodes, which are used to describe input or output parameters, e.g., p11-p33. In a planning graph, a set of service nodes can form a layer called a service node layer, while a set of parameter nodes can form a layer called the parameter node layer. Arcs are drawn from service nodes to parameter nodes or from parameter nodes to service nodes. Service composition based on a planning graph has a forward searching stage and a backward combination stage. The former is used to search services in a service storage to construct a planning graph that has parameter node layers and service node layers that appear alternately, as shown in Figure 1, where the nodes in the first parameter layer, called the initial layer, are the input parameters given by the users, and the nodes in the last parameter layer, called the target layer, contain all of the output parameters required by the user. The latter stage is a reverse searching process from the target layer to the initial layer. It is used to find services in the planning graph and combine them as a composite service that satisfies a user’s request.

Complete Article List

Search this Journal:
Volume 33: 6 Issues (2021): 2 Released, 4 Forthcoming
Volume 32: 4 Issues (2020)
Volume 31: 4 Issues (2019)
Volume 30: 4 Issues (2018)
Volume 29: 4 Issues (2017)
Volume 28: 4 Issues (2016)
Volume 27: 4 Issues (2015)
Volume 26: 4 Issues (2014)
Volume 25: 4 Issues (2013)
Volume 24: 4 Issues (2012)
Volume 23: 4 Issues (2011)
Volume 22: 4 Issues (2010)
Volume 21: 4 Issues (2009)
Volume 20: 4 Issues (2008)
Volume 19: 4 Issues (2007)
Volume 18: 4 Issues (2006)
Volume 17: 4 Issues (2005)
Volume 16: 4 Issues (2004)
Volume 15: 4 Issues (2003)
Volume 14: 4 Issues (2002)
Volume 13: 4 Issues (2001)
Volume 12: 4 Issues (2000)
Volume 11: 4 Issues (1999)
Volume 10: 4 Issues (1998)
Volume 9: 4 Issues (1997)
Volume 8: 4 Issues (1996)
Volume 7: 4 Issues (1995)
Volume 6: 4 Issues (1994)
Volume 5: 4 Issues (1993)
Volume 4: 4 Issues (1992)
Volume 3: 4 Issues (1991)
Volume 2: 4 Issues (1990)
Volume 1: 3 Issues (1989)
View Complete Journal Contents Listing