一句话：系统刻画正则路径查询求值中乘积图方法可达到的复杂度上界，并给出细粒度条件下界。
正则路径查询（RPQ）用正则表达式 q 返回图数据库中由标签属于 L(q) 的路径相连的所有节点对。常用求值方法是构造 q 的 NFA 与数据库的乘积图（PG 方法），简单且高效，但其最优性尚不明确。本文在细粒度复杂度框架下系统研究 PG 方法能取得的上界，并给出条件下界；特别关注枚举与延迟界以及数据复杂度视角。主要发现是 PG 方法可达到最优或接近最优的算法，但枚举延迟较高（与数据库大小成线性）。为此，作者探索三条实现亚线性延迟的途径：超线性预处理、解集近似，以及限制 RPQ 类。
A regular path query (RPQ) is a regular expression q that returns all node pairs (u, v) from a graph database that are connected by an arbitrary path labelled with a word from L(q). The obvious algorithmic approach to RPQ-evaluation (called PG-approach), i.e., constructing the product graph between an NFA for q and the graph database, is appealing due to its simplicity and also leads to efficient algorithms. However, it is unclear whether the PG-approach is optimal. We address this question by thoroughly investigating which upper complexity bounds can be achieved by the PG-approach, and we complement these with conditional lower bounds (in the sense of the fine-grained complexity framework). A special focus is put on enumeration and delay bounds, as well as the data complexity perspective. A main insight is that we can achieve optimal (or near optimal) algorithms with the PG-approach, but the delay for enumeration is rather high (linear in the database). We explore three successful approaches towards enumeration with sub-linear delay: super-linear preprocessing, approximations of the solution sets, and restricted classes of RPQs.