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] 发现的小路径的三角形。 除此三角形结果外, 我们还研究可分级、 直径、 直观、 练习、 查点 问题是如何延伸到 的特性 。

0
下载
关闭预览

相关内容

专知会员服务
41+阅读 · 2021年4月2日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【新书】Python编程基础,669页pdf
专知会员服务
193+阅读 · 2019年10月10日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
CCF A类 | 顶级会议RTSS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年4月17日
学术会议 | 知识图谱顶会 ISWC 征稿:Poster/Demo
开放知识图谱
5+阅读 · 2019年4月16日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
已删除
清华大学研究生教育
3+阅读 · 2018年6月30日
Arxiv
0+阅读 · 2021年12月22日
Arxiv
0+阅读 · 2021年12月15日
Arxiv
11+阅读 · 2021年2月17日
Logically-Constrained Reinforcement Learning
Arxiv
3+阅读 · 2018年12月6日
Efficient and Effective $L_0$ Feature Selection
Arxiv
5+阅读 · 2018年8月7日
VIP会员
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
CCF A类 | 顶级会议RTSS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年4月17日
学术会议 | 知识图谱顶会 ISWC 征稿:Poster/Demo
开放知识图谱
5+阅读 · 2019年4月16日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
已删除
清华大学研究生教育
3+阅读 · 2018年6月30日
Top
微信扫码咨询专知VIP会员