Pontificia Universidad Católica de Chile Pontificia Universidad Católica de Chile
Pérez J., Arenas M. and Gutiérrez C. (2010)

nSPARQL: A navigational language for RDF

Revista : Journal of Web Semantics
Volumen : 8
Número : 4
Páginas : 255–270
Tipo de publicación : ISI

Abstract

Navigational features have been largely recognized as fundamental for graph database query languages. This fact has motivated several authors to propose RDF query languages with navigational capabilities. In this paper, we propose the query language nSPARQL that uses nested regular expressions to navigate RDF data. We study some of the fundamental properties of nSPARQL and nested regular expressions concerning expressiveness and complexity of evaluation. Regarding expressiveness, we show that nSPARQL is expressive enough to answer queries considering the semantics of the RDFS vocabulary by directly
traversing the input graph. We also show that nesting is necessary in nSPARQL to obtain this last result, and we study the expressiveness of the combination of nested regular expressions and SPARQL operators.
Regarding complexity of evaluation, we prove that given an RDF graph G and a nested regular expression E, this problem can be solved in time O(|G| · |E|).