Structural characterization of graph navigational languages

Graph navigational languages define binary relations in terms of pair of nodes in a graph subject to the existence of a path satisfying a certain regular expression. The goal of this paper is to give a novel characterization of navigational languages in terms of the structure of the graph embracing the results of a query. We define novel graph-based query evaluation semantics and efficient algorithms able to represent and capture intermediate nodes/edges linking pairs of nodes in the answer. We enhance the language of Nested Regular Expressions (NREs) with our machineries, thus defining the language of Structural NREs (sNREs).