Walking your fingers through the trees in OWL: why there are things you want to say but can’t

Summary

OWL has a tree model property. This property is (one of the) reasons why the reasoning problems underlying, say, the computation of the inferred class hierarchy, are decidable [1]. As a modeller in OWL, we notice this property because it restricts what can be said in an ontology. Very roughly speaking, in OWL, we describe tree-shaped structures: we illustrate what this means using pictures and videos of two fingers walking along the trees. Some things one would like to say in OWL require using three fingers to do the tracing between the objects in our axioms – making triangles between the objects being related. However, some form of triangles can be described in OWL, and we illustrate these as well.

 

Authors

Robert Stevens and Uli Sattler

Bio-Health and Information Management Groups
School of Computer Science
University of Manchester
Oxford Road
Manchester
M13 9PL

Robert.Stevens@Manchester.ac.uk and sattler@cs.man.ac.uk

 

The tree model Property of OWL

 

The description logic upon which OWL is based uses a form of the tree-model property: the expressive power of OWL is such that the axioms in an ontology can only enforce the (anonymous) objects in a model [2]. We use the core of an ontology about family history to illustrate how OWL restricts ontologies to descriptions of trees. Take the ontology:

 

Class: Man SubClassOf Person
Class: Woman SubClassOf Person
Class: Person SubClassOf (hasMother some Woman) and (hasFather some Man)
ObjectProperty: hasMother Characteristics: Functional SubPropertyOf hasParent
ObjectProperty: hasFather Characteristics: Functional SubPropertyOf hasParent

Here we have a simple ontology that introduces two classes, Man and Woman, that are each a subclass of Person. A person hasFather some Man and hasMother some Woman; hasFather and hasMother are functional and are sub-properties of hasParent. We have illustrated the restriction that OWL places on how instances of the classes introduced can be related via a video.  In the video you can see how the axioms enforce a world where persons and their parents are related via the properties hasMother and hasFather in a tree-shaped structure.

Now assume we add another axiom that describes happy grandchildren (HGC) as those who have a mother who has a mother who is Nice (a nice grandmother):

Class: HGC EquivalentTo: Person and (hasMother some (hasMother some Nice)

An explanation of how we can figure out the meaning of HGC by walking our (family) tree with 2 fingers is given in the next video. Again, you can see that it is possible to use just the two fingers to talk about how the objects in these axioms are related to each other.

Making triangles of properties and objects is (mostly) not allowed

So far, what we have seen is what we can say in OWL. If we, however, wished to define a class of happy children as those children whose mother loves their father, we are facing some difficulties, as explained in our third video. In a nutshell, this idea of happy children would involve the description of a “triangle” between the child, their mother, and their father – and thus it would involve “3 fingers” to keep hold of the relationships between those elements. This breaks the tree shaped structure of the axioms – the triangle forms a non-tree shaped graph. In fact, we cannot define such a concept in OWL, since OWL class descriptions are mostly of the kind that is traceable with two fingers – that is, the tree.

When triangles of things can be done in OWL

 

Next, we will discuss exceptions to this rule of thumb (or fingers!).

First, we can describe triangles – or any form of structure – on named individuals. For example, see the following assertions:

Individual: Peter
Facts: hasMother Sue,
hasFather Bob

Individual: Sue
Facts: loves Bob

Here the facts asserted about Bob, Sue and Peter form a triangle with the hasMother, hasFather and loves properties. This happens all the time with individuals and it is fine to do lots of this sort of non-tree like thing.

 

 

 

Second, we can describe triangular forms of relations via transitive properties or via sub-property chains, as in the following property axioms:

ObjectProperty: hasGrandParent
SubPropertyChain: hasParent o hasParent

ObjectProperty: hasUncle
SubPropertyChain: hasParent o hasBrother

With the hasGrandParent property, where we see objects linked along the hasParent property, we’re forming triangles: a person’s grandparent is also linked to them via their parent. A similar observation holds true for a person’s uncle. Also, transitive properties such as has Ancestor lead to the formation of whole series of triangles between a person and all their ancestors via the direct has Parent relationships.

Last words

 

So, while OWL is great at describing trees, we face some difficulties when we want to describe classes via some features that involve triangular shapes – but triangular structures are ok in other parts of OWL, such as in facts about named individuals and as general characteristics of properties. The tree model property keeps the description logic underlying OWL decidable. Sometimes the things we’d like to say as a modeller break this tree-shaped aspect of OWL’s axioms – you can check what’s going on in your axioms and explain the constraint to yourself and others by walking along a set of objects in a model of your ontology with your fingers; when you need more than two to walk along the objects involved in your description, then you’re often going to be in problems, apart from the exceptions outlined above.

 

 

References

  1. Q.Y.E. Grädel, "Why Are Modal Logics So Robustly Decidable?"http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.28.5238