论文部分内容阅读
近年来,互联网上产生了大量的RDF数据,并且形成了许多以RDF数据为知识单元的大规模开放知识库或者垂直领域知识库。为了发挥RDF数据的实用价值,基于知识库的查询回答技术逐渐成为人工智能和数据库领域广泛的研究热点。然而,在人们热衷于提高查询回答技术的质量和效率时,很少有人针对查询回答系统在无法得出好的结果时给出合理的解释。特别地,当查询回答系统返回的查询结果中缺失了用户期望的结果时,系统自身无法提供一种解释机制来告诉用户为什么他们期望的答案没有出现在结果集中,因此用户只能通过修改查询条件进行不断的试错来探索原因。由于RDF数据具有和关系表不同的数据结构,并且具有更加丰富的结构和语义信息,导致现有的基于关系数据库的解释模型无法直接用来处理RDF数据上的why-not问题。针对上述问题,本文提出一种统一的基于图匹配的解释框架,并采用贪心搜索和模拟退火两种近似策略来计算解释,为处理用户在RDF数据上针对基本图模式的SPARQL查询提出的why-not问题提供了高效的求解算法,从而满足用户更高层次的信息需求。具体而言,本文的主要工作以及贡献包含如下几点内容:(1)提出了一种统一的基于图匹配的解释框架,将RDF数据上的why-not问题转换成一个图匹配的问题。并且根据查询分解方式的不同,分别提出星匹配和路径匹配两种方式来计算解释。此外,在匹配的过程中引入了一种相似度评分机制,充分考虑了查询和数据模式之间的结构和语义信息,从而保证生成尽可能合理的解释。(2)针对两种图匹配的算法分别提出了贪心搜索和模拟退火两种近似策略,从而避免在使用图匹配求解why-not问题所面临的指数级复杂度。虽然通过近似求解策略可能会降低问题的解的准确度,但在很大程度上可以提升算法的效率。(3)实现了本文提出的算法,并在大规模开放数据集上通过实验分析了图匹配算法的效率,以及计算出的解释的合理程度。实验结果表明,本文提出的算法相比现有最好的工作更加高效,并且能提供给用户更高质量的解释。