2

The problem is how to calculate the distance between two nodes (concepts) in a Triple Store (RDF) using sparql queries without know the type of edges. Essencially, is to use Dijkstras_algorithm to find the shorter path between two concepts in a Triple Store.

It is possible if we know the type of egde: Calculate length of path between nodes?

One other solution is to use classes distances(do not work if concepts are not extended from the main classes): Measuring distances among classes in RDF/OWL graphs

Example:

Find the shorter distance between http://bioinformatics.ua.pt/coeus/resource/uniprot_P01008 and http://bioinformatics.ua.pt/coeus/resource/go_GO:0005576

Community
  • 1
  • 1
Malex
  • 41
  • 4
  • You may find a wildcard useful. E.g., see http://stackoverflow.com/questions/30916040/sparql-is-there-any-path-between-two-nodes/30916584#30916584, but beware that once you have wildcards, there may be many more paths than you were expecting (e.g., if you're using a reasoner). And all of these techniques presume that there's just one path between the nodes. – Joshua Taylor Jun 25 '15 at 11:09

1 Answers1

4

You can use the same technique that's used in Calculate length of path between nodes?, but you'll need to use a wildcard instead of a particular property. The pattern (<>|!<>) is a wildcard, because every property is either <> or it isn't. You could also use (:|!:), but that will only work if you have a : prefix defined. (<>|!<>) will always work. Here's an example:

@prefix : <urn:ex:>

:a :p :b .
:b :q :c .
:c :r :d .
:d :s :e .

prefix : <urn:ex:>

select ?start ?end (count(?mid) as ?length) {
  ?start (<>|!<>)* ?mid .
  ?mid (<>|!<>)+ ?end .
}
group by ?start ?end

------------------------
| start | end | length |
========================
| :a    | :b  | 1      |
| :a    | :c  | 2      |
| :a    | :d  | 3      |
| :a    | :e  | 4      |
| :b    | :c  | 1      |
| :b    | :d  | 2      |
| :b    | :e  | 3      |
| :c    | :d  | 1      |
| :c    | :e  | 2      |
| :d    | :e  | 1      |
------------------------
Community
  • 1
  • 1
Joshua Taylor
  • 84,998
  • 9
  • 154
  • 353
  • `<>` only works if a `BASE` is defined, some SPARQL processors may infer a base if one is not explicitly defined but it would be incorrect to say that `<>` will always work – RobV Jun 29 '15 at 08:47
  • @RobV I haven't read the referenced RFC yet, but the SPARQL 1.1 says (emphasis added), "The BASE keyword defines the Base IRI used to resolve relative IRIs per RFC3986 section 5.1.1, "Base URI Embedded in Content". Section 5.1.2, "Base URI from the Encapsulating Entity" defines how the Base IRI may come from an encapsulating document, such as a SOAP envelope with an xml:base directive or a mime multipart document with a Content-Location header. The "Retrieval URI" identified in 5.1.3, Base "URI from the Retrieval URI", is the URL from – Joshua Taylor Jun 29 '15 at 13:15
  • which a particular SPARQL query was retrieved. **If none of the above specifies the Base URI, the default Base URI (section 5.1.4, "Default Base URI") is used."**" That makes it sound like there will always be a base URI. – Joshua Taylor Jun 29 '15 at 13:16
  • @RobV OK, going into the RFC, section 5.1.4 says "If none of the conditions described above apply, then the base URI is defined by the context of the application. As this definition is necessarily application-dependent, failing to define a base URI by using one of the other methods may result in the same content being interpreted differently by different types of applications. A sender of a representation containing relative references is responsible for ensuring that a base URI – Joshua Taylor Jun 29 '15 at 13:23
  • "for those references can be established. Aside from fragment-only references, relative references can only be used reliably in situations where the base URI is well defined." So it's not really clear to me whether an application must provide a base URI or not. There's no language about "*if* an application defines a base URI", etc., but I wouldn't stake too much on that. But a query like this definitely shirks its responsibility to "[ensure] that a base URI for those references can be established." – Joshua Taylor Jun 29 '15 at 13:26