0

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.

Waltteri
  • 1
  • 2
  • You can try using *: `?subject <:raised>* ?object` or +: `?subject <:raised>+ ?object` operators to access data recursively – Krzysztof Majewski Sep 15 '22 at 15:35
  • 1
    You may find this helpful: [Calculate length of path between nodes?](https://stackoverflow.com/q/5198889/1281433), which asks "For instance, given an organizational hierarchy, how can I determine how far separated are a parent and an descendant organization?" It's not exactly the same, since it's only going in one direction, but it might help. – Joshua Taylor Sep 16 '22 at 01:44
  • Your examples show direct ancestors and direct descendants. Would you also want, for instance, aunts and uncles? And what is the degree of separation for an aunt or uncle? Is it 3? – Joshua Taylor Sep 16 '22 at 01:48
  • Do you care about counting closer relations in the "more distant" patterns? E.g., if you're asking for degree 2 links, you'd want you sibling (up to parent, down to sibling), but not yourself (up to parent, down to self). For degree 3 links, (^raised/^raised/raised) can get you back to a parent that also had a degree 2 link. – Joshua Taylor Sep 16 '22 at 02:03
  • Is it possible to make the property-path answers work with any possible predicate? So not just with <:raised> or any other specific one? – Waltteri Sep 16 '22 at 07:30
  • SPARQL has no "wildcard" for property paths per se, but the idiom `(:p|!:p)` can be used. That is, the "union of some property and anything that is not that property" (i.e., all properties). – Ora Lassila Sep 16 '22 at 10:38
  • The property path approaches also don't give me full s-p-o triples, especially if I don't use some specific predicate... It's looking like I'll have to stick to my original approach. – Waltteri Sep 21 '22 at 09:50

1 Answers1

0

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...

Ora Lassila
  • 392
  • 1
  • 3
  • 1
    That's up to three degrees. If you want unlimited degrees, do this: `SELECT ?rel { :me (:raised|^:raised)+ ?rel }`. – Ora Lassila Sep 15 '22 at 17:23