With the increased use of ontologies in semantically-enabled applications, the issue of debugging defects in ontologies has become increasingly important. These defects can lead to wrong or incomplete results for the applications. Debugging consists of the phases of detection and repairing. In this paper we focus on the repairing phase of a particular kind of defects, i.e., the missing relations in the is-a hierarchy. We show that this can be formalized as an abduction problem. Further, we define properties for the ontology, the set of is-a relations to repair and the domain expert, as well as preference criteria on solutions and discuss the influences of these properties and criteria on the existence of solutions for the abduction problem. We also discuss the consequences of our analyses of the repairing problem for the development and use of debugging systems.
Developing ontologies is not an easy task, and often the resulting ontologies are not
consistent or complete. Such ontologies, although often useful, also lead to problems
when used in semantically-enabled applications. Wrong conclusions may be derived
or valid conclusions may be missed. Defects in ontologies can take different forms
(e.g., [
Modeling defects have mainly been discussed for taxonomies, i.e., from a knowledge representation point of view, a simple kind of ontologies. The focus has been on defects regarding the is-a structure (Section 5). In addition to its importance for the correct modeling of a domain, the structural information in ontologies is also important in semantically-enabled applications such as ontology-based search and annotation. In this paper we formalize the problem of repairing the is-a structure of ontologies.
There are different ways to detect missing is-a relations (Section 5). One way is inspection by domain experts. Another way is to use ontology learning techniques or patterns. When the ontology is part of a network of ontologies connected by mappings, missing is-a relations may be detected using logical derivation in the network. However, although there are many approaches to detect missing is-a relations, these approaches, Missing is-a relations • wrist joint is-a joint • hip joint is-a joint • knee joint is-a joint • elbow joint is-a joint • ankle joint is-a joint • shoulder joint is-a joint • metacarpo-phalangeal joint is-a joint
Thing autopod joint limb joint joint hinderlimb joint forelimb joint joint of rib joint of vertebral arch hip joint foot joint knee joint ankle joint hand joint elbow joint wrist joint
shoulder joint metacarpo-phalangea joint in general, do not detect all missing is-a relations. For instance, although the precision for the linguistic patterns approaches is high, their recall is usually very low.
In this paper we assume that the detection phase has been performed. We assume that we have obtained a set of missing is-a relations for a given ontology (validated or not) and focus on the repairing phase. In the ideal case where our set of missing is-a relations contains all missing is-a relations, the repairing phase is easy. We just add all missing is-a relations to the ontology and a reasoner can compute all logical consequences. However, when the set of missing is-a relations does not contain all missing is-a relations - and this is the common case - there are different ways to repair the ontology.
For instance, Figures 1 and 2 (T ) show a small ontology representing a part of the Adult Mouse Anatomy (MA) ontology concerning joint, that is relevant for our discussion. M is a set of detected missing is-a relations. Adding these relations to the ontology will repair the missing is-a structure. However, there are other more interesting possibilities. For instance, adding limb-joint ⊑˙ joint also repairs the missing is-a structure. Further, this is-a relation is correct according to the domain and constitutes a new isa relation that was not derivable from the ontology and not originally detected by the detection algorithm.
The contributions of this paper are the following. First, in Section 2 we formalize the
problem of repairing missing is-a structure as an abduction problem (extension of [
In the following we explain how the problem of finding possible ways to repair the
missing is-a structure in an ontology is formalized as a generalized version of the TBox
abduction problem (extension of [
set of atomic concepts. Let M = { Ci ⊑˙ Di | 1 ≤ i ≤ m } be a set of TBox assertions where Ci, Di ∈ C. Let H = {Ei⊑˙ Fi | 1 ≤ i ≤ n} where Ei, Fi ∈ C. A solution to the generalized TBox abduction problem (GTAP) (T, C, H, M ) is any finite set S ⊆ H, such that T ∪ S is consistent and T ∪ S |= M . The set of all such solutions is denoted as S(T, C, H, M ).
Moreover, we are interested in two problems which are useful in practice. The first problem is the so called existence problem. That is, the decision problem of whether S(T, C, H, M ) 6= ∅. Clearly, with a concrete debugging task the existence problem should be answered at the beginning. If the answer to the existence problem is positive, 1 In the remainder of this paper when we say that concept subsumptions or is-a relations are correct, we mean correct according to the domain. we are interested in finding a solution2. This is normally a realistic goal in practice, since the number of all solutions could be considerably big.
Next, we discuss different properties of T , H and M and how these properties and their combinations affect the existence and type of solutions. In this discussion we make the assumption that the domain is consistent.
The GTAP definition requires T to be consistent. If this would not be the case, it would mean that the original ontology is not consistent. In this case approaches for debugging semantic defects could be used to obtain a consistent ontology. We also note that if T is not consistent then there are no solutions satisfying the definition (as T ∪ S would be inconsistent). However, even if T is consistent, it is possible that T contains relations which are not correct. It would mean that the developers introduced a modeling defect. Therefore, we indentify two cases for T - all the is-a relations in T are correct (’T correct’ in Table 1), or not (’T not correct’ in Table 1).
For M there are 2 cases. In the first case we assume that all is-a relations in M are correct, and thus they are really missing is-a relations (’Missing’ in Table 1). In the second case M may contain missing as well as wrong is-a relations (’Missing + Wrong’ in Table 1). This is a common case when possible missing is-a relations are generated by detection algorithms (e.g., using patterns or ontology learning methods) and not validated by a domain expert. It may also occur when M is generated by domain experts (e.g., using inspection) - as it is an error-prone task, the experts may make mistakes.
For H we identified the following interesting cases. In the first case (’Complete
Knowledge’ in Table 1) H contains all correct is-a relations and no others. In this case
we are sure that if an is-a relation belongs to H , it is correct and if not, it is not
correct. This case represents the ideal situation of an all-knowing domain expert. In the
second case (’Partial-Correct’ in Table 1) H contains only correct is-a relations, but not
necessarily all. This case represents a domain expert who knows a part of the domain
well. If the domain expert validates an is-a relation as correct, it is correct. Otherwise,
the is-a relation is wrong or the domain expert does not know. An approximation of
this case is when using several domain experts and a skeptical approach. We only
consider an is-a relation correct if all domain experts validate it as correct. In the third
case (’Wrong’ in Table 1) H may contain relations that are not correct. In this case,
the domain expert can make mistakes regarding the validation of is-a relations. Some
wrong is-a relations may be validated as correct. This is a common case as exemplified
by the use case in [
M Complete M 6⊆ H Knowledge No solution PartialCorrect
M 6⊆ H No solution
T correct M is solution All solutions are correct M ⊆ H or M 6⊆ H No solution if M 6⊆ H ∧ T ∪ H 6|= M if M ⊆ H then M is a solution if M 6⊆ H ∧ T ∪ H |= M then H is a solution All solutions are correct M ⊆ H or M 6⊆ H No solution if M 6⊆ H ∧ T ∪ H 6|= M No solution if
∀S : S 6= ∅ ∧ S ⊆ H → T ∪ S inconsistent if M ⊆ H then M is a solution if M 6⊆ H ∧ T ∪ H |= M ∧ T ∪ H consistent
then H is a solution If M is solution, then correct, no guarantee otherwise M ⊆ H M is solution If M is solution, then correct, no guarantee otherwise
Missing
T not correct
An ideal situation is the case where the domain expert has complete knowledge (H contains all correct is-a relations and no others) and T and M contain only correct is-a relations. In this case, M ⊆ H. Further, M is a solution and all solutions are correct.
For any case where T ∪ M is inconsistent, there is no solution. Indeed, for any solution S we have that T ∪ S |= M and thus T ∪ S would not be consistent.
In the cases where M contains wrong is-a relations, there may be no solutions. If there are solutions, these are not correct. Further, correctness of solutions is only guaranteed when M does not contain wrong is-a relations and H represents complete knowledge or partial-correct. There are no solutions if T ∪ S is inconsistent for every non-empty subset S of H .
If M ⊆ H and T ∪ M is consistent, then M is a solution. If M 6⊆ H , T ∪ H is consistent and T ∪ H |= M , then H is a solution.
In the case of no expert (H = {Ei ⊑˙Fi | Ei, Fi ∈ C}) we have that M ⊆ H and all is-a relations are allowed in the solution. Therefore, if T ∪ M is consistent, then M is a solution, otherwise there is no solution. However, as there is no domain expert, there is no guarantee that any solution other than M is correct. Further, in the cases where M contains wrong is-a relations, M is a solution, but not correct. As there is no validation, only logical consistency can be guaranteed, but no correctness. 3
There can be many solutions for a GTAP and, as explained in Section 1, not all solutions are equally interesting. Therefore, we propose two preference criteria on the solutions.
be subset minimal iff there is no proper subset S′ ( S such that S′ is a solution. The set of all subset minimal solutions is denoted as Smin(T , C, H, M ).
Examples of subset minimal solutions for P1 in Figure 2 are {limb-joint ⊑˙ joint} and {hinderlimb-joint ⊑˙ joint, forelimb-joint ⊑˙ joint}.
Assuming there exist solutions, the answer to the existence problem for subsetminimal solutions is yes, if and only if T ∪ H |= M . To find a solution S, we can start from H , and remove the is-a relations h stepwise, such that T ∪ H \ h |= M holds. The process continues until no is-a relation can be removed. Thus if the entailment problem for the underlying ontology is tractable, finding a solution can be done in polynomial time. This is indeed the case for the is-a taxonomy.
The second criterion prefers solutions that imply more information.
Definition 3 (More Informative) Let S and S′ be two solutions to the GTAP (T , C, H, M ). S is said to be more informative than S′ iff T ∪ S |= T ∪ S′ and there exists a ψ such that T ∪ S |= ψ and T ∪ S′ 6|= ψ. Further, we say that S is equally informative as S′ iff T ∪ S |= S′ and T ∪ S′ |= S.
Consider two solutions to P1 in Figure 2, S = {limb-joint ⊑˙ joint} and S’={hinderlimbjoint ⊑˙ joint, hand-joint ⊑˙ joint}. S is more informative than S’ as T ∪ S entails limbjoint ⊑˙ joint in addition to everything that T ∪ S’ entails.
to be semantically maximal iff there is no solution S′ which is more informative than S. The set of all semantically maximal solutions is denoted as Smax(T , C, H, M ).
Analogous to the subset minimality, assuming the existence of GTAP solutions, the answer to the existence problem for a semantically maximal solution is yes, if and only if T ∪ H |= M holds. Moreover, in the case where M ⊆ H , and T ∪ H is consistent, H is a semantically maximal solution.
In practice, both of the above two criteria are desirable. However, only with the semantic maximality we might obtain a solution with redundancy. Although subset minimality does not yield redundancy, there is no guarantee that the solution is the most informative. In the following we propose definitions on solutions by combining these criteria. There are diverse interpretations for the combination of subset minimality and semantic maximality, depending on what kind of priority we assign for the single preferences. A first interpretation implies a higher priority on subset minimality than the semantic maximality. As the second interpretation, higher priority for semantic maximality can be assigned to subset minimality. In the third interpretation, the skyline-style interpretation, we treat both preferences equally and the chosen solution is such that there does not exist another solution which is preferable on both criteria.
(T , C, H, M ) is said to be minmax optimal iff S is subset minimal and there does not exist another subset minimal solution S′ such that S′ is more informative than S. The set of all minmax optimal solutions is denoted as Smmianx(T , C, H, M ).
Lemma 1. Smmianx(T , C, H, M ) ⊆ Smin(T , C, H, M )
As an example, {limb-joint ⊑˙ joint} is a minmax optimal solution for P1, while {hinderlimb-joint ⊑˙ joint, forelimb-joint ⊑˙ joint} is a minmax optimal solution for P2.
The existence problem is equivalent to the existence problem of the subset minimal solutions, i.e., there exists a subset minimal solution if and only if there exists a minmax optimal solution. On the other hand, finding a minmax optimal solution tends to be a harder problem. One naive method is first collecting all the subset minimal solutions, then removing those which are less informative. Obviously this is intractable, because theoretically there could be an exponential number of subset minimal solutions already.
In practice, minmax optimal solutions ensure fewer is-a relations to be added, thus avoiding redundancy. This is desirable if the domain expert would prefer to look at as small solutions as possible. The disadvantage is that there may be redundant relations that are correct and not be derivable when they are not added.
GTAP (T , C, H, M ) is said to be maxmin optimal iff S is semantically maximal and there does not exist another semantically maximal solution S′ such that S′ is a proper subset of S. The set of all maxmin optimal solutions is denoted as Smmianx(T , C, H, M ). Lemma 2. Smmianx(T , C, H, M ) ⊆ Smax(T , C, H, M )
As an example, {limb-joint ⊑˙ joint, autopod-joint ⊑˙ limb-joint} is a maxmin optimal solution for P1.
Analogous to the case of minmax optimal, the existence problem of maxmin optimal is equivalent to the existence problem of the semantic maximal solutions. Moreover, if H is a semantically maximal solution, finding a maxmin optimal solution S can be done by starting from H , and stepwise removing the is-a relations h such that T ∪ S \ h |= H holds. Intuitively, the goal is to remove the redundant relations in H . Of course there might be multiple maxmin optimal solutions in this regard, but finding one such a solution is tractable as long as the reasoning task for the underlying logic is tractable.
The advantage of the maxmin optimal semantics is that a maximal body of correct information is added to the ontology. If the domain expert would prefer to look at as informative solutions as possible without (set) redundancy, maxmin optimal solutions is preferable than the minmax optimal solutions. This conclusion can even be strengthened from the efficiency point of view, as finding a maxmin optimal solution is more efficient than finding a minmax optimal one. The disadvantage is that more relations need to be validated.
For the skyline interpretation, we consider the subset minimality and the semantic maximality as two dimensions for a solution S. S is skyline optimal if it is not dominated by any other solution. A solution dominates another solution if it is as good or better in all dimensions and better in at least one dimension. Therefore regarding the above two dimensions we define that a solution S dominates another solution S′ if one of the following conditions is fulfilled: 1. S ( S′ and S is more informative than S′, or 2. S = S′ and S is more informative than S′, or 3. S ( S′ and S is equally informative as S′.
It is easy to verify that condition 1 and 2 can never be fulfilled, due to the monotonicity property of the entailment. Therefore, a solution S dominates another solution S′ if and only if condition 3 is fulfilled. Accordingly, we have the definition for the skyline optimality as follows.
Definition 7 (Skyline optimal) A solution S to the GTAP (T, C, H, M ) is said to be skyline optimal iff there does not exist another solution S′ such that S′ is a proper subset of S and S′ is equally informative as S. The set of all skyline optimal solutions is denoted as Smmianx(T, C, H, M ).
Skyline optimal is a relaxed criterion. It requires subset minimality for some level of informativeness. It comprises all the subset minimal solutions – which in turn comprises all the minmax optimal solutions – and all the maxmin optimal solutions. This relationship can be easily verified.
Lemma 3. Smin(T, C, H, M ) ∪ Smmianx(T, C, H, M ) ⊆ Smmianx(T, C, H, M ).
As an example, M in Figure 2 is a skyline optimal solution for P1, P2, P3 and P4. All previous examples for subset mininal, minmax optimal and maxmin optimal solutions are also skyline optimal solutions. However, there are semantically maximal solutions that are not skyline optimal. For instance, {hinderlimb-joint ⊑˙ joint, forelimbjoint ⊑˙ joint, hand-joint ⊑˙ joint} is a semantically maximal solution for P2, but it is not skyline optimal as its subset {hinderlimb-joint ⊑˙ joint, forelimb-joint ⊑˙ joint} is equally informative. 4 4.1
A system for repairing the missing is-a structure in ontologies, takes as input the ontology T and a set of is-a relations to repair M . C is implicit and can be computed using T . Further, the system should be used by a domain expert who validates is-a relations (H)3. In general, however, when starting a debugging session, we do not know the properties of T , M and H. Further, H represents the knowledge about is-a relations from the domain expert, but is normally not available beforehand, but only through interaction of the domain expert with the debugging system. This means that even in the situations where H is a solution, this does not readily provide us a solution in practice. It also means that one cannot just take subsets of H and check whether they are solutions.
Table 1 provides us with some guidelines for the development and the use of debugging systems. First, it is clear that we prefer an all-knowing expert. The second best case for obtaining correct solutions is the partial-correct expert. As discussed in Section 2, this could be approximated by using multiple domain experts and a skeptical approach.
If there are wrong is-a relations in M , there will be no solution or solutions that are not correct. The repaired ontology will contain incorrect is-a relations. Therefore, the expert should validate M at the beginning of the debugging session. Those is-a relations which are identified to be incorrect should be removed from M .4 Another advantage of the validation is that, after validation we have that Mvalidated ⊆ H.
Further, as we do not know whether T is correct according to the domain or not, it should be checked whether T ∪ Mvalidated is consistent. If not, then there are no solutions. Otherwise, we know that Mvalidated is a solution. When we remove the redundancy from Mvalidated, then we also have a subset minimal solution. This solution could then be used as a basis for finding more informative solutions. The difficulty is in finding subsets S of H (which is not available) such that T ∪ S is consistent. 4.2
The system in [
Although the system allows to switch between the different phases, in all our
experiments we started with validating M , which is as suggested by our analysis in Section
4.1. If M contained wrong is-a relations, we used semantic debugging techniques to
repair these. This allowed us to remove incorrect is-a relations in T . When all the wrong
is-a relations are repaired and removed from M , we obtain a new Mvalidated. If the
domain expert validated M in a correct way, we are in a situation in the upper part of
Table 1. The is-a relations in Mvalidated are then repaired. When they are repaired using
3 If there would be no expert, as shown in Table 1, in the best case M could be a correct solution,
but there is no guarantee for solutions. We do not discuss this case further in this section.
4 Depending on the detection method to generate M , the wrong is-a relations in M may lead to
other debugging opportunities for semantic defects (e.g., [
Initially, Mvalidated is added to the ontology. This means that we start with a least
informative solution. When removing redundancy from Mvalidated, it is also a subset
minimal solution. Then, the system tries to generate more informative solutions. For
this, the missing is-a relations are repaired one at the time. For each missing is-a relation
mi a set of is-a relations Ri is computed that guarantees that T ∪ {ri} |= mi for each
ri ∈ Ri. Thus, for each missing is-a relation, at most one is-a relation is added to
the ontology. By removing redundancy subset minimal solutions can be guaranteed.
Further, for each missing is-a relation on its own semantically maximal solutions are
generated with the extra conditions that only one is-a relation is used for repairing and
no unnecessary equivalences (≪SH in [
One immediate consequence of our analysis is that we should allow a domain expert to choose several elements of each Ri. This is an easy extension to the system that would provide more informative solutions. Another consequence is that it would be advantageous to allow a domain expert to deal with a previously repaired is-a relation again, when new knowlegde was added to the ontology. New more informative solutions may be found. Further, there should be a way for domain experts to add new is-a relations that do not occur within the repairing process.
An interesting observation during the debugging described in [
Repairing missing is-a relations. There is not much work on the repairing of missing
is-a structure. In [
TBox abduction. Except for [
Related topics. There is work that addresses related topics but not directly the
problem that is addressed in this paper. Regarding detecting missing is-a relations there is
much work on finding relationships between terms in the ontology learning area [
In this paper we formalized repairing missing is-a structure in ontologies as an abduction problem. We defined properties for the ontology, the set of is-a relations to repair and the domain expert, as well as preference criteria on solutions and discussed the influences of these properties and criteria on the existence of solutions for the abductive problem. We also discussed the consequences of our analyses for the development and use of debugging systems. One direction for future work is to analyze the complexity of the decision problems for different knowledge representation languages. Further, we want to investigate in algorithms that satisfy the preference criteria for different languages and that can be used in practice in a debugging system.