Counting to k, or How SPARQL 1.1 Could be Efficiently Enhanced with top k Shortest Path Queries

While graph data on the Web and represented in RDF is growing, SPARQL, as the standard query language for RDF still remains largely unusable for the most typical graph query task: finding paths between selected nodes through the graph. Property Paths, as introduced in SPARQL1.1 turn out to be unfit for this task, as they can only be used for testing path existence and not even allow to count the number of paths between nodes. While such a feature has been shown to theoretically highly intractable, particularly in graphs with a high degree of cyclicity, practical use cases still demand a solution. A common restriction in fact is not to ask for all, but only the $k$-shortest paths between two nodes, in order to obtain at least the most important of potentially infeasibly many possible paths. In this paper, we extend SPARQL 1.1 property paths in a manner that allows to compute and return the $k$ shortest paths matching a property path expression between two nodes.

We present an algorithm and implementation and demonstrate in our evaluation that a realtively straightforward solution works (in fact, more efficiently than other, tailored solutions in the literature) in practical use cases.