License
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://drops.dagstuhl.de/opus/volltexte/2018/8594/
Go to the corresponding LIPIcs Volume Portal


Martens, Wim ; Trautner, Tina

Evaluation and Enumeration Problems for Regular Path Queries

pdf-format:
LIPIcs-ICDT-2018-19.pdf (0.6 MB)


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
Seminar: 21st International Conference on Database Theory (ICDT 2018)
Issue Date: 2018
Date of publication: 28.02.2018


DROPS-Home | Fulltext Search | Imprint Published by LZI