模块化本体缓存方案

摘要:该文提出了一种模块化本体缓存方案,使用该方案能够缩短本体推理的平均时间。给出了缓存的对象和缓存一致性检查方法,通过中断方式和增量模式传递知识更新信息,能够减少通信量和提高更新的效率。

关键字:本体;模块化;缓存

中图分类号:TP311文献标识码:A文章编号:1009-3044(2010)11-2627-02

Cache Scheme in Modular Ontology

JIANG Zong-hua

(College of Information Engineering, Anhui University of Finance & Economics, Bengbu 233041, China)

Abstract: The author presents a cache scheme in modular ontology,the average ontology reasoning time can be decreased by using the scheme.The cache objects and the cache consistency checking method are described. By transmitting knowledge updating messages in interrupt mode and incremental mode, the total communication volume can be reduced and the efficiency of updating can be enhanced.

Key words: ontology; modular; cache

本体是指共享概念模型的明确的形式化规范说明,通过描述概念及概念之间的关系来描述概念的语义。本体不仅被某个应用主体所接受,而是在各种应用主体之间交换意见时所用到的共同语言。本体最主要的优势是共享和重用。

随着对某个领域认识的深入,相应的领域本体也越来越大,大规模单一本体会带来一系列问题:在大规模单一本体上进行推理的效率低;即使只需要小部分知识也要引入整个本体,重用率低;开发者需了解整个本体,不利于分工合作和本体进化等。模块化是有效克服这些问题的方法,通过模块化,本体被分成若干个功能相对独立的模块,而在模块化本体中引入接口的方法,能进一步提高模块的独立性。

模块化本体中,一个本体模块在进行推理时,可能要用到多个其它模块的知识,甚至于这些模块分布在网络中的不同主机上。引入缓存即通过对一些概念和角色的术语和断言进行缓存,能够提高本体推理的效率。为了保持本体缓存的一致性,当相关模块的知识变化时,应及时更新缓存的对象。

1 基于接口的模块化本体

在基于接口的模块化本体中,本体被定义成接口和本体模块的集合[1],一个接口是一个概念名、角色名和关于它们的包含公理集合,而一个本体模块是一个可以用任何描述逻辑语言表达的本体。通过引入接口的概念,将本体模块的知识分为公有部分和私有部分。

本体表示语言的逻辑基础是描述逻辑[2],描述逻辑的知识库由ABox(断言)和TBox(术语)两部分组成。ABox是一个关于个体的断言组成的有限集,形如C(a)或r(a,b),其中C是概念名而r是角色名,a、b是个体名,在本体表述中,个体指概念的实例。TBox是一个概念包含公理的有限集,形如A?哿B,其中A和B是概念表达式。

每个接口中的TBox公理构成了本体模块的共享段,共享段的逻辑结果会被传播到所有其它相关模块中,以下是接口的定义:

定义1:一个接口定义为I=其中T是接口的TBox,Cn和Rn分别是在T中用到的概念和角色的名称集合,接口I中没有ABox断言。

本体模块的断言集和内部TBox公理是私有的,只能通过知识查询来访问,私有段知识的改变只在局部知道。每个本体模块指定它要使用的接口集和它实现的接口集。当作为接口的实现者时,该模块将提供接口中有关概念和角色的解释;当作为接口的使用者时,能够集成接口实现者模块的知识。以下是本体模块的定义:

定义2:一个本体模块定义为M=,其中Ψ由模块内的TBox公理和ABox断言集合组成,Ir是模块M实现的接口集合,Iu是模块M使用的接口集合。

本体模块具有局部语义和清晰接口,从而进一步提高了模块的独立性。一个本体模块使用另一个模块时,是通过使用接口实现的。在基于接口的模块化本体中,模块的进化和接口的配置是分开的。在模块进化时,仅确定了使用的接口而没有确定接口由哪个模块实现,这样就不必知道被使用模块的名称和符号;在配置时,选择模块来实现接口,使得实现者模块容易被替换。

2 缓存方案

2.1 缓存对象

由于在缓存方案中,对角色的处理和对概念的处理是相似的,以下仅讨论对概念的处理。在基于接口的模块化本体中,如果某模块在推理的过程中用到其它模块的知识,则需要向相关接口发起查询,从接口的实现者模块中查得相关概念的实例。为了尽可能地缩短本体推理的时间,每个本体模块可以分配一个缓存空间,用来存放经常被查询的外部知识。文献[3]提出本体模块存储所有用到的外部概念之间的包含公理,这在时间复杂性和空间复杂性上是难以接受的。另外文献[3]没有区分外部概念之间稳定的和暂时的包含公理之间的区别,不能高效地更新有稳定子集关系的相关概念。而在基于接口的模块化本体中,模块使用者用到的外部概念放在接口中,同时接口中的TBOX中存放这些概念间稳定的包含公理。而对于因组合爆炸产生的数量巨大的暂时性包含关系则由实现者模块决定,是动态的。在实现者模块中并不存储这些暂时的包含关系,而只是解释接口中概念,概念之间的包含公理由它们的实例决定,知识的存储是线性的。使用者模块可以向接口发起查询从而获得相关概念的实例,而被查询概念稳定的祖先概念可以由接口中TBOX推理出。

本方案中缓存的知识主要由两部分构成:ABOX缓存知识和TBOX缓存知识。ABOX存放一些经常被查询的概念有哪些实例,例如“直辖市”概念有北京、上海等实例。TBOX存放经常被查询的包含关系,假设A和B两个概念中至少有一个是外部概念,如果经常要查询A和B的包含关系,查询结果(例如是A?哿B)则被缓存。由于缓存空间的有限性,当缓存空间将要用尽时,可以采用最近最久未用法等置换算法删除一部分缓存内容。

采用缓存机制后,推理如果用到外部模块的知识则先在缓存中查找,如果命中则本地的知识便能完成推理,否则再向实现者模块发起知识查询,根据局部性原理,这样能够显著缩短平均推理时间。

2.2 缓存一致性

当一个本体模块的相关模块知识改变时,可能会造成缓存内容的失效。在文献[1]中,一个本体模块对相关模块的知识集成是通过发起知识查询来进行的,然而如果对缓存中的概念不断发起知识查询,以此来判断有无发生更改显然是低效的,会造成模块间通信量的剧增和相关模块推理任务的加重。本研究中,用中断的方式来替代查询的方式,由发生知识改变的模块负责发送消息给相关模块。

若某模块的知识发生变化时,首先确定该知识变化所影响的概念,如果相关的概念都未在接口中出现,则说明对接口的解释没有改变,只是发生和接口使用者无关的局部语义改变,不必发送更新消息。否则,将发生改变的概念的实例发送给接口的使用者模块。发生改变的概念如果在接口中有祖先概念,势必也会引起祖先概念实例的改变,但此时只发送最底层概念和它的实例,这是因为接口的TBOX知识能传播到使用者模块从而能够推理出祖先概念。由于接口的使用者模块的缓存对象是它的局部信息,接口的实现者模块并不知道该信息,无法判断发生语义改变的概念出现在哪些使用者模块的缓存中,所以知识更新消息将发给所有使用者模块。

发生改变的概念实例采用增量的模式发送,在消息中指出哪个概念增加(或减少)了哪些实例。只向相关模块定向发送和采用增量模式,可以减少通信量。使用者模块收到消息后,结合自身的知识和相关接口的TBOX,推理出发生改变的概念所有祖先概念,加上该概念自身得到一个概念集。由于接口中的TBOX知识已被加入到使用者模块的本地知识库,故这一步的推理是在本地进行的。如果该概念集中的所有概念均未在使用者模块的缓存中出现,使用者模块将丢弃收到的更新消息。如果在缓存的ABOX部分找到了概念集中的某个概念,则更新ABOX缓存知识。下一步是查找该概念集中的概念有无在缓存的TBOX部分中出现,假设该概念集中的某概念出现在缓存中一条形如A?哿B的包含公理中,则分为下述几种情况决定该包含公理是否失效,对失效的公理将从缓存中删除。

1)A的实例减少或不变而B的实例不变或增加。这种情况下该条包含公理仍有效。

2)A的实例增加。这种情况下则首先查询缓存ABOX知识中有无概念B,若没有则要向概念B的实现者模块发送知识查询信息,得到概念B的实例集。令A1表示A增加实例的集合,如果A1?哿B,则该条包含公理仍有效,否则该条包含公理失效。

3)B的实例减少。这种情况下则首先查询缓存ABOX知识中有无概念A,若没有则要向概念A的实现者模块发送知识查询信息,得到概念A的实例集。令B1表示B减少实例的集合,如果B1∩A=?I,则该条包含公理仍有效,否则该条包含公理失效。

如果实现者模块重新定义了一个概念,造成一个概念的实例大规模变化,使得发送概念增量实例可能比发送概念实例通信量更大,这种情况下也可以直接发送概念实例。由于使用者模块的缓存中可能没有该概念,为了减少通信量,在知识更新消息中仅发送该概念的名称和一个特殊标志指出当前工作在非增量模式。该概念和它的祖先概念构成一个概念集,如果该概念集的某个概念出现在使用者模块缓存中一条形如A?哿B的包含公理中,则不论位置如何,都要重新判断该条包含公理的有效性。通过向相关实现者模块发起知识查询,得到A和B的实例集,再判断A?哿B的有效性。非增量模式下缓存ABOX检查是类似的。

3 结束语

为了提高模块化本体推理的效率,本研究提出了模块化本体缓存方案,给出了缓存的对象和缓存一致性检查方法。进一步的研究是将该方案应用到具体的系统中并进行验证。

参考文献:

[1] Ensan F.Formalizing Ontology Modularization through the Notion of Interfaces[C].Acitrezza,Catania,Italy:Proc. of the 16th International Conference on Knowledge Engineering and Knowledge Management,2008:74-82.

[2] Borgida A,Serafini L.Distributed Description Logics:Assimilating Information from Peer Sources[J].Journal of Data Semantics,2003,1(1):153-184.

[3] Stuckenschmidt H,Klein M.Reasoning and Change Management in Modular Ontologies[J].Data and Knowledge Engineering,2007,63(2):200-223.