OpenLink Virtuoso: Finding if two nodes are connected within a certain distance

Question

How can I find the distance between 2 nodes in a graph using Virtuoso? I've read the Transitivity documentations but they limit you to one predicate e.g.:

SELECT ?link ?g ?step ?path
WHERE
{
  {
    SELECT ?s ?o ?g
    WHERE
      {
        graph ?g {?s foaf:knows ?o }
      }
  } OPTION (TRANSITIVE, t_distinct, t_in(?s), t_out(?o), t_no_cycles, T_shortest_only,
  t_step (?s) as ?link, t_step ('path_id') as ?path, t_step ('step_no') as ?step, t_direction 3) .
  FILTER (?s= <http://www.w3.org/People/Berners-Lee/card#i>
  && ?o = <http://www.advogato.org/person/mparaz/foaf.rdf#me>)
}
LIMIT 20

Only traverses foaf:knows and not any predicate type. How can I extend this to 'whatever predicate'? I don't need the actual path, just a true/false (ASK query). Changing the foaf:knows to ?p seems like an overkill.

I'm currently performing a set of recursive ASKs to find out if two nodes are connected within a specific distance but that doesn't seem efficient.

Answer 1

You should be able to use ?p instead of foaf:knows in your query to determine if there's a path between the nodes. E.g.:

SELECT ?link ?g ?step ?path
   WHERE
   {
     {
       SELECT ?s ?o ?g
       WHERE
         {
           graph ?g {?s ?p ?o }
         }
     } OPTION (TRANSITIVE, t_distinct, t_in(?s), t_out(?o), t_no_cycles, T_shortest_only,
     t_step (?s) as ?link, t_step ('path_id') as ?path, t_step ('step_no') as ?step, t_direction 3) .
     FILTER (?s= <http://www.w3.org/People/Berners-Lee/card#i>
     && ?o = <http://www.advogato.org/person/mparaz/foaf.rdf#me>)
   }
   LIMIT 20

Answer 2

Here's an approach that works if there's at most one path between the nodes that you're interested in. If you have data like this (note that there are different properties connecting the resources):

@prefix : <https://stackoverflow.com/q/3914522/1281433/>

:a :p :b .
:b :q :c .
:c :r :d .

Then a query like the following finds the distance between each pair of nodes. The property path (:|!:) consists a property that is either : or something other than : (i.e., anything). Thus (:|!:)* is zero or more occurrences of any property; it's a wildcard path. (The technique used here is described more fully in Is it possible to get the position of an element in an RDF Collection in SPARQL?.)

prefix : <https://stackoverflow.com/q/3914522/1281433/>

select ?begin ?end (count(?mid)-1 as ?distance) where {
 ?begin (:|!:)* ?mid .
 ?mid (:|!:)* ?end .
}
group by ?begin ?end
order by ?begin ?end ?distance

--------------------------
| begin | end | distance |
==========================
| :a    | :a  | 0        |
| :a    | :b  | 1        |
| :a    | :c  | 2        |
| :a    | :d  | 3        |
| :b    | :b  | 0        |
| :b    | :c  | 1        |
| :b    | :d  | 2        |
| :c    | :c  | 0        |
| :c    | :d  | 1        |
| :d    | :d  | 0        |
--------------------------

To just find out whether there's a path between two nodes that's less than some particular length, you use an ask query instead of a select, fix the values of ?begin and ?end, and restrict the value of count(?mid)-1 rather than binding it to ?distance. E.g., is there a path from :a to :d of length less than three?

prefix : <https://stackoverflow.com/q/3914522/1281433/>

ask {
 values (?begin ?end) { (:a :d) }
 ?begin (:|!:)* ?mid .
 ?mid (:|!:)* ?end .
}
group by ?begin ?end
having ( (count(?mid)-1 < 3 ) )

Ask => No

On the other hand, there is a path from :a to :c with length less than 5:

prefix : <https://stackoverflow.com/q/3914522/1281433/>

ask {
 values (?begin ?end) { (:a :c) }
 ?begin (:|!:)* ?mid .
 ?mid (:|!:)* ?end .
}
group by ?begin ?end
having ( (count(?mid)-1 < 5 ) )

Ask => Yes