Titlebar

Export bibliographic data
Literature by the same author
plus on the publication server
plus at Google Scholar

 

Evaluation and Enumeration Problems for Regular Path Queries

Title data

Martens, Wim ; Trautner, Tina:
Evaluation and Enumeration Problems for Regular Path Queries.
In: Kimelfeld, Benny ; Amsterdamer, Yael (ed.): 21st International Conference on Database Theory (ICDT 2018) : Proceedings. - Saarbrücken , 2018 . - No. 19 . - (LIPIcs ; 98 )
ISBN 978-3-95977-063-7
DOI: https://doi.org/10.4230/LIPIcs.ICDT.2018.19

Project information

Project financing: Deutsche Forschungsgemeinschaft

Abstract in another language

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.

Further data

Item Type: Article in a book
Refereed: Yes
Keywords: graph databases; regular path queries; regular languages; parameterized complexity
Institutions of the University: Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Computer Science > Professorship Applied Computer Science > Professorship Applied Computer Science VII - Univ.-Prof. Dr. Wim Martens
Research Institutions > Research Centres > Forschungszentrum für Modellbildung und Simulation (MODUS)
Faculties
Faculties > Faculty of Mathematics, Physics und Computer Science
Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Computer Science
Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Computer Science > Professorship Applied Computer Science
Research Institutions
Research Institutions > Research Centres
Result of work at the UBT: Yes
DDC Subjects: 000 Computer Science, information, general works > 004 Computer science
Date Deposited: 02 Oct 2019 08:12
Last Modified: 11 Oct 2019 11:14
URI: https://eref.uni-bayreuth.de/id/eprint/52643