VladimirAlexiev
commented
1 year ago GraphDB's implementation is described at https://graphdb.ontotext.com/documentation/10.3/graph-path-search.html.
Rather than new keywords (VIA), it uses existing mechanisms:
- an outer
SERVICEto call path search - a nested
SERVICEto specify the "path step" pattern ("step generator")
Eg the "Kevin Bacon" query looks like this:
SELECT ?edge ?index ?path
WHERE {
VALUES (?src ?dst) {
( dbr:Chris_Evans_\(actor\) dbr:Chris_Hemsworth )
}
SERVICE <http://www.ontotext.com/path#search> {
<urn:path> path:findPath path:allPaths ;
path:sourceNode ?src ;
path:destinationNode ?dst ;
path:pathIndex ?path ;
path:minPathLength 2 ;
path:startNode ?start;
path:resultBinding ?edge ;
path:endNode ?end;
path:resultBindingIndex ?index .
SERVICE <urn:path> {
?film a dbo:Film .
?film dbp:starring ?start .
?film dbp:starring ?end .
}
}
}Results are returned as RDF-star triples:
- The path can be visualized
- The triples are annotated with useful additional info (eg path number in case of multiple paths, and sequential index along the path).
- You can project any bindings out of the "step generator".
@mgberg We'll appreciate feedback on whether you like our approach, and ideas for potential improvement. I'll ask my colleagues whether we can add a custom distance function.
mgberg
ktk
rvesse
afs
Why?
There are several reasons a built-in pathfinding query capability would be useful. For example:
Previous work
There are several vendors/systems that implement pathfindng/more expressive path queries, and they do so in a number of different ways. For example, some extend the SPARQL query syntax, while others take advantage of SPARQL's federation capabilities to create a special service URI that performs the pathfinding operations.
Stardog has (in my opinion) a fantastic implementation of this but with (at least) one flaw. Their implementation can do both pathfinding and more expressive path queries, and is expressed in a very intuitive and SPARQL-friendly way (again, in my opinion). Paths can be provided by either a single predicate, a property path, or a SPARQL query expression. Start and/or end nodes can either be bound or unbound. The documentation can be found here: https://docs.stardog.com/query-stardog/path-queries
The one flaw that sticks out to me is that the only length metric they support is the number of "hops" in the path. If the path is specified by a SPARQL pattern, it would be nice to be able to project out a third variable specifying the value to use for the "length" of that connection. This would enable it to optionally behave more like pathfinding function in a property graph where the length metric is an edge property. I mentioned it in a post in the Stardog Community here: https://community.stardog.com/t/specify-path-length-in-path-queries/4583
Below is an example copied from the linked documentation above- see the documentation for more examples.
There is an implicit relationship between actors based on the movies they appeared together. We can use a basic graph pattern with multiple triple patterns in the path query to extract this information:
PATHS START ?x = :Kevin_Bacon END ?y = :Robert_Redford VIA { ?movie a :Film ; :starring ?x , ?y }Note that this query filters the intermediate nodes; only the connections via movies are desired, not TV series or other types of works.
This query might return:
If the filter on movies is irrelevant, then a more concise version can be used:
PATHS START ?x = :Kevin_Bacon END ?y = :Robert_Redford VIA ^:starring/:starringConsiderations for backward compatibility
The primary issue with backward compatibility I can think of is that it would require extending the SPARQL result format, and likely intermediate query engine internal representations, as this requires storing and returning lists and/or objects of results, or subtables of results, as a first class citizen. If that was supported, then this would be easier. I made an issue about this a while back (#151), but there are other similar feature requests too.