Recursion in SPARQL

Tracking #: 2518-3732

Adrián Soto
Juan Reutter2
Domagoj Vrgoč1

Responsible editor: 
Oscar Corcho

Submission type: 
Full Paper
The need for recursive queries in the Semantic Web setting is becoming more and more apparent with the emergence of datasets where different pieces of information are connected by complicated patterns. This was acknowledged by the W3C committee by the inclusion of property paths in the SPARQL standard. However, as more data becomes available, it is becoming clear that property paths alone are not enough to capture all recursive queries that the users are interested in, and the literature has already proposed several extensions to allow searching for more complex patterns. We propose a rather different, but simpler approach: add a general purpose recursion operator directly to SPARQL. In this paper we provide a formal syntax and semantics for this proposal, study its theoretical properties, and develop algorithms for evaluating it in practical scenarios. We also show how to implement this extension as a plug-in on top of existing systems, and test its performance on several synthetic and real world datasets, ranging from small graphs, up to the entire Wikidata database.
Full PDF Version: 
Previous Version: 


Solicited Reviews:
Click to Expand/Collapse
Review #1
Anonymous submitted on 11/Jul/2020
Review Comment:

This manuscript is well written and all the suggested observations were considered

Review #2
Anonymous submitted on 25/Aug/2020
Review Comment:

This manuscript was submitted as 'full paper' and should be reviewed along the usual dimensions for research contributions which include (1) originality, (2) significance of the results, and (3) quality of writing.


The authors appear to have taken on board the reviewers' recommendations
carefully. My recommendations required a significant amount of rewriting,
which I am pleased to see the authors have carried out in detail. Here I only
provide a general feedback as the paper seems now much improved and worthy of
publication in this Journal.

The paper now includes comparison with Datalog-like languages and the
technically less deep points have been addressed properly.

The main changes were operated in Section 3. The section now includes formal
definitions of the chosen query language fragments as well as sound definitions
of the new values.

Overall, though not trailblazing, this is a valuable contribution and I
recommend the acceptance of the submission.

Review #3
Anonymous submitted on 03/Sep/2020
Review Comment:

I thank the authors for their careful revision and response to the reviews. All of my points for improvement have been addressed. Hence, I recommend acceptance of this submission.