Current ontology development tools o er debugging support by presenting justi cations for entailments of OWL ontologies. In many cases even a single entailment may have many distinct justi cations, and justi cations for distinct entailments may be critically related. We call the set of relations between multiple justi cations the justi catory structure of an ontology. A restricted analysis of justi catory structure has already been successfully exploited to reduce e ort when debugging ontologies with large numbers of unsatis able classes by identifying root unsatis able classes. In this paper we present a preliminary analytical framework for the justi catory structure of an ontology and explore possible applications.
Explanation support signi cantly improves the user experience when working
with OWL ontologies. With regard to the task of debugging it is often impossible
to nd the cause of an erroneous entailment, such as an unsatis able class,
without any tools that guide the user to the source of the error [
Justi cations are minimal subsets of the ontology that are su cient for an
entailment to hold. Explanation support through justi cations is currently
provided by ontology development tools such as Protege 4. Current research mainly
focuses on making individual justi cations easier to understand, for example
through de ning ne-grained justi cations [
We are now interested not only in what justi cations can tell us about an
entailment, but also how the relationships between justi cations a ect the entire
ontology, the understanding of the user, and potential repair strategies in the
debugging process. Measuring metrics in order to assess properties like the
cohesion of an ontology has been the focus of previous research [
In this paper we introduce the justi catory structure of OWL ontologies, that is, metrics describing the occurrences of multiple justi cations, as well as dependencies and other relations between justi cations in an ontology. We show that these structural properties describe important and useful information to the users, which can help them understand entailments and their origins by providing deeper insight into the ontology. In order to show the usefulness of this approach, we outline potential application areas and explain which aspects of the justi catory structure can be used in the respective context. 2
2.1
In this paper, we use the OWL Manchester Syntax1 and following notation: O for an ontology, A; B; : : : for class names, r and s for property names, and a for an individual. Axioms can be of the form (Class: C SubClassOf: D) or (Class: C EquivalentTo: D), where C and D are class expressions that are built from class and property names.2 An entailment of an ontology O is written as O j= . 2.2
Typically, not all axioms in an ontology are needed to cause an entailment to
hold. In many cases a small subset of the ontology is already su cient. Working
with these subsets when trying to understand the reason for an entailment has
shown to be much easier than having to deal with the full ontology [
O; J j= and,
The unsatis ability of a class is a particularly relevant entailment in the debugging process, as it commonly represents a modelling error in the ontology. A class A is unsatis able wrt. an ontology O if O j= (A SubClassOf: owl:Nothing). An ontology that contains unsatis able classes is called incoherent, as shown in
2 For legibility and space reasons, we omit several parts of the Manchester syntax, including declarations and the leading Class:. The complete examples can be accessed at http://owl.cs.manchester.ac.uk/explanation/owled2010. this simple example where class C is unsatis able: O = fC SubClassOf : A and D
A SubClassOf : E and B B SubClassOf : not D and r some D F SubClassOf : r only A
D SubClassOf : s some owl : T hingg j= C SubClassOf : owl : N othing Here, there exists only one justi cation for the unsatis ability of C, which is the set of the rst three axioms. It is obvious that the error is much easier to spot once we know which axioms to focus on, rather than examining the whole ontology. Often, there exist multiple justi cations for one entailment, and it is not unusual to have ten or more justi cations per entailment, as shown in table 2.
With respect to debugging, it is often the task to nd a repair that \breaks"
the entailment. This can be achieved by removing one axiom from each
justication from the ontology [
While incoherence can be regarded as a modelling error that needs to be repaired, a large number of actively used ontologies do in fact contain unsatis able classes. This does not cause any further problems, unless statements are added that lead to a contradiction in the knowledge base. For example, if the axiom (Individual: a Types: C) was added to the example above, the ontology would be rendered inconsistent, since it would require an instance of an uninstantiable class.
The term ne-grained describes justi cations whose axioms do not contain
any super uous information [
We identify a set of relations that represent di erent aspects of the justi catory structure of an OWL ontology. These aspects can be classi ed into: quanti able properties of justi cations in an ontology (metrics), information about the syntactic relations of justi cations, and semantic relationships between justi cations. 3.1
Multiple justi cations can be regarded in the context of single entailments, as well as for multiple distinct entailments. In the following we mainly discuss the occurrence of multiple justi cations for a single entailment, namely inferred atomic subsumptions and unsatis able named classes.
There are two interesting aspects when dealing with multiple justi cations, which we denote as coping and exploiting. Firstly, when seen from a debugging point of view, we can ask: how can we cope with this potentially large number of justi cations? Is it possible to nd useful information about their interactions, which could simplify the repair process? Based on ndings from preliminary experiments with 16 ontologies (all available from the TONES3 repository), it is easy to see that multiple justi cations do occur in ontologies.
While the set of ontologies presented in table 1 is not representative of all ontologies, it illustrates di erent properties and phenomena that can occur in ontologies of various sizes and expressivities. Table 2 shows the average number of regular and laconic justi cations (AvgR, AvgL), as well as the respective maxima (MaxR, MaxL) measured in our experiments. It also lists the number of unsatis able classes (UC) and how many of these are root unsatis able (RUC). The number of regular justi cations per entailment in our test set di ers # Ontology Expressivity Axioms Entailments 1 MGEDOntology ALEOF (D) 4679 2 2 DOLCE Lite SHIF 536 3 3 Mini Tambis ALCN 400 65 4 Nautilus ALCHF 172 10 5 Generations ALCOIF 60 24 6 Mereology SHIN 80 2 7 Relative Places SHIF 130 7 8 Cell EL + + 14743 11 9 People + Pets ALCHOIN 370 33 10 University SOIN (D) 92 10 11 Numerics SHIF (D) 478 3098 12 Earth Realm ALCHO 1613 2751 13 Economy ALCH(D) 2330 51 14 Programmes SHIF (D) 560 51 15 Adolena SRIQ 415 3 16 Chemical ALCHF 192 43 strongly, ranging from exactly one justi cation (e.g. Mini Tambis, Nautilus) to 24 (DOLCE Lite). The average number of regular justi cations per entailment is 1.8, with an average size of 3.3 axioms. Note that in some cases, entailments with single regular justi cations have multiple laconic ones. The extreme cases in particular, where up to 68 laconic justi cations are obtained for a single entailment, show that it is necessary to develop methods that help users cope with such a large number of justi cations. 3 http://owl.cs.manchester.ac.uk/repository
Exploiting refers to a di erent aspect of multiple justi cations: is it possible to utilize this phenomenon in order to obtain information about the ontology itself? In which way do the relationships between justi cations a ect other properties of the ontology, and vice versa? For example, regarding the results from our experiments, we would like to learn why there are such signi cant di erences in the numbers of justi cations for each ontology. From these considerations also follows the question of how this information can then be made accessible to the user, suited to the required task. 3.2
Simple statistics about the justi cations found in an ontology can provide an insight into its structure and connectedness, which will be discussed in section 4. These statistics include the number and size of regular justi cations for a single entailment, the number and size of laconic justi cations for a single entailment and their respective ratios. 3.3
Subset Relationships One of the most important syntactic relationships is the containment of one justi cation in another. This property has been utilised in the de nition of root and derived unsatis able classes, which are relevant for the debugging and repair process.
Presenting justi cations to the user and distinguishing root and derived
unsatis able classes has shown to drastically reduce user e ort when debugging
an ontology that has multiple unsatis able classes [
In the following example, O entails the unsatis ability of both C and A, J1 =fC SubClassOf: D, C SubClassOf: not Dg and J2 = O being the respective justi cations:
O = fA SubClassOf : r some C
C SubClassOf : D
C SubClassOf : not Dg j= A SubClassOf : owl : N othing A is a derived unsatis able class, as its justi cation J2 is a strict superset of the justi cation J1 for the unsatis ability of C. We can also say that J1 causes the unsatis ability, while J2 propagates it. By repairing C's unsatis ability (for example by removing the third axiom from the set), class A will also be repaired. In terms of debugging unsatis able classes, this shows that by repairing the root unsatis able classes rst all the derived unsatis able classes may be xed at the same time.
In some ontologies, such as Tambis,4 which contains 144 unsatis able classes,
it has been shown that nearly all of the derived unsatis abilities (111 in Tambis)
could be repaired by simple xing a small number of root unsatis able classes
(only 3 in the case of Tambis) [
Intersection As a more general case of subset relations, intersection provides
a starting point when developing a repair strategy for breaking an entailment.
Again, we only consider syntactical overlap here, i.e. multiple justi cations
sharing a common axiom. Removing only one axiom that occurs in the overlapping
parts of multiple justi cations for a single entailment can lead to a repair that
has less impact on the rest of the ontology. This is desirable, as repairs should
be minimal and ideally only a ect the entailment in question [
Entailment It is possible for justi cations to entail each other. This can be both unidirectional (J1 j= J2, J2 2 J1) and bidirectional (J1 j= J2, J2 j= J1). A special case of entailment is a subset relationship, as a set of axioms naturally entails its subsets.
Masking A special case of dependencies between justi cations is the
phenomenon of masking [
O = fA SubClassOf : B and not B and C
C SubClassOf : D and not Dg j= A SubClassOf : owl : N othing The only justi cation is J1 =fA SubClassOf: B and not B and C g, and there are no root / derived relationships. If we attempt to break the entailment, for example by removing (not B) from the justi cation, it still holds because of the unsatis ability now being derived from the second axiom. This gives us another justi cation for the entailment, namely J2 = O, which is clearly a superset of J1. This case is not captured by the above de nition for derived justi cations, as a superset of a justi cation for the same entailment is by de nition not a justi cation (due to the minimality constraint). However, we lose valuable information if this dependency of J2 on J1 is not pointed out to the user in the repair process. Shared Cores Masking Shared cores describe a particular type of masking, where the justi cations have parts that are structurally equal. This is illustrated by the following example:
O = fA SubClassOf : B and not B and C
A SubClassOf : B and not Bg j= A SubClassOf : owl : N othing The part (and C) can be removed from the justi cation J1 = fA SubClassOf: B and not B and C g, as it is not relevant for the entailment to hold. This leads to the laconic version of J1, which is syntactically equal to J2 = fA SubClassOf: B and not B g. If this phenomenon is pointed out to the user, they can easily see that there exists only a single reason for an entailment rather than several, which they can then focus on in the repair process. 3.5
De ning or classifying the justi catory structure of an ontology with respect to some metric allows to investigate how the structure a ects the ontology and vice versa. We can potentially categorise di erent types of justi catory structure intuitively, based on their complexity: a weak justi catory structure exhibits only a small average number of mostly disjoint justi cations, such as one justi cation per entailment. An ontology with a strong (complex) justi catory structure comprises a large number of justi cations for each entailment and a high degree of interconnectivity (intersections, subset relationships, entailment) between them. Extensive experiments will allow us to identify the aspects of justi catory structure and their respective weights that are most suitable for specifying a metric to classify it. 4
In this section, we provide an overview of potential applications of analysing the justi catory structure. These cover a wide range of potential users from ontology engineers to reasoner developers, as well as both task-speci c and global usage in the ontology development process. 4.1
One of the main tasks that explanation deals with is debugging support in the ontology engineering process. First of all, by making use of the information about dependencies between justi cations, the user can be guided to understand the cause of an entailment. The information can then be used to provide a suitable repair strategy, that allows the user to amend the entailment without causing unwanted changes to the ontology. We use the abstract term information here, as there exist di erent levels of interaction with the user: we can provide raw data, such as J1 J2, which can already be helpful for experienced users. By embedding this information into a more user-friendly representation and exploiting it in tools, such as a visualisation interface, understanding dependencies and their impact on entailments can be made more accessible to the user. 4.2
Explanation support for ontology comprehension can be considered di erent
from using justi cations for debugging, as it is less task-based and success is
harder to de ne: what exactly does understanding the ontology mean? One way
of de ning ontology comprehension is based on the ability to answer questions
relating to information in the ontology, as previously shown in a user study
[
Thus far, axiomatic richness has no formal de nition and is more of an abstract concept than a measurable property. As an example, taxonomic ontologies containing only trivial axioms of the form (A SubClassOf: B) are commonly regarded as axiomatically weak. A simple indicator for axiomatic richness could be a large average number of justi cations for entailments. Reasoner development and testing can be regarded as another potential application area of the justi catory structure. We can ask: does a certain type of justi catory structure make reasoning harder? Again, this hypothesis has to be tested in more extensive experiments. 5
In this paper, we have presented a framework for analysing the various dependencies between justi cations in OWL ontologies, which are believed to o er useful structural information about an ontology. We have shown that there exists a number of interactions between justi cations, such as syntactic overlap and entailment. The di erent aspects of this justi catory structure of an ontology were grouped into syntactical connections, semantic relations and metrics. Services using the justi catory structure in the ontology development process could support users with debugging tasks, assist in understanding ontologies and provide metrics for classifying ontologies.
For future work, we aim to de ne the di erent aspects of the justi catory structure of an ontology more clearly. In the long term, algorithms and services will be developed that generate and use the data, which can then be presented to the user in a way tailored to the respective task. Examining di erent forms of visualisation for this purpose o ers another extension to the topic discussed in this paper.