模糊描述逻辑本体合取查询研究

摘要

为了在语义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-LiteF,□为例，给出f-DL-Lite系列描述逻辑知识库可满足性的判定算法。在此基础上，重点研究了f-DL-Lite系列知识库的合取查询应答问题，给出f-DLR-LiteF,□知识库合取查询应答的具体步骤和算法，并进行了算法时间复杂性分析，讨论了该合取查询过程的一阶逻辑可归结性。
　　(2)表达能力丰富的f-SH系列模糊描述逻辑合取查询蕴涵的研究。首先，给出了模糊布尔合取查询的语法、语义以及模糊合取查询蕴涵问题的定义。其次，分析了模糊合取查询蕴涵与单个模糊断言蕴涵的区别，以及判定模糊布尔合取查询蕴涵需要先行解决的问题。第三，给出了基于模糊表推演算法的合取查询蕴涵判定算法，证明了算法对于f-SHOIQ的真子逻辑的可靠性、完备性和可终止性，证明了算法对于f-SHOIQ是可靠的，并分析了导致算法不可终止的原因。最后，对于该问题的数据复杂度，证明了当查询中不存在传递角色时其严格的CONP上限。对于联合复杂度，证明了算法关于知识库和查询大小的CO3NEXPTIME时间复杂度上限。
　　(3)基于模糊描述逻辑f-SHOIQ及其子逻辑的知识库可满足性推理算法和f-SHOIQ及其真子逻辑的模糊查询蕴涵算法，设计并实现了首个支持表达能力丰富的模糊描述逻辑合取查询应答的推理机原型系统FReQ。首先，介绍了FReQ所提供的推理服务和查询应答服务。然后，详细描述了FReQ的框架结构及各组成部分的设计与实现，并着重阐述了FReQ推理机的特色和实现过程中所采用的优化技术。最后，比较了优化前后FReQ推理机的性能，并分析其原因。
　　(4)模糊OWL本体合取查询应答问题研究。首先，构建模糊OWL本体与模糊描述逻辑知识库的对应关系。然后，构建模糊SPARQL查询与datalog形式布尔合取查询的对应关系。最后，利用上述对应关系，将模糊OWL本体的查询应答问题归结为相应的模糊描述逻辑知识库的查询蕴涵问题。

目录

声明

摘要

第1章 绪论

1．1 研究背景

1．2 国内外相关研究的现状与分析

1．2．1 模糊描述逻辑研究

1．2．2 描述逻辑合取查询的研究

1．2．3 模糊描述逻辑合取查询的研究

1．2．4 描述逻辑推理机及查询引擎研究

1．3 本文工作

1．3．1 研究内容

1．3．2 论文的组织结构

第2章 相关理论基础

2．1 描述逻辑基础

2．1．1 描述逻辑ALC

2．1．2 常见描述逻辑构件

2．2 模糊集基本理论

2．2．1 模糊集的基本概念

2．2．2 模糊集运算

2．3 模糊描述逻辑f-ALC

2．4 本章小结

第3章 f-DL-Lite合取查询应答

3．1 描述逻辑DL-Lite系列

3．2 模糊描述逻辑f-DL-Lite系列

3．2．1 f-DL-Litecore

3．2．2 f-DL-Litecore扩展

3．3 合取查询语言

3．4 模糊合取查询应答

3．4．1 知识库标准化

3．4．2 知识库可满足性检查

3．4．3 查询重写

3．4．4 top-k应答

3．4．5 完整算法

3．4．6 f-DL-Lite系列合取查询应答算法

3．4．7 算法复杂性分析

3．5 本章小结

第4章 f-SH系列描述逻辑合取查询蕴涵

4．1 模糊描述逻辑f-SH系列

4．1．1 f-SHOIQ语法

4．1．2 f-SHOIQ语义

4．1．3 基本假设

4．2 模糊合取查询语言

4．3 模糊查询蕴涵算法

4．3．1 FL-知识库的完全图

4．3．2 完全图的模型与知识库的模型

4．3．3 在完全图中检查查询蕴涵

4．3．4 模糊推演表与规范模型

4．4 可终止性与复杂度分析

4．5 本章小结

第5章 查询推理机的设计与实现

5．1 功能描述

5．2 GKRSS语法

5．3 结构与设计

5．3．1 语法处理模块

5．3．2 基本推理服务转换器

5．3．3 模糊描述逻辑推理引擎

5．3．4 查询转换器

5．3．5 查询引擎

5．4 优化技术

5．4．1 惰性展开

5．4．2 跟踪

5．4．3 知识库标准化和简化

5．4．4 隶属度规范化

5．5 用户指南

5．6 测试与性能分析

5．7 本章小结

第6章 模糊OWL本体查询

6．1 OWL与DL

6．1．1 OWL DL语法语义

6．1．2 OWL本体推理与描述逻辑推理

6．2 f-OWL

6．3 f-SPARQL

6．3．1 SPARQL介绍

6．3．2 f-SPARQL语法

6．4 模糊本体合取查询

6．4．1 f-OWL到f-SHOIN(D)

6．4．2 f-SPARQL到datalog布尔合取查询

6．4．3 f-OWL本体查询应答到模糊描述逻辑知识库查询蕴涵

6．4．4 本体查询实例

6．5 本章小结

第7章 结束语

7．1 本文的主要贡献与结论

7．2 未来工作

参考文献

致谢

攻博期间参加的科研项目

攻读博士期间发表的文章