Nsparql: a navigational language for RDF. 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 particular, we have argued in a previous paper that nested regular expressions are appropriate to navigate RDF data, and we have proposed the nSPARQL query language for RDF, that uses nested regular expressions as building blocks. In this paper, we study some of the fundamental properties of nSPARQL 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 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 the evaluation of a nested regular expression E over an RDF graph G can be computed in time O(|G|·|E|).
Keywords for this software
References in zbMATH (referenced in 4 articles )
Showing results 1 to 4 of 4.
- Vrgoč, Domagoj: Using variable automata for querying data graphs (2015)
- Czerwiński, Wojciech; Martens, Wim; Masopust, Tomáš: Efficient separability of regular languages by subsequences and suffixes (2013)
- Theoharis, Yannis; Georgakopoulos, George; Christophides, Vassilis: PoweRGen: a power-law based generator of RDFS schemas (2012)
- Gutierrez, Claudio; Hurtado, Carlos A.; Mendelzon, Alberto O.; Pérez, Jorge: Foundations of semantic web databases (2011)