面向图数据的结构化正则路径查询方法  

Efficient method of structured regular path query for graph data

作　　者：邱涛 王屿涵 邓国鹏 孙尧[2] 吕光华 夏秀峰 Qiu Tao;Wang Yuhan;Deng Guopeng;Sun Yao;Lyu Guanghua;Xia Xiufeng(School of Computer Science,Shenyang Aerospace University,Shenyang 110136,China;Shenyang Aircraft Industry(Group)Co.Ltd.,Shenyang 110034,China)

机构地区：[1]沈阳航空航天大学计算机学院,沈阳110136 [2]沈阳飞机工业(集团)有限公司,沈阳110034

出　　处：《计算机应用研究》2023年第10期3022-3027,共6页Application Research of Computers

基　　金：国家自然科学基金资助项目(62002245);辽宁省自然科学基金资助项目(2022-BS-218)。

摘　　要：正则路径查询是一种应用正则表达式在图数据上进行查询的技术,通常利用有限状态自动机实现查询匹配。现有正则路径查询方法的匹配结果为顶点对的序列,未能充分保留图的结构,为了解决这一问题,提出了一种面向图数据的结构化正则路径查询方法,通过在不同的序列间加以结构化约束,使得查询结果由路径转变为子图。为了实现这一目的,首先定义了一种结构化的正则路径查询语言,并设计了结构化的查询解析以及基于此结构的匹配算法。实验在模拟数据集和真实数据集上进行了测试与分析,验证了网络规模对查询速度的影响,并设置了对照实验。实验结果表明,提出方法能够在保证满足正则表达式约束的前提下实现结构化查询。Regular path query is a technique of using regular expressions to query graph data,usually uses finite state automata to achieve query matching.The matching result of the existing regular path query method is a sequence of vertex pairs,and the structure of the graph is not fully preserved.In order to solve this problem,this paper proposed a method of structured regu-lar path query for graph data.By structuring constraints between different sequences,the query results could be transformed from paths to subgraphs.For this purpose,the method firstly defined a structured regular path query language,and then designed a structured query parsing and a matching algorithm based on this structure.Experimental results on simulated and real datasets verify the influence of network size on query speed.This paper compared the proposed method with the control group.Experimental results show that the proposed method can realize structured query under the premise of satisfying regular expression constraints.

关 键 词：正则路径查询 图数据 有限状态自动机 子图匹配 

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