PDF《大规模 RDF 图数据上高效率分布式查询处理》

1 所示. PREFIX yago:?http://dbpediaorg/class/yago/? PREFIX dbp:?http://dbpediaorg/property/? SELECT ?country ?population WHERE{ ?country a yago:LandlockedCountries. ?country dbp:populationEstimate ?population.} Fig.1 An example SPARQL BGP query Q 图1示例 SPARQL BGP 查询 Q 目前,处理大规模 RDF 智能图数据查询的研究工作分为两大类――单机和分布式.单机 SPARQL 查询引擎, 如RDF-3X[5] 和gStore[6] ,采用基于空间换时间策略构建不同的索引方案,利用索引减少查询匹配的搜索空间;

分 布式 SPARQL 查询处理系统以是否采用分解查询图策略分为两类:一类方法将 SPARQL 查询图分解为三元组 模式(triple pattern,至少包含一个变量的三元组)[7?11] 或者带有局部结构信息子图的集合,先对分解后的查询子 图进行匹配,之后对子图的匹配结果进行连接操作获得最终匹配结果;

另一类方法直接处理完整查询图[12?14] ,大500 Journal of Software 软件学报 Vol.30, No.3, March

2019 部分通过图探索减少连接操作的较高代价,通过优化探索计划提高查询性能. 本文将 RDF 图内嵌的语义和结构作为启发式信息(h-值),并利用 h-值将 RDF 查询图分解为星形结构(高度 为1的树)的集合进行匹配.Lai 等人[15] 指出:无向无标签图上基于星形-连接的算法[16] 在评估包含多边的星形时 会生成大量中间匹配结果,如:将包含

3 条边的星形结构匹配到最大度为

1 000 的数据图,产生

109 个匹配结果. 为此,他们提出了基于 MapReduce[17] 的TwinTwigJoin 算法,将查询图分解成 TwinTwig 结构,该结构只包含一条 边或两条相连的边.造成上述问题的根本原因是:顶点和边缺乏可区别信息时,星型结构匹配过程可能会产生大 量的中间结果.但是 RDF 图中的顶点标签是独一无二的 URIs,同时,边是有方向且带标签的,因此,Lai 等人在文 献[15]中提出的问题在 RDF 图中不存在.与分解成 TwinTwig 结构[15] 相比,星形分解策略可以保持更多原始查询 图的信息,同时,在MapReduce 计算模型下可以在更少次 MapReduce 迭代操作内结束查询. 本文的主要贡献如下: (1) 提出了基于 MapReduce 计算模型的有效 SPARQL 基本图模式匹配算法,利用 RDF 智能图数据丰富的 语义和自身的图特性设计星形分解策略,并给出中间结果较少的星形匹配顺序来提高查询效率,每轮 MapReduce 操作按序连接一个星形结构直至匹配结束;

(2) 为进一步提高算法的性能,引入两种优化技术:一个通过基于布隆过滤器的邻居信息编码技术过滤 MapReduce 操作中的无用数据输入,另一个技术推迟笛卡尔积操作以提高查询效率;

(3) 在主流大数据处理框架 Spark 下实现了上述算法,并在标准合成数据集 WatDiv[18] 和真实数据集 DBpedia 上进行了大量实验,验证了算法的有效性、高效性和可伸缩性,并对查询匹配的时间开销与 数据集规模及集群中节点数量的关系进行分析. 本文第

1 节介绍相关工作.第2节介绍 RDF 图和 SPARQL 基本图模式查询的预备知识.第3节描述如何存 储RDF 数据,分解 SPARQL 查询,并在分布式计算框架 MapReduce 下匹配查询.第4节提出两种优化技术:一个 通过基于布隆过滤器的邻居信息编码过滤掉 MapReduce 迭代中无用的数据输入;

另一优化技术将星形匹配过 程中的笛卡尔积推迟到 MapReduce 迭代结束来减少该过程中大量无用的笛卡尔积.第5节在标准合成数据集 和真实数据集上进行实验,并在第