SPARQL: is there any path between two nodes?

Question

Is there a good kind of SPARQL query that let's me answer if two given nodes are connected on a single / multiple SPARQL endpoints?

Let's say i want to check if the two nodes

<http://wiktionary.dbpedia.org/resource/dog>

and

<http://dbpedia.org/resource/Dog>

are connected. If yes, i'd be interested in the path.

By guessing i already knew they were connected via the label, so a query like this returns a path of length 3:

SELECT * WHERE {
  <http://wiktionary.dbpedia.org/resource/dog> ?p1 ?n1. 
  # SERVICE <http://dbpedia.org/sparql> {
    <http://dbpedia.org/resource/Dog> ?p2 ?n1 .
  # }
}

try yourself

Now what if i don't have an idea yet and want to do this automatically & for arbitrary length and direction?

I'm aware of SPARQL 1.1's property paths, but they only seem to work for known properties (http://www.w3.org/TR/sparql11-query/#propertypaths):

Variables can not be used as part of the path itself, only the ends.

Also i would want to allow for any path, so the predicates on the path may change.

My current (as i find ridiculous) approach is to query for all possible paths of length k up to a limit of n.

Dumping isn't an option for me as it's billions of triples... I want to use SPARQL!

Answer 1

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 →_rdf:type owl:Thing ←_rdf:type ?v