Page 360 - 《软件学报》2026年第5期

陈迪 等: 大图数据的统一查询处理机制 2239

描述每个顶点的局部信息, 根据图数据和模式图中的邻居签名可有效地对候选点进行裁剪, 从而加快匹配速度.
除此之外, Han 等人 [31] 提出了 Turbo 算法用于加快精确图匹配查询, 该算法涉及候选匹配区域探索和结果合
并两个过程, 其首先对匹配区域进行有效排序, 然后基于邻居等价集合来选择匹配的顶点, 一定程度上可保证尽早
进行剪枝, 从而加快查询效率. Carletti 等人 [32] 近些年又提出了 VF3 算法, 可加快巨大并稠密的大图数据中的精确
图匹配查询. 还可采用子图结构来建立索引, 通过数据挖掘技术提取出图中的频繁子图从而建立索引, 能够很大程
度上降低索引结构的规模. Sun 等人 [33] 提出了结合候选顶点及其邻居构建 BI (bigraph index) 索引, 基于此索引提
出高效算法 VC, 在子图匹配过程中高效支持邻居检索与剪枝, 显著提升了子图同构查询的性能.
上述算法都是针对相应的查询问题提出的, 其中涉及的图划分策略和索引的构建策略均不相同, 无法直接应
用到统一的大图查询处理机制中.
2 问题定义

本节首先给出图的定义, 随后给出可达、最短路径、关键字和图匹配这 4 种查询问题的定义, 最后给出本文
研究内容统一查询处理机制的问题定义.
定义 1. 图数据. 在图论中, 带有标签的有向图可用 G=(V, E, L, Σ) 表示. V 表示图中顶点的集合. E 表示图中边
的集合, 对于图中任意边 e ∈ E, 可表示为 (u, v), 其中顶点 u,v ∈ V, 即顶点 u 可达顶点 v. L 为作用于顶点集合 V 上
的标签函数, 对于顶点集 V 中的任意顶点, L(v) 即为顶点 v 的标签, Σ 为标签集合. 顶点上的标签可呈现该顶点的
性质, 如关键字、等级和社会角色等, 并且每个顶点上的标签不唯一, 其拥有一个标签集合. 例如, 图 3 所示, 顶点
8 含有标签{e, f, g}.

17 {a}

0 {a, b, c}

{b, d} 1 2 {a, c}
{h} 4
3
7 {d, e}
13 {i}
{c, h, g} 5 {h, f}
8 {e, f, g} {h, i}
11 6 12 16 {d, h}
{d, g} {c}
14 9
15 {h}
{f, i} {e} 10
{f}
图 3 有向图 G

定义 2. 可达查询. 给定一个有向图 G 和图中的两个顶点 u 和 v, 查询 u 能否到达另一个顶点 v, 即是否存在一
条以 u 为起始顶点, 以 v 为终止顶点的路径, 是一种布尔类型的查询.
例如, 图 3 中顶点 1 和顶点 5 的可达查询返回 true, 顶点 1 和顶点 9 的可达查询返回 false.
定义 3. 最短路径查询. 给定一个有向图 G 和图中的两顶点 u 和 v, 最短路径查询需在顶点 u 和顶点 v 的所有
可达路径中找到距离和最小的那条路径, D s (u, v) 记为最短路径的路径长度.
如果查询的两顶点间仅有一条可达路径, 那该条路径即为最短路径. 例如, 图 3 中假设每一条边距离为 1, 则
D s (8, 5) = 3.
定义 4. 关键字查询. 给定一个有向图 G 和一组关键字 q k = (w 1 ,w 2 ,...,w m ) 后, 关键字查询需在 G 中查询可达
t =< r,(n 1 ,n 2 ,...,n m ) >, 其中 r 和 n i 是图 G 中的顶点, 这些顶点需要满足如下性质:
这组关键字的顶点并返回
(1) 覆盖性: 对于每一个 i (1≤i≤m) 来说, 顶点 n i 的标签集合中含有关键字 w i .
(2) 连接性: 对于每一个 i (1≤i≤m) 来说, 顶点 r 在图 G 中可达顶点 n i .