Combining Default Logic Databases ^{∗}

Chitta Baral^{†}  Sarit Kraus^{‡}  Jack Minker^{§}  V.S.Subrahmanian^{¶}

Abstract

During the past decade, it has become increasingly clear that the future generation of large-scale knowledge bases will consist, not of one single isolated knowledge base, but a multiplicity of specialized knowledge bases that contain knowledge about different domains of expertise. These knowledge bases will work cooperatively, pooling together their varied bodies of knowledge, so as to be able to solve complex problems that no single knowledge base, by itself, would have been able to address successfully. In any such situation, inconsistencies are bound to arise. In this paper, we address the question: “Suppose we have a set of knowledge bases, KB_{1}, …, KB_{n}, each of which uses default logic as the formalism for knowledge representation, and a set of integrity constraints IC. What knowledge base constitutes an acceptable combination of KB_{1}, …, KB_{n}?”

1 Introduction

During the past decade, it has become increasingly clear that the future generation of large-scale knowledge bases will consist, not of one single isolated knowledge base, but a multiplicity of specialized knowledge bases that contain knowledge about different domains of expertise. These knowledge bases will work cooperatively, pooling together their varied bodies of knowledge, so as to be able to solve complex problems that no single knowledge base, by itself, would have been able to address successfully. At the same time the knowledge bases also have to follow certain guidelines, similar to integrity constraints in databases.

∗This research was supported by NSF grants IRI-8609170, IRI-9109755, CDA 90-15-006, IRI 92-11-662, by ARO grant DAAL-03-92-G-0225, by AFOSR grant F49620-93-1-0065 and by Israeli Ministry of Science and the Arts grant 4210-1-93. Please address all correspondence to: Jack Minker.

†Department of Computer Science, University of Texas at El Paso, El Paso, Texas 79968, U.S.A. E-mail:

chitta@cs.ep.utexas.edu

‡Department of Computer Science, Bar-Ilan University, Ramat Gan, Israel. E-mail:

sarit@bimacs.cs.biu.ac.il

§Department of Computer Science and Institute for Advanced Computer Studies, University of Maryland, College Park, Maryland 20742. E-mail: minker@cs.umd.edu

¶Department of Computer Science and Institute for Advanced Computer Studies, University of Maryland, College Park, Maryland 20742. E-mail: vs@cs.umd.edu

The problem of combining certain kinds of multiple knowledge bases has been studied previously in [1, 2]. There, we considered how to combine a set {KB_{1}, …, KB_{n}} of knowledge bases in presence of integrity constraints when each of the knowledge bases was (i) a Horn theory [1], or (ii) a first order logic theory [2].

A key aspect of knowledge representation is the ability to represent and use rules that are “almost always” valid, but which may be inappropriate in exceptional circumstances. For instance, if we have a FLIGHT database that contains information about airplane schedules, an airline may use a rule of the form:

If plane P is used for flight F from location A to location B, and the estimated flight time is T, and the flight departs at time Dep, then plane P should be at place B at time (Dep + T).

This may be expressed as the logic rule:

at(P, B, Dep + T) ← plane(P) &
at(P, A, Dep) &
flight(F, A, B, T) &
departs(F, Dep) &
used for(P, F).

Here, plane(P) means “P is a plane”, at(P, A, Dep) means “P is at place A at departure time Dep”, flight(F, A, B, T) means that “Flight number F is from place A to place B and takes T hours”, departs(F, Dep) means that “flight F departs at time Dep” and used for(P, F) means that “plane P is used for flight F.

The above rule is quite reasonable, but there may be exceptions to it. For example, plane P may have to make an emergency landing at some intermediate point C. In such a case, the airline database would be updated to specify that plane P is at location C at time (Dep + T). However, if the above rule is present, it would allow us to conclude that plane P is at location B, thus leading to an inconsistency (assuming that the plane can be at only one place at a time). The point being made is that the above rule is defeasible; it is applicable under “ordinary” circumstances, but as soon as an unusual event (such as an emergency landing) occurs, the rule needs to be suppressed. Default logic, introduced by Reiter [14], is one significant proposal to allow the suppression of such rules under unusual circumstances.

The key aim of this paper is to study the combination of multiple knowledge bases when each of these knowledge bases is a default logic theory. This provides an important extension of the work reported in [1, 2]:

• In real life, most rules provided by domain experts are defeasible in nature – they apply most of the time, but not always. In exceptional circumstances, the knowledge representation formalism must have the ability to suppress certain rules, and default logic, unlike Horn clause logic and first order logic, possesses this property.

• The relationship between default logic and the semantics of deductive databases has been carefully studied [11]. Hence, all the work reported here directly applies to combining multiple non-monotonic deductive databases.

There are several criteria we would like any techniques for combining databases to follow:

Identity: If the set of knowledge bases being combined is a singleton set, then the combination function should not make any changes.

Consistency: As we will demonstrate in the following section, when combining different knowledge bases, each consistent by itself, inconsistencies may arise. We would like the result of the combination to be consistent. There are two main situations, both of which will be considered in this paper:

• The person (or the system) who combines the data/knowledge bases has no additional information for restoring consistency.

• The person (or the system) does have additional information, including some numeric evaluation or, more generally, a (total or partial) order on knowledge bases. In this case, they are called priorities.^{1}

Correctness: All the information included in the result of the combination function should have origins in one of the theories being combined.

Maximization: The result of the combination function should include as much information as possible (given the consistency restriction) of the theories being combined. (The reader will observe that the principle of identity above may be viewed as a special case of the principle of maximization).

Commutativity: The order of the theories to be combined do not matter. The fact that a theory is listed first does not give it any priority.

We formalize the above notions in the paper, and provide a combination function that satisfies these properties.

The organization of this paper is as follows: in Section 2, we present an example motivating the need for combining multiple knowledge bases. Section 3 presents a cautious approach to characterizing the meaning of an inconsistent default logic knowledge base. Section 4 shows how to use the framework of the previous section to combine multiple default logic knowledge bases. It provides axioms defining a suitable combination function, and presents three alternative combination functions satisfying these axioms. In Section 5, we show how to combine a set of default theories that have an associated priority ordering imposed upon them. Section 6 discusses extensions of this work and some of its principles.

1Though it is possible to have meta-rules about priorities, we do not consider those here – they are treated in detail in a companion paper by Pradhan, Minker and Subrahmanian [12].

2 Motivating Example

A reasoning agent functioning in a complex environment may need to take a number of diverse factors into account when attempting to evaluate the situation it is facing. For example, consider a robot in a nuclear plant. When evaluating the current conditions, the robot may need to consult multiple databases (or at least a database constructed by consulting multiple sources). Thus, for instance, the robot may observe that at time t_{0}:

Robot Observations

temperature(875, t_{0}) ←  (1)
pressure(400, t_{0}) ←  (2)
smoke level(117, t_{0}) ←  (3)
malfunctioning(component1, t_{0}) ←  (4)
malfunctioning(component2, t_{0}) ←  (5)

In addition, the robot has recourse to knowledge bases containing information on repairing the components in the nuclear plant. These components tend to be very complex, and hence, different components require different types of expertise. The expert on component 1 provides the following rules:

KB_{1} (Knowledge Base on Component 1)

ok(component1, T) ← pressure(X, T) & X ≤ 200  (6)
pressure(200, T + 1) ← do action1(T)  (7)
do action1(T) ← pressure(X, T) & X > 200.  (8)

The rules simply say that component1 functions correctly when the pressure is less than or equal to 200. Rule 7 provides for corrective action – it says that if action1 is performed at time T, then the pressure will be stabilized at 200.

The second expert, whose domain of knowledge concerns component2, provides the following information:

KB_{2} (Knowledge Base on Component 2)

ok(component2, T) ← temperature(T emp, T) & T emp ≤ 800  (9)
temperature(775, T + 1) ← do action2(T).  (10)
do action2(T) ← temperature(T emp, T) & T > 800.  (11)

His information says that component2 functions just fine as long as the temperature is under 800 degrees. He also tells us that performing action2 has the desired effect of bringing the temperature down to 775 degrees.

Finally, let us assume that we have an individual who is an expert on the overall functioning of a nuclear plant, but who knows little about the specifics of components 1 and 2. He may provide the rules:

KB_{3} (Knowledge Base on Overall Operations)

danger(high, T) ← pressure(P, T) & P ≥ 200 &  (12)
temperature(T emp, T) & T > 800 &
smoke level(S, T) & S ≥ 100.
danger(zero, T + 1) ← take safety action(T)  (13)
take safety ction(T) ← danger(high, T)  (14)

If we think carefully about KB_{1} and KB_{2}, we observe that the experts on the two components probably have very specialized knowledge. They are experts on their respective components, but probably do not have general knowledge of the overall aspects of the functioning of the power plant. It may be that component1 deals only with pressure, while component2 deals only with temperature, and that each expert is working under the assumption that temperature (in the first case) is reasonable, while in the second case, the expert assumes that the pressure is at reasonable levels. Both may assume that smoke levels are reasonable. However, the combination of high pressure (over 200), high temperature (over 800 degrees) and a high smoke level (over 100) may be a very unusual and bizarre situation.

Furthermore, the robot may have the rule:

do action1(T) ∨ do action2(T) ∨ take safety action(T) ← danger(high, T) (15)

In addition, there are constraints IC saying that the robot can perform only one action at any given time T. While pooling together the knowledge of several knowledge bases it is important not to violate these constraints.

A careful scrutiny of KB_{1}, KB_{2}, KB_{3} together with the robot observations and the integrity constraint IC reveals that:

• (Existence of Inconsistency) If we simply take the union of KB_{1}, KB_{2}, KB_{3} and the robot observations, then the integrity constraints are violated. Hence, combining knowledge of multiple experts in this way may lead to inconsistency.

• (Defeasibility and Rule Suppression) In order to recover consistency, we should suppress some of the rules. The rules, in any case, are intended solely as rules of thumb: they are true “most” of the time, but not always. A fundamental open question is: which rules should be suppressed, and how should this suppression be effected?

• (Prioritization) In this specific example, we may choose to suppress the actions suggested by the experts on the individual components. The reason is that the expert on overall operations of the nuclear plant is more credible on the overall safety aspects of the plant.

In the rest of this paper, we study different ways of combining multiple knowledge bases consisting of default theories. Before doing so, we observe that even a single default theory may be “meaningless”, and this problem needs to be addressed before we attempt to combine multiple knowledge bases. In fact, the solution to this problem is key to the combination of multiple knowledge bases.

3 Cautious Semantics for Inconsistent/Incoherent Default Theories

We assume that we have a fixed logical language L, whose ground atoms are denoted by AT. A (propositional) default is a triple d = (p(d), j(d), c(d)), where p(d) and c(d) are formulas of L = L(AT)^{2}, and j(d) is a finite subset of L. p(d) is called the prerequisite of d, j(d) the justification of d, and c(d) the conclusion of d. A default d is usually written as \frac{p(d):j(d)}{c(d)}. A default theory is a pair (D, W), where W ⊆ L and D is a collection of defaults.

Given a default theory (D, W) and a set E of formulas (called the context), we can define an operator R^{E,D} which maps sets of formulas to sets of formulas in the following way:

R^{E,D}(S) = Cn(S ∪ {c(d) : d ∈ D, p(d) ∈ S, ¬j(d) ∩ E = ∅}).

Here, Cn denotes the familiar Tarskian consequence operator and ¬j(d) denotes the set {¬β | β ∈ j(d)}. The operator R^{E,D}(S) was initially defined by Reiter [14] and is related to the notion of strong default proof discussed in [11]. The least fixpoint of this operator above Cn(W) is the set of formulas that have a strong proof [11] ¿from W using D and with respect to the context E. More formally,

Definition 1 (Iteration of R^{E,D}) Suppose (D, W) is a default theory, and E is a context. Then we define the iteration of R^{E,D} as follows:

R_{0}^{E,D}(W) = Cn(W).

R_{n+1}^{E,D}(W) = R^{E,D}(R_{n}^{E,D}(W))

R_{∞}^{E,D}(W) = ⋃_{n=0}^{∞} R_{n}^{E,D}(W) □

The most important structures in default logic are extensions, which are formally defined as follows.

Definition 2 (Extension) E is an extension of a default theory (D, W) iff E = R_{∞}^{E,D}(W). □

Example 1 The rule in section 1 can be represented by the following default rule:

\frac{plane(P), at(P, A, Dep), flight(F, A, B, T), departs(F, Dep), used for(P, F) : normal(P, T, Dep)}{at(P, B, Dep + T)}.

When there is an exception then the fact ¬normal(P, T, Dep) is added to the theory to prevent the default rule from concluding that P is at place B at time (Dep + T).

2L(AT) is the propositional language generated by considering the ground atoms in AT to be propositional symbols.

In the following example we discuss how to represent the robot example as a default theory.

Example 2 (Robot Example Revisited) If we return to the Robot Example, we observe that all the robot observations are definitive facts. There is nothing defeasible about them. Hence, the observations of the robot may be formulated as a default theory (D_{obs}, W_{obs}) where D_{obs} = ∅ and W_{obs} contains all the observations. On the other hand, the first rule (“If the pressure is less than 200 at time T, then component 1 is okay”) provided by the expert on component 1 is defeasible. In view of its defeasibility, it should be represented as:

\frac{pressure(X, T) & X ≤ 200 : ok(component1, T)}{ok(component1, T)}.

The default rule says that if the pressure at time T is known to be below 200 and it is consistent to assume that component 1 is okay at time T, then we can go ahead and make this assumption. The rules provided by the other experts may be treated similarly. Appendix 1 contains a complete translation of the knowledge provided by the multiple experts into default logic.

There are three integral components in any deductive database system: an extensional database (EDB) of “base” facts, an intensional database (IDB) of rules expressing relationships between EDB and/or IDB predicates, and a set of integrity constraints which the database must not violate (i.e. the database must be consistent with the integrity constraints). When databases are represented by a default logic theory (D, W), the EDB component is included in W. Those rules that are non-defeasible are also in W, while defeasible rules are expressed as defaults in D. Thus, in addition to a default theory (D, W), we assume default logic databases have an associated set, IC of integrity constraints.

Given the three parts of a default logic database, i.e., D, W and IC, one can define different notions of consistency. One criteria is whether the database possesses an extension or not. However, this can’t be the only criteria. An extension may be inconsistent with respect to classical logic as we demonstrate in Example 3 below. Furthermore, even if an extension of a database is consistent, we want to require that it satisfies the integrity constraints. We formalize these notions in the following definition.

Definition 3 (Consistency of default theories) A default theory Δ = (D, W) is said to be

• coherent iff Δ possesses an extension

• consistent iff Δ possesses an extension that is consistent w.r.t. the semantics of classical logic

• inconsistent iff Δ is not consistent and

• consistent w.r.t integrity constraints IC iff (D, W ∪ IC) is consistent.

In the following example we show that a default theory Δ may be coherent (i.e. has an extension) but still may not be consistent.

Example 3 Consider the default theory Δ = (D, W) where D = ∅ and W = {p, ¬p, r}. Δ is coherent as the set of all wffs of our language is an extension of Δ. However, Δ is not consistent.

We would like the result of combining databases to be consistent with respect to (w.r.t) integrity constraints. The main issue is how to resolve the inconsistencies of the combined theories. In the previous example we may decide to circumvent the inconsistency by concluding r because the sources of inconsistency, p and ¬p, are not in any sentence together with r. There are several approaches to resolving inconsistency in Knowledge Bases. Blair and Subrahmanian [3] and Kifer and Lozinskii [10] studied the problem of reasoning with inconsistencies in logic programs using multivalued logics. Grant and Subrahmanian [9] developed non-classical OD-semantics for reasoning in inconsistent knowledge bases. The problem with these approaches is that when the theory is consistent, their semantics may not always agree with the classical meaning of the theory. To reason with default theories which may be inconsistent we follow the approach in [2] (based on work of Rescher and Brandon[13]) where we consider maximal consistent subsets of a first order theory. Given a consistent first order theory, we obtain the original theory using the maximal consistent subsets approach.

A maximal consistent subset of an inconsistent theory Δ with respect to an ordering < is a consistent theory Δ′ < Δ such that there does not exist a consistent theory Δ^{∗} with Δ′ < Δ^{∗} ≤ Δ. Intuitively, each maximally consistent subset of Δ corresponds to a consistent state of the world Δ is trying to characterize. The maximization requirement provides a technique to retain as much information from the original theory as possible. In the presence of a set of worlds, one can either be bold and pick one of them as the “real” state of the world, or one can be cautious and consider all of them. But in the presence of integrity constraints (world knowledge or guidelines that every theory has to satisfy), we have to consider only those worlds that are consistent with respect to the integrity constraints. One approach would be to consider only those maximally consistent subsets that agree with the integrity constraints. Another approach would be to subdivide a maximal consistent subset Δ′ of the original theory Δ into the maximal subsets of Δ′ that are consistent with the integrity constraints. We follow the second approach, which is more cautious than the first one.

In the case of first order theories, maximality is defined based on the subset ordering. Since default theories have two different components, we have many choices for defining an ordering. We consider two possibilities in this paper: The ordering ≤_{s} treats both D and W equally, and is simply an inclusion ordering on both the W part and the D part of the default theory. The second ordering, ≤_{d}, treats the default part as being less important than the W part of the default theory. We further discuss the impact of our choices after defining maximality based on these orderings.

Definition 4 (Ordering) Given two default theories Δ_{1} = (D_{1}, W_{1}) and Δ_{2} = (D_{2}, W_{2}), we define two simple orderings on them.

1. Δ_{1} ≤_{s} Δ_{2} iff D_{1} ⊆ D_{2} and W_{1} ⊆ W_{2}.

2. Δ_{1} ≤_{d} Δ_{2} iff

(a) W_{1} ⊆ W_{2} and
(b) if W_{1} = W_{2} then D_{1} ⊆ D_{2}.

The following definition is a standard definition of maximal elements of a partially ordered set.

Definition 5 (Maximal elements) An element a in a partially ordered set (S, ≤) is said to be ≤-maximal in S iff there is no b ∈ S such that a ≠ b and a ≤ b.

We now use the notion of maximality above to define two different notions of “maximally consistent subset” of a default theory w.r.t. a set of integrity constraints.

Definition 6 (Maximal Consistency) Given Δ = (D, W) and a set IC of integrity constraints, we use the notation:

1. Lower(Δ) to denote the set {Δ_{1} : Δ_{1} ≤_{s} Δ }.

2. ConsLower(Δ, IC) denotes the set {Δ_{1} : Δ_{1} ∈ Lower(Δ) and Δ_{1} is consistent with IC}.

3. MAXCONS^{s}(Δ, IC) denotes the set of s-maximal elements of ConsLower(Δ, IC).

4. MAXCONS^{d}(Δ, IC) denotes the set of d-maximal elements of ConsLower(Δ, IC).

The main distinction between s-maximality and d-maximality is that in the former, the elements of the non-default part of the default theory play the same role (or are of equal importance) as the defaults themselves. In the case of d-maximality, the elements of W are preferred over the defaults themselves. In short, d-maximality considers defaults to be more defeasible (hence the prefix d-) than the first order formulas in W, while in s-maximality, defaults and first order formulas are equally defeasible – neither enjoys priority over the other. To see the distinction, consider the following example:

Example 4 Let Δ = (D, W) be the default theory where:

D = \{\frac{q : ¬p}{p}\} W = {r, q}

and let IC = ∅. Δ has no extensions. If we consider s-maximality, then there are two s-maximally consistent subsets Δ_{1} = (D_{1}, W_{1}) and Δ_{2} = (D_{2}, W_{2}) where:

D_{1} = ∅ W_{1} = {r, q}

D_{2} = \{\frac{q : ¬p}{p}\} W_{2} = {r} Of these two, however, only Δ_{1} = (D_{1}, W_{1}) is d-maximal because W_{2} ⊂ W_{1} and hence, Δ_{2} ≤_{d} Δ_{1}.

Note also that MAXCONS^{s}((D, W), IC) ≠ MAXCONS^{s}((D, W ∪ IC), ∅) and MAXCONS^{d}((D, W), IC) ≠ MAXCONS^{d}((D, W ∪ IC), ∅). This is demonstrated in the following simple example.

Example 5 Let Δ = (D, W) be the theory where D = ∅ and W = {p, q}. Let IC = {¬p ∨ ¬q}. It is easy to see that

MAXCONS^{s}((D, W), IC) = MAXCONS^{d}((D, W), IC) = {{p}, {q}}

while MAXCONS^{s}((D, W ∪ IC), ∅) = MAXCONS^{d}((D, W ∪ IC), ∅)

= {{p, q}, {p, ¬p ∨ ¬q}, {q, ¬p ∨ ¬q}}.

After removing the IC from the second set of theories we get {{p}, {q}, { p, q}} which is of course unacceptable if we would like the results to follow the “world knowledge”.

Given the definitions of s-maximality and d-maximality, we define the notion of sentailment and d-entailment respectively, based on the cautious approach.

Definition 7 (Cautious Semantics) Suppose Δ = (D, W) is a default logic theory. We say that Δ cautiously s-entails a formula F w.r.t. integrity constraints IC, denoted Δ ⊧C^{s} F, iff, for every s-maximally consistent subset Δ′ of Δ (w.r.t. IC), it is the case that F is true in each extension of Δ′.

The notation Caut s(Δ) denotes the set {F : Δ ⊧C^{s} F }.

The superscript s on the turnstyle refers to the fact that we are considering s-maximal subsets. Likewise, the subscript C represents that we are using the cautious approach.

The concept of d-entailment, denoted Δ ⊧C^{d} F may be defined similarly. So may the set Caut d(Δ).

The intuition behind the above definition is as follows: ⊧C^{s} (resp. ⊧C^{d}) is not easily willing to admit that anything is true. To conclude that p is true using ⊧C^{s} (resp. ⊧C^{d}), we must, intuitively, find all possible causes of inconsistency. If, after eliminating the cause of the inconsistency in all s-maximal possible ways, it turns out that p is true in each possible scenario (i.e., in any s-maximal consistent set), only then do we consider p to be true. We choose this approach as the basis of our combination function since there is no obvious reason to prefer one possible scenario over the other when there are no priorities over the theories to be combined. The following example demonstrates the differences between ⊧C^{s}

and ⊧C^{d}.

Example 6 Consider the default theory Δ = (D, W) of Example 4. In this case:

• Caut s(Δ) = {F | Δ ⊧C^{s} F } = Cn({r})

• Caut d(Δ) = {F | Δ ⊧C^{d} F } = Cn({q, r})

Algorithm 1 Procedure MAXCONS1^{s}(Δ = (D, W), IC) temp^{s} = ∅ If Δ is consistent with IC then MAXCONS1^{s}(Δ, IC) = Δ

else
   begin

{** Let D be the set of defaults {d_{1}, ⋯, d_{n}} and W be the set of sentences {w_{1}, ⋯, w_{m}}.**}

     If n > 1 then

For i = 1 ⋯ n do D_{i} := D − {d_{i}} temp^{s} = temp^{s} ∪ MAXCONS1^{s}((D_{i}, W), IC)

      od
     If m > 1 then

For i = 1 ⋯ m do W_{i} := W − {w_{i}} temp^{s} = temp^{s} ∪ MAXCONS1^{s}((D, W_{i}), IC)

      od

MAXCONS1^{s}(Δ, IC) := s-maximal elements of temp^{s}.

   end

Figure 1: Computing Maximally Consistent Subsets

3.1 Computing s-maximally consistent subsets

In this section, we study the problem of computing s-maximally consistent subsets of a default theory Δ.

To begin with, we point out that the problem is more subtle than might appear at first glance because a default theory Δ, unlike a first order theory, may be inconsistent while the theory obtained by adding elements to Δ may become consistent. For example, the default theory (\{\frac{b:¬a}{f}\}, \{¬f\}) is inconsistent, while the default theory (\{\frac{b:¬a}{f}\}, \{a, ¬f\}) is consistent.

Figure 1 contains a simple algorithm for this purpose. An algorithm that often performs fewer operations is presented in Figure 2.

The following shows that while computing the maximally consistent subsets we either directly or indirectly take into consideration all possible subsets. That means we do not leave out a potential maximally consistent subset.

Proposition 1 Suppose Δ = (D, W) is a default theory. Then for each default theory Δ′ that is consistent with IC and that has the property Δ′ ≤_{s} Δ, there exists a Δ′′ such that Δ′ ≤_{s} Δ′′ ≤_{s} Δ and:

1. the consistency of Δ′′ with IC is tested during the execution of algorithm MAXCONS1 on input Δ = (D, W) and

2. Δ′′ is found to be consistent with IC.

Proof. Immediately follows from the algorithm. □

We now prove the correctness of Algorithm 1.

Theorem 1 MAXCONS^{s}(Δ, IC) = MAXCONS1^{s}(Δ, IC).

Proof. [MAXCONS^{s}(Δ, IC) ⊆ MAXCONS1^{s}(Δ, IC)] Suppose X ∈ MAXCONS^{s}(Δ, IC) where X = (D_{X}, W_{X}). We proceed by induction on n where

n = ∥D∥ + ∥W ∥ − ∥D_{X}∥ − ∥W_{X}∥.

Base Case. (n = 0) The only way this is possible is if X = Δ. In that case, MAXCONS^{s}(Δ, IC) = {Δ}. Hence, when algorithm MAXCONS1^{s} is invoked with inputs Δ and IC, the consistency of Δ with IC is immediately established by the third line of the algorithm, and {Δ} is returned by the algorithm.

Inductive Case. (n = k + 1) In this case, X contains (k + 1) elements less than Δ. Suppose r of these elements are defaults, and (k + 1 − r) are wffs from the W part of Δ. There are two subcases.

Subcase 1. (r = 0) Then X = (D, W′) where W′ is obtained from W by deleting (k + 1) elements. Suppose these elements are deleted in the order:

f_{1}, …, f_{k+1}.

Then, each f_{i} = w_{α(i)} for some integer 1 ≤ α(i) ≤ m where W = {w_{1}, …, w_{m}}. Consequently, in the 4th line from the bottom of Algorithm 1, W_{α(i)} is set to (W − {f_{i}}) and a recursive call is made to MAXCONS1^{s} with inputs (D, W_{α(i)}) and IC. But now, with reference to this recursive call to MAXCONS1^{s}, the number

n′ = ∥D∥ + ∥W′∥ − ∥D_{X}∥ − ∥W_{X}∥

is equal to (n − 1), i.e. n′ = (n − 1) = k. Therefore, by the inductive hypothesis, X is in MAXCONS1^{s}(Δ′, IC) where Δ′ = (D, W′). As X is an s-maximally consistent subset of Δ′, we know that X is consistent, and is also a subset of Δ. The only remaining possibility is that X is not an s-maximally consistent subset of Δ. The only way this could happen is if the addition of f_{1} = w_{α(i)} to X causes X to be consistent which is impossible because then (D_{X}, W_{X} ∪ {f_{1}}) would be in MAXCONS^{s}(Δ, IC) thus contradicting the assumption that X ∈ MAXCONS^{s}(Δ, IC). Hence, X ∈ MAXCONS^{s}(Δ, IC).

Subcase 2. (r > 0) The proof is similar to Subcase 1. The only difference is that in this case, the f_{i}’s may be either in D or in W (rather than being from W in Subcase 1).

MAXCONS1^{s}(Δ, IC) ⊆ MAXCONS^{s}(Δ, IC) If X ∈ MAXCONS1^{s}(Δ, IC), then X must have entered the set temp^{s} at the j’th iteration of the loop of the MAXCONS1^{s} procedure. The proof is by a straightforward induction on i. □

The problem of finding the maximally consistent subsets of a default theory is inherently complex. Our goal in this paper is to focus on parts of Algorithm 1 that can be improved. But before that we briefly discuss the inherent complexity of the problem.

We show in Proposition 2 that a default theory may have an exponential number of maximally consistent subsets. But even to determine if a particular default theory (D, W) is consistent w.r.t. IC amounts to deciding if there exists an extension of (D, W ∪IC) which is consistent w.r.t. the semantics of classical logic. Gottlob [8] shows that the (simpler) problem of deciding whether a default theory has an extension is Σ_{2}^{p}-complete for seminormal default theories.

With these negative results in mind, our goal is to improve Algorithm 1 by eliminating redundant consistency checks.

Proposition 2 In the worst case, the MAXCONS1 algorithm may perform a consistency test exponentially many times (exponential in the size of the input).

Proof. Consider the input default theory Δ = (∅, {a_{1}, ¬a_{1}, …, a_{n}, ¬a_{n}} and IC = ∅. This default theory has 2^{n} s-maximal consistent subsets. The result follows from Proposition 1.

□

Proposition 2 shows that the procedure MAXCONS1^{s}(Δ, IC) may take exponential time. However, the proof of Proposition 2 uses an example that contains O(2^{n}) maximally consistent subsets. In this case, it would take exponential time just to write the output and hence, no algorithm (including ours) can be expected to do better than this.

The procedure MAXCONS1^{s}(Δ, IC), however, is an inefficient way of computing the smaximally consistent subsets of a default theory Δ. This is because when MAXCONS1^{s}(Δ, IC) is called, the procedure may check the consistency of a particular subset of Δ more than once, i.e. redundant computations may be performed. The following example illustrates such a case.

Example 7 Consider the default theory Δ = (D, W), where D = {d_{1}, d_{2}} and W = {w_{1}, w_{2}} and where none of the theories, Δ, ({d_{1}}, {w_{1}, w_{2}}), ({d_{2}}, {w_{1}, w_{2}}), ({d_{1}, d_{2}}, {w_{1}}), and ({d_{1}, d_{2}}, {w_{2}}) are consistent. Furthermore, let IC = ∅. When MAXCONS1^{s}(Δ, IC) is called the consistency of ({d_{1}}, {w_{1}}), ({d_{2}}, {w_{1}}), ({d_{1}}, {w_{2}}), and ({d_{2}}, {w_{1}}) is checked twice. □

As Example 7 shows, the MAXCONS1^{s} procedure may perform consistency checks more often than required. This is something that cannot be ignored because such consistency checking may be very expensive. We now proceed to develop a more efficient algorithm for this purpose. Figure 2 describes a procedure that checks to see, given a candidate smaximally consistent subset, whether a “bigger” s-maximally consistent subset is already known to exist. If so, then the candidate in question is not going to lead to s-maximality.

Using Algorithm 2, we may now define a more efficient procedure to compute the smaximally consistent subsets of a default theory Δ.

Algorithm 3, Figure 3, generates the s-maximal consistent subsets of a default theory Δ. The algorithm operates in a top-down fashion by first testing the consistency of the “largest”

Algorithm 2 Procedure Blocked(Y, Block) {** Checks to see if there is an element X ∈ Block such that Y ≤_{s} X **} Blocked(Y, Block) := false For all elements X in Block do

If Y ≤_{s} X then Blocked(Y, Block) := true; EXIT.

od

Figure 2: Finding if Y is blocked.

possible subsets of Δ, and testing smaller subsets only when needed. This is done by starting with all the subsets with the highest cardinality pair (for both the D and the W part) and checking all subsets of that cardinality pair.

On finding a consistent subset of Δ, this subset is saved in temp^{s}. Subsequently, before checking the consistency of other candidate subsets S, the algorithm checks if S is a subset of something already in temp^{s}. If so, then S cannot possibly lead to a s-maximally consistent subset and hence, its consistency need not be examined (thus saving a consistency test). If not, the consistency of S must be tested.

The variables wlast and dlast keep track of the unblocked subsets of W and D of the particular cardinality pair being considered. This serves two purposes: (1) Subsets of the unblocked elements need not be checked for consistency. (2) When the algorithm finds that there is no unblocked subset of length k in W (which means that for all subsets of length k a bigger consistent set is already found) then it does not test subsets of Δ whose W component contains less than k elements (similarly for the D part).

The following proposition shows that we take into consideration (either directly or indirectly) all subsets of Δ.

Proposition 3 Suppose Δ = (D, W) is a default theory and the algorithm NewMAXCONS1^{s} is called with inputs Δ and IC. Then: for all Δ′ such that Δ′ ≤_{s} Δ, there exists a Δ′′ such that:

• Δ′ ≤_{s} Δ′′ ≤_{s} Δ and

• the consistency of Δ′′ is tested and found to be consistent w.r.t. IC.

Proof. Similar to the proof of Proposition 1. □

We now show that the algorithm NewMAXCONS1^{s} does not perform any unnecessary consistency checking. This is the key proposition that distinguishes this algorithm from the MAXCONS1^{s} algorithm, which would, in many cases, perform redundant checking of this kind.

Algorithm 3 Procedure NewMAXCONS1^{s}(Δ, IC) {** Let Δ = (D, W). **} {** Let D be the set of defaults {d_{1}, ⋯, d_{n}} and W be the set of sentences {w_{1}, ⋯, w_{m}}.**} temp^{s} := ∅ For wlength = m to 1 do (1)

For all subsets W_{i} of W of cardinality wlength do (2)

    begin

wlast := ∅ ** Keeps track of the unblocked subsets of W of cardinality wlength**} For dlength = n to 1 do (3) For all subsets D_{i} of D of cardinality dlength do (4)

       begin

dlast := ∅ {** Similar use as wlast **}

If not Blocked((D_{i}, W_{i}), temp^{s}) (5)

        then
         beginthen

dlast := dlast ∪D_{i} wlast := wlast ∪W_{i} If (D_{i}, W_{i}) is consistent with IC

          then
           beginthen

temp^{s} := temp^{s} ∪(D_{i}, W_{i})

           endthen
         endthen

od (4)

If dlast = ∅ then EXIT {**meaning end this loop **}

od (3) od (2)

If wlast = ∅ then EXIT {** If all subsets of W of cardinality wlength are blocked then STOP**} od (1) NewMAXCONS^{s} = temp^{s}.

Figure 3: Efficiently Computing s-Maximally Consistent Subsets Proposition 4 Suppose Δ = (D, W) is a default theory and the algorithm NewMAXCONS1^{s} is called with inputs Δ and IC. Then: there is no default theory Δ′ such that the consistency of Δ′ is checked more than once during the execution of algorithm NewMAXCONS1^{s} on inputs Δ and IC.

Proof. Suppose the consistency of Δ′ has been checked once. There are two possible cases.

Case 1. [Δ′ is consistent with IC] In this case, Δ′ is saved in temp^{s}. The only place consistency tests are performed in algorithm NewMAXCONS1^{s} is in the line labeled (5). However, this line is executed only if the condition Blocked((D_{i}, W_{i}), temp^{s}) is false. Consequently, if Δ′ is already in temp^{s}, this test will fail if (D_{i}, W_{i}) = Δ′, and hence the consistency of Δ′ with IC is not checked a second time.

Case 2. [Δ′ is not consistent with IC] In this case, all recursive calls pick subsets of Δ′; consequently, no attempt is ever made later to check for consistency of Δ′ with IC. □

The following corollary follows immediately from Proposition 4.

Corollary 1 Suppose Δ = (D, W) is a default theory, IC is a set of integrity constraints and the algorithm NewMAXCONS1^{s} is called with inputs Δ and IC. Suppose Δ′ is a consistent subset of Δ. Then: for all Δ′′ such that Δ′′ ≤_{s} Δ′, the consistency of Δ′′ with IC is not tested. □

The following proposition shows that the NewMAXCONS1^{s} algorithm does not perform redundant blocking checks.

Proposition 5 Suppose Δ = (D, W) is a default theory, IC is a set of integrity constraints, and the algorithm NewMAXCONS1^{s} is called with inputs Δ and IC. Suppose Δ_{x} = (D_{x}, W_{x}) is such that

• D_{x} ⊆ D and

• the size of D_{x} is n and

• Δ_{x} is blocked during the execution of NewMAXCONS1^{s} on inputs Δ and IC.

Then: for all Δ_{y} = (D_{y}, W_{y}) such that D_{y} ⊆ D and the size of D_{y} is less than n, NewMAXCONS1^{s}(Δ, IC) terminates without checking if Δ_{y} is blocked or not. □

Proposition 4 and Proposition 5 show that NewMAXCONS1^{s} is more effective than MAXCONS1^{s} since NewMAXCONS1^{s} performs neither unnecessary consistency checks nor redundant blocking checks.

Even though NewMAXCONS1^{s} performs fewer consistency checks than MAXCONS1^{s}, the improvement in efficiency is limited by the fact that both NewMAXCONS1^{s} and MAXCONS1^{s} continue to check subsets of inconsistent theories in the hope of finding a maximal consistent subset. For example, consider the default theory (∅, {a_{1}, ¬a_{1}, a_{2}, …, a_{n}}). This theory has two maximal consistent subsets (∅, {a_{1}, a_{2}, …, a_{n}}) and (∅, {¬a_{1}, a_{2}, …, a_{n}}).

NewMAXCONS1^{s} is able to find them after making n+1 consistency checks but does not stop right after finding them. Even though it does not check the consistency of any subsets (because of blocking) of these two sets, it still checks the consistency of all inconsistent subsets of the original theory, which are exponential in number.

Finally, we prove that the algorithm NewMAXCONS1^{s} is correct.

Theorem 2 MAXCONS^{s}(Δ, IC) = NewMAXCONS1^{s}(Δ, IC).

Proof. It is immediate from the algorithm that NewMAXCONS1^{s}(Δ, IC) ⊆ MAXCONS_{1}^{s}(Δ, IC). It suffices to prove that MAXCONS_{1}^{s}(Δ, IC) ⊆ NewMAXCONS1^{s}(Δ, IC).

Suppose (D′, W′) is in MAXCONS_{1}^{s}(Δ, IC). As (D′, W′) is in MAXCONS_{1}^{s}(Δ, IC), there is no superset (D^{∗}, W^{∗}) such that (D^{∗}, W^{∗}) is consistent with IC. Consequently, no such (D^{∗}, W^{∗}) is in temp^{s}.^{3} Consequently, when we attempt to check if (D′, W′) is blocked by something in temp^{s}, there will be no such block, and hence the consistency of (D′, W′) with IC is tested (successfully) and hence, (D′, W′) is added to temp^{s}. As nothing that is added to temp^{s} is ever deleted, (D′, W′) is returned by the algorithm. □

3.2 Computing d-maximally consistent subsets

The key difference between s-maximally consistent subsets of a default theory Δ and integrity constraints IC, and the d-maximally consistent subsets is that in the former, both default rules, as well as rules in W are considered to be “equally true”. However, this situation is not always appropriate: after all, a rule is represented as a default because it is intended to be defeasible. Hence, in many situations, it may be preferable to suppress default rules rather than rules in W.

We now present an algorithm (Figure 3) to compute the d-maximally consistent subsets of Δ with respect to integrity constraints IC.

Proposition 6 Suppose Δ = (D, W) is a default theory with integrity constraints IC. Then: for each Δ′ ≤_{d} Δ, there exists a Δ′′ such that Δ′ ≤_{d} Δ′′ ≤_{d} Δ and:

1. the consistency of Δ′′ with IC is tested during the execution of algorithm MAXCONS1^{d} on input Δ = (D, W) and

2. Δ′′ is found to be consistent with IC.

Proof. The proof is analogous to the proof of Proposition 1. □

The following theorem proves the correctness of Algorithm 4.

Theorem 3 MAXCONS^{d}(Δ, IC) = MAXCONS1^{d}(Δ, IC).

3(D^{∗}, W^{∗}) is said to be a superset of (D, W) iff (D^{∗}, W^{∗}) ≠ (D, W) and D^{∗} ⊃ D and W^{∗} ⊃ W.

Algorithm 4 Procedure MAXCONS1^{d}(Δ, IC) {** Let Δ = (D, W). **} {** Let D be the set of defaults {d_{1}, ⋯, d_{n}} and W be the set of sentences {w_{1}, ⋯, w_{m}}.**} temp^{d} := ∅ If Δ is consistent with IC then return Δ

    else
     begin

For all subsets D_{i} of D do If (D_{i}, W) is consistent with IC then temp^{d} := temp^{d} ∪(D_{i}, W).

        endif
       od

If temp^{d} = ∅ and m > 1

       then

For i = 1 ⋯ m do W_{i} := W − {w_{i}} temp^{d} := temp^{d} ∪MAXCONS1^{d}((D, W_{i}), IC)

        od

MAXCONS1^{d}(Δ, IC) = d-maximal elements of temp^{d}.

     end

Figure 4: Computing d-Maximally Consistent Subsets Algorithm 5 Procedure Blocked^{d}(Y, Block) {** Finds if a superset of Y is already present in Block. **} Blocked^{d}(Y, Block) := false For all elements X in Block do

If Y ⊆ X then Blocked^{d}(Y, Block) := true; STOP.

od

Figure 5: d-Blocking Algorithm

Proof. The proof is analogous to the proof of Theorem 1. □

In the worst case, the MAXCONS1^{d} algorithm may perform a consistency test exponentially many times (exponential in the size of the input). Furthermore, as in the case of the MAXCONS1^{s} algorithm, it is possible that the MAXCONS1^{d} algorithm will perform redundant consistency checks. The procedures described in Figure 4 and Figure 5 may be used to correctly compute the d-maximally consistent subsets of Δ without redundant computations being performed. The procedure of Figure 4 is analogous, but not identical, to the blocking procedure for computation of s-maximally consistent sets. Similarly, the procedure of Figure 5 represents a version of the procedure NewMAXCONS1^{s}, modified to effectively compute the d-maximally consistent subsets (w.r.t. integrity constraints IC) of a default theory Δ.

The following results are proved in exactly the same way as the analogous results for computation of s-maximally consistent subsets. They show that the algorithm NewMAXCONS1^{d} is sound and complete for such computations, and also that no redundant consistency checks are performed.

Proposition 7 Suppose Δ = (D, W) is a default theory, IC is a set of integrity constraints, and the algorithm NewMAXCONS1^{d} is called with inputs Δ and IC. Then: for all Δ′ such that Δ′ ≤_{d} Δ, there exists a Δ′′ such that:

• Δ′ ≤_{d} Δ′′ ≤_{d} Δ and

• the consistency of Δ′′ is tested and found to be consistent with IC. □

Proposition 8 Suppose Δ = (D, W) is a default theory, IC is a set of integrity constraints, and the algorithm NewMAXCONS1^{d} is called with inputs Δ and IC. Then: there is no default theory Δ′ such that the consistency of Δ′ with IC is checked more than once during the execution of algorithm NewMAXCONS1^{s} on inputs Δ and IC. □

Proposition 9 Suppose Δ = (D, W) is a default theory, IC is a set of integrity constraints, and the algorithm NewMAXCONS1^{s} is called with inputs Δ and IC. Suppose Δ′ is a consistent subset of Δ. Then: for all Δ′′ such that Δ′′ ≤_{d} Δ′, the consistency of Δ′′ with IC is not tested. □

Algorithm 6 Procedure NewMAXCONS1^{d}(Δ, IC) {** Let Δ = (D, W). **} {** Let D be the set of defaults {d_{1}, ⋯, d_{n}} and W be the set of sentences {w_{1}, ⋯, w_{m}}.**} temp^{d} := ∅ wblock := ∅ {** Keeps track of the W part of the maximally consistent subsets found so far**} For wlength = m to 1 do (1)

For all subsets W_{i} of W of cardinality wlength do (2)

   begin

wlast := ∅{** Keeps track of the unblocked subsets of W of cardinality wlength**} If not Blocked^{d}(W_{i}, wblock)

    then
     beginthen

wlast := wlast ∪W_{i}

dblock := ∅ {** Similar use as wblock **} For dlength = n to 1 do (3) For all subsets D_{i} of D of cardinality dlength do (4)

        begin

dlast := ∅ {** Similar use as wlast **}

If not Blocked^{d}(D_{i}, dblock) (5)

         then
          beginthen

dlast := dlast ∪D_{i}

If (D_{i}, W_{i}) is consistent with IC

            then
             beginthen

temp^{d} := temp^{d} ∪(D_{i}, W_{i})

dblock := dblock ∪D_{i} wblock := wblock ∪W_{i}

             endthen
          endthen

od (4)

If dlast = ∅ then EXIT

od (3)

     endthen

od (2) If wlast = ∅ then EXIT {** If all subsets of W of cardinality wlength are blocked then STOP**} od (1) NewMAXCONS1^{d}(Δ, IC) := temp^{d}.

Figure 6: Computing d-Maximally Consistent Subsets Efficiently The following two results are proved in the same way as the analogous results for s-maximal consistency.

Theorem 4 MAXCONS^{d}(Δ, IC) = NewMAXCONS1^{d}(Δ, IC). □

Theorem 5 For any integer n, there exists a propositional default theory Δ of cardinality n such that cardinality of MAXCONS^{s}(Δ, IC) is O(2^{n}).

4 Combining Default Theories

In the previous section, we have described techniques and algorithms for characterizing the semantics of a single default theory that contains inconsistencies. In this section, we will study two possible ways of combining multiple knowledge bases that are represented by default theories. Intuitively, the idea is the following: we have a set Δ_{1} = (D_{1}, W_{1}), …, Δ_{n} = (D_{n}, W_{n}) of default theories, and a set, IC, of integrity constraints. Recall that IC is simply a consistent set of first-order formulas. We would like to retain as much information from (D_{1} ∪⋯∪ D_{n} , W_{1} ∪⋯∪ W_{n}) as possible without violating the integrity constraints. The two methods we study reflect two possible ways of achieving this goal.

Since the semantics of default theories described in the previous section takes into the account the s-maximal (or d-maximal) subsets of the theory, we can view an inconsistent default theory as a set of its s-maximal (or d-maximal) subsets. The following definition makes it more precise.

Definition 8 (Flock) A flock (a term borrowed from [5]) is a set of default theories. The s-flock (resp. d-flock) corresponding to an inconsistent default theory Δ is the set of s-maximal (resp. d-maximal) consistent subsets of Δ.

Definition 9 (Relation between flocks) Let F_{1} and F_{2} be flocks. We say that:

1. F_{1} ⪯_{s} F_{2} iff (∀Δ ∈ F_{1})(∃Δ′ ∈ F_{2}) : Δ ⪯_{s} Δ′.

2. F_{1} ⪯_{d} F_{2} iff (∀Δ ∈ F_{1})(∃Δ′ ∈ F_{2}) : Δ ⪯_{d} Δ′.

The following properties of flocks will be used in the definition of combining function.

Definition 10 (Consistency) A flock F is said to be consistent with respect to a set of integrity constraints IC, iff, for every default theory Δ = (D, W) ∈ F, (D, W ∪ IC) is consistent.

Definition 11 (Correctness) A default theory Δ = (D, W) is said to be ⪯_{s}-correct with respect to default theories Δ_{1}, ⋯, Δ_{k}, if {Δ} ⪯_{s} {Δ_{1} ∪ ⋯ ∪ Δ_{k}}. ^{4} ⪯_{d}-correctness is defined similarly.

4We use the notation Δ_{1} ∪⋯∪Δ_{k} as shorthand to denote the default theory (D_{1} ∪⋯∪D_{k}, W_{1} ∪⋯∪W_{k})

The following definition specifies some desirable properties that any reasonable way of combining multiple knowledge bases must possess.

Definition 12 (Combination function) Let Δ_{1}, ⋯, Δ_{k} be a set of default theories and IC a set of integrity constraints such that each Δ_{i} is consistent with IC. C is an scombination (resp. d-combination) function if its domain is a collection of pairs (flock, integrity constraints), its range is the set of flocks, and it satisfies the following properties:

1. (Identity) C({Δ}, IC) = Δ.

2. (Consistency) C({Δ_{1}, ⋯, Δ_{k}}, IC) is consistent with respect to IC.

3. (Correctness) C({Δ_{1}, ⋯, Δ_{k}}, IC) is ⪯_{s}-correct (resp. ⪯_{d}-correct) with respect to the default theories Δ_{1}, ⋯, Δ_{k}.

4. (Commutativity) C({Δ_{1}, ..., Δ_{k}}, IC) = C({Δ_{i_{1}}, ..., Δ_{i_{k}}}, IC) where for all j, l = 1, ..k, 1 ≤ i_{j} ≤ k and i_{j} ≠ i_{l}.

Intuitively, the identity requirement says that when we are working only with a single default theory that is already consistent with the integrity constraints, then the combination function should not allow any modifications to occur. The consistency condition specifies that the flock generated by the combination function should only consist of default logic theories that are consistent with the integrity constraints. Finally, the correctness condition insists that the flock generated by the combination function should not be “too informative”

– everything in it must have been in one of the theories being combined. The commutativity condition specifies that the order of the theories to be combined is not important.

We now proceed to define two combination functions. In the rest of the paper, we will only discuss s-combinations, as the analogous concepts for d-combinations follow immediately in a symmetric fashion. The two combination functions we define are skeptical in nature. Intuitively, the first combination function constructs the union of the default theories being considered and then looks at the maximal consistent subsets of this union that also satisfy the integrity constraints.

Definition 13 Suppose Δ_{1}, ⋯, Δ_{k} is a set of default theories where Δ_{i} = (D_{i}, W_{i}), 1 ≤ i ≤ n, and IC is a set of integrity constraints. Furthermore, assume that each Δ_{i}, 1 ≤ i ≤ k, is consistent with IC. We define

Comb_{1}({Δ_{1}, ⋯, Δ_{k}}, IC) = MAXCONS^{s}((D_{1} ∪ ⋯ ∪ D_{k}, W_{1} ∪ ⋯ ∪ W_{k}), IC).

Theorem 6 Comb_{1} is a combination function, i.e. it satisfies the identity, consistency and correctness criteria. Furthermore, Comb_{1} is associative.

Proof. Straightforward verification of the axioms. □

Example 8 (The Robot Example Revisited) If we reconsider the robot example, Comb_{1}({Δ_{1}, Δ_{2}, Δ_{3}}, IC) contains three elements in it. The first says that do action1(t_{0}) should be performed, the second says that do action2(t_{0}) should be performed, while the third says that take safety action(t_{0}) should be performed.

The second combination function constructs the union of the default theories, and then finds its maximal consistent subsets without, for the time being, considering the integrity constraints. Having found these maximally consistent subsets, it looks at each of them in turn, and finds maximal consistent subsets of the previously found maximally consistent subsets which are consistent with IC.

Given a set of default theories Δ_{i} = (D_{i}, W_{i}), 1 ≤ i ≤ n, and a set of integrity constraints IC, one might define Comb_{2}({Δ_{1}, ⋯, Δ_{k}}, IC) as the set of maximal elements of {Δ_{X} | Δ_{X} ∈ MAXCONS^{s}((D′_{i}, W′_{i}), IC) where (D′_{i}, W′_{i}) ∈ MAXCONS^{s}(Δ_{1} ∪ ⋯ ∪ Δ_{k}, IC)}. However, Comb_{2} may not be a combination function at all because the identity property is not satisfied. To see this, consider the following example:

Example 9 Let

Δ_{1} = (\{ \frac{: ¬a}{a}\}, \{b\})

Let IC = {a}. Note that Δ_{1} is consistent with IC (even though Δ_{1} is inconsistent by itself).

It turns out that Comb_{2}({Δ_{1}}, IC) = {(D_{2}, W_{2}} where D_{2} = ∅ and W_{2} = {b}.

This result is related to the nonmonotonicity of default theories. While in classical logic, if a theory has a model then all its subsets have models, this is not necessarily the case in default logic: it may happen, as in Example 8, that a default theory has an extension, while its subsets do not have one.

5 Prioritized Combination of Default Theories

If we look carefully at the robot example, the knowledge (represented in KB_{3}) provided by the expert on the overall operations of the plant must be preferred to the knowledge (in KB_{2}) provided by the expert on component 2. The reason is that the expert on overall plant operations looks at the global picture (represented by pressure readings, temperature readings and smoke levels), whereas the expert on component 2 is concerned primarily with the behaviour of component 2, as opposed to the situation in the entire plant. Hence, under circumstances such as these, it is useful to have a priority ordering on the different knowledge bases. The priority ordering reflects our degree of confidence in the information provided by different experts.

Technically, suppose we have a set {Δ_{1}, ⋯, Δ_{k}} of default theories, and a set IC of integrity constraints. Let us assume first that this set is totally ordered as

Δ_{1} ≺ Δ_{2} ≺ ⋯ ≺ Δ_{k}.

Intuitively, Δ_{i} ≺ Δ_{j} means that Δ_{j} has greater priority than Δ_{i}. As always, the integrity constraints have the highest priority, i.e. Δ_{k} ≺ IC.

Suppose we have only two theories, Δ_{1} and Δ_{2} where Δ_{1} ⪯ Δ_{2}. We would like to use the combination function Comb_{1} defined in the previous section to combine theories, while giving higher priority to Δ_{2}. The intuition is to let Δ_{2} play the role of the integrity Algorithm 7 Procedure Comb − botup(Comb_{1}, Δ_{1} ⪯ ⋯ ⪯ Δ_{k}, IC) Comb = {Δ_{1}} For i = 1 to k do begin

Temp = ∅

For all Δ in Comb do

Temp = Temp ∪ Comb_{1}({Δ, Δ_{i+1}}, Δ_{i+1}) Comb = maximal elements of Temp

end Comb’=Comb_{2}(Comb, (∅, IC)) Output(Comb’)

Figure 7: Bottom-up Combination of Default Theories

constraints (in addition to being one of the theories to be combined) in the combination process. Thus, the default theories in the result of the combination will be “consistent” with Δ_{2}. However, until now we have assumed that IC is a first order logic theory, and we need to extend our definition of consistency to the case of the integrity constraints being a default theory. The following definition will be used in the rest of the section.

Definition 14 A default theory Δ = (D, W) is said to be consistent w.r.t Δ_{IC} = (D_{IC}, W_{IC}) iff (D ∪ D_{IC}, W ∪ W_{IC}) is consistent.

Using the new definition, we can combine the above Δ_{1} and Δ_{2} with a priority to Δ_{2} by Comb_{1}({Δ_{1}, Δ_{2}}, Δ_{2}) where Comb_{1}({Δ_{1}, ⋯, Δ_{k}}, IC) = MAXCONS^{s}(Δ_{1} ∪⋯∪Δ_{k}, IC) If Δ_{2} is consistent, all the theories in the combination will include Δ_{2}.

If there are more than two theories, Δ_{1} ≺ Δ_{2} ≺ ⋯ ≺ Δ_{k}, to be combined, then there are two distinct approaches to combining the default theories that immediately come to mind: bottom-up and top-down. The bottom-up algorithm, Algorithm 7, appears in Figure 6.

In the bottom-up approach we start by combining Δ_{1} and Δ_{2} with preference to Δ_{2}. The combined default theory is then a set of default theories as defined above (i.e., as Comb_{1}({Δ_{1}, Δ_{2}}, Δ_{2}). The result is then combined with Δ_{3} with preference to Δ_{3}. This means that each default theory in the result is combined with Δ_{3}, and the final result is the set which is the union of particular results (each result is a set). This continues until Δ_{k}. The result is then combined by itself with respect to the IC.

There can be other variations of this algorithm. For example, one can ensure that after each combination step the results are consistent with respect to the IC constraints. It is easy to show that the results of the two variants may be different.

In the top-down approach, we start by combining Δ_{k} and IC with preference to IC. The result is combined with Δ_{k−1} with preference to the default theories in the result. This is continued until Δ_{1} is processed. Then, we remove the IC from the results.

Algorithm 8 Procedure Comb − topdn(Comb_{1}, Δ_{1} ⪯ ⋯ ⪯ Δ_{k}, IC) Δ_{k+1} = IC Comb = {Δ_{k+1}} For i = k to 1 do begin

Temp = ∅

For all Δ in Comb do

Temp = Temp ∪ Comb_{1}({Δ_{i}, Δ}, Δ) Comb = maximal elements of Temp

end Comb′ = {(D, W \ IC)|(D, W) ∈ Comb} Output(Comb’)

Figure 8: Top-down Combination of Default Theories

In [2], we showed that combining first order theories bottom-up may not always lead to the same results as a top-down combination. As first order logic is a special case of default logic (by setting the D part of any default theory to ∅), it follows that in general, top-down and bottom-up combinations may not be the same for default logic either.

The bottom-up approach is similar to updating. We start with the a KB Δ_{1} and update it using new information Δ_{2} obtaining a new KB Δ_{1,2}. While updating we assume that the information in Δ_{2} is more up-to-date than that of Δ_{1}. When additional new information Δ_{3} arrives, we update the previous KB, i.e., Δ_{1,2}, giving higher priority to Δ_{3} the more recent information. That is, the resulting theory of the bottom-up approach reflects the order that the information arrived, giving higher priority to more recent information. However, it doesn’t consider old conflict resolution decisions that were made in previous steps, given the recent information.

The top-down approach is closer to our intuition about combining, when all information is already available. We start with the KB with the highest priority. The conflicts in lower priority theories will be resolved in the light of all information with higher priority. No information will be lost for historical reasons.

We now explain both approaches using a simple example.

Example 10 Consider the theories Δ_{1}, Δ_{2}, Δ_{3} and the set IC of integrity constraints given below: The priority ordering we have is Δ_{1} ≺ Δ_{2} ≺ Δ_{3} ≺ IC.

Δ_{1} = (∅, {b(opus)}) Δ_{2} = (\{\frac{b(X) : ¬ab(X)}{f(X)}\}, \{¬ab(opus), ¬f(opus)\}) Δ_{3} = (∅, {f(opus)}) IC = ∅ The theory Δ_{1} tells us that “opus is a bird” and Δ_{2} tells us that “normally birds fly”, “opus is normal” and “opus does not fly”. The theory Δ_{3} tells us that “opus flies”.

Combining the theories top-down proceeds as follows: combining Δ_{3} and Δ_{2}, we obtain

Δ_{32} = ((\{\frac{b(X) : ¬ab(X)}{f(X)}\}, \{¬ab(opus), f(opus)\})

and combining Δ_{32} and Δ_{1} we obtain

Δ_{321} = ((\{\frac{b(X) : ¬ab(X)}{f(X)}\}, \{b(opus), ¬ab(opus), f(opus)\})

Combining the theories bottom-up proceeds as follows: combining Δ_{1} and Δ_{2} we obtain {Δ_{12}} where

Δ_{12} = ((\{\frac{b(X) : ¬ab(X)}{f(X)}\}, \{¬ab(opus), ¬f(opus)\}).

Combining Δ_{12} and Δ_{3} we obtain

Δ_{123} = ((\{\frac{b(X) : ¬ab(X)}{f(X)}\}, \{¬ab(opus), f(opus)\})

Therefore that the bottom-up and top-down approaches yield different answers. Note that were we to delete the default in Δ_{2}, then the above three default theories could be viewed as first order theories (as all of them would have no defaults in them); even though [2] show that bottom-up and top-down combinations of first order theories may lead to different results, in this case, they lead to the same result, given by the set {b(opus), ¬ab(opus), f(opus)}. Therefore it is the inclusion of defaults that causes the top-down and bottom-up approaches to yield different answers in this case.

□

There are situations where the theories to be combined are only partially ordered. For example, it is possible that we have prioritized groups of default theories G_{1}, …, G_{n}. Any two default theories in the same group have the same priority; however, the groups themselves have priorities G_{1} ≺ G_{2} ≺ ⋯ ≺ G_{n}. This situation may arise when there is a partial hierarchy in an organization. For example, suppose there is a company which includes programmers, department managers, and managers. Each worker in the company provides a report on the situation of the company. There is no priority among each group members, e.g., we don’t prefer one programmer over the other, but it is assumed that the department managers are more knowledgeable on the company’s situation than the programmers and the managers are more knowledgeable than the members of the two other groups.

The most straightforward way to combine the resulting multitude of default theories is given in Algorithm 9. The intuition behind this algorithm is as follows. In the first step all default theories in a given group G_{i} 1 ≤ i ≤ n are combined with no priorities and the resulting default theories is denoted by S_{i}. Then, we combine any combination of s_{1}, ..., s_{n} of n default theories, where s_{i} ∈ S_{i} 1 ≤ i ≤ n. This combination is done with the priority s_{1} ≺ s_{2} ≺ ⋯ ≺ s_{n}.

Our algorithms, 7,8 and 9 can be extended to be used in the combination of any partially ordered default theories. For example, if we have Δ_{1} ≺ Δ_{2} and Δ_{3} ≺ Δ_{4}, then we can Algorithm 9 Prioritized Combination

1. For all 1 ≤ i ≤ n, set S_{i} = Comb_{1}(G_{i}, IC).

(** Thus, at this stage, for any 1 ≤ i ≤ n, all default theories in the group G_{i} have been combined together. Each S_{i} is thus a set of default theories. **)

2. Construct S = (S_{1} × ⋯ × S_{n})

(** i.e. S is the Cartesian product of the S_{i}’s.**)

3. Let S = {V_{1}, …, V_{k}} where each V_{i} is of the form ⟨s_{1}, …, s_{n}⟩ where s_{j} ∈ S_{j} for all 1 ≤ j ≤ n.

4. Combine default theories s_{1}, …, s_{n} with priorities s_{1} ≺ s_{2} ≺ ⋯ ≺ s_{n}.

Do this for all V_{i} ∈ S.

Let the resulting default theories be {T H_{1} …, T H_{k}}.

5. Choose the maximal elements of {T H_{1} …, T H_{k}}.

Figure 9: Combining prioritized groups of default theories

combine with priorities (using, for example Algorithm 7) Δ_{1} and Δ_{2} denote the result by S_{1} and combine with priorities Δ_{3} and Δ_{4} and denote the results by S_{2}. Then the elements of S_{1} and S_{2} should be combined without priorities. That is, we do steps 2-5 of Algorithm 9, when the combination in step 4 is done without priorities.

6 Discussion and Conclusions

We have concentrated in this paper on default logics based on Reiter’s approach. This work can be extended in two directions.

First, several restricted versions of Reiter’s default logic have been studied in the literature. For example, a normal default theory has only normal defaults, which have the form \frac{α:β}{β}. Reiter [14] shows that normal default theories are coherent. i.e. they always have at least one extension. The union of normal theories is also a normal theory. Since normal theories are always coherent, inconsistency can only arise because of classical inconsistency in the W part of the default theory. Hence the definitions of s- and d-maximality coincide, and the algorithm to obtain the maximal consistent subsets need only look at the W part of the theory. This algorithm can easily be constructed by simplifying Algorithm 6

Second, one can consider extending the present approach to alternate formalizations of non-monotonic reasoning, such as auto-epistemic theories with respect to expansions, normal logic programs with respect to stable models, and nonmonotonic modal theories with respect to expansions. (Equivalence between these theories with respect to suitable translations have been proved in the literature [11, 7].)

In the case of normal logic programs, consistency coincides with coherence. In other words, if a stable model exists it is always classically consistent. Like Reiter’s default theories, auto-epistemic theories and nonmonotonic modal theories can be both incoherent and classically inconsistent. But they do not have two different parts as in default theories. One way to proceed would be to consider sentences having the modal operator as the default part, and sentences without modal operators as the classical part. This distinction can then be used to define s- and d-maximality.

Finally, we conclude with some meta-remarks concerning our approach. First, note that our notion of s (and d) - maximality is syntax-dependent. In other words, two default theories with syntactically different first-order parts but with identical models (i.e. semantically equivalent), may behave differently when combined with another theory, as illustrated by the following example suggested by an anonymous reviewer.

Example 11 Let Δ_{1} = (W_{1}, ∅) with W_{1} = {a, b, c} and Δ_{2} = (W_{2}, ∅) with W_{2} = {a, a → b, b → c}. It is easy to see that Δ_{1} and Δ_{2} have the same models. Let us consider individually combining Δ_{1} and Δ_{2} with Δ = ({¬c}, ∅).

Δ_{1} ∪ Δ has two maximal consistent subsets {a, b, c} and {a, b, ¬c}, and entails a, while Δ_{2}∪Δ has four maximal consistent subsets, {a, a → b, b → c}, {a, a → b, ¬c}, {a, b → c, ¬c}, {a → b, b → c, ¬c}, and does not entail a. □

Our approach is based on the premise that when we are combining theories which may come from different experts, we need to stay with the syntax. In the above example it is possible that Δ_{1} and Δ_{2} are obtained from combining theories, and hence we treat them differently even though they have the same models.

Second, the general question we tried to answer in this paper is “What is the result of combining a set of knowledge bases represented as default theories in presence of integrity constraints?”

This can be answered either directly, by suggesting an operator that computes the combined knowledge base, or indirectly, by giving a set of axioms or postulates that is satisfied by each reasonable combination operator.

In this paper we follow the first approach, presenting ways to compute the combined knowledge base. Our approach is similar to the solution of the database update problem by Fagin et al. [5] (which is also a syntax dependent approach). The second approach is similar to the solution of the database update problem in [6], where several postulates that should be satisfied by any update operator are given. We do partially follow the second approach in suggesting that any reasonable combination operator should satisfy the identity, consistency and correctness criteria.

Revesz [15] considers the combination^{5} of propositional theories (without integrity constraints) as a special case of model fitting. He presents several postulates for model fitting and also provides a model theoretic characterization of combination.

5He refers to it as arbitration.

References

[1] C. Baral, S. Kraus and J. Minker. (1991) Combining Multiple Knowledge Bases, IEEE Trans. on Knowledge and Data Engineering, 3, 2, pps 200-220.

[2] C. Baral, S. Kraus, J. Minker and V.S. Subrahmanian. (1992) Combining Knowledge Bases Consisting of First Order Theories, Computational Intelligence, 8, 1, pps 45–71.

[3] H. A. Blair and V.S. Subrahmanian. (1989) Paraconsistent Logic Programming, Theoretical Computer Science, 68, pp 35-54. Preliminary version in: LNCS 287, Dec. 1987, Springer.

[4] D. Etherington. Reasoning with Incomplete Information. Morgan Kaufmann Publishers, California.

[5] R. Fagin, G. Kuper, J. Ullman, and M. Vardi. Updating logical databases. In Advances in Computing Research, pages 1–18, 1986.

[6] P. Gardenfors. Knowledge in Flux: Modelling the dynamics of epistemic states. Bradford Books,MIT Press, Cambridge, MA 1988.

[7] M. Gelfond and V. Lifschitz. The Stable Model Semantics for Logic Programming. In R.A. Kowalski and K.A. Bowen, editors, Proc. 5^{th} International Conference and Symposium on Logic Programming, pages 1070–1080, Seattle, Washington, August 15-19, 1988.

[8] G.. Gottlob. Complexity results for nonmonotonic reasoning J. of Logic and Computation 2(3):397–425, 1992 (Also, Tech Report 91/24. Technische Universitat Wien, Vienna, Austria, August, 1991.)

[9] J. Grant and V.S. Subrahmanian. (1994) Reasoning About Inconsistent Knowledge Bases, accepted for publication in: IEEE Transactions on Knowledge and Data Engineering.

[10] M. Kifer and E. Lozinskii. (1989) RI: A Logic for Reasoning with Inconsistency, 4-th Symposium on Logic in Computer Science, Asilomar, CA, pp. 253-262. Full version to appear in: Journal of Automated Reasoning.

[11] W. Marek and M. Truszczynski. Relating autoepistemic and default logics. Technical Report, Department of Computer Science, University of Kentucky at Lexington, 1989.

[12] S. Pradhan, J. Minker and V.S. Subrahmanian. (1993) Combining Databases with Prioritized Information, accepted for publication in: Journal of Intelligent Information Systems.

[13] N. Rescher and R. Brandom. (1979) The Logic of Inconsistency, Rowman & Littlefield, 1979.

[14] Raymond Reiter. A logic for default reasoning. Artificial Intelligence, 13:81–132, 1980.

[15] Peter Revesz. On the semantics of Theory Change: Arbitration between old and new information. Proceedings of PODS 93, 71- 82, 1993.

Appendix I

The robot example may be expressed in default logic as follows: Robot Observations: Δ_{obs} = (D_{obs}, W_{obs}) D_{obs} = ∅ W_{obs} = {:

temperature(875, t_{0}) ←
pressure(400, t_{0}) ←
smoke level(117, t_{0}) ←
malfunctioning(component1, t_{0}) ←
malfunctioning(component2, t_{0}) ←

}

Expert 1: Δ_{1} = (D_{1}, ∅)

D_{1}:

\frac{pressure(X,T) & X≤200 : ok(component1,T)}{ok(component1,T)}

\frac{do action1(T) : pressure(200,T +1)}{pressure(200,T +1)}

\frac{pressure(X,T) & X>200 : do action1(T)}{do action1(T)}

Expert 2: Δ_{2} = (D_{2}, ∅)

D_{2}:

\frac{temperature(T emp,T)) & T emp≤800 : ok(component21,T)}{ok(component21,T)}

\frac{do action2(T) : temperature(775,T +1)}{temperature(775,T +1)}

\frac{temperature(T emp,T) & T emp>800 : do action2(T)}{do action2(T)}

Expert 3: Δ_{3} = (D_{3}, W_{3})

W_{3}:

danger(high, T) ← pressure(P, T) & P ≥ 200  (16)
temperature(T emp, T) & T ≥ 800
smoke level(S, T) & S ≥ 100.
danger(zero, T + 1) ← take safety action(T)  (17)

D_{3}:

\frac{danger(high,T) : take safety action(T)}{take safety action(T)}

Integrity Constraints

do action1(T) ∨ do action2(T) ∨ take safety action(T) ← danger(high, T) (18)

¬do action1(T) ∨ ¬do action2(T)  (19)

¬do action1(T) ∨ ¬take safety action(T)  (20)

¬take safety action(T) ∨ ¬do action2(T)  (21)

The last three axioms specify that only one action can be taken at a time when we have only the three actions that are mentioned.