一句话：证明固定正则表达式下 trail 语义 RPQ 求值的复杂度三分法，并刻画可处理类 Ttract。
正则路径查询（RPQ）是图查询语言的核心组件：给定正则表达式 r 与边标记有向图 G，寻找标签序列属于 L(r) 的路径。为避免无限多条路径，部分数据库引擎限制路径为 trail，即不重复边的路径。本文研究固定表达式下 trail 语义 RPQ 的求值问题，证明其复杂度存在三分法：正则语言被划分为有限语言、可处理类 Ttract 与其余语言；仅 Ttract 类可在多项式时间内求值，其余为难解。该可处理类比 Bagan、Bonifati 和 Groz 针对简单路径发现的三分法中的可处理类更大。作者还研究了 Ttract 的刻画、表达能力、识别问题与闭包性质，并将判定问题扩展为对实践更重要的枚举问题。
Regular path queries (RPQs) are an essential component of graph query languages. Such queries consider a regular expression r and a directed edge-labeled graph G and search for paths in G for which the sequence of labels is in the language of r. In order to avoid having to consider infinitely many paths, some database engines restrict such paths to be trails, that is, they only consider paths without repeated edges. In this paper we consider the evaluation problem for RPQs under trail semantics, in the case where the expression is fixed. We show that, in this setting, there exists a trichotomy. More precisely, the complexity of RPQ evaluation divides the regular languages into the finite languages, the class Ttract (for which the problem is tractable), and the rest. Interestingly, the tractable class in the trichotomy is larger than for the trichotomy for simple paths, discovered by Bagan, Bonifati, and Groz [JCSS 2020]. In addition to this trichotomy result, we also study characterizations of the tractable class, its expressivity, the recognition problem, closure properties, and show how the decision problem can be extended to the enumeration problem, which is relevant to practice.