Abstract

Nested regular expressions (NREs) have been proposed as a powerful formalism for querying RDFS graphs, but not too much investigation on NREs has been pursued in a more general graph database context. In this paper we study the relative expressiveness of NREs by comparing it with the language of conjunctive two-way regular path queries (C2RPQs), which is one of the most widely studied query languages for graph databases. Among other results, we show that NREs and C2RPQs are incomparable in terms of expressive power, but NREs properly extend the language of unions of acyclic C2RPQs. Even more, there is a natural fragment of NREs that coincide in expressive power with the class of unions of acyclic C2RPQs. Our results, plus previous results that show that NREs can be evaluated in linear time in combined complexity, put forward NREs as a query language for graph-structured data that deserves further attention.