论文部分内容阅读
为了在语义Web中实现知识的可重用性和高度互用性,通常使用本体来表示领域知识。基于本体的知识表示和推理是语义Web的重要组成部分。描述逻辑(Description logics,简称DLs)是一种形式化表示知识的方法,是OWL DL等Web本体语言的理论基础。描述逻辑最显著的特征是其内置的推理机制。利用这一机制,可以由知识库中显式存储的知识推导出隐含的信息。描述逻辑的基本推理服务包括知识库可满足性检查、概念包含检查和实例检索等。为了表示语义Web应用中广泛存在的模糊和不精确信息,已有大量的研究工作致力于描述逻辑的模糊扩展,并设计出符合模糊描述逻辑特性的推理服务,开发出相应的推理算法和推理机系统。在数据密集型的应用中,描述逻辑知识库和本体的查询占据着重要的位置。实例检索等简单形式的查询表达能力相对较弱,无法有效地表达用户的查询意图。源于数据库领域的合取查询(conjunctive queries, CQs),近来被视为查询和访问描述逻辑知识库的一种理想形式,它提供了比实例检索表达能力更丰富的查询语言。通过对国内外在描述逻辑模糊扩展、(模糊)描述逻辑合取查询、(模糊)描述逻辑推理机和查询引擎实现等方面研究现状的分析,发现现有的模糊描述逻辑知识库合取查询研究存在以下问题:(1)对于轻量级模糊描述逻辑f-DL-Lite系列,现有文献通常只针对其中的某一种逻辑语言,而并未系统地讨论整个语言系列的推理和查询应答问题。(2)现有的查询蕴涵算法无法处理表达能力丰富且应用广泛的f-SH系列模糊描述逻辑的合取查询蕴涵及合取查询应答问题。(3)现有模糊描述逻辑推理机不支持表达能力丰富的模糊描述逻辑知识库的合取查询应答。(4)现有的讨论模糊描述逻辑合取查询应答问题的文献并未深入讨论算法的复杂性问题和算法优化问题。为此,本文深入研究了轻量级模糊描述逻辑f-DL-Lite系列的推理和查询应答问题,表达能力丰富的f-SH系列模糊描述逻辑知识库合取查询蕴涵问题,支持模糊描述逻辑合取查询的推理机原型系统的设计与实现,以及模糊OWL DL本体查询应答问题到模糊描述逻辑合取查询蕴涵问题的归结。具体研究内容包括以下几个方面:(1)系统研究了f-DL-Lite系列描述逻辑的合取查询应答问题。首先,给出该类逻辑的语法、语义以及知识库的形式化定义。然后,以f-DLR-LiteFn为例,给出f-DL-Lite系列描述逻辑知识库可满足性的判定算法。在此基础上,重点研究了f-DL-Lite系列知识库的合取查询应答问题,给出f-DLR-LiteF,知识库合取查询应答的具体步骤和算法,并进行了算法时间复杂性分析,讨论了该合取查询过程的一阶逻辑可归结性。(2)表达能力丰富的f-SH系列模糊描述逻辑合取查询蕴涵的研究。首先,给出了模糊布尔合取查询的语法、语义以及模糊合取查询蕴涵问题的定义。其次,分析了模糊合取查询蕴涵与单个模糊断言蕴涵的区别,以及判定模糊布尔合取查询蕴涵需要先行解决的问题。第三,给出了基于模糊表推演算法的合取查询蕴涵判定算法,证明了算法对于f-SHOIQ的真子逻辑的可靠性、完备性和可终止性,证明了算法对于f-SHOIQ是可靠的,并分析了导致算法不可终止的原因。最后,对于该问题的数据复杂度,证明了当查询中不存在传递角色时其严格的CONP上限。对于联合复杂度,证明了算法关于知识库和查询大小的C03NEXPTIME时间复杂度上限。(3)基于模糊描述逻辑f-SHOIQ及其子逻辑的知识库可满足性推理算法和f-SHOIQ及其真子逻辑的模糊查询蕴涵算法,设计并实现了首个支持表达能力丰富的模糊描述逻辑合取查询应答的推理机原型系统FReQ。首先,介绍了FReQ所提供的推理服务和查询应答服务。然后,详细描述了FReQ的框架结构及各组成部分的设计与实现,并着重阐述了FReQ推理机的特色和实现过程中所采用的优化技术。最后,比较了优化前后FReQ推理机的性能,并分析其原因。(4)模糊OWL本体合取查询应答问题研究。首先,构建模糊OWL本体与模糊描述逻辑知识库的对应关系。然后,构建模糊SPARQL查询与datalog形式布尔合取查询的对应关系。最后,利用上述对应关系,将模糊OWL本体的查询应答问题归结为相应的模糊描述逻辑知识库的查询蕴涵问题。