Geek Answers Handbook

Finding the Shortest Path Using a SPARQL Query

I am trying to understand the computational limitations of a SPARQL query, and I would like to know how to write a query that will determine if there is a directional path between two objects.

I know a way to do this for a path of a certain length:

SELECT ?a ?b ?c ?d WHERE { ?a <http://graphtheory/hasNeighbor> ?b . ?b <http://graphtheory/hasNeighbor> ?c . ?c <http://graphtheory/hasNeighbor> ?d . FILTER (?a != ?c && ?b != ?d && ?a = <http://graphtheory/node/1> && ?d = <http://graphtheory/node/2>) } LIMIT 10

Is there a way to find any length path in a single query? Is this not possible with SPARQL?

+4
source share
2 answers

AndyS provided all the elements to answer this question, but there are some typos that may make them difficult to use. As he says:

SPARQL 1.1 has a property path that includes the * operator for any number.

This does not tell you what the path or the length of the shortest path is - is there only such a path.

A way to do this (based on AndyS, but with two minor fixes):

 PREFIX : <http://graphtheory/> PREFIX node: <http://graphtheory/node/> ASK { node:1 :hasNeighbor* node:2 }

As far as I can tell, there is no way to do this without using property paths.

+6
source

SPARQL 1.1 has property paths that include the * operator for "any number."

This does not tell you what the path or the length of the shortest path is - is there only such a path.

 PREFIX : <http://graphtheory/node/> PREFIX node: <http://graphtheory/node/> ASK { node:1 :hasNeighbor* node:2 }

(You do not need ?a = and ?d = , you can write values ​​to the query.)

Adding the path data type to the language is the place for future work - several experimental systems have addressed the problem.

+4
source

More articles:


All Articles