缺失和不一致数据环境下描述逻辑查询回答的高效方法研究

Description logics are important knowledge representation languages that underpin the next generation World Wide Web called Semantic Web. Query answering is a core reasoning mechanism in description logics, which has been widely applied in a variety of domains. However, the existing mechanism for query answering cannot handle missing data and inconsistent data. The existence of missing data will result in incomplete query answers, while the existence of inconsistency will even make query results meaningless. To address these two important problems in query answering, this project will study a new mechanism for query answering over an inconsistent DL knowledge base that contains missing data. The mechanism is a combination of abductive reasoning in description logics and inconsistency-tolerant reasoning in description logics. In more details, this project will study the syntax, semantics and computational complexity of the new mechanism, as well as study feasible methods for realizing this mechanism and ranking methods for the query answers generated by the mechanism. Considering that both abductive reasoning and inconsistency-tolerant reasoning have a high computational complexity, this project will also study approximate methods to make the new mechanism scale to very large DL knowledge bases. To verify the practicality of the new mechanism, this project will also apply it to a concrete application in the e-tourism domain. The mechanism and its methods studied in this project can be directly applied to a variety of DL based scenarios about information search and matchmaking, making the existing Web information more valuable.

描述逻辑是重要的知识表达语言，是下一代万维网语义Web的基础。查询回答是描述逻辑中的核心推理机制，在各个领域中有着广泛的应用。但是现有的查询回答机制不能处理缺失数据和不一致数据。缺失数据的存在导致查询答案不完备，而不一致查询不能返回有意义的结果。为了解决这两个重要问题，本项目研究一种在带有缺失数据的不一致描述逻辑知识库中进行查询回答的新机制。该机制结合了描述逻辑中的溯因推理机制和不一致容忍查询机制。更具体地，本项目研究该新机制的形式、语义和计算复杂度，研究实现该机制的可行方法，研究该机制下查询答案的排序方法。鉴于溯因推理和不一致容忍查询都具有较高的计算复杂度，本项目还研究实现该新机制的近似方法，使其能够用于大规模的描述逻辑知识库。此外，本项目以电子旅游为具体的应用场合，验证该机制的实用性。项目的研究成果能够直接应用于各种基于描述逻辑的信息搜索和匹配场合，提高万维网信息的使用价值。

基于描述逻辑的查询回答已有广泛的应用，但现有的查询回答机制不能处理缺失数据和不一致数据。缺失数据的存在导致查询答案不完备，而不一致查询不能返回有意义的结果。为了解决这两个重要问题，本项目研究一种在带有缺失数据的不一致描述逻辑知识库中进行查询回答的新机制——溯因查询回答机制。这种机制可以直接作用于任意给定的描述逻辑知识库，而不需要事先为知识库补充数据或将知识库转成一致的。我们提出了不一致描述逻辑知识库中溯因查询答案的语义，该语义使用特定的最小溯因解释来定义。我们提出了求解查询答案及其对应最小溯因解释的高效方法，其中针对一阶可重写描述逻辑知识库，我们提出了数据复杂度多项式时间的分层次计算的精确方法，而针对其他任意的描述逻辑知识库，我们提出了基于有限辩解模式集合的近似方法。上述方法的效率和可扩展性都已经在千万公理级别的大型描述逻辑知识库中得到验证。对于溯因查询答案的排序，我们提出了三种最近邻算法和用于评估答案对应最小溯因解释真实程度的知识表示学习方法。这种方法都可以应用于溯因查询答案的排序。我们分别在汽车导购和租房服务领域进行了应用实践，初步验证了溯因查询回答机制的实用性。项目已申请1项已标注的国家发明专利，发表已标注的相关学术论文14篇，包括中国计算机学会推荐A类学术会议论文3篇（AAAI2014、AAAI2015和AAAI2017）、中国计算机学会推荐B类学术会议论文3篇（CIKM2014、CIKM2015和ISWC2015）、中国计算机学会推荐C类学术会议论文3篇（KSEM2015、APWEB2015、APWEB2016），其他EI检索学术论文5篇。项目的研究成果能够直接应用于各种基于描述逻辑的信息搜索和匹配场合，提高万维网信息的使用价值。