Regular queries on graph databases

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

18 Scopus citations


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 with transitive closure rules. 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 nonelementary. 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.

Original languageEnglish
Title of host publication18th International Conference on Database Theory, ICDT 2015
EditorsMarcelo Arenas, Martin Ugarte
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Number of pages18
ISBN (Electronic)9783939897798
StatePublished - 2015
Externally publishedYes
Event18th International Conference on Database Theory, ICDT 2015 - Brussels, Belgium
Duration: 23 Mar 201527 Mar 2015

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference18th International Conference on Database Theory, ICDT 2015


  • Conjunctive regular path queries
  • Containment
  • Graph databases
  • Regular queries


Dive into the research topics of 'Regular queries on graph databases'. Together they form a unique fingerprint.

Cite this