Measuring distances among classes in RDF/OWL graphs

Question

Maybe someone could give me a hint. Is it possible to measure the distance between 2 concepts/classes that belong to the same ontology?

For example, let's suppose I have an ontology with the Astronomy class and the Telescope class. There is a link between both, but it is not a direct link. Astronomy has a parent class called Science, and Telescope has a parent class called Optical Instrument which belongs to its parent called Instrumentation, that is related to a class called Empirical Science that finally belongs to a class called Science.

So there is an indirect link between Telescope and Astronomy, and I want to find out the number of steps needed to reach one class starting from the another one.

Is there an easy SPARQL query that resolves that question? Or are there better ways to do that job? Or is not possible to find that out using Semantic Web paradigm?

Any hint will be very appreciated.

Answer 1

SPARQL provides the ability to search for arbitrary length paths in a graph but no mechanism to tell you the length of that path.

So you can do something like:

SELECT * WHERE { ?s ex:property+ ?o }

The syntax is very much like regex so you can do alternatives, restricted cardinalities etc

Answer 2

In my understanding SPARQL doesn't contain any recursive constructions to be able to measure indirect link of arbitrary length. The best you could do is to prepare set of queries distance_1(a, b), distance_2(a, b)... to check for specific distance between two concepts.

Another alternative is to discover this information using non-SPARQL technology, for example writing graph traversing algorithm in Python with RDFlib.

Answer 3

Since you explicitly mentioned that you are talking about classes and they will be in the same ontology, it is safe to assume that they will be always connected (because ultimately both will be a subclass of "Thing", right?). On the other hand, the path I mentioned in the parentheses (Class1 -> ... -> Thing <- ... <- Class2) is a trivial one, so I assume you want to find... all of the existing paths between two classes, in other words, all of the existing paths between two vertices. Is that true? Or are you looking for the shortest path? Your question is not very clear in that aspect, can you clarify it?

As far as I know there is no simple SPARQL construct that will list all the paths between classes or the shortest path. However some semantic web triple stores come with graph traversal algorithms such as breadth-first-search or depth-first-search, please refer to:

• http://www.franz.com/agraph/support/documentation/current/lisp-reference.html#sna

You may also find the source code of the following project very useful:

• RelFinder, Interactive Relationship Discovery in RDF Data, http://www.visualdataweb.org/relfinder.php