SPARQL: is there any path between two nodes?

While you can’t use variables in property paths, you can use a wildcard by taking advantage of the fact that for any URI, every property either is that property or isn’t. E.g., (<>|!<>) matches any property, since every property either is <> or isn’t. You can make a wildcard that goes in either direction by alternating that with itself in the other direction: (<>|!<>)|^(<>|!<>). That means that there’s a path, with properties going in either direction, between two nodes ?u and ?v when

?u ((<>|!<>)|^(<>|!<>))* ?v

For instance, the following query should return true (indicating that there is a path):

ASK {
  <http://wiktionary.dbpedia.org/resource/dog> ((<>|!<>)|^(<>|!<>))* <http://dbpedia.org/resource/Dog> 
}

Now, to actually get the links of a path between between two nodes, you can do (letting <wildcard> stand for the nasty looking wildcard):

?start <wildcard>* ?u .
?u ?p ?v .
?v <wildcard>* ?end .

Then ?u, ?p, and ?v give you all the edges on the path. Note that if there are multiple paths, you’ll be getting all the edges from all the paths. Since your wildcards go in either direction, you can actually get to anything reachable from the ?start or ?end, so you really should consider restricting the wildcard somehow.

On the endpoint that you linked to, it doesn’t, but that appears to be an issue with Virtuoso’s implementation of property paths, rather than a problem with the actual query.

Do note that this will be trivially satisfied in many cases if you have any kind of inference happening. E.g., if you’re using OWL, then every individual is an instance of owl:Thing, so there’d always be a path of the form:

        ?u &rightarrow;rdf:type owl:Thing &leftarrow;rdf:type ?v

Leave a Comment