基于RDF图结构切分的高效子图匹配方法  

Efficient subgraph matching method based on structure segmentation of RDF graph

作　　者：关皓元 朱斌[1] 李冠宇[1] 赵玲 GUAN Haoyuan;ZHU Bin;LI Guanyu;ZHAO Ling(Faculty of Information Science ＆ Technology,Dalian Maritime University,Dalian Liaoning 116026,China)

机构地区：[1]大连海事大学信息科学技术学院,辽宁大连116026

出　　处：《计算机应用》2018年第7期1898-1904,1909,共8页journal of Computer Applications

基　　金：国家自然科学基金资助项目(61371090)~~

摘　　要：针对在SPARQL查询处理中,随着查询图结构逐渐复杂而导致基于图的查询效率愈发低下的问题,通过分析几种资源描述框架(RDF)图的基本结构,提出了一种基于查询图结构切分的子图匹配方法——RSM。首先,将查询图切分为若干结构简单的查询子图,并通过相邻谓词结构索引来定义查询图节点的搜索空间;然后,通过相邻子图结构来缩小搜索空间范围,在数据图中根据搜索空间中的搜索范围找到符合的子图结构;最后,将得到的子图进行连接并作为查询结果输出。将RSM与RDF-3X、R3F、GraSS等主流查询方法作比较,对比了各方法在不同数据集上对于复杂程度不同的查询图的查询响应时间。实验结果充分表明,与其他3种方法相比,在处理结构复杂的查询图时,RSM的查询响应时间更短,具有更高的查询效率。With the complexity increasing of query graph structure, the efficiency of graph-based query in SPARQL query processing becomes lower and lower. By analyzing the basic structure of Resource Description Framework （RDF） graph, a subgraph matching method based on structure segmentation of query graph, called RSM （RDF Subgraph Matching）, was proposed. Firstly, a query graph was divided into several simple query subgraphs, and query graph node searching space was defined through structure index of adjacent predicate. Secondly, the searching space was narrowed down by the adjacent subgraph structure, and a matchable subgraph could be found in data graph according to the searching area in the searching space. Finally, the result graph was output by joining related subgraphs. The query response times of RSM, RDF-3X, R3F and GraSS on query graphs with different structural complexity in different data sets were compared. The experimental results show that, compared with the other three methods, RSM has a shorter query response time and higher query efficiency in processing complex query graphs.

关 键 词：SPARQL查询处理 资源描述框架 子图匹配 结构切分 搜索空间 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]