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

6 节对全文总结.

1 相关工作 近年来,研究者逐步意识到图数据管理的重要性,高效处理 RDF 数据已成为该方向的研究热点之一.本节将 对目前已有的大规模 RDF 数据上 SPARQL 查询研究工作进行介绍,主要分为以下两类. 1.1 单机系统上的RDF图查询处理 RDF-3X 查询引擎[5] 采用原生态的三元组存储模式,将RDF 数据和按照 SPO 排列的

15 种SPO(包含 SPO 中1,2 或3个)索引压缩存储在 B+ -树中,以冗余存储提高查询性能.该方法通过自底向上的动态规划算法选择出 代价最优的连接顺序.另外,RDF-3X 收集单个实体的统计信息,大量使用合并连接来换取较高查询效率. gStore[6] 是基于图的单机 SPARQL 查询引擎,使用邻接链表存储 RDF 图,并将顶点类和实体用固定长度的比特 串编码压缩存储,通过建立 VS*-树索引结构提高查询处理效率并采用剪枝策略减少搜索空间. 随着 Tim Berners-Lee 发起的 Linked Data 运动的持续推进,各个领域发布的 RDF 数据一直持续增长,数据 规模达到百亿级.单机已经无法有效处理现有规模 RDF 数据上的 SPARQL 查询[19] ,分布式/并行技术已成为 RDF 数据管理不可或缺的工具. 1.2 分布式系统上的RDF图查询处理 近年来,大量研究者和实践者提出了若干种方法分布式处理大规模 RDF 图上的 SPARQL 查询问题,分两类 叙述. (1) 分解查询图. SHARD[7] 基于三元组存储处理 RDF 数据集上的 SPARQL 查询,查询图被分解为三元组模式(包含变量的三 王鑫 等:大规模 RDF 图数据上高效率分布式查询处理

501 元组,即一个查询子句)的集合,通过在三元组模式上迭代将变量绑定到数据图的顶点,该绑定必须同时满足查 询中的所有约束.每一轮 MapRedue 操作通过连接操作只添加一个查询子句.类似地,HadoopRDF[8] 中查询图的 最小分解单位也是三元组模式,并且它也使用 MapReduce 计算框架将 RDF 三元组基于谓语划分到多个小文件 中.SPARQL 查询中的一个子句,也就是一个三元组模式,只能同时参与到一个 Hadoop 作业中.这两种方法都没 有使用查询图的结构信息,需要过多的 MapReduce 迭代操作,并且大量的连接操作导致很高的查询代价.而本文 利用部分图的结构特性,在每次 MapReduce 迭代中添加一个星形,可以在更少的迭代次数内完成查询匹配,从而 提高查询效率.同样地,S2X[9] 虽然建立在分布式图计算框架 GraphX[20] 上实现 SPARQL 的BGP 匹配,查询图也 被分解成查询子句,也就是三元组模式.首先,BGP 查询中所有的三元组模式被匹配;

其次,通过迭代计算逐渐舍 弃部分中间结果;

最后,将剩余的匹配结果进行连接操作,这一阶段可能会导致大量的中间结果.另外,Virtuoso[10] 和S2RDF[11] 基于关系数据库处理 RDF 图查询,将SPARQL 查询子句转化为 SQL 语句,通过关系表的连接操作 得到匹配结果.S2RDF[11] 引入关系划分模型 ExtVP 存储 RDF 数据,该方法基于 Spark[21] 并行计算框架,可以有效 最小化查询输入大小.但是 ExtVP 存储方案的预处理需要提前在垂直划分表上作大量的连接操作,代价非常高. 本文将 RDF 图分布式存储在多个邻接链表中,可以同时在各个主语顶点的邻接链表上并行进行 MapReduce 计算,加快查询处理. (2) 完整查询图. Trinity.RDF[12] 将RDF 数据模型化为原始图的形式,并使用键-值存储 RDF 数据,将顶点标识符作为键,顶点 的邻接链表作为值.采用基于代价的方法找到最优探索计划,利用图探索而不是连接操作减少中间结果量,但是 最终结果需要在集群中心节点上使用单线程获得.此外,Peng 等人[13] 采用局部计算和装配的分布式框架基于 gStore 执行 SPARQL 查询.在局部计算阶段,集群中每个节点匹配完整查询,然后在装配阶........