（计算机软件与理论专业论文）含放松dlsafe规则知识库的可判定性研究.pdf

河海大学硕士学位论文摘要 摘要 下一代语义网使用本体来表示知识，引入规则来增强知识表达力和自动推理能力。o 、l d l 与 s w r l 分别是语义网中应用最广泛的本体语言和规则语言，两者的结合具有强大的知识表达力。但 由于s 、脉i ，规则的推理不可判定，无法得到可靠的推理算法，限制了其应用。德国卡尔斯鲁厄大学 的b o r i sm o t i k 等人将o w l d l 对应的描述逻辑s h o 烈( d ) 与规则结合，通过将规则限制在所谓的 “d l s a f e 规则”( 事实上是s w l 也的一个可判定子集) 范围内，提出了一种可满足性检测可判定的 推理算法。但是在实际应用中仍有大量含规则知识库因其规则集不满足“d l s a f e 规则”的严格限制 而无法使用上述推理算法，本文旨在确保含规则知识库的可满足性检测可判定的前提下，对“d l s a f e 规则”的限制进行放松，使知识表示及推理的应用范围扩大。 本文工作主要包括以下四个方面： ( 1 ) 针对含规则知识库中因复合关系的使用被隐式引入到a b o x 中的个体( 称匿名个体) ，对 “d l - s a f e 规则”进行了放松，提出了“放松d l s a f e 规则”的定义。 ( 2 ) 形式化证明了含“放松d l s a f e 规则”知识库的可满足性检测是可判定的。 ( 3 ) 为了使含“放松d l - s a f e 规则”知识库仍能运用b o r i sm o t i k 等人提出的推理算法，提出了 一个判断转换算法a j c ，该算法不仅能判断含规则知识库是否满足“放松d l s a f e 规则”，而且能将 满足“放松d l - s a f e 规则”的知识库等价转换为满足“d l s a f e 规则”的知识库；同时分析了算法时 间复杂度。 ( 4 ) 在以上理论研究的基础上，开发了实现a j c 算法的原型工具l r c ，并通过实验进行了案 例研究，验证了算法的有效性与时间复杂度。 研究结果表明，本文提出的“放松d l s a f e 规则”涵盖了b o r i sm o t i k 等人提出的“d l s a f e 规则”， 依然是s w r l 规则的一个可判定子集。本文研究成果使得可满足性检测可判定的含规则知识库中的 规则限制有了一定的放松，从而使b o r i sm o t i k 等人提出的推理算法可应用于更一般的含规则知识库， 亦即可应用于语义网上更普遍的场合。 关键词：语义网，描述逻辑，含规则知识库，推理，可判定性 河海大学硕士学位论文 a b s t r a c t a b s t r a c t i nn e x tg e n e r a t i o no fs e m a n t i cw e b ，o n t o l o g i e sa r eu s e df o rk n o w l e d g er e p r e s e n t a t i o n ，锄dr u l e sa r e b r o u g h tt oe n h a n c et h el ( n o w l e d g ee x p r e s s i b i l i t ya n da b i l 时t or e a s o na u t o m a i i c a l l y o w l d la n ds w r l a r er e s p e c t i v e l y 廿l eo n t o l o g y 一卸dr u l e - l a n g u a g et h a ta r em o s tw i d e l yu s e di ns e m a n t i cw e b p o w e r f u l e x p r e s s i b i l 时c 锄b eg a i n e db yt h ec o m b i n a t i o no fo w l d la n ds w i 也h o w e v e r ，s w l 也a l s ob r i n g s u n d e c i d a b l i t yo fr e a s o n i n g ，s on or e l i a b l er e a s o n i n ga l g o r i t h mh 笛b e e ng i v e ns of a r ，w h i c hl i m i t si t s 印p l i c a t i o n b o r i sm o t i k s ( u n i v e r s i t ) ，o fk a r l s r u h e ，g e m 锄y ) t e 锄，f o u n daw a y t oe n s u r et h ed e c i d a b i l i 妙 o fr e a s o n i n gi ns h o r n ( d ) l ( n o w l e d g eb a s e sw j t hr u l e sb yr e s 仃i c t i n gt h er u l e st os o c a l l e d “d l s a f er u l e ” ( 1 nf a c t ，“d l s a f er u l e ”i sad e c i d a b l es u b s e to fs w r i ，r u l e ) t h e ya l s ob r o u g h tar e l i a b l er e a s o n i n g a l g o r i t h m h o w e v e r ，t h e r ee x i s ts t i l lp l e n 妙o fk n o w l e d g eb 船e sw i t hm l e si nw h i c ht h ea l g o r i t h ma b o v e c 猢o tb eu s e db e c a u s et h em i e si nt h e s ek n o w l e d g eb a s e sw i t h1 1 l l e sd o n tm e e tt h ec o n d i t i o n so f “d l s a f e m l e ，i np r a c t i c a l 印p l i c a t i o n s t h i st h e s i sr e l a x e st h er e s t r i c t i o ni nd e f i n i t i o no f d l s a f e 砌e 锄de n l 唱e s t h ea p p l i c a t i o nm n g eo fl ( n o w i e d g er e p r e s e n t a t i o na n dr e 鹊o n i n g w r o r ki nt h i st h e s i si n c l u d e sf o u rp a n sb e l o w ： ( 1 ) t b i n d i v i d u a l su n e x p l i c i t l yb r o u g h tt oa b o x ( c a l l e da n o n y m o u si n d i v i d u a l s ) i nl ( n o w l e d g e b a s e sw i t l lr u l e s ，豫l a ) 【t 1 1 er e s t r i c t i o ni nd e f i n i t i o no f “d l s a f em l e ”a j l dp r o p o s et h e d e f i n i t i o no f “r e l a x e dd l - s a f em l e ” ( 2 ) af o m a lp r 0 0 ft h a tc h e c k i n gi fl ( n o w l e d g eb 雏e sw i t l l “r e l a ) 【e dd l - s a f em l e s ”a r es a t i s f i a b l e i sd e c i d a b l e ( 3 ) a na l g o r i t h mc a l l e da j cw h i c hc a nt e l ll ( n o w i e d g eb 鹊e sw i t h “r e l a x e dd l s a f er u l e s ”f b m 0 t h e r sa 1 1 dc o n v e r tr e a s o n i n gi nk n o w l e d g eb 雒e sw i t h “r e i a x e dd l - s a f er u l e s ”i n t or e a s o n i n g i nk n o w l e d g eb a s e sw i t l l “d l - s a f er u l e s ”i ft h e i rr u i e sa r e “r e l a x e dd l s a f e1 1 j l e s ”a n d 锄 a n a l y s i s0 nt i m e - c o m p l e x i t yo fa j c s ot h ea l g o r i t h mg i v e nb yb o r i sm o t i k st e 锄c 硼b e u s e di n t h a t ( 4 ) o n t 1 1 ef o u n d a t o no fm e o 拶a _ b o v e ，ap r o t o 妙p et i d 0 ln 啪e dk b r ci m p l e m e m i n ga l g o r i t l l | i l a j ci sg i v e na 1 1 di t s 删l a b i l i t ) ，扑dt i m e c o m p l e x i 够a r er e s e a r c h e db ye x p e r i m e n t a t i o n s 1 tc o u l db ec o n c l u d e df r o mt 1 1 ew o r ka b o v et h a t r e l a x e dd l - s 疵m l e ”c o n t a i n i n g “d l - s a f em l e ， g i v e nb ym o t i k st e a mi ss t i l lad e c i d a b l es u b s e to fs w i 也r u l e r e s e a r c hr e s u l ti nt h i st h e s i sr e i a x e sm l e s i nl ( n o w l e d g eb a s e sw i t hr u l e sw h o s es a t - s f i a b i l i t yc h e c k i n gi sd e c i d a b l e ，w h i c hm a l ( e st h ea l g o r i t h mg i v e n b yb o r i sm o t i k st e 锄c a nb eu s e di nm o r eg e n e r a ll ( 1 1 0 w l e d g eb a s e sw i t hr u l e sa n ds i t u a t i o n si ns e m a n t i c w e b k e yw o r d s ：s e m a n t i cw e b ，d e s c r i p t i o nl o g i c s ，k n o w l e d g eb a s ew i t hr u l e s ，r e a s o n i n g ，d e c i d a b i l i t y 学位论文独创性声明： 本人所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中 不包含其他人已经发表或撰写过的研究成果。与我一同工作的同事对本研 究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。如不实， 本人负全部责任。 论文作者( 签名) ： ( 注：手写亲笔签名) 学位论文使用授权说明 夕各年歹月，9 日 河海大学、中国科学技术信息研究所、国家图书馆、中国学术期刊( 光 盘版) 电子杂志社有权保留本人所送交学位论文的复印件或电子文档，可以 采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论 文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅。 论文全部或部分内容的公布( 包括刊登) 授权河海大学研究生院办理。 论文作者( 签名) ： ( 注：手写亲笔签名) 口年占其昏b 河海大学硕士学位论文绪论 第一章绪论 1 1 研究背景与选题依据 w 曲创始人t i mb e m e r s l e e 于1 9 9 8 年首次提出了语义w e b 的构想【1 1 。语义w 曲 旨在让人和机器都能理解网络世界表示的信息，通过添加具有描述内容的元数据标记使 得w 曲资源及其语义更易被机器理解。语义w 曲被认为是下一代w 曲的信息基础设施， 它为w 曲的实际信息内容提供了形式化语义，以实现信息在语义层次的互操作性，语 义w r e b 旨在实现w r e b 上数据之间的链接，为这些数据赋予语义信息，使得计算机能够 理解和自动处理。在语义w 如层次模型中，语义w 曲的实现依赖于以下关键技术：用 x m l 来承载w 曲页面的内容，使得w e b 文档含有) ( 1 l 标签所携带的元数据信息；用 本体定义x m l 标签的语义，使得x m l 标签所携带的元数据信息得到共同的理解；使 用智能a g e m ，基于逻辑推理，对w 曲文档进行自动处理。 在丸蛆1 2 0 0 6 会议上，原有的语义w e b 体系被进一步修改，语义w e b 新体系结构被提 议( 如图1 1 ) ，其中正是突出了“本体规则并行的思想。 图1 1 语义网层次结构 w 3 c 于2 0 0 4 年2 月接受了基于描述逻辑的o w l 【2 1 ( w 曲o n t o l o g ) ，l a n g u a g e ) 语言，将其 作为w 曲本体语言的推荐标准。o w l 是逐步从r d f 【3 ，4 1 、i m f s 、d a m l + o i l l 5 ，6 】演化 来的最新版本描述语言，o w l 沿袭i m f 的基本事实陈述方式以及i m f s 的类和属性分 层结构，并以描述逻辑为基础理论而构建语言系统。具体而言，o w l 语言提供了三种 表示能力不同的子语言，来分别满足不同组织团体的语言实现者和使用者：o w ll i t e ， o w l d l 和o w lf u l l 。描述逻辑是语义w 曲的逻辑基础，其中，在描述能力上，o w l l i t e 和o w l d l 分别与描述逻辑s h i f ( d ) 以及s h o 烈( d ) 等价。o w ll i t e 是o w l d l 河海大学硕士学位论文 绪论 的子集，这二者都使用基于框架语言的抽象句法，同时也可映射为r d f 三元组；而其 语言以及形式语义则基于描述逻辑的定义，使得本体间的推理问题能够归约为描述逻辑 知识库的可满足性检测问题。o w ll i t e ，0 w l d l 以及o w lf u l l 作为o w l 提出的三 种子语言，其表达能力依次增强，且推理能力逐个向下兼容。不过前两者基于比较抽象 的框架式句法，采用经典逻辑学中的解释。而o w lf u l l 则可视为不受限制的i m f ( s ) 的扩展，句法仍使用i m f 三元组，并基于非经典的模型论对) f 语义做o w l 的语义 扩展。 即便如此，o w l 仍然只能表示树型结构知识，为了进一步提高其表达能力，人们 将o w l d l 和r u l e m l l 7 ，8 ，9 】( r u l em a r k u pl a l l g u a g e s ) 规则语言结合，提出了s w r l 【1 0 】 ( s e m a n t i cw 曲r u l el a n g u a g e ) 语言。s w r l 允许且只允许d l 中的c o n c e p t 和r o l e 出现 在h o m 子句前提和结论中。s w r l 的规则的i m p 中保留了r u l e m l 中以h e a d 表示推理 结果，b o d y 表示推理前提的基本形态。h e a d 和b o d y 中的允许出现的基本成分是原子， 即其架构中所使用的h o m 子句都是由原子所组成。h n p 的h e a d 部分只允许出现一个原 子，而b o d y 部分允许出现若干个原子的合取，即规则具有h o m 子句的特征，而具有 h o m 子句形式可以便于推理。原子中所使用的变量部分记录在变量中，原子分为四种 形式：c ( x ) ，c 是o w l 的类描述；尸( 工，y ) ，p 是o w l 的属性而x ，y 可以是变量，o w l 个体或是o w l 数值；跏叫j ( 薯y ) ，表示x 和y 等价；d 獗脚刀砌所( x ，y ) ，表示x 和y 不 同。s w l u 提供了更为强大的表达能力，但遗憾的是，由于h o m 规则的引入，破坏了 原有知识的树型结构，导致了s w r l 推理的不可判定性【l l l 。b o r i sm o t i k 等人提出 “d l s a f e 规则【1 2 ，1 3 1 概念，实则为s w r l 的一个可判定子集，它允许向描述逻辑中引 入规则，但要将规则在一个所谓“d l s a f e 的范围内，并给出了对应其的推理算法。 “d l s a f e 规则 解决了一部分含规则知识库的可判定推理问题，但在含s 吼规 则知识库中仍存在大量含规则知识库因不满足“d l s a f e 限制而无法应用b o r i sm o t i k 等人提出的可靠的推理算法。鉴于此，本文将对“d l s 疵规则”进行放松，提出“放 松d l s a f e 规则的概念，并证明含“放松d l s a f e 规则 知识库的可满足性检测是可 判定的。另外本文将提出转换算法，在符合相关条件下通过改造原有知识库的a b o x 部 分，将含“放松d l s a f e 规则”知识库上的推理转换为含“d l s a f e 规则”知识库上的 推理，从而使得b o r i sm o t i k 等人提出的推理算法可应用于更一般的含规则知识库及语 义网上更普遍的场合。 1 2 相关工作及技术现状综述 s w i u 与o w l 的结合使用构成含规则知识库，可抽象为描述逻辑与规则的混合系 统。在描述逻辑与规则的混合系统及其对应的推理问题研究上，前人有大量可借鉴的工 作。本节将依次介绍几个有代表性的含规则知识库系统或相关语言，并简单评述其性能 及优缺点。 2 河海大学硕- 上学位论文绪论 1 2 1c l a s s i c 与l o o m 系统 早在描述逻辑的早期，就有一些基于描述逻辑的系统包含相应的规则语言组件，以 c l a s s i c 【1 4 ，1 5 ，16 1 ，l o o m 【1 7 ，1 8 ，19 】为代表。只是此时的规则所能表达的语义较弱，甚至不 能直接简单地表达出一个概念是另一个概念的子概念，概念之间的包容关系只能通过对 其概念的不同描述实现。这些系统中的规则所能表达的语义很弱。形式仅仅限定为 c ( x ) 一d ( z )c ，d 为概念谓词 并且这些规则只能应用于实例。所以该类系统的推理只能应用于个体与概念间检验，不 能用于进行给予概念间的推理。 1 2 2a l l o g 与c a r i n 系统 a l 1 0 9 【2 0 ，2 1 ，2 2 1 系统结合了a l c 基本描述逻辑和d a t a l o g 异构规则。要求规则中的所有 变量都必须出现在非描述逻辑谓词( n o n d lp r e d i c a t e ) 中。所有规则只能适用于在知识库 中明确存在的实例。但规则的前件中仅可以包含以a l c 描述逻辑中的概念作为一元谓词 的项，不支持角色对应的二元谓词。 c a r i n 【2 3 ，2 4 ，2 5 ，2 6 1 系统结合a l c n r 描述逻辑和d a t a l o g 异构规则，包含一个h o m 规则 集合以及描述逻辑的概念和角色定义，所有概念和角色谓词项都可以出现在规则的前件 中。为了确保其可判定性，c a r i n 分别对描述逻辑和h o m 规则进行了限制：第一，描述 逻辑中的最大子集a l c n r 可以和任意类型的非递归无函数的h o m 规则相结合而不影响 推理过程的完备性。第二，规则角色项中出现的变量中至少有一个要出现在一个非描述 逻辑谓词中，概念和角色谓词项只能出现在规则的前件中。 在a l 1 0 9 中异构规则只允许出现d l 概念，而c a r i n 接受异构规则中出现的d l 概念 和d l 角色。 1 2 3s 、眦语言 s w r l 语言结合o w l d l 与h o m 规则，不对规则中概念与角色谓词的出现位置以 及谓词中的变量作限制，这使得s 吼具有强大的表达能力，同时使得s w i u 在推理 中不可判定。通过将该一致性的判定问题映射为一个已知的不可判定性问题，其不可判 定性容易证明。此类问题的详细证明过程参看文献】。 s w r l 主要分为四部分组成，分别是i m p 、a t o m 、a b l e 和b u i l d i n g 。在i m p 中 保留了r u l e m l 中以h e a d 表示推理结果，b o d y 表示推理前提的基本形态。h e a d 和b o d y 中的允许出现的基本成分是原子，即其架构中所使用的h o m 子句都是由原子所组成。 i m p 的h e a d 部分只允许出现有一个原子，而b o d y 部分允许出现若干个原子的合取，即 规则具有h o m 子句的特征，而具有h o m 子句形式可以便于推理。原子中所使用的变量 河海大学硕十学位论文 绪论 部分记录在变量中，在原子分为四种形式：c ( x ) ，c 是o w l 的类描述；尺( j ，y ) r 是 o w l 的属性而x ，y 可以是变量，o w l 个体或是o w l 数值；跏鲥s ( 工，j ，) ，表示x 和y 等价：d f 纷佗聊乃伽阮y ) ，表示x 和y 不同。 1 2 4d i 广s a f e 规则 s w i u 提供了强大的知识表达力，但s 眦推理的不可判定严重限制了其实际应 用。“d l s a f e 规则 在此背景下提出，“d l s a f e 规则”要求规则为选言规则( d i s j u n c t i v e r _ u l e ) 形式： 4 v 4 v v 以卜目，岛，色 并对前件蜀，岛，毽中的变量进行限制，类似于a l 1 0 9 系统对变量的限制，规则前件中 的变量必须同时出现在该前件中的某个非描述逻辑谓词中。这是为了确保所有被规则使 用的个体都是被显式引入到知识库的，从而确保其可判定性。与有些含规则描述逻辑混 合系统不同，“d l s a f e 规则 则是对描述逻辑与规则间的接口作限制，要求规则满足选 言规则形式同时规则中的变量所涉及个体为被显式引入到a b o x 的个体。 不满足“d l s a f e 规则”的例子： 爿b ，疗p 阡7 a 心p r ( d 一尸鄹d 阼( 工) ，_ f l ，e ：爿f ( 工，y ) ，w d 成4 f ( 墨y ) 满足“d l s a f e 规则”的例子： 胁所p 腑以秽( x ) 卜尸绷鲫( 工) ，如别眠y ) ，w d ，枷眠) ，) ，d 0 ) ，d ( y ) 文献【1 3 1 已经表明，这种定义结果的表达力比原有描述逻辑与h o m 规则都强，其满 足性可判定，相应推理算法也被给出。 1 2 5 对d l s a f e 规则的放松 “d l s a f e 规则要求严格，规则必须为选言规则形式： 4v4 v v4 卜置，岛，尾 后件中各项必须间以逻辑析取符号连接，前件各项必须以逻辑合取符号连接：且规则前 件所涉个体须显式引入到知识库。于是人们便试图在不影响其可判定性前提下，降低其 对规则的限制要求。文献【2 7 】对规则的选言形式进行了放松，提出在满足一定条件下，可 以不局限于h o m 规则的合并中，可以允许在规则前件中出现逻辑析取符号。逻辑析取 符号不仅仅局限在规则的后件中，充分利用描述逻辑的析取表达能力，可以使某种形式 的析取表达式出现在规则的前件中，这些是通过对规则中谓词的合并来实现的。为此该 文引入“可合并谓词项 的概念。 定义1 1 可合并谓词项 假设存在两个谓词项爿和b ，如果满足以下两个条件，则爿和b 为“可合并的谓词 项”： 4 河海大学硕士学位论文 绪论 i ) 谓词项j 4 与召分别为为形如c ( 力，j d o ，) 的谓词，其中c ，d c ，x ，y 为实例变量。 i i ) x ，y 不是相异的常量实例。 定义引入后，通过所谓“谓词合并算法 来实现相关谓词之间的合并。 算法输入：谓词项爿和b 算法输出：合并结果项 ( 1 ) b e g i n ( 2 ) i f 爿和b 不是可合并的谓词项，t l l e n 停止 ( 3 ) 使一= c ( 曲，且b = d ( x ) ( 4 ) i f 五y 是实例变量，且j = y ( 5 )t h e n 建立新概念= c u d ，删绷e ( 工) ( 6 ) e l s ei f 工是一个实例变量，用y 替换工 ( 7 )t 1 1 e n 建立新概念e = c u d ，甜删( y ) ( 8 ) e n d 当两个谓词项在第5 步和第7 步被合并时，需要利用描述逻辑中的u n i o n 概念定 义符建立新概念，并作为合并结果返回。谓词项合并的目的便是在与合并谓词项有关的 规则前件中引入析取，从而放松“d l s a f e 规则 的选言形式限制，提高其表达力。既 而提出所谓“规则抽取算法 。 算法输入： 规则1 ：( 。v ) 卜( q ，q ，匕，气，q 。) 规则2 ：( 。v ) 卜( g ，o ，昂，吃。) 算法输出：q = 配，巴。 c ，g = g ，) c ，只= 只，只。 尺， b = b ，) r ，呒= ( 呢。v 呢。) p ，= ，v 坼 所抽取的新规则：( wv ) 卜( l ，弓，墨，最，0 l ，) ，= 巨，蜀 心， 尸= e ，只) 尺，= 峨v ) p ( 1 ) 初始化谓词项集合e = a ，户= o 。 ( 2 ) 对谓词项集合巴，g 进行搜索，如果在这些谓词项中存在两个不同的常量实例， 则两条规则无法合并，停止。 ( 3 ) 如果q ，q 中只存在一个常量实例口，合并分别来自集合e ，g 中的每个谓词项对。 然后将每个谓词项对合并的结果谓词加入到集合e 。将所有在这两条规则中出现的变量 都用口代替，转到第5 步。 ( 4 ) 如果q ，g 中没有出现常量实例。从规则中的变量中随意选择个变量工。用变 量工来替换其他所有规则中出现的其他变量。然后合并分别来自q ，q 中的每个谓词项 对。并将每个谓词项对合并的结果加入到集合e 。转到第5 步。 ( 5 ) 对两个谓词项集合只，只。和弓，进行匹配。如果对于每个谓词项都可以在另 一个谓词项集合中找到一个相同的谓词项，则匹配成功。将只，只。加入到谓词项集合尸 河海大学硕士学位论文绪论 中。反之停止。 ( 6 ) 将e 和中的谓词项直接加入到集合形中。并保留规则前件中所有的谓词d 项。 返回新生成的规则。 经过运用上述规则抽取算法从而在规则前件中引入逻辑析取，且不影响其推理的可 判定性。 本文也将对“d l s a f e 规则 进行放松，但不同于上述对“d l s a f e 规则”选言规则 形式的放松，本文将针对含“d l s a f e 规则 知识库中个体须显式引入的这一限制进行 放松。本文将指出，在满足一定条件下，允许部分个体被隐式引入到知识库中。 1 2 6 小结 本节介绍了几个有代表性的含规则知识库系统或相关语言。不难看到，从c l a s s i c 至s w i u 的推理渐难表达力渐增，“d l s a f e 规则对规则进行限制从而表达力减弱到 对“d l s a f e 规则 的放松，研究者一直在寻求描述逻辑与规则间的结合点，旨在保证 推理容易实现前提下尽量增加知识表达力。 1 3 研究内容与研究目标 1 针对含规则知识库中因复合关系的使用被隐式引入到a b o x 中的个体( 称匿名 个体) ，对“d l s a f e 规则 进行放松，提出“放松d l s a f e 规则”的定义。 2 证明含“放松d l s a 佗规则”知识库的可满足性检测检测是可判定的。 3 提出一个判断转换算法，该算法能够判断含规则知识库是否满足“放松d l s 疵 规则”，而且能将满足“放松d l s a f e 规则 的知识库等价转换为满足“d l s a f e 规则 的知识库。 4 开发实现a j c 算法的原型工具，并通过实验进行了案例研究，验证算法的有效 性与时间复杂度。 1 4 本文组织结构 第一章，绪论。表述本文的研究背景、相关研究工作分析、研究内容与研究目标。 相关工作中包含早期含规则描述逻辑混合系统c l a s s i c ，l o o m ，a l l o g ，c a r i n ； s w r l 语言，“d l s a f e 规则 以及针对“d l s a f e 规则 的放松工作。重点介绍“d l s 疵 规则”放松工作。 第二章，预备知识。详细介绍描述逻辑、规则、“d l s a f e 规则”。以a l c 为例介 绍描述逻辑的逻辑组成及推理知识；介绍s h 系列描述逻辑，并指出o w l 各构造子与 其的对应关系；以s w r l 为例介绍规则的结构及与o w l 本体的结合。 第三章，放松d l s a f e 规则。给出“放松d l s a f e 规则的定义，并证明其可满足 性检测可判定。通过引入“匿名个体 、“同一性待定个体对”、“可确定匿名个体” 6 河海人学硕士学位论文 绪论 等辅助定义， 转换算法。 第四章， 描述。 第五章， 第六章， 最终给出“放松d l s a f e 规则的定义，并对其可判定性进行证明；给出 开发原型工具，实现第三章的转换算法。分别对算法中的各模块功能进行 案例分析。从实验角度分析算法有效性和时间复杂度。 总结与展望。对本文的研究工作进行总结，并展望进一步的工作方向。 河海大学硕上学位论文预备知识 第二章预备知识 2 1 描述逻辑与o w l d l 语言 描述逻辑是人们进行知识表示的有力工具【2 8 ，2 9 ，3 0 1 。描述逻辑是由所谓的“结构化层 级网络 发展而来的，结构化层级网络是为了克服早期语义网络和框架的歧义性提出的， 语义网络和框架最早是在k l o n e 系统中实现的。在第一个基于逻辑的语义学应用于 k l o n e l i k e 知识表示语言之后，人们发现一些描述逻辑系统使用的语言的表达能力太 强，这使得一些推理问题很难处理。但是，后来的研究表明，推理的难处理性( 超多项 式复杂度) 并没有妨碍d l 在应用中的有用性。 在描述逻辑系统中，首先通过定义该领域内的相关概念，表示一个应用领域的知识； 然后使用这些概念指明出现在该领域内的对象和个体的性质。描述逻辑的特点在于不像 早期的知识结构网络表示一样，描述逻辑本身具备一个形式化的、基于逻辑的语义。另 外一个显著的特点是描述逻辑以推理为服务重点：知识推理使人们可以从知识库中的外 层显式知识得到蕴含在其内部的隐含知识，而往往这些隐含知识才是对人们有用的。描 述逻辑中含有的各种构造子是人们用来描述知识结构的直接手段。其中概念和个体的分 类确定了给定的领域中概念间的包含关系，个体与概念间的归属关系。 2 1 1 描述逻辑的基本结构 每个描述逻辑知识库结构都是相似的，一个是t b o x ，一个是a b o x 。t b o x 用一个 术语学的形式包含紧凑的知识。并且通过描述概念的一般的属性定义而构造的。由于概 念之间的构成术语学的包含关系的本质，t b o x 通常被认为具有一种类似格子的结构。 这种数学结构是通过包含关系承担的，和任何实现没有关系。a b o x 包含扩展知识也称 为断言知识，这种知识指与讨论领域中的个体相关的知识。描述逻辑知识库的一个关键 元素是用来构造术语学的操作给定的。这种操作直接和在t b o x 中宣称的形式和意义相 关。在t b o x 中断言的基本形式是概念定义，也就是，根据另外的先前定义的概念来定 义一个新的概念。例如，一个女人可以用一个女性的人来定义，如下断言： w o m 口n 暑p e r s o nnf e m 口l e 这样的一个断言通常理解成一个逻辑等式，它提供了判断一个个体是女人的充分必 要条件。这种形式的定义比其他种类的知识表示中使用的形式更强，其他的表示形式只 施加了必要条件，这种断言的强度通常被认为是描述逻辑知识库的一个标志特征。因此 在描述逻辑知识库中，某领域知识是用以上形式的的概念定义集合构成的。 特别的，构造领域知识的基本任务是分类，也就是在一个概念分类层次的正确位置 上放置一个新的概念。分类可以通过验证每个已定义的层次中的概念和新的概念之间包 含关系来完成。概念必须放置在最特定的包含新概念的点和新概念包含的最广泛的概念 河海大学硕士学位论文预备知识 点之间。 a b o x 包含关于感兴趣领域的扩展知识，也就是说，关于个体的断言，通常称为实 例断言。例如： f e m n l e p e r s 0 叹a m l 由 指出个体a 衄a 是一个女人。类似地， h o s c h i l d 0 a n n 口，0 q c o p o 指加m a 有个叫作j a c o p o 的孩子。第一种断言也称为概念断言，而第二种断言也称为角 色断言。 在a b o x 中可以指定概念断言和角色断言的知识。在概念断言中，通用的概念表达 是允许的，而角色断言，其中的角色不是一个原子角色而是一个角色表达式，这是不允 许的。 2 1 2 描述逻辑的推理 描述逻辑的推理问题可概括为五类【3 1 】： ( 1 ) 知识库的可满足性：给定一个描述逻辑知识库船，如果存在一个解释，使得 ， 脑 ( 2 ) 概念的可满足性：关于描述逻辑知识库舳的t b o x 部分丁，如果概念c 非空，即 存在一个解释，其中j r 净7 ，满足c 7 f 2 j ( 3 ) 概念的包含关系：关于描述逻辑知识库黜的t b o x 部分丁，如果概念c l 包含概 念c 2 ，即对任意解释，其中， 7 ，满足c 2 7 c 1 7 ( 4 ) 实例检测：关于描述逻辑知识库脚，如果个体名口属于概念c ，即对任意解释j r ， 其 中j k b ，满匙a 1 c | ( 5 ) 查询检索：关于描述逻辑知识库煳，查询概念c 的所有个体名口，使得船 c ( 口) 在a b o x 中基本的推理任务是实例检查，就是验证一个给定的个体是否是一个特定 概念的实例。虽然通常也考虑和使用另外的推理服务，但这些服务也可以根据实例检查 来定义。这方面的应用包括知识库一致性：即验证知识库中的每个概念是否都承认至少 一个个体；实现：即找到一个个体对象是最特定概念的一个实例；检索：即找到为知识 库中某个给定概念实例的个体。这些都可以通过实例检查的手段来达到。 t b o x 中基本的推理任务是包含关系，这种t b o x 的基本推理服务可以看作是逻辑 蕴含，也就是验证一个原子关系( 例如两个概念表达之间的包含关系) 是否是一个t b o x 断言的逻辑推论。主要提供分类方面的服务。 9 河海大学硕士学位论文预备知识 2 1 3a l c 描述逻辑 a l 描述逻辑是一种基本描述逻辑【3 2 ，3 3 1 ，其语法规则构成如下： c ，d _ 一i t i 刖一i c r 、d i v r c l 3 尺c 需要注意的是，在a l 语言中，否定只能被应用于原子概念，而且，在某角色的存在变 量的范围内，只允许全局变量使用。因为历史的原因，a l 语言的子语言中，不允许否 定应用于原子概念的被称为f l 。；f l 的子语言中，不允许使用由限制的存在变量的，被 称作f l o 。 a l c 描述逻辑是a l 的一种扩展逻辑，不再限定否定构造子仅应用于原子概念。其 构造子与语法语义如表2 1 ： 表2 1 l c 描述逻辑构造子及语义语法 构造子语法语义 原子概念彳一c 原子关系 足月7c 7 顶 t 底 上。 交 n c 7n d 并 u c lu 存在 j j r c 工l j ) ，( 工，y ) 尺7 y c 。) 任意 v j r c x l v y ，( j ，y ) j r 7 + j ，c 7 ) 否定 1 c一c 2 1 4s h 描述逻辑族 a l c 作为最基本的一种描述逻辑，不足以满足实际应用的需要。实际应用中不仅要 描述概念，还要增强角色的表达能力。具有传递性的角色常用于构造复合对象，a l c r a + 是在a l c 基础上允许部分角色具有传递性。参照这种形式语言与命题模态逻辑s 4 的紧 密联系，简称其为s 。进一步，若纳入角色包含公理形成角色分层则得到s h 描述逻辑。 另一方面，若s 中对角色的逆是封闭的，即存在“逆角色 构造子，则形成s i 描述逻 辑。在s h i 描述逻辑的基础上再添加数量限制、函数性约束或定性数量限制，可得到 s h i n ，s h i f ，s h i q a 当需要对个体实例进行刻画，通过枚举实例来描述概念时，可在描述逻辑中加入枚 举构造子。如s h o q ，s h o 烈就是在s h q ，s h i n 的基础上扩展而来。除了描述抽象概 念，实际应用中还常常需要对诸如整数、字符串之类的具体数据类型和数据值进行刻画 1 0 河海大学硕士学位论文预备知识 和推理。在引入具体数据类型后，相应的s h i f ，s h o i n ，s h o q 便转变为s h i f ( d ) ， s h o i n ( d ) ，s h o q ( d ) 。 2 1 5o 、m l 广d l 语言 o w l 本体”，3 5 ，3 6 ，3 7 1 语言的o w ll i t e 和o w l d l 子语言逻辑上分别与描述逻辑 s h i f ( d ) 以及s h o 跗( d ) 等价。o w l 三个子语言中，基于表达能力与推理难度的折中考 虑，o w l d l 的使用相对更普遍。表2 2 列举o w l d l 语言构造子与所对应的 s h o i n ( d ) 描述逻辑形式及o w l - d l 的公理和事实与所对应的s h o i n ( d ) 描述逻辑形式： 表2 2o w i 广d l 构造子对应的描述逻辑表示 o 、l d l 中类构造子与描述逻辑的关系 u n i o n o p c lu u c ： c o m p l e m e n t o p ，c o n e o p “，毛 a l i v a l u e s f r o n lv 尺c s o m e v 柚u e s f r o mj 兑c m a x c a r d i n a l i t ) ， s 疗尺 m i n c a r d i n a l i l ) ，幸 疗j r e q u i v a l e n t c l 勰s q 兰c 2 d i s j o i n t w i t h c lnc 2 = a s a m e i n d i v i d u a l a s“ 毫k ) d i 厅e r e n t f m m 五 n 屯 = 乃 s u b p r d p e r i y o f 日罡 e q u i v a j e n t p m p e r 哆墨宝最 i n v e r s e o f 仃肌s t i v e p r o p e r i ) ， 胁c t i o n a m r o p e n ) r i n v e r s e f u n c t i o n a l p r o p e r 哆 毋兰巧 日暑巧 tc sl 尺 t c 1 尺一 o w l - d l 具有较强的知识表达力，并且由于其构造子可与s h o i n ( d ) 一一对应，保 证了其任何推理可在有限的时间内完成，使得用0 w l d l 表示的本体具有可靠推理算 法，可得到普遍的推理技术支持。r a c e r 及p e l l e t 等便是针对o w l d l 语言应用最广泛 的推理工具。 河海大学硕士学位论文 预备知识 2 2 规则与s w i 乩语言 规则早在描述逻辑发展早期就被提出并被尝试加入到描述逻辑知识库系统，尤其是 在规则被列入语义网层次模型后，规则受到更深入的研究。规则常用于描述陈述性知识。 2 2 1s 、m 地语言 如今被使用并影响最广的规则语言便是s w l