论文部分内容阅读
随着RDF (Resource Description Framework)数据模型的广泛应用,万维网上越来越多的数据正在以RDF数据模型表示。在过去的十年间,RDF数据查询处理技术的研究重心主要集中于集中式单节点的RDF数据存储、索引及查询优化等问题上。然而,鉴于RDF数据持续快速的增长,集中式单节点的RDF数据查询处理系统无论是存储能力还是计算能力都已经无法满足需求,这使得研究分布式可扩展的RDF数据查询处理技术成为一种必然的趋势。与传统集中式单节点的RDF数据查询处理系统相比,分布式RDF数据查询处理的最大区别是将原来集中存储的RDF数据分散存储到多个通过网络连接的存储/计算节点中,以获得更大的存储容量和更高的并行处理能力。然而,数据分布式存储的引入,对提高RDF数据查询处理性能带来了新的挑战。在分布式环境下,查询处理过程中所产生的中间结果都需要通过网络传输到各个计算节点中。这使得网络通信开销成为影响分布式查询处理性能的主要因素之一。从这个核心问题出发,围绕分布式RDF数据查询处理的关键技术展开广泛深入的研究。首先,在分布式RDF数据查询处理过程中,RDF数据的划分技术在很大程度上影响着网络通信开销的大小。传统的RDF数据哈希划分算法无法利用RDF数据语义关联信息,导致网络通信开销较大,严重影响分布式SPARQL (Simple Protocol and RDF Query Language)查询处理性能。针对此问题,提出一种基于语义关联的RDF数据划分技术。该技术首先分析并抽取RDF数据的语义关联信息,并结合语义关联信息提出一种混合式的RDF数据划分算法。为了进一步提高分布式查询处理性能,采用轻量级的辅助信息传递策略对分布式连接运算的输入数据进行有效地过滤,从而达到降低分布式连接运算处理开销的目的。通过使用标准测试集LUBM (Lehigh University Benchmark)对基于语义关联的RDF数据划分技术进行性能测试,实验结果表明该技术显著地提升了查询处理性能。其次,由于RDF图结构复杂,相应地,SPARQL查询也会涉及到图结构复杂的连接操作。在处理此类SPARQL查询时,如果没有针对复杂图结构精心设计的数据划分算法,分布式连接运算所引起大量的网络通信开销会严重影响查询处理性能。针对此问题,提出一种面向复杂图结构的RDF数据划分技术。通过分析RDF图和SPARQL结构的特征,该技术采用基于路径的RDF数据划分模型,并根据RDF数据划分的评判标准抽象出基于路径的RDF数据划分优化问题。由于此优化问题是NP-Hard问题,设计高效的路径划分近似算法解决此问题。自底向上的路径合并算法可以进一步降低时间和空间复杂度。通过多种广泛使用的标准测试集对面向复杂图结构的RDF数据划分技术进行查询性能测试,实验结果表明采用该技术可以将查询性能提升1~3个数量级。最后,查询特征感知的SPARQL查询优化技术通过制定优秀的查询执行计划,可以从另一个方面解决网络通信开销的问题。具体来说,结合一种通用的RDF数据划分模型,使得该技术可以兼容现有的RDF数据划分技术。基于此模型,该技术设计一种高效的查询执行计划枚举算法计算生成最优的查询执行计划。此外,为了高效地处理结构复杂的查询,该技术还提出一种剪枝策略来缩小搜索空间和一种查询图简化算法降低查询图的规模。查询特征感知的SPARQL查询优化技术可以自主地分析查询特征并为之提供最适合的查询优化算法计算查询执行计划。大规模实验结果表明查询特征感知的SPARQL查询优化技术无论在计算最优查询执行计划的效率方面,还是在提升查询处理性能方面都有十分优异的表现。