Chapter 5

Combining Multiple Knowledge Bases consisting of Logic Programs

5.1 Introduction

As research in intelligent knowledge based systems has progressed steadily over the past decade, it has become increasingly clear that there are classes of complex problems which cannot be solved by a single system in isolation; they require several systems to work together interactively in a cooperative framework. Furthermore, as the number of knowledge based systems is growing, it makes sense to use preexisting systems in cooperation, wherever possible, rather than developing new systems.In light of this an advantage of having methods to combine knowledge bases is that it will be of interest to determine if large knowledge bases can be built in sections and later combined.

The main concern in this chapter and the next two chapters is to define what it means to combine knowledge present in multiple knowledge base systems into a single knowledge base, and to present methods to combine knowledge bases. In this chapter we consider a knowledge base be an extension of a deductive database in that it permits function symbols as part of the theory. We consider alternative knowledge bases that deal with the same subject matter. Each knowledge base consists of a set of normal clauses and a set of integrity constraints. The set of integrity constraints (IC) is assumed to be same for all knowledge bases, but the sets of normal clauses may differ. We assume that each knowledge base is consistent with respect to the integrity constraints when considered alone.

While combining multiple knowledge bases we have to ensure that the combination is consistent with respect to the integrity constraints. Such a problem might arise in a large company with branches overseas. Each branch manages its own knowledge base. A consistent combination of the knowledge bases is required while trying to make a decision about the overall company.

The rest of the chapter is organized as follows. In Section 5.2, we discuss problems that may arise in combining alternative knowledge bases. Basic definitions are presented in Section 5.3. In Section 5.4, we present algorithms to combine multiple knowledge bases. In Section 5.5, we compare this problem with the view update problem in databases [FUV83, FKUV86, RN89].

5.2 Combining Knowledge Bases

We assume the knowledge bases to be logic programs with integrity constraints associated with the program.

5.2.1 Combining Logic Programs

Suppose we consider the problem of combining several logic programs without integrity constraints. In order to combine the logic programs one may take their union, i.e., all information available from all of the logic programs are combined into a single program. It is easy to see that this union is consistent.

Theorem 5.2.1 If T_{1}, ⋯, T_{k} are normal logic programs then T_{1} ∪ ⋯ ∪ T_{k} is consistent. □

Consider two logic programs T_{1} and T_{2} that contradict each other, i.e. using one we can derive P(a) while in the other we may derive ¬P (a). (Note : By “derive” we refer to an SLDNF derivation [Llo87]). As shown in Theorem 1, T_{1}∪T_{2} is consistent, and therefore even in such a case it is reasonable to combine them by taking their union. In the union of the two theories we might derive P (a) or we might derive ¬P (a). This is because the minimal model of T_{1} ∪ T_{2} is not necessarily the union of the minimal models of P_{1} and P_{2}, due to non monotonicity of the semantics. We explain this by the following example. Example 5.2.1 Consider the following logic programs P_{1} and P_{2} P_{1} :

abnormal(tweety)

bird(tweety)

bird(charli) P_{2} :

abnormal(ostrich)

bird(tweety)

flys(X) ← bird(X), ¬abnormal(X) We can derive ¬flys(tweety) from P_{1} and flys(tweety) from P_{2}. But from P_{1} ∪P_{2} we can derive ¬flys(tweety). On the other hand, from both P_{1} and P_{2} we can derive ¬flys(charli) but from P_{1} ∪ P_{2} we can derive flys(charli). □

5.2.2 Handling Integrity constraints

In real world applications, integrity constraints restrict a knowledge base to a particular meaning [MG90]. In the presence of integrity constraints, the union of a set of logic programs can violate an integrity constraint, even though each individual logic program does not violate it. Hence, in the presence of integrity constraints, the union of logic programs may not always be the correct way to combine the theories. For example if we have fatherof(ken,nick) in T_{1}, where fatherof(X,Y) denotes that Y is the father of X, and fatherof(ken,george) in T_{2}, and we take the union of the two theories, then although the union is consistent, it violates an integrity constraint that characterizes fatherhood, which states that, “one person can not have two fathers,” even though both T_{1} and T_{2} individually satisfy the integrity constraint. To combine theories T_{1} and T_{2}, we can choose one of them and include it in the combination, we can partially favor one theory and combine them as fatherof(ken, nick) ← ¬fatherof(ken, george) or we can combine them as fatherof(ken, nick) ∨ fatherof(ken, george). In the last situation we do not prefer any theory, and give the user the freedom to choose the appropriate model from the various models suggested by the combined theory. A normal clause representation of the last approach would be the unstratified clauses : fatherof(ken, nick) ← ¬fatherof(ken, george) fatherof(ken, george) ← ¬fatherof(ken, nick) Semantics of such unstratified normal logic programs, have been proposed in [BLM89b, vGRS88, Prz89c, GL88]. We do not explore this possibility in this Chapter.

5.2.3 Possible Solutions

As noted in the previous section there are different options available to combine alternative theories. The following are the major possible alternatives:

1. An Oracle exists which knows everything. Whenever a contradiction between theories exists, a decision as to what to include in the combination is determined according to the Oracle, which may support one of the theories or neither.

2. A partial order exists between all possible pairs of < theory, concept >. In case of a contradiction between two theories relative to a specific concept, in the combination we may always select data from the preferable theory with respect to this concept. For example < cardiologist, cancer > ≤ < oncologist, cancer >. That is, the cancer specialist (called “oncologist”) knows at least as much as the cardiologist about cancer and so we might trust his beliefs about cancer rather than the cardiologist’s view. A syntactic method based on this is discussed in Section 5.4.3

3. In the extreme case we might define a fact to be unknown when the facts in the two knowledge bases contradict one another. We want to remark that to define a concept as unknown is different than not to include it in the combination. If we do not include it in the knowledge base, in logic programs we will be able to derive the concept’s negation. In order to be able to implement such an approach one needs to move to three valued logic [Prz89c, BLM89b, Fit86a, FBJ88] or to protected circumscription [MP84a, MP84b, MP85].

4. A maximal amount of consistent information could be combined from alternative theories. In case of a contradiction the information could be combined to make the knowledge base consistent by converting it into a disjunctive knowledge base. This knowledge base may be presented to the user and he might choose among the disjunctive facts.

Creating an Oracle, as suggested in the first approach, is almost impossible, especially while dealing with distributed knowledge bases. There are some technical problems, but there are also some essential problems, such as who knows the truths to supply to the Oracle. We may not have the priority information available so that the second approach might not be possible. When we define a concept as unknown we lose information that existed in the original knowledge bases; so the third option may be questionable.

In this Chapter we take the last approach, where we maximally combine the set of knowledge bases subject to consistency with the integrity constraints. We also note that there is another option possible, where the user decides what is to be done.

5.3 Basic Definitions

Recently, several different semantics have been given to logic programs [vGRS88, Prz89c, GL88, BLM89b]. In the case of Horn logic programs without negation, it is well known [vEK76, AvE82] that there exists a unique minimal model. This model is used as the meaning of the program. In the case of stratified normal programs, there is a single perfect model [Prz88d, ABW88] and this model is used as the meaning of the program. In the case of stratified disjunctive logic programs we use its set of perfect models as its meaning. We call the set of perfect models of a stratified disjunctive program P, as MINSET (P). In this Chapter we only consider stratified programs and further assume that the union of the theories to be combined is also stratified.

Definition 5.3.1 Given a program P, HERB(P) denotes the (possibly infinite) set of clauses which are ground instances of program clauses in P. □

The definition of perfect model is based on a partial order between minimal models. The partial order between minimal models is based on a partial order between elements of the Herbrand base of the program P, dictated by the position of literals in HERB(P). This partial order (<) is formally defined in Definition 2.4.1.

Since, we are considering only stratified programs, the relation < is a partial order.

Definition 5.3.2 Relation between minimal models [Prz88c] Let M and N be two distinct models. We say N ≪ M (N is preferable to M) if, ∀A(a ground atom) in N-M, ∃ a ground atom B in M-N, such that A < B. □

Example 5.3.1 Consider the program: A ← ¬B C ← ¬D It has four minimal models {A,C}, {A,D}, {B,C} and {B,D}. Using the definition for the relation <, we have A < B and C < D. Consider the models {A,C} and {A,D}. Since C < D, hence we have {A,C} ≪ {A,D}. □

Definition 5.3.3 Definition of MINSET(P) The MINSET(P) of a program P is a set of minimal models of P, such that:

1. ∀x (x is a minimal model of P ⇒ ∃y, y ∈ MINSET(P) and y ≪ x).

2. ∀x,y (x,y ∈ MINSET(P) and x ≠ y ⇒ x ≪̸ y, y ≪̸ x). □

Example 5.3.2 In the last example we have {A,C} ≪ {A,D}, {A,C} ≪ {B,C}, {A,C} ≪ {B,D}. Hence, MINSET(P) = { {A,C} }. □

The syntax of integrity constraints we use is similar to that used by Sadri and Kowalski [KS86] and Chakravarthy, Grant and Minker [CGM86]. Integrity constraints are of the form ← L_{1}, ⋯, L_{m}, m > 0; where the L_{i} are literals and all variables are assumed to be universally quantified in front of the constraint in which they occur. Such clauses are called denials. When L_{i} are restricted to be only atoms we call it a positive integrity constraint. Denials have to be range restricted, that is, any variable that occurs in a negative literal of the constraint must also have an occurrence in a positive literal of the constraint. Sadri and Kowalski [KS86] show that integrity constraints of this form are general enough to represent any closed first order formula using the transformations suggested in [KS86, LT84].

There are several different definitions of integrity constraint satisfaction in a database or knowledge base [KS86]. The two main definitions are the theoremhood definition and the consistency definition. Let P be a program and Sem(P) be the semantics of the program. According to the theoremhood definition, program P satisfies an integrity constraint I iff I is true in Sem(P). According to the consistency definition P satisfies I iff Sem(P) ∪ I is consistent. The two approaches are the same when the program is complete. A program P is said to be complete with respect to a semantics, Sem(P), when for any formula W, either W is true in Sem(P) or W is false in Sem(P). Most papers that deal with the theoremhood approach use Comp(P), Clark’s completion of a program [Cla78], as Sem(P).

We use Sem(P) as the perfect model of the program, if the program is a normal program and, as we are dealing with stratified programs, they have a unique perfect model. When the program is a disjunctive program we use the set of minimal models defined as MINSET(P) as Sem(P). In the case of normal programs, P is complete with respect to our definition of Sem(P), and hence there is no difference between the consistency and the theoremhood definition with respect to our definition of Sem(P). In the case of disjunctive programs we use the consistency definition.

Definition 5.3.4 Consistency A theory T, where T may be disjunctive, is said to be consistent with respect to a set of integrity constraints IC, iff every minimal model of T that is present in MINSET(P) satisfies the integrity constraints. □

Definition 5.3.5 The ≤ relationship between theories Let T_{1} and T_{2} be two theories (possibly disjunctive). We say T_{1} ≤ T_{2} iff ∀x : x ∈ MINSET (T_{1}), ∃y : y ∈ MINSET (T_{2}) and x ⊆ y. □

Definition 5.3.6 Maximality A theory T_{i} is said to be maximal among a set of theories { T_{1} ⋯ T_{n}}, iff there does not exist j, such that 1 ≤i,j ≤ n and T_{i} ≤ T_{j}. □

Definition 5.3.7 Correctness A theory T is said to be correct with respect to theories T_{1}, ⋯, T_{k}, if T ≤ T_{1} ∪ ⋯ ∪ T_{k}. □

Definition 5.3.8 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. The combination function C, maps from a set of theories and a set of integrity constraints into a theory. It should satisfy the following four properties. 1.(identity) C(T,IC) = T. 2.(commutativity) C(T_{1}, ⋯, T_{i−1}, T_{i}, ⋯, T_{j}, T_{j+1}, ⋯, T_{k}, IC) = C(T_{1}, ⋯, T_{i−1}, T_{j}, ⋯, T_{i}, T_{j+1}, ⋯, T_{k}, IC). 3.(consistency) C(T_{1}, ⋯, T_{k}, IC) is consistent with respect to IC. 4.(correctness) C(T_{1}, ⋯, T_{k}, IC) is 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 MINSET(P) = MIN-SET(Q). □

Our goal is to combine a set of theories such that C(T_{1}, ⋯, T_{k}, IC) is maximal among all consistent and correct combinations of T_{1}, ⋯, T_{k}. The intuition behind the maximality property is that we would like the combination of the theories to include as much information as possible from all theories. The intuition behind the correctness is that the combination will not include new information that does not have a basis in the union. Consider the following example.

Example 5.3.3 Consider two theories T_{1} = {A} and T_{2} = {B} and the integrity constraint ← A, B. In the absence of any priority information, there are three consistent and correct combinations of T_{1} and T_{2}.

1. The combination whose only minimal model is {A}.

2. The combination whose only minimal model is {B}.

3. The combination that has two minimal models {A} and {B}. By definition of maximality the third combination is the maximal combination. Our goal is to develop algorithms to combine theories maximally. □

Theorem 5.3.1 Let T_{1}, ⋯, T_{k} be a set of theories and IC a set of positive integrity constraints. There exists a maximal combination of T_{1}, ⋯, T_{k}. All such combinations have the same set of minimal models. Proof: Consider the set of minimal models in MINSET(T_{1} ∪ ⋯ ∪ T_{k}). Let them be {m_{1}, ⋯, m_{s} }. Divide these minimal models so as to obtain a set of maximal models, such that none of the maximal models violate any integrity constraints in IC. For example, if m_{i} = {A_{1} ⋯ A_{n}} is one of the original minimal models, and ← A_{1} ⋯ A_{r} where r ≤ n is an integrity constraint in IC, then m is divided into the set of maximal models: {A_{1}, ⋯, A_{r−1}, A_{r+1} ⋯ A_{n}} , {A_{1}, ⋯, A_{r−2}, A_{r}, A_{r+1} ⋯ A_{n}} ⋯ {A_{2}, ⋯, A_{r+1} ⋯ A_{n}}. After dividing the original set of minimal models so as to be consistent with respect to all the integrity constraints, suppose we obtain M = { m′_{1}, ⋯ m′_{j}} as the set of maximal models. We claim that any theory which has its minimal models as M, is a maximal combination of T_{1}, ⋯, T_{k}.

Suppose this is false. i.e. ∃M′: M ≤ M′, and M′ is a combination of T_{1}, ⋯, T_{k}. Since, M ≤ M′, ∃x, y : x ∈ M and y ∈ M′ and x ⊂ y. Since M′ is correct (a property of all combinations), ∃i 1 ≤ i ≤ s : y ⊆ m_{i}. Since, x ⊂ y, x ⊆ m_{i}. i.e., x is obtained from m_{i}, while dividing m_{i} to make it consistent with respect to the integrity constraints. Since the division creates a set of maximal consistent models, x ⊂ y implies y is not consistent with respect to the integrity constraints. Hence M′ is not consistent with respect to the integrity constraints and hence it is not a combination. This contradicts our initial assumption that M′ is a combination of T_{1}, ⋯, T_{k}, and hence M is the maximal combination of T_{1}, ⋯, T_{k}. □

5.4 Combining a set of Belief Systems

In this section we give algorithms to maximally combine a set of normal logic programs. First we give algorithms to combine theories that contain only facts, then we allow rules without negation in their body and finally we consider normal logic programs.

Throughout the rest of the Chapter we assume that the SLDNF-proof tree when an integrity constraint is considered as a query, with respect to the union of the theories, is finite. A sufficient restriction for having finite SLDNF proof trees is that the theory be function free and hierarchical. By hierarchical, we mean that the theory does not have any recursion. We also assume that integrity constraints do not have negation in their body.

5.4.1 Combining Theories Consisting Only of Facts

Our initial assumption is that theories consist only of facts. Consider a simple case where T_{1} consists of P(a) and T_{2} consists of P(b), and the integrity constraint is ← P (X), P (Y), X ≠ Y. In the absence of any information about preferences we can combine these two theories, without the combination (T) violating the integrity constraint and without preferring one theory over the other, by placing only P(a) ∨ P(b) in the combination T, of the two theories. The theory T has two minimal models: one is { P(a)} and the other is {P(b)} .

Before presenting our algorithm we first show, through an example, how a combination is achieved.

Example 5.4.1 Let T_{1} =^{def} {P (a); P (b)}, T_{2} =^{def} {P (c)}, and the integrity constraint be ← P (a), P (b), P (c). The combined theory has to satisfy the logically equivalent integrity constraint, ¬P (a) ∨ ¬P (b) ∨ ¬P (c). To be maximal, we want the least number of atoms to be false in the combination. In other words we want the least number of negative literals to be true. We rename the negative literals in the clauses obtained by transferring atoms to the left in each of the integrity constraints. We rename ¬P (a) as P′(a) and others in a similar manner. After renaming we obtain the clause P′(a) ∨ P′(b) ∨ P′(c). This clause has three minimal models, {{P′(a)}, {P′(b)}, {P′(c)}}. The minimal model {P′(a)} means P′(a) is true, and others are false; that means ¬P (a) is true and all other negative literals are false; which means P(a) is false, and all other atoms are true. Each minimal model of the renamed clauses corresponds to a maximal model.

Hence, we take the integrity constraints and form clauses by transferring the atoms to the left. Next we rename the atoms in the clauses. We find the set of minimal models for the renamed clauses. Since each minimal model corresponds to a maximal model, we collect the set of these maximal models. We then construct a theory whose minimal models are the set of maximal models. The theory constructed is the maximally combined theory.

In this example the minimal models of the renamed theory are {{P′(a)}, {P′(b)}, {P′(c)}}. The maximal model corresponding to {P′(a)} is {P(b), P(c) }; the maximal model corresponding to {P′(b)} is {P(a), P(c) } and the maximal model corresponding to {P′(c)} is {P(a), P(b) }. The theory, whose minimal models are { {P(b), P(c) }, {P(a), P(c) }, {P(a), P(b) } } is P(a) ∨ P(b), P(a) ∨ P(c), P(b) ∨ P(c), and is the combined theory which is consistent with respect to the integrity constraints. □

It should be noted that the combined theory is disjunctive in the above example. An answer to the query ← P (X) with respect to the combined theory is P(a) ∨ P(b), while the answer to the query ← P (a) is ‘unknown’.

We now give an algorithm to combine a set of theories consisting only of facts, such that the resultant theory is correct with respect to the original theories, consistent with respect to the integrity constraints and is a maximal combination.

Algorithm 5.4.1 (To combine theories consisting only of facts) INPUT:

1. A set of k Horn theories {T_{1} ⋯ T_{k}} which have to be combined, where each T_{i} consists only of facts.

2. A set of s integrity constraints, IC = { IC_{1}, ⋯, IC_{s} } where each integrity constraint is satisfied by each of the theories. OUTPUT: A theory T, which is the maximal combination of the input set of theories, such that T is also satisfied by each of the integrity constraints. The combined theory T can be disjunctive. STEP 1 : Find S the set of instances of integrity constraints that violate the union of the theories. S = ∅; For i = 1 to s do begin Let IC_{i} be of the form ← P_{1}, ⋯, P_{k}, where P_{1}, ⋯, P_{k} are atoms. Solve IC_{i} with respect to T_{1} ∪ ⋯ ∪ T_{k}. (Note that, in the beginning of this section we assume this to be decidable) If there are no solutions then continue with the next i, else: Let θ_{1} ⋯ θ_{l_{i}} be all the ground answer substitutions when the IC_{i} is satisfied as a query to the union of the knowledge bases, meaning that IC_{i} violates the union of the knowledge bases S = S ∪ { ← (P_{1}, ⋯ P_{k})θ_{1}; ⋯; ← (P_{1}, ⋯ P_{k})θ_{l_{i}} } end S is the set of instantiated integrity constraints which violates the combined theory T_{1} ∪ ⋯ ∪ T_{k}. If S is empty, then the combined theory T_{1} ∪ ⋯ ∪ T_{k} is consistent with respect to the integrity constraints and the algorithm terminates. If S is not empty, continue with STEP 2. STEP 2 : Obtain the set of minimal models of the transformed and renamed clauses in S and their corresponding maximal model Let S be { C_{1}, ⋯, C_{n} }, where each C_{i} (1 ≤ i ≤ n) is defined by ← C_{i1}, C_{i2}, ⋯, C_{ik_{l}}. Let { A_{1}, ⋯ A_{p} } be all ground atoms present in S. We call this set the interfering facts.

The set of facts that is present in T_{1} ∪⋯∪T_{k} but not in { A_{1}, ⋯ A_{p} } are called non-interfering facts. Construct the set of clauses { ¬C_{11}∨¬C_{12}∨⋯ ¬C_{1k_{1}}, ⋯, ¬C_{n1}∨¬C_{n2}∨⋯ ¬C_{nk_{n}} } by transferring the atoms in the instantiated integrity constraints to the left of the arrow. Rename the negative literals ¬C_{ij} by C′_{ij} in the above set of clauses. Find all minimal models of the renamed set of clauses given by { C′_{11} ∨ C′_{12} ∨ ⋯ C′_{1k_{1}}, ⋯, C′_{n1} ∨ C′_{n2} ∨ ⋯ C′_{nk_{n}} } Let the minimal models be m′_{1}, ⋯, m′_{l} For i=1 to l do

m_{i}^{∗} = m′_{i} with C′_{ij} replaced by C_{ij} STEP 3 : Obtain the theory whose only minimal models are the maximal models found in STEP-2 For i = 1 to l do m_{i} = { A_{1}, ⋯ A_{p} } - m_{i}^{∗} Construct a theory T (possibly disjunctive) whose only minimal models are m_{1} ⋯ m_{l} by doing the following. T = {x : x = fact(A_{1} ∨ A_{2} ⋯ ∨ A_{l}), where for all i ≤ l, A_{i} is in m_{i}. }; where fact is a function that removes all but one occurrence of repeated atoms in a disjunction. STEP 4 : Obtain the combined theory, by augmenting the non interfering facts. Add all the atoms in T_{1} ∪ T_{2} ∪ ⋯ ∪ T_{k} that do not appear in { A_{1}, ⋯ A_{p} } from STEP 2 to T, and call it C(T_{1}, ⋯, T_{k}, IC). □

The intuition behind this algorithm is as follows; in order for the combination of the theories to be consistent with the integrity constraints, at least one negative literal of each clausal form of the integrity constraint has to be true in each minimal model of the combination. On the other hand, in order to make the combination maximal one needs to minimize those negations.

We demonstrate this algorithm by some examples.

Example 5.4.2 We first show example 5.4.1 with respect to this algorithm.

Let T_{1} =^{def} {P (a); P (b)}, T_{2} =^{def} {P (c)}, and the integrity constraint be ← P (a), P (b), P (c). STEP 1: We find that the integrity constraint ← P (a), P (b), P (c) violates the union of the theories. STEP 2: We transfer the atoms in the integrity constraint to the left and rename the negative literals. The resulting clause is {P′(a) ∨ P′(b) ∨ P′(c) }. We find the minimal models of P′(a) ∨ P′(b) ∨ P′(c) as {{P′(a)}, {P′(b)}, {P′(c)}}. STEP 3: For all minimal models found in STEP 2 the corresponding maximal models are { {P(b), P(c) }, {P(a), P(c) }, {P(a), P(b) } }. This is because for the minimal model {P′(a)} in STEP 2 the corresponding maximal model { {P(b), P(c) }. This is further explained in Example 5.4.1. We find the theory, whose minimal models are { {P(b), P(c) }, {P(a), P(c) }, {P(a), P(b) } } to be P(a) ∨ P(b), P(a) ∨ P(c), P(b) ∨ P(c) . STEP 4: The combined theory is the theory found in STEP 3. □

Example 5.4.3 Let T_{1} =^{def} {P (a)}, T_{2} =^{def} {P (b)}, T_{3} =^{def} {P (c)}, and the integrity constraint be ← P (X), P (Y), X ≠ Y. STEP 1: After solving the constraint we find ← P(a), P(b); ← P(a), P(c) and ← P(b), P(c) to be the instantiated integrity constraints that violate the union of the theories. STEP 2: We find the minimal models of {P′(a) ∨ P′(b), P′(a) ∨ P′(c), P′(b) ∨ P′(c)} to be {{P′(a), P′(b)}, {P′(a), P′(c)}, {P′(b), P′(c)}}. STEP 3: We find the theory, whose minimal models are { {P(c)}, {P(b)}, {P(a)} } to be P(a) ∨ P(b) ∨ P(c). STEP 4: The combined theory is the theory found in STEP 3. □

The following proves the correctness of our algorithm.

Theorem 5.4.1 C(T_{1}, ⋯ T_{k}, IC), as given by Algorithm 5.4.1 is a maximal combination of T_{1} ⋯ T_{k}.

Proof:

(a) C(T_{1}, ⋯, T_{k}, IC) is correct because all atoms in its clauses are satisfied by T_{1} ∪ ⋯ ∪ T_{k}.

(b) C(T_{1}, ⋯, T_{k}, IC) is consistent because all its minimal models by virtue of its construction in step 3, do not violate the integrity constraints. (c)Let C be all the facts in T_{1} ∪ ⋯ ∪ T_{k}. Let B = { A_{1}, ⋯, A_{p} } be the ground atoms present in S in step 2. Let A = C - B. From STEP-1 of the algorithm, we find that the atoms in B can not be all true in the same model of C(T_{1} ∪ ⋯ ∪ T_{k}, IC), because they violate the integrity constraints. In STEP-2 of the algorithm we find a set of minimal sets, where each minimal set has the minimal number of atoms false for the integrity constraints to be satisfied. Thus each minimal set of false atoms is equivalent to a maximal set of true atoms that can be true, while still not violating the integrity constraints. Thus in STEP-3 of the algorithm we split B into a set { m_{1}, ⋯, m_{l} } of maximal models, and we construct T, which has {m_{1}, ⋯, m_{l} } as the only minimal models. In STEP-4 we have C(T_{1} ∪ ⋯ ∪ T_{k}, IC) = T ∪ A . Now assume that our combination is not maximal, i.e. ∃T′ : C(T_{1} ∪ ⋯ ∪ T_{k}, IC) ≤ T′ ≤ T_{1} ∪ ⋯ ∪ T_{k}. ⟹ ∃ a model m of c : m ⊂ m′ and m′ is a model of T′. ⟹ m = A + m_{i}, where 1 ≤ i ≤ l. ⟹ m_{i} ⊂ m′ − A ⟹ But since m_{i} is one of the maximal set(by construction in step-3), the above can not be true. ⟹ Such a T′ can not exist and hence our combination is maximal. □

5.4.2 Combining Theories With Rules Without Negation in their Body

We now extend Algorithm 5.4.1 to the case where we have rules in the theories. We do not allow negative literals in the body of the rules.

Algorithm 5.4.2 (To combine theories with Horn rules) INPUT:

1. A set of k Horn theories {T_{1} ⋯ T_{k}} which have to be combined. (Note that Horn theories do not have negative literals in the body of their rules)

2. A set of s integrity constraints, IC = { IC_{1}, ⋯, IC_{s} } where each integrity constraint is satisfied by each of the theories. OUTPUT: A theory T, which is the maximal combination of the input set of theories, such that T is also satisfied by each of the integrity constraints. The combined theory T can be disjunctive. ASSUMPTIONS: Each of the theories in T_{1} ⋯ T_{k} is Horn and consists of facts and rules without negation in their body. STEP 1 : Find S′ the set of instances of integrity constraints that violate the union of the theories and for each such instance find the set of interfering rules. S′ := ∅; For i = 1 to s do begin Let IC_{i} be of the form ← P_{1}, ⋯, P_{k}, where P_{1}, ⋯, P_{k} are atoms. Solve IC_{i} with respect to T_{1} ∪ ⋯ ∪ T_{k}. (Note that we assume this to be decidable, in the beginning of the section) If there are no solutions continue with the next i, else: Let θ_{1}, ⋯, θ_{l_{i}} be the ground answer substitutions for the IC_{i} ; and for each ground answer substitution θ_{j}, Let R_{j} = {R_{j1}, ⋯, R_{jk}} be the set of rules, which were used to obtain the ground answer substitution θ_{j}, where their heads unify with one of the P_{i}s. Let R_{ji} be the rule whose head unifies with P_{i}. S′ := S′ ∪{<← (P_{1}, ⋯, P_{k})θ_{1}, R_{1}, θ_{1} >, ⋯, <← (P_{1}, ⋯, P_{k})θ_{l_{i}}, R_{l_{i}}, θ_{l_{i}} > } end S′ contains the instantiated integrity constraints that are violated by T_{1}∪⋯∪T_{k} and a set of rules for each, that have to be restricted. The set of rules present in S′ are called interfering rules. The set of rules present in T_{1} ∪⋯∪T_{k} but not in S′ are called non-interfering rules. If S is empty, then the combined theory T_{1} ∪ ⋯ ∪ T_{k} is consistent with respect to the integrity constraints and the algorithm terminates. If S is not empty, continue with STEP 2. STEP 2 : Find the set of minimal models of the transformed and renamed clauses in S and their corresponding maximal model S := the first element of each tuple of S′. (S contains the set of instantiated integrity constraints of S′ in step 1). Do STEP 2 of Algorithm 5.4.1. STEP 3 : Find the theory whose only minimal models are the maximal models found in STEP-2 Do STEP 3 of Algorithm 5.4.1 and let the theory generated be T. STEP 4 : Find the resultant theory by augmenting the non interfering facts. T := T ∪ all facts in T_{1} ∪ ⋯ ∪ T_{k} that do not appear in { A_{1}, ⋯ A_{p} } (see algorithm 5.4.1). STEP 5 : Find the resultant theory, by augmenting the restricted version of the interfering rules. function Restrict(R : a set of rules, θ_{i} : a variable substitution) : a set of rules; begin If θ_{i} is empty then Restrict = ∅ . STOP else Restrict(R,θ_{i}) := ∅ For all rules R_{i} in R do

Consider the variables in the head of R_{i} and the substitution given by θ_{i}.

Let X_{i1}, ⋯, X_{ik_{i}} be variables in the head of R_{i} and

t_{i1}, ⋯, t_{ik_{i}} be the corresponding variable substitutions.

Let R_{i} be head ← tail.

Restrict(R,θ_{i}) := Restrict(R,θ_{i}) ∪ {head ← tail, X_{i1} ≠ t_{i1}; ⋯; head ← tail, X_{ik_{i}} ≠ t_{ik_{i}}}

end {This function restricts rules with respect to a variable substitution.} Obtain from S′ the pairs < R, θ > and call it ruleset. The ruleset is { < R_{1}, θ_{1} >, ⋯, < R_{t}, θ_{t} > } Let R ={R_{1}, ⋯, R_{t}} . We call this set of rules the interfering rules, Since there might me multiple instances of the same rule in R, for each rule r in R do Restrict(Restrict(⋯ Restrict(r, θ_{r_{1}}) ⋯ θ_{r_{s−1}})θ_{r_{s}}) where θ_{r_{1}} ⋯ θ_{r_{s}} are the various variable substitutions associated with the rule r, in ruleset. T := T ∪ the collection of the above restricted rules. STEP 6: Find the combined theory, by augmenting the non interfering rules. T := T ∪ all the rules in T_{1} ∪ ⋯ ∪ T_{k} that do not appear in R. C(T_{1} ∪ ⋯ ∪ T_{k}, IC) := T. □

One may ask why we restrict the rules and do not, for example, remove the facts that are used in order to solve the integrity constraints. This is because we want to gain maximality. Taking out the facts will restrict the combined theory. On the other hand, by restricting the rules, and minimizing the negations of the facts of the integrity constraints, and leaving as much information as possible from the original theories, we obtain a maximally combined theory consistent with the integrity constraints.

The following example illustrates the above algorithm.

Example 5.4.4 Consider the integrity constraint ← P (X), P (Y), X ≠ Y, and the theories T_{1} and T_{2}.

T_{1} T_{2} P(Y) ← Q(Y) P(X) ← R(X) R(a) Q(b)

Step 1: When we solve the integrity constraint as a query we find that it is violated when x = a and y = b. So the instantiated integrity constraint is ← P (a), P (b) and the two rules that are used are P (X) ← R(X) and P (Y) ← Q(Y). In the representation given in STEP 1 of Algorithm 5.4.2 we obtain S′ = {<← P (a), P (b), {P (X) ← R(X), P (Y) ← Q(Y)}, {X/a, Y/b} > }. Step 2 and 3 gives us T = P(a) ∨ P(b). In Step-4 we do not have any non interfering facts to be added. In Step 5 we add the restricted rules P(Y) ← Q(Y), Y ≠ b and P(X) ← R(X), X ≠ a to T. After we add the facts in T_{1}∪ T_{2} that are absent in T, we get C(T_{1}, T_{2}, IC) as

P(a) ∨ P(b)

R(a)

Q(b)

P(Y) ← Q(Y), Y ≠ b P(X) ← R(X), X ≠ a

The above combined theory has the minimal models {P(a), R(a), Q(b) } and {P(b), R(a), Q(b) }. The union of the original theories has the minimal model {P(a), P(b), R(a), Q(b) } and since the instantiated integrity constraint is ← P (a), P (b), we observe that indeed this algorithm gives a maximal and consistent combination of the theories. □

Theorem 5.4.2 C(T_{1}, ⋯, T_{k}, IC) as given by Algorithm 5.4.2 is a maximal combination of T_{1}, ⋯, T_{k}. Proof:

(1) C(T_{1}, ⋯, T_{k}, IC) is consistent because, for all satisfiable instances of integrity constraints : ← (P_{1}, ⋯, P_{k})θ we restrict the rules(in step-5) which expand (P_{1})θ, ⋯, (P_{k})θ) , and add a set of disjunctive facts in step-3, to make sure they are not satisfied by the resulting combination.

(2) C(T_{1}, ⋯, T_{k}, IC) is correct because, besides restricting the rule, the disjunctive fact we add has all its minimal models as a subset of T_{1} ∪ ⋯ ∪ T_{k}.

(3) (maximality) Let C be the minimal model of T_{1} ∪ ⋯ ∪ T_{k}. (Note that T_{1} ∪ ⋯ ∪ T_{k} is a Horn theory) Let B = { A_{1}, ⋯, A_{k} } be the ground atoms present in S in step-2. In step-5 by restricting the rules we make sure that atoms in B can not be proven using those rules. Also it is clear that atoms in C - B belong to all models in MINSET (C(T_{1}, ⋯, T_{k}, IC). Let A = B -C Similar to Algorithm 5.4.1 we split B into a set { m_{1}, ⋯, m_{l} } of maximal models and construct T in step-3 which has { m_{1}, ⋯, m_{l} } as the only minimal models. The rest of the proof is same as in the proof of Theorem 5.4.1. □

5.4.3 A Syntactic Approach

Several syntactic methods have been suggested to compile integrity constraints into a deductive database [KS88, CGM86]. In these approaches, the integrity constraints are embedded as part of the deductive rules and the integrity constraints are no longer needed. Normal clauses result in the theory combined with the integrity constraints. It would then appear that multiple knowledge bases might be combined syntactically by compiling the integrity constraints to their union using the methods suggested in [KS88, CGM86]. We show by a counter example that this approach does not provide the desired result. We first describe Kowalski and Sadri’s method [KS88] and then give counter examples to show why such a syntactic approach can not be used to combine knowledge bases. However, applying Algorithm 5.4.2 to the union of the theories provides the desired result.

Kowalski and Sadri in [KS88] give a method to compile integrity constraints inside a theory. They assume that one atom in every integrity constraint is more preferable than the rest of the atoms. They call it the retractable atom of the theory.

Algorithm 5.4.3 (Kowalski-Sadri algorithm) INPUT: A theory T, and a set of s integrity constraints, IC = { IC_{1}, ⋯, IC_{s} } where for each integrity constraint a retractable atom is specified. OUTPUT: Revised theory that satisfies all the integrity constraints in IC. MAIN STEP: For i = 1 to s, Call Eliminate(T, IC_{i}). Procedure Eliminate (T : Theory, IC: an integrity constraint with its retractable atom specified); {Comments: T is the input theory and also the revised theory that is output.} begin If ← A(t), Conj is the integrity constraint, where A(t) is retractable, to eliminate it by compiling it into the rules, replace each deductive rule in T of the form A(t′) ← Conj′ by

1. A(t′)θ ← Conj′θ, ¬Conjθ, where θ is the mgu of A(t) and A(t′).

2. A(t′) ← Conj′, t ≠ t′, where t′ is an instant of t. end □

The following example explains this technique.

Example 5.4.5 Let the theory be P(X) ← Q(X) and the integrity constraints be IC_{1} : ← P (Y), R(Y) IC_{2} : ← P (b), S(c) When we eliminate IC_{1}, the retractable atom P(Y) in IC_{1} unifies with the head of the rule P(X) ← Q(X) and after elimination we obtain the rule P(X) ← Q(X), ¬ R(X), using step 1 of the procedure Eliminate. When we eliminate IC_{2}, we have

P(b) ← Q(b), ¬R(b), ¬S(c), by step 1 of the method and

P(X) ← Q(X), ¬R(X), X ≠ b, by step 2 of the method. □

If we are given a preference relation between atoms through retractable atoms in each integrity constraint, we can use Kowalski and Sadri’s syntactic method. We initially assumed that we are not given any such information. In that case, one may think that to compile the integrity constraint ← P (a), Q(b), R(c) when the retractable atom is not given, we compile three integrity constraints ← P (a), Q(b), R(c), ← Q(b), P (a), R(c) and ← R(c), Q(b), P (a) where the first atom in each is the retractable atom. We show by a counter example that such a syntactic method of compiling each integrity constraint a multiple number of times, each time assuming a different atom as retractable does not necessarily provide a consistent combination.

Example 5.4.6 Consider combining four theories each consisting of a single fact, A; B; C; D, respectively and the set of integrity constraints IC = { ← B, D ; ← A, B ; ← A, C }. After eliminating all versions of the integrity constraints from the union of the theories, we obtain P = { A ← ¬B, ¬C; B ← ¬D, ¬A; C ← ¬A; D ← ¬B }. One of the minimal models in MINSET(P), {A, B}, violates the integrity constraint. Hence the syntactic approach does not provide the desired result.

Using Algorithm 5.4.2 we generate the theory {A ∨ C; D ∨ C; D ∨ B} whose minimal models are {A,D}, {C,D} and {B,C} and they all agree with the integrity constraint. □

5.4.4 Incremental Combination of Theories

In the previous sections we gave algorithms to maximally combine a set of theories, which do not have negation in the body of the rules of the theory, so that the combination of the theories is correct and consistent. Consider the case when we have combined the theories T_{1}, ⋯, T_{k} to obtain a possibly disjunctive theory T, and we obtain another set of theories T_{k+1}, ⋯, T_{n} to be combined with the initial set of theories. We would like to combine the partially combined theory T with the new set of theories so as to obtain an equivalent theory to the one we would have obtained if we had started with the theories T_{1}, ⋯, T_{n}. But now we can not use the combining algorithm given in the previous sections. They can only be used to combine Horn theories without negation; and in this case T could be a disjunctive theory. We consider this problem in the following subsection.

Integrity Constraints and Disjunctive Theories

A disjunctive theory has multiple minimal models. As defined before, we say a disjunctive theory satisfies an integrity constraint if it is satisfied in all minimal models of the disjunctive theory. To combine theories we have to first determine whether or not the naive union of the theories violates the integrity constraints. Note that although the algorithms in previous sections generated a disjunctive theory, they made sure that the integrity constraints were satisfied.

Definition 5.4.1 Semantic Definition A disjunctive theory is said to violate an integrity constraint, iff it is violated in some minimal model. □

Let IC : ← P_{1}, ⋯, P_{k} be an integrity constraint and T be a theory. If T is a Horn theory then T violates IC if ← P_{1}, ⋯, P_{k} has a solution with respect to T i.e. T ⇒ ∃(P_{1}, ⋯, P_{k}). But if T has more than one minimal model or it is a disjunctive theory this is not the case. If T is a disjunctive theory ← P_{1}, ⋯, P_{k} will have a solution with respect to T iff ← P_{1}, ⋯, P_{k} has a solution in all minimal models of T; while ← P_{1}, ⋯, P_{k} violates T iff ← P_{1}, ⋯, P_{k} has a solution in at least one minimal model of T. It may therefore be seen that, determining if an IC is violated by a disjunctive theory is not trivial.

Definition 5.4.2 Syntactic Definition A query ← Q is true in at least one minimal model of a theory T iff ∃K, where K is clause(possibly nil) and T ⊢ Q ∨ K and T ⊬ K. □

The proof of the equivalence of the syntactic and semantic definition of a disjunctive theory violating an integrity constraint is similar to the proof of the equivalence of the syntactic and semantic definition of Minker’s GCWA [Min82]. The algorithm to determine if a disjunctive theory violates an integrity constraint can easily be constructed using the above syntactic definition and Minker and Rajasekar’s [MR88] algorithm to solve a negative ground query with respect to a disjunctive theory.

But even after finding all instances of the integrity constraints that violate the disjunctive theory, we do not know which particular minimal model is violated. Without knowing the particular minimal model violated, it is difficult to subdivide those particular minimal models violated, into a set of maximal non violating models. This is not a problem in the case of Horn theories as there is only a single minimal model.

The following algorithm explains semantically what we mean by a combination of disjunctive theories. In this algorithm we start with the set of minimal models of the union of the theories, and start dividing these minimal models such that we get a set of maximal models, such that none of these maximal models violate the integrity constraints. We call this algorithm a semantic algorithm because we do not have an algorithm to find which integrity constraints are violated by which minimal model. With the hope that such an algorithm can be found later, we present the following algorithm. We also hope the following algorithm will be used as a guideline to a more practical algorithm.

Algorithm 5.4.4 (Semantic combination of disjunctive theories) INPUT: A set S = { T_{1}, ⋯, T_{k} } of k disjunctive theories and IC = { IC_{1}, ⋯, IC_{n} }, a set of n integrity constraints. OUTPUT: A combined theory of the k disjunctive theories, such that it satisfies all the integrity constraints and is maximal. STEP 1 : Find all minimal models of T_{1} ∪ ⋯ ∪ T_{k}. Let the set of minimal models be m = {m_{1}, ⋯, m_{t}}. STEP 2 : t_{1} := t; For i = 1 to n(there are n integrity constraints) Do Begin newm := ∅;

For j = 1 to t_{i} DO

Begin

Solve IC_{i} with respect to m_{j}.

Divide m_{j} into a set of minimal models as follows.

Apply Algorithm 5.4.1 to (m_{j},IC_{i}) up to step 3 and let

m_{j}^{∗} := be the set of minimal models . newm := newm ∪ m_{j}^{∗}. end

m := newm t_{i+1} := number of elements in newm. end STEP 3 : Let m = { m_{1}, ⋯, m_{t_{n+1}} }; Remove all models from m which are subsets of some other model and let the resultant set be m′. Construct a theory whose only minimal models are the models in m′. □

We illustrate the above algorithm by the following example.

Example 5.4.7 Consider the combined disjunctive theory(T) : A ∨ B ← C C ∨ D E F which is inconsistent with respect to the integrity constraint ← B, C The minimal models of the theory are m_{1} = {D,E,F} , m_{2} = {C,B,E,F} and m_{3} = {C,A,E,F}. m_{2} violates the integrity constraint and therefore in Step 2 of the algorithm it is split to m_{21} = {C,E,F} and m_{22} = {B,E,F}, so that each of them satisfy the integrity constraint. In Step 3 of the algorithm we have m = {m_{1}, m_{3}, m_{21}, m_{22}}. Since m_{21} ⊂ m_{3}, and only the maximal sets should be present in m, we remove m_{21} from m. Hence the consistent combined theory should have the minimal models as {m_{1}, m_{3}, m_{22}}. □

Theorem 5.4.3 Algorithm 5.4.4 generates a maximal combination of theories. Proof:(Using Theorem 5.3.1 and Theorem 5.4.1) By Theorem 5.4.1, STEP 2 of Algorithm 5.4.4 divides minimal models to a maximal set of minimal models. Hence, by Theorem 5.3.1, Algorithm 5.4.4 generates a maximal combination. □

Incremental Combination using Partial Backtracking

Let S = {T_{1}, ⋯, T_{k}, ⋯, T_{n} } be a set of Horn theories, IC be a set of integrity constraints and T = C(T_{1}, ⋯, T_{k}, IC). T could be a disjunctive theory. We assume that we are given the first k theories of S and subsequently, we need to combine the rest of the theories in S. If T is a disjunctive theory, we can not use the previous algorithms. We now provide a method to combine the remaining theories with the previously combined theories . Our method takes advantage of the fact that T is a maximal and consistent combination of Horn theories. By virtue of the combining algorithm of Horn theories the clauses in T are of two major types. The first type is the set of disjunctive facts and the second type is the restricted rules and the unaffected rules and facts. We take the atoms in the disjunctive facts and combine these atoms with the remaining clauses of the theory T, to obtain a new theory T′. The theory T′ is addition equivalent to the union of the original theories T_{1}, ⋯, T_{k}, where addition equivalence of Horn theories is defined as follows:

Definition 5.4.3 We say two Horn theories T_{1} and T_{2} are addition equivalent to each other (denoted by T_{1} ≡ T_{2}) iff ∀S, where S is a set of Horn clauses (possibly empty), the minimal model of T_{1} ∪ S is same as the minimal model of T_{2} ∪ S and vice versa. □

Example 5.4.8 Consider the theory T:

P (X) ← Q(X)

Q(a)

Q(b) A theory which is addition equivalent to this theory is

P (X) ← Q(X), X ≠ a, X ≠ b P (a) P(b) Q(a) Q(b)

The theory T′ = {P(a); P(b); Q(b); Q(a) } is not addition equivalent to T, even though their minimal models are same. This is because P(c) is in the minimal model of T ∪ {Q(c)}, while it is not in the minimal model of T′ ∪ {Q(c)}. □

Algorithm 5.4.5 The incremental combination algorithm INPUT: T_{1}, ⋯, T_{n} are Horn theories. T = C(T_{1}, ⋯, T_{k}); and T_{k+1}, ⋯, T_{n} are to be combined with T. IC is the set of integrity constraints satisfied by each T_{i}, i = 1 ⋯ n and T. OUTPUT: The combined theory of T and T_{k+1}, ⋯, T_{n}. STEP 1: By virtue of construction of T using Algorithm 5.4.2, T = Gen_{3} ∪ Gen_{4} ∪ Gen_{5}; where Gen_{i} is the theory added in the STEP-i of Algorithm 5.4.2. Gen_{3} consists of a set of disjunctive clauses. Gen_{4} consists of the non interfering facts and Gen_{5} consists of the restricted rules and the non interfering rules. STEP 2 : FACTS := The set of atoms present in the clauses of Gen_{3} Let T′ := F ACT S ∪ Gen_{4} ∪ Gen_{5}. By virtue of the construction of T using Algorithm 5.4.2 and as proved in Theorem 5.4.4, T′ ≡ T_{1} ∪ ⋯ ∪ T_{k} Now use Algorithm 5.4.2 to combine T′, T_{k+1}, ⋯, T_{n}. □

Theorem 5.4.4 In STEP 2 of Algorithm 5.4.5, T′ ≡ T_{1} ∪ ⋯ ∪ T_{k}. Proof: The difference between T′ and T_{1} ∪ ⋯ ∪ T_{k} is that some clauses(C) like: P(X_{1}, ⋯, X_{n}) ← Body, in T_{1} ∪ ⋯ ∪ T_{k} is replaced by the set of clauses: C_{1} : P(a_{11}, ⋯, a_{1n}) , ⋮ C_{m} : P (a_{m1}, ⋯, a_{mn}) and C_{m+1} : P(X_{1}, ⋯, X_{n}) ← Body, X_{11} ≠ a_{11}, ⋯, X_{1n} ≠ a_{1n}, ⋯, X_{mn} ≠ a_{mn} in T′. Since for all such cases C ≡ C_{1} ∪ ⋯ ∪ C_{m+1}, i.e., for any set of clauses S, C ∪ S has the same minimal model as C_{1} ∪ ⋯ ∪ C_{m+1} ∪ S; we have T′ ≡ T_{1} ∪ ⋯ ∪ T_{k}. □

Theorem 5.4.5 If T′_{1} ≡ T′_{2} then C(T′_{1}, T_{1}, ⋯, T_{k}) and C(T′_{2}, T_{1}, ⋯, T_{k}) have the same minimal models. Proof: Since T′_{1} ≡ T′_{2}, T′_{1} ∪ T_{1} ∪ ⋯ T_{k} and T′_{2} ∪ T_{1} ∪ ⋯ T_{k} have the same minimal models. Hence the same integrity constraints violate them and since the combination is a maximal combination and the set of minimal models of the combinations are unique, the maximal combination of the above two sets of the theories have the same minimal models. □

Theorem 5.4.6 Associativity of the combination C(T′, T_{k+1}, ⋯, T_{n}) has the same minimal models as C(T_{1}, ⋯, T_{k}, ⋯, T_{n}). Proof: From the previous two theorems. □

In the above algorithm we decompose T into a Horn theory T′, strongly equivalent to the initial theory component of T. But this does not mean that we are starting all over again. That is because any integrity constraint that violates T_{1} ∪ ⋯ ∪ T_{k} will also violate T′, but we can determine its violation with respect to T′ very easily as we only use the facts ( not any rules) when we try to solve it as a query. Hence we call our algorithm a partial backtracking algorithm. The following example explains the incremental combination algorithm.

Example 5.4.9 Let T_{1} =^{def} {P (X) ← Q(X); Q(X) ← R(X); R(a)}, T_{2} =^{def} {P (b)}, T_{3} =^{def} {P (c)}, and the integrity constraint be ← P (X), P (Y), X ≠ Y. If we combine T_{1} and T_{2} first we obtain C(T_{1}, T_{2}) = {P (X) ← Q(X), X ≠ a; Q(X) ← R(X); R(a); P (a) ∨ P (b)}. T′ = {P (X) ← Q(X), X ≠ a; Q(X) ← R(X); R(a); P (a); P (b)}. C(T′, T_{3}) = {P (X) ← Q(X), X ≠ a; Q(X) ← R(X); R(a); P (a) ∨ P (b) ∨ P (c)}. If we had combined all of the theories together as in Example 5.4.3 we would have obtained C(T_{1}, T_{2}, T_{3}) = {P (X) ← Q(X), X ≠ a; Q(X) ← R(X); R(a); P (a) ∨ P (b) ∨ P (c)} which is the same as C(T′, T_{3}). Notice that when we solve the integrity constraint ← P (X), P (Y), X ≠ Y with respect to T′ ∪T_{3} we do not use any rules in T′ while when we solve the integrity constraint ← P (X), P (Y), X ≠ Y with respect to T_{1} ∪ T_{2} ∪ T_{3} we use the rules in T_{1}. □

5.4.5 Normal Theories

We now allow negative literals in the body of rules of a theory. In general such theories have multiple minimal models. As explained in the previous sub-section, it is extremely difficult to combine theories that have multiple minimal models. We shall assume that our theories are stratified. In that case such a theory has a single preferred model [Prz88c] among its minimal models, called the perfect model. If we combine theories, T_{1}, ⋯, T_{k} all of which are stratified, it does not necessarily mean that T = T_{1} ∪ ⋯ ∪ T_{k} is also stratified. If T is not stratified it is again very difficult to restrict it with the integrity constraints. We further assume that T is stratified. If T is stratified then we need an algorithm similar to Algorithm 5.4.2 to combine the theories appropriately. Since T has negated atoms in the body of the rules, the combined theory might also have negated atoms in the body of its rules.

The combined theory, which will be a disjunctive theory with negated atoms in the body of its rules will have multiple minimal models. But, as in stratified normal theories, where we consider only the perfect model amongst all minimal models, here we want to consider a subset of the set of minimal models, i.e., the set of minimal models present in MINSET(P) (defined in Definition 5.3.3).

We now give an example and show why Algorithm 5.4.2 is not sufficiently powerful to combine normal theories.

Example 5.4.10 Consider the following theories.

T_{1} : T_{2} : P(X) ← ¬ Q(X) R(a) Q(a)

Let the integrity constraints be ←P(a), R(a) and ← Q(a), R(a). Step-1 of Algorithm 5.4.2 gives us S = <←Q(a),R(a), {Q(a),R(a)},{}>.

Step-2 and 3 give T = Q(a) ∨ R(a). Step-5 adds the rule as it is. The combined theory is :

Q(a) ∨ R(a)

P(X) ← ¬ Q(X) The integrity constraint ← P (a), R(a) is violated in one minimal model of the combined theory even though it did not violate the original union of the two theories. This is because before the combination, Q(a) was true and P(a) was false in all minimal models, but after the combination Q(a) became false in some minimal models and P(a) became true in those minimal models. Also, the new combination is not correct according to Definition 5.3.7. That is because {P(a),R(a)}, a minimal model of the combination is not a subset of any minimal model of the union of the original theorems.

In order to solve these problems one needs to restrict rules with negative literals in their body that are added as disjunctions to the combined theory. In this example since Q(a) is added as a disjunction we would like to restrict rules with ¬Q(X) in their bodies. Hence, we restrict P (X) ← ¬Q(X) as P (X) ← ¬Q(X), X ≠ a and the combined theory becomes

Q(a) ∨ R(a)

P(X) ← ¬Q(X), X ≠ a which does not violate any of the integrity constraints. □

We now give the combination algorithm that uses Algorithm 5.4.2

Algorithm 5.4.6 The General Combination Algorithm INPUT:

1. A set of k normal theories {T_{1} ⋯ T_{k}} which have to be combined. Each of the T_{i} is stratified. The union of the T_{i}’s is also stratified.

2. A set of s integrity constraints, IC = { IC_{1}, ⋯, IC_{s} } where each integrity constraint is satisfied by each of the theories. OUTPUT: A theory T, which is the maximal combination of the input set of theories, such that T is also satisfied by each of the integrity constraints. The combined theory T can be disjunctive. STEP 1 to STEP 5 are same as in Algorithm 5.4.2. STEP 6 : For each rule R in the union of the theories, that has a negative literal in its body, say ¬P (X_{1}, ⋯, X_{l}), if there exists a substitution θ such P (X_{1}, ⋯, X_{l})θ is a member of {A_{1}, ⋯, A_{p}} defined in step 2 of Algorithm 5.4.2, then add Restrict(R, θ) to the combined theory. (Restrict is defined in Algorithm 5.4.2) end STEP 7: T := T ∪ all the rules in T_{1} ∪ ⋯ ∪ T_{k} that do not appear in R (defined in step-5 of Algorithm 5.4.2) and are not restricted in step-6 of this algorithm. C(T_{1} ∪ ⋯ ∪ T_{k}, IC) := T. □

Theorem 5.4.7 Let T_{1} ⋯ T_{k} be stratified normal theories that consist of normal clauses and let T_{1} ∪ ⋯ ∪ T_{k} also be stratified. Then C(T_{1}, ⋯, T_{k},IC), obtained by Algorithm 5.4.6 is a maximal combination with respect to T_{1}∪⋯∪T_{k}. Proof: Consistency and Correctness: In Step 1 to Step 5 of the algorithm, the resulting theory is made consistent with the integrity constraints. In Step 6, by restricting the rules with negative literals in their body that are added as disjunctions to the combined theory we have correctness. Steps 6 and 7 do not affect the fact that the resulting theory is made consistent with respect to the integrity constraints. Maximality: The only difference between Algorithm 5.4.6 and Algorithm 5.4.2, is that in the former we restrict the rules with negative literals in their body that are added as disjunctions to the combined theory. A particular ground instances of the head of these rules is not present in any minimal model of T_{1} ∪ ⋯ ∪ T_{k}, using the unrestricted form of the rule. Therefore, by restricting the rule, we do not loose maximality. □

In the case of theories with negated atoms in the body of its rules, the incremental combination of theories is not effective. The reason is that the combination is not associative. The following example illustrates what might happen.

Example 5.4.11 Consider the theories:

T_{1}  T_{2}  T_{3}
P(X) ← ¬Q(X)  R(a)  Q(a)

Let the integrity constraint be ← P (a), R(a). C(T_{1}, T_{3}) = { P(X) ← ¬ Q(X); Q(a) }. C(C(T_{1}, T_{3}), T_{2}) = { P(X) ← ¬Q(X); Q(a) ; R(a) }. C(T_{1}, T_{2}) = { P(X) ← ¬Q(X), X ≠ a; P(a) ∨ R(a) } C(C(T_{1}, T_{2}), T_{3}) = C(T_{1}, T_{2})∪ {Q(a)} □

The nonmonotonic nature of negation is the reason the combination is not associative. One way to deal with this is to consider the preference relation dictated by the syntax of the program. In the above example, when we combine T_{1} and T_{2}, its union has a perfect model {P(a),R(a)}, which violates the integrity constraint. Since R(a) is a fact and P(a) is obtained using default reasoning in the union of T_{1} and T_{2}, we might assume that R(a) is preferable to P(a). In that case we can eliminate P(a) to make the combination consistent. To eliminate P(a), we restrict the rule with P(X) in the head by adding X ≠ a to the body. We then obtain the combined theory to be {P(X) ← ¬Q(X), X ≠ a; R(a) }. But this approach is not general enough. If we have R(X) ← ¬Q(X) instead of R(a) in T_{2}, then we can obtain both P(a) and R(a) using default reasoning and we can not decide how to choose between P(a) and R(a).

5.5 Combining Theories and the View Update Problem

The problem of view update in databases has been discussed by Fagin et al. [FUV83, FKUV86], Rossi and Naqvi [RN89] and others. They deal with the ambiguity that arises from translating a view update to an update over the underlying base relations. Consider the database D = {P (X) ← b_{1}(X), P (X) ← b_{2}(X)}, where P(X) can only be defined intensionally. When P(a) is to be inserted to this database, by only changing base facts (the basic requirement of the view update problem) there are two possible updated theories T_{1} = D ∪ {b_{1}(a)} and T_{2} = D ∪{b_{2}(a)}. Fagin et al. want the update to reflect both these theories and to have the updated theory a disjunctive theory which has multiple models (in this case two), each reflecting a possible updated theory. Rossi and Naqvi [RN89] give algorithms to deal with a general sequence of updates in an efficient way (both time and space). In the above example the updated theory obtained by Rossi and Naqvi [RN89] is {P (X) ← b_{1}(X); P (X) ← b_{2}(X); b_{1}(a) ∨ b_{2}(a)}, which is a disjunctive theory. In this chapter we dealt with the problem of combining a set of theories represented by logic programs, where we do not prefer any one theory over the others.

In the view update problem rules are considered to be universal and hence unchangable. In the case of combining theories, rules are part of individual theories. Since they lose their individuality when we combine them, we permit restrictions to them in the modified theory.

The insertion problem in view updates as discussed in [RN89] is different than combining the facts to be inserted with the original theory. In the case of combining multiple knowledge bases, the combined theory has to be consistent with respect to a set of integrity constraints.

Fagin et al. in section 3 of [FUV83] consider the case of updating databases in the presence of integrity constraints. Their approach requires giving priorities to sentences of the theory. In the case of combining theories we are concerned with the situation where priorities are not available.

If the integrity constraints are considered part of the original theory and facts are inserted, then in the updated theory the inserted facts have to be true. In the case of combining multiple theories, the combination is affected by the integrity constraints and the facts to be combined may become disjuncts in the combined theory.

On the other hand the integrity constraints could be considered as deletions followed by insertions. In that case a deletion is forced after any insertion. We deal with this case later, when we discuss deletions.

Even in the absence of integrity constraints, while combining theories we can modify rules. This is not allowed during insertion in the view update problem.

The following example shows the differences in the two approaches:

Example 5.5.1 Let the initial theory T be:

P (X) ← b_{1}(X)

P (X) ← b_{2}(X)

b_{1}(a) If we want to insert the fact P(b) to the theory T we obtain T_{1} to be

P (X) ← b_{1}(X)

P (X) ← b_{2}(X)

b_{1}(a)

b_{1}(b) ∨ b_{2}(b) If we want to accomplish the insertion of fact P(b) by combining T with the theory {P(b)} we obtain the theory T_{2} to be

P (X) ← b_{1}(X)

P (X) ← b_{2}(X)

b_{1}(a)

P (b) Note that T_{1} is not correct according to our definition of correctness as b_{1}(b) is present in a minimal model of T_{1}, even though it is absent in the minimal model of T ∪ {P (b)}. □

The deletion in the view update problem is similar to making a theory consistent with respect to an integrity constraint. When we combine a set of theories we essentially try to make the union of the theories consistent with respect to the integrity constraints. The deletion of P (a) ∧ Q(a) from a theory T is equivalent to making T consistent with respect to the integrity constraint ← P(a), Q(a). The updated theory, T_{1}, in the view update problem neither changes nor deletes rules. When we make a theory consistent with respect to an integrity constraint we might change the rules. Let this theory be called T_{2}. Because of this T_{1} is not necessarily maximal, while T_{2} is always maximal. The following example illustrates this situation.

Example 5.5.2 Let the original theory T be:

P (X) ← b_{1}(X)

P (X) ← b_{2}(X)

b_{1}(a)

b_{2}(a) If we want to delete P(a) from T, the updated theory T_{1} is:

P (X) ← b_{1}(X)

P (X) ← b_{2}(X)

¬b_{1}(a)

¬b_{2}(a) If we treat deleting P(a) as making T consistent with respect to the integrity constraint ← P(a) we obtain the theory T_{2} to be :

P (X) ← b_{1}(X), X ≠ a

P (X) ← b_{2}(X), X ≠ a

b_{1}(a)

b_{2}(a) Since b_{1}(a) and b_{2}(a) are in the minimal model of T_{2} and not in the minimal model of T_{1}, T_{1} is not maximal. □

5.6 Conclusion

In this Chapter we presented algorithms to combine knowledge contained in Horn theories. We did so in such a manner as to achieve a maximal theory. We defined the concept of a maximal theory, and we proved the maximality of our algorithms. We gave methods to combine different positive theories written in the same language such that the combination does not violate the integrity constraints and yet they are a maximal combination. We defined what it means for an integrity constraint to violate a disjunctive knowledge base and defined the notion of strong equivalence of logic programs, and used them in our algorithms and proofs. We also gave algorithms to combine them incrementally. Finally, we gave an algorithm to combine normal theories (i.e. theories with negation in their body) maximally, when the theories and their union are stratified.

We used a a restricted syntax for integrity constraints. We are presently working on generalizing the approach given in this Chapter to general integrity constraints. Although we have given a semantic algorithm to combine disjunctive theories, a more practical algorithm is desirable. Practical algorithms to combine unstratified normal theories are also needed.

In the next two chapters we consider knowledge bases to be first order theories and default theories respectively and present algorithms to combine such theories.