SPARQL degrees of separation

Viewed 47

Using SPARQL, how can I find entities linked to an entity by x degrees of separation, for example 4 or 5 degrees? For example, with test data like this, how do I find which of my relatives connects to which one? The aim is to form a graph from the triples. (Using only “raised” as predicates in this example, but any connection should be considered.)

<http://www.example.com/great-grandma> <:raised1> <http://www.example.com/grandma> .
<http://www.example.com/grandma> <:raised2> <http://www.example.com/ma> .
<http://www.example.com/ma> <:raised3> <http://www.example.com/me> .
<http://www.example.com/ma> <:raised4> <http://www.example.com/sis> .
<http://www.example.com/me> <:raised5> <http://www.example.com/kid> .
<http://www.example.com/spouse> <:raised6> <http://www.example.com/kid> .

So from the above, the wanted first-degree relationships would be:

<http://www.example.com/ma> <:raised3> <http://www.example.com/me> .
<http://www.example.com/me> <:raised5> <http://www.example.com/kid> .

With the whole s-p-o triple as the result.

I can get to two degrees relatively easily:

SELECT  *
WHERE
  {   { SELECT DISTINCT ?s ?p ?o
        WHERE
          { ?s ?p1 <http://www.example.com/me> .
             ?s ?p ?o
          }
      }
    UNION
      { SELECT DISTINCT ?s ?p ?o
        WHERE
          { <http://www.example.com/me> ?p1 ?o .
             ?s ?p ?o
          }
      }
    UNION
      { SELECT DISTINCT ?s ?p ?o
        WHERE
          { ?o  ?p1  <http://www.example.com/me> .
            ?s  ?p   ?o
          }
      }
    UNION
      { SELECT DISTINCT ?s ?p ?o
        WHERE
          { <http://www.example.com/me> ?p1  ?s .
            ?s ?p ?o
          }
      }
  }

This finds my grandmother and sister, for example. But this does not seem practical with more degrees of separation, as the number of sub-queries would double with each new degree. Is there a better way to do this? It would need to work with larger amounts of data too, so can't just run a new query on every linked entity.

EDIT: Highlighting that different predicates should be expected, I clarified and changed the example a bit.

1 Answers

Property paths are your friend.

SELECT DISTINCT ?rel {
    {
        SELECT ?rel {
            :me (:raised|^:raised) ?rel
        }
    }
    UNION {
        SELECT ?rel {
            :me (:raised|^:raised)/(:raised|^:raised) ?rel
        }
    }
    UNION {
        SELECT ?rel {
            :me (:raised|^:raised)/(:raised|^:raised)/(:raised|^:raised) ?rel
        }
    }
}

and so on...

Related