Document Server@UHasselt >
Research >
Research publications >

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
Issue Date: 2014
Citation: 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
URI: http://hdl.handle.net/1942/17801
Link to publication: http://comjnl.oxfordjournals.org/content/early/2014/11/10/comjnl.bxu128.full.pdf+html
DOI: 10.1093/comjnl/bxu128
ISI #: 000365157000004
ISSN: 0010-4620
Category: A1
Type: Journal Contribution
Validation: ecoom, 2016
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
artikel240.29 kBAdobe PDF

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.