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 nontrivial solutions and cases that are longstanding 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:119:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770637},
ISSN = {18688969},
year = {2018},
volume = {98},
editor = {Benny Kimelfeld and Yael Amsterdamer},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8594},
URN = {urn:nbn:de:0030drops85947},
doi = {10.4230/LIPIcs.ICDT.2018.19},
annote = {Keywords: graph databases, regular path queries, regular languages, parameterized complexity}
}
2018
Keywords: 

graph databases, regular path queries, regular languages, parameterized complexity 
Seminar: 

21st International Conference on Database Theory (ICDT 2018)

Issue date: 

2018 
Date of publication: 

2018 