《包含前置条件和后置条件的基于扩展的语义匹配》由会员分享，可在线阅读，更多相关《包含前置条件和后置条件的基于扩展的语义匹配（13页珍藏版）》请在金锄头文库上搜索。
1、包含前置条件和后置条件的基于扩展的语义匹配AbstractCentral 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 se
2、rvice 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 i
3、n 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 match
4、ing that is layered on the top of inputoutput 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
5、 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术语描述服务
6、的语义。现在大多数的匹配算法都是仅仅基于输入和输出的语义匹配。但是，一个完整的服务的概要说明还包括前置条件和后置条件。为了能找到正确的匹配，匹配算法还需要对advertisements的前置条件和后置条件进行匹配。在论文中，我们解释了在原有基础上增加了web服务上下文中的前置条件和后置条件的匹配算法。而且，我们提出一种条件匹配的算法，这种算法是在输入-输出之上的匹配，并且克服了现有匹配算法的局限。虽然条件匹配的问题是NP完全问题，我们还是可以通过启发式的方式来克服局限性，而且这种启发式的方法的时间复杂度为多项式级别的复杂度。我们也分析了在强制匹配算法的复杂度。实验显示，精确度相同的情况下我们的
7、算法比强制匹配的算法高效得多。1. 介绍发布-发现- 绑定的结构的目标是动态服务调用。例如，服务调用的客户端不能优先知道服务描述的知识，因此不能链接已编译的存根。规约标准如WSDL和注册标准如UDDI 使服务发现的过程变得容易，服务发现的过程在服务的动态调用中是必需的。但是，UDDI的查找能力仅仅限于基于语义的查找，这将会导致一些不正确的结果除非查询是基于种类的。例如，一个简单的服务可以将两个整数作为输入，并产生一个浮点数作为输出，在实际执行的是一系列操作中的一个，比如利息的计算是根据本金和周期，每场游戏的平均分是根据总分和游戏的场数，等等。一个简单的基于语法的匹配可能会产生错误的正数，因为服
8、务的本质没有在服务的描述中表示。为了克服上述局限性，语法的概念经由OWL-S被引入。在这个方法中，服务的功能通过输入、输出、前置条件和后置条件进行描述。服务的输入和输出可以表述为属于某一本体集合中的概念。本体的使用允许指向某个单一概念，这个概念来自两个个到多个不同的术语。而且，它消除了由由术语之间的语法差异所产生的局限性，因为匹配可能基于本体的概念，而本体是用来描述输入和输出。再者，语法匹配的引入也引入了复杂匹配的概念，匹配算法的输出将不再是布尔类型（匹配或者不匹配）。相反的，将会有多种匹配的程度，如在3中所提及的精确匹配、插入匹配、包含匹配等。这些模仿了实际的服务的使用场景，客户并不实现知道
9、服务提供者，因此精确匹配是非常少见的。基于输入和输出的服务描述的语义匹配是有必要的，但却是不够的。为了得到准确的结果，输入-输出的匹配，和前置条件与后置条件是同样需要的。基于输入输出的语义匹配的领域已经有大量的工作已经完成，相对来说，基于前置条件和后置条件的领域却是没有什么进展。在本文中，我们演示了用基于前置条件和后置条件的服务描述来匹配要查询的服务发现的算法。这个算法是建立在原有的匹配输入和输出的工作基础上，实际上，也是使用了相同的策略来完成匹配。算法使用SMT理论来产生时间复杂度为多项式时间的解决NP完全问题的方案。本文的剩余部分的结构如下：首先，我们描述前置条件和后置条件的匹配，以及系统
10、地阐述了问题。然后，我们指出5所提及的算法的某些局限性。接着，我们提出基于前置条件和后置条件的算法。最后，我们分析我们的算法的性能。2. 问题陈述如下所示是一个旅馆预定的服务的描述。它要查找在指定城市且特定时间的一个旅馆，而且附带一些个人喜好的条件，诸如预期的房租价格和房间数的要求等等。每个输入和输出都是属于旅游本体，当然这儿为了简便起见，我们忽略了一些其他的东西。描述中所提到的ExpressionType可以是任意的表达式语言，诸如KIF 14 或者PDDL 15。( _ROOMCOUNT 8)(我们假设，如果服务没有找到客户所提出的给定数量的房间、给定的房租价格的限制以及指定的时间范围的旅
11、馆，那么它将返回一个不可用的状态。在这个案例中，服务的描述显示了服务只能接收那些房间数在1到7的查询结果。客户查询的服务，可能会以相同的格式，但是输入和输出可能会有不同的名字。(假设在这个案例中，本体的概念中的对不同参数的服务描述，和那些客户的请求相匹配。语义的匹配方法如3 和4 中所使用的基于输入和输出的匹配，可以标示这个服务为客户请求的潜在的候选者。但是，客户不提供这些参数的前置条件。如果客户确实选择了服务，并使用某些输入值的集合来调用了服务，执行可能会在服务调用的过程中失败，如果服务的前置条件不被满足，这是因为在服务的前置条件缺少的条件下，下行为不能被定义。即使我们假设客户的输入满足所有
12、的前置条件，服务和客户之间的合同可能是不合法的除非服务的输出的值也符合客户请求的后置条件的标准。这说明，前置条件和后置条件，加上输入和输出，应该是匹配的标准，因为前置条件在服务提供方是必需的，而后置条件对客户端是必需的。而且，所有的IOPE都是必须匹配的。3. 相关工作语义匹配的概念在3中被引入。作者提出了依据IOPE来描述 web服务的方案。输入和输出的每个属于都和本体的概念相关。OWL-S 12 提供了一个通过使用输入、输出、前置条件和后置条件来表示web服务的标准。它允许每个术语和相关的本体的URLs相关联。灵活的匹配的概念伴随着语义服务，在3中被引入。3中引入的匹配程度有4种。我们认为
13、AdOp是某个请求的服务其中一个输出的概念，QOp是要其中一个提供的服务输出的概念。4种匹配程度如下： 精确匹配：如果AdOp和QOp等价，那么可以认为他们是精确匹配。如果QOp 是AdOp的子类，在基于服务提供者同意提供的输出是AdOp的所有可能的子类的假设下，也可以认为是精确匹配。 插入匹配：如果AdOp包含QOp ，那么AdOp 可以插入替换 QOp。这里，我们也假设，服务提供者同意提供的输出是AdOp中的子类。 包含匹配：如果QOp归纳AdOp ，那么服务可以完成需求当所请求的服务可以是QOp 定义的子类的概念。 失败匹配：如果QOp和AdOp之间没有任何包含关系，那么可以认为匹配是失
14、败的。如果匹配输入项，请求的服务的角色和提供的服务的角色要反转。匹配的程度可以被描述如上面的优先权递减的顺序，当然，精确匹配具有最大的优先权。但是，3中所指定的匹配程度可以假设为，如果请求的服务在本体的特定的概念中提供了在本体中指定的某个特定概念的输入，它可以支持所有概念的所有可能的子类。在4和16中讨论的假设，在实际的场景中并不合适。它导致服务提供者提供更为泛化的输出项，因为这样的输出项与请求的服务会有更好的匹配度。如果提供者提供的输出项为owl:Thing类，这个类在owl的描述中是所有其他类的父类，因此，请求的服务将能插入匹配所有的查询。对输入项也是同样的道理。但是，它们能被用户查询给查
15、找出来。4中也提及到了插入匹配的条件，条件也是基于上述类似的假设。如果我们去掉上述假设，包含假设的匹配的条件要强于插入匹配。因此，一种新的匹配程度的方案在16中被提出来。 精确匹配：如果AdOp和QOp 是 等价概念，那么它们可以标示为精确匹配。 插入匹配：如果QOp包含AdOp，那么，服务可以完成请求者的需求，因为服务的提供者可以满足由QOp定义的概念的子集。因此，它是一个插入匹配。 包含匹配：如果AdOp包含QOp ，那么它就是一个包含匹配。 失败匹配：如果QOp和AdOp没有包含关系，那么它被成为失败匹配。不同的作者提出了各种各样的基于输入输出项的语义匹配的方法。3中的贪心算法和4中的二
16、分布图算法就是其中的例子。正如我们在上一节所描述的，仅基于输入输出项的匹配是不不能满足客户的需求的，其中一个方法就是5 中所提到的基于前置条件和后置条件的方法。但是这个方法中还是存在一定的局限性。 这个方法可能无法发现两个条件之间的匹配，在用两种不同的方式表达相同的条件时可能出现。例如：(Period 3) and (Rent 5000 or Room 4)也可以表示为(Period 3 and Rent 5000) or (Period 3 and Room 4)。 这个方法假设，通过对所有项执行语义的匹配，使用上述两个条件，我们可以决定这两个条件是否等价。但是，和使用这两个条件的项的匹配一起，这两个条件的结构的等价也是必需的。例如，考虑如下例子：1. (Room 4) and (Rent 5000)2. (Room 4) or (Rent 5000)条件1使用的所有项在条件2都出现了，但是
