EUVIMEDEUVIMED entdecken
Crossref

Regular Queries on Graph Databases

Juan L. Reutter, Miguel Romero, Moshe Y. Vardi

Theory of Computing Systems · 2017-07 · 61 (1) · 31-83

DOI: 10.1007/s00224-016-9676-2 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Theory of Computing Systems, online erschienen am 16.04.2016. Verfasst von Juan L. Reutter und 2 weiteren Autor:innen. Die Arbeit wurde bisher 33-mal zitiert (Crossref) und nennt 46 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Graph databases are currently one of the most popular paradigms for storing data. One of the key conceptual differences between graph and relational databases is the focus on navigational queries that ask whether some nodes are connected by paths satisfying certain restrictions. This focus has driven the definition of several different query languages and the subsequent study of their fundamental properties. We define the graph query language of Regular Queries, which is a natural extension of unions of conjunctive 2-way regular path queries (UC2RPQs) and unions of conjunctive nested 2-way regular path queries (UCN2RPQs). Regular queries allow expressing complex regular patterns between nodes. We formalize regular queries as nonrecursive Datalog programs extended with the transitive closure of binary predicates. This language has been previously considered, but its algorithmic properties are not well understood. Our main contribution is to show elementary tight bounds for the containment problem for regular queries. Specifically, we show that this problem is 2Expspace-complete. For all extensions of regular queries known to date, the containment problem turns out to be non-elementary. Together with the fact that evaluating regular queries is not harder than evaluating UCN2RPQs, our results show that regular queries achieve a good balance between expressiveness and complexity, and constitute a well-behaved class that deserves further investigation.

Zitieren

APA

Reutter, J. L., Romero, M., & Vardi, M. Y. (2017). Regular Queries on Graph Databases. Theory of Computing Systems, 61(1), 31-83. https://doi.org/10.1007/s00224-016-9676-2

Vancouver

Reutter JL, Romero M, Vardi MY. Regular Queries on Graph Databases. Theory of Computing Systems. 2017;61(1):31-83. doi:10.1007/s00224-016-9676-2

BibTeX
@article{Reutter2017,
  author = {Reutter, Juan L. and Romero, Miguel and Vardi, Moshe Y.},
  title = {Regular Queries on Graph Databases},
  journal = {Theory of Computing Systems},
  year = {2017},
  volume = {61},
  number = {1},
  pages = {31--83},
  doi = {10.1007/s00224-016-9676-2}
}
Kostenlos starten →