Retrieving all paths in an OWL class hierarchy with SPARQL and Jena

Question

I have an RDF graph of with a hierarchy three levels deep. I want to retrieve all the paths starting from the root of the class hierarchy (i.e., owl:Thing) down to classes in the third level without using a reasoner. For instance, I would like the path C₁ &rightarrow; C₂ &rightarrow; C₃ is a path, where each C_i is a class at the i^th level of the hierarchy.

I need to retrieve all the paths in the RDF graph using the breadth first search algorithm with no considerations to the object properties in the graph.

You put "Thing" in parenthesis. Do I understand you correctly: you have a class hierarchy with some root, and you're looking to find all the paths from the root to the subclasses (with maximum depth 3)? Can you provide an example of your data and the results that you'd _like_ to get back? That would help in formulating a solution. — Joshua Taylor, Jul 19 '13 at 16:28
Yes I have a class hierarchy but with only only one root that is Thing is a root class. — user2502144, Jul 19 '13 at 19:34
Take for example the following ontology: http://protege.cim3.net/file/pub/ontologies/camera/camera.owl the paths I want one should look like Thing - PurchaseableItem - Camera - Digital, Thing - PurchaseableItem -Camera - Large-Format and so on...and other paths. Thank you. — user2502144, Jul 19 '13 at 20:08

Joshua Taylor · Accepted Answer · 2014-05-20T15:09:46.977

Given some data like this (where length of the class name is an indication of the depth of the class in the hierarchy):

@prefix : <http://example.org/> .
@prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#> .

:a a rdfs:Class .

:aa rdfs:subClassOf :a .
:ab rdfs:subClassOf :a .
:ac rdfs:subClassOf :a .

:aaa rdfs:subClassOf :aa .
:aab rdfs:subClassOf :aa .
:aac rdfs:subClassOf :aa .

:aaba rdfs:subClassOf :aab .
:aabb rdfs:subClassOf :aab .

:aba rdfs:subClassOf :ab .
:abb rdfs:subClassOf :ab .

You can use a SPARQL query to select the paths that you're looking for.

Using a SPARQL query

You can write a SPARQL query like this to get the following results:

prefix : <http://example.org/>
prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#>

select ?c1 ?c2 ?c3 where { 
  values ?c1 { :a }
  ?c1 ^rdfs:subClassOf ?c2 .
  OPTIONAL {
    ?c2 ^rdfs:subClassOf ?c3 .
  }
}
order by ?c3 ?c2 ?c1

-------------------
| c1 | c2  | c3   |
===================
| :a | :ac |      |
| :a | :aa | :aaa |
| :a | :aa | :aab |
| :a | :aa | :aac |
| :a | :ab | :aba |
| :a | :ab | :abb |
-------------------

Using the camera ontology

This approach works with the camera ontology that has been mentioned in the comments, though the query requires a little extension to handle deeper class paths. Thus:

PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
PREFIX owl: <http://www.w3.org/2002/07/owl#>
PREFIX : <http://www.xfront.com/owl/ontologies/camera/#>

select * where { 
  values ?c1 { owl:Thing } 
  ?c1 ^rdfs:subClassOf ?c2 .
  OPTIONAL { 
    ?c2 ^rdfs:subClassOf ?c3 .
    OPTIONAL { 
      ?c3 ^rdfs:subClassOf ?c4 .
    }
  }
}
order by ?c4 ?c3 ?c2

-----------------------------------------------------------
| c1        | c2                | c3      | c4            |
===========================================================
| owl:Thing | :Money            |         |               |
| owl:Thing | :Range            |         |               |
| owl:Thing | :Window           |         |               |
| owl:Thing | :PurchaseableItem | :Body   |               |
| owl:Thing | :PurchaseableItem | :Lens   |               |
| owl:Thing | :PurchaseableItem | :Camera | :Digital      |
| owl:Thing | :PurchaseableItem | :Camera | :Large-Format |
-----------------------------------------------------------

Using the Jena API

While the above SPARQL query produces the paths in the order that would expected from a breadth first traversal, there is actually no guarantee on how ARQ generates the results. We can also implement a Breadth First Search directly, using the Jena Model API to retrieve subclasses. Here's a straightforward implementation:

import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import com.hp.hpl.jena.rdf.model.Model;
import com.hp.hpl.jena.rdf.model.ModelFactory;
import com.hp.hpl.jena.rdf.model.Resource;
import com.hp.hpl.jena.rdf.model.StmtIterator;
import com.hp.hpl.jena.vocabulary.OWL;
import com.hp.hpl.jena.vocabulary.RDFS;

public class BFSInRDFWithJena {

    public static List<List<Resource>> BFS( final Model model, final Queue<List<Resource>> queue, final int depth ) {
        final List<List<Resource>> results = new ArrayList<>();
        while ( !queue.isEmpty() ) {
            final List<Resource> path = queue.poll();
            results.add( path );
            if ( path.size() < depth ) {
                final Resource last = path.get( path.size() - 1 );
                final StmtIterator stmt = model.listStatements( null, RDFS.subClassOf, last );
                while ( stmt.hasNext() ) {
                    final List<Resource> extPath = new ArrayList<>( path );
                    extPath.add( stmt.next().getSubject().asResource() );
                    queue.offer( extPath );
                }
            }
        }
        return results;
    }

    public static void main( final String[] args ) throws IOException {
        final Model model = ModelFactory.createDefaultModel();
        try ( final InputStream in = BFSInRDFWithJena.class.getClassLoader().getResourceAsStream( "camera.owl" ) ) {
            model.read( in, null );
        }

        // setup the initial queue
        final Queue<List<Resource>> queue = new LinkedList<>();
        final List<Resource> thingPath = new ArrayList<>();
        thingPath.add( OWL.Thing );
        queue.offer( thingPath );

        // Get the paths, and display them
        final List<List<Resource>> paths = BFS( model, queue, 4 );
        for ( List<Resource> path : paths ) {
            System.out.println( path );
        }
    }
}

[http://www.w3.org/2002/07/owl#Thing]
[http://www.w3.org/2002/07/owl#Thing, http://www.xfront.com/owl/ontologies/camera/#PurchaseableItem]
[http://www.w3.org/2002/07/owl#Thing, http://www.xfront.com/owl/ontologies/camera/#Window]
[http://www.w3.org/2002/07/owl#Thing, http://www.xfront.com/owl/ontologies/camera/#Range]
[http://www.w3.org/2002/07/owl#Thing, http://www.xfront.com/owl/ontologies/camera/#Money]
[http://www.w3.org/2002/07/owl#Thing, http://www.xfront.com/owl/ontologies/camera/#PurchaseableItem, http://www.xfront.com/owl/ontologies/camera/#Camera]
[http://www.w3.org/2002/07/owl#Thing, http://www.xfront.com/owl/ontologies/camera/#PurchaseableItem, http://www.xfront.com/owl/ontologies/camera/#Lens]
[http://www.w3.org/2002/07/owl#Thing, http://www.xfront.com/owl/ontologies/camera/#PurchaseableItem, http://www.xfront.com/owl/ontologies/camera/#Body]
[http://www.w3.org/2002/07/owl#Thing, http://www.xfront.com/owl/ontologies/camera/#PurchaseableItem, http://www.xfront.com/owl/ontologies/camera/#Camera, http://www.xfront.com/owl/ontologies/camera/#Digital]
[http://www.w3.org/2002/07/owl#Thing, http://www.xfront.com/owl/ontologies/camera/#PurchaseableItem, http://www.xfront.com/owl/ontologies/camera/#Camera, http://www.xfront.com/owl/ontologies/camera/#Large-Format]

Thank you. But that is not what I want. Take for example the following ontology: http://protege.cim3.net/file/pub/ontologies/camera/camera.owl the paths I want one should look like Thing PurchaseableItem Camera Digital and so on... — user2502144, Jul 19 '13 at 20:05
@user2502144 Yes, so you replace `:a` by `owl:Thing`, and since it seems that you want four layers of classes (since you're including the `owl:Thing`), you add one more `OPTIONAL` pattern to get out to `?c4`. — Joshua Taylor, Jul 19 '13 at 20:51
@user2502144 I've updated the answer to show how this query can be used with the `camera.owl` you linked to. — Joshua Taylor, Jul 19 '13 at 20:57
Joshua the answer is correct, but that is not the approach I need to retrieve those paths. I need to retrieve all the paths in an RDF graph using the BREADTH FIRST SEARCH Algorithm in Jena. Thank you. — user2502144, Jul 20 '13 at 05:59
OK, so you mean you actually want to use the Jena Model or OntModel API and write the traversal? Take a look [another answer](http://stackoverflow.com/a/17026669/1281433) I've posted about performing depth first search on an RDF graph using Jena's API. Assuming you've got some familiarity with how to implement breadth first and depth first searches, that example should show enough of the Jena specific API that you'll need to do a BFS. — Joshua Taylor, Jul 20 '13 at 13:45
@user2502144 In addition to the answer linked in the previous comment, I've added some Java code here that uses the Jena API to perform a Breadth First Traversal of the class hierarchy up to a given depth. — Joshua Taylor, Jul 20 '13 at 14:19
@JoshuaTaylor What is we don't have the depth of the class in the 'camera ontology' example? — RFAI, Jul 20 '19 at 13:40

Retrieving all paths in an OWL class hierarchy with SPARQL and Jena

1 Answers1

Using a SPARQL query

Using the camera ontology

Using the Jena API

Linked