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

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

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

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

中图分类号：TP311.12 文献标志码：A 文章编号：1001-3695（2023）10-021-3022-06

doi：10.19734/j.issn.1001-3695.2023.02.0079

Efficient method of structured regular path query for graph data

Qiu Tao1， Wang Yuhan1， Deng Guopeng2， Sun Yao2， Lyu Guanghua2， Xia Xiufeng1

（1.School of Computer Science， Shenyang Aerospace University， Shenyang 110136， China; 2.Shenyang Aircraft Industry （Group） Co. Ltd.， Shenyang 110034， China）

Abstract：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.

Key words：regular path query; graph data; finite state automaton; subgraph matching

0 引言

隨着信息社会的发展，在图数据中实现高效、准确并且可扩展的查询已经引起越来多的关注和研究。正则路径查询最早用于文本上的查询，近年来作为一种面向图数据的查询方法，已经成为检测、分析数据的重要手段。正则路径查询能够对图数据中满足某种查询模式实现匹配，得到满足查询中约束条件的结果序列，具有快速、准确的特点，因此被广泛地应用到生物信息检索［1］、社交推荐系统［2］等各个领域。

目前，基于正则路径查询的工作主要有带标签约束的可达性查询问题和根据完整的正则表达式进行查询匹配的问题，前者常常应用与可达性算法中的部分优化技术，后者主要是基于状态自动机的方法，将正则表达式解析为对应的状态自动机，可进一步指导图上的搜索，获得图中满足该正则表达式的路径相连接的“源—目标”顶点对的序列。例如，某社交软件的网络图描述了若干用户构成的关系网，通过正则路径查询，不仅可以验证该网络图中存在的某种关系，还能够查询满足该关系的两个实体（该模式下两个顶点之间的可达性）。

由于图数据使用图的方式来表现数据对象之间的联系，而正则路径查询仅能进行路径匹配，匹配结果仅仅为多条由图中顶点和边构成的路径组成的序列，虽然匹配结果中的每一条路径各自满足正则表达式的语义，却无法在路径间进行有效的结构化约束，将结果表示成网状结构。

为了描述路径之间的关系，体现查询的结构性，本文提出在图上进行结构化的正则路径查询方法。该方法基于正则路经查询，通过路径间的结构化约束模式生成由若干路径构成的关系网，在图中表示为一种结构（如在社交网络图中由关系“父子”“母子”“夫妻”构成的结构——“家庭”），因此该方法对于路径之间的关系能进行有效描述。本文的主要贡献如下：

a）定义了一種结构化正则路径查询语言来描述结构化正则路径查询，在保留正则表达式约束的同时，在路径之间加以结构化约束，规定了某两条路径之间也满足某种关系。

b）提出了结构化的正则路径查询解析，定义了非确定性有穷自动机（SNFA）作为查询执行的载体，该查询解析体现了结构化查询语言的特殊性。

c）设计了基于图上深度优先遍历的自动机匹配方法。SRPQMatch算法能够根据输入的数据图和自动机进行查询结果的反馈；基于递归的算法getNextState用于记录查询中间结果和监控自动机运行状态；isParallelState算法可实现对路径之间约束的处理。通过该方法能够分别从正则表达式约束和路径结构化约束两个维度实现结构化查询，同时保证匹配结果的准确性和匹配过程高效性。

1 相关工作

图数据是一种使用图结构进行语义查询的数据库，使用顶点、边和属性来表示和存储数据，其中顶点表示现实中的实体，顶点之间的边可表达实体之间的联系。与传统关系型数据相比，图数据在处理海量数据关联关系时具有非常高的性能优势，能够快速找到实体间的深度关联关系且数据模型非常灵活，可以轻松实现添加或删除顶点、边，扩充或者缩小图模型。此外，图数据模型非常敏捷直观，降低数据挖掘和业务开发门槛，提供生产开发效率。

目前，对图数据的描述主要有属性图模型和RDF（资源描述框架）图模型［3］两种数据模型，前者实际上仍然采用“键—值”的形势进行存储，顶点上具有属性表，代表查询语言有Cypher、Gremlin等，代表系统有Neo4j等；后者是从语义网演变而来的，采用的结构是“主谓宾”形式的三元组，代表查询语言有SPARQL［4］，代表系统有gStore［5］等。Bornea等人［6］描述了一种新的RDF存储和查询机制，在现有关系表示的基础上将RDF分解成关系；Abadi等人［7］研究了当前RDF数据管理解决方案扩展性差的原因，并探讨了这些方法的基本可扩展性的局限性。RDF-3X引擎［8］基于SPARQL实现了卓越的性能。Weiss等人［9］提出了一种RDF存储方案，将三元组扩展到六元，增强了RDF数据管理的效率和可扩展性。Peng等人［10］提出了在分布式环境中通过大型RDF图处理SPARQL查询的技术，通过在RDF图的每个片段中引入局部部分匹配作为部分答案。

正则路径查询是在图数据上进行查询的重要技术，目的是找到有向数据图中满足正则表达式约束的路径集合，每条路径以顶点对的形式表示，表示这两点之间存在至少一条满足正则表达式约束的路径。Libkin等人［11］将图数据库典型查询语言与数据查询的标准关系机制结合，提出了面向图数据的正则路径查询。目前，已有很多应用于系统上的正则路径查询算法：Zhang等人［12，13］对查询的正则表达式进行划分，首先处理最长的固定谓词序列，然后再对包含闭包的子表达式进行处理。Yakovets等人［14］提出WavePlan，为1.1版本的SPARQL查询构建了基于成本的优化器，从而进行有效的优化和评估。Koschmieder等人［15，16］提出使用RareLabel的方法，采用分治策略将完整的正则路径查询划分成若干规模较小的子查询，在自建的图数据索引上进行双向的广度优先遍历。

子图匹配本质上是在一张图上找到另一张图的所有匹配，又称为子图同构，其判定和列举所有子图匹配出现的位置都具有高复杂性，在实践中需要大量算法进行优化。其中子图判定是NP-complete问题，其思想是对查询图Q加以限制；子图位置列举是NP-hard问题，在实践中可采用大量的过滤策略来检索搜索空间，从而提高查询的性能。Mhedhbi等人［17］研究了优化子图查询的问题，在查询执行期间更改最坏情况最佳子计划的顺序；Sun等人［18］提出了基于深度优先加回溯的方式实现子图匹配；Wi等人［19］提出了基于广度优先的多路连接方法，在列式数据结构的基础上引入了字典来优化存储与运算性能；Han等人［20］提出一种使用SIMD指令的集合交集算法，提高了子图匹配的效率；Zeng等人［21］设计了一种高效的子图同构算法，通过利用GPU架构的特性突破了子图同构性能在实际应用中的瓶颈。

2 预备工作

2.1 图数据

在本文设计的模型中，图的类型为有向图，以顶点和标签来表示。其中，两个顶点分别表示图中边的起点和终点的关系实体，标签则表示这两个顶点之间连成的边上的属性，也代表实体之间的关系。

定义1 数据图。数据图G=G（V，E，L）包含了现实中任意两个实体之间的关系及其类型，其本质是一个有向图，是由顶点集合V（如社交网络中的用户）、有向边集合E（如两个用户之间的关系）以及边上的关联函数集合L（关系的类型）构成的有序三元组。对于任意的l∈L={l1，l2，…，lk}，它使得任意e∈E对应V中的一个有序顶点对（v1，v2）。本文使用数字及小写字母表示图上的顶点（如顶点v1、v2等），小写字母表示边上的属性（如标签a、b等），如图1所示。

例1 图1展示了某社交网络图中多个用户之间的社交关系。图中包含11个顶点，若干条边，以及a、b、c共三种标签类型。这些顶点和边上标签共同构成正则路径查询的匹配图G。

数据图可以用布尔矩阵M表示。仅当（v0，ex，v1）是G中的一条边时，M［i，j］=1，称M为G的邻接矩阵。另一种方法是采用邻接链表，即一个顶点的所有邻接顶点都用链表来表示。

定义2 路径。在数据图G中，若任意两点间能够连通，则称这两点间存在至少一条路径，表示为p，具有单向性。在数据图中，一条路径表示为顶点对及边上标签构成的三元组T的一个序列，即p={（v0，e0，v1），…，（vn-1，ex，vn）}，表示从v0到vn的一条路径。其中，v0…vn∈V，ex∈E。序列中相邻的顶点对均满足首尾相连。

例2 图1所示的数据图G=G（V，E，L）中存在的一条路径v1av2bv5cv6cv9bv11，根据定义2可以表示为p={（v1，a，v2），（v2，b，v5），（v5，c，v6），（v6，c，v9），（v9，b，v11）}。

2.2 查询

在图上的查询需要通过正则表达式进行约束，正则路经查询（RPQ）是面向带标签的图数据上的一种重要查询，是对图数据中满足某种特定查询模式的路径进行识别操作，旨在找出由至少一条满足条件的路径相连接的顶点对，其中需满足的条件以正则表达式表达，查询结果表示为顶点对的序列。

定义3 正则路径查询（RPQ）。正则路径查询可表示为Q=（s，R，t），其中，s，t∈V，分别表示图中的两个顶点，R为正则表达式。

正则路经查询的实现是利用有限状态自动机（finite state automaton）实现，由正则表达式解析得到，其本质是一个识别器，对每个输入的字符进行识别和判断，以确定其能到达的最终状态或状态集和路径。有限状态自动机分为不确定的有限自动机（NFA）［22］和确定的有限自动机（DFA）两类。以下将介绍基于NFA的解析方式。在NFA中，使用数字及小写字母表示自动机上的状态（如q1、q2），小写字母表示边上的关系属性（如标签a、b）。如图2所示，NFA的初始状态为s0=q0，接受状态为q9∈F。

NFA在数据图中按其状态的转移顺序依次遍历，通常采用深度优先遍历来实现，实现过程如图3所示。在匹配过程中，将数据图上匹配到的边记录为三元组T=（va，ex，vb），其中，va，vb∈V，ex∈E。当一轮查询结束时，称由若干个三元组T构成的集合序列p={T0，…，Tx，…Tm}为一条路径，其中，x∈（0，m），m≤|n（n－1）/2|，且n=|V|。通常情况下，存在多个符合匹配约束条件的路径结果，因此用R表示一组路径的集合，|R|表示该集合的大小。

例3 图2展示的NFA对应正则表达式R=ab*（b|c）c+，NFA的生成是根据正则表达式，通过查询解析树进行语法解析后得到的。给定图1的数据图G和图2的NFA，在匹配过程中共有6次遍歷到达最终状态，经过同类项合并后的路径有4条，如p1={（v1，a，v2），（v2，b，v5），（v5，b，v8），（v8，c，v7）}，此时|R|=4。

正则路经查询解决了对数据图的正则表达式约束，但是没有回答路径结构化约束问题，因此设计了结构化正则表达式，并基于此提出了结构化正则路经查询。

定义4 结构化正则路径查询（structured regular path query，SRPQ），表示为QS=（s，RS，t）。其中，s和t分别表示查询的起点和终点；RS为结构化正则表达式，是由字符串组成的集合。字符串是符号的有限序列，包括基本运算符和有限字母表Σ。QS通过正则表达式约束和路径结构化约束，在给定查询图G=G（V，E，L）上进行顶点之间边上标签的查询，找到G上所有满足RS约束条件的匹配结果集合。

结构化正则表达式RS规定了四种基本运算符，对于其中任意两个子表达式RS1和RS2，存在以下规则：

a）连接（RS1·RS2）。查询中先执行子式RS1，再执行RS2，两个子表达式首尾相连。

b）选择（RS1|RS2）。选择子式RS1或RS2的其中一个执行，若子式都满足查询条件，则作为多条查询结果处理。

c）重复（RS1+或RS1*）。子式RS1经过多次连接运算得到。其中，+表示至少进行1次连接运算，*表示运算0次及以上。

d）并列（RS1&RS2）。子式RS1与RS2必须同时满足约束条件，否则不执行，经过该规则约束后的查询结果数量不变。

值得注意的是，连接、选择和重复实现了RS的正则表达式约束，即代表查询结果的序列中的每条路径都满足正则表达式约束。并列运算是结构化的RPQ中最显著的特征，该运算体现了对查询结果的路径结构化约束，即序列中的路径之间满足特定的约束。因此，由字母表Σ和运算符构成的新的用于表示程序语言中单词的正则表达式，形成了一种结构化正则路径查询语言，用于描述结构化查询。

定义5 问题定义。给定数据图G=G（V，E，L）和结构化正则路径查询QS，找到图上所有满足结构化正则表达式RS中所有约束条件的匹配结果，表现形式为子图的集合C。具体的实现方法将在第3章中详细阐述。

结构化正则路径查询的匹配流程如图4所示。以数据图G和查询QS为系统的输入，系统输出即为数据图G中由顶点和边上标签构成的图路径的集合，这些子结构必须满足查询QS的所有约束条件。

3 结构化正则路径查询匹配方法

3.1 结构化查询解析

在本小节中，对结构化正则表达式的解析进行了说明。为了体现查询QS的路径结构化约束，需要构造与RS相应的自动机，使其既能够合理地表达正则表达式的全部内容，又符合自动机的规范。

定义6 结构化非确定性有穷自动机（SNFA），表示为六元组AS=（SS，Σ，δS，s0，F，S&）。其中：SS表示有限状态的非空集合，对于任意的q∈SS，称q是SS中的一个状态；Σ是正则表达式RS上的有限字母表的集合；δS是自动机的状态转移函数，记录了相邻状态之间的转移；s0是自动机的初始状态，s0∈SS；F是接受状态集合，FSS，对于任意的q∈F，称q为SNFA的一个接受状态；S&是并列约束函数。

在NFA的基础上，SNFA定义了新的有限状态，由此产生了新的转移函数。在有限状态集合中，状态分为以下几种类型：

a）初始状态，自动机执行的最初状态。

b）直接状态，经过转移函数δS后到达的新状态。值得注意的是，由于结构化正则路径查询语言解析后可能存在空属性边ε（RS中存在空表达式），影响匹配的效率，所以在自动机每一步匹配之前需要先对这些边进行处理。

c）间接状态，到达直接状态后，跳过其后所有的空属性边，直到不再出现ε为止。在解析过程中，一个直接状态可能对应多个间接状态（如分支结构），都视为自动机执行下一跳的开始。

d）接受状态，该状态后不存在自动机的其他状态。若到达这一步，查询结束，找到一条路径。

e）并列状态，NFA在图上执行匹配时，无论以何种方式，状态的转移是唯一的，即只能从一个状态转移到另一个状态。SNFA在NFA的基础上提出了并列状态，对应结构化正则表达式的并列操作符。在SNFA中，并列状态集合表示为&，分为两个子集，分别为&start和&end。其中，&start为并列开始状态集合，经过并列开始状态可同时到达其后多个直接状态；&end为并列结束状态集合，并列结束状态同时作为多个状态的直接后继状态。在SNFA中，由于任意一个并列结构都需要具备一对并列状态，所以需要使用函数实现关联约束。

定义7 并列约束函数，表示为S&=（q1，q2，d）。其中，q1∈&start，q2∈&end。对于并列状态集合中任意一个并列开始状态，都唯一对应一个并列结束状态，两者共同对两者间的分支结构进行约束；d表示两者共同的度，即这对状态之间的分支数量。

图5所示为一个结构化的NFA，其中，初始状态为s0=q0，接受状态为q9∈F，并列约束函数为S&={q2，q6，2}。

例4 给定正则表达式RS=a·（（b·a）&（c|a））·c+，其中，子式（b·a）和（c|a）为并列关系。RS转换为SNFA后，以q2和q6组成的一对并列状态之间的两条子路径形成了结构化约束。与此同时，q3、q4和q5三个顶点形成了子图结构，它们两两之间都存在着约束。

若要在数据图G上成功查询，需要找到SNFA最后可能出现的状态，然后判断最后的状态中是否存在接受状态。对于SNFA中出现的每一个状态，当其在数据图上匹配到下一条边时，能够达到的状态的个数是不确定的（不确定性有限状态特性），因此需要一个集合來记录所有能够到达的状态。

定义8 激活状态集合（SA）。记录了SNFA在图G上匹配的过程中，哪些状态（顶点）被激活。首先，将集合初始化为SA={s0}，将初始状态激活。若后续状态可以通过状态转移函数δS激活，则动态添加到激活状态集合中，同时将之前的激活状态移除。从初始状态之后，每次执行激活之前，需要保证集合中的状态均为间接状态或并列状态。

例5 在图5中，SNFA的初始状态集合SA={q0}。若下一条边a被激活，状态集合更新为SA={q2}，其中q2为q0的间接状态。其对于并列状态q2，当且仅当q3和q4均可到达时才能发生状态转移，此时的状态集合为SA={q3，q4}。对于并列状态q6，当且仅当q5和q3均已激活，且q3可通过边a到达时才能发生状态转移，并更新为下一个间接状态，此时的状态集合为SA={q7}。

查询解析过程实质上是根据输入的正则表达式字符串构造自动机的过程，首先，识别出表达式中的逻辑运算符，预先设定逻辑运算符的优先级，将表达式分割重组，生成字母表、状态集和函数集。至此，查询解析环节结束。

3.2 查询匹配方法

3.2.1 结构化的NFA匹配算法

基于自动机的匹配是将自动机看做一种匹配模式，在数据图上寻找相同的结构，类似于子图匹配。当基于正则表达式的自动机构造完成后，查询由原来的字符串形式转为图的形式，且查询图具有起点。为了选择在数据图上的匹配位置，首先在图上建立基于标签的倒排索引列表，将数据图中所有的边，按照图中字母表进行分类，以字母表中的属性为表头，表中存储的是具有该属性的有向顶点对，可根据数据图上的属性值（边上的标签）来查找记录（顶点对）。

下面利用本文提出的结构化的NFA匹配算法在数据图上做查询匹配。当输入数据图和查询后，系统会首先将查询QS解析为SNFA，并建立不同的模块来存储解析后的各个组件。设置初始的激活状态集合SA，用于记录自动机匹配过程中状态的变化情况；设置路径p，记录根据自动机状态匹配得到的实时路径，随着自动机的执行动态更新；设置路径结果集合C，将符合条件的结果序列存储下来；设置访问标志数组，用于记录图中顶点的访问情况，在初始化阶段，所有顶点均为未访问状态。初始化完成后，确保SNFA的字母表中的元素在数据图的字母表中存在映射，否则，数据图中不存在符合条件的匹配结果。接下来将自动机中的初始边与数据图上的边逐一匹配，确定在图上的开始位置；当匹配完成执行之后，路径结果集合会根据查询结果写入相应的路径，该过程如算法1所示。

在算法1中，第12行getNextState方法使用了图中查询的起点、自动机初始状态以及初始化的激活状态集合作为输入，通过递归的方式执行图上的深度优先遍历，实现过程如算法2所示。在查询遍历开始时，通过使用倒排索引能够根据列表元素和自动机初始状态快速地在图上锁定查询起点（第8～10行）。

对算法1的时间复杂度进行分析。设数据图的规模为M条边，解析后的自动机有N条边。由于自动机是按照顺序进行解析的，查询起点位于自动机解析函数的第一项，所以算法1中第8行的外层循环复杂度为O（1），内层循环中最多需要遍历M次，故算法1的时间复杂度为O（M）。

3.2.2 更新激活状态集合

在深度优先搜索算法中，通过算法1输入的数据作为查询开始条件，采用递归式搜索策略，使得每一次的遍历结果能够在执行过程中保存，若查询的某一分支在数据图上无法匹配到相应结果时，可通过回溯法寻找其他分支。在每一次递归过程中都将更新路径和激活状态集合，自动机的状态设置为当前状态的后继状态。

算法2 基于深度优先遍历的更新算法 getNextState

输入：当前激活状态集合SA;当前状态q;当前顶点v。

输出：下一个激活状态集合SA。

1 for each f start from q in AS.δS

2if label l in function is empty

3 add q.next to SA and delete q from SA;

4SA←getNextState（SA，v，q.next）;

5return SA;

6 if q not in S&

7check if q is a final state;

8 delete q from SA;

9for each e in G.E

10 for each f in AS.δS

11 if e.match（f）

12add q.next to SA and add e to path p;

13 SA←getNextState（SA，w，q.next）;

14 else

15 SA←isParallelState （SA，v，q）;

16 return SA.

在算法2中，首先是對直接状态的处理（第1～5行），剔除自动机中不包含属性的边，避免算法在每一次迭代中存在无法匹配的情况。接下来执行自动机在图上的正则表达式约束，对SNFA中除了并列以外的状态，这是与传统自动机匹配算法相似的部分。首先判断其是否到达最终状态（第7行）；然后按顺序遍历自动机和数据图，若存在匹配的标签，则将自动机上通过标签到达的状态添加到激活状态集合中，并将图上的对应路径加入到路径集合中，该过程为递归式的深度优先搜索（第9～13行）。对并列状态的处理算法如算法3所示。

算法3 并列状态处理算法isParallelState

输入：当前激活状态集合SA;当前状态q;当前顶点v。

输出：下一个激活状态集合SA。

1 if q in &start

2delete q from SA;

3for each e in G.E and v.next is not visited

4for each f start from q in AS.δS

5 if e.match（f） and q.next is not visited

6set q.next and v.next are visited;

7queue Q.add（q.next， e）;

8 for each f start from q in AS.δS

9if q.next is not visited

10return SA;

11 S&.degree←queue.size（） where S&.q1.equals（q）;

12for each element in Q

13add q.next to SA and add e to path p;

14 SA←getNextState（SA，w，q.next）;

15 return SA;

16 else if q in &end

17set S&.degree-1 where S&.q2.equals（q）;

18if （S&.degree）.equals（0）

19 delete q.next to SA and delete q from SA;

20SA←getNextState（SA，w，q.next）;

21return SA.

算法3中，若输入并列开始状态，则在该状态标记为已访问状态后，将其后续所有的直接状态与图中目标顶点存入队列（第6、7行），其目的是为了统计该状态之后的分支数量，作为该顶点的度。在算法第8～10行中，筛掉了未满足全部分支约束的情况，保证该状态之后的所有状态都可到达；随后，在每一条分支上执行深度优先遍历（第12～14行）。若输入并列结束状态，由于其入度与对应的并列开始顶点的出度相等，所以在每次访问后，该顶点的入度减1。当入度减少为0时，表明其所有的前驱状态都已访问过，并列状态处理结束。

由于需要依次遍历自动机和图上的边，算法2和3的时间复杂度均为O（MN）。基于图上深度优先遍历的自动机匹配过程如图6所示。图中的每个顶点标明了数据图上的顶点以及自动机的当前状态。非并列状态下的查询过程为树型结构，每次遍历到叶子顶点时，不存在与自动机状态匹配的数据图上的顶点时，回溯至上一个顶点继续查询。并列状态下的查询过程为有向无环图结构，当遍历到并列结束状态顶点时，需等待其他分支全部遍历完成后才能继续查询。

例6 随着匹配过程的迭代，执行树上节点对应的激活状态集合发生变化，其中虚线矩形部分为自动机查询中并约束。叶子节点中存在两个接受状态v9和v10。

3.2.3 判断最终状态是否匹配

在算法2中，每当遍历执行时，需要判断当前状态q是否在自动机的接受状态集合F中。若q是一个接受状态，则成功找到一个符合要求的结果，将路径p存入结果集合C中。

图6所示的算法执行树中，符合约束的查询结果有两个，分别是以v4顶点开始，以v9和v10顶点结束的两条序列。每条序列中的顶点对构成一个子图，如图7所示。当自动机在数据图上的遍历完成后，系统最终以算法1为结束，输出查询结果集合C。在本样例中，集合C中包含了两条序列p1和p2。图7中，子图序列p2以加粗边的形式展现。

查询结果表明，经过结构化的正则路径查询可得到子图形式的查询结果。在数据图中，连接顶点v5、v6和v8之间的三条路径之间同时满足一定的约束，三个顶点构成了图结构，实现了结构化查询的目标。

4 实验分析

本章通过实验测试对提出的利用深度优先遍历递归实现结构化正则路径查询匹配方法进行性能分析和评价。实验在基于C++的原型系统中实现了前面描述的所有查询评估技术。

4.1 实验设置

本文使用了真实的社交网络数据集进行评估，数据集来自Stanford大学的大型网络数据集网站整理的基于社交网络的Advogato数据集，共包含5 200个点，47 100条边（以三元组表示），每条边以起点、标签、终点形式给出，边上的标签一共有三种。查询采用手动构造的符合数据集中包含的标签的结构化正则路径查询，根据查询中体现的路径结构化约束将查询分为四组，每组包含20个查询。查询的设置如表1所示，Q1～Q4分别为根据标准划定的不同类型的四组查询，每组查询中边的标签均包含在自动机定义的字母表中。其中，Q1组查询解析后不存在并列结构；Q2组只存在串联或并联的并列结构，且每个并列结构中不存在子式；Q3组在Q2组的基础上，允許并列结构中包含子式，但不允许子式中存在并列结构；Q4组查询中存在并列结构的嵌套，查询Q1～Q4的复杂程度依次递增。

实验基于以下两个方面进行评估：a）通过控制变量法，分析查询的解析和匹配性能；b）通过对比实验，分析本文算法的优势。实验在Intel Core 2.60 GHz CPU i7和16 GB内存的Windows 10系统上进行。

4.2 实验评估

实验基于分组后不同类型的查询进行性能检验。在第一个实验中，分别测试了查询解析和查询匹配的时间，并设置了对比实验；在第二个实验中，通过随机选取数据集上不同规模的子集，测试了数据网络规模对匹配速度的影响。

4.2.1 查询整体时间对比实验

实验分别设置了Q1～Q4四种不同类型的结构化正则路径查询，每种查询设置20个为一组进行实验，解析和匹配时间选取各组的平均值。对照组采用相同的查询，但是其解析和匹配基于一般的正则路径查询。由于一般方法中无法对路径结构化约束进行有效描述，所以规定在对照组中，当遍历执行到并列时，只选取其一条分支而忽略另一条分支，之后将未遍历到的剩余分支作为单独的查询进行处理，最后通过累加作为总体匹配时间。如对查询Q2的处理：首先选取子表达式（b&c）中的b和（c&a）中的c作为主要路径，将查询转换为abcca；接下来处理剩余的分支acc和caa；最后将这三个正则表达式分别进行解析和匹配，所需时间的总和作为对照组的查询时间。实验效果如图8所示。结果表明，在查询字母表不变的情况下，随着查询结构的复杂化，其对应的解析和匹配的速度均呈降低趋势。各组查询中，结构化正则路径查询方法的匹配速度总体上优于对照组。

4.2.2 查询匹配时间梯度实验

实验基于真实数据集Advogato。首先，分别随机选取数据集中10%、30%、50%、80%和100%的边，形成五种不同规模的数据图，再将Q1～Q4共四组查询依次输入，各组查询在数据集上的平均匹配时间如图9所示。

结果表明，数据集的规模对匹配速度有着明显的影响，两者呈现正比的关系。例如在查询Q2中，当其数据集的规模呈直线增加时，匹配时间也是线性增长的。由于数据集中顶点之间边的分布是不均匀的，实际结果与理论值会有所偏差。

5 结束语

本文研究了基于有限状态自动机的结构化正则路径查询问题，目的是使得查询在图上的匹配结果序列不仅满足传统自动机匹配算法的正则表达式约束，同时使得路径之间满足结构化约束，以解决传统正则路径查询在图上的查询结果的信息丢失问题。本文提出了结构化约束的概念，设计了结构化正则路径查询语言和结构化非确定性自动机来实现这种方式。在提出的结构化正则路径查询匹配方法中，引入自动机的并列状态，进行路径结构化约束，最后通过基于图上的深度优先遍历算法实现了自动机在数据图上的匹配。实验结果验证了该方法的可行性，对于匹配性能上的提升将是下一步的努力方向。

参考文献：

［1]Wang Mingyu，Zhang Jiaheng，Liu Jun，et al. PDD graph：bridging electronic medical records and biomedical knowledge graphs via entity linking［C］//Proc of the 16th International Semantic Web Confe-rence.Berlin：Springer-Verlag，2017：219-227.

［2]Ma Hao，Zhou Dengyong，Liu Chao，et al.Recommender systems with social regularization［C］//Proc of the 4th ACM International Confe-rence on Web Search and Data Mining.New York：ACM Press，2011：287-296.

［3]杜方，陈跃国，杜小勇.RDF数据查询处理技术综述［J］.软件学报，2013，24（6）：1222-1242.（Du Fang，Chen Yueguo，Du Xiao-yong. Survey of RDF query processing techniques［J］.Journal of Software，2013，24（6）：1222-1242.）

［4]王鑫，邹磊，王朝坤，等.知识图谱数据管理研究综述［J］.软件学报，2019，30（7）：2139-2174.（Wang Xin，Zou Lei，Wang Chaokun，et al.Research on knowledge graph data management：a survey［J］.Journal of Software，2019，30（7）：2139-2174.）

［5]Zou Lei，Mo Jinghui，Chen Lei，et al.gStore：answering SPARQL queries via subgraph matching［J］.Proceedings of the VLDB Endowment，2011，4（8）：482-493.

［6]Bornea M A，Dolby J，Kementsietsidis A，et al.Building an efficient RDF store over a relational database［C］//Proc of ACM SIGMOD International Conference on Management of Data.New York：ACM Press，2013：121-132.

［7]Abadi D， Marcus A， Madden S， et al. SW-Store：a vertically partitioned DBMS for Semantic Web data management［J］.The VLDB Journal，2009，18（2）：385-406.

［8]Neumann T， Weikum G. The RDF-3X engine for scalable management of RDF data［J］.The VLDB Journal，2010，19（1）：91-113.

［9]Weiss C， Karras P， Bernstein A. Hexastore： sextuple indexing for semantic Web data management［J］.Proceedings of the VLDB Endowment，2008，1（1）：1008-1019.

［10]Peng Peng， Zou Lei， zsu M T， et al. Processing SPARQL queries over distributed RDF graphs［J］.The VLDB Journal，2016，25（2）：243-268.

［11]Libkin L， VrgoCˇ D. Regular path queries on graphs with data［C］//Proc of the 15th International Conference on Database Theory.New York：ACM Press，2012：74-85.

［12]Zhang Xiaowang， Feng Zhiyong， Wang Xin， et al. Context-free path queries on RDF graphs［C］//Proc of the 15th International Semantic Web Conference.Berlin：Springer-Verlag，2016：632-648.

［13]Zhang Xiaowang， Van den Bussche J. On the power of SPARQL in expressing navigational queries［J］.The Computer Journal，2015，58（11）：2841-2851.

［14]Yakovets N， Godfrey P， Gryz J. Query planning for evaluating SPARQL property paths［C］//Proc of International Conference on Management of Data.New York：ACM Press，2016：1875-1889.

［15]Koschmieder A， Leser U. Regular path queries on large graphs［C］//Proc of the 24th International Conference on Scientific and Statistical Database Management.Berlin：Springer-Verlag，2012：177-194.

［16]Koschmieder A. Cost-based optimization of regular path queries on large graphs［EB/OL］.（2010-03-25）.https：//ceur-ws.org/Vol-581/gvd2010_2_1.pdf.

［17]Mhedhbi A， Salihoglu S. Optimizing subgraph queries by combining binary and worst-case optimal joins［J］.Proceedings of the VLDB Endowment，2019，12（11）：1692-1704.

［18]Sun Shixuan， Luo Qiong. In-memory subgraph matching： an in-depth study［C］//Proc of ACM SIGMOD International Conference on Mana-gement of Data.New York：ACM Press，2020：1083-1098.

［19]Wi S， Han W S， Chang C， et al. Towards multi-way join aware optimizer in SAP HANA［J］.Proceedings of the VLDB Endowment，2020，13（12）：3019-3031.

［20]Han Shuo， Zou Lei， Yu J X. Speeding up set intersections in graph algorithms using SIMD instructions［C］//Proc of International Conference on Management of Data.New York：ACM Press，2018：1587-1602.

［21]Zeng Li， Zou Lei， zsu M T， et al. GSI： GPU-friendly subgraph isomorphism［C］//Proc of the 36th IEEE International Conference on Data Engineering.Piscataway，NJ：IEEE Press，2020：1249-1260.

［22]Holzer M， Kutrib M. Nondeterministic finite automata-recent results on the descriptional and computational complexity［J］.International Journal of Foundations of Computer Science，2009，20（4）：563-580.

收稿日期：2023-02-10；修回日期：2023-04-29

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

作者简介：邱涛（1989-），男，江西萍乡人，副教授，硕导，博士，主要研究方向为序列数据处理、查询优化、数据挖掘;王屿涵（1997-），男（通信作者），辽宁沈阳人，硕士，主要研究方向为数据查询（wangyuhan@stu.sau.edu.cn）；邓国鹏（1977-），男，辽宁开原人，主要研究方向为遥测数据分析处理；孙尧（1984-），男，河北迁西人，高级工程师；吕光华，男，安徽界首人，高级工程师；夏秀峰（1964-），男，山东青岛人，教授，硕导，博士，主要研究方向为数据库、数据仓库、数据挖掘.