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
C1 →
C2 →
C3
is a path, where each
Ci
is a class at the ith 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.
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.
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 |
-------------------
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 |
-----------------------------------------------------------
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]