On Extending Semantic Matchmaking to Include Preconditions and Effects

Central to the notion of dynamic binding and loose coupling that underlie service-oriented architectures is dynamic service discovery. At the heart of most service discovery mechanisms is a matchmaking algorithm that matches a semantic query to a set of compatible web service advertisements. These advertisements also describe service semantics as a set of OWL-S terms. Most current matchmaking algorithms are based on semantic matching of input and output terms alone. However, a complete description of the service profile also includes preconditions and effects and in order to find a true match the matchmaker needs to match on these aspects of the advertisement as well. In this paper, we make the case for augmenting existing matchmaking algorithms with preconditions and effects in the context of Web Services. Further, we propose an algorithm for condition matching that is layered on the top of input-output term matching that overcomes the limitations of existing work. Although the problem of condition matching is NP-Complete, we can overcome this limitation by using a set of heuristics that gives us results in polynomial time. We also analyze complexity of the algorithm by comparing it with brute force approach of matching. We show that our algorithm yields results more efficiently than brute force matching but with the same accuracy.