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

摘要：

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

关键词：RDF查询;SPARQL;查询优化;子图同态

所属期刊栏目：41

分类号：TP391.4(计算技术、计算机技术)

资助基金：国家自然科学基金;广西自然科学基金

在线出版日期：2022-01-10（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：393-399