Contractions Based on Optimal Repairs (Extended Abstract)

1 Introduction

Representing knowledge in a logic-based knowledge representation language allows one to derive implicit consequences from a given knowledge base (KB). Modifying a given KB such that a certain unwanted consequence no longer follows is a nontrivial task, which has been investigated in the area of belief change under the name of contraction [Alchourrón et al., 1985] and in ontology engineering under the name of repair [Kalyanpur et al., 2006; Schlobach et al., 2007; Baader et al., 2018; Troquard et al., 2018].

∗This extended abstract reports on the approaches developed and results obtained in a paper published at KR 2024 [Baader and Wassermann, 2024a].

The purpose of the KR paper [Baader and Wassermann, 2024a] was to leverage recent advances in characterizing and computing optimal repairs [Baader et al., 2021; Baader et al., 2022; Baader and Kriegel, 2022; Baader et al., 2023] of ontologies based on Description Logics (DLs) [Baader et al., 2017] to obtain contraction operations that combine the advantages of belief set [Alchourrón et al., 1985] and belief base [Hansson, 1992; Nebel, 1989] contractions. To be more precise, it introduces a general framework for constructing contraction operations satisfying certain well-known rationality postulates, which generalizes the partial meet contraction approach in that it employs optimal repairs instead of optimal classical repairs as remainders. Like base contraction approaches, the contraction operations obtained this way have the advantage that (under certain conditions) they can work with finite KBs. However, in contrast to base contractions, they are syntax independent and lose less consequences.

Instead of introducing and applying this new approach for a specific instance, we consider in [Baader and Wassermann, 2024a] a very general setup, which clarifies the basic properties needed to apply it. Basically, we consider an entailment relation between KBs, without making explicit assumptions on the structure of the KBs and their semantics. For a start, we only require that entailment is reflexive and transitive. In addition, we abstract from non-entailment of a certain consequence as repair goal and only require that the set of repairs is closed under entailment. To apply a variant of the partial meet contraction approach in this setting, we need to make some additional assumptions. First, we assume that operations akin to (but not necessarily equal to) conjunction and disjunction are available, which we will respectively call sum and product. These operations correspond to union and intersection of belief sets, but are performed on (possibly finite) KBs representing them. From a technical point of view, sum is needed to formulate some of the relevant postulates whereas product plays the role of meet in the construction of the contraction operation. In addition, we require the existence of remainders, which are optimal repairs in our setting. An important property needed in the proof of the characterization theorem (i.e., the theorem that states the connections between the constructed contraction operations and the postulates) is that finitely many of these optimal repairs cover all repairs in the sense that every repair is entailed by an optimal one. In this extended abstract, we first recall the general setup and then describe the new contraction approach (called partial product contractions since the product is used as the meet operation), and state the characterization theorem. Due to space constraints, we can mention the different instances of the general approach only very briefly.

2 The General Setup

We assume that we are given a set of knowledge bases (KBs) and an entailment relation between knowledge bases. We usually write KBs as K, possibly primed (K′ ) or with an index (Ki), and entailment as |=, i.e., K |= K′ means that K entails K′ , or equivalently that K′ is entailed by K. We assume that entailment satisfies the following properties:

• K |= K (reflexivity),
• K |= K′ and K′ |= K′′ implies K |= K′′ (transitivity).

We call two knowledge bases K and K′ equivalent (and write K ≡ K′ ) if they entail each other, i.e., if K |= K′ and K′ |= K. We say that K strictly entails K′ if K |= K′ , but K′ ̸|= K. In this case we write K |=s K′ . The relation ≡ on KBs is indeed an equivalence relation, and we write the equivalence class of a KBK as [K], i.e., [K] := {K′ | K ≡ K′ }.

To illustrate the notions introduced in this section, we use a very simple example.

Example 1. Given a countably infinite set of propositional variables V , a knowledge base is a finite conjunction of such variables, where the empty conjunction is the always true constant ⊤. Entailment |= between KBs is then classical entailment in propositional logic, which obviously satisfies reflexivity and transitivity. For such a KB K, we denote the set of variables occurring in it with Var(K). It is easy to see that K |= K′ iff Var(K′ ) ⊆ Var(K). Consequently, K ≡ K′ iff Var(K) = Var(K′ ).

In the general case, we make no assumptions on the inner structure of knowledge bases, but we assume that we have operations sum and product available that are akin to conjunction and disjunction.

Definition 1. We call the operations ⊕ and ⊗ on finite, nonempty sets of KBs sum and product operations, respectively, if they satisfy the following properties for each finite, non-empty set of KBs K:

• ⊕K |= K for all K ∈ K and ⊕K is the least KB satisfying this property, i.e., if K′ is a KB satisfying K′ |= K for all K ∈ K, then K′ |= ⊕K.
• K |= ⊗K for all K ∈ K and ⊗K is the greatest KB satisfying this property, i.e., if K′ is a KB satisfying K |= K′ for all K ∈ K, then ⊗K |= K′ .

Note that "least" and "greatest" in the above definition must be read modulo equivalence of KBs. In fact, it is easy to see that the above conditions imply that sum and product of a finite set of KBs are unique up to equivalence. If K = {K} is a singleton set, then ⊕K ≡ K ≡ ⊗K. If K = {K1, . . . , Kn} for n ≥ 2, then we will sometimes write its sum as K1 ⊕ . . . ⊕ Kn and its product as K1 ⊗ . . . ⊗ Kn.

Example 1 (continued). It is easy to see that sum corresponds to conjunction of KBs, and thus to the union of the corresponding variable sets. Dually, product corresponds to the intersection of the variable sets. Thus, we define

where, for a finite set P ⊆ V , we denote the conjunction of its elements as KB(P). E.g.: p∧q∧r⊕q∧s = p∧q∧r∧s and p ∧ q ∧ r ⊗ q ∧ s = q. It is easy to see that the product and sum operations defined this way satisfy the properties required by Definition 1 (see [Baader and Wassermann, 2024b] for details).

When defining repairs, we assume that we have additional syntactic entities called repair requests.

Definition 2. Given a KB K, a repair request α determines a set of KBs Rep(K, α) such that

• K |= K′ holds for every element K′ ∈ Rep(K, α), and
• K′ ∈ Rep(K, α) and K′ |= K′′ imply K′′ ∈ Rep(K, α).

We call the elements of Rep(K, α) repairs of K for α. Two repair requests α and α′ are equivalent w.r.t. K (α ≡K α′ ) if they induce the same repairs of K, i.e., Rep(K, α) = Rep(K, α′ ).

Example 1 (continued). In this example, we consider a standard repair setting, where each KB can also be used as a repair request. Given a KB K and a repair request α, the goal then is to find a KB entailed by K that does not entail α, i.e., the induced set of repairs is defined as Rep(K, α) := {K′ | K |= K′ ,K′ ̸|= α}, where K′ ranges over KBs. The first condition on repair sets of Definition 2 is satisfied by definition and the second by transitivity of |=.

Continuing with presenting our general setup, we additionally assume the optimal repair property, which says that, for every pair K, α consisting of a KB and a repair request (called a repair problem), there exists a finite set of KBs Orep(K, α) satisfying

• Orep(K, α) ⊆ Rep(K, α) (repair property),
• every element K′ of Orep(K, α) is optimal, i.e., there is no K′′ ∈ Rep(K, α) such that K′′ |=s K′ (optimality),
• Orep(K, α) covers all repairs, i.e., for every K′′ ∈ Rep(K, α) there is K′ ∈ Orep(K, α) such that K′ |= K′′ (coverage).

Example 1 (continued). In this example, the optimal repair property is satisfied. Let K and α be KBs. If K ̸|= α, then we set Orep(K, α) := {K}, which in this case clearly is a set of optimal repairs that covers all repairs. If α = ⊤, then there is no repair, and we can set Orep(K, α) := ∅. Finally, assume that K |= α and α ̸= ⊤, which means that ∅ ̸= Var(α) ⊆ Var(K). For every p ∈ Var(α) we define K-p := KB(Var(K)\{p}). It is easy to see that each such KBK-p is a repair of K for α, i.e., is entailed by K and does not entail α. It is not hard to show that Orep(K, α) := {K-p | p ∈ Var(α)} is a set of optimal repairs of K for α that covers all repairs (see [Baader and Wassermann, 2024b] for details).

We conclude this section with a simple example that considers repair requests that do not require non-entailment. It is inspired by variable forgetting in propositional logic [Lang et al., 2003].

Example 2. Given a countably infinite set of propositional variables V , a knowledge base is a formula of propositional logic (built using the connectives ∧, ∨, ¬, and the truth constants ⊤ and ⊥). Entailment |= between KBs is the following restriction of classical entailment |=PL in propositional logic: K |= K′ if K |=PL K′ and additionally Var(K) ⊇ Var(K′ ) is satisfied. This entailment relation is clearly reflexive and transitive. As repair requests, we consider finite subsets of the set of propositional variables V . Given a KB K and a repair request α, the induced set of repairs is defined as Rep(K, α) := {K′ | K |= K′ , Var(K′ ) ∩ α = ∅}. Due to the additional requirement on entailment, the second condition of Definition 2 is satisfied.

Given a repair problem K, α, we construct the associated set of optimal repairs as follows. For every mapping τ : α → {⊤,⊥}, let Kτ be the propositional formula obtained from K by replacing every variable p ∈ α with τ(p). We set Orep(K, α) := {K-α}, where K-α is the disjunction of the formulas Kτ with τ ranging over all mappings from α to {⊤,⊥}. Clearly, the formulas Kτ do not contain any of the variables of α, and thus the same is true for K-α. A proof of optimality and coverage can be found in [Baader and Wassermann, 2024b].

It is easy to see that the sum operation again corresponds to conjunction, i.e., K1 ⊕. . .⊕Kn := K1 ∧ . . . ∧Kn. For the product, one could be tempted to use the disjunction operation of propositional logic. While disjunction behaves correctly w.r.t. |=PL, there is a problem with the containment condition for the variables. The set of variables occurring in a disjunction is again the union of the set of variables occurring in its disjuncts, but we would need it to be the intersection. We overcome this problem by repairing the disjunction. To be more precise, consider KBs K1, . . . , Kn, and set β := ⋃1≤i≤n Var(Ki) \ ⋂1≤i≤n Var(Ki). We define K1 ⊗ . . . ⊗ Kn := (K1 ∨ . . . ∨ Kn)-β . It is easy to see that, with this definition, the properties required for the product are satisfied (see [Baader and Wassermann, 2024b]).

3 Partial Product Contractions

In this section, we assume that we are given a set of KBs, a set of repair requests inducing repair sets that satisfy the conditions in Definition 2, and an entailment relation |= such that all the properties introduced in the previous section are satisfied. In the following, we adapt the partial meet contraction approach to this setting, but call the resulting approach the partial product contraction (PPC) approach since intersection (meet) is replaced with the product. Since the properties of entailment relations introduced in the previous section are needed for this contraction approach to work, we call such entailment relations PPC enabling.

Definition 3. Given a set of knowledge bases (KBs), a set of repair requests inducing repair sets, and a binary relation |= between KBs, we call |= PPC enabling if it is reflexive and transitive, has sum and product operations ⊕ and ⊗ satisfying the properties stated in Definition 1, and for every repair problem K, α the induced set of repairs Rep(K, α) satisfies the conditions in Definition 2 and has a finite subset Orep(K, α) that consists of optimal repairs and covers all repairs.

Let K be a KB and Orep(K, α) for each repair request α the corresponding set of optimal repairs, which covers all repairs of K for α. A selection function γ for K takes such sets of optimal repairs as input and satisfies the following properties, for each repair request α:

• If Orep(K, α) ̸= ∅, then the selected set γ(Orep(K, α)) satisfies ∅ ̸= γ(Orep(K, α)) ⊆ Orep(K, α).
• If Orep(K, α) = ∅, then γ(Orep(K, α)) = {K}.

Note that coverage of Orep(K, α) implies that this set is empty iff Rep(K, α) = ∅.

In addition, we require that selection functions are invariant under equivalence of their input sets, where we say that two sets K and K′ of knowledge bases are equivalent (written K ≡ K′ ) if they induce the same sets of equivalence classes, i.e., {[K] | K ∈ K} = {[K′ ] | K′ ∈ K′ }. More formally, the third condition on selection functions requires that, for all repair requests α and α′ , the following property is satisfied:

• If Orep(K, α) ≡ Orep(K, α′ ), then γ(Orep(K, α)) ≡ γ(Orep(K, α′ )).

Each selection function γ induces a PPC operation ctrγ:

A PPC operation defined using a selection function γ satisfying |γ(Orep(K, α))| = 1 for all repair requests α is called a MaxiChoice PPC operation. In this setting, the selection function returns a singleton set consisting of K (if there is no repair) or an optimal repair (otherwise). In the latter case, ctrγ(K, α) is then this optimal repair.

3.1 Postulates

We show that each PPC operation ctr satisfies the following rationality postulates:

• K |= ctr(K, α) (logical inclusion),
• ctr(K, α) ∈ Rep(K, α) if Rep(K, α) ̸= ∅ (success),
• ctr(K, α) ≡ K if Rep(K, α) = ∅ (failure),
• if K ∈ Rep(K, α), then ctr(K, α) ≡ K (vacuity),
• if α ≡K α′ , then ctr(K, α) ≡ ctr(K, α′ ) (preservation),
• if K |= K′ and ctr(K, α) ̸|= K′ , then there is K′′ such that K |=s K′′ |= ctr(K, α), K′′ ∈ Rep(K, α), and K′′ ⊕K′ ̸∈ Rep(K, α) (relevance).

MaxiChoice PPC operations also satisfy the postulate fullness, which is stronger than relevance:

• if K |= K′ and ctr(K, α) ̸|= K′ , then ctr(K, α) ⊕K′ ̸∈ Rep(K, α) (fullness).

It is easy to see that, in the presence of logical inclusion, success, and failure, the postulate fullness implies relevance.

Proposition 4. Let γ be a selection function. Then the PPC operation ctrγ induced by γ satisfies the postulates logical inclusion, success, failure, vacuity, preservation, and relevance. If γ is such that |γ(Orep(K, α))| = 1 for all repair requests α, then ctrγ additionally satisfies fullness.

The proof of this proposition is similar to standard proofs of such results from the belief change community, and in particular to the proof of the corresponding result in [Rienstra et al., 2020] for the special case of concept contraction in the DL EL. It is nevertheless important to have a detailed proof of this proposition since one needs to check that such a proof also goes through under the sparse assumptions made by our framework. Such a detailed proof can be found in [Baader and Wassermann, 2024b].

The postulates logical inclusion, success, vacuity, and preservation are variants of the original AGM postulates for belief set contraction [Alchourrón et al., 1985], but adapted to a setting where the belief set is represented by a KB K and the goal of the contraction may be different from getting rid of an unwanted consequence (see Example 2). The AGM postulate recovery is replaced with relevance or fullness.

3.2 Characterization Theorem

We now show that, modulo equivalence, the converse of Proposition 4 holds as well. We say that two contraction operations ctr and ctr′ are equivalent if ctr(K, α) ≡ ctr′ (K, α) holds for all KBs K and repair requests α. The following theorem states this result simultaneously for the general and the MaxiChoice setting.

Theorem 1. Assume that |= is PPC enabling, and let ctr be an operation that receives as input a KB and a repair request, and returns as output a KB. Then the following are equivalent:

1. The operation ctr satisfies logical inclusion, success, failure, vacuity, preservation, and relevance (fullness).
2. The operation ctr is equivalent to a (MaxiChoice) PPC operation.

Proof. (sketch) The implication "2 ⇒ 1" is an immediate consequence of Proposition 4.

To prove "1 ⇒ 2," we first consider the MaxiChoice case. Thus, assume that ctr satisfies the postulates logical inclusion, success, failure, vacuity, preservation, and fullness. To show that ctr is a MaxiChoice PPC operation, we define an appropriate selection function. For a KB K and repair request α, we set

It is shown in [Baader andWassermann, 2024b] that this definition yields a well-defined selection function γ satisfying |γ(Orep(K, α))| = 1 and ctr ≡ ctrγ .

For the general case, we assume that ctr satisfies the postulates logical inclusion, success, failure, vacuity, preservation, and relevance. To show that ctr is a PPC operation, we again define an appropriate selection function. For a KB K and repair request α, we set

The proof that this definition yields a well-defined selection function γ satisfying ctr ≡ ctrγ can again be found in [Baader and Wassermann, 2024b].

4 Instances of the General Setup

In [Baader and Wassermann, 2024a], a number of instances of the general framework introduced in the previous two sections are described in detail. Additional instances can be found in the accompanying technical report [Baader and Wassermann, 2024b]. Due to space restrictions, we can mentions these instances only very briefly here.

First, it is shown in [Baader and Wassermann, 2024a] that under weak assumptions on the underlying logic (inclusion, monotonicity, idempotency, and compactness of the closure operator), partial meet contractions for belief sets are an instance of the framework. Thus, the PPC approach introduced in Section 3 can be used to obtain contraction operations for belief sets that satisfy the postulates logical inclusion, success, failure, vacuity, preservation, and relevance (and additionally fullness in the MaxiChoice case). These postulates do not coincide with the ones given in [Alchourrón et al., 1985]. In particular, recovery is replaced with relevance or fullness. The reason is that Alchourrón et al. make additional assumptions on the formulas and the closure operator.

Second, as practically relevant instances of the general setup for which KBs are finite, various types of KBs and entailment relations connected with the DL EL [Baader et al., 2017] are considered. This encompasses (a) EL concepts as KBs with subsumption as entailment relation, where the repair goal is either to get rid of subsuming concepts or to forget parts of the signature used to formulate the concepts; (b) quantified ABoxes as knowledge bases describing data and different kinds of entailment relations, depending on the kinds of queries one wants to employ; (c) EL terminologies (TBoxes) as KBs with a restricted form of entailment relation between them that preserves the structure of the TBox. In most of these cases, the optimal repair property had already been shown by previous work [Baader, 2023; Baader et al., 2021; Kriegel, 2022], and the main additional task was to establish the existence of appropriate product and sum operations.

Third, to illustrate the generality of the approach, a setting is considered where KBs define formal languages and entailment corresponds to the superset relation between languages. The repair request is then a finite language α, and the repair goal is to remove at least one element (choice approach) or all elements (package approach) of α. It is shown that the superset relation is PPC enabling if KBs are finite automata, linear bounded automata, or Turing machines. However, if context-free grammars are used instead, then this entailment relation is not PPC enabling since the product need not exist.

Acknowledgements

Franz Baader was partially supported by DFG, Grant 389792660, within TRR 248 "Center for Perspicuous Computing", and by the German Federal Ministry of Education and Research (BMBF, SCADS22B) and the Saxon State Ministry for Science, Culture and Tourism (SMWK) by funding the competence center for Big Data and AI "ScaDS.AI Dresden/Leipzig". He would also like to thank the participants of the "6th Madeira Workshop on Belief Revision, Argumentation, Ontologies, and Norms (BRAON 2024)" for helpful discussions. Renata Wassermann would like to thank the Center for Artificial Intelligence (C4AI-USP), supported by the São Paulo Research Foundation (FAPESP grant #2019/07665-4) and the IBMCorporation. Both authors thank the anonymous reviewers of the KR paper for their helpful comments.