Thinking Clearly .

In the previous post, I gave a hint at the enormous power of (arbitrary) SWRL rules by showing how they can be used (directly and fairly easily) define various built in OWL constructs. SWRL faces the standard tradeoff for expressivity: loss of efficiency. SWRL is undecidable, that is, there is no algorithm that can, in finite time, compute the whether (for example) an axiom is entailed by a SWRL knowledge base. It is, in fact, semi-decidable—if an axiom is entailed, then there is an algorithm that can show that; but if an axiom is not entailed, it’s possible to “go into an infinite loop”, i.e., not to terminate.

In some future post I’ll explain exactly why, how, and when I think decidability matters, but for the moment, let’s presume that it is a desirable property. Also, we should remember that a critical goal of SWRL is to augment OWL, so we should expect serious users of OWL (e.g., people building large OWL ontologies) to want to use these rules and want to use them in conjunction with a reasoner in their existing ontologies. Thus, it would be good if we could add rule support as an extension of existing reasoners (e.g., Pellet!) and get workable performance.

DL Safety is a simple idea which is implicit in many rule systems (especially those with a database or Prolog connection) and has been used in other contexts to regain decidability: Variables in DL Safe rules bind only to explicitly named individuals in your ontology. Adding this restriction is sufficient to make SWRL rules decidable.

What does this restriction really mean? One way of thinking about it is that it shifts SWRL rules from being a kind of super powerful TBox and RBox (i.e., class and property) axiom to them being a (slightly odd) sort of data manipulation (i.e., ABox) axiom.

Consider the SWRL rule for the ancestor relation (discussed in part 1):

      ancestorOf(?X, ?Z) :- ancestorOf(?X, ?Y), ancestorOf(?Y, ?Z).

As you might recall, this is equivalent to declaring that ancestorOf is transitive property. If we impose the DL Safety restriction on it, then that is no longer true (though they coincidence in some cases; transitive properties are a strict expressive superset of the DL Safe version). Let’s consider a case where the DL Safe and non-DL Safe version of this rule diverge.

Consider a simple chain of ancestors:

    :mary :ancestorOf :sheevah.
    :sheevah :ancestorOf :akane.
    :akane a :AncestorOfACreep.

(Yes, I’ve switched to Turtle syntax because, well, either I’m perverse or the tool chain is perverse. My perversity may lie in using this freaking toolchain!)

We can ask for the ancestors of :akane by making a class that uses nominals:

    :AncestorOfAkane  a owl:Class;
        owl:equivalentClass [a owl:Restriction;
            owl:onProperty :ancestorOf;
            owl:hasValue :akane].

With nothing else in the ontology, the only instance of :AncestorOfAkane will be :sheevah, i.e., the direct ancestor. If we add a owl:TransitiveProperty assertion, or the DL Safe rule above, then :mary will also be found to be an instance of this class. So far so good. But what if we know that :akane has a descendent who is a creep, and we want to know who else is an ancestor of a creep. (Yeah, so I hate Akane’s descendants. Sue me. They’re creepy!)

    :akane a :AncestorOfACreep.
    :Creep a owl:Class.  

    :AncestorOfACreep a owl:Class;
        owl:equivalentClass [a owl:Restriction;
            owl:onProperty :ancestorOf;
            owl:someValuesFrom :Creep].

If we are reasoning with the DL Safe rule, then only :akane is an instance of :AncestorOfACreep, because the DL Safe rule does not propagate values to unnamed/unknown entities, and we don’t know any of :akane’s decendents. We only know that she has at least one creepy one.

If we’ve made :ancestorOf transitive (or the rule is interpreted as unrestricted, i.e., not DL Safe), then not only do :mary and :sheevah become instances of :AncestorOfACreep but so do all possible instances of :AncestorOfAkane. So we have a new subsumption relation, as you can see in this screenshot of OWLSight:

Clicking on the “Why?” button gives us the axioms sufficient to produce the subsumption:

Since Pellet can process DL Safe rules (and backs OWLSight), we can browse the DL Safe rule version of this ontology:

As we can see, the only instance of :AncestorOfACreep is :akane, however, all the expected members of :AncestorOfAkane appear:

Unfortunately, there is a bug in the explanation finder which, for some reason, thinks that :ancestorOf is transitive: doesn’t understand that SWRL rules are axioms (more on this in a future post):

You can also play with these from the Pellet command line. I have both versions of the ontology available both in Turtle and in RDF/XML (courtesy of Joshua Tabuer’s Validator/Converter—which, alas, is a bit finicky and doesn’t pretty print RDF/XML nicely at all; but hey, it worked). I use the following options:

     ./pellet.sh -if http://www.cs.man.ac.uk/~bparsia/2007/examples/dl-safe-ancestor.txt  -c TREE -r -s off -ifmt N3 

If you use one of the .owl files, you can leave off the -ifmt. You might try commenting out the transitivity axiom to see what things look like with neither rule. When using SWRL syntax, Pellet will throw up a lot of warnings: Just Ignore Them. UPDATE: Thanks to Mike Smith (in comments) for pointing out that -s off will turn off the warnings.

I’ve not tested these with KAON2, which would have some problems with the nominal I’m using instead of a query. You could pretty easily make some SPARQL queries that exhibit the difference.

I used transitivity because it’s a fairly obvious sort of rule and the unrestricted SWRL version can be paraphrased can be in plain OWL. It’s important to note that unrestricted SWRL can say a hell of a lot more than this!

Still to come: DL Safe SWRL rules vs. other sorts of rules; some SPARQL connections; SWRL and SROIQ; builtins; implementation issues; and who knows?

This entry was posted on Monday, August 27th, 2007 at 9:34 am and is filed under Pellet, SWRL. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.