Recursion in SPARQL

Abstract

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.