I'm currently working on a shortest path problem that does have a
fixed property. In my application, icons can optionally be associated
with types and I'd like entities to use the "closest" icon(s) (i.e.
direct type(s), then parent(s), then grandparent(s), etc.). Assuming
no RDFS inferencing were performed, to get the icon(s) for particular
instance you'd do something like:
PREFIX rdf:<http://www.w3.org/1999/02/22-rdf-syntax-ns#>
PREFIX rdfs:<http://www.w3.org/2000/01/rdf-schema#>
PREFIX ex:<http://example.org/>
select ?icon
where {
ex:Entity1 rdf:type/SHORTEST(rdfs:subClassOf*/ex:hasIcon) ?icon .
}
I saw some discussion of path lengths at [1][2], and I understand why
general path length is difficult because of the introduction of a new
datatype, but the shortest path operator here doesn't require
reporting the actual length to the user.
Do you think it's feasible to implement such an operator that utilizes
a breadth-first search in order to match the shortest paths? I have
to admit I'm not as familiar with the property path code as I'd like
to be.
Yes and I think it's a good idea to have it.
SPARQL isn't a graph analysis language but access to some common
operators so mixed purpose queries can be done is going to be helpful.
I am doing some work on property paths at the moment to add the features
that SPARQL-WG is likely to adopt. Even if they don't having them in
ARQ/extended-SPARQL will be good so I'm doing them anyway. [*]
As I have the parser and syntax support to update, I'll add SHORTEST at
the same time. It'll parse ... and throw "unimplemented" if touched at
execution time. ARQ/extended-SPARQL experimental feature.
Alternatively, is there some way I'm missing to do this with sub-queries?
As the path can be arbitrary length, and * and + give you no control on
outcome, there isn't a way to use a sub-query (that I can think of!).
Floyd-Warshall grows the shortest path from each end of the path and
terminates when it meets in the middle. That's an arbitrary loop.
Andy
Thanks,
Stephen
[1]
http://www.w3.org/2009/sparql/meeting/2009-03-17#path_lengths___26___20_path__2d_matching_variables
[2] http://www.w3.org/2009/sparql/wiki/Feature%3aPathLength
Andy
