Bridging Belief Change and Ontology Repair

1. Introduction

Knowledge Representation (KR) is a field of artificial intelligence that aims to represent knowledge about the world, allowing reasoners to infer more information from it (Brachman & Levesque, 2004). Knowledge is dynamic, and even a small change can significantly impact an entire knowledge base (KB) (Peppas, 2008). Belief Change explores methods to handle these changes.

In their seminal paper, Alchourrón et al. (1985), proposed a paradigm for Belief Change, where the beliefs of an agent are represented as belief sets, sets of formulas in propositional logic. This paradigm, which became known as Alchourrón, Gärdenfors, and Makinson (AGM), describes the principles that characterize the operations of expansion, revision, and contraction of belief sets. The AGM paradigm was generalized in several ways, including the use of other logics, such as description logics (DLs) (Baader et al., 2017). Hansson (1993b) proposed a generalization of belief sets known as belief bases together with a new construction of contractions based on the notions of kernels and incision functions (Hansson, 1994).

Ontology Engineering studies how to model an ontology representing a domain in terms of concepts and roles. In the construction of an ontology, the need for repair has proven to be critical to maintain consistency. Ontology Repair (Kalyanpur, 2006; Keet, 2018), then, explores different methods to repair an ontology. Classical approaches significantly impact the KB, leading to unnecessary loss of information while repairing an ontology. Baader et al. (2018) present a strategy to make repairs more gentle. Although this method proved efficient at alleviating the impact of a repair, it remained highly dependent on the syntax of the axioms. In Baader et al. (2020), a method is introduced to remove unwanted assertions by using an extension of ABoxes called quantified ABoxes (qABoxes). In Baader et al. (2021), the authors presented an approach to finding optimal repairs that focuses on assertions within the ontology while keeping the terminological part static.

Several studies have sought to map similarities between Belief Change and Ontology Repair. Following the generalizations presented in Hansson (1993a), Santos et al. (2018) examined the properties of partial meet pseudo-contractions, defining a new construction of this operation that used a different consequence relation. Matos et al. (2019) extended the work of Santos et al. (2018) to the notions of kernel contractions and related the constructions of pseudo-contraction operations to gentle repair approaches. However, their work did not yet consider constructions of optimal repairs, which were introduced only later in Baader et al. (2020), Baader et al. (2021). Baader (2023) explored how functional approaches to construct optimal repairs align with pseudo-contraction operations under certain conditions.

The aim of this work is to explore the differences between optimal repairs and the outcomes of pseudo-contraction operations, a comparison that contributes to the integration, initiated in Matos et al. (2019), of the fields of Belief Change and Ontology Repair, which address similar problems but have traditionally developed independently. In this sense, our work expands (Matos et al., 2019) by incorporating the study of optimal repair constructions into this comparison. We also introduce a method for saturating the KB, which allows us to bring the results of these two approaches closer together. Additionally, we provide a comprehensive synthesis of existing work on optimal ABox repairs, supporting future research in this field. This clarification helps to make explicit the relationship between belief change operators and ontology repair techniques.

2. Preliminaries

We first introduce the foundations of DLs, focusing on the DL E L , and then recall some important definitions considered in this paper.

2.1. Description Logic

DLs are a family of KR languages that can be used to represent knowledge of an application domain in a structured and well-understood way (Baader et al., 2017). The signature Σ of a DL denotes the space available for defining concepts and assertions. It comprises the disjoint union of sets of individual names Σ I , concept names Σ C , and role names Σ R :

Σ = Σ I ∪ ˙ Σ C ∪ ˙ Σ R

In DL, concept names are unary predicates of first-order logic and role names are binary predicates of first-order logic. Concepts are constructed from concept names using concept constructors and correspond to first-order formulas with one free variable. In contrast, roles are formulas with two free variables, built from role names, that express the relationship between individuals.

A KB is a set of axioms categorized into terminological and assertional axioms. Terminological axioms (TBox) restrict the interpretation of concepts and roles, representing the knowledge about the domain in the form of concept inclusions C ⊑ D . Assertional axioms (ABox) limit individuals’ interpretation, representing knowledge about a concrete situation. In other words, given a TBox T and an ABox A , a KB K is:

K = ( T , A )

A DL is characterized in terms of first-order interpretations. An interpretation I is a pair ⟨ Δ I , . I ⟩ where Δ I is a non-empty set representing the domain and . I is an interpretation function that maps every concept name C ∈ Σ C to a concept C I ⊆ Δ I , every role name r ∈ Σ R to a set r I ⊆ Δ I × Δ I of pairs of individuals and every individual a ∈ Σ I to an individual a I ∈ Δ I . This mapping is extended to concept descriptions according to the semantics of the constructors (for more details, please see Baader et al., 2017).

An interpretation I satisfies a concept inclusion C ⊑ D if C I ⊆ D I and I is a model of a TBox T if it satisfies all its concept inclusions. In the same way, an interpretation I is a model of an ABox A if it satisfies its assertions. Finally, it is a model of a KB K = ( T , A ) if it is a model of T and A .

A variety of axioms may be part of TBoxes, depending on the language used. We will emphasize the general concept inclusion for the terminological part and concept and role assertions for the assertional part. The syntax and semantics of these axioms are defined in Table 1.

OPEN IN VIEWER

Table 1.

Terminological and Assertional Axioms Baader et al. (2017).

Axiom	Name	Syntax	Semantics
Terminological	General concept inclusion (GCI)	C ⊑ D	C I ⊆ D I
Assertional	Concept assertion	C ( a )	a I ∈ C I
	Role assertion	r ( a , b )	⟨ a I , b I ⟩ ∈ r I

2.3. The Description Logic E L

There is a range of DLs and their extensions. They start from a basic logic and are incrementally extended with extensions to enhance expressivity. Extensions introduce new constructors for complex concepts by adding new types of formulas. Like other DLs, a KB in E L is structured using concepts, roles, and individuals, with roles defining relationships among individuals.

An E L atom is either a concept name A ∈ Σ C or an existential restriction ∃ r . C , where r is a role name and C is an E L concept description.

An E L concept description is defined inductively according to this grammar rule:

C ::= ⊤ | A | C ⊓ C | ∃ r . C

where A ranges over concept names and r ranges over role names.

An E L TBox is a finite set of E L concept inclusions C ⊑ D where C and D are E L concept descriptions. It represents subconcept–superconcept relationships between concept descriptions.

Finally, an E L ABox consists of a finite set of E L assertions. These assertions can be concept assertions C ( a ) that relate individuals to concepts or role assertions r ( a , b ) that relate individuals to others. In this context, a and b represent individuals, r stands for a role name, and C is a concept description.

From the definitions above, an E L ontology ¹ is a pair consisting of an E L ABox and an E L TBox.

2.4. Quantified ABoxes

qABoxes were first introduced in the work of Baader et al. (2020) as an extension of usual ABoxes, replacing the set of individuals Σ I with a set of objects Σ O that comprises not only individuals but also variables.

Formally, a qABox ∃ X . A is defined as a finite set X of variables and the matrix A , which is a finite set of concept assertions of the form C ( u ) , where C is a concept name, and role assertions r ( u , v ) , where u and v can be either individuals or variables.

The set of individuals in a qABox is denoted by the set of objects Σ O after removing all variables:

Σ I ( ∃ X . A ) = Σ O ( ∃ X . A ) ∖ X

Every ABox A is essentially a qABox without variables.

In the same work, the authors characterized a qABox as a first-order formula by taking the conjunction of the assertions in A and prefixing it with an existential quantifier prefix containing the variables in X . qABoxes allow the representation of assertions involving unknown or intentionally anonymized individuals. For instance, the statement “Mark knows a politician” could be represented as:

∃ { x } ⋅ { knows ( Mark , x ) , Politician ( x ) }

As a result, they brought more expressivity to the KBs, allowing the creation of assertional axioms that were not possible with conventional ABoxes.

3. Belief Change

Belief Change is a field of KR that aims to understand the dynamics of epistemic states of an agent. An epistemic state of an agent represents all of their beliefs in a given moment (Ribeiro, 2010). In other words, Belief Change seeks to comprehend the agent’s behavior when faced with changes in its beliefs (Matos, 2021; Ribeiro, 2010).

The seminal contribution to Belief Change was made by Alchourrón et al. (1985), who proposed a method to represent the agent’s epistemic state alongside a set of operations to manage the changes in its beliefs when receiving new information. The guiding principle behind this method is the principle of minimal change, which suggests that a rational agent should adjust its beliefs as little as possible in order to accommodate the new information (Peppas, 2008). Due to the authors’ names, this model became known as the AGM framework.

In the AGM model, beliefs are represented by formulas of a propositional language, while the epistemic state of an agent is represented by a logically closed set of propositions, known as belief sets (Alchourrón et al., 1985). This model defines three fundamental operations on belief sets: Expansion, contraction and revision.

An expansion operation is responsible for adding new beliefs to the belief set. For a given belief set K and a belief φ , the expansion K + φ adds φ to the initial belief set and computes the logical consequences of the resulting set:

K + φ = Cn ( K ∪ { φ } )

A contraction is responsible for removing unwanted beliefs. In simple terms, a contraction operation consists of giving up as many beliefs as needed to ensure that the new belief set no longer implies the unwanted information. Unlike expansion, contraction is not defined by a single formula but by postulates that capture the underlying intuition behind the operation (Alchourrón et al., 1985). These postulates include properties such as closure, ensuring that the result of a contraction K − φ remains a belief set; inclusion, stating that no new beliefs are introduced into the set; and success, guaranteeing the unwanted belief is always removed.

Finally, a revision operation comprises of adding new beliefs to the set of beliefs while ensuring that the final belief set remains consistent. Revision is equivalent to expansion if adding a belief does not introduce inconsistencies. However, if the expansion results in an inconsistency, other beliefs of the initial belief set may need to be removed to achieve consistency. Like a contraction, the revision operation K * φ is characterized by a set of basic postulates including closure, just like in contraction; success, indicating that the resulting belief set contains the desired belief; inclusion, ensuring that no new belief besides the revised belief will be added; and preservation, that consists of preserving as many beliefs as possible.

3.1. Partial Meet Contraction

The postulates do not determine a unique contraction or revision operation for a belief set but rather characterize such operations. In the work of Alchourrón et al. (1985), the authors introduce a construction for contraction functions based on the idea of selecting maximal subsets that do not entail the belief being contracted. This operation is known as partial meet contraction.

In partial meet contraction, the remainders of a belief set K with respect to φ , denoted by rem ( K , φ ) are a family of all maximal subsets of K that do not imply φ (Alchourrón & Makinson, 1981). A selection function γ determines which of these remainders are chosen in a way that they do not entail the contracted belief. The partial meet contraction is then defined as the intersection of the selected remainders:

K − γ φ = ⋂ γ ( rem ( K , φ ) )

This construction satisfies the six basic postulates of contraction in the AGM model, while aiming to minimize the loss of information from the belief set during the contraction. The limiting case, when for all beliefs φ , the selection function γ always picks up only one element of its argument, is called maxichoice contraction operation (Alchourrón et al., 1985).

3.2. Belief Bases

The AGM paradigm treated all beliefs in a belief set equally, making no distinction between basic beliefs and those inferred from the basic ones. Hansson (1991) proposed a significant generalization by introducing belief bases. A belief base is a set of beliefs that is not closed under logical consequence. Its elements represent beliefs held independently of any other belief or set of beliefs (Hansson, 1991). This way, models utilizing belief bases enhance expressiveness compared to the belief set presented in Alchourrón et al. (1985).

Hansson further generalized partial meet contraction to apply to belief bases. It is important to note that while partial meet contraction relies on selecting maximal subsets that do not imply the contracted belief, it is not sufficient for these subsets that they do not contain the contracted sentence. Hansson then characterizes partial meet base contraction in terms of the following postulates:

 

Success: Unless the belief is a tautology, the contracted belief will not be part of the set of consequences derived from the contracted belief base

 

Inclusion: New beliefs will never be added to the belief base during the contraction

 

Relevance: Blocks the exclusion of elements for which there is no good reason to exclude

 

Uniformity: Ensures that the result of contracting a sentence from a belief base only depends on which subsets of the belief base imply the contracted sentence.

3.2.1. Kernel Contraction

Hansson (1994) introduced another construction for obtaining contraction operations, based on the notions of kernels and incision functions. Unlike partial meet contractions that aim for maximal subsets that do not imply the undesired belief, a kernel contraction targets the minimal belief sets that do imply the unwanted sentence.

As explained in (Wassermann, 2000), the idea behind kernel contraction is that by removing at least one element from each minimal subset that implies the unwanted belief, we obtain a belief base that no longer implies this belief. To perform these removals, we use an incision function.

In Kernel contraction, a kernel set of a belief base B with respect to φ , denoted by k e r ( B , φ ) , is the family of all minimal subsets of B that entails φ . An incision function is a function that selects at least one element from each kernel for removal. A kernel contraction then, is defined as:

B − σ φ = B ∖ σ ( ker ( B , φ ) )

Broadly speaking, kernel contractions are more general than partial meet contractions. However, if the kernel contraction is induced by a minimal incision function, then it becomes a maxichoice contraction.

3.3. Pseudo-contraction

A downside of the contraction notions introduced in the AGM framework (Alchourrón et al., 1985), when applied to belief bases, is their syntax dependency, in the sense that they can only use sentences explicitly present in the belief base. For example, consider a belief base B = { p ∧ q } where we want to get rid of the unwanted consequence q . The empty belief base would result from this contraction. However, by transforming B into the equivalent belief base B ′ = { p , q } , the contraction would keep the belief p . This issue arises from the inclusion postulate, which forbids the addition of beliefs during a contraction.

In Hansson (1989), a weakening of the inclusion postulate was introduced, termed logical inclusion. In logical inclusion, the consequences of a contraction are contained in the consequences of the belief base:

Cn ( B − φ ) ⊆ Cn ( B )

By replacing the inclusion postulate, Hansson allowed beliefs in the contraction’s consequences to be added to the resulting belief base during the contraction. Some years later, Hansson proposed to call an operation that satisfies success and logical inclusion a pseudo-contraction (Hansson, 1993a).

3.3.1. C n * Partial Meet Pseudo-contraction

Following the results from Hansson (1993a), Santos proposed a pseudo-contraction operation that depended on the formulas allowed to be added when contracting the belief base called Cn * partial meet pseudo-contraction (Santos, 2016; Santos et al., 2018). Let B be a belief base, Cn * a consequence relation and γ a selection function. The Cn* partial meet pseudo-contraction is an operator such that for all φ :

B − γ * φ = ⋂ γ ( rem ( Cn * ( B ) , φ ) )

As detailed in Santos et al. (2018), Cn * is a consequence relation that, in general, produces fewer consequences than the classical Cn. Let B ⊆ Cn * ( B ) ⊆ Cn ( B ) , if Cn * ( B ) = B , a Cn * pseudo-contraction becomes partial meet contraction for belief bases, and if Cn * ( B ) = Cn ( B ) , it becomes partial meet contraction for belief sets. This operator generalizes those approaches, allowing us to get results in the whole spectrum if Cn * ranges between B and Cn ( B ) , corresponding to the thresholds for satisfaction of inclusion and logical inclusion, respectively.

3.3.2. C n * Kernel Pseudo-contraction

Analogously to Cn * partial meet pseudo-contraction, Matos introduced Cn * kernel pseudo-contraction by using kernels and incision functions for Cn * ( B ) rather than B (Matos, 2021). Let B be a belief base, Cn * a consequence relation and σ an incision function. The Cn* kernel pseudo-contraction of B by a sentence φ , is such that, for all sentences φ :

B − σ * φ = Cn * ( B ) ∖ σ ( ker ( Cn * ( B ) , φ ) )

3.3.3. Two-place Pseudo-contraction

Matos presented another kind of Cn * pseudo-contraction using consequence operators that also considers the input formula (Matos, 2021). Applying a two-place consequence operator to partial meet pseudo-contraction instead of using the classical one-place operator, the Two-place C n * partial meet pseudo-contraction is defined as:

B − γ * φ = ⋂ γ ( rem ( Cn * ( B , φ ) , φ ) )

where B be a belief base, Cn * a two-place consequence operator and γ a selection function. In case the value returned by Cn * does not depend on φ , then Cn * ( B ) = Cn * ( B , φ ) and Cn * is called a one-place consequence operator.

Two-place C n * kernel pseudo-contraction are defined in Matos (2021) analogously by using kernels and incision functions for Cn * ( B , φ ) rather than for B :

B − σ * φ = Cn * ( B , φ ) ∖ σ ( ker ( Cn * ( B , φ ) , φ ) )

As in Cn * partial meet pseudo-contraction, this operation generalizes Cn * kernel pseudo-contractions.

4. Ontology Repair

In ontology engineering, we might need to repair a KB either when modeling errors are detected or when it is necessary to remove an undesired formula (Baader, 2023). The central question in ontology repair studies is then how to repair a KB, removing the unwanted information while ensuring that:

(a)

no new information is introduced;

(b)

the ontology remains as close as possible to the original.

4.1. Classical Approaches

Classical repair approaches define a repair as a maximal subset of the KB that does not imply unwanted sentences (Baader et al., 2021). These approaches ensure that no new axioms are added during the repair process, maintaining the ontology as close as possible to its original by adhering to the maximality condition (Baader, 2023). Classical methods are based on axiom pinpointing (Schlobach & Cornet, 2003), which provides methods to understand why a particular consequence holds by computing its justifications. A justification is defined as a minimal subset of the KB that entails the consequence in question.

From its justifications, classical repairs are computed ensuring that no justification holds in the computed subsets of the KB. Formally, a repair of a KB K with respect to the sentence α is a set K ′ such that Cn ( K ′ ) ⊆ Cn ( K ) and K ′ does not entail α , that is, α ∉ Cn ( K ′ ) . An optimal repair is a repair such that there is no other repair which contains it.

A classical repair of a KB K with respect to α is repair K ′ such that K ′ ⊂ K . An optimal classical repair is a classical repair such that there is no other classical repair which contains it.

While these classical approaches preserve as many sentences as possible, the obtained results may not preserve a maximal amount of consequences and are syntax-dependent. For instance, suppose we have the sentence ( A ⊓ B ⊓ C ) ( a ) , and we want to remove A ( a ) from its consequences. In this case, the repaired ontology would be the empty set, resulting in the loss of ( B ⊓ C ) ( a ) . To overcome this problem, gentle repair approaches have been introduced in Baader et al. (2018). Instead of completely removing certain axioms, these approaches replace them with weaker ones.

However, as shown in Baader et al. (2018), this approach still need not produce optimal repairs, that is, ones that preserve a maximal set of consequences, and they are also dependent on the syntactic form of the axioms.

4.2. Functional Approaches

Functional approaches to produce ontology repairs were developed to create a method of repair where the syntactic structure of the axioms in the ontology was supposed to be irrelevant. These approaches shift the focus from the axioms to their consequences, interpreting the repair conditions as:

(a)

no new consequences are introduced;

(b)

a maximal set of consequences is preserved rather than a maximal set of axioms.

In Baader et al. (2021), the authors proposed methods to compute optimal repairs, considering the use of qABoxes in scenarios where the initial qABox might contain errors while assuming the TBox to be static.

In these terms, an optimal repair is defined as an ontology that does not have unwanted consequences, is entailed by the original ontology, and preserves the maximal amount of implications in the sense that there is no repair that strictly entails it (Baader et al. (2021)). In the same work, the authors also demonstrated that, in general, optimal repairs need not exist, even if there are repairs. Moreover, unlike classical repair approaches, even if optimal repairs exist, they need not cover all repairs in the sense that every repair is contained in an optimal repair.

4.2.1. Canonical Repairs

The intuition behind canonical repairs originates from generating variations of the initial qABox while maintaining entailment relationships between them, until it no longer entails any unwanted consequences (Baader et al., 2023). Although this process, known as blind search, works for computing optimal repairs, it is very inefficient.

Canonical repair arises then, as a construction where copies of individuals and their assertions are created while removing unwanted consequences. Each copy replicates the original individual, preserving information that would otherwise be lost when removing certain consequences. For example, given the assertions:

A := { Journalist( Francesca) , Italian(Francesca) }

If we aim to remove the assertion that Francesca is a journalist, we would also lose the consequence that there is an Italian who is a journalist. However, by creating a copy of Francesca as a free variable x , we would be able to create a qABox that can retain this knowledge:

∃ X ⋅ A ′ := ∃ { x } ⋅ { Italian (Francesca) , Journalist ( x ) , Italian ( x ) }

The unwanted sentence Journalist(Francesca) was removed, but the consequence “There is an Italian who is a journalist” was retained. Inevitably, creating copies extends the initial ABox to a qABox, where the added variables serve as copies of the original objects.

Canonical repair is restricted to E L ontologies where the TBox is assumed to be correct and thus will not change during the process. However, the construction still considers the existence of terminological axioms to ensure that the removed consequences are not reintroduced by them (Baader et al., 2021).

Rather than comparing ontologies based on their models, the process of computing optimal repairs described in Baader et al. (2021), Baader (2023), suggests comparing them based on the answers to the queries they entail. For a given query language QL, we say that a qABox ∃ X . A QL-entails a qABox ∃ Y . B ( ∃ X . A ⊨ Q L ∃ Y . B ) if the queries entailed by ∃ Y . B are entailed by ∃ X . A . We say that they are QL-equivalent, if they entail each other ( ∃ X . A ≡ Q L ∃ Y . B ) (Baader et al., 2021). For E L ontologies, (Baader et al., 2021) consider two types of queries:

 

Instance queries: E L concept descriptions viewed as first-order formulae with one free variable.

 

Conjunctive queries: Quantified ABoxes with their individuals viewed as free variables. Due to this close connection, it is an easy consequence that the classical entailment relation between qABoxes coincides with CQ-entailment.

In what follows, the construction of repairs is explained using the notion of repair requests. A repair request is defined as a finite set of E L concept assertions representing the unwanted consequences (Baader et al., 2021), that is, what must be removed from the base.

The process for computing a canonical repair ∃ Y . B of the ABox A with respect to the TBox T and the repair request R begins with a saturation step, which simplifies the assertions bringing the knowledge of the TBox into the ABox. This is followed by a process of copying, where assertions are duplicated using free variables. Next, the repairing step determines which assertions will be removed and which will be preserved. Finally, the process concludes with a selection step, where one of the copies will represent the initial individual.

The remainder of this section describes each of these steps in detail.

 

Saturation: The saturation process extends the given ABox with the consequences entailed by the TBox (Baader et al., 2021). Intuitively, it copies all the knowledge into the ABox as atomic parts, so that only the unwanted parts need to be removed. The rules applied during this step depend on the query language used during the repair.

For CQs, the CQ-saturation rules are defined as follows:

 

⊓ -rule: If ( C 1 ⊓ ⋯ ⊓ C n ) ( t ) ∈ A , then replace this assertion with C 1 ( t ) , … , C n ( t ) .

 

∃ -rule: If ( ∃ r . C ) ( t ) ∈ A , then replace this assertion with the pair of assertions r ( t , x ) and C ( x ) , and add x to X , where x is a fresh variable not occurring in A or X .

 

⊑ -rule: If C ⊑ D ∈ T and A ⊨ C ( t ) , and A ⊭ D ( t ) , then add D ( t ) to A .

While the third rule adds new concept assertions implied by the ABox and the TBox, the other two rules break down complex concept assertions into atomic parts. The ⊓ -rule has the highest priority, followed by the ∃ -rule and the ⊑ -rule.

In Baader et al. (2021), the authors demonstrated that applying these rules may not always terminate, but for cycle-restricted TBoxes, CQ-saturation always terminates.

For instance queries, the IQ-saturation rules are slightly different:

 

⊓ -rule: If ( C 1 ⊓ ⋯ ⊓ C n ) ( t ) ∈ A , then replace this assertion with C 1 ( t ) , … , C n ( t ) .

 

∃ -rule: If ( ∃ r . C ) ( t ) ∈ A , then replace this assertion with the pair of assertions r ( t , x C ) and C ( x C ) , and add x C to X if it is not already there.

 

⊑ -rule: If C ⊑ D ∈ T and A ⊨ C ( t ) , and A ⊭ D ( t ) , then add D ( t ) to A .

As shown in Baader et al. (2021), the IQ-saturation always terminates without imposing any restriction on the TBox. The key difference lies in the fact that IQ-saturation rules are more parsimonious when introducing new objects, ensuring that added variables are linked to existing concepts. For instance, when applying the ∃ -rule to an assertion ∃ r . C ( t ) , the IQ-saturation adds a new fresh variable x C only if it is not contained in X ; otherwise, it reuses the existing in the new assertion. This restriction ensures that the saturation will not be trapped in a cycle, thereby ensuring it will terminate.

Regardless of the chosen query language, saturation is the process of exhaustively applying the respective rules to break down complex concepts and add consequences of the TBox into the ABox. This process results in a qABox formed by atomic concepts, making it suitable for repair since the TBox information is included within the resulting qABox.

 

Copying: The process of copying generates copies of the objects in the saturated ABox. Each object u in the input qABox ∃ X . A receives copies of the form ⟨ u , M ⟩ where M specifies which assertions C ( u ) entailed by A must not hold for this copy (Baader et al., 2023). This set is called repair type. A repair type M for u is a subset of the set of atoms occurring in either the TBox T or in the repair request R that satisfies the following properties:

A ⊨ C ( u ) for each atom C ∈ M .

C ⋢ ∅ D for each pair of distinct atoms C , D in M .

If C is an atom in M and E ⊑ F is an axiom in T with A ⊨ E ( u ) and F ⊑ ∅ C , then there is an atom D in M such that E ⊑ ∅ D .

The first condition ensures that u is an instance of the atoms in M . The second condition avoids duplicates, while the third ensures that the TBox will not reintroduce consequences removed due to M .

 

Repairing: While the copying process generates multiple copies of each object, the repairing step will choose specific assertions for each new variable to preserve. These assertions will retain particular knowledge while avoiding unwanted consequences. Using the generated copies, the matrix B of canonical repairs is defined in Baader et al. (2023) and consists of the following assertions:

A ( ⟨ u , M ⟩ ) if A ( u ) ∈ A and A ∉ M .

r ( ⟨ u , M ⟩ , ⟨ v , N ⟩ ) if r ( u , v ) ∈ A and for each ∃ r . C ∈ M with A ⊨ C ( v ) , there is an atom D ∈ N such that C ⊑ ∅ D .

These conditions ensure that the assertions added to B are not related to the atoms in their repair type. The intuition is that an object cannot be an instance of an unwanted consequence. Since the repair type is formed by atoms of unwanted consequences, by removing these assertions, the canonical repair ensures that the unwanted consequence no longer follows.

 

Selection: The result of the repairing step is a qABox formed by copies of the original objects. The selection step chooses, for each individual a in the original qABox, one of its copies as representative of a in B , in a way that the obtained qABox is really a repair (Baader et al., 2023). This choice is realized by fixing a repair seed. A repair seed S maps each individual a to a repair type S a for a such that the following condition is satisfied:

If C ( a ) ∈ R and A ⊨ C ( a ) , then there is an atom D in S a such that C ⊑ ∅ D .

Given the repair seed S , the canonical repair is the qABox ∃ Y . B where the copies ⟨ a , S a ⟩ are replaced by their respective individual a . The other objects are variables in Y . This construction works both in the CQ and the IQ case, and yields a set of repairs that covers all repairs (Baader et al., 2023).

4.2.2. Optimized Repairs

While canonical repairs compute optimal repairs, it also introduces more copies than necessary to achieve an optimal repair (Baader et al., 2021). In contrast, the optimized repair approach presented in Baader et al. (2021) constructs an optimal repair using only the essential copies, ensuring that the resulting repair is equivalent to the canonical one.

All the processes of repair, such as saturation, copying, repairing, and selection, are identical to those described in the canonical approach. The key difference in the optimized approach is the addition of the pruning step. Instead of utilizing all the generated variables in the repairing, this step filters out redundant copies by selecting those associated with minimal cover repair types.

Before explaining the process of pruning, it is first necessary to define the concept of coverage. Given two sets of concept descriptions M and N , N covers M if each concept in M is subsumed by some concept in N .

 

Pruning: Recalling the definition of canonical repairs, an assertion r ( ⟨ u , M ⟩ , ⟨ v , N ⟩ ) belongs to the resulting repair if the saturation contains r ( u , v ) and for each ∃ r . C ∈ M where A ⊨ C ( v ) , there is an atom D ∈ N such that C is subsumed by D .

In Baader et al. (2021), the authors rephrase it in terms of coverage: An assertion r ( ⟨ u , M ⟩ , ⟨ v , N ⟩ ) belongs to the resulting repair if the saturation contains r ( u , v ) and N covers Succ ( M , r , v ) , where Succ defines the set of concepts that v is an instance of, and is related to u through an existential restriction:

Succ ( M , r , v ) := { C | ∃ r . C ∈ M and A entails C ( v ) }

The rules proposed in Baader et al. (2021) for constructing optimized repairs are dependent on the chosen query language. For the IQ-case, the construction starts with Y as an empty set of variables and proceeds by exhaustively applying the following rule:

 

IQ-rule: The variable ⟨ u , P ⟩ is added to Y if: i.

⟨ t , M ⟩ is an element of Σ I ∪ Y i

ii.

The saturated ABox contains the role assertion r ( t , u )

iii.

P is a repair type for u

iv.

P is a minimal cover of Succ ( M , r , u )

v.

⟨ u , P ⟩ is not contained in Σ I ∪ Y i

For the CQ-case, Y starts as the set of variables ⟨ t , ∅ ⟩ , where t is an object occurring in the saturated ABox and proceeds by exhaustively applying the following rule:

CQ-rule: The variable ⟨ u , P ⟩ is added to Y if:

i.

⟨ t , M ⟩ and ⟨ u , N ⟩ are elements of Σ I ∪ Y i

ii.

The saturated ABox contains the role assertion r ( t , u )

iii.

The repair type N does not cover Succ ( M , r , u )

iv.

P is a repair type for u

v.

P is a minimal cover of N ∪ Succ ( M , r , u )

vi.

⟨ u , P ⟩ is not contained in Σ I ∪ Y i

The intuition behind the pruning step is to select only the variables reachable from the initial individuals that have a repair type that minimally affects the KB.

4.3. An Example of Optimal Repairs

Consider an example in which Francesca loves an individual who is both Italian and a chef. This relationship could be represented by the following KB:

O = { ∃ loves . ( Italian ⊓ Chef ) ( Francesca ) }

Now, let’s say we want to get rid of this assertion. In this case, the repair request containing the unwanted consequence is defined as:

R = { ∃ loves . ( Italian ⊓ Chef ) ( Francesca ) }

The remainder of this section illustrates each step in building a canonical repair and also an optimized repair, as described in the previous section.

Saturation:

Starting with the initial ABox A , the saturation rules are exhaustively applied as follows:

∃ -rule: ∃ X . A = ∃ { x ( I ⊓ C ) } ⋅ { loves ( Francesca , x ( I ⊓ C ) ) , ( Italian ⊓ Chef ) ( x ( I ⊓ C ) ) }

⊓ -rule: ∃ X . A = ∃ { x ( I ⊓ C ) } ⋅ { loves ( Francesca , x ( I ⊓ C ) ) , Italian ( x ( I ⊓ C ) ) , Chef ( x ( I ⊓ C ) ) }

According to the ∃ -rule from the IQ-saturation, the created variable should be named x ( I ⊓ C ) . However, since this is the only variable resulting from the saturation, we will name it x . The resulting qABox is then:

∃ X . A = ∃ { x } ⋅ { loves ( Francesca , x ) , Italian ( x ) , Chef ( x ) }

Copying:

The copying process creates copies of the objects in Σ O ( ∃ X . A ) . Each copy is associated with a repair type that specifies which atoms should be removed for this copy. In the current example, the atoms present in the sentences of the repair request R and the TBox T are:

Atoms ( R , T ) = { Italian , Chef , ∃ loves ( Italian ⊓ Chef ) }

The possible repair types are given by the power set of the existing atoms:

M 0 := { } M 1 := { Italian } M 2 := { Chef } M 3 := { ∃ loves ( Italian ⊓ Chef ) } M 4 := { Italian , Chef } M 5 := { Italian , ∃ loves ( Italian ⊓ Chef ) } M 6 := { Chef , ∃ loves ( Italian ⊓ Chef ) } M 7 := { Italian , Chef , ∃ loves ( Italian ⊓ Chef ) }

For each object in Σ O ( ∃ X . A ) , we use the definition of repair type to check whether a repair type is valid for the given object and then create the new variables:

y 0 := ⟨ Francesca , M 0 ⟩ ⟨ Francesca , M 1 ⟩ ⟨ Francesca , M 2 ⟩ y 1 := ⟨ Francesca , M 3 ⟩ ⟨ Francesca , M 4 ⟩ ⟨ Francesca , M 5 ⟩ ⟨ Francesca , M 6 ⟩ ⟨ Francesca , M 7 ⟩ y 2 := ⟨ x , M 0 ⟩ y 3 := ⟨ x , M 1 ⟩ y 4 := ⟨ x , M 2 ⟩ ⟨ x , M 3 ⟩ y 5 := ⟨ x , M 4 ⟩ ⟨ x , M 5 ⟩ ⟨ x , M 6 ⟩ ⟨ x , M 7 ⟩

By following these steps, we have computed y 0 and y 1 as copies of Francesca, and y 2 , y 3 , y 4 and y 5 as copies of x .

Selection:

Following the creation of new copies, the selection process will select, for each individual in Σ I ( ∃ X . A ) , one of its copies as representative of this individual in the repaired qABox. In this example, there exists only one possible repair seed that follows the definition:

S Francesca := { ∃ loves ( Italian ⊓ Chef ) }

Given that M 3 is defined as M 3 := { ∃ loves ( Italian ⊓ Chef ) } , the copy of Francesca selected to represent it in the repaired qABox corresponds to the one associated with M 3 :

Francesca ⟺ y 1 := ⟨ Francesca , M 3 ⟩

Repairing:

The repairing process then, will create the assertions for each copy based on the original object and the associated repair type. The generated assertions take into account the conditions described in the repairing definition:

Italian ( y 2 ) Chef ( y 2 ) Chef ( y 3 ) Italian ( y 4 ) loves ( y 0 , y 2 ) loves ( y 0 , y 3 ) loves ( y 0 , y 4 ) loves ( y 0 , y 5 ) loves ( Francesca , y 3 ) loves ( Francesca , y 4 ) loves ( Francesca , y 5 )

The canonical resulting repaired qABox is then:

∃ Y . B = ∃ { y 0 , y 2 , y 3 , y 4 , y 5 } ⋅ { Italian ( y 2 ) , Chef ( y 2 ) , Chef ( y 3 ) , Italian ( y 4 ) , loves ( y 0 , y 2 ) , loves ( y 0 , y 3 ) , loves ( y 0 , y 4 ) , loves ( y 0 , y 5 ) , loves ( Francesca , y 3 ) , loves ( Francesca , y 4 ) , loves ( Francesca , y 5 ) }

For the optimized approach, we add the pruning step prior to the repairing process:

Pruning:

The copying process created variables with valid repair types. In this step, unnecessary variables are pruned. For the IQ-repair, the construction begins with an empty set of variables and only one individual:

Y 0 = ∅

Σ I ∪ Y 0 = { Francesca }

Recall that Francesca is represented by the variable ⟨ Francesca , M 3 ⟩ . The repeated application of the IQ-rules generates the following set of variables:

Y 1 = Y 0 ∪ { y 3 } , where y 3 := ⟨ x , M 1 ⟩

Y 2 = Y 1 ∪ { y 4 } , where y 4 := ⟨ x , M 2 ⟩

Since the rule cannot be reapplied, the final set of variables is used in the repair is:

Y := { y 3 , y 4 }

Repairing:

The repairing step, then, will create the assertions for the remaining copies. The process is the same as the canonical repair but now running over the results of the pruning step:

Chef ( y 3 ) Italian ( y 4 ) loves ( y 1 , y 3 ) loves ( y 1 , y 4 )

The optimized resulting repaired qABox is then:

∃ Y . B = ∃ { y 3 , y 4 } ⋅ { Chef ( y 3 ) , Italian ( y 4 ) , loves ( Francesca , y 3 ) , loves ( Francesca , y 4 ) }

5. Optimal Repairs as Pseudo-contractions

It is intuitive to see the similarities between contractions and ontology repair approaches. Previous studies, such as Matos et al. (2019), have identified equivalences between pseudo-contraction operations and ontology repair methods. Baader (2023) explored the connection between optimal repairs and pseudo-contractions. By defining a consequence operator, he showed that, under certain conditions, optimal repairs could be obtained from pseudo-contractions.

Given the KB K and the unwanted consequence φ , he defined as a consequence operator Cn * , the following two-place function:

Cn * ( K , φ ) := K ∪ ⋃ O rep ( K , φ )

In the same work, it is proved that this function can effectively be computed since, as presented in Baader et al. (2022), optimal repairs can be computed by first computing the optimal qABox repairs, which results in a finite and computable set. Building on this, Baader proved that when the ABox is restricted to being acyclic and the TBox to being cycle-restricted, the existence of an optimal repair implies that there exists a remainder of Cn * ( K , φ ) that is equivalent to it (Baader, 2023; Baader et al., 2022).

As a consequence, it was shown that a maxichoice Cn * partial meet pseudo-contractions always produce optimal repairs in case O rep ( K , φ ) covers all repairs (Baader, 2023). Additionally, since every kernel contraction induced by a minimal incision function can be obtained as a maxichoice partial meet contraction, the results also hold for Cn * kernel pseudo-contractions.

From this point forward, we focus on the results of contractions and repairs, aiming to better understand their differences. We begin by comparing their results.

5.1. Comparing Optimal Repairs and Pseudo-contractions

Any of the approaches presented in Baader et al. (2021) to find an optimal ontology repair, whether through canonical or optimized repairs, use qABoxes to increase the number of consequences preserved during the repair. However, as shown in Baader et al. (2022), Baader (2023), optimal ABox repairs are limited to the non-existence of cycles in the base. Consider, as an example, the following ontology and repair request:

(Ontology)

O = { ∃ r . B ⊑ A , A ⊑ ∃ s . A , ∃ s . A ⊑ A , r ( a , b ) , B ( b ) }

(Repair Request)

R = { A ( a ) }

In this example, the GCI ∃ s . A ⊑ A together with A ⊑ ∃ s . A characterizes a cycle, yielding a cyclic qABox as a repair:

∃ Y . B = ∃ { x , y } ⋅ { r ( a , x ) , B ( b ) , s ( a , y ) , s ( y , y ) }

The resulting qABox has no equivalent optimal ABox repair as the cycle s ( y , y ) prevents the removal of the variable y . While the qABox enhanced the expressivity, it took the ontology out of the original language without giving the possibility of returning.

The main question is that KBs represent a potentially infinite set of consequences. Once we look at this set and try to find a maximal subset that does not imply a particular formula, a finite representation of this maximal subset may not exist.

In contrast, the same KB and repair request in a partial meet pseudo-contraction operation that uses the consequence operator of ELK ² (Kazakov et al., 2012), Cn ELK , would result in the following set of remainders:

r 1 = { A ⊑ ∃ s . A , ∃ s . A ⊑ A , ∃ r . B ⊑ A , r ( a , b ) }

r 2 = { A ⊑ ∃ s . A , ∃ s . A ⊑ A , ∃ r . B ⊑ A , B ( b ) }

r 3 = { A ⊑ ∃ s . A , ∃ s . A ⊑ A , B ( b ) , r ( a , b ) }

This difference can be explained by the fact that, in Belief Revision, contractions consider the entire KB as refutable, whereas constructing optimal repairs in the presented approaches assumes that terminological axioms cannot change.

In AGM theory (Alchourrón et al., 1985), beliefs are represented by belief sets, which are closed under logical consequence. Thus, a remainder is a maximal subset of the belief set that does not imply a specific formula, but, at the same time, because the sets are closed, it is also a maximal set with respect to preserving consequences, such as in optimal repairs.

In belief bases, remainders are maximal subsets of the base, that is, of the finite representation, regardless of how they behave concerning the consequences. By using the classical consequence operator, a contraction could keep the maximum number of consequences since it includes all the existing consequences. However, it turns out that this is not a computable set. Reasoners only compute a closure of the consequences based on the tasks they can perform, such as classification, instance checking, or satisfiability checking. Otherwise, the number of inferences could become infinite, and the reasoner would never stop.

The limitation of reasoners in computing consequences also produces differences when comparing the results of pseudo-contractions and optimal repairs, even though both aim to find the maximal set of consequences. For instance, consider a scenario with an empty TBox:

 

(Ontology) O = { r ( a , b ) , A ( b ) , B ( b ) }

 

(Repair Request) R = { ∃ r . ( A ⊓ B ) ( a ) }

The optimal repair computed by an optimized IQ-repair construction achieves one of the following qABox:

∃ Y 1 . B 1 = ∃ { y 3 } ⋅ { r ( a , b ) , A ( b ) , r ( a , y 3 ) , B ( y 3 ) }

∃ Y 2 . B 2 = ∃ { y 4 } ⋅ { r ( a , b ) , B ( b ) , r ( a , y 4 ) , B ( y 4 ) }

These results are dependent on the chosen repair seed and can be expressed by equivalent ABoxes:

C 1 = { r ( a , b ) , A ( b ) , ∃ r . B ( a ) }

C 2 = { r ( a , b ) , B ( b ) , ∃ r . A ( a ) }

This example results in non-equivalent remainders when running the partial meet pseudo-contraction under consequences computed by the ELK reasoner:

r 1 = { r ( a , b ) , A ( b ) }

r 2 = { r ( a , b ) , B ( b ) }

r 3 = { A ( b ) , B ( b ) }

ELK did not compute any consequences for this base, which implies the lack of existential restrictions in its assertions, such as ∃ r . A ( a ) and ∃ r . B ( a ) .

Optimal repairs offer the possibility of having more consequences in an extended version of the language while restricting the existence of cycles. On the other hand, pseudo-contractions are not concerned with cycles but depend on the closure of consequences computed by the reasoner. We fall between the absence of cycles or the dependency of reasoners. Let’s explore one more example:

 

(Ontology) O = { A ⊑ B , r ( a , b ) , A ( b ) }

 

(Repair Request) R = { ∃ r . ( A ⊓ B ) ( a ) }

This example illustrates the scenario where the TBox contributes to the justification of the unwanted sentence, and therefore, it needs to be considered during the repair process. The generation of variables provides a small set of copies for a and b :

a 0 := ⟨ a , ∅ ⟩ a 1 := ⟨ a , { ∃ r . ( A ⊓ B ) } ⟩ b 0 := ⟨ b , ∅ ⟩ b 1 := ⟨ b , { A } ⟩ b 2 := ⟨ b , { A , B } ⟩

Note that only a 1 is a valid repair seed S a for a , while any of the copies of b can be used as a repair seed S b for b . It follows that, the optimized IQ-repair construction produce the following repairs depending on the chosen repair seed:

O 1 = { A ⊑ B , ∃ r . B ( a ) , A ( b ) , B ( b ) }

O 2 = { A ⊑ B , r ( a , b ) , B ( b ) }

O 3 = { A ⊑ B , r ( a , b ) , ∃ r . B ( a ) }

The first two repairs are optimal repairs for the given base and repair request. The third one is entailed by O 2 and, therefore, is not optimal.

Now, let’s compare the optimized IQ-repair construction results with the remainders obtained from a partial meet pseudo-contraction operation using the same KB and unwanted sentence. To do so, we will use the set of consequences computed by ELK:

Cn ELK ( O ) = { A ⊑ B , r ( a , b ) , A ( b ) , B ( b ) }

From the inferred base, the remainders are as follows:

r 1 = { A ⊑ B , A ( b ) , B ( b ) }

r 2 = { A ⊑ B , r ( a , b ) , B ( b ) }

r 3 = { r ( a , b ) , A ( b ) }

When comparing the remainders with the computed optimal repairs, they yield similar results. It is easy to see that r 2 is equal to O 2 . Also, note that r 1 and O 1 are almost the same, differing only in the assertion ∃ r . B ( a ) , which could not be computed due to the limitations of ELK in computing the set of consequences. Finally, the last remainder represents a contraction obtained by removing the axiom A ⊑ B from the TBox, which has no equivalent in optimal repairs, as the ontology repair constructions do not change the TBox.

The following section proposes an algorithm to extend the closure of consequences computed by the reasoner with a set of axioms entailed by the base.

5.2. An Ontology Saturator

Reasoners can only infer consequences based on their reasoning methods. To extend this set of consequences, we propose a new method to compute a specific family of consequences. Consider the following assertions:

loves ( Francesca , Gabriele )

Chef ( Gabriele )

The first assertion says that Francesca loves Gabriele, while the second says that Gabriele is a chef. Together, they imply that “Francesca loves a chef”. The following axiom can represent this:

∃ loves . Chef ( Francesca )

In other words, there exists a relationship loves between Francesca and an individual who is an instance of the concept Chef. We can also use the same construction to entail a chain of individual relations. For example, by adding the axioms:

friendOf ( Giulia , Francesca )

Economist ( Giulia )

we can entail an axiom saying that Giulia is a friend of someone who loves a chef, that is:

∃ friendOf . ∃ loves . Chef ( Giulia )

Axioms in a KB can express the connections between individuals, and this form of axiom describes the chain of relations that connect a pair of individuals. If we imagine each individual in the base as a node and each axiom of the form r ( a , b ) as an edge ⟨ a , b ⟩ , we can then create a graph of the relations existing in the base. In our example, we would have the graph presented in Figure 1.

OPEN IN VIEWER

Figure 1.

Graph of the relations generated from the specified axioms.

By traversing the graph from a node to all reachable nodes, we can generate the existing chains of relations starting from the chosen node. Repeating this process for each node in the graph allows us to infer all the existing chains in the KB. Using the depth-first search (DFS) algorithm, Algorithms 1 and 2 describe the changes to compute the saturated KB.

OPEN IN VIEWER

Algorithm 2 starts with graph G , constructed from the given ontology. The algorithm iterates through all the axioms in the ontology in order to build the graph. For each axiom of the form r ( a , b ) , an edge ⟨ a , b ⟩ is added to the graph, where the edge stores the relationship r between the two individuals. Similarly, each node a includes a structure that stores all axioms of the form C ( a ) found during the iteration. The algorithm initializes all the nodes marked as unvisited, indicating that no node has been processed yet. Then, for each unvisited node in the graph, a DFS is performed starting from that node. The DFS function traverses the graph and collects new axioms based on the relationships encountered during the traversal. The original ontology is combined with the set of all encountered axioms, extending the ontology with the inferred axioms.

OPEN IN VIEWER

Algorithm 3 presents the modified DFS algorithm. Iterating over all adjacent nodes of the current node, the algorithm runs a routine to generate the axioms related to these adjacent nodes (Algorithm 3). Additionally, it also executes a routine to associate the generated chains of axioms from the recursive DFS calls with the current individual concerning the roles that connect them (Algorithm 3).

OPEN IN VIEWER

Algorithm 3 constructs new axioms based on the roles between the subject and the object individuals, also taking into account the concepts in which the object is an instance. Finally, Algorithm 4 processes a set of axioms to generate new chain axioms based on the roles and the relationships between the individuals subject and object.

OPEN IN VIEWER

It is important to note that infinite chains could occur depending on the existence of cycles in the graph. For instance, the addition of friendOf(Francesca, Giulia) to the previous example would result in the graph of Figure 2.

OPEN IN VIEWER

Figure 2.

Graph of relations generated after adding a cycle to the ontology.

This cycle generates the infinite chain ( ∃ friendOf . ) n ⊤ ( Giulia ) . Note, however, that an infinite chain cannot be represented, as the algorithm would get stuck in infinite recursive calls. To avoid this, we use the cycle detection of DFS to represent only the first level of recursion within the cycle. Thus, the above cycle would generate the following chains:

∃ friendOf . ⊤ ( Giulia ) ∃ friendOf . ∃ friendOf . Economist ( Giulia ) ∃ friendOf . Economist ( Francesca ) ∃ friendOf . ∃ friendOf . ⊤ ( Francesca )

Going back to the previous example, given the following ontology and repair request:  

(Ontology) O = { A ⊑ B , r ( a , b ) , A ( b ) }

 

(Repair Request) R = { ∃ r . ( A ⊓ B ) ( a ) }

Consider using ELK to compute the consequences and then applying the saturation over the inferred ontology:

Cn ELK ( O ) = { A ⊑ B , r ( a , b ) , A ( b ) , B ( b ) }

Sat ( Cn ELK ( O ) ) = { A ⊑ B , r ( a , b ) , A ( b ) , B ( b ) , ∃ r . A ( a ) , ∃ r . B ( a ) }

The partial meet pseudo-contraction, now, results in the following remainders:

r 1 = { A ⊑ B , ∃ r . B ( a ) , A ( b ) , B ( b ) } r 2 = { A ⊑ B , r ( a , b ) , B ( b ) , ∃ r . B ( a ) } r 3 = { r ( a , b ) , A ( b ) , ∃ r . A ( a ) , ∃ r . B ( a ) } r 4 = { r ( a , b ) , B ( b ) , ∃ r . A ( a ) , ∃ r . B ( a ) } r 5 = { A ( b ) , B ( b ) , ∃ r . A ( a ) , ∃ r . B ( a ) }

Comparing the remainders to the results obtained by repairs, note that r 1 and r 2 are equivalent to the optimal repairs. All other remainders represent possible contractions obtained by changing the TBox. In this case, the existential restrictions added by the saturation process were sufficient to generate remainders equivalent to the optimal repairs. Let’s examine another example:  

(Ontology) O = { ( A ⊓ C ) ⊑ B , r ( a , b ) , A ( b ) , C ( b ) }

 

(Repair Request) R = { ∃ r . B ( a ) }

Again, the TBox contributes to the justification of the unwanted sentence and therefore is considered to generate the copies:

a 0 := ⟨ a , ∅ ⟩ a 1 := ⟨ a , { ∃ r . B } ⟩ b 0 := ⟨ b , ∅ ⟩ b 1 := ⟨ b , { A } ⟩ b 2 := ⟨ b , { C } ⟩ b 3 := ⟨ b , { A , B } ⟩ b 4 := ⟨ b , { A , C } ⟩ b 5 := ⟨ b , { B , C } ⟩ b 6 := ⟨ b , { A , B , C } ⟩

As the number of atoms increases, the number of variables generated and, consequently, the number of repairs will also increase. The only option of a repair seed for a is a 1 . For the individual b , any generated variables can be used as a repair seed since no assertion of b is requested to be removed. It follows that the optimized IQ-repair is one of the following repairs:

O 1 = { ( A ⊓ C ) ⊑ B , ∃ r . A ( a ) , ∃ r . C ( a ) , A ( b ) , B ( b ) , C ( b ) } O 2 = { ( A ⊓ C ) ⊑ B , ∃ r . A ( a ) , ∃ r . C ( a ) , B ( b ) , C ( b ) } O 3 = { ( A ⊓ C ) ⊑ B , ∃ r . A ( a ) , ∃ r . C ( a ) , A ( b ) , B ( b ) } O 4 = { ( A ⊓ C ) ⊑ B , ∃ r . A ( a ) , ∃ r . C ( a ) , B ( b ) } O 5 = { ( A ⊓ C ) ⊑ B , r ( a , b ) , C ( b ) , ∃ r . A ( a ) } O 6 = { ( A ⊓ C ) ⊑ B , r ( a , b ) , A ( b ) , ∃ r . C ( a ) } O 7 = { ( A ⊓ C ) ⊑ B , ∃ r . A ( a ) , ∃ r . C ( a ) }

From the computed repairs, only O 1 , O 5 and O 6 are optimal repairs. All the others are contained in O 1 . Again, let’s consider the computed remainders computed without the saturation process:

r 1 = { ( A ⊓ C ) ⊑ B , A ( b ) , B ( b ) , C ( b ) } r 2 = { ( A ⊓ C ) ⊑ B , r ( a , b ) , C ( b ) } r 3 = { ( A ⊓ C ) ⊑ B , r ( a , b ) , A ( b ) } r 4 = { r ( a , b ) , A ( b ) , C ( b ) }

In this example, no remainder is equivalent to an optimal repair. Although remainders and repairs are very similar, the remainders lack the consequences that the reasoner could not compute. By computing the consequences on ELK and then saturating the inferred ontology, the contraction operation will increase the number of consequences on the remainders:

Cn ELK ( O ) = { ( A ⊓ C ) ⊑ B , r ( a , b ) , A ( b ) , B ( b ) , C ( b ) }

Sat ( Cn ELK ( O ) ) = { ( A ⊓ C ) ⊑ B , r ( a , b ) , A ( b ) , B ( b ) , C ( b ) ∃ r . A ( a ) , ∃ r . B ( a ) , ∃ r . C ( a ) }

The remainders then, computed by a partial meet pseudo-contraction, are:

r 1 = { ( A ⊓ C ) ⊑ B , A ( b ) , B ( b ) , C ( b ) , ∃ r . C ( a ) , ∃ r . A ( a ) } r 2 = { ( A ⊓ C ) ⊑ B , r ( a , b ) , C ( b ) , ∃ r . C ( a ) , ∃ r . A ( a ) } r 3 = { ( A ⊓ C ) ⊑ B , r ( a , b ) , A ( b ) , ∃ r . C ( a ) , ∃ r . A ( a ) } r 4 = { r ( a , b ) , A ( b ) , C ( b ) , ∃ r . C ( a ) , ∃ r . A ( a ) }

With the help of the reasoner, the saturator increased the closure of computed consequences so that the contraction achieved equivalence with the optimal repairs. The first three remainders are equivalent to the optimal repairs, while the last one has no equivalence, as it results from a contraction that changes the TBox.

The source code of the saturator developed for extending the ontology described in this section is available on GitHub ³ .

6. Discussion

In this work, we undertook a detailed study of approaches to construct optimal repairs in Ontology Engineering and how they relate to contractions in Belief Revision. This comparison is valuable as it highlights potential overlaps and similarities between these two areas, helping us to understand how approaches from each field may complement and enhance one another. Previous work examined classical repair approaches, which provided methods for constructing repairs by computing justifications. Santos et al. (2018) and Matos et al. (2019) explored the similarities between classical repairs and pseudo-contractions. Starting from Baader et al. (2020), the authors introduced a series of works to propose functional approaches of repairs that were not dependent on the syntactic structure of the axioms. These approaches focused on repairing the ABoxes while assuming that TBoxes did not change. In Baader (2023), the author compared optimal repairs resulting from functional constructions with pseudo-contractions, proving that in certain specific cases, optimal repairs were equivalent to the remainders of a partial meet pseudo-contraction. In this study, we have aimed to understand the scenarios in which the results of optimal repairs diverge from the remainders in contractions, enriching the understanding of how these approaches resemble each other.

Our work also synthesizes existing research on optimal repairs, enriching this synthesis with examples that can improve the understanding of each approach. By organizing these studies, we aim to support further exploration in the field of optimal repairs.

Compared to contractions, while the constructions of repairs presented in Baader et al. (2021) could achieve optimal results, the restriction to cycles and the fact that a repair does not affect the TBox can be seen as a pain point depending on the ontology that we need to repair. On the other hand, while functional approaches could find optimal repairs, the impossibility of a reasoner to compute an infinite set of consequences prevented the pseudo-contractions from achieving optimal results in some specific scenarios.

To summarize and clarify these differences, Table 2 presents a structured comparison between pseudo-contractions and optimal repairs, highlighting the main distinctions discussed above.

To bridge this gap between optimal repairs and pseudo-contractions, we proposed a method to saturate a KB, expanding the closure of computed consequences. This approach helped achieve optimal repairs in bases where pseudo-contractions could not compute optimal results using only the reasoner’s consequences.

There are still some open questions that this paper did not address, but they would provide interesting directions for future work. For example, it is unclear whether the consequences introduced through saturation are sufficient to ensure that pseudo-contractions consistently achieve optimal repairs. Also, it would be interesting to understand how functional approaches handle DLs other than E L , and whether it is possible to extend them to cases where TBoxes can also change.

Another aspect that was not considered in this work is the computational cost of the proposed algorithms. Since computational cost is a central concern in Ontology Repair, a deeper analysis of the cost of saturation would be an important direction for future research.