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|).

References in zbMATH (referenced in 13 articles )

Showing results 1 to 13 of 13.
Sorted by year (citations)

  1. Reutter, Juan L.; Romero, Miguel; Vardi, Moshe Y.: Regular queries on graph databases (2017)
  2. Reutter, Juan L.; Vrgoč, Domagoj: Navigational and rule-based languages for graph databases (2017)
  3. Fionda, Valeria; Gutierrez, Claudio; Pirrò, Giuseppe: Building knowledge maps of web graphs (2016)
  4. Bienvenu, Meghyn; Ortiz, Magdalena: Ontology-mediated query answering with data-tractable description logics (2015)
  5. Fletcher, George H. L.; Gyssens, Marc; Leinders, Dirk; Surinx, Dimitri; Van den Bussche, Jan; Van Gucht, Dirk; Vansummeren, Stijn; Wu, Yuqing: Relative expressive power of navigational querying on graphs (2015)
  6. Vrgoč, Domagoj: Using variable automata for querying data graphs (2015)
  7. Czerwiński, Wojciech; Martens, Wim; Masopust, Tomáš: Efficient separability of regular languages by subsequences and suffixes (2013)
  8. Polleres, Axel; Wallner, Johannes Peter: On the relation between SPARQL1.1 and answer set programming (2013)
  9. Arenas, Marcelo; Pérez, Jorge: Federation and navigation in SPARQL 1.1 (2012)
  10. Theoharis, Yannis; Georgakopoulos, George; Christophides, Vassilis: PoweRGen: a power-law based generator of RDFS schemas (2012) ioport
  11. Gutierrez, Claudio; Hurtado, Carlos A.; Mendelzon, Alberto O.; Pérez, Jorge: Foundations of semantic web databases (2011)
  12. Arenas, Marcelo; Gutierrez, Claudio; Pérez, Jorge: Foundations of RDF databases (2009)
  13. Pérez, Jorge; Arenas, Marcelo; Gutierrez, Claudio: nSPARQL: A navigational language for RDF (2008) ioport