💻 computer science

PathFinder: A unified approach for handling paths in graph query languages

本文介绍了 PathFinder，这是一种用于处理现代图语言中路径查询的统一且高效的方法，它利用紧凑的路径表示和流水线执行来实现稳定的性能，并使性能超越现有图引擎一个数量级。

原作者： Benjamín Farías, Wim Martens, Carlos Rojas, Domagoj Vrgoč

发布于 2026-07-15

📖 1 分钟阅读☕ 轻松阅读

原作者： Benjamín Farías, Wim Martens, Carlos Rojas, Domagoj Vrgoč

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象你正在探索一座名为 Graph City（图之城） 的宏大魔法城市。在这座城市里，每一个人都是一栋建筑（节点），而他们之间的每段关系都是一条路（边），并且每条路上都有特定的路标，比如“关注”、“居住”或“工作”。

多年来，这座城市的导游们（旧的数据库引擎）有一个奇怪的规则：如果你问，“请展示所有我从乔（Joe）到埃菲尔铁塔的路径，且只能通过‘关注’这条路”，导游只会指着终点说，“好的，你可以到达那里！”然后就停下了。他们只给了你目的地，却不会向你展示旅途的地图。

这对侦探们来说是个问题。如果你试图解决一个谜团（比如发现洗钱行为或追踪谣言），你不仅需要知道谁与谁相连，还需要看到他们所走的完整路径。他们是直达的吗？还是绕了三圈才到？或者是走了捷径？

于是，PathFinder 登场了。这是一个由 Benjamín、Wim、Carlos 和 Domagoj 构建的超级智能新导游。这篇论文介绍了 PathFinder，它是第一个不仅能告诉你谁与谁相连，还能亲手递给你每一条可能路径的精确地图的导游，无论规则多么复杂。

“乘积图”的魔力

PathFinder 是如何在不迷失在迷宫中的呢？想象你有一张普通的城市地图，同时你还有一个微小的、神奇的清单（自动机），上面写着：“你必须走一条‘关注’的路，再走一条‘关注’的路，然后走一条‘工作’的路。”

PathFinder 不仅仅是在城市中行走；它构建了一个影子城市（称为乘积图 Product Graph），在这里，每一栋建筑都是一个真实城市建筑加上清单上的一步。

如果你在“乔”这里且尚未进行任何步骤，你就处于 (乔, 步骤 0)。
如果你走过一条“关注”的路到达“保罗”，你就移动到了 (保罗, 步骤 1)。

通过在这个影子城市中行走，PathFinder 可以瞬间识别出哪些路径符合你的清单。这就像拥有一个 GPS，它只会在你被允许行驶的道路上亮起，忽略其余部分。

27 种行走方式

论文解释说，在 Graph City 中共有 27 种不同的规则（称为“模式”）。PathFinder 是第一个能够处理所有 27 种模式的引擎。以下是其中一些风格：

WALK（漫步）： 你可以去任何地方，即使你在同一个地方转圈或者两次访问同一栋房子。（这最简单，但会导致无限循环！）。
TRAIL（小径）： 你可以两次访问同一栋房子，但不能两次走在同一条路上。
SIMPLE（简单路径）： 你不能两次访问同一栋房子（除非起点和终点是同一个地方）。这是最难遵守的规则，因为可能的路径数量会爆炸式增长。
ANY SHORTEST（任意最短路径）： 只给我提供一条最快的路径。
ALL SHORTEST（所有最短路径）： 把所有最快的路径都给我。
SHORTEST k GROUPS（k 组最短路径）： 给我最快的路径，然后是第二快的路径组，依此类推，直到第 $k$ 组。

作者展示了，虽然某些规则（如寻找“简单路径”）在理论上是非常困难的——难到计算机在面对巨大的地图时通常会放弃——但 PathFinder 在现实世界中处理得非常出色。

“无限循环”问题

Graph City 中的一个大麻烦是，如果存在一个环路（比如乔关注保罗，而保罗又关注乔），你可能会在这个环路中永远走下去。如果你要求“所有的漫步路径”，答案将是无限的！

为了解决这个问题，GQL 和 SQL/PGQ 标准（这些语言的规则书）允许你选择一种模式，如“Simple”或“Trail”来停止无限循环。PathFinder 完美地遵守了这些规则。它准确地知道何时停止探索一条路径，以免陷入无尽的循环，同时仍能找到你请求的所有有效路径。

速度测试：PathFinder 对阵其他选手

作者不仅构建了 PathFinder，还将其投入测试，与行业内的巨头进行了对比：Neo4j、Nebula、Kuzu、Jena、Blazegraph 和 Virtuoso。

他们在三种场景下进行了测试：

Pokec： 一个中型社交网络，拥有 160 万人和 3000 万个连接。
Wikidata： 一个巨大的现实世界知识图谱，拥有 3.64 亿个节点和 12.57 亿条边。
Diamond（钻石图）： 一个精心构造的数学图，旨在产生指数级的路径数量（具体为 $2^n$ 条路径）。

测试结果：

速度： 在几乎所有的测试中，PathFinder 比其他引擎快 10 到 100 倍。
稳定性： 当路径变得更长或更复杂时，其他引擎开始崩溃或超时（放弃），而 PathFinder 依然能稳步运行。
“不可行性”的惊喜： 对于“Simple”和“Trail”模式，理论上说计算机需要花费极长时间才能找到答案。但在现实世界的测试中（如在 Wikidata 上），PathFinder 快速找到了 10 万条路径。作者认为这是因为现实世界的数据通常不会出现让数学计算发生爆炸的特定“完美风暴”式的连接。

PathFinder 暂时还做不到的事

了解这篇论文没有声称做到的事情也很重要：

它并没有说 PathFinder 是魔法。如果你在一个有环路的图中要求获取每一条路径，答案仍然是无限的，没有任何计算机能打印出来。PathFinder 只是会在你设置的限制内停止（例如 10 万条结果）。
它没有声称已经解决了所有可能图谱中的“简单路径”问题。论文承认，在最坏的理论场景下，寻找简单路径仍然是 NP-complete（一个表示“计算极其困难”的术语）。PathFinder 只是在处理我们实际使用的图谱时表现得比其他人好得多。
它还没有声称已经修复了针对 RDF（一种特定数据格式）的“Simple”模式。作者表示他们还没有实现针对 RDF 的“Trail”模式，因为当边没有唯一名称时，很难定义什么是“trail”。

总结

PathFinder 是一个全新的引擎，它扮演着超级强力导游的角色。它可以接受一套复杂的规则（例如“找出所有从乔到 ENS Paris，且遵循‘关注’后接‘工作’模式的路径”），并返回这些旅程的实际地图。

作者在真实数据上衡量了这一点，发现 PathFinder 比目前的顶尖图数据库快得多且更稳定。他们甚至展示了如何将 PathFinder 添加到现有系统（如 SPARQL 引擎）中，从而赋予它们这种新的超能力。虽然数学理论说这些任务快速完成是不可能的，但在混乱的现实世界中，PathFinder 证明了它可以以惊人的速度完成这些任务。

技术摘要：PathFinder：图查询中的路径返回

问题陈述

现代图查询语言，包括 SPARQL、Cypher、SQL/PGQ 以及新兴的 GQL 标准，都高度依赖路径查询。虽然 SPARQL 支持正则路径查询（RPQs）以识别连接匹配正则表达式的节点对，但它仅返回端点。相比之下，Cypher、SQL/PGQ 和 GQL 允许用户返回满足这些查询的完整路径（见证）。

然而，在这些语言的理论能力与实际实现之间存在显著差距。目前的图数据库引擎缺乏对 GQL 和 SQL/PGQ 标准定义的 27 种路径模式 全谱系的全面支持。这些模式包括各种限制（例如 WALK、TRAIL、SIMPLE、ACYCLIC）和选择器（例如 ANY、ALL SHORTEST、SHORTEST k、SHORTEST k GROUPS）。现有的引擎要么：

支持所有 RPQs 但无法返回路径（SPARQL 引擎）。
可以返回路径，但仅限于正则表达式或路径模式的一个子集（属性图引擎，如 Neo4j、Kuzu、Nebula）。
存在可扩展性问题，由于匹配路径的数量可能呈指数级增长，往往无法高效处理路径查询。

此外，尽管寻找简单路径（simple paths）或迹（trails）的理论复杂度已知是 NP 完全的，但在处理现实世界数据中的理论上难以处理的查询时，实际实现往往难以提供稳定的性能。

方法论

本文介绍了 PATHFINDER，一个用于评估 RPQs 并返回所有 27 种 GQL 路径模式下路径的统一框架。该方法的核心在于积图构建（product graph construction），即将输入的图数据库 $G$ 与由查询的正则表达式导出的非确定有限自动机（NFA） $A$ 相结合。

核心算法原理

积图构建： 框架构建一个积图 $G \times A$ ，其中节点是 $(v, q)$ 对，代表图中的节点 $v$ 和自动机中的状态 $q$ 。积图中的边对应于匹配图中边标签的自动机转换。
延迟构建（Lazy Construction）： 积图是延迟构建的，这意味着仅生成评估查询所需的必要部分，从而允许流水线执行，即一旦检测到结果即可返回。
路径多重集表示（PMR）： 算法使用搜索状态来维护所有匹配路径的紧凑表示。一个搜索状态通常包括当前节点、自动机状态、深度以及指向前驱状态的指针，从而能够在不显式存储路径的情况下重建路径。

针对不同路径模式的具体算法

论文详细说明了针对不同路径模式对积图搜索进行的特定适配：

WALK 模式 (ANY, ANY SHORTEST, ALL SHORTEST, ANY k, SHORTEST k, SHORTEST k GROUPS)：
- ANY/ANY SHORTEST： 在积图上使用标准的 BFS 或 DFS。为了处理非确定性和确保每个端点对仅返回一条路径，算法会跟踪已访问状态 $(n, q)$ 并使用 ReachedFinal 集合来防止重复返回。
- ALL SHORTEST： 扩展 BFS 以跟踪到达节点的所有最短路径。搜索状态包含一个指向所有产生最短路径的前驱节点的指针列表 (prevList)，从而允许枚举多条最短路径。
- SHORTEST k / ANY k： 跟踪增加长度直至限制 $k$ 的路径。算法维护到达每个状态的路径计数，以确保终止并返回 $k$ 条最短路径。
- SHORTEST k GROUPS： 与上述类似，但按长度对路径进行分组，返回所有直到第 $k$ 个发现的不同长度的路径。
受限模式 (TRAIL, SIMPLE, ACYCLIC)：
- 这些模式在最坏情况下已知是 NP 完全的。该框架采用带有**剪枝（pruning）**的积图暴力探索。
- isValid 函数检查扩展路径是否违反了特定限制（例如，对于 TRAIL 检查是否重复边，或对于 SIMPLE 检查是否重复节点）。
- 虽然最坏情况下的复杂度仍然是指数级的，但该方法旨在处理现实世界图数据时保持高效，因为有效路径的数量通常是可控的。

实现与集成

属性图： 基于 MillenniumDB（一个开源图引擎）实现。其语法扩展了类 Cypher 模式，以包含路径变量和模式（例如 MATCH (src)=[MODE ?p rgx]=>(tgt)）。
SPARQL 扩展： 该框架扩展了 SPARQL 语法以支持路径返回（例如 src MODE (path AS ?p) tgt），证明了现有的 RDF 引擎可以被增强以具备这些能力。
执行模型： 算法使用线性迭代器实现流水线执行，确保路径是即时返回的，而不是在输出之前构建整个解集。

主要贡献

首个统一框架： PATHFINDER 是第一个支持为 所有 27 种 GQL 和 SQL/PGQ 标准规定的路径模式 返回路径的 所有正则路径查询（RPQs） 的系统。
算法创新： 它提供了基于积图构建的可实现算法，能够处理路径模式的复杂性，包括处理非确定性自动机以及枚举多条最短路径或路径组。
SPARQL 扩展： 它证明了扩展 SPARQL 以返回路径见证的可行性，弥合了 RDF 与属性图查询能力之间的差距。
实际可行性： 通过广泛的实验，论文表明尽管对于某些模式（如 TRAIL）存在理论上的困难，但该方法在处理现实世界数据时表现出了稳定的性能。

实验结果

作者使用三个数据集评估了 PATHFINDER：Pokec（社交网络）、Wikidata（大规模知识图谱）和合成的 Diamond 图（设计用于具有指数级数量的路径）。

性能： PATHFINDER 一致优于最先进的引擎（Neo4j, Nebula, Kuzu, Jena, Blazegraph, Virtuoso），实现了 一个到两个数量级（10倍–100倍）的加速。
可扩展性：
- 在 Pokec 上，随着路径长度的增加，PATHFINDER 保持了稳定的性能，而其他系统经常超时。
- 在 Wikidata 上，PATHFINDER 成功处理了 659 个复杂查询，而 SPARQL 引擎（不返回路径）明显更慢，且属性图引擎（Neo4j）在绝大多数查询上都超时了。
- 在 Diamond 图上，PATHFINDER 在 WALK 模式下展示了线性时间复杂度，而其他引擎则表现出指数级增长。对于 TRAIL 模式，PATHFINDER 的深度优先搜索（DFS）变体在处理海量路径方面优于广度优先搜索（BFS）。
鲁棒性： 该系统能够以稳定的性能处理理论上难以处理的查询（例如大型图上的 TRAIL），这表明现实世界的数据分布缓解了最坏情况下的理论复杂度。

意义与主张

论文声称，PATHFINDER 通过统一 GQL/SQL/PGQ 的理论能力与实际实现，代表了图查询处理领域的重要进步。

路径返回的可行性： 这项工作证明了为复杂的 RPQs 返回完整的路径见证不仅在理论上是可能的，而且在实践中是高效的，即使对于此前被认为难以处理的模式也是如此。
标准合规性： 它是第一个完全支持 GQL 标准中 27 种路径模式的引擎，填补了当前数据库技术的一个关键空白。
可扩展性： 将其成功集成到 MillenniumDB 中以及对 SPARQL 的扩展表明，这些算法可以在不要求完全重写底层引擎的情况下，集成到现有的数据库流水线中。
对未来的展望： 作者指出，虽然目前的实现处理标准的 RPQs，但未来的工作将探索涉及节点和边数据属性的更具表达力的查询，并且需要进一步研究路径返回语义如何与 SPARQL 特有的属性路径语法相结合。

总之，PATHFINDER 提供了一种处理路径返回查询的高性能且可靠的策略，挑战了“此类功能必然以牺牲可扩展性或限制查询语言表达能力为代价”的观点。