分布式查询处理：大规模RDF图数据的高效解决方案

"大规模RDF图数据上高效率分布式查询处理" 本文主要探讨了在处理大规模RDF图数据时如何实现高效率的分布式查询处理。RDF（Resource Description Framework）是一种用于表示网络数据的标准模型，广泛应用于构建知识图谱。随着知识图谱的发展，RDF图数据量日益增大，对查询性能提出了更高的要求。SPARQL是针对RDF数据的查询语言，其查询语义对应于图同态，属于NP-完全问题，因此在大规模数据上执行SPARQL查询具有相当的复杂性。 文章指出，现有的MapReduce框架虽然能处理大规模数据，但在处理RDF查询时，由于未能充分利用RDF数据的语义和图结构特性，往往导致过多的迭代次数，从而影响效率。为解决这一问题，作者提出了一种新的基于星形分解的分布式SPARQL查询处理算法。 该算法首先利用RDF数据内部蕴含的语义和结构信息，将复杂的查询图分解为星形结构的集合。星形结构在RDF图中常见且易于处理，这样的分解可以减少MapReduce的迭代次数，提高查询效率。接着，算法设计了一种能产生较少中间结果的星形匹配顺序，使得每次MapReduce操作能匹配一个新的星形，逐步逼近最终答案。 实验部分，该方法在WatDiv合成数据集和真实的DBpedia数据集上进行了大量测试，结果显示提出的星形分解算法能显著提升查询效率，查询时间平均比现有SHARD和S2X算法快一个数量级。进一步地，优化后的算法相比于基础算法，查询时间缩短了49.63%至78.71%，显示出良好的性能优化效果。 关键词：星形分解、分布式、基本图模式匹配、大规模RDF图、MapReduce 中图法分类号：TP311 中文引用格式：王鑫, 徐强, 柴乐乐, 杨雅君, 柴云鹏."大规模RDF图数据上高效率分布式查询处理". 软件学报, 2019, 30(3): 498−514. [doi:10.13328/j.cnki.jos.005696]