Context-Free Path Queries on RDF Graphs

A navigational query on a graph database returns binary relations over the nodes of the graph. Recently, regular expression-based path query languages are popular in expressing navigational queries on RDF graphs. It is natural to replace regular expressions by context-free grammar so that the power of current regular expression-based path query languages would be increased since regular expressions are strictly subsumed in context-free grammar. In this paper, we present context-free path queries and context-free SPARQL queries on RDF graphs and investigate some of their fundamental properties. Our results show that those proposed context-free path queries have efficient query evaluation and context-free SPARQL queries have the same complexity of query evaluation as SPARQL queries. Regarding expressiveness, we prove that those context-free path queries exactly subsume corresponding fragments of nested regular expressions and context-free SPARQL is a strict extension of both SPARQL and nSPARQL.