Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/17801
Title: | On the power of SPARQL in expressing navigational queries | Authors: | ZHANG, Xiaowang VAN DEN BUSSCHE, Jan |
Issue Date: | 2014 | Source: | COMPUTER JOURNAL, 58 (11), p. 2841-2851 | Abstract: | Navigational queries on graph databases return binary relations over the nodes of the graph. The calculus of relations, popularized by Tarski, serves as a natural benchmark for first-order navigational querying. Recently, nested regular expressions (nre's) have been proposed to extend navigational querying to resource description framework graphs, i.e. ternary relations. This paper investigates the expressiveness of nre's and their relationship to basic SPARQL queries. An elegant proof is given to the effect that nre queries are already expressible as basic SPARQL queries. This result takes exception of nre's involving Kleene star (transitive closure), but on the other hand it holds even when extending nre's with negation (complementation). The resulting language of ‘star-free nre's with negation (sfnre¬)’ can in fact be captured by a precisely delineated fragment of SPARQL, called Tarski-SPARQL. The resulting language is also compared with an alternative extension that adds negation in the form of the difference operator. While sfnre¬ queries are subsumed by first-order logic with three variables (FO3), it is shown that some natural FO3 queries are not expressible in nre¬, even when allowing transitive closure. | Notes: | Van den Bussche, J (reprint author), Univ Limburg, Hasselt Univ & Transnat, B-3500 Hasselt, Belgium. jan.vandenbussche@uhasselt.be | Keywords: | RDF databases; nested regular expression; star-free nested regular expression;complement; difference; Tarski-SPARQL | Document URI: | http://hdl.handle.net/1942/17801 | Link to publication/dataset: | http://comjnl.oxfordjournals.org/content/early/2014/11/10/comjnl.bxu128.full.pdf+html http://alpha.uhasselt.be/jan.vandenbussche/navSPARQL_revision.pdf |
ISSN: | 0010-4620 | e-ISSN: | 1460-2067 | DOI: | 10.1093/comjnl/bxu128 | ISI #: | 000365157000004 | Rights: | © The British Computer Society 2014. All rights reserved. For Permissions, please email: journals.permissions@oup.com | Category: | A1 | Type: | Journal Contribution | Validations: | ecoom 2016 |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
navSPARQL_revision (1).pdf | Early view | 240.29 kB | Adobe PDF | View/Open |
SCOPUSTM
Citations
19
checked on Sep 3, 2020
WEB OF SCIENCETM
Citations
12
checked on Oct 13, 2024
Page view(s)
68
checked on Sep 7, 2022
Download(s)
200
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.