4

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.

4

1 回答 1

6

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]
于 2013-07-19T16:43:09.093 回答