A powerful traversal language for discoverable graphs

There is renewed interest in graph query languages, where querying Web data (such as linked data, or on-line social networks) is considered an important application scenario. Implementing responsive evaluation techniques for queries on Web graphs (where navigation causes additional data to be discovered on the fly) demands a judicious choice of language features that achieve high expressibility while retaining low complexity. This paper presents GenTLE, a graph traversal language that targets Web data and offers a novel and attractive expressiveness/ complexity trade-off. GenTLE expressions are evaluated on discoverable graphs. The proposed language retains the low polynomial time (data and query) combined complexity of Nested Regular Expression languages while significantly extending their expressibility with support for path conjunction, path negation, and the output of explanation subgraphs as answers.