基于资源描述框架图切分与顶点选择性的高效子图匹配方法

发布时间：2021-01-20 04:16

　　在SPARQL查询过程中,含有复杂结构的资源描述框架（RDF）图的查询效率低下。为此,通过分析几种RDF图的基本结构与RDF顶点的选择性,提出RDF三元组模式选择性（RTPS）——一种基于RDF顶点选择性的图结构切分规则,以提高面向RDF图的子图匹配效率。首先,根据谓词结构在数据图与查询图中的通性建立RDF相邻谓词路径（RAPP）索引,将数据图结构转化为传入-传出双向谓词路径结构以确定查询顶点的搜索空间,并加快顶点的过滤;接着,通过整数线性规划（ILP）问题计算建模将复杂RDF查询图结构分解为若干结构简单的查询子图,通过分析RDF顶点在查询图中的相邻子图结构与特征,确立查询顶点的选择性以确定最优切分方式;然后,通过RDF顶点选择性与相邻子图的结构特征来缩小查询顶点的搜索空间范围,并在数据图中找到符合条件的RDF顶点;最后,遍历数据图以找到与查询子图结构相匹配的子图结构,将得到的子图进行连接并将其作为查询结果输出。实验采用控制变量法,比较了RTPS、RDF子图匹配（RSM）、RDF-3X、Gra SS与R3F的查询响应时间。实验结果充分表明,与其他4种方法相比,当查询图复杂度高于9时,R... 

【文章来源】：计算机应用. 2019,39(02)北大核心

【文章页数】：10 页

【部分图文】：

ＲDF数据图示例Fig．3ExampleofＲDFdatagraph从定义1与定义2对谓词的

闪教跷酱事肪?组成了ＲDF顶点的相邻谓词结构，根据ＲAPP索引，对ＲDF顶点的相邻谓词结构定义如下。定义4ＲDF顶点的相邻谓词结构。以APS(v)=〈v，p，p'，ppl〉来表示数据图中ＲDF顶点的相邻谓词结构。其中:v是当前ＲDF顶点;p是顶点的传入谓词结构;p'是顶点的传出谓词结构;ppl为传入谓词路径与传出谓词路径的最大长度，基于本文的ＲAPS索引的深度为3，ppl的范围设置为ppl=∈{1，2}。根据ＲAPP索引树中的谓词路径结构，将图3数据图中的ＲDF顶点分类存储到相应的Vlist中，存储结果如表1所示。在本文的方法中，ＲAPP索引树的深度为3(MaxL=2)，即谓词路径的最大长度为2，这样可以避免因谓词种类关联过多而产生的存储空间冗余。2．3确定查询顶点的搜索空间在ＲAPP索引建立后，通过索引在数据图中进行ＲDF顶点的遍历，将顶点根据与其相连的谓词结构分类存储到ＲAPP索引树中的谓词节点上，根据查询图中查询顶点的相邻谓词结构来定义查询顶点的初始搜索空间。本文引用了gStore［16］中提出的子图匹配原则定理，引理如下:引理1子图匹配原则定理。在面向ＲDF的子图匹配中，一个查询顶点的绑定顶点，其标签值、与其相连的谓词结第2期关皓元等:基于资源描述框架图切分与顶点选择性的高效子图匹配方法363


本文编号：2988352