Combining Knowledge Bases Consisting of First Order Theories

Chitta Baral, Sarit Kraus, Jack Minker and V. S. Subrahmanian Department of Computer Science

and

University of Maryland Institute for Advanced Computer Studies University of Maryland College Park, MD 20742, U.S.A.

Abstract

Consider the construction of an expert system by encoding the knowledge of different experts. Suppose the knowledge provided by each expert is encoded into a knowledge base. Then the process of combining the knowledge of these different experts is an important and non-trivial problem. We study this problem here when the expert systems are considered to be first order theories. We present techniques for resolving inconsistencies in such knowledge bases. We also provide algorithms for implementing these techniques.

1 Introduction

Consider the construction of an expert system by encoding the knowledge of different experts. Suppose the knowledge provided by each expert is encoded into a knowledge base. Then the process of combining the knowledge of these different experts is an important and non-trivial problem.

The problem is important because the user of the expert system so constructed should have access to the knowledge of each of the experts. In particular, he/she should be able to use the knowledge of two different experts to jointly derive a fact that neither of the experts, individually, knew. In other words, one important feature involved in consulting multiple experts is to pool their knowledge together and thus obtain knowledge that no individual expert previously had.

The problem is non-trivial because individual experts can, and often do, hold conflicting views on their domain of expertise. Two attorneys involved in a legal defense may well hold conflicting views on the best possible defense strategy, just as two doctors may well differ in their assessment of a patient’s malady. In a logic knowledge base, these conflicting opinions manifest themselves in the form of inconsistencies. Classical logic would then indicate that the resulting knowledge base is meaningless – a state of affairs that is clearly inappropriate in this context. Just as the attorneys and doctors would work together to reconcile their views in the interests of the defendant or patient, so should a knowledge base management system reconcile these inconsistencies and allow sensible decisions to be drawn. The key problem here is: how should these inconsistencies be reconciled? This is the problem addressed in this paper.

Baral, Kraus and Minker [BKM89] formalize the notion of combining knowledge bases when each knowledge base is a normal Horn logic program (set of rules with only atoms allowed in the head) and assume that the union of the knowledge bases is stratified (no recursion through negation). They assume the presence of world knowledge in the form of integrity constraints, which all the individual knowledge bases satisfy, and the combined knowledge base is required to satisfy. They present methods to obtain a maximally combined knowledge base with respect to the union of knowledge bases that is consistent with respect to the integrity constraints. Since they consider each knowledge base to be a normal Horn logic program the union of the knowledge bases is always consistent and the combined knowledge base they obtain is maximal with respect to it.

In this paper we consider each knowledge base as a first order theory. All knowledge are expressed in the same underlying logical language^{1} . The set of integrity constraints is also assumed to be a first order theory. In this case the union of the knowledge bases is not necessarily consistent. Because of this, in the absence of integrity constraints, to have the combined knowledge base as the union of the knowledge bases, we need a semantics for inconsistent theories. Many such semantics have been suggested in the past [BS89, BS88, dCSV89, Gra74, Gra75, Gra77, Gra78, Sub89, GL, KS]. In this paper we use the cautious approach of Grant and Subrahmanian [GS90] to characterize the semantics of inconsistent theories. In the cautious approach the semantics of an inconsistent theory is the semantics obtained by considering all maximally consistent subsets of the inconsistent theory. A sentence is considered \underline{true} (\underline{false}) if it is \underline{true} (\underline{false}) in all maximally consistent subsets of the original theory.

In the next section, we will present a scenario which will be used throughout the paper to illustrate the basic intuitions behind our technical development. In section 3 of the paper, we discuss the cautious semantics of inconsistent theories in the presence of integrity constraints. In the subsequent section we formalize combining a set of theories having the same priority, in the presence of integrity constraints and its relationship with view update approaches [FKUV86, FUV83]. We then allow the theories to be prioritized and formalize the notion of combining a set of prioritized theories.

2 A Motivating Scenario

Inconsistencies can easily arise when multiple reasoning agents each arrive at a particular view of the world. While these individual views are usually self-consistent, they often tend to conflict with one another. We now present a simple scenario which we will use over and over again to motivate the basic ideas in the paper.

The Scenario: At 1:00 AM on January 14, 1990, Don was shot outside the Good Times Bar in Washington. The street was more or less deserted (it being late in the night) except for four people: Don (who got shot), the murderer, and two rather drunk individuals, John and Bill, who were on the street. John is an eighty-five year old man who was about 100 yards away from the shooting, while Bill is thirty years old. Bill was about 75 yards away from the shooting. Their stories are the following:

1Baral, Kraus and Minker [BKM90] present methods to translate between knowledge bases expressed in different logical languages.

John’s Story:

1. The murderer wore an orange coat.

2. The murderer wore no hat.

3. He knows the murderer got away in a car (as he heard the engine revving up and the car taking off), but he was hiding in a doorway and was too scared to look, and hence cannot tell us anything about the car.

Bill’s Story:

1. The murderer wore a dark (probably black) coat.

2. The murderer wore no hat.

3. The murderer drove off in a pink Mercedes.

If we look at John’s story and Bill’s story, they are self-consistent. If Bill had not been around, we would probably have accepted John’s version of the story (and viceversa). However, their stories conflict with each other (if we make the reasonable assumption that the murderer wore only one coat). This assumption has the status of an integrity constraint: for the purposes of the story, it is a statement all parties are willing to accept.

Integrity Constraints:

1. The murderer wore only one coat at the time of the murder.

2. Based on other evidence, the police present a convincing case that the murderer knew the victim well.

3. Don’s close cronies are Jeff, Ed and Tom.

4. There is no evidence that any of these three individuals had either borrowed or bought a coat recently; so the only coats they could have worn were their own.

5. Both Jeff and Ed have pink Mercedes. Tom doesn’t know how to drive.

6. Jeff has an orange coat.

7. Ed has a black coat.

8. there is no possibility of any collusion between Jeff and Ed.

Based on the above story, we are led to suspect Ed or Jeff, but not both. Only one of them was the murderer. If we accept John’s story, then Jeff is the murderer. If we accept Bill’s story, then Ed is the murderer.

We are faced with the following problem: who did it ? There are numerous alternatives:

Alternative 1: In a court of law, the guilt of a person must be established beyond ALL reasonable doubt. This cannot be established in this case. For example, if Jeff is on trial for the murder of Don, then a reasonable doubt can be cast on his guilt by the defense. A similar situation would occur if Ed was on trial. This situation corresponds to the case where one views each and every possibility in the correctness of the witnesses’ statements. We accept a person as guilty iff he/she turns out to be guilty in in all these different possible worlds. Thus, according to alternative 1, we can conclude that Jeff or Ed is guilty, but we can neither prove that Jeff is guilty nor can we prove that Ed is guilty.

Alternative 2: We may be led to doubt the correctness of John’s statements. After all, he is eighty-five years old, as compared to Bill’s thirty years, and hence, presumably, Bill’s eyesight is better. Furthermore, Bill was much closer to the scene of the crime, and hence, one may feel that his evidence is more credible. In deciding who to prosecute (Ed or Jeff), the police may well decide that they can make a more compelling case against Ed based on Bill’s evidence. This alternative corresponds to the assignment of a priority to Bill’s evidence, rather than to John.

Alternative 3: The third alternative is to simply conclude that the evidence is inconsistent and to use the semantics of classical logic to conclude everything.

These are only three possible scenarios. Each of these represents a reasonable way of reasoning about the body of evidence in front of us. We will illustrate the technical development of the paper by frequent reference to this example.

3 Cautious Semantics for Inconsistent Theories

We consider a theory to be a set of well-formed formulas. Unless explicitly mentioned otherwise, theories will always be assumed to be finite. Several semantics for inconsistent theories have been discussed in [GS90]. One of the approaches to characterize an inconsistent theory is to consider the maximally consistent subsets of the inconsistent theory. A maximally consistent subset of an inconsistent theory T is a theory which is a consistent subset of T, and which becomes inconsistent if any other sentence of T is added to it. Intuitively, each maximally consistent subset of T corresponds to a consistent state of the world T is trying to characterize. 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 (some call it skeptical) and consider all of them. Hence, in the cautious characterization of inconsistent theories, the truth value of a sentence L corresponds to the intuition: “Is L true w.r.t. each and every maximally consistent state of affairs ?”. Maximal consistent subsets correspond to the normal default theories [R80, Eth88] and the cautious and bold approaches are similar to the characterizations of default theories based on truth in all its extensions, and truth in a particular extension respectively due to [Eth88].

Consider a theory T whose maximal consistent subsets are T_{1}, …, T_{n}. In the presence of integrity constraints (world knowledge which every theory has to satisfy) we have to consider only those worlds that are consistent with respect to the integrity constraints. The bold approach of doing this would be to consider only those T_{i}’s, 1 ≤ i ≤ n, that satisfy the integrity constraints. Thus, maximal consistent subsets of T that do not satisfy the integrity constraints would be discarded. The cautious approach, on the other hand, would look at each T_{i}, 1 ≤ i ≤ n and then find maximal subsets of T_{i} that are consistent with the integrity constraints. An example may clarify this point:

Example 3.1 Suppose our theory T consists of the following sentences:

1) p → q

2) p → ¬q

3) r

4) p

T has three maximally consistent sets:

T_{1} = {1, 2, 3} T_{2} = {1, 3, 4} T_{3} = {2, 3, 4}

Suppose we have as an integrity constraint the single formula ¬(r & p). T_{1} satisfies IC, but neither T_{2} nor T_{3} do. Thus, the “bold” approach would discard T_{2} and T_{3} and select T_{1}.

The cautious approach would also pick T_{1}, but it would not discard T_{2} and T_{3}. It would, instead, try to find maximal consistent subsets of T_{2} and T_{3} that satisfy the integrity constraint. In the case of each of T_{2}, T_{3}, this is achieved by discarding 4). Hence, the cautious approach would look at the three sets:

T_{1} T_{4} = {1, 3} (obtained by discarding 4) from T_{2}) T_{5} = {2, 3} (obtained by discarding 4) from T_{3}) □

Example 3.2 With respect to the murder example described in the previous section, the cautious semantics would accept the conclusion “X is the murderer” iff X was the murderer irrespective of whether we chose to believe John or Bill. Thus, according to the cautious semantics, there would be no such individual X. However, the cautious semantics would allow us to conclude the sentence “Either Ed is the murderer or Jeff is the murderer” because this follows irrespective of whether we believe John or Bill. □

In the following definitions MAXCONS(P) and MAXCONS(P, IC) are maximal consistent subsets of P and maximal consistent subsets of P with priority to IC. By, maximal consistent subsets of P with priority to IC we mean maximal consistent subsets of P ∪ IC, which contain all elements of IC.

Definition 3.1 (Maximal Consistency) Let P be a theory and IC be a set of integrity constraints. A subset Q ⊆ P is said to be maximally consistent with priority to IC iff Q ∪ IC is consistent, and for every theory Q′ such that Q ⊂ Q′ ⊆ P, it is the case that Q′ ∪ IC is inconsistent. MAXCONS(P, IC) is the set of maximally consistent subsets of P with priority to IC. When IC is an empty set then MAXCONS(P, IC) is called MAXCONS(P) and is the set of maximally consistent subsets of P.

Theorem 1 below shows that all theories possess at least one maximal consistent subset with respect to any consistent set of integrity constraints.

Theorem 1 Suppose P is any (possibly infinite) first order theory and IC is any consistent set of integrity constraints. Then P ∪ IC has at least one (possibly infinite) maximally consistent subset P′ such that IC ⊆ P′. (If P is finite, then its maximal consistent subsets are obviously finite).

Proof. P ∪ IC has at least one consistent subset that is a superset of IC, viz. IC itself. Thus, let CONS(P, IC) denote the set {X|X ⊆ P ∪IC and X is consistent and IC ⊆ X}, and let CONS(P) be defined as CONS(P, ∅). Thus, CONS(P, IC) ≠ ∅ because IC ∈ CONS(P, IC). We show below that every ascending chain of elements in CONS(P) has an upper bound in CONS(P). The result then follows from Zorn’s Lemma.

Suppose M_{1} ⊆ M_{2} ⊆ M_{3} ⊆ ⋯ is an ascending sequence of members of CONS(P), i.e. each M_{i} is a consistent subset of P ∪ IC and IC ⊆ M_{i}. Then M = ⋃_{i=1}^{∞} M_{i} is an upper bound for this ascending sequence. Moreover, M is consistent, IC ⊆ M and M ⊆ P ∪ IC, i.e. M ∈ CONS(P). The only non-obvious part is the consistency of M.

To see this, suppose M is not consistent. Then, by the Compactness Theorem, there is a finite subset M′ ⊆ M such that M′ is inconsistent. Let M′ = {γ_{1}, …, γ_{n}} for some integer n. Hence, for each 1 ≤ i ≤ n, there is an integer, denoted α_{i} such that γ_{i} ∈ M_{α(i)}. Let α = max{α(1) …, α(n)}. Then M′ ⊆ M_{α}. Hence, as M′ is inconsistent, M_{α} is also inconsistent, thus contradicting our assumption that each M_{j}, j ≥ 1, is in CONS(P). □

A weaker version of the above theorem has been established by Grant and Subrahmanian [GS90] (cf. Corollary 3.1 below). An important point to note about MAXCONS(P) is that it depends upon the syntactic nature of P. For instance, if we take P_{1} = {a, b, ¬a} and P_{2} = {(a&b), ¬a}, then MAXCONS(P_{1}) = {{a, b}, {¬a, b}} and so it is perfectly reasonable to cautiously conclude b from P_{1}. On the other hand, MAXCONS(P_{2}) = {{(a & b)}, {¬a}} from which we cannot cautiously conclude b. Even though the theory {(a&b)} is logically equivalent to the theory {a, b} according to classical logic, this equivalence does not hold when we treat inconsistent theories non-classically. The following corollary of Theorem 1 shows that all theories have at least one maximally consistent subset. Corollary 3.1 [GS90] Every theory P has at least one maximally consistent subset. Proof. Take IC to be the empty set in the proof of Theorem 1. □ We now define a notion of entailment based on the cautious approach. Definition 3.2 (⊢_{∀}-Entailment) [GS90] Suppose P is a theory, and F is a formula. A notion of entailment, ⊢_{∀} based on the cautious approach is defined as follows: P ⊢_{∀} F iff P′ ⊧ F for every maximal consistent subset P′ ⊆ P. We now state some basic properties of ⊢_{∀}-entailment. Theorem 2 [GS90] Suppose P is a theory, and L, L_{1}, L_{2} are ground literals. Then:

1. for all ground literals L, it is not the case that P ⊢_{∀} L and P ⊢_{∀} ¬L.

2. P ⊢_{∀} (L_{1} & L_{2}) iff P ⊢_{∀} L_{1} and P ⊢_{∀} L_{2}.

3. P ⊢_{∀} F for all tautologies F of classical logic. □ Example 3.3 Let P be:

p ∨ ¬q
¬p ∨ ¬q
r
q

In this case, MAXCONS(P) consists of three elements: {p ∨ ¬q ; r; q }, {¬p ∨ ¬q ; r; q }, {p ∨ ¬q ; ¬p ∨ ¬q ; r }. In this case, P ⊢_{∀} r. But P ⊬_{∀} q and P ⊬_{∀} p and P ⊬_{∀} ¬q and P ⊬_{∀} ¬p. □

The appendix contains algorithms that compute MAXCONS(P) and MAXCONS(P, IC). The algorithms assume that the theories have a finite Herbrand Base. Function-free databases satisfy this condition. It is possible to determine the Herbrand-consistency of function-free databases. A database is Herbrand consistent iff it has an Herbrand model. Note that Herbrand consistent databases are always consistent in the usual sense of logic, though the converse is not necessarily true. However, it has become a standard practice in the deductive database (or “Datalog”) community to consider Herbrand consistency instead of ordinary first order logical consistency. Throughout the rest of this paper, we will use the word “consistent” to refer to Herbrand consistency.

When an inconsistent theory P consists of n sentences, the algorithm MAXCONS1(P) given in the appendix (Algorithm 6.1), constructs its maximal consistent subsets by determining the consistency of each subset of P of cardinality n − 1. All such consistent subsets are stored in a set S. For each inconsistent subset, its maximal consistent subsets are added to S. The set of maximal elements of S is MAXCONS(P). The algorithm MAXCONS1(P, IC), which is also in the appendix (Algorithm 6.2), extends MAXCONS1(P) by allowing integrity constraints to be present. MAXCONS1(P, IC) tests the consistency of the union of IC with each subset of P and designates some of these subsets as being maximally consistent with respect to IC.

Theorem 3 below proves that algorithm MAXCONS1(P) correctly computes the maximal consistent subsets of P.

Theorem 3 MAXCONS(P) = MAXCONS1(P)

Proof: [MAXCONS(P) ⊆ MAXCONS1(P)] Suppose X ∈ MAXCONS(P). Then X = P − {C_{1}, …, C_{r}} for some integer r ≥ 0 where {C_{1}, …, C_{r}} ⊆ P. We proceed by induction on r.

Base Case. (r = 0) In this case MAXCONS(P) = {P } = MAXCONS1(P).

Inductive Case. (r = k + 1) Consider P′ = P − {C_{k+1}}. Then X is a maximal consistent subset of P′ and furthermore, X = P′ − {C_{1}, …, C_{k}}. Therefore, by the induction hypothesis, X ∈ MAXCONS1(P′). As X ∪ {C_{k+1}} is inconsistent, X is in MAXCONS1(P).

[MAXCONS1(P) ⊆ MAXCONS(P)] Similar. □

The following theorem demonstrates that algorithm MAXCONS1(P, IC) correctly computes the maximal consistent subsets of P with respect to integrity constraints IC.

Theorem 4 MAXCONS(P, IC) = MAXCONS1(P, IC)

Proof: Proceeds along exactly the same lines as the proof of Theorem 3. □

Returning to the motivating murder example in Section 2, if we take P to be the union of John’s evidence and Bill’s evidence, then MAXCONS(P, IC) consists of two theories T_{1} and T_{2}. T_{1} contains:

1. all integrity constraints and

2. sentences 1,2, 3 of John’s story and sentences 2, 3 of Bill’s story.

Likewise, T_{2} contains:

1. all integrity constraints and

2. sentences 2 and 3 of John’s story and sentences 1,2, 3 of Bill’s story.

Thus, using the MAXCONS(P, IC) semantics, we may conclude that the murderer wore no hat (this being true in both T_{1} and T_{2} above). However, we may not conclude anything about the color of the murderer’s coat. We may also conclude that the murderer drove away in a pink Mercedes.

We now discuss a technique for computing MAXCONS(P) in cases when P is a finite set of clauses (a clause is a disjunction of literals). Throughout the rest of this section, we consider only sets of clauses.

Definition 3.3 (Refutations) Suppose T is a consistent set of clauses and D is a clause such that T ∪ {D} is inconsistent. A refutation of D from T is a sequence C_{1}, …, C_{n} such that:

1. C_{n} is the empty clause □ and

2. each C_{i}, 1 ≤ i ≤ n is either in T ∪ {D} or is a resolvent of two clauses C, C′ ∈ T ∪ {D} ∪ {C_{1}, …, C_{i−1}}.

C_{1}, …, C_{n} is called a minimal refutation of D from T if there is no strict subsequence of C_{1}, …, C_{n} which is also a refutation of D from T, i.e. there is no sequence D_{1}, …, D_{m} such that {D_{1}, …, D_{m}} ⊂ {C_{1}, …, C_{n}} and if D_{i} = C_{j} and D_{i+1} = C_{k}, then j < k.

Definition 3.4 (Potential Causes) Suppose T is a consistent set of clauses and D is a clause such that T ∪ {D} is inconsistent. Let ℜ be some minimal refutation of D from T. Then the set ℜ ∩ T is said to be a potential cause of D.

Example 3.4 Suppose T is the following set of clauses:

C1: a ∨ b C2: a ∨ ¬b C3: a ∨ c C4: a ∨ ¬c

and D ≡ ¬a. There are two minimal refutations ℜ_{1} and ℜ_{2} of D from T where:

ℜ_{1} = C1, C2, a, D, □
ℜ_{2} = C3, C4, a, D, □

(Actually a few more minimal refutations may be obtained by re-arranging the occurrences of some of the clauses in ℜ_{1}, ℜ_{2}). Thus the potential causes of D are: P C_{1} = {C1, C2, } and P C_{2} = {C3, C4} corresponding to ℜ_{1}, ℜ_{2} respectively. □

In the context of the murder scenario outlined in Section 2, there is only one potential cause of the inconsistency, viz. the following three sentences:

1. John: The murderer wore an orange coat.

2. Bill: The murderer wore a black coat.

3. IC: The murderer wore only one coat at the time of the murder.

If T is itself inconsistent, we may talk of refutations of the empty clause, □, from T. This refers simply to different refutations of □ from T. In this case, each minimal refutation of T gives rise to a potential cause of the inconsistency of T, viz. the potential cause of □ w.r.t. the refutation we are currently considering. Given theorem T, MINS(T) is the set of minimal (w.r.t. inclusion) potential causes of the inconsistency of T.

Algorithm MAXCONS2, which is given in the appendix (Algorithm 6.3), presents a different way of computing maximal consistent subsets of P. It performs this computation by identifying potential causes of inconsistencies and deleting some of them. In the remaining Lemma and Theorems of this section, any unexplained notation will refer to the notation used in the MAXCONS2 algorithm.

Theorem 5 below shows that algorithm MAXCONS2 correctly computes maximal consistent subsets of P. We first prove Lemma 3.1 and then use it to prove Theorem 5. Lemma 3.1 shows that when we remove a minimal potential cause of an inconsistency from P, then the remaining theory is consistent.

Lemma 3.1 Suppose P is a set of clauses and Z ∈ MINS(P). Then (P − Z) is consistent.

Proof. Suppose (P − Z) is inconsistent. Then there is a minimal refutation of (P − Z). Let z_{1}, …, z_{m} be the members of (P − Z) (and hence of P) occurring in this refutation. Therefore, there exists an 1 ≤ i ≤ n such that S_{i} = {z_{1}, …, z_{m}}. But then, as Z ∈ MINS, there must exist a 1 ≤ j ≤ m such that z_{j} ∈ Z. This implies that z_{j} ∉ (P − Z); a contradiction. □

Theorem 5 MAXCONS(P) = MAXCONS2(P)

Proof: [MAXCONS(P) ⊆ MAXCONS2(P)] Suppose X ∈ MAXCONS(P). It suffices to show that (P − X) ∈ MINS. To do this, we need to show two things.

I. First we show that (P −X) ∩ S_{i} ≠ ∅ for all 1 ≤ i ≤ n. Suppose (P −X) ∩ S_{i} = ∅ for some 1 ≤ i ≤ n. Then S_{i} ⊆ X which contradicts the assumption that X is consistent.

II. Next, we show that (P − X) is a minimal element of S′ w.r.t. inclusion. Suppose not. Then there is a Z ∈ MINS such that Z ⊂ (P − X). In particular, there exists an a ∈ (P − X) − Z. But then, by Lemma 3.1, (P − Z) would be a consistent subset of P. But X ⊂ (P − Z) thus contradicting the maximality of X.

[MAXCONS2(P) ⊆ MAXCONS(P)] Suppose X ∈ MAXCONS2(P). Let S_{1}, …, S_{n} be all the potential causes of the inconsistency of P. If n = 0, then X = P ∈ MAXCONS2(P).

So assume n > 0. Then X = (P − Y) where Y = {a_{1}, …, a_{n}} and for all 1 ≤ i ≤ n, a_{i} ∈ S_{i} and Y ∈ MINS.

Claim 1: X is consistent. Proof of Claim 1: Suppose not. Then there exists an 1 ≤ i ≤ n such that S_{i} ⊆ X. In addition, a_{i} ∈ S_{i}. But a_{i} ∉ X because X = (P − Y). But this contradicts the statement that S_{i} ⊆ X.

Claim 2: X is maximally consistent. Proof of Claim 2: Suppose not, i.e. there exists a maximal consistent X′ such that X ⊂ X′ ⊆ P. let X = (P − Y) and X′ = (P − Y′). As X ⊂ X′, Y′ ⊂ Y. As X′ is a maximal consistent subset of P, by the [MAXCONS(P) ⊆ MAXCONS2(P)] part of the proof, X′ ∈ MAXCONS2(P). Thus, Y′ ∈ MINS. But Y ∈ MINS also. But this is a contradiction because Y′ ⊂ Y. □

Algorithm MAXCONS2(P, IC) which is also in the appendix (Algorithm 6.4), extends MAXCONS2(P) to the case when integrity constraints are present. The theorem below establishes that MAXCONS2(P, IC) correctly computes the maximal consistent subsets of P with respect to integrity constraints IC.

Theorem 6 MAXCONS(P, IC) = MAXCONS2(P, IC)

Proof: Similar to the proof of Theorem 5. □

We now prove some results on the complexity of cautious entailment for propositional theories.

Theorem 7 For any n, there exists a propositional theory T of cardinality n such that cardinality of MAXCONS(T) is O(2^{n}).

Proof: For any value of n consider the theory T_{n} = {a_{1}, ¬a_{1}, ⋯, a_{n}, ¬a_{n}}. It can be easily proved that the cardinality of MAXCONS(T_{n}) is 2^{n}. □

In order to place complexity results in context, we reiterate the following result due to Plaisted and Vardi.

Theorem 8 (Plaisted [Pl84], Vardi [Va82]) The Herbrand satisfiability problem for clause form formulas is EXPTIME-complete.

An immediate corollary is the following:

Corollary 3.2 The problem: Given (as input) finite sets T and T′ of function free wffs such that T ⊆ T′, determining whether T is a maximal consistent subset of T′ is EXPTIME-hard.

Hence, the problem of combining multiple theories seems to be one for which algorithms tend to be exponential in nature.

4 Combining General Theories

The problem of combining general theories is formalized as follows. We have a set of consistent theories and a set of integrity constraints^{2}. Each theory satisfies the integrity constraints. We would like to combine the given set of theories so that the combined theory is also consistent with respect to the integrity constraints and contains as much consistent information as possible.

The combination of several theories often leads to a multiplicity of resulting theories. Hence, we need to set up a mechanism to work with sets of theories.

Definition 4.1 (Flock) A flock (a term borrowed from [FKUV86]) is a set of theories. The flock corresponding to a theory T is a set of subtheories of T.

Usually, when we consider an inconsistent theory T, the flock of interest is the flock of all maximal consistent subsets of T. In order to define combinations of theories, we need to specify the properties that combination functions must satisfy.

Definition 4.2 (Relation between flocks) Let F_{1} and F_{2} be flocks. F_{1} ≤_{1} F_{2} iff (∀T ∈ F_{1})(∃T′ ∈ F_{2}) : T ⊆ T′.^{3}

Definition 4.3 (Consistency) A flock F is said to be consistent with respect to a set of integrity constraints IC, iff for every theory T present in F, T ∪IC is consistent. □ Definition 4.4 (Correctness) A flock F is said to be ≤_{1}-correct with respect to theories T_{1}, ⋯, T_{k}, if F ≤_{1} MAXCONS(T_{1} ∪ ⋯ ∪ T_{k}). ≤_{2}-correctness is defined analogously. □

2Throughout this paper, we assume that whenever we are combining theories T_{1}, …, T_{n} and w.r.t. the set IC of integrity constraints, then each T_{i}, 1 ≤ i ≤ n, is consistent. Note however that different T_{i}, T_{j} may be mutually inconsistent for 1 ≤ i, j ≤ n, i ≠ j.

3Many other orderings between flocks can also be defined. One such ordering is defined as:

F_{1} ≤_{2} F_{2} iff (∀T ∈ F_{1})(∃T′ ∈ F_{2}) : Cn(T) ⊆ Cn(T′), where Cn(T) is the set of classical logic consequences of T.

Using the properties of consistency and correctness defined above, we now present the concept of combination functions.

Definition 4.5 (Combination of Theories) Let T_{1}, ⋯, T_{k} be a set of theories and IC a set of integrity constraints; where each T_{i} satisfies IC. A combination function C is a mapping from a set of theories and a set of integrity constraints into a flock satisfying the following three criteria. 1.(identity) C({T }, IC) = {T }. 2.(consistency) C({T_{1}, ⋯, T_{k}}, IC) is consistent with respect to IC. 3.(correctness) C({T_{1}, ⋯, T_{k}}, IC) is ≤_{1}-correct with respect to the theories T_{1}, ⋯, T_{k}.

Another useful property is associativity, which is defined as follows. C({T_{1}, ⋯, T_{j}, C({T_{j+1}, ⋯, T_{k}}, IC)}, IC) =_{mm} C({C({T_{1}, ⋯, T_{j}}, IC), T_{j+1}, ⋯, T_{k}}, IC) =_{mm} C({T_{1}, ⋯, T_{k}}, IC); where P =_{mm} Q means Cn(P) = Cn(Q). □

We now define three combination functions. The first two are skeptical in nature. The first combination function takes the union of the theories and the integrity constraints and looks at the maximal consistent subsets of this union with priority to the integrity constraints. More formally,

Definition 4.6 Comb_{1}({T_{1}, ⋯, T_{k}}, IC) =^{def} MAXCONS(T_{1} ∪ ⋯ ∪ T_{k}, IC).

We now show that Comb_{1} is a valid combination function.

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

Note that the combination function Comb_{1} takes the union of theories T_{1}, …, T_{k} and then finds the maximal subsets that are consistent with the integrity constraints,IC. We now apply Comb_{1} to the murder example.

Example 4.1 (Murder Example on Comb_{1}) Returning to the murder example. In this case, Comb_{1} would take the two witness accounts (John and Bill) as two theories. Let us consider John’s three statements to constitute theory T_{1} and Bill’s three statements to constitute theory T_{2}. In addition the set of eight integrity constraints is denoted IC. Comb_{1} would try to identify maximal subsets of T_{1} ∪ T_{2} that are consistent with IC. There would be two maximal consistent subsets, and the flock Comb_{1}({T_{1}, T_{2}}, IC) would consist of these two sets. The difference between the two is that one of these maximal sets contains the statement “The murderer wore an orange coat” (this set would tend to implicate Jeff as the murderer) while the other contains the statement “The murderer wore a dark coat” (this set would implicate Ed). □

The second combination function takes the union of the theories and finds its maximal consistent subsets. It then looks at all the theories in MAXCONS(Y_{i}, IC) for all Y_{i} ∈ MAXCONS(T_{1} ∪ ⋯ ∪ T_{k}).

Definition 4.7 Comb_{2}({T_{1}, ⋯, T_{k}}, IC) =^{def} maximal elements of S, where S = {X : X ∈ MAXCONS(Y_{i}, IC) where Y_{i} ∈ MAXCONS(T_{1} ∪ ⋯ ∪ T_{k})}.

The following example illustrates the two approaches.

Example 4.2 Let the union of the theories T be: a b c ¬a ∨ ¬b and the set of integrity constraints be IC = {¬a ∨ ¬c} MAXCONS(T, IC) = {{a, b}, {a, ¬a ∨ ¬b}, {b, c, ¬a ∨ ¬b}} MAXCONS(T) = {T_{1} = {a, b, c}, T_{2} = {a, c, ¬a ∨ ¬b}, T_{3} = {b, c, ¬a ∨ ¬b}} MAXCONS(T_{1}, IC) = {{a, b}, {c, b}} MAXCONS(T_{2}, IC) = {{a, ¬a ∨ ¬b}, {c, ¬a ∨ ¬b} } MAXCONS(T_{3}, IC) = {{b, c, ¬a ∨ ¬b}} Hence, in this example MAXCONS(T, IC) = maximal members of the set ⋃_{T_{i}∈MAXCONS(T)} MAXCONS(T_{i}, IC). a ∨ b is true in all models of members of MAXCONS(T, IC) and hence it is true with respect to the combination of these theories. □

We now use the murder example to illustrate the behavior of Comb_{2}.

Example 4.3 (Murder Example on Comb_{2}) To see how Comb_{2} behaves w.r.t. the murder scenario of Section 2, Comb_{2} would first construct MAXCONS(P) where P is the union of John’s story and Bill’s story. Note that P is perfectly consistent and hence MAXCONS(P) = {P }. (The fact that the murderer wore only one coat at the time of the murder is necessary for the inconsistency to arise). Comb_{2} now computes the maximal elements of {X | X ∈ MAXCONS(Y_{i}, IC) where Y_{i} ∈ MAXCONS(P)}. In this case, this leads to exactly the same results as Comb_{1}. □

That these two seemingly different combination functions lead to the same results is not an accident – as shown in the following theorem.

Theorem 10 MAXCONS(T, IC) = maximal members of the set S: where, S = {X : X ∈ MAXCONS(T_{i}, IC) where T_{i} ∈ MAXCONS(T)}

Proof: ⇒ Let X ∈ MAXCONS(T, IC). Then there exists a Y in MAXCONS(T) such that:

(1) X ∩ T ⊆ Y and (2) X ∈ MAXCONS(Y, IC) Consider such a Y. Suppose X ∉ MAXCONS(Y, IC). Since, X ∪ IC is consistent, this means that there is an X′ such that X ⊂ X′, and such that X′ ∈ MAXCONS(Y, IC), but then our assumption that X ∈ MAXCONS(T, IC) is contradicted. Hence, X ∈ MAXCONS(Y, IC). This proves that X ∈ S. Since, X ∈ MAXCONS(T, IC), it has to be a maximal member of S.

⇐ Suppose X is a maximal element of S. Then there is a T_{i} ∈ MAXCONS(T) such that X ∈ MAXCONS(T_{i}, IC) and Y such that X ⊂ Y and Y ∈ MAXCONS(T_{j}, IC) for some T_{j} ∈ MAXCONS(T). This implies that X is consistent (note that by definition of MAXCONS, IC ⊆ X and so X is consistent w.r.t. IC).

Suppose X ∉ MAXCONS(T, IC). Then there is an α such that X ⊂ α and α ∈ MAXCONS(T, IC). By the first part of the theorem, this means, that α ∈ MAXCONS(T_{j}, IC), for some T_{j} ∈ MAXCONS(T). This violates our initial assumption about X, which says that no such T_{j} exists. A contradiction. Hence, X ∈ MAXCONS(T, IC). □

Corollary 4.1 Comb_{2} is an associative combination function. □

The third function uses a bold approach. Here we consider any maximal consistent subset of the union of the given theories, which satisfy the Integrity Constraints. It is defined as follows.

Definition 4.8 Comb_{3}({T_{1}, ⋯, T_{k}}, IC) =^{def} {X : X ∈ MAXCONS(T_{1} ∪ ⋯ ∪

T_{k}) and X ∪ IC is consistent. }

Considering Example 4.2, we have MAXCONS(T) = {T_{1} = {a, b, c}, T_{2} = {a, c, ¬a ∨ ¬b}, T_{3} = {b, c, ¬a ∨ ¬b}} Of the three theories in MAXCONS(T) only T_{3} is consistent with respect to IC = {¬a ∨ ¬c}. Hence, the third approach considers only T_{3}.

Unlike Comb_{1} and Comb_{2}, Comb_{3} is not associative.

Theorem 11 Comb_{3} is a non associative combination function. □

The proof that Comb_{3} is a combination function is a simple verification of the three conditions that a combination function must satisfy. The example below demonstrates the non-associative nature of Comb_{3}.

Example 4.4 Consider the theories T_{1}, T_{2}, T_{3} and the set IC of integrity constraints shown below:

T_{1} = {(a ∨ b), c} T_{2} = {¬a} T_{3} = {a, ¬c} IC = {¬b}

In this case, combining T_{1} and T_{2} first and then combining the result with T_{3} yields a flock consisting of one set only:

C(C({T_{1}, T_{2}}, IC), IC) = {{¬a}}.

However, combining T_{2} and T_{3} first and then combining the result with T_{1} yields a flock containing three sets:

C({T_{1}, C({T_{2}, T_{3}}, IC)}, IC)

= {{(a ∨ b), a, c} ,

{(a ∨ b), a, ¬c},
{c, ¬a}}.

This shows that combining the theories T_{1}, T_{2}, T_{3} in different orders leads to different results. □

One may wonder what the relationship between combining theories using Comb_{1} and using Comb_{3} is. The theorem below shows that Comb_{3} may be viewed as a “bolder” combination strategy than Comb_{1}.

Theorem 12 Let {T_{1}, …, T_{k}} be a flock and IC a set of integrity constraints. Then:

Comb_{3}({T_{1}, …, T_{k}}, IC) ⊆ Comb_{1}({T_{1}, …, T_{k}}, IC).

Proof. Suppose T ∈ Comb_{3}({T_{1}, …, T_{k}}, IC). Then T ∈ MAXCONS(T_{1} ∪⋯∪T_{k}) and T ∪ IC is consistent. Consequently, T ∈ MAXCONS(T_{1} ∪⋯∪ T_{k}, IC). Hence, T ∈ Comb_{1}({T_{1}, …, T_{k}}, IC). □

The distinction between Comb_{1} and Comb_{3} may be further illustrated by the following example:

Example 4.5 Consider the theories T_{1}, T_{2} and the set of integrity constraints IC shown below:

T_{1} = {(a ∨ b), (¬a ∨ c)} T_{2} = {¬b} IC = {¬c}

In this case, Comb_{1}({T_{1}, T_{2}}, IC) consists of the following three theories:

{¬c, (a ∨ b), (¬a ∨ c)} {¬c, (a ∨ b), ¬b} {¬c, (¬a ∨ c), ¬b}

On the other hand, Comb_{3}({T_{1}, T_{2}}, IC) is the empty flock. □

Comb_{3}, when applied to the murder example, yields a different result than Comb_{1} and Comb_{2}.

Example 4.6 (Murder Example w.r.t. Comb_{3}) Using Comb_{3}, the murder example would result in the empty flock. This is because the union of John’s story and Bill’s story is consistent; however, the union is no longer consistent with IC and hence is rejected by Comb_{3}. □

The salient difference between Comb_{3} and Comb_{1} (and hence also Comb_{2}) is that the former:

• is non-associative and

• is bolder than Comb_{1} as it picks a subset of the set of theories picked by Comb_{1}

The non-associativity of Comb_{3} restricts the applicability of Comb_{3} to situations where we want to combine theories according to a particular ordering. Such a situation may arise, for instance, if all theories are ranked, and we always combine them starting from the lowest rank upwards. On the other hand, it appears to be easier, in practice, to compute Comb_{3} than it is to compute Comb_{1}. In the case of Comb_{3}, we simply check if the maximally consistent subsets of T_{1} ∪ ⋯ ∪ T_{k} are consistent with the integrity constraints. Let Y_{1}, …, Y_{m} be these maximal consistent subsets. Those Y_{i}’s, 1 ≤ i ≤ m that are not consistent with IC are discarded. The remainder are retained. In the case of Comb_{2}, however, we would first (as before) find the maximal consistent subsets Y_{1}, …, Y_{m} of T_{1} ∪⋯∪ T_{k}. We would then try to find maximal subsets of each of the Y_{i}’s that are consistent with IC. This is more time-consuming and laborious operation than simply checking if the Y_{i}’s are consistent with IC. Thus, we would recommend that in time-critical situations, Comb_{3} could be first computed and this could give a quick “forecast” of the results. If time remains to do a more detailed analysis, then Comb_{1} could be used.

4.1 A More Practical Approach

In all the previous combination functions we searched for all the maximally consistent subsets of the inconsistent theories. This is an extremely time consuming process since it requires consistency checks in each step of the algorithm (Algorithm 6.2). In this section we would like to present a more practical algorithm.

In addition we are motivated by the following argument. We are combining several theories. Each of them is consistent and the inconsistency arose from the union of the theories and we do not know which of the theories being combined contains erroneous information. We would like to search for a combination that will include as much information as possible from the original theories. By “as much”, we mean as many clauses as possible, i.e. theories that are maximal w.r.t. cardinality rather than with respect to inclusion.

The algorithm MAXCONS3 given in the appendix (Algorithm 6.5) serves both purposes.

Definition 4.9 Comb_{4}({T_{1}, ⋯, T_{k}}, IC) =^{def} MAXCONS3(T_{1} ∪ ⋯ ∪ T_{k}, IC).

The intuitive motivation behind Comb_{4} is that “everytime we discard something, we are (implicitly) saying that the discarded object constitutes a mistake made by the expert. As this information is obtained from experts, it seems appropriate to assume that they don’t make too many mistakes; hence we want to pick those maximal consistent subsets where the number of mistakes is minimized.” Comb_{4} thus seems to be suitable in situations where it is appropriate to make this assumption.

The theorem below shows that Comb_{4} is bolder than Comb_{1}.

Theorem 13 Comb_{4}({T_{1}, ⋯, T_{k}}, IC) = maximal sets WRT cardinality of Comb_{1}({T_{1}, ⋯, T_{k}}, IC).

Comb_{4} coincides with Comb_{1} on the murder example. The following example illustrates the difference between this approach and the MAXCONS(P) approach.

Example 4.7 Consider the theory P below:

d ¬d d → e d → ¬e

MAXCONS3(P) contains exactly one element, viz. {¬d, d → e, d → ¬e}. Note, however, that in addition to this set, MAXCONS(P) contains {d, d → e}, {d, d → ¬e}, {¬d, d → ¬e}, {d, d → ¬e}, {d, d → e}, {¬d, d → e}. □

The following result is easy to establish.

Corollary 4.2 Let P be any first order theory. MAXCONS3(P) ⊆ MAXCON(P). □

We note that the inferences of MAXCONS3 are less cautious and more optimistic than those MAXCONS, i.e. everything that is inferred from MAXCONS is also inferred from MAXCONS3, but there is more information that is inferred from MAXCONS3 than from MAXCONS. A straightforward verification demonstrates that Comb_{4} is a combination function.

Theorem 14 1. Comb_{4} is a combination function.

2. Furthermore, for all theories T_{1}, …, T_{n} and any set IC of integrity constraints, Comb_{4}({T_{1}, …, T_{n}}, IC) ⊆ Comb_{1}({T_{1}, …, T_{n}}, IC).

An important point to note is that there is no obvious “subset-like” relationship of the sort proved in Theorem 14 that links Comb_{3} and Comb_{4}. The following two examples confirm this. Example 4.8 shows that it may not always be the case that Comb_{3}({T_{1}, T_{2}}, IC) ⊆ Comb_{4}({T_{1}, T_{2}}, IC) and Example 4.9 demonstrates that the reverse inclusion does not hold either.

Example 4.8 Suppose T_{1}, T_{2}, IC are as given below:

T_{1} = {(a ∨ b), ¬b} T_{2} = {¬a, (b ∨ c)} IC = {¬c}

In this case, MAXCONS(T_{1} ∪ T_{2}) = {{(a ∨ b), ¬b, (b ∨ c)}, {(a ∨ b), ¬a, (b ∨

Figure 1: Subset Relationships of Different Combination Functions

c)}, {¬b, ¬a, (b ∨ c)}}. Of these, only the first set in MAXCONS(T_{1} ∪ T_{2}) is consistent with IC; hence, Comb_{3}({T_{1}, T_{2}}, IC) = {(a ∨ b), ¬b, (b ∨ c)}}.

On the other hand, Comb_{1}({T_{1}, T_{2}}, IC) = {{(a ∨ b), ¬b, (b ∨ c)}, {(a ∨ b), ¬a}, {(a ∨ b), (b ∨ c)}, {¬a, (b ∨ c)}}. Of these, only one set is of maximal cardinality, viz. the first set, and hence Comb_{4}({T_{1}, T_{2}}, IC) = {{(a ∨ b), ¬b, (b ∨ c)}}.

Thus, in this case, Comb_{3}({T_{1}, T_{2}}, IC) ⊈ Comb_{4}({T_{1}, T_{2}}, IC). □

Example 4.9 Suppose T_{1}, T_{2}, IC are as given below:

T_{1} = {(a ∨ b)} T_{2} = {¬a} IC = {¬b}

In this case, Comb_{3}({T_{1}, T_{2}}, IC) = ∅ whereas Comb_{4}({T_{1}, T_{2}}, IC) = {{(a∨b)}, {¬a}}.

Thus, this example demonstrates that Comb_{4}({T_{1}, T_{2}}, IC) may not be a subset of Comb_{3}({T_{1}, T_{2}}, IC). □

We say combination function Comb_{i} is a subset of Comb_{j}, denoted Comb_{i} ⊆ Comb_{j}, iff for all theories T_{1}, …, T_{n} and integrity constraints IC, it is the case that

Comb_{i}({T_{1}, …, T_{n}}, IC) ⊆ Comb_{j}({T_{1}, …, T_{n}}, IC).

Figure 1 shows the complete “subset” relationships between the four different combination functions we have defined so far. All subset relationships are shown in Fig. 1; the absence of a subset relationship means it does not hold.

From the point of view of ease of implementation, we believe that Comb_{1} and Comb_{2} are the hardest to implement, while Comb_{3} and Comb_{4} are relatively easier to implement. Suppose T_{1}, …, T_{n} are first order theories and IC is a set of integrity constraints. In the case of Comb_{3}, we find the maximal consistent subsets of (T_{1} ∪⋯∪T_{n}) and then simply delete those that violate the integrity constraints.

In the case of Comb_{2} and hence of Comb_{1}), we need to perform some additional work. those maximal consistent subsets that are not deleted when computing Comb_{3} must be further examined: suppose Y_{i} is one such maximally consistent subset of (T_{1} ∪ ⋯ ∪ T_{n}) that violates IC. Then we need to find maximal subsets of Y_{i} that are consistent with IC. This may involve a great deal of additional work.

Implementing Comb_{4} is different. We compute maximally consistent subsets of (T_{1} ∪ ⋯ ∪ T_{n} ∪ IC) that contain IC. It is easy to see that this is of the same order of complexity as computing the maximal consistent subsets of (T_{1} ∪ ⋯ ∪ T_{n}). We then simply retain those maximal subsets that are of the greatest cardinality. A detailed discussion of the complexity of these problems, however, is beyond the scope of the paper.

4.2 Relationship with Updating of Theories

The problem of updating theories and revising beliefs has been extensively studied [FUV83, FKUV86, Gar88, Dal88, KM89, GM88, Sat88]. In brief, an update may take one of two forms:

1. An Insertion: In this, some new information is added to T.

2. A Deletion: Here, either a formula F in T is deleted, or a formula entailed by T is deleted.

Inserting a formula F into T may lead to an inconsistency. In this case, the result of the insertion must be defined in such a way that the inconsistency is properly handled. Deletions do not give rise to inconsistencies (unless T was already inconsistent).

There is some resemblance between insertions and the combination of theories we have discussed earlier. Insertions into theories may be viewed as a special case of our framework: take the sentence F to be inserted to be an integrity constraint, i.e. IC = {F } and now compute MAXCONS(T, IC). This is the gist of Theorem 16 below.

One may wonder whether combining theory T_{1} with theory T_{2} may be accomplished by inserting each element of T_{2} into T_{1}. This is not true in general (cf.

Example 4.10 below). The reason for this is that we do not have any priorities over the set of the combined theories.^{4} For example when we insert elements of T_{2} into T_{1} one by one, then the last element of T_{2} to be inserted is accorded the status of an integrity constraint, even though this last element of T_{2} may not be present in all maximal consistent subsets of T_{1} ∪ T_{2}.

Fagin, Ullman and Vardi [FUV83] present a theory of updating theories. Before discussing the relationship between updating and combining we discuss the theory updating approach of Fagin, Ullman and Vardi [FUV83].

Definition 4.10 (Insertion and Deletion) [FUV83] Let T be a theory and T ∗ be the set of clauses logically implied by T. A theory S is said to accomplish the insertion of a clause σ into T if σ ∈ S. A theory S is said to accomplish the deletion of a clause σ into T if σ ∉ S∗.

Definition 4.11 [FUV83] Let T, T_{1} and T_{2} be theories. T_{1} has fewer insertions than T_{2}, if T_{1} − T ⊂ T_{2} − T. T_{1} has no more insertions than T_{2}, with respect to T, if T_{1}−T ⊆ T_{2}−T. T_{1} has the same insertions as T_{2}, with respect to T, if T_{1}−T = T_{2}−T Let T, T_{1} and T_{2} be theories. T_{1} has fewer deletions than T_{2}, if T − T_{1} ⊂ T − T_{2}. T_{1} has no more deletions than T_{2}, with respect to T, if T − T_{1} ⊆ T − T_{2}. T_{1} has the same deletions as T_{2}, with respect to T, if T − T_{1} ⊆ T − T_{2}.

Definition 4.12 [FUV83] Let T, T_{1} and T_{2} be theories. T_{1} accomplishes an update u (could be an insertion or a deletion) of T with a smaller change than T_{2} if both T_{1} and T_{2} accomplish u, and either T_{1} has fewer deletions than T_{2} or T_{1} has the same deletions as T_{2} but T_{1} has fewer insertions than T_{2}.

Definition 4.13 Minimal Updating [FUV83] A theory S accomplishes an update u of a theory T minimally if there is no theory S′ that accomplishes u with a smaller change than S.

In the following theorem Fagin et al. [FUV83] present a different characterization of minimal updating of theories. This new characterization can be used to construct algorithms that can minimally update a theory.

4Using Gärdenfors’ terminology, our combination functions do not satisfy axiom K_{2}^{+} ([Gar88] page 48)

Theorem 15 [FUV83] Let S and T be theories and let σ be a sentence. Then,

1. S accomplishes the deletion of σ from T minimally if and only if S is a maximal subset of T that is consistent with ¬σ, and

2. S accomplishes the insertion of σ from T minimally if and only if S ∩ T is a maximal subset of T that is consistent with σ. □

The following theorem describes a relationship between combining theories and updating theories, when the union of the theories to be combined is consistent.

Theorem 16 Let T_{1}, ⋯, T_{k} be theories to be combined in the presence of a finite set IC of integrity constraints. Let σ_{ic} be the conjunction of the integrity constraints in IC. If T_{1} ∪ ⋯ ∪ T_{k} is consistent then, Comb_{1}({T_{1}, ⋯, T_{k}}, {σ_{ic}}) = { X|X accomplishes the insertion of σ_{ic} into T_{1} ∪ ⋯ ∪ T_{k} minimally. } □

Proof: [Comb_{1}({T_{1}, ⋯, T_{k}}, σ_{ic}) ⊆ {X|X accomplishes the insertion of σ_{ic} into T_{1} ∪ ⋯ ∪ T_{k} minimally }] Suppose X ∈ Comb_{1}({T_{1}, ⋯, T_{k}}, σ_{ic}). Then X is a maximally consistent set such that {σ_{ic}} ⊆ X ⊆ T_{1} ∪ ⋯ ∪ T_{k} ∪ {σ_{ic}}. Hence, σ_{ic} ∈ X. It now suffices to show that X is a maximally consistent subset of T_{1} ∪ ⋯ T_{k} ∪ {σ_{ic}}. But this is true. Hence X ∈ {X|X accomplishes the insertion of σ_{ic} into T_{1} ∪ ⋯ ∪ T_{k} minimally }.

[{X|X accomplishes the insertion of σ_{ic} into T_{1}∪⋯∪T_{k} minimally } ⊆ Comb_{1}({T_{1}, ⋯, T_{k}}, σ_{ic})] The proof is similar. □

Theorem 16 above demonstrates that the Fagin et. al. [FKUV86] framework for inserting sentences into theories may be captured in our framework. The example below shows that successive insertions of sentences of theory T_{2} into theory T_{1} does not correctly capture the combination of theories.

Example 4.10 Suppose T_{1} = { a → c, a → ¬b, a → b},

and T_{2} = {a}. Inserting a into T_{1} gives us two sets that accomplish this insertion: S_{1} = { a a → c a → ¬b}

and S_{2} = { a a → c a → b}

c is true in both S_{1} and S_{2}. Note however, that according to MAXCONS(T_{1} ∪ T_{2}), c is not true in T_{1} which is a maximally consistent subset of T_{1} ∪ T_{2}. □

We now the use of the theory developed by Fagin et al. [FKUV86] for updates in flocks to compare with our problem of combining theories.

Definition 4.14 Minimal Flock Updating [FKUV86] Let S = {S_{1}, ⋯, S_{n}} be a flock. A flock T = {T_{1}, ⋯, T_{n}} accomplishes an update u of S minimally if T_{i} accomplishes the update of S_{i} minimally. □

Fagin et al. [FKUV86] defined the updating of a flock as follows:

Definition 4.15 [FKUV86] Let S be a flock and S_{1}, ⋯, S_{k} be the flocks that accomplish an update u of S minimally. Then the result of u is the flock ⋃_{1≤i≤k} S_{i}. □

We would like to change Definition 4.15 so that the resulting flock consists of maximal elements only. Formally,

Definition 4.16 Let S be a flock and S_{1}, ⋯, S_{k} be the flocks that accomplish an update u of S minimally. Then the result of u is the flock consisting maximal elements of ⋃_{1≤i≤k} S_{i}. □

The following result relating combining theories with updating flocks of theories is immediate. It uses the modified definition of updating a flock as defined in Definition 4.16.

Theorem 17 Let T_{1}, ⋯, T_{k} be a set of theories and let IC be a finite set of integrity constraints. Let T be the flock MAXCONS(T_{1}∪⋯∪T_{k}). Let σ_{ic} be the conjunction of the integrity constraints in IC. Comb_{1}({T_{1}, ⋯, T_{k}}, {σ_{ic}}) = the flock obtained by updating T with σ_{ic} by using Definition 4.16. □

5 Combining Prioritized Theories

The different knowledge bases that have to be combined might have different priorities associated with them. Intuitively, there might be compelling reasons that cause one knowledge base to be preferable to another. In such a case we would like to use this priority information while combining the knowledge bases. For example, if a knowledge base with higher priority or believability directly contradicts another knowledge base with a lower priority, with respect to a certain aspect we might want the combined theory to contain the point of view of the knowledge base with the higher priority. In this section we formalize what we mean by combining prioritized theories.

In the context of the murder example of Section 2, the information provided by Bill (the younger witness who was also closer to the scene of action) may seem more credible to the police who may then pursue further investigations based on his version of events as opposed to John’s version.

As a first step suppose we have theories T_{1}, ⋯, T_{k} to be combined with the priority relation (a total order) where the priority of T_{i} is less than priority of T_{j} iff i < j. With a slight abuse of notation it can be written as, T_{1} ≺ T_{2} ≺ ⋯ ≺ T_{k}. As always the integrity constraints have the highest priority, i.e. T_{k} ≺ IC. There are two distinct approaches to combine the theories that come to mind immediately; bottom-up and top-down.

In the bottom-up approach we start by combining T_{1} and T_{2} with preference to T_{2}. The combined theory is then a set of theories defined as {T : T_{2} ⊆ T and T − T_{2} is a maximal subset of T_{1} such that T is consistent}. The result is then combined with T_{3} with preference to T_{3}. This means that each theory in the result is combined with T_{3} and the final result is the set which is the union of particular results (each result is a set). This continues until T_{k}. The result is then combined with IC with preference to IC.

Algorithm 5.1 Procedure Comb − botup(Comb_{i}, T_{1} ⪯ ⋯ ⪯ T_{k}, IC) T_{k+1} = IC Comb = {T_{1}} For i = 1 to k do

begin

Temp = ∅ For all T in Comb do

Temp = Temp ∪ Comb_{i}({T }, T_{i+1}) Comb = maximal elements of Temp end

Output(Comb)

In the top-down approach we start with combining T_{k} and IC with preference to IC. The result is combined with T_{k−1} with preference to the theories in the result. This is continued until T_{1}.

Algorithm 5.2 Procedure Comb − topdn(Comb_{i}, T_{1} ⪯ ⋯ ⪯ T_{k}, IC) T_{k+1} = IC Comb = {T_{k+1}} For i = k to 1 do

begin

Temp = ∅

For all T in Comb do

Temp = Temp ∪ Comb_{i}({T_{i}}, T) Comb = maximal elements of Temp end

Output(Comb)

The following example demonstrates the difference between bottom-up and top-down combining.

Example 5.1 (“Flying Snakes”) Consider the theories T_{1}, T_{2}, T_{3} and the set IC of integrity constraints given below: The priority ordering we have is T_{1} ≺ T_{2} ≺ T_{3} ≺ IC.

T_{1} = {¬have wings(snakes)} T_{2} = {¬have wings(snakes) → ¬fly(snakes); fly(snakes)} T_{3} = {¬fly(snakes)} IC = ∅.

Thus, if we consider T_{1}, T_{2}, T_{3} to have been provided by three different experts E_{1}, E_{2}, E_{3}, the ordering T_{1} ≺ T_{2} ≺ T_{3} denotes that we have more faith in E_{2} than in E_{1} and we have the greatest degree of belief in E_{3}. E_{1} tells us that snakes don’t have wings. E_{2} tells us two things: first, that “things that don’t have wings don’t fly” and he also tells us that “snakes fly”^{5}. T_{3} tells us that “snakes don’t fly”. Bottom-up and top-down combination (using Comb_{1}) with priorities leads to two different results:

Top-down: Combining T_{3} and T_{2} we obtain

T_{32} = {{¬have wings(snakes) → ¬fly(snakes); ¬fly(snakes)}}.

Combining T_{32} with T_{1} we obtain

T_{321} = {{¬have wings(snakes) → ¬fly(snakes); ¬fly(snakes); ¬have wings(snakes)}}.

Bottom-up: Combining T_{1} and T_{2} we obtain

T_{12} = {{¬have wings(snakes) → ¬fly(snakes); fly(snakes)}}.

Combining T_{12} with T_{3} we obtain

T_{123} = {{¬have wings(snakes) → ¬fly(snakes); ¬fly(snakes)}}.

Hence in this case the result obtained by the top-down approach is different from the result obtained by the bottom-up approach.

An (artificial) objection may be raised that actually our assignment of priorities may be inappropriate because expert E_{2} provides the patently false piece of information that snakes can fly. However, this objection assumes that we assign priorities to the experts’ credibility after they provide their advice. Furthermore, in this example it is easy to see that the statement “Snakes can fly” is false because all of us know something about snakes. On the other hand, if the experts were providing information about a domain of which the reader had little knowledge (such as the history of ancient Egypt, say), he may make a patently false statement such as “Tutankhamen was Pharaoh before Akhenaton” without this being readily identifiable as a falsehood. Finally, it may be possible that the proposition “snakes fly” is not given as an objective fact by Expert 2, but is derived from a collection of thousand rules (not listed in T_{2} above), of which 999 are correct, and one is incorrect. In such cases, it may make perfect sense to prefer E_{2}’s advice over E_{1}’s because only one of 1000 rules provided by him is flawed. □

5Our example would be more forceful if we actually modify T_{2} so that expert E_{2} tells us that “All things that don’t have wings don’t fly” and then goes on to give a long list of things that don’t have wings – e.g. cats, dogs, lizards, crocodiles, elephants, etc. However, physically describing the combination of these theories would then be more cumbersome,and this is why we restrict ourselves to this small example.

Example 5.2 (Murder Example Revisited) Let us revisit the murder example. Here, we may give priority to the facts reported by Bill instead of those reported by Ed because Bill was closer to the scene of the murder and, in addition, he has better eyesight (as he is much younger). In this case, both bottom up and top down combination result in the same conclusions: one where Bill’s first statement (“the murderer wore a dark coat”) is discarded, and everything else is accepted. □

In general top-down combining is better than the bottom-up combining. That is because top-down combining results in a combination with more information than the bottom-up approach. This is evident from the “flying snakes” example. In general, if we are combining theories T_{1}, …, T_{n} and integrity constraints IC, what may happen in the bottom-up combination is the following: We start by combining T_{1} and T_{2} to get a new theory T_{12}. In the process, we may discard a wff W_{1} from T_{1} because it is inconsistent with a wff or set of wffs in T_{2}. When we combine the T_{12} with T_{3} (call the result T_{123}), we may discard that part of T_{2} that causes W_{1} to be discarded. The combination of T_{12} would not, then, restore W_{1} even though W_{1} may be consistent with the new combination T_{123}. Thus W_{1} would be “lost”.

But why then consider both approaches? It is because both approaches have parallels in real life decision making. The bottom-up approach corresponds to the following scenario. Consider an organization with a strict hierarchical employee structure. When the employee at the bottom of the hierarchy proposes an idea to his supervisor, his supervisor combines the employees idea with his beliefs (with more priority to his beliefs) and passes it on to his supervisor. This goes on till it reaches the highest authority. This passing of idea corresponds to the bottom-up approach. In fact, this mimics precisely what happens in bottom-up combination, employee E_{1}’s supervisor E_{2} may never pass on some of E_{1}’s input to his supervisor E_{3}. Thus that input would never trickle up the hierarchy and would be “lost”. Similarly, the top-down corresponds to the case when the topmost manager passes an idea or order to his subordinate and he to his subordinate and so on.

Coming back to the problem of updating, one may wonder whether the combining of prioritized theories is similar to the updating problem. Since the motivations for the two problems are different so are the results. The updating problem can be simulated by the bottom-up procedure for combining prioritized theories which is different from both the top-down procedure and the procedure for combining nonprioritized theories.

While speaking of the combination of prioritized theories, we briefly mention that it is possible that we have prioritized groups of theories G_{1}, …, G_{n}. Any two theories in the same group have the same priority; however, the groups themselves have priorities G_{1} ≺ G_{2} ≺ ⋯ ≺ G_{n}. The most straightforward way of combining the resulting multitude of theories is to proceed as follows:

Step 1: For all 1 ≤ i ≤ n, set S_{i} = MAXCON(⋃_{T ∈G_{i}} T). Thus, at this stage, for any 1 ≤ i ≤ n, all theories in the group G_{i} have been combined together. Each S_{i} is thus a set of theories.

Step 2. Construct S = (S_{1} × ⋯ × S_{n}), i.e. S is the Cartesian product of the S_{i}’s.

Step 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.

Step 4. Combine theories s_{1}, …,_{n} with priorities s_{1} ≺ s_{2} ≺ ⋯ ≺ s_{n}. Do this for all V_{i} ∈ S. Let the resulting theories be {T H_{1} …, T H_{k}}.

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

A detailed discussion about combining prioritized groups of theories is beyond the scope of this paper.

In order to see how the work described thus far relates to existing work on reasoning with inconsistency, consider the following program P:

p ¬p p → q ¬p → q p & ¬p → r

Using the annotated logic semantics of Blair and Subrahmanian [BS88, BS89] and later improved by Kifer and Lozinskii [KL89], it would be possible to infer r even though r depends on a somewhat shaky justification, viz. (p & ¬p). However, the annotated logic semantics does not allow us to conclude ¬r or ¬q. Clearly, the fact that ¬r and ¬q cannot be inferred corresponds quite well with our intuition. The MAXCONS(P) approach would allow us to conclude r. At the same time, neither ¬r nor ¬q can be concluded.

Considering the same program P, the semantics of Gelfond and Lifschitz [GL] and Kowalski and Sadri [KS] allows us to conclude everything. In particular, r can be concluded (in the same way as in [BS88, BS89]), but in addition, both ¬r and ¬q may be concluded.

One advantage of the Blair and Subrahmanian [BS88, BS89, KL89] approach is that in the case of programs containing function symbols, their semantics leads to a semidecidable consequence relation. When function symbols are present, this does not appear to be true for the MAXCONS(P) semantics.

6 Discussion and Conclusions

Expert database systems are traditionally built by a team of knowledge engineers who elicit knowledge from multiple experts in the domain of interest. Each of these experts provides information (which we will assume is represented in first order logic). As the people being asked for information are experts in the domain of interest, one would usually assume that the information they provide is correct and usually this is the case. However, two phenomena that makes the problem of coalescing the information provided by multiple experts much harder are:

• An expert provides some information that is incorrect (i.e. is false). In such a case, it may be possible to detect and correct the error – the expert will usually be quick to change his/her mind when the mistake is pointed out. However, the database may be in use for quite some time before the mistake is ever detected.

• Two experts may disagree. In this case, there is no easy way to rectify the problem. The disagreement of the two experts manifests itself as an inconsistency and one is forced to continue reasoning despite the presence of the inconsistency.

Hence the process of combining multiple knowledge bases is a genuine problem that arises frequently. In this paper, we have provided four ways of combining multiple knowledge bases when these knowledge bases all have the same priority, i.e. they are all considered to have been obtained from equally credible sources. These four ways are based on the functions Comb_{1}, Comb_{2}, Comb_{3} and Comb_{4}. We prove various relationships between these four combination techniques. All these techniques deal with methods to manipulate “maximal” consistent subsets. The differences arise depending upon:

• (Step 1) which is the set of formulas whose maximal consistent subsets are being considered ? and

• (Step 2) having made a selection in the previous step (above), which maximal consistent subsets do we retain as “acceptable” and which do we discard ?

It turns out that Comb_{1} and Comb_{2} give the same results, but compute the results differently. Comb_{3} and Comb_{4} are “bolder” than Comb_{1} in the sense that they may discard more maximal consistent subsets in Step 2 than Comb_{1} does. Comb_{3} acts on the philosophy that the integrity constraints (if any) play a role only in determining which maximal consistent subsets should be chosen. Thus, in step 1, Comb_{3} ignores the integrity constraints and finds various maximal subsets, and then in Step 2, discards some (possibly none) of the maximal consistent subsets. The great danger with Comb_{3} is that it may choose to discard everything generated in step 1. Comb_{4}, on the other hand, never discards everything. What it does is to simply pick all the maximal consistent subsets of the highest possible cardinality. As stated earlier, the intuitive motivation behind Comb_{4} is that “everytime we discard something, we are (implicitly) saying that the discarded object constitutes a mistake made by the expert. As this information is obtained from experts, it may be advisable to assume that they don’t make too many mistakes; hence we want to pick those maximal consistent subsets where the number of mistakes is minimized.” Comb_{4} thus seems to be suitable in situations where it is appropriate to make this assumption. Comb_{3} on the other hand is more appropriate in situations where the integrity constraints do not play a role in computing maximal consistent subsets. This may arise if the experts are providing advice about a domain, but they are not fully aware of some of the constraints that the individual seeking the advice has. For instance, in an expert system for putting out oil fires that may be used by many different companies engaged in this task, a (user) may have the constraint “Our company can make an initial financial outlay of only $ 274,000 towards fighting this fire”. This is a constraint the experts don’t have. However, this constraint limits the company in the range of choices it can adopt. If the maximal consistent subsets correspond to the range of choices available, then this user constraint limits the choices the company has to those maximal consistent subsets that satisfy the $ 274,000 constraint. Thus, Comb_{3} may find applications in situations where the user (not the expert) keeps adding additional constraints. Comb_{1}, which coincides with Comb_{2} is the most conservative of all the combination functions. It generates all possibilities and does not ignore any piece of information. It is an appropriate combination function to use in situations where it is essential to consider all possibilities (such as in life threatening situations and in medical expert systems).

Comb_{1}, Comb_{2}, Comb_{3}, Comb_{4} all assume that the experts providing different data are all equally credible. This is not always an appropriate assumption to make because we often have different “degrees of faith” in the credibility of the experts providing information. For instance, we may give greater weight to an economic forecast made by a Nobel Laureate in economics than by a graduate student in economics. When we have a linearly ordered set of theories (where the linear order reflects the prioritization of the theories), we have presented two prioritized combination schemes top-down and bottom-up. In the bottom-up approach, some information may be “lost” while in the top-down approach, this information may not be lost. Nonetheless, the bottomup approach, despite the loss of information, mirrors the way strict administrative hierarchies (such as in companies). often work; some information/ideas from the lower rungs of the hierarchy are “lost” when they propagate upward.

These are some of the guidelines that a database designer may choose when deciding which algorithms to use. It is really up to the individual researcher to decide which semantics is most appropriate for his/her use. We do not believe that there is one all-encompassing way of combining multiple knowledge bases.

We are currently extending this work in different directions. One direction is related to the question “How should we combine multiple knowledge bases consisting not of first order theories, but non-monotonic theories like default theories or auto-epistemic theories ?” Another important direction is a kind of hybrid reasoning: how do we integrate knowledge bases expressed in different formalisms ?

Acknowledgements. We wish to express our appreciation to the National Science Foundation for their support of our work under grant numbers IRI-86-09170 and IRI-91-09755 as well as the Army Research Office under grant number DAAG-29-85-K-0-177. Sarit Kraus was partially supported by National Science Foundation grant IRI-8907122. Thanks to Daniel Lehmann and to the referees for their useful comments.

References

[BKM89] C. Baral, S. Kraus, and J. Minker. Combining Multiple Knowledge Bases. Technical Report UMIACS TR 89-90, CS TR 2316, Department of Computer Science and UMIACS, University of Maryland, College Park, Md 20742, September 1989. To appear in IEEE Transactions on Data and Knowledge Engineering.

[BKM90] C. Baral, S. Kraus, and J. Minker. Communicating between multiple knowledge-based systems with different languages. In S.M. Deen, editor, Proc. of the Working Conference on Cooperating Knowledge Based Systems, pages 121–124, England, 1990.

[BS88] H. A. Blair and V.S. Subrahmanian. Paraconsistent Foundations for Logic Programming. Journal of Non-Classical Logic, 5,2, 1988.

[BS89] H. A. Blair and V.S. Subrahmanian. Paraconsistent Logic Programming. Theoretical Computer Science, 68:135–154, 1989.

[Dal88] M. Dalal. Investigations into a Theory of Knowledge Base Revision: Preliminary Report. In AAAI, pages 475–479, 1988.

[dCSV89] N.C.A. da Costa, V.S. Subrahmanian, and C. Vago. The Paraconsistent Logics PT. to appear in Zeitschrift fur Mathematische Logik und Grundlagen der Mathematik, 37, 1991.

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

[FKUV86] R. Fagin, G. Kuper, J. Ullman, and M. Vardi. Updating Logical Databases. In Advances in Computing Research, volume 3, pages 1–18, 1986.

[FUV83] R. Fagin, J.D. Ullman, and M.Y. Vardi. On the Semantics of Updates in Databases. In ACM SIGACT/SIGMOD Symposium on Principles of Database Systems, pages 352–365, 1983.

[Gar88] P. Gardenfors. Knowledge in Flux: Modeling the Dynamics of Epistemic States. MIT Press, 1988.

[GL] M. Gelfond and V. Lifschitz. Logic Programs with Classical Negation. In Proc. 7th Intl. Conf. on Logic Programming, pages 579–597, MIT Press.

[GM88] P. Gardenfors and David Makinson. Revisions of Knowledge Systems using Epistemic Entrenchment. In Proc. 2nd Conference on Theoretical Aspects of Reasoning about Knowledge, pages 83–95, 1988.

[Gra74] J. Grant. Incomplete Models. Notre Dame J. of Formal Logic, XV(4):601– 607, 1974.

[Gra75] J. Grant. Inconsistent and Incomplete Logics. Mathematics Magazine of Mathematical Association of America, 48(3):154–159, 1975.

[Gra77] J. Grant. Incompleteness and Inconsistency in Propositional Logic. Relevant Logic Newsletter, 1977.

[Gra78] J. Grant. Classifications for Inconsistent Theories. Notre Dame J. of Formal Logic, XIX(3):435–444, 1978.

[GS90] J. Grant and V. S. Subrahmanian. Reasoning in Inconsistent Databases, 1990. manuscript.

[KM89] H. Katsuno and A. Mendelzon. A Unified View of Propositional Knowledge Base Updates. In Eleventh International Joint Conference on AI, Detroit, August 89.

[KL89] M. Kifer and E. Lozinskii. A Logic for Reasoning with Inconsistency. to appear in J. of Automated Reasoning. Preliminary version in: Proc. Logic in Computer Science 1989.

[KS] R. Kowalski and F. Sadri. Logic Programs with Exceptions. In Proc. 7th Intl. Conf. on Logic Programming, pages 598–613, MIT Press.

[Pl84] D. Plaisted. Complete Problems in the First Order Predicate Calculus. Journal of Computer and Systems Sciences, 29, pages 8–35.

[R80] R. Reiter. A Logic for Default Reasoning. Artificial Intelligence, 13, pages 81–132.

[Sat88] Ken Satoh. Non-Monotonic Reasoning by Belief Revision. In Proc. of the international Conference on Fifth Generation Computer Systems, pages 455–462, 1988.

[Sub89] V. S. Subrahmanian. Paraconsistent Disjunctive Deductive Databases. to appear in Theoretical Computer Science, 1992.

[Va82] M. Vardi. The Complexity of Relational Query Languages. Proc. ACM Symp. on Theory of Computing, 1982.

Appendix: Description of Algorithms

Algorithm 6.1 Procedure MAXCONS1(P) MAXCON = ∅ If P is consistent then MAXCONS1(P) = {P }.

else
begin

{** Let P be the set of sentences {C_{1}, ⋯, C_{n}}. **} For i = 1 ⋯ n do P_{i} := P − {C_{i}} od For i = 1 ⋯ n do MAXCON := MAXCON ∪ MAXCONS1(P_{i}) od MAXCONS1(P) := maximal elements of MAXCON.

end

Algorithm 6.2 Procedure MAXCONS1(P, IC) MAXCON = ∅ If P ∪ IC is consistent then MAXCONS1(P, IC) = {P }.

else
begin

{** Let P be the set of sentences {C_{1}, ⋯, C_{n}}. **} For i = 1 ⋯ n do P_{i} := P − {C_{i}} od For i = 1 ⋯ n do MAXCON := MAXCON ∪ MAXCONS1(P_{i}, IC) od MAXCONS1(P, IC) := maximal elements of MAXCON.

end

Algorithm 6.3 Procedure MAXCONS2(P) Let there be n potential causes of the inconsistency of P. If n = 0 then MAXCONS2(P) = {P }.

else
begin

For i = 1 ⋯ n do S_{i} := the i’th potential cause of the inconsistency of P od S := S_{1} × ⋯ × S_{n} S′ := {{a_{1}, …, a_{n}} | (a_{1}, …, a_{n}) ∈ S} MINS := minimal elements of S′ w.r.t inclusion MAXCONS2(P) = {P − Y, | Y ∈ MINS}

end

Algorithm 6.4 Procedure MAXCONS2(P, IC) Let there be n potential causes of the inconsistency of P ∪ IC If n = 0 then MAXCONS2(P, IC) = {P }.

else
begin

For i = 1 ⋯ n do S_{i} := (the i’th potential cause of the inconsistency) - IC od S := S_{1} × ⋯ × S_{n} S′ := {{a_{1}, …, a_{n}} | (a_{1}, …, a_{n}) ∈ S} MINS := minimal elements of S′ w.r.t. inclusion MAXCONS2(P, IC) = {(P − Y) | Y ∈ MINS}

end

Algorithm 6.5 Procedure MAXCONS3(P, IC) MAXCON = ∅. CHECK = {P }. F ound = false While not Found

   begin

T EMP = ∅.

For all P_{i} ∈ CHECK do

      begin

If P_{i} ∪ IC is consistent then

        begin

Found=True.

MAXCON = MAXCON ∪ {P_{i} ∪ IC}.

        end
      else
        begin

{** Let P_{i} be the set of sentences {C_{i1}, ⋯, C_{in}}. **} For j = 1 ⋯ n do T EMP = T EMP ∪ {P_{i} − {C_{ij}}} od

        end

end CHECK = T EMP.

   end

MAXCONS3(P, IC) := maximal elements of MAXCON.

end