【作者】 周丽平；

【导师】 黄厚宽；

【作者基本信息】 北京交通大学 ， 计算机应用技术， 2010， 博士

【摘要】 随着当前Web上信息量的不断增长,人们迫切要求Web上的内容是计算机可以理解的,并可以由计算机自动来做有意义的处理。1998年,Web的创始人TimBurners-Lee首次提出了“语义Web" (Semantic Web).语义Web是当前万维网的一个扩充,网页上的内容不仅仅是通过自然语言来描述,而且增加了一种计算机可以理解的语义,从而使计算机也可以参与进来,帮助人们获取有用的资源。由于语义Web要实现的是信息在知识上的共享和语义上的互操作性,从而便于机器处理和交互,所以语义Web中的信息应采用共享的词汇描述,并赋予严格的语义。本体作为共享概念模型的明确的规范说明,可以描述某个领域甚至更广范围内的概念以及概念之间的关系,使得这些概念和关系在共享的范围内具有大家共同认可的、明确的、唯一的定义,是人机之间以及机器之间进行交流的知识基础。本体在语义Web中扮演着重要的角色,所以创建、管理和维护一个高质量的本体是非常重要的。然而,在现实生活中,本体的构建过程有可能是分布性的、多作者的或者是由不同的数据源得来的,容易导致前后出现不一致的情况。而且本体的扩展、重用或合并也有可能导致本体不一致。当一个本体知识库出现不一致时,在经典逻辑的语义下,本体知识库可以平凡地演绎出任何结论,这意味着针对这样的本体知识库的推理是毫无意义的,因此,如何处理本体的不一致是语义Web中的重要问题。目前存在的方法一般都是基于强表达能力的描述逻辑(Expressive Description Logic),不适用具有大规模现实数据的本体,因为这些描述逻辑本体推理时最差情况下复杂度是指数级的。作为一种易处理描述逻辑(Tractable Description Logic), DL-Lite可以保证在大型数据上仍然具有多项式级时间的推理。本文基于易处理描述逻辑DL-Lite讨论了语义Web上不一致本体的处理,分别在诊断不一致本体、超一致查询问答及度量不一致性三个方面提出了解决方法,具体贡献如下：(1)诊断不一致本体通过分析DL-Lite本体中不可满足概念或角色所具有的特点,提出了一种有效地计算DL-Lite本体中不可满足概念或角色的所有最小不可满足保持子集(MUPS)的算法,并将此算法与当前最有代表性的算法进行了比较,实验表明所提出的算法对于DL-Lite本体来说是有效的,优于其它的算法。(2)超一致查询问答提出了对不一致的DL-Lite本体进行超一致合取查询问答,将经典语义下查询问答框架扩充到多值语义下,并给出了对DL-Lite本体进行一致合取查询问答的算法,证明此算法的复杂度是基于ABox大小LOGSPACE的。(3)度量本体不一致度提出了一个度量DL-Lite本体不一致的方法。对于一个DL-Lite本体,我们证明了在三值语义下可以直接基于TBox的否定包含闭包集、ABox及本体中的所有个体常量来度量不一致。给出了一个计算DL-Lite本体的不一致度的精确算法,证明了此算法的复杂度是基于本体的大小多项式级的。不同于其它文献中用一个序列值来度量知识库不一致,我们仅用一个直观的、更易理解的值来度量DL-Lite本体的不一致。(4)度量原子断言不一致度本体的不一致度是度量整个知识库中所具有的可能的矛盾,并不能反映出本体中每个公理断言的不一致性。为了找出导致本体不一致的根源,提出了对DL-Lite本体中原子断言进行不一致度量,并给出原子断言不一致度的定义。一个原子断言的不一致度越高,说明它最有可能导致本体不一致。同时我们给出了度量DL-Lite本体中原子断言的不一致度算法,并证明此算法可以在多项式级时间内完成。更多还原

【Abstract】 As the increasing growth of Web information, it is urgent that Web contents need to be understandable for computer so that computer can process Web contents automatically and meaningfully. To solve this problem, Tim Berners-Lee first put forward the Semantic Web, which is an evolving extension of the World Wide Web in 1998. For Semantic Web, Web contents can be expressed not only by natural language, but also in a format that computer can read and use, thus computer can find Web sources automatically. Since the main aim of Semantic Web is that information can be shared and cooperated so that computers can interact each other, the shared knowledge with a standard format is needed.As an explicit specification of shared conceptualization, ontologies can define concepts and relations among them for one or more domains, so that concepts and relations among them can have explicit, unique definitions that people can accept in a shared knowledge base. So ontologies play an important role in Semantic Web. It is important to create, manage and maintain ontologies with high quality.However, ontologies may be created by distribution, multi-authorship, or different data sources. All these characteristics may introduce inconsistencies. Also, the reuse, merging or further extension of ontologies may result in inconsistencies in ontologies. When in-consistency occurs, the classical entailment in logics is explosive:any formula is a logical consequence of a contradiction. Therefore, conclusions drawn from an inconsistent ontology by classical logic inference may be completely meaningless. So it is essential to study how to deal with inconsistent ontologies.So far, most existing approaches mainly focus on expressive description logics (DL) which suffer from worst-case exponential time behavior of reasoning. As an important tractable DL family, DL-Lite can keep all the reasoning tasks tractable, in particular, with polynomial time complexity with respect to the size of the ontology. In this paper, we focus on DL-Lite and discuss how to deal with inconsistencies of Semantic Web ontologies. We mainly provide solutions to inconsistency debugging, paraconsistent query answering, and inconsistency measuring. Our contributions include the following points:(1) Inconsistency Diagnosis After analyzing some features of unsatisfiable concepts or unsatisfiable roles in DL-Lite, we present a novel algorithm for computing all minimal unsatisfiability-preserving sub-TBox (MUPS) of an ontology for an unsatisfiable con-cept or role in a DL-Lite ontology. We also present a comparison of our algorithm with another representative algorithm. The results indicate that the proposed algorithm is effecient and has an advantage over the previous work.(2) Paraconsistent Query Answering We propose to paraconsitent conjunctive query an-swering (CQA) in DL-Lite and extend the classical framework of query answering over DL-Lite ontologies to a three-valued semantics framework. We present a novel algorithm for paraconsistent query answering over DL-Lite and show that its compu-tational complexity is LOGSPACE in the size of the ABox.(3) Measuring inconsistency degrees of ontologies We propose a fine-gained approach to measuring inconsistency degrees of DL-Lite ontologies based on three-valued se-mantics. For a DL-Lite ontology, we show that it is desirable to consider all individ-uals, ABox and the negative inclusion closure of TBox to measure inconsistency and use them to define an inconsistency degree of a DL-Lite ontology. We present a pre-cise algorithm to compute the proposed inconsistency degree of a DL-Lite ontology and show that it is polynomial with respect to the size of the whole ontology. Unlike the approach that adopts a sequence of values to measure inconsistency in other pa-pers, we define a single value to measure inconsistency of a DL-Lite ontology which is more intuitive to be used as an inconsistency degree than a sequence of values.(4) Measuring inconsistency degrees of membership assertions The inconsistency de-gree of ontologies represents the contradiction that the whole ontology contains. How-ever, it can not tell us that which axiom assertions lead to inconsistency. In order to find the cause of inconsistency, we propose to measure inconsistency for membership assertions. We first give a definition of an inconsistency degree for membership asser-tions in DL-Lite ontologies. Then we present an algorithm to measure inconsistency for membership assertions and show that it is polynomial with respect to the size of the whole ontology.更多还原