包含前置条件和后置条件的基于扩展的语义匹配.doc

包含前置条件和后置条件的基于扩展的语义匹配 Abstract 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. 摘要 由面向服务的架构所引出的动态绑定和松散耦合的概念的核心，是动态服务发现。大多数服务发现机制的关键是匹配算法，匹配算法要能在一堆待查询的服务集合中找到符合的web服务集合。这些advertisements也是通过OWL-S术语描述服务的语义。现在大多数的匹配算法都是仅仅基于输入和输出的语义匹配。但是，一个完整的服务的概要说明还包括前置条件和后置条件。为了能找到正确的匹配，匹配算法还需要对advertisements的前置条件和后置条件进行匹配。在论文中，我们解释了在原有基础上增加了web服务上下文中的前置条件和后置条件的匹配算法。而且，我们提出一种条件匹配的算法，这种算法是在输入-输出之上的匹配，并且克服了现有匹配算法的局限。虽然条件匹配的问题是NP完全问题，我们还是可以通过启发式的方式来克服局限性，而且这种启发式的方法的时间复杂度为多项式级别的复杂度。我们也分析了在强制匹配算法的复杂度。实验显示，精确度相同的情况下我们的算法比强制匹配的算法高效得多。 1. 介绍 发布-发现-绑定的结构的目标是动态服务调用。例如，服务调用的客户端不能优先知道服务描述的知识，因此不能链接已编译的存根。规约标准如WSDL和注册标准如UDDI使服务发现的过程变得容易，服务发现的过程在服务的动态调用中是必需的。但是，UDDI的查找能力仅仅限于基于语义的查找，这将会导致一些不正确的结果除非查询是基于种类的。例如，一个简单的服务