The Ontology Revision

1 Introduction

A general approach for studying belief revision is to provide a set of postulates such as the AGM axiom [Alchourr et al., 1985] and the DP axiom [Darwiche and Pearl, 1997] for belief revision functions.

In the process of building and maintaining ontologies, new statements which may be inconsistent with ontologies are added to the ontologies constantly, and it is necessary for the ontologies to be revised to accommodate new statements. For convenience, we assume an ontology O is a tree under the subsumption relation between concepts and can infer what are not explicitly stated by the ontology.

The ontology revision should have the following features:

• Similar to belief revision, there are two kinds of ontology revision: ontology-set revision and ontology-base revision. For an ontology O, its ontology-set is Th(O), a set of statements deduced from O by a set of inference rules; and its ontology-base is O. In this paper, we only discuss ontologybase revision. Moreover, like belief revision, the ontology

∗The work is supported by the National NSF of China (60373042, 60273019 and 60073017), the National 973 Project of China (G1999032701) and Ministry of Science and Technology (2001CCA03000).

revision satisfies some basic principles: success, consistency and minimal change.

• In belief revision, if a knowledge base K and a revising statement α is inconsistent then K is to be contracted. In ontology revision, let O ◦ θ be the ontology results from revising O by a revising statement θ; S be the smallest set of statements extracted from O to ensure (O ∪ {θ}) - S is consistent; ∆ be the smallest set of statements extracted from O other than S, and T be the smallest set of statements added to O ◦ θ other than θ, which is consistent with (O ∪ {θ}) - S. To preserve structural properties of the revised ontology, let O ◦ θ = ((O ∪ {θ}) - (S ∪ ∆)) ∪ T.
• An ontology O is inconsistent iff there is a statement δ such that δ, ¬δ ∈ OCWA, where OCWA is an extended theory of Th(O) in terms of the closed world assumption. An ontology revision should consider two cases: (1) O ∪ {θ} is consistent; and (2) O ∪ {θ} is inconsistent. When O ∪ {θ} is inconsistent, if θ is positive then either ¬θ ∈ O, ¬θ ∈ Th(O) or ¬θ ∈ OCWA; otherwise, either ¬θ ∈ O or ¬θ ∈ Th(O).

In terms of the postulates the ontology revision should satisfy, to preserve structural properties of ontologies and infer implicit statements ontologies have inherently during revision processes, we propose a Z axiom system for the ontology revision and a concrete operator satisfying the Z axiom system.

2 Ontologies

Definition 1 An ontology O consists of

1. a set of concepts and properties;
2. four binary relations: the subsumption relation ⊑ between concepts; the inheritance relation ⇒ and the default one ⇒d between concepts and properties; the implication relation ↦→ between properties; and
3. a set of positive statements of the form

and their negations of the form

where C, D are concepts and ϕ, ψ are properties.

• C ⊑ D means that C is a sub-concept of D; C ⇒ ϕ means that ϕ is a property of C instantiated by every instance of C; C ⇒d ϕ means that ϕ is a default property of C, which means that normally, every instance of C satisfies ϕ; ϕ ↦→ ψ

means that ϕ implies ψ logically; ϕ ⇒ C means that any instance satisfying ϕ is an instance of C. We assume that if a statement δ is positive, then ¬δ is its negation; otherwise, ¬δ is its positive form.

An ontology O is assumed to be complete about the properties in the following sense: (1) every property is in O; (2) for any properties ϕ, ψ ∈ O, if ϕ logically implies ψ then ϕ ↦→ ψ ∈ O; and (3) for any concepts C,D ∈ O, if C ̸= D then there is a property ϕ such that either C ⇒d ϕ and D ̸⇒d ϕ, or C ̸⇒d ϕ and D ⇒d ϕ.

Deduction rules in ontologies include transitivity rules, (default) inheritance rules and the closed world assumptions. For the inheritance rules,

there is a priority order among the default rules so that subconcepts override super-concepts. For the transitivity, besides the transitivity of ⊑ among concepts, there are the following three kinds of transitivity rules:

With the above rules, we define O ⊢ δ if there is a deduction of δ from O. Then, Th(O) = {δ : O ⊢ δ} and OCWA = Th(O) ∪ {¬δ : O ̸⊢ δ, δ is positive}.

3 The ontology revision

For an ontology O to be revised and a revising statement θ, we have the following presuppositions about ◦:

1. O is consistent and O ◦ θ is an ontology.
2. θ is of the form: C ⊑ D, C ̸⊑ D, C ⇒ ϕ and C ̸⇒ ϕ.
3. The ontology revision satisfies the principles of success (θ ∈ O ◦ θ), consistency (O ◦ θ is consistent) and minimal change (the symmetric difference between the set of statements in O and the set of statements in O ◦ θ is minimal.)
4. Statements other than θ are added to O ◦ θ to infer implicit statements.

To keep the structure of O ◦ θ, we may add to O ◦ θ new statements if θ = C ̸⊑ D; and extract statements from O if θ = C ⊑ D. Not like in the belief revision, in the ontology revision, revising statement θ is atomic.

Based on the above discussion, we propose a Z axiom system for the ontology revision:

• Z0. O ◦ θ is an ontology.
• Z1. O ◦ θ is consistent if θ is not contradictory.
• Z2. θ ∈ O ◦ θ.
• Z3. If O ∪ {θ} is consistent, then O ◦ θ = (O ∪ {θ}) -∆.
• Z4. If O ∪ {θ} is inconsistent, then

• Z5. If O ◦ θ ⊢ δ then (O ◦ δ) ◦ θ ≡ O ◦ θ.

The Z axiom system is the combination of the AGM axiom and the DP axiom for the iterated belief revision. For the ontology revision, such a combination is appropriate, because of δ being atomic.

Theorem 1 The Z axiom system satisfies the principles of success, consistency and minimal change.

Theorem 1 holds for the ontology revision, because we use atomic statements to revise ontologies, and in the belief revision, the revising statements may not be atomic.

4 A concrete ontology revision ◦

We shall give a concrete ontology revision ◦ satisfying the Z axiom system. Assume that θ is not contradictory (otherwise, let O ◦ θ = ∅). By presupposition 2, θ is of one of the following forms: C ⊑D; C ̸⊑D; C ⇒ϕ; C ̸⇒ϕ.

In the ontology revision, O ∪ {θ} is either consistent or inconsistent. When O ∪ {θ} is consistent, if θ is positive then either θ ∈ O, θ ∈ Th(O) or ¬θ ∈ OCWA; otherwise ¬θ /∈ Th(O). When O ∪ {θ} is inconsistent, if θ is positive then either ¬θ ∈ O, ¬θ ∈ Th(O) or ¬θ ∈ OCWA; otherwise either ¬θ ∈ O, or ¬θ ∈ Th(O).

The concrete ontology revision ◦ is given according to the above 18 cases. For the page limit, we only discuss two cases: Case 1. O ∪ {θ} is consistent and θ = C ⊑ D, θ /∈ O, T h(O), ¬θ ∈ OCWA. Let O ◦ θ = (O ∪ {θ}) - ∆, where ∆ = {C ⊏ E ∈ O : D ⊏ E /∈ Th(O)}.

Case 2. O ∪ {θ} is inconsistent and θ = C ⊑ D, ¬θ ∈ O. Let O ◦ θ = ((O ∪ {θ}) - (S ∪ ∆)) ∪ T ; where

• S = {C ̸⊑ D} ∪ {C ̸⇒ ϕ ∈ O : D ⇒ ϕ ∈ T h(O)}∪ {C ̸⇒d ϕ ∈ O : D ⇒d ϕ ∈ Th(O)};

∆ = {C ⊏ E ∈ O : D ⊏ E /∈ Th(O)};

{C ⇒d ϕ ∈ Th(O) : D ⇒d ϕ /∈ Th(O)}.

By verifying that ◦ defined in every case satisfies the Z axiom, we have the following theorem:

Theorem 2 The defined ◦ satisfies the Z axiom system.

5 Further works

The future work will introduce to the ontology revision the logical properties between statements (such as C ⇒ ϕ implies C ⇒d ϕ, etc.), the structure of concepts (complex concepts as ¬C, C ⊓D, etc.) and properties in description logics and first order logic, which are omitted for the simplicity in this paper.