License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2018.19
URN: urn:nbn:de:0030-drops-85947
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8594/
Martens, Wim ;
Trautner, Tina
Evaluation and Enumeration Problems for Regular Path Queries
Abstract
Regular path queries (RPQs) are a central component of graph databases. We investigate decision- and enumeration problems concerning the evaluation of RPQs under several semantics that have recently been considered: arbitrary paths, shortest paths, and simple paths. Whereas arbitrary and shortest paths can be enumerated in polynomial delay, the situation is much more intricate for simple paths. For instance, already the question if a given graph contains a simple path of a certain length has cases with highly non-trivial solutions and cases that are long-standing open problems. We study RPQ evaluation for simple paths from a parameterized complexity perspective and define a class of simple transitive expressions that is prominent in practice and for which we can prove a dichotomy for the evaluation problem. We observe that, even though simple path semantics is intractable for RPQs in general, it is feasible for the vast majority of RPQs that are used in practice. At the heart of our study on simple paths is a result of independent interest: the two disjoint paths problem in directed graphs is W[1]-hard if parameterized by the length of one of the two paths.
BibTeX - Entry
@InProceedings{martens_et_al:LIPIcs:2018:8594,
author = {Wim Martens and Tina Trautner},
title = {{Evaluation and Enumeration Problems for Regular Path Queries}},
booktitle = {21st International Conference on Database Theory (ICDT 2018)},
pages = {19:1--19:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-063-7},
ISSN = {1868-8969},
year = {2018},
volume = {98},
editor = {Benny Kimelfeld and Yael Amsterdamer},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8594},
URN = {urn:nbn:de:0030-drops-85947},
doi = {10.4230/LIPIcs.ICDT.2018.19},
annote = {Keywords: graph databases, regular path queries, regular languages, parameterized complexity}
}
|
Keywords: |
|
graph databases, regular path queries, regular languages, parameterized complexity |
|
Collection: |
|
21st International Conference on Database Theory (ICDT 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
05.03.2018 |
