一种基于树搜索的RDF查询算法

摘要

针对海量RDF数据的查询效率问题,提出一种基于树搜索的RDF查询算法—RI-Triples。该算法将RDF查询问题转化为子图同态问题。在数据预处理阶段,分别构建了邻接表、逆邻接表、P-In和P-Out四种索引,以减少查询图中变量节点的候选域。在匹配阶段之前,RI-Triples基于贪心思想为查询图生成一个按照约束大小排序的节点匹配序列,以减少匹配阶段的搜索空间。在匹配阶段,基于深度优先遍历节点匹配序列与数据图所构成的搜索空间树,通过子图同态约束修剪搜索空间树中不可行的分支。实验使用RDF测试基准LUBM,对于LUBM6M、LUBM13M和LUBM33M数据集,RI-Triples的查询时间分别为gStore的0.59、0.54和0.74倍,为RDF-3X的0.24、0.27和0.34倍。实验结果表明,RI-Triples具有良好的扩展性和查询性能。

关键词

RDF查询 / SPARQL / 查询优化 / 子图同态