View publication
| Title | nSPARQL: A Navigational Language for RDF |
| Authors | Jorge Pérez, Marcelo Arenas, Claudio Gutierrez |
| Publication date | 2010 |
| 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 con- cerning 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|). |
| Pages | 255-270 |
| Volume | 8 |
| Journal name | Journal of Web Semantics |
| Publisher | Elsevier Science (Amsterdam, The Netherlands) |
| Reference URL |
|