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

An RDF query algorithm based on tree search

作　　者：刘江江 董荣胜 LIU Jiangjiang;DONG Rongsheng(School of Computer and Information Security,Guilin University of Electronic Technology,Guilin 541004,China)

机构地区：[1]桂林电子科技大学计算机与信息安全学院,广西桂林541004

出　　处：《桂林电子科技大学学报》2021年第5期393-399,共7页Journal of Guilin University of Electronic Technology

基　　金：国家自然科学基金(61762024);广西自然科学基金(2017GXNSFDA198050)。

摘　　要：针对海量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具有良好的扩展性和查询性能。To improve the query efficiency of massive RDF data, a tree search-based RDF query algorithm—RI-Triples is proposed. This algorithm transforms the RDF query problem into a subgraph homomorphism problem. In the data preprocessing stage, four indexes, namely adjacency list, inverse adjacency list, P-In and P-Out, are constructed to reduce the candidates of variable nodes in the query graph. Before the matching, RI-Triples generates a node matching sequence sorted by constraint for the query graph based on greedy strategy to reduce the search space during the matching phase. In the matching phase, the search space tree composed of the node matching sequence and the RDF data graph is traversed based on the depth first, and the infeasible branches are pruned by the subgraph homomorphism constraint. The experiment uses the RDF test benchmark LUBM. For the LUBM6 M, LUBM13 M and LUBM33 M datasets, the query time of RI-Triples is 0.59, 0.54 and 0.74 times that of gStore, and 0.24, 0.27 and 0.34 times that of RDF-3 X, respectively. Experiments show that RI-Triples has good scalability and query performance.

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

分 类 号：TP391.4[自动化与计算机技术—计算机应用技术]