%0 Journal Article
%T Context-Free Path Queries on RDF Graphs
%A Xiaowang Zhang
%A Zhiyong Feng
%A Xin Wang
%A Guozheng Rao
%J Computer Science
%D 2015
%I arXiv
%X 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.
%U http://arxiv.org/abs/1506.00743v1