论文导读 | 合取正则路径查询

前言

合取正则路径查询（Conjunctive Regular Path Query, CRPQ）是各种主流图数据库查询语言（如SPARQL、Cypher、GQL）中的核心组成部分之一。要介绍合取正则路径查询，需要从正则路径查询（Regular Path Query, RPQ）开始讲起。

RPQ $r$是图的边标签上的一个正则表达式，形如：
$r\to ϵ|a|r_1/r_2|r_1+r_2|r?|r^{\ast }|r^{+}$

在边上带标签的有向图$G=(V,E,\Sigma ,l)$上，正则表达式$r$的结果是至少存在一条路径其边标签序列满足$r$的节点对集合：$[[r]{]}_G=\{⟨u,v⟩|\exists p\in G,p.s=u\wedge p.t=v\wedge l(p)\in L(r)\}$

一个CRPQ由若干RPQ合取得到，可以表示为如下公式：$Q(\bar{x})\leftarrow {\bigwedge }_{i=1}^l{R}_{a_i}(y_i,z_i)\wedge {\bigwedge }_{i=l+1}^k{r}_i(y_i,z_i)$，其中$a_i\in \Sigma$表示单个边标签，$r_i$表示RPQ， x ˉ = { x 1 , ⋯ , x n } ⊆ { y 1 , z 1 , ⋯ , y k , z k } \bar x=\{x_1,\cdots,x_n\}\subseteq \{y_1,z_1,\cdots,y_k,z_k\} xˉ={x1​,⋯,xn​}⊆{y1​,z1​,⋯,yk​,zk​}表示返回变量集合。

我们可以将 CRPQ 视为边可由边标签或 RPQ 指定的子图匹配查询。

我们研究 CRPQ 的动机可以由 A. Bonifati, G. Fletcher, H. Voigt 等学者所著的书 Querying Graphs (2022) 中的这段话总结：

“Few of the current graph processing systems are able to optimize across unions of conjunctive regular path queries. This topic remains at the forefront of current research on efficient graph query evaluation, planning, and optimization.”（“目前很少有图处理系统能够对联合的合取正则路径查询进行优化。该问题仍然是当前高效图查询执行、规划和优化研究的前沿领域。”）

其中，联合的合取正则路径查询（Union of Conjunctive Regular Path Query, UCRPQ）是在 CRPQ 基础上添加表示对结果求并集的运算符。这段话对 CRPQ 也同样适用：目前很少有图处理系统能够对 CRPQ 进行优化。

下面，我们将介绍近年来研究 CRPQ 的三篇论文。

Join Ordering of SPARQL Property Path Queries [1]

这篇文章将 CRPQ 优化看作一个连接排序（Join Ordering）问题，即对 CRPQ 中三元组（可能为带单个边标签的普通三元组，也可能为 RPQ）之间的连接做排序，选择最高效的排序来执行，实际上隐含假设使用二元连接而非多路连接。

CRPQ 的代价模型

要选择最高效的连接排序，需要评估不同的排序，因此需要一个代价模型。然而，仅由普通三元组构成的基础图模式（Basic Graph Pattern, BGP）的代价模型不适用于 CRPQ ，因为它们仅关注基数（即查询结果集大小）：

然而，当 RPQ 的两边都绑定到常量（无论是在查询中指定还是在执行过程中绑定）时，其成本可能远大于其基数。比如，对于以下的查询来说：

尽管在评估 tp3 时 ?x1 被绑定，但 tp3 的成本仍然等于未绑定时的成本，这远大于它的基数。这个结论可以推广到一般情况：两侧均被绑定到常量的 RPQ 与至少一侧未绑定、正则表达式相同的 RPQ 执行代价相等，这是由一般的图数据库执行器对 RPQ 的处理方式决定的。所以，仍然可以沿用上述代价模型 $C_{mm}$ ，但需要估计 CRPQ 的基数，而且不管其中的 RPQ 两侧变量是否绑定都按照未绑定的情形来估计基数。

CRPQ 的基数估计

这篇文章提出了一种基于随机游走的算法来估计 CRPQ 的基数。这种算法源于以下的 BGP 的基数估计算法：令 $J=⟨t{p}_1,\cdots ,t{p}_n⟩$ 为用于随机游走的连接顺序（其中 $t{p}_i$ 为第 i 条三元组）；一次随机游走 $\gamma =⟨t_1,\cdots ,t_n⟩$ 由首先在 $[[t{p}_1]{]}_G$ 中随机选择 $t_1$ ，之后每步在 $[[t_{i-1}\bowtie t{p}_i]{]}_G$ 中随机选择 $t_i(i>1)$ 得到，则采样到 $\gamma$ 的概率为 $P(\gamma )=|[[t{p}_1]{]}_G{|}^{-1}{\Pi }_{i=2}^n|[[t_{i-1}\bowtie t{p}_i]{]}_G{|}^{-1}$ ；令 $\Gamma =⟨{\gamma }_1,\cdots ,{\gamma }_k⟩$ 为采样得到的随机游走多重集合，则 BGP 的基数估计为 $card(\Gamma )=|\Gamma {|}^{-1}{\Sigma }_{i=1}^{|\Gamma |}P({\gamma }_i{)}^{-1}$ 。

在此基础上，估计 CRPQ 基数的基本思想是将 CRPQ 重写为若干不包含 RPQ 的模式（即 BGP ），再用上述算法来估计其基数。具体来说，假设在 RPQ 中 Kleene 闭包路径的最大长度为 $d$ ，那么该 RPQ 可以重写为包含 $d$ 个子句的并集；例如，假设 $d=2$ ，?x1 wdt:P641+ ?y 即可重写为 {?x1 wdt:P641 ?y} UNION {?x1 wdt:P641/wdt:P641 ?y} 。在基数估计过程中，将随机游走分布到 $d$ 个并集子句中，得到 $d$ 个随机游走的多重集合；基数估计如下计算：${\Sigma }_{i=1}^{d}card({\Gamma }_i)$ 。由于 SPARQL 中 RPQ 的集合语义（相同结果会被去重），这总是一个高估。

算法中，最大路径长度 $d$ 是即时估计的。在进行随机游走之前，从 1 到 $d_{max}$ 之间均匀随机抽样一个 $d_{cur}$ 作为当前的随机游走长度上限；$d_{max}$ 初始化为 1 ，当成功采样了一个长度为 $d_{max}$ 的随机游走后，对 $d_{max}$ 递增 1。

实验结果

论文使用 WDBench [4] 作为实验基准，其中的数据图包含 1,257,169,959 条三元组，选取负载中含有 CRPQ 的查询进行实验，共 213 条。文章中的算法实现为外部 Python 程序，通过向 BlazeGraph 和 Virtuoso 传递查询提示来强制执行算法选择的连接顺序，与这两种图数据库自身的优化器产生的连接顺序对比优化时间、查询执行时间及端到端总时间（即前两者之和）。实验显示本文算法（下表中的 Proposal ）的端到端总时间优于 BlazeGraph 和 Virtuoso ；表中的 $k$ 为随机游走的数目。

下面两张图分别给出了本文算法与 BlazeGraph 和 Virtuoso 之间，每个查询端到端总时间的对比，左侧为 BlazeGraph ，右侧为 Virtuoso 。图中对查询按照在原版系统中的端到端总时间从左到右降序排序，灰色表示原版系统时间，蓝色表示本文算法时间。可见本文提出的优化主要有利于长时间运行的查询，因为它可以改善这些查询糟糕的连接顺序。

Size Bounds and Algorithms for Conjunctive Regular Path Queries [2]

与上一篇文章不同，这篇文章考虑使用多路连接来解决 CRPQ 问题。本文思路主要是：首先给出针对 CRPQ 的最坏情况最优 （ Worst-Case Optimal, WCO ）算法很可能不存在的理论结论，再提出一种具有较低时间复杂度、但空间复杂度很高的算法 FullMaterialization ，然后再循序渐进地提出两种空间复杂度较低、时间复杂度逐渐靠近 FullMaterialization 的算法：GenericJoinCRPQ 和 GenericJoinCRPQ-Bipartite ，其中后者对 CRPQ 的结构有一定的要求。

针对 CRPQ 的 WCO 算法很可能不存在

最坏情况最优（ WCO ）是算法的一种性质，其定义是：算法的时间复杂度以任何所有类型的边数目均与当前图相同的图中的最大结果元组数为上界。本文证明了：根据通常的复杂性假设，存在一些 CPRQ ，不存在 WCO 算法能够回答它们。此处“通常的复杂性假设”指布尔矩阵乘法（BMM）假设，即对于大小为 $n\times n$ 的两个方阵，不存在一个 $O(n^2)$ 算法来计算它们的乘积矩阵。在此假设下，对于 RPQ ，不存在 WCO 算法，因为 RPQ 算法可以用来解决 BMM ，而 RPQ 的结果数目是以 $O(n^2)$ 为上界的。对于 CRPQ 而言，结果同样如此，因为 CRPQ 算法可以用来解决 RPQ 。构造下面的例子来证明：考虑 $Q(x,y,z)\leftarrow R_a(x,y)\wedge S_b(y,z)\wedge r(x,z)$ 这个 CRPQ ，其中 $a,b$ 是边标签，$r$ 是 RPQ ；若有 $|R_a|=|S_b|=n$ ，则 $Q$ 的结果数目以 $O(n^2)$ 为上界，所以它的 WCO 算法时间复杂度也以 $O(n^2)$ 为上界；然而，在图 $G$ 上能够回答 CRPQ $Q$ 的算法能用于在图 G ′ = ( V G ∪ { 1 } , E G ′ ) G'=(V_G\cup\{1\},E_{G'}) G′=(VG​∪{1},EG′​) 上回答 RPQ $r$ ，其中 $R_a=\{(v_i,1)|1\le i\le n\},S_b=\{(1,v_i)|1\le i\le n\}$ 。

FullMaterialization 算法

由于 CRPQ 很可能不存在 WCO 算法，下面这篇文章尝试给出一种时间复杂度“尽量好”的算法，称为 FullMaterialization 算法。这个算法的步骤非常简单，分为以下三步：

1. 计算在图 $G$ 上 $Q$ 中所有 RPQ $r$ 的结果；
2. 将这些结果物化为边，作为具有新标签的边加到图 $G$ 中；将 $Q$ 中的 RPQ 改写为具有新边标签的普通三元组，此时 $Q$ 变为一个 BGP ；
3. 使用针对 BGP 的 WCO 算法（例如 GenericJoin [5]）来计算 $Q$ 的结果。

这种算法的时间复杂度为 $O(|V{|}^3+AGM(Q,G))$ ，其中 $AGM(Q,G)$ 为 $Q$ 在 $G$ 上的 AGM 界，$O(|V{|}^3)$ 为物化 RPQ 结果的时间；空间复杂度为 $O(|V{|}^2)$ 。由于空间复杂度非常高，下面的两种算法旨在将空间复杂度改进到线性的前提下，尽量接近 FullMaterialization 算法的时间复杂度。

GenericJoinCRPQ 算法

这种算法遵循DFS式的多路连接框架；相对 FullMaterialization 算法来说，降低空间复杂度的关键在于按需物化 RPQ 结果，而非全部物化。算法步骤如下：

1. 根据查询节点的排序（本文没有讨论如何确定此排序），计算当前查询节点的候选数据节点集合。
2. 对所有候选数据节点循环：
   1. 对当前的候选数据节点，将其绑定到当前查询节点上。
   2. 如果所有的查询节点都已经绑定，输出结果；否则，将涉及当前查询节点的所有 RPQ 的结果作为具有新标签的边物化到数据图中，并用具有这些新边标签的普通三元组替换查询中的 RPQ。
   3. 递归调用方法来处理下一个查询节点。

下面以 $Q(x,y,z)\leftarrow a^{+}(x,y)\wedge b^{+}(y,z)\wedge c^{+}(x,z)$ 这个 CRPQ 为例说明算法的运行过程。这个 CRPQ 可以表示为如下查询图，其中数字表示一种可能的查询节点排序。

对于 y 的每个候选数据节点，物化它导向的所有 $a^{+}$ 和 $b^{+}$ 结果，这样在处理 x 时，它们就会被视为普通的边。但是，无法避免嵌套计算 $c^{+}$ ，无论 y 绑定到哪个数据节点，都会重复计算一遍。对于这个查询，无论查询节点的顺序如何，都无法避免这种嵌套的 RPQ 计算，因此时间复杂度会退化为 $O(|V{|}^2\cdot AGM(Q,G))$ 。

GenericJoinCRPQ-Bipartite 算法

GenericJoinCRPQ 的时间复杂度劣化是由于 RPQ 的嵌套计算；对于特定类别的 CRPQ，可以避免这种嵌套。这类 CRPQ 在文章中被称为 RPQ 二部（ RPQ-Bipartite ）的 CRPQ ，它由两组查询节点构成，RPQ 只会出现在组间，不会出现在组内，形式定义如下：

$Q(\bar{x})\leftarrow {\bigwedge }_{i=1}^l{R}_{a_i}(y_i,z_i)\wedge {\bigwedge }_{i=l+1}^k{r}_i(y_i,z_i)$ 是 RPQ 二部的，若 $G_r(Q)=(V_r,E_r)$ 是二部图，其中 V r = ⋃ i = l + 1 k { y i , z i } , E r = { ( y i , z i ) ∣ i = l + 1 , ⋯ , k } V_r=\bigcup_{i=l+1}^k\{y_i,z_i\}, E_r=\{(y_i,z_i)|i=l+1,\cdots,k\} Vr​=⋃i=l+1k​{yi​,zi​},Er​={(yi​,zi​)∣i=l+1,⋯,k} 。

对于 RPQ 二部的 CRPQ ，其中 $\overline{x_1},\bar{x}-\overline{x_1}$ 是查询节点的二部划分，GenericJoinCRPQ-Bipartite 算法步骤如下：

1. 使用多路连接计算 $Q_{\overline{x_1}}$ 的结果元组 $t_{\overline{x_1}}$ ；
2. 对于每个结果元组 $t_{\overline{x_1}}$ ，将与它关联的所有 RPQ 结果物化到数据图中，然后使用多路连接计算剩余的与 $\bar{x}-\overline{x_1}$ 相关的连接。

这种算法不会再出现嵌套 RPQ 计算的情况；当 $|{\bar{x}}_1|=1$ 或 $|\bar{x}-\overline{x_1}|=1$ 时，其时间复杂度与 FullMaterialization 相同。

这篇文章为理论文章，没有提供实验结果。

Efficient Evaluation of Conjunctive Regular Path Queries Using Multi-way Joins [3]

这篇论文在上一篇的基础上细化和改进了一些实现要点，包括查询节点排序、多路连接的实现、避免物化 RPQ 结果的方法，并提供了实验证据。

RPQ 在 CRPQ 多路连接中的角色

上一篇文章在每次多路连接后，物化当前查询节点相关的所有RPQ结果，以供生成下一个查询节点的候选数据节点集。本文避免了 RPQ 结果的物化（除了下文将会介绍的一种特例），在多路连接中如下处理 RPQ ：

• 当去除最外层 Kleene 星号/加号时，RPQ 使用多路连接来规划和执行。
• 对于每个查询节点，在多路连接之前最多选择一个RPQ进行计算，其结果在连接过程中将被视为普通边。
• 所有其他的 RPQ 都被视为可达性模式，即通过多路连接生成的每个绑定都会检查是否满足所有其他 RPQ 。

我们用以下例子说明本文算法的执行过程。仍然使用下面的查询图，包括其查询节点排序：

当用多路连接计算 z 的结果时：

• 上一篇文章：由于 y 和 x 已被执行，$b^{+}$ 和 $c^{+}$ 的结果都已经被物化，因此它们被视为普通边。
• 本文：$b^{+}$ 或 $c^{+}$ 会被选取先执行，剩下的另一条会被当成可达性模式，每条结果检查是否满足它。

被选取在多路连接前首先计算的 RPQ 或普通三元组被称为引导三元组（Guiding Triple），它的用途是引导集合求交，即迭代其结果以探查建立在其他三元组结果上的哈希表。不考虑哈希映射构建成本的情况下，引导三元组应具有最少的结果，以达到最高的连接效率。普通三元组模式的基数使用现有方法来估计；RPQ 的基数分两种情况估计：

1. 浅估计（Shallow Estimation）：对于单标签Kleene闭包（例如 $(s,a^{+},?o)$ ），将单标签普通三元组的估计（例如 $(s,a,?o)$ ）用作浅估计。由于浅估计总是低估，如果浅估计已经大于其他三元组的估计，则可以直接跳过当前三元组。
2. 默认估计（Default Estimation）：执行RPQ直到指定的路径长度上界（本文实验中设定为5），使用实际结果数目作为估计值。

得到所有普通三元组和 RPQ 的基数估计值后，选取估计值最小的作为引导三元组。

查询节点排序

为了应对具有两个变量的RPQ，采用动态的节点排序，因为 RPQ 在执行过程中一旦有一个变量被绑定，就可以在动态排序中加以考虑，而静态排序无法顾及它们。

本文在实验中对比了两种不同的查询节点排序策略，分别是选择能最大程度减小搜索空间的查询节点，和选择引致最小基数结果的查询节点。

仍需物化 RPQ 结果的特殊情况

当上述算法会引发嵌套的 RPQ 计算时，本文选择先物化该 RPQ 的结果。例如，对于 SELECT * WHERE { ?x <p1> ?z . ?z <p2> ?y . ?y <p3>+ <o> . } 这个查询，如果 y 没有被选为排序中的第一个查询节点，那么 <p3>+ 这个 RPQ 就会被嵌套计算。所以，本文会先物化 ?y <p3>+ <o> . 这条 RPQ 的结果到数据图中。

实验结果

本文同样采用 WDBench [4] 作为实验基准，算法在 Tentris [6] 系统中实现。下图为各方法 QPS 的箱状图对比，其中 JP 是总在 RPQ 前执行连接的算法，RP 为总在连接前执行 RPQ 的算法，RPC 为在 RP 的基础上加上特殊情况下物化 RPQ 结果，这三者为朴素算法；FRF、FMC 分别为使用“最大程度减小搜索空间”和“引致最小基数结果”动态节点排序策略的完整算法。可见 FRF、FMC 的 QPS 接近，高于其他所有方法。

参考文献

[1] J. Aimonier-Davat, H. Skaf-Molli, P. Molli, M.-H. Dang, and B. Nédelec, “Join Ordering of SPARQL Property Path Queries,” in The Semantic Web, 2023.

[2] T. Cucumides, J. Reutter, D. Vrgoč, “Size bounds and algorithms for conjunctive regular path queries,” 26th International Conference on Database Theory (ICDT 2023).

[3] N. Karalis, A. Bigerl, L. Heidrich, et al, “Efficient Evaluation of Conjunctive Regular Path Queries Using Multi-way Joins,” European Semantic Web Conference, 2024.

[4] Angles, R., Aranda, C.B., Hogan, A., Rojas, C., Vrgoč, D.: WDBench: a wikidata graph query benchmark. ISWC 2022.

[5] Hung Q. Ngo, Christopher Ré, and Atri Rudra. Skew strikes back: new developments in the theory of join algorithms. SIGMOD Rec., 42(4):5–16, 2013.

[6] Bigerl, A., Conrads, F., Behning, C., Sherif, M.A., Saleem, M., Ngomo, A.N.: Tentris - A tensor-based triple store. In: Pan, J.Z., Tamma, V.A.M., d’Amato, C., Janowicz, K., Fu, B., Polleres, A., Seneviratne, O., Kagal, L. (eds.) The Semantic Web - ISWC 2020