Title

AND/OR Graph and Search Algorithm for Discovering Composite Web Services

Publication Type

Journal Article

Publication Date

2005

Abstract

This paper presents a formalization of the Web Service composition problem as a search problem in an AND/OR graph, and a search algorithm for searching the graph to identify composite service(s) that satisfies a Web Service request. Given a service request that can only be satisfied by a composition of Web Services, we identify the service categories that are relevant to the request and dynamically construct an AND/OR graph to capture the input/output dependencies among the Web Services of these service categories. The graph is modified, based on the information provided in the service request. The search algorithm is then used to search the modified AND/OR graph for a minimal and complete composite service template that satisfies the service request. The algorithm can be applied repeatedly to the graph to search for alternative templates until the result is approved by the service requester. We have evaluated the algorithm both analytically and experimentally, and the experiment results are presented.

Discipline

Software Engineering

Research Areas

Software Systems

Publication

International Journal of Web Services Research

Volume

2

Issue

4

First Page

48

Last Page

67

ISSN

1545-7362

Identifier

10.4018/jwsr.2005100103

Publisher

IGI Global

Additional URL

http://dx.doi.org/10.4018/jwsr.2005100103