引言
近年来，许多应用系统都采用本体作为语义支撑来满足不断增长的知识交换和知识集成需求。本体(Ontology)是某一领域共享概念模型的明确表示和描述，环境的变化和业务需求的多变性常常会引发支撑本体的演化m，由此产生了本体演化（OntologyEvolu?tion)问题。本体的变化对本体所定义的数据、依赖于该本体的其他本体以及使用这些本体和数据的应用系统都会产生较大的影响。
降低本体演化的影响可以从两个角度进行：1)降低本体演化的影响范围，即当本体演化后受到波及的服务个数越少越好。2)减轻服务的受影响程度，即如果某服务不可避免地受到波及，那么是否可以控制本体演化的过程使其朝着有利于服务修订的方向进行,使其变得尽可能的简单易行。其中需求2的满足依赖于服务的具体实现方式，难以提出一个通用的算法，本文主要从满足需求1的角度出发来探讨如何降低本体演化的影响。当前本体演化研究的焦点在于保证演化需求的实现以及维护演化前后本体的一致性3,对于降低演化的影响关注甚少。由于本体演化的复杂性，大多数研究还停留在框架分析和定性讨论层面。而演化影响的降低不但可以显著减轻依赖本体的应用系统的开发和维护的负担,还可以大幅提高系统的健壮性和灵活性。当前，流行的本体编辑演化工具如OntoEdit4、OilEd5、KAON都存在演化策略简单、依赖人工等问题。
据此，本文基于本体图模型,凭借矩阵变换与运算对本体演化中的波及效应进行了深入的分析和量化界定。同时给出了本体元素影响度及受影响度的计算方法。在强分图理论的支持下定义了本体强子图，并分析了子图内聚度、强子图影响度的计算方法。在此基础上建立了基于最小波及效应（MinimalRipple-ffect,MRE)的本体演化算法，将本体演化过程转变为求图的最短路径过程,通过寻找一条影响值最小的变更路径来减小本体演化的影响范围。
1本体图与本体矩阵
1.1本体模型
本文所依赖的本体模型被定义一个二元组：
定义1本体模型=(E,/mjp)。
其中,E为本体的实体集合;Imp为导入的其他本体模型。
定义2本体的实体集合E被定义为一个12元组：
EI=(C,P,I,Hc,Hp,label,domain,range,mincard,maxcard,instconc,instprop)
1.2本体图与邻接矩阵
定义3(本体图）一个本体O的图模型是一种有向的类型图G=<V,E>,其中节点集V的元素对应O中的概念或关系，边集E的元素对应O中的函数、概念
基于本体和本体图模型定义可以将本体表示成图的形式，这种图形方式的本体模型清晰地体现出本体的结构性。例如，一个本体用基于ODM的模型表示如图1所示。
2本体变更波及效应量化
本体演化是在本体元素发生变更时，通过相应其他元素的配套更改而重新达到本体一致的过程。本体演化算法通过顺序执行相应的变更操作来完成变更需求，每一个变更都将带来一系列元素的更改，最终导致_条变更执行路径的产生。分析本体演化的波及效应实质上就是分析变更操作及其组成的变更执行路径的波及效应。本体元素的变更操作可以分为4类:添加、删除、重命名和设置。其中添加、删除为基本操作，而重命名和设置可以由基本操作组合而成。虽然两种基本操作带来的波及效应不同，但只要确定变更所影响的元素，波及效应的计算方法是相同的。下面给出本体元素变更的波及效应量化方法。
2.1本体元素量化
此在变更过程中应尽量避免对强子图中元素的更改。
3MRE算法
文献1〇]通过公式推导将本体演化带来的服务变更的减小问题转化为本体演化波及效应减小问题。这里直接针对本体演化波及效应的最小化展开讨论。根据上一节的分析，本体演化最小波及效应的问题可以归结为寻找一条变更执行路径，使得演化后的本体满足一致性约束且所改变的本体元素个数最小。MRE算法将最小演化代价问题转化为针对本体图的最短路径问题。其中，图的节点是本体元素，按照之前的讨论,节点赋值为该本体元素的影响度。
3.1算法设计
算法寻找路径的过程为从变更元素的出边开始，到达所有可达孤立元素的过程。此时经历的路径称为搜索路径。依据算法的设计目标,MRE算法被描述为如下过程:在图的搜索过程中计算已搜索路径的变更影响值，如果该值大于已经搜索到的最小值就不再继续搜索。搜索过程中，已搜索路径的影响值小于原先搜索到的最小值，那么将作为一个新的备选解。MRE算法以_个待演化本体邻接矩阵以及_个变更元素为输入，以一条最小变更执行路径和最小影响值为输出。MRE算法描述如下：
输入:变更节点ChgNod,ChgNod与其可达的所有节点构造的邻接矩阵Q(可以通过待演化本体邻接矩阵构造），Q的秩为N,infect为Q中节点的影响度。
输出：已经搜索到的最小影响值minValue和最小变更执行路径minPath。
3.2复杂度分析与改进
MRE算法的主体是求图顶点到各节点最短路径的过程，无论采用何种图存储方法其算法复杂度都为〇(N2),当本体规模增加时，算法执行时间的增加也很可观。根据2.2节对强子图的分析不难发现，当本体图中包含强子图时,MRE算法的搜索路径只要包含强子图的任意节点，算法的计算结果都是一样的,我们引入强子图节点化方法对算法进行简化。
定义10(强子图节点化）由于对强子图任意元素的更改造成的波及效应等同于对整个强子图的更改造成的波及效应,为了分析方便我们将本体图的强子图转化为节点，该节点的先行后续关系为强子图所有节点对外关系的并集。这个过程称为强子图节点化，转化后的节点称为强节点。
如果本体图包含m个强子图，所有强子图总元素个数为n那么结点化后本体图的节点数为N-n+m,算法复杂度降为〇((N-n+m)2)。在本体图的构造过程中，原本的关联关系有包含、继承等多种，而图构造时都统一为连接线，这样本体图中很容易出现强子图；当本体图中元素个数很多时,不同元素间的关系错综复杂，也很容易出现强子图。因此在实际的演化路径生成过程中，强子图节点化在大多数情况下都可简化演化过程。
3.3应用评价
某生产部门要打造中央级的产品资源集成门户，允许各级生产单元自主加入总体资源中。其本体片段如图3所示。在该集成门户的打造中，本体的构建是一个核心任务。各级生产单元依赖本体以统一的方式接入，由于事先不能确定加入共享资源的生产单元，因此无法事先构建出一个能满足所有需求的全局本体。另外，随着产品升级换代必然带来本体结构的变化。也就是说生产部门本体会随着生产单元的加入与产品升级换代而不断演化。但是，本体演化会对已构建的平台服务带来极大影响，每一次本体演化都可能引起平台服务的重新修订和重新部署[11]。因此，如何减轻本体演化对平台服务的影响就成为实现产品集成门户的关键。
下面以图3所示的产品本体中的产品A片段为实验数据，验证不同变更算法的效率。该片段共涉及9种产品资源以及与这些资源相关的搜索、统计等共计60多个服务。为了方便比较不同变更算法的效率，我们使用元素变更率的概念，即：
变更率=演化后需要改变的元素个数/元素总数
(3)采用Prot6g6、KAON变更执行算法和MRE算法分别对该本体执行演化后得到元素的变更率。以删除操作为例，实验内容和结果如表1所示。显然，MRE算法对元素的平均变更程度明显小于其他两种算法。
表1反映出MRE算法的有效性主要体现在非叶节点的改变上,这是因为非叶节点与其可达所有节点构造的图中节点数较多。非叶节点在系统中的层次越高，其子节点和属性越多，与之关联的可达节点也越多,MRE算法有效性也越明显。对于叶节点的改变,3种算法所引起的服务变更率基本持平。这是因为当关联元素很少时，最短路径与一般路径的差别不是很大。从平均效果来看,Prot6g6和KAON算法的服务变更率基本持平。MRE算法的服务变更率则明显低于这两个算法，仅为其65%左右。该实验结果可以充分说明本文所提出算法能够有效减小本体变更的影响范围。
通过实验结果还可以发现MRE算法相比其他算法的特性。在整个本体图中,子部件2与非回转类零件的本体元素图中存在强子图，而子部件2中还存在一个影响度很大的节点。Pr〇t6g6与KAON采用的演化算法之所以变更率较大还因为他们没有在变更路径中避开这些节点，而MRE算法通过最短路径的搜寻有效避开了这些节点，因而取得了较好的效果。因此在实际应用中，可以考虑以避开影响度大的节点尤其是强子图中的节点为先验知识的高速演化路径生成算法，在较小的时间复杂度下获得与MRE算法近似的次优解。
4结束语
本文提出的MRE算法，以较小的时间代价使平均变更影响范围大大小于现有的本体演化算法。为了抽象出问题的本质,本文的分析没有考虑不同变更操作影响度的不同以及本体描述语言因素，进一步的研究工作包括针对具体本体语言的本体演化波及效应精确分析、本体演化算法等。
刘世卿
(中航工业西安航空计算技术研究所，陕西西安710119)
