Axiom weakening is a technique that allows for a fine-grained repair of inconsistent ontologies. Its main advantage is that it repairs ontologies by making axioms less restrictive rather than by deleting them, employing refinement operators. In this paper, we build on previously introduced axiom weakening for ℒ, and show how it can be extended to deal with ℛℐ, the expressive and decidable description logic underlying OWL 2 DL. The main problem here is to ensure that the regularity conditions of ℛℐ are preserved in the weakening process, as not every weaker axiom can be inserted into an ontology without compromising regularity. We present a basic regularity-preserving weakening approach for ℛℐ, describe briefly a prototype implementation realising it as well as an accompanying Protégé plugin, and perform and discuss basic evaluations of the approach.
Many approaches to repairing inconsistent ontologies amount to identifying problematic axioms
and then removing them (e.g., [
In this paper, we extend the previous work on axiom weakening in DLs by extending the
underlying basic principles to the logic ℛℐ, including also the weakening of RIAs. We
discuss a number of scenarios where weakening can impact regularity of ℛℐ RBoxes,
and provide a framework where this is avoided. Additionally, by implementing the proposed
refinement and weakening operators we are able to perform experimental evaluation, also on
ontologies using the more expressive features of ℛℐ. The results reafirm the results of
[
We first give a brief description of the DL ℛℐ; for full details, see [
, ::= | | − , ::= ⊥ | ⊤ | | ¬ | ⊓ | ⊔ | ∀. | ∃. |
≥ . |≤ . | ∃.Self | {} , where ∈ is a concept name, ∈ is a role name, ∈ is an individual name and ∈ N0 is a non-negative integer. is the universal role. is a simple role in the RBox ℛ (see below). In the following, ℒ( , , ) and ℒ() = ∪ { } ∪ {− | ∈ } denote, respectively, the set of concepts and roles that can be built over , , and in ℛℐ.
We next define the notions of TBox, ABox, and (regular) RBox, of complex role inclusions, and of (non-)simple roles: A TBox is a finite set of concept inclusions (GCIs) of the form ⊑ where and are concepts. The TBox is used to store terminological knowledge concerning the relationship between concepts. An ABox is a finite set of statements of the form (), (, ), ¬(, ), = , and ̸= , where is a concept, is a role and and are individual names. The ABox expresses knowledge regarding individuals in the domain. An RBox ℛ is a finite set of role inclusions (RIAs) of the form 1 ∘ · · · ∘ ⊑ , and disjoint role axioms disjoint (1, 2) where , 1, . . . , , 1, and 2 are roles. 1 and 2 are simple (defined next) in the RBox ℛ. The special case of = 1 is a simple role inclusion, while we call the cases where > 1 complex role inclusions. The RBox represents knowledge about the relationships between roles.
The set of non-simple roles in ℛ is the smallest set such that: is non-simple; any role that appears as the super role of a complex RIA 1 ∘ · · · ∘ ⊑ where > 1 is non-simple; any role that appears on the right-hand side of a simple RIA ⊑ where is non-simple, is also non-simple; and a role is non-simple if and only if − is non-simple. All other roles are simple.
For convenience, let us define the function inv () such that inv () = − and inv (− ) = for all role names ∈ . An RBox ℛ is regular if there exists a preorder ⪯ , i.e., a transitive and reflexive relation over the set of roles appearing in ℛ such that, ⪯ ⇐⇒ inv () ⪯ , and all RIAs in ℛ are of the forms: inv () ⊑ , ∘ ⊑ , ⊑ , ∘ 1 ∘ · · · ∘ ⊑ , 1 ∘ · · · ∘ ∘ ⊑ , or 1 ∘ · · · ∘ ⊑ , where > 1 and , , 1, · · · , are roles such that ⪯ , ⪯ , and ̸⪯ for = 1, . . . , . This regularity restriction has been chosen to align with the implementation of the OWL 2 DL [13] profile checker in the OWL API [14]. Definition 1. A ℛℐ ontology = ∪ ∪ ℛ consists of a TBox , an ABox , and a RBox ℛ in the language of ℛℐ, and where the RBox ℛ is regular.
The semantics of ℛℐ is defined using interpretations = ⟨∆ , · ⟩, where ∆ is a
nonempty domain and · is a function associating to each individual name an element of the
domain ∈ ∆ , to each concept a subset of the domain ⊆ ∆ , and to each role a
binary relation on the domain ⊆ ∆ × ∆ ; see [
Given two concepts and we say that is subsumed by (or subsumes ) with respect to the ontology , written ⊑ , if ⊆ in every model of . Further, is strictly subsumed by , written ⊏ , if ⊑ but not ⊑ . Analogously, given two roles and , is subsumed by with respect to ( ⊑ ) if ⊑ in all models of . Again, ⊏ holds if ⊑ but not ⊑ .
The case of ℒ. Axiom weakening, as discussed in [
Once a reference ontology ref has been chosen, and as long as is inconsistent, we select a “bad axiom” and replace it with a random weakening of it with respect to ref. We can randomly sample a number of (or all the) minimally inconsistent subsets of axioms 1, 2, . . . ⊆ and return one axiom in ∪ from the ones occurring the most often. Weakening of GCIs is performed by either using the specialization operator to refine the left-hand side or the generalization operator for the right-hand side. For class assertions, the concept is refined using the generalization operator.
The case of ℛℐ. The main dificulties that arise when weakening axioms in ℛℐ ontologies, and especially when weakening RIAs, are related to ensuring that the constraints on the use of non-simple roles and the regularity of the RBox as a whole are maintained. Not every weaker axiom can be inserted into a valid ℛℐ ontology without causing a violation of these restrictions, as shown in the next example.
Example 1. Take the ontology = { ∘ ∘ ⊑ , ⊑ , ⊤ ⊑ ∀.⊥, ∃.Self ⊑ ⊤}. Since is empty in every model of this ontology, the axiom ⊑ could be weakened to ⊑ if we ignore the additional constraints. This would result in an ontology where is non-simple, which is not allowed since is used as part of a self constraint. Additionally, using this weakening would also cause a non-regular RBox, because for any preorder ⪯ , ̸⪯ must hold for the complex RIA and ⪯ must hold for the new axiom. Yet, this is a contradiction.
To prevent these kinds of issues, we restrict how concepts are refined and RIAs weakened.
In [
Firstly, the covers and refinement operators for roles operate only on roles that are simple.
A similar restriction has already been applied in the refinement operator suggested in [
Then, to ensure further that by adding weakened axioms we do not cause a constraint violation in existing axioms and concepts, we choose the allowed weakening for RIAs such that all roles that are simple in full, are also simple after adding to it a weakening of one of its axioms. We observe that for complex RIAs 1 ∘ · · · ∘ ⊑ we should not refine the role . Since all roles returned by our refinement operator are simple in full, a replacement of with a refinement ′ would create an axiom which would make a role which was simple in full now non-simple. A similar argument can be made for refining in a simple RIA ⊑ where the role is non-simple in full. So the only way to refine the super role during the weakening of a RIA is when it is a simple RIA and additionally the sub role of the axiom is simple in full.
When it comes to refining the left-hand side of RIAs, we do not need any special restrictions. The main significant observation is that all roles that are returned by the refinement will be simple. This means that in a simple RIA ⊑ , even if is simple, replacing with another simple role will not cause to become non-simple. For a complex RIA 1 ∘ · · · ∘ ⊑ on the other hand, the role must already have been non-simple in full, and replacing any with a refinement has no efect on which roles are simple.
A more interesting question is whether such a weakening may still cause a non-regular RBox. The important insight is that simple roles are always allowed on the left-hand side of a RIA. While this is more directly evident in some alternative definitions of regularity (e.g., [ 16]) it is not so apparent from the one presented in this paper. Intuitively, the constraints given above for regularity disallow dependency cycles that contain complex RIAs. Simple roles cannot be part of such a cycle, since the cycle must contain at least one complex RIA to be a violation of the constraint, and all roles that depend in this sense on a complex RIA must be non-simple. A more formal justification for this fact is given in Lemma 4. Since all refinements of the left-hand side of RIAs are performed using simple roles, these cannot lead to a non-regular RBox. Further, refinements of the super role of RIAs are only performed on simple RIAs ⊑ where is a simple role. Since is simple in this case, all refinements of are allowed, potentially also if the refinement yielded a non-simple role.
Definition 2. Let be a ℛℐ ontology. The set of subconcepts of is given by sub() = {⊤, ⊥} ∪
⋃︁ sub() ∪ ()∈
⋃︁ (sub() ∪ sub()) , ⊑∈ where sub() is the set of subconcepts in .
We will define now the upward and downward cover sets for concepts and roles. Intuitively, for a given concept the upward cover is the set of the most specific generalizations from the (fixed) set of subconcepts or roles, while the downward cover set contains the most general specializations from the same set of subconcepts and roles. (Note that the related open search for e.g. a least common subsumer is in general a harder problem [17].) We define the upward and downward cover additionally also for non-negative integers, as they will be useful in the refinement of cardinality constraints.
Definition 3. Let full and ref ⊆ full be two ℛℐ ontologies that share the same vocabulary , , and . The upward cover and downward cover for a concept are given by
UpCoverref,full () = { ∈ sub(full) | ⊑ref and DownCoverref,full () = { ∈ sub(full) | ⊑ref and ∄′ ∈ sub(full) with ⊏ref ′ ⊏ref } , ∄′ ∈ sub(full) with ⊏ref ′ ⊏ref } .
The upward and downward covers for a role are given by The upward and downward covers for a non-negative integer are given by
UpCoverref,full () = { ∈ ℒ() | ⊑ref and ∄′ ∈ ℒ() with ⊏ref ′ ⊏ref and , ′ are simple in full} , DownCoverref,full () = { ∈ ℒ() | ⊑ref and ∄′ ∈ ℒ() with ⊏ref ′ ⊏ref and , ′ are simple in full} .
DownCoverref,full () =
UpCoverref,full () = {, + 1} , {︃{} if n = 0 {, − 1} if n > 0 .
Since they operate only over the subconcepts of full, on their own, the upward and downward covers of concepts are missing some interesting refinements.
Example 2. Let = {, , }, = {, }, and = { ⊑ , ⊑ }. sub() = {⊤, ⊥, , }. The upward cover of ⊔ is equal to UpCover,( ⊔) = {⊤}. The potentiality refinement to ⊔ will be missed even by iterated application of the upward cover because ⊔ ̸∈ sub(). Similarly, UpCover,(∀.) = {⊤}, even if ∀. and ∀. are reasonable generalizations.
To also capture these omissions, we define generalization and specialization operators that exploit the recursive structure of the concept being refined to generate more complex refinements. For convenience, we also define these operators for roles. recursively by induction on the structure of concepts as follows.
Definition 4. map every concept to a finite subset of every non-negative integer to a finite subset of ℒ( , , ), every role to a subset of ℒ(), and
N0. The abstract refinement operator is defined Let ↑ and ↓ be two functions with domain ℒ( , , ) ∪ ℒ() ∪ N0. They ↑,↓() = ↑() , ∈ ∪ {⊤, ⊥} , ↑,↓(¬) = ↑(¬) ∪ {¬′ | ′ ∈ ↓,↑()} , ↑,↓( ⊓ ) = ↑( ⊓ ) ∪ {′ ⊓ | ′ ∈ ↑,↓()} ∪ { ⊓ ′ | ′ ∈ ↑,↓()} , ↑,↓( ⊔ ) = ↑( ⊔ ) ∪ {′ ⊔ | ′ ∈ ↑,↓()} ∪ { ⊔ ′ | ′ ∈ ↑,↓()} , ↑,↓(∀.) = ↑(∀.) ∪ {∀′. | ′ ∈ ↓()} ∪ {∀.′ | ′ ∈ ↑,↓()} , ↑,↓(∃.) = ↑(∃.) ∪ {∃′. | ′ ∈ ↑()} ∪ {∃.′ | ′ ∈ ↑,↓()} ,
ℛℐ concepts: ↑,↓({}) = ↑({}) , ↑,↓(∃.Self ) = ↑(∃.Self ) ∪ {∃′.Self | ′ ∈ ↑()} , ↑,↓(≥ .) = ↑(≥ .) ∪ {≥ ′. | ′ ∈ ↑()} ↑,↓(≤ .) = ↑(≤ .) ∪ {≤ ′. | ′ ∈ ↓()} ∪ {≥ .′ | ′ ∈ ↑,↓()} ∪ {≥ ′. | ′ ∈ ↓()} , ∪ {≤ .′ | ′ ∈ ↓,↑()} ∪ {≤ ′. | ′ ∈ ↑()} , ℛℐ roles: ↑,↓() = ↑() . operator and specialization operator are, respectively, defined as From the abstract refinement operator ↑,↓, two concrete refinement operators, the generalization ref,full = UpCoverref,full ,DownCoverref,full and ref,full = DownCoverref,full ,UpCoverref,full . prove useful in the remainder of this paper.
Revisiting the case in Example 2 we observe that ,( ⊔ ) = {⊤, ⊤ ⊔ , ⊔ , ⊔ } does contain ⊔ as a possible refinement. Similarly, contains ∀.. We will show now some basic properties of ,(∀.) = {⊤, ∀., ∀., ∀.} ref,full and ref,full that will , ∈ ℒ( , , ) ∪ ℒ(): Lemma 1. For every pair of ℛℐ ontologies 1. generalisation: if ∈
specialisation: if ∈ 2. generalisation finiteness: specialisation finiteness: ref,full ( ) then ⊑ref ref,full ( ) then ⊑ref ref,full ( ) is finite ref,full ( ) is finite operators.
We define now the axiom weakening operator using these generalization and specialization ref, full and every pair of concepts or roles Definition 5. Given an axiom , the set of weakenings with respect to the reference ontology ref and full ontology full, written ref,full () is defined such that ref,full (1 ∘ · · · ∘
The axioms in the set ref,full () are indeed weaker than for every axiom , in the sense that, given the reference ontology ref, entails them and the opposite in not necessarily true. Lemma 2. For every ℛℐ axiom , if ′ ∈ ref,full (), then |=ref ′
Clearly, replacing an axiom in the full ontology with a weakening cannot reduce the number of models of the ontology. However, for the weakening to be useful in practice, we must show additionally that by adding the weakened axioms to the ontology will not violate any of the constraints that ensure the decidability of ℛℐ. To do this, we show first that all roles that are simple in full are also simple in the ontology obtained by adding the weakening of any axiom.
Lemma 3. Let be an ontology such that all simple roles of full are also simple in . For every axiom ∈ and role , if ′ ∈ ref,full () and simple in , then is simple in ∪ {′}.
Note that removal of axioms will never cause a role that was previously simple to become non-simple, so all roles simple in are also simple in ∖ {} ∪ {′}. Further, it should be noted that repeated replacement of axioms with weakened axioms keeps simple roles simple. This is an important observation, since repeated weakening is required for the proposed ontology repair algorithm.
Lemma 4. Let be an ontology such that all simple roles of full are also simple in . For every axiom ∈ , if ′ ∈ ref,full () and the RBox of is regular, then the RBox of ∪ {′} is also regular.
Like for the invariant on simple roles, also regularity is maintained by repeated replacement of axioms with weakenings. With the help of Lemma 3 and Lemma 4 we can now show that adding weakened axioms to a ℛℐ ontology will yield another valid ℛℐ ontology. Theorem 1. Given that ref and full are valid ℛℐ ontologies. For every axiom ∈ full, if ′ ∈ ref,full (), then full ∪ {′} is a valid ℛℐ ontology.
The refinement operators and axiom weakening have previously been implemented for ℒ in
[
Algorithm 1 RepairOntologyWeaken() fruefll ← ← FindMaximalConsistentSubset() while is inconsistent do bad ← FindBadAxiom() Φweaker ← ref,full (bad) weaker ← SelectWeakerAxiom(Φweaker) ← ( ∖ {bad}) ∪ {weaker} end while Return Algorithm 2 RepairOntologyRemove() while is inconsistent do bad ← FindBadAxiom() ← ∖ { bad} end while Return
The automatic repair by weakening is implemented as shown in Algorithm 1. The reference ontology is selected by choosing a maximal consistent subset of the inconsistent ontology. In our implementation used for the evaluation in this paper, the reference ontology was selected by randomly sampling a maximal consistent subset. The procedure FindBadAxiom() may be implemented in a number of ways. Here we consider an implementation that samples some (or all) of the minimal inconsistent subsets of and selects as the bad axiom the one occurring most frequently. Then, SelectWeakerAxiom(Φ weaker) has been chosen such that is selects an axiom uniformly at random from Φ weaker. Regarding termination, we showed that the corresponding algorithm for weakening for the ℒ fragment almost certainly terminates (the event in which it does not terminate has probability 0) [18], and we expect a similar result to hold for the extended weakening procedure for ℛℐ, however, we here must leave the verification of the details to future work. For all experiments presented in this paper, the FaCT++ reasoner [19] was used to compute all entailment and consistency checks.
To experimentally evaluate the proposed axiom weakening operator in the context of its use
in automatic repair of ontologies, we need some way to compare the quality of repair. As has
already been discussed in [
The inferred class hierarchy of an ontology is given by
Inf() = { ⊑ | , ∈ and |= ⊑ } .
The inferable information content of an ontology 1 with respect to another ontology 2 is given by
IIC(1, 2) =
card(Inf(1) ∖ Inf(2)) card(Inf(1) ∖ Inf(2)) + card(Inf(2) ∖ Inf(1)) where card( ) is the cardinality of the set .
For the experimental evaluation we have selected ontologies of varying size and expressivity from BioPortal3 [20]. Additionally, the pizza ontology4 was included in the testing. Some characteristics of the used ontologies are shown in Table 1. On average, they contain about 289 axioms, 73 concept names, 29 role names, and 168 subconcepts.
Since the ontologies use OWL 2, the axioms and concepts do not map directly to ℛℐ. In order to follow the definitions laid out in this paper, the OWL ontologies axioms were 4Available from Protégé at https://protege.stanford.edu/ontologies/pizza/pizza.owl. normalized to conform with ℛℐ. During the preprocessing, we further removed axioms related to data properties and any axiom that caused any OWL 2 DL profile violation, as our weakening does not handle them.
The evaluation proceeds by first making the ontologies inconsistent. This was achieved by repeatedly adding axioms to the ontology until they became inconsistent. The newly added axioms were generated by strengthening randomly selected axioms of the original ontology. It was ensured that the added axioms on their own were not inconsistent. After making the ontology inconsistent, it was repaired once with the repair algorithm using the axiom weakening operator presented in Algorithm 1 and once using Algorithm 2. Additionally, the repair was also performed by selecting a randomly sampled maximal consistent subset. Note that Algorithm 2 is not guaranteed to produce a maximal consistent subset. This process, both making the ontology inconsistent and then repairing it, was repeated one hundred times for each ontology, and the IIC was computed between the repairs generated using the diferent approaches. The evaluation was performed using a randomly selected maximal consistent subset as the reference ontology and by sampling 16 minimal inconsistent subsets during the selection of bad axioms.
Unfortunately, even though the utilized reasoners are generally very fast to evaluate queries on the selected ontologies, they exhibit undesirable performance in some edge cases. When performance pitfalls are encountered, they make the computations required for weakening unreasonably slow. For this reason a timeout of 5 minutes was placed on the repairs execution and the outputs of these runs were discarded and replaced by new runs. The results of these experiments are listed in Table 2 and shown in Figure 1 and Figure 2.
The results of the evaluation suggest that the repair by weakening is on average about as good
or better than the repair by removal of axioms. While this supports the conclusion in [
We have proposed refinement operators and an axiom weakening operator for all aspects of ℛℐ and shown that for repairs of inconsistent ontologies weakening can, in some cases, significantly outperform removal. Further additions to the refinement operators may be studied, e.g., using non-simple roles in the upward and downward covers in certain contexts. Relaxing the allowed weakening for RIAs may also be considered, and to cover also extensions to regularity conditions such as those studied in [21]. We have also seen that the repair algorithm likely needs better heuristics to steer the selection of bad and weakened axioms in order to result in better repairs. Future work could further focus on finding more robust measures for comparing the quality of repairs. [12] F. Baader, I. Horrocks, C. Lutz, U. Sattler, An Introduction to Description Logic, Cambridge
University Press, 2017. [13] OWL 2 Web Ontology Language. Structural Specicfiation and Functional-Style Syntax (Second Edition) (2012). URL: http://www.w3.org/TR/owl2-syntax/. [14] M. Horridge, S. Bechhofer, The OWL API: A Java API for OWL Ontologies, Semantic Web 2 (2011) 11–21. [15] D. Lembo, M. Lenzerini, R. Rosati, M. Ruzzi, D. F. Savo, Inconsistency-tolerant semantics for description logics, in: P. Hitzler, T. Lukasiewicz (Eds.), Web Reasoning and Rule Systems - Fourth International Conference, RR 2010, Bressanone/Brixen, Italy, September 22-24, 2010. Proceedings, volume 6333 of Lecture Notes in Computer Science, Springer, 2010, pp. 103–117. [16] S. Rudolph, Foundations of description logics, Reasoning Web. Semantic Technologies for the Web of Data: 7th International Summer School 2011, Galway, Ireland, August 23-27, 2011, Tutorial Lectures 7 (2011) 76–136. [17] F. Baader, Least common subsumers and most specific concepts in a description logic with existential restrictions and terminological cycles, in: G. Gottlob, T. Walsh (Eds.), IJCAI-03, Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, Acapulco, Mexico, August 9-15, 2003, Morgan Kaufmann, 2003, pp. 319–324. [18] R. Confalonieri, P. Galliani, O. Kutz, D. Porello, G. Righetti, N. Troquard, Almost Certain Termination for ℒ Weakening, in: G. Marreiros, B. Martins, A. Paiva, B. Ribeiro, A. Sardinha (Eds.), Progress in Artificial Intelligence: 21st EPIA Conference on Artificial Intelligence, EPIA 2022, Lisbon, Portugal, August 31–September 2, 2022, volume 13566 of Lecture Notes in Computer Science, Springer, 2022, pp. 663–675. [19] D. Tsarkov, I. Horrocks, Fact++ description logic reasoner: System description, in: Automated Reasoning: Third International Joint Conference, IJCAR 2006, Seattle, WA, USA, August 17-20, 2006. Proceedings 3, Springer, 2006, pp. 292–297. [20] P. L. Whetzel, N. F. Noy, N. H. Shah, P. R. Alexander, C. Nyulas, T. Tudorache, M. A.
Musen, Bioportal: enhanced functionality via new web services from the national center for biomedical ontology to access and use ontologies in software applications, Nucleic acids research 39 (2011) W541–W545. [21] Y. Kazakov, An Extension of Complex Role Inclusion Axioms in the Description Logic ℛℐ, in: J. Giesl, R. Hähnle (Eds.), Automated Reasoning, 5th International Joint Conference, IJCAR 2010, Edinburgh, UK, July 16-19, 2010. Proceedings, volume 6173 of Lecture Notes in Computer Science, Springer, 2010, pp. 472–486.