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.
翻译:常规路径查询( RPQs) 是图形查询语言的一个基本组成部分 。 这些查询考虑的是常规表达式 r 和 定向边缘标签图形 G, 并在 G 中搜索路径, 标签的顺序在 r 语言中 。 为避免考虑无限多路径, 一些数据库引擎限制这些路径为路径, 也就是说, 它们只考虑没有反复边缘的路径 。 在本文中, 在表达式固定的情况下, 我们考虑在线索语义下对 RPQ 的评估问题 。 我们显示, 在这种环境下, 存在三角形 。 更确切地说, RPQ 评估的复杂性将常规语言分为限定语言、 类Ttrat( 问题可以拖动) 和 休息 。 有趣的是, 三角线的可拉动类大于由 Bagan、 Bonifati 和 Groz [ JCSS 2020] 发现的小路径的三角形。 除此三角形结果外, 我们还研究可分级、 直径、 直观、 练习、 查点 问题是如何延伸到 的特性 。