计算机应用研究

作者：邱涛,王屿涵,邓国鹏,孙尧,吕光华,夏秀峰,

单位：1.沈阳航空航天大学计算机学院,沈阳110136；2.沈阳飞机工业(集团)有限公司,沈阳110034；

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

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

正则路径查询是一种应用正则表达式在图数据上进行查询的技术，通常利用有限状态自动机实现查询匹配。现有正则路径查询方法的匹配结果为顶点对的序列，未能充分保留图的结构，为了解决这一问题，提出了一种面向图数据的结构化正则路径查询方法，通过在不同的序列间加以结构化约束，使得查询结果由路径转变为子图。为了实现这一目的，首先定义了一种结构化的正则路径查询语言，并设计了结构化的查询解析以及基于此结构的匹配算法。实验在模拟数据集和真实数据集上进行了测试与分析，验证了网络规模对查询速度的影响，并设置了对照实验。实验结果表明，提出方法能够在保证满足正则表达式约束的前提下实现结构化查询。

来源：2023年第10期

《计算机应用研究》期刊编辑部

查看计算机应用研究杂志2023年第10期