On Completeness of Web Service Compositions

The main objective of composing web services is to identify usable web services through discovery and to orchestrate or assemble selected services according to the goal specification. In this paper, we formulate and study a framework of composing web services through discovery from a given goal service. A general algorithm for composition with or without a goal service invocation request is developed. Two notions of completeness, "schema completeness" and "instance completeness", are defined, which measure the ability of how thoroughly an algorithm can find a composition. The two notions correspond to compositions without or with a goal service request, resp. We show that schema completeness can be achieved by depth-first or breadth-first search combined with a tightening strategy. Further, the breadth-first search avoids redundancy. We also show that while instance complete algorithms exist, they generally need do invoke all candidate services.