Property path search -- depth-first, breadth-first, or something else?

Support
1

When Stardog does a search of a path, the query knows the start IRI and the end IRI. Does the search perform a depth-first search, breadth-first, or something else in order to find the path between the start and end entities?

2

Hi Tom,

It's a variation of BFS. It's not very common that both ends are constants, usually at least one is a variable but it does not affect the algorithm too much.

Is there a specific reason why you ask?

Best,
Pavel

3

Hi Pavel,

Thanks for your response. I'd appreciate a little more detail on the BFS variation.

There are a few questions that I'm trying to answer by using property paths. In my situation, I have a large number of people, schools that they attended, employers where they worked, business transactions that involved multiple people, property that they purchased, etc. I want to be able to ask "Are 'John Smith' and 'Bill Jones' connected to each other?" and, if so, "How?".

It would not unusual for a path from one person to another require 6-10 property traversals. There may be 12-15 classes of resources that are connected. While most class instances have a small number of connections, some of those class instances (i.e., schools and employers) may have hundreds of thousands of connections.

I'd like to get a sense of how the Stardog path queries would process this network to answer questions.

Thank you,

Tom

4

Ah, sorry I thought you were talking about the property paths in SPARQL 1.1 while you are in fact asking about the path queries in Stardog. There yes, it's common to have constants on both ends.

The choice of BFS is mostly due to the shortest path semantics of path queries (unless you do paths all which is much less common).

Most BFS optimisations in path queries are on fairly low (i.e. data access) levels while the algorithm itself is pretty classical. Stardog will try to determine the best traversal direction (forward or backwards) depending the statistics that it has about the data. If your VIA pattern is complex, it will try to simplify it but if it's just ?start ?p ?end, it simply fires off BFS.

Best,
Pavel

5

This topic was automatically closed 14 days after the last reply. New replies are no longer allowed.