基于动态描述逻辑的语义Web服务PE匹配算法

郭媛香

（晋中学院信息技术与工程学院，山西 晋中 030619）

基于动态描述逻辑的语义Web服务PE匹配算法

郭媛香

（晋中学院信息技术与工程学院，山西 晋中 030619）

将基于描述逻辑断言构成的PE描述公理的有限集合看作一个本体知识库，因此有关PE的语义匹配问题就转化到两个基于描述逻辑的本体知识库之间的逻辑蕴含判定问题，然后将逻辑蕴含推理问题转化为本体库的可满足性检测问题，并通过可判的扩展算法解决，同时对匹配结果进行有意义的排序及分类.所提方法与现有方法相当的情况下，具有更高的查全率，能够更好地区分匹配结果.

语义Web服务；前提/效果；动态描述逻辑；服务匹配

W eb服务[1]是一个崭新的分布式计算模型，是W eb上数据和信息集成的有效机制，具有自包容、自描述性的应用模块，可以通过W eb来发布、查询和调用，它的出现及推广将变革现有的W eb应用模式.语义W eb服务扩展了当前的W eb服务，赋予W eb中所有信息以良好的语义，是W eb提供的一种动态服务，每一个服务可以看成一个动作.

描述逻辑（DL）是一种基于对象的形式化知识表示工具，对概念性知识的处理非常有效，它具有清晰的模型—理论语义，具有很强的表达能力和可判定性，能够提供有效的可判定推理服务.动态描述逻辑[2]（DDL）是描述逻辑的一种动态扩展，支持语义W eb环境下对动作的描述和推理，该DDL清晰的语义特征能够让系统理解语义，有效地对静态知识和动态知识进行表示和推理.一个W eb服务的功能性描述可以抽象为一个DDL原子动作.

目前，大多数的语义匹配算法主要关注服务的IO匹配，对PE匹配算法的研究很少，但PE的描述是至关重要的.在执行一个服务需求链时，没有考虑服务PE的匹配会给整个任务带来负面影响，因此需要设计算法解决PE的匹配.本文结合描述逻辑的知识[3]，提出一种基于动态描述逻辑的语义W eb服务PE匹配算法，以基于描述逻辑断言构成的知识库对服务的PE进行描述，将PE匹配问题转化为描述逻辑知识库之间的逻辑蕴含判定问题.

1 基于动态描述逻辑的PE匹配方法

语义W eb服务功能性描述主要指服务的输人（I）、输出（O）、前提（P）和效果（E）的描述，W eb服务匹配实质上是服务描述的匹配，就是利用服务的语义描述信息和动态描述逻辑对知识的推理功能，服务需求方从已经发布的W eb服务中找到符合需求的服务的过程.从描述逻辑的定义和性质可以看出，一个服务本质上就是一对描述逻辑知识库[4]，本文以描述逻辑知识库之间的语义推导和逻辑蕴含关系的一致性检测为基础，给出了基于描述逻辑知识库一致性检测的语义W eb服务PE匹配算法，因此有关PE的语义匹配问题就转化到两个基于描述逻辑的本体知识库之间的逻辑蕴含判定问题.

1.1 描述逻辑基础

描述逻辑由语法和语义组成，语义是通过解释I=（ΔI，·I）给出，其中，ΔI是解释领域的非空集合，·I是解释函数，能够把每个原子概念A映射到的ΔI的子集，把每一个原子关系P映射到ΔI×ΔI的子集.ALC是最基本的描述逻辑，包括以下算子：交（∩）、并（∪）、非（┐），存在量词（□）和全称量词（□）.在ALC的基础上添加不同的构造算子能构成不同表达能力的描述逻辑.SHOIN(D)为对应语义Web本体语言OWL DL的描述逻辑表示语言.

在一定领域中，一个基于DL的知识库К=＜TBox，ABox＞由TBox和ABox两部分组成.其中，TBox是由包含概念定义及公理构成的包含断言的有限集合，概念A、C间包含关系的断言表示为A⊆C，概念A、C引入概念名称的过程表示为A□C，ABox是由断言公式或其否定形式构成的实例断言的有限集合，形如R (a，b)、C（a）的公式分别是描述逻辑中的角色断言、概念断言，二者统称为断言公式，其中C是相对于TBox的简单概念名，C（a）表示个体a满足概念C的约束；R是一个关系，aRb，R（a，b）表示个体a的属性R的一个取值是b，a、b为个体对象.

1.2 语义Web服务形式化定义

为了利用描述逻辑知识库一致性检测进行服务的PE匹配，我们以形式化的方式定义W eb服务的前置条件P和后置条件E，并在此基础上进行分析.将具有相似功能的一类服务抽象为一个DDL原子动作，然后将蕴含推理问题转化为本体库的可满足性检测问题[5]，并且将这些推理问题转换为DDL SH OIN（D）中公式的可满足性问题.为了便于说明，本文认为服务的输入和输出都已经被实例化为个体，描述只考虑了原子基础服务PE.

定义1给定某个TBox，将一个原子基础服务К=（P，E）看成一个原子动作.其中：К为原子动作名；P为服务前提，抽象为TBox上断言公式或其否定式组成的有限集合，表示动作执行前必须满足的前提条件；E为服务效果，抽象为TBox上简单公式组成的有限集合，表示执行该动作后将会发生的影响.К=（P，E）包括：①一个由描述逻辑公理组成的表示前提的有限集(知识库)；②一个由描述逻辑公理组成的表示效果的有限集（知识库）.

一个W eb服务可用一个描述逻辑的表达式描述，用Pa、Ea表示服务提供者的PE描述信息，用Pr、Er表示服务请求者的PE描述信息，那么对于同一个TBox，请求服务Кr=（Pr，Er）和发布服务Кa=（Pa，Ea）之间的匹配可以分为以下四种定义：

Exact：如果Pr≡Pa，Er≡Ea，即Кr|=Кa和Кa|=Кr均成立，则Кr⇔Кa.此时服务提供者与服务请求者的描述完全等价，表明服务提供者Кr和服务请求者Кa完全匹配.

FatherContains：如果Pr□Pa，Er□Ea，即Кa|=Кr成立，但Кr|=Кa不成立，此时服务提供者的服务执行后产生的效果Кa逻辑蕴含服务请求要求的效果Кr，表明服务提供者的服务执行后会对客观世界产生额外的效果.

SubContains：如果Pr□Pa，Er□Ea，即Кr|=Кa成立，但Кa|=Кr不成立，此时服务请求者的服务Кr逻辑蕴含服务提供者的服务Кa，表明服务请求者能够满足服务提供者规定的服务发生的条件.

Fail：如果Pr≠Pa，或者Er≠Ea，即Кr|=Кa和Кa|=Кr均不成立，表明Кr与Кa完全不匹配，匹配失败.

该算法利用本体描述逻辑语言描述语义信息，并将匹配结果细化，在精确与失败两种匹配结果的基础上添加了FatherContains匹配和SubContains匹配的情形，从而提高匹配精度.服务间的匹配程度按照匹配的强弱程度分为四个等级，即Exact＞FatherContains＞SubContains＞Fail.

1.3 PE匹配算法

Web服务匹配包含了两个功能：一个是发布服务，一个是从服务的描述数据库中查询服务.服务提供者将服务的描述发布在匹配器的服务注册中心，用户则通过提交查询来获取所需服务的信息.为了判断服务发布者是否提供了用户需求的功能，基于描述逻辑的服务本体为匹配模型提供了描述信息.Web服务匹配过程如图1所示.

在服务匹配的过程中，查询语句和每一个存放在注册中心的服务描述进行匹配.在进行匹配时，需求服务和服务描述的所有前置条件和后置条件都要进行匹配，每当一个服务和用户需求匹配成功就将其记录到查询结果的列表中，并将它与其他匹配成功的服务进行匹配度的排序.

图1 基于描述逻辑的语义Web匹配的流程图

在PE匹配中，结合描述逻辑的知识，用ABox概念断言描述服务发布和服务请求的前提条件和效果，用TBox描述推理依赖的领域知识，给出一个能够通过两个服务的PE描述信息计算出匹配结果的算法1.在匹配结果中也可能存在多个服务发布与服务请求相匹配，该算法并对它们的匹配结果集进行排序，该算法的伪代码形式化表示如表1所示.

表1 判别匹配结果精确分类的算法

1.4 PE匹配推理

W eb服务推理对保障知识库的一致性非常重要.基本推理主要有：概念可满足性检测，一致性检测，包含检测，实例检测等.其中概念可满足性检测推理、一个知识库可满足性检测问题都能被简化成关于术语的概念可满足性问题.

定义2可满足性：对于给定的TBox Τ，ABox Α，如果存在术语库Τ的一个解释I及概念C，使得CI≠Ф，那么概念C是关于Τ可满足的.此时，我们说I是C的一个模型.

解释I是包含断言C⊆D的模型，当且仅当CI⊆DI.

解释I是概念断言C（a）的模型，当且仅当a∈CI.

解释I是角色断言R（a，b）的模型，当且仅当（a，b）∈RI.

解释I是知识库К的模型，当且仅当I是К中包含断言和实例断言的模型.

若К有模型，则К是可满足的.

定理1概念C是可满足的⇔形如{C（a）}的断言关于TBox是一致的.

证明：

充分性.若C是可满足的，假设{C（a）}是不一致的，则必有TBox Τ的一个模型I，使得

而CI≠ CI，这与C是可满足的矛盾.

必要性.若{C（a）}是一致的，对所有的I∈Int（L），C∈Τ有CI=CI，即I|=Τ，所以C是可满足的.

定理2令К表示基于SH OIN（D）的知识库，A表示SH OIN（D）的一个原子事件，G（A）表示事件断言集，则：

К|=A当且仅当К与{G（A）}是一致的；К与{G（A）}是一致的当且仅当К∪{┐G（A）}是不一致的.

当且仅当（A∈К1）∩(К1|=К2)成立，则К1|=К2.

当且仅当（К1|=К2）∩(К2|=К1)成立，则К1⇔К2.

本文将PE描述公理的有限集合看作一个本体知识库，因此有关PE的语义匹配问题就转化到两个基于描述逻辑的本体知识库的关系问题.令δ（К）为这样一个转化：把知识库中的形如□C∈К的公理转化为公理a：C，其中a表示一个实例的名字，C表示知识库中的类.那么，判别一个本体知识库蕴含另一个本体知识库的算法表示如表2所示.

表2 判别本体知识库蕴含关系的算法描述

2 匹配示例

本文以物流领域信息服务中的发布/订阅系统为例来说明匹配过程.关注产品流通的用户向产品流通环节发布的信息中请求消息订阅服务，订阅自己感兴趣的产品流通信息，根据业务语义来进行事件与订阅的匹配分析，如果该业务事件符合用户的订阅要求，该物流环节上的信息服务提供者就会自动通知该用户，从而达到用户请求服务与实时发布服务的匹配.

本文将用户的订阅看作是概念，每一个原子事件看作是一个个体.令Sub（e）为事件断言集，Sub（e）表示事件e匹配订阅Sub，若要判断事件e是否匹配订阅Sub，就是根据描述逻辑中基于个体推理的知识库来判断个体e是否满足概念Sub的约束.物流领域的业务状态如图2所示.

用户的订阅需求：货物的业务状态变为t ransport i ng→通知用户.

图2 物流领域业务状态图

用户的订阅表达式：Sub=Transact i onEvent∩□St ep.Transport i ng.

条件：系统中产生了一个交易事件，且该事件的St ep取值为rai l carryi ng.

目标：判断该事件是否匹配订阅Sub.

匹配过程：

（1）断言知识库К={Transact i onEvent(e),St ep（e,rai l Canrryi ng）}

（2）计算S={КU{┐Sub(e)}}的完全形式：

（3）判断S的不一致性：

S中的第一个集合元素是不一致的，因为该集合元素包含Transact i onEvent（e）和┐Transact i onEvent（e）；由于S中的第二个集合元素包含┐l andCarryi ng（rai l Carryi ng），显然也是不一致的，因而S是不一致的，所以由定理2可知事件e匹配订阅Sub.

由此可知，对于原子订阅的匹配算法，算法的主要工作集中在判断知识库完全形式的一致性上.充分利用DL推理机的强大推理功能，实现了本文提出的基于描述逻辑的W eb服务匹配算法.将W eb服务的功能抽象为DDL动作后，从DDL具有动态语义模型出发，通过推理由前提条件的动作产生的效果来实现W eb服务的匹配.

3 结束语

针对语义W eb服务的前提/效果匹配问题，本文提出了一种基于动态描述逻辑的方法来实现W eb服务功能性层面上的自动匹配.将基于描述逻辑断言构成的PE描述公理的有限集合抽象为一个本体知识库，然后提出一种基于描述逻辑知识库一致性检测的PE匹配算法，并对该算法的合理性进行了实例分析.由于本文提出的匹配算法仅针对原子基础服务，还未能在更多的实际应用中表达复杂的业务逻辑，接下来的工作方向是扩展DDL使得它支持复合服务的匹配，在兼顾匹配效率的情况下来提高描述语言的表达能力，并在实践中进行检验.

［1］Jai deep R,Anupam a.R.Underst andi ngW eb servi ces［C］//IT Prof essi onal，Vol um e3.W ashi ngt on：IEEE Com put erSoci et y，2001.

［2］BaadeF，Cal vaneseD，eta1.TheDescri pt i on Logi c H andboo K：Theory Im pl em ent at i on and Appl i cat i ons［M］.Cam bri dge Uni versi t yPress.2003：47～100．

［3］石莲，孙吉贵.描述逻辑［J］.计算机科学，2006，33（1）：194～198.

［4］BADER F，LUTZ C，M ILICIC M，eta1.A descri pt i on l ogi cbased approach t oreasoni ngaboutW eb servi ces［C］//Proceedi ngsoft he W W W 2005 W orkshop on W eb Servi ceSem ant i csNew York：USA：ACM 2005.

［5］吴强，刘宗田，强宇.基于本体的知识库推理研究［J］.计算机应用研究，2005（1）：51～53.

（编辑 张瑛）

TP311

A

1673-1808（2014）03-0064-05

2013-12-23

郭媛香（1963-），女，山西榆社人，晋中学院信息技术与工程学院，副教授，研究方向：计算机技术与应用、数据挖掘.