View publication
| Title | Relative Expressiveness of Nested Regular Expressions |
| Authors | Pablo Barceló, Jorge Pérez, Juan Reutter |
| Publication date | 2012 |
| Abstract | Nested regular expressions (NREs) have been proposed as a powerful formalism for querying RDFS graphs, but not too much investi- gation on NREs has been pursued in a more general graph database con- text. In this paper we study the relative expressiveness of NREs by com- paring 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 ex- tend 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. |
| Pages | 180-195 |
| Conference name | Alberto Mendelzon International Workshop on Foundations of Data Management |
| Publisher | CEUR Publications |
| Reference URL |
|