10.4230/LIPICS.STACS.2020.7
Martens, Wim
Wim
Martens
https://orcid.org/0000-0001-9480-3522
University of Bayreuth, Germany
Niewerth, Matthias
Matthias
Niewerth
https://orcid.org/0000-0003-2032-5374
University of Bayreuth, Germany
Trautner, Tina
Tina
Trautner
https://orcid.org/0000-0001-6355-3815
University of Bayreuth, Germany
A Trichotomy for Regular Trail Queries
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
2020
ConferencePaper
Regular languages
query languages
path queries
graph databases
databases
complexity
trails
simple paths
en
Christophe Paul
https://orcid.org/0000-0001-6519-975X
University of Bayreuth, Germany
Markus Bläser
University of Bayreuth, Germany
https://arxiv.org/abs/1903.00226
10.4230/LIPIcs.STACS.2020
978-3-95977-140-5
1868-8969
https://wiki.dbpedia.org
http://arxiv.org/abs/1903.00226
https://doi.org/10.2307/1988844
https://neo4j.com/
https://github.com/opencypher/openCypher/blob/master/docs/openCypher9.pdf
https://www.oracle.com/database/technologies/spatialandgraph.html
https://www.tigergraph.com/
https://www.w3.org/TR/sparql11-query/
https://www.wikidata.org/
Creative Commons Attribution 3.0 Unported license
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 T_tract (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 et al. [Bagan et al., 2013]. 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.
LIPIcs, Vol. 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), pages 7:1-7:16