郭欣彤, 高 宏

(哈尔滨工业大学 计算机科学与技术学院，哈尔滨 150001)

0 引 言

知识图谱将客观世界中的海量信息以结构化的形式描述，提供了强大的组织、管理和理解互联网海量信息的能力。知识图谱不仅给搜索引擎带来了新的活力，同时也在智能决策中显示出强大威力，是人工智能的重要基石。随着知识图谱被广泛应用于各个领域，在真实SPARQL查询历史中发现很多相似查询。如果一定时间段内的相似查询可以一起处理，就能减少冗余计算，从而大大降低查询响应时间，提高吞吐量。因此，本文研究在知识图谱上的多查询优化问题。

关系数据库上的多查询优化问题是NP-hard，由于SQL与SPARQL二者之间有等价关系，因此RDF/SPARQL上的多查询优化问题也是NP-hard。MQO是关系数据和半结构化数据上的一个经典问题，有很多方法取得了很好的效果。一个很直观的想法是把已有方法推广到RDF数据上，但现有的方法并不能无缝的集成在已有的RDF查询引擎上，主要原因有：

(1)关系数据上的SQL查询通常可以转换成一棵抽象语法树，在树上检测同构的子树较为简单，而SPARQL查询通常表示成图结构，因此公共子结构检测更难；

(2)RDF的物理存储和索引并没有固定的模式，每个系统选用的方法都不同，例如 RDF-3X中使用全索引结构[1]，Jena使用属性表[2]，还有最近很多系统采用的垂直划分方法，这些多样的存储模式和索引选择，使得代价估算不准确，某些情形下优化后的响应时间并不总是小于未优化的；

(3)真实世界中的 SPARQL查询远比关系数据库上的SQL语句复杂，连接更多，这可以通过比较 TPC 测试集和一些RDF测试集得出结论。……