EUVIMEDEUVIMED entdecken
Crossref

Dichotomies for Evaluating Simple Regular Path Queries

Wim Martens, Tina Trautner

ACM Transactions on Database Systems · 31.12.2019 · 44 (4) · 1-46

DOI: 10.1145/3331446 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Database Systems, online erschienen am 15.10.2019. Verfasst von Wim Martens und 1 weiteren Autor:innen. Die Arbeit wurde bisher 16-mal zitiert (Crossref) und nennt 58 Literaturangaben. Gefördert von: Deutsche Forschungsgemeinschaft.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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, paths without node repetitions (simple paths), and paths without edge repetitions (trails). Whereas arbitrary and shortest paths can be dealt with efficiently, simple paths and trails become computationally difficult already for very small RPQs. We study RPQ evaluation for simple paths and trails from a parameterized complexity perspective and define a class of simple transitive expressions that is prominent in practice and for which we can prove dichotomies for the evaluation problem. We observe that, even though simple path and trail semantics are intractable for RPQs in general, they are feasible for the vast majority of RPQs that are used in practice. At the heart of this study 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.

Förderung

  • Deutsche Forschungsgemeinschaft

Zitieren

APA

Martens, W., & Trautner, T. (2019). Dichotomies for Evaluating Simple Regular Path Queries. ACM Transactions on Database Systems, 44(4), 1-46. https://doi.org/10.1145/3331446

Vancouver

Martens W, Trautner T. Dichotomies for Evaluating Simple Regular Path Queries. ACM Transactions on Database Systems. 2019;44(4):1-46. doi:10.1145/3331446

BibTeX
@article{Martens2019,
  author = {Martens, Wim and Trautner, Tina},
  title = {Dichotomies for Evaluating Simple Regular Path Queries},
  journal = {ACM Transactions on Database Systems},
  year = {2019},
  volume = {44},
  number = {4},
  pages = {1--46},
  doi = {10.1145/3331446}
}
Kostenlos starten →