We have seen that the addition of new information in the database can produce inconsistencies, that are resolved by the revision mechanism incorporated in the proof procedure. In this section we investigate how this revision process is related to belief revision theory, and, in particular, we compare our approach with prioritized base revisionintroduced by Nebel in 33].
Prioritized base revision is a form of syntax based revision in which the belief base Z, subject to revision, is partitioned into disjointpriority classesZi, i1. In our case, the priority classes are given by the sets of facts S1:::Sn which are created by the evaluation of a conditional query S1> ::: > Sn> A from .
We recall the denition of prioritized base revision of nite belief bases as given in 33]. Let `PC be derivability in classical logic and let Cn(T), for a set of formulas T, be the set of logical consequences of T in classical logic. Let Z be a belief base partitioned into disjoint priority classes Zi, i1 and let be a formula. The prioritized removal of (written Z + ) is the set of all maximal subsets of Z not implying , where the sentences in Zi have higher priority than those in Zj, for i < j:
Z+ =nY Z jY 6` Y =Si1Yi
8i1 : (YiZi and
8X : YiXZi)(Sij;1=1YjX)` o:
When the belief base Z is nite, the prioritized base revision operation, denoted by , can be dened as follows:
Z =
Cn((W(Z+: ))^ ) if 6`:
Z^ otherwise:
Notice that, in the denition above, we have used the negation :, rather than the boolean negation
, and, as usual, : has to be interpreted as ?. Hence, in the following, when we say that a set of formulas & is consistent (in PC), we mean that &6j=PC ?. We want to compare the evaluation of a goal S1> ::: > Sn> A from with the revision of a prioritized base. Suppose that, in proving the above goal,
S1:::Sn;1have been added to the program and Sn> A is the goal remaining to be proved. The addition of Sn to the program jS1:::Sn;1 can be regarded as a revision of the belief base Z = S1:::Sn;1
with (VSn)^, where the priority classes are Z1= Sn;1, Z2= Sn;2, :::, Zn;1= S1, and (VSn) is the conjunction of the atoms in Sn.
Since the information in is permanent, it has to hold after any revision. For this reason, is inserted together with the new set of facts Sn. In order to make a comparison with Nebel's revision, we have to restrict our consideration to sets of clauses and constraints not containing conditional formulas (the revision formula cannot contain conditionals).
We want to establish a correspondence between abductive solutions for and the prioritized base revision. To this purpose, we say that an abductive solution (#T#F) for is total with respect to S1:::Sn, if for all assumptions in H of the form2(Si > ::: > Sn > A) with i = 1:::n;1, either
2(Si> ::: > Sn> A)2#T or 2(Si> ::: > Sn> A)2#F (see the end of section 3, for comments about the totality requirement).
No requirement of totality is put on the other assumptions inH.
Let be a set of clauses and constraints that do not contain conditional formulas, = fG A :
2(G A)2gand S1:::Snbe sets of atomic formulas.
Theorem 5.1. Assume thatSn6j=CLU ?. There is a bijective mapping between the abductive solutions (#T#F) for that are total with respect toS1:::Snand the sets Y 2Z + :((VSn)^), where Z = S1:::Sn;1 is a belief base with priority classesZj=Sn;j,j = 1:::n;1.
Note that the class Si+1, has higher priority than Si. Updating with a set of atoms Sn a program P with protected part , corresponds to updating the revisable part of P with Snand .
To prove Theorem 5.1 we need the following lemma.
Lemma 5.1. For each permanent database not containing conditional formulas and for each set of ab-ducibles#,
#j=CLU S1> ::: > Sn> Ai#S1:::Sn j=PC A
#j=CLU S1> ::: > Sn>:A i#S1:::Sn j=PC:A
where#S1:::Sn =fA : 2(Si> ::: > Sn> A)2# A2Si and i = 1:::n;1gSn.
Lemma 5.1 is an easy consequence of the completeness of the monotonic proof procedure. When does not contain conditional formulas, the context S1:::Sn of the derivation is determined by the initial goal and it does not change during the proof. Hence the proof can be regarded as a standard SLD-proof in which, at each step, either a clause in or an hypothesis in # is used. #S1:::Sn is a set of atoms containing all the atoms from S1:::Snwhich are visible in that context.
Proof.
of theorem 5.1
]Let Z = S1:::Sn;1 be a belief base with priority classes Zj=Sn;j, j = 1:::n;1. Assume that
Sn6j=CLU ?. We will prove the following:
(i) Given an abductive solution (#T#F) for that is total with respect to S1:::Sn: if Y =fA : 2(Si> ::: > Sn> A)2#T A2Si and i = 1:::n;1g
then Y 2Z +:((^Sn)^):
(ii) If
Y 2Z +:((^Sn)^)
then there is a total abductive solution (#T#F) for such that
Y =fA : 2(Si> ::: > Sn> A)2#T A2Si and i = 1n;1g:
We rst prove (i). Let us dene, for all i = 1:::n;1,
Yi=fA : 2(Si> ::: > Sn> A)2#T and A2Sig
so that Y =Sni=1;1Yi. To prove that Y 2Z +:((VSn)^), we have to prove that Y is a subset of Z such that Y 6j=PC :((VSn)^) and that Y is maximal according to the priority classes.
Let us rst prove Y 6j=PC :((VSn)^). If Y = , then this is obvious. In fact, from the fact that Sn 6j=CLU ? it follows that of Sn 6j=PC ?. If Y 6= , let k be the least i = 1:::n;1 such that Yi 6= . Then there is an assumption 2(Sk > ::: > Sn > B) 2#T. By property (b) of abductive solutions (and by totality w.r.t. S1:::Sn) #T 6j=CLU Sk > ::: > Sn > :B. By Lamma 5.1,
#TSk:::Sn 6j=PC:B, that is, Yk:::Yn;1Sn6j=PC :B. Hence, by denition of Y and since B2Yk, Y Sn6j=PC?, that is Y 6j=PC :((VSn)^).
To show that Y is maximal according to the priority classes, let us assume, by absurdum, that, for some i = 1:::n;1 and for some B 2 Si such that B 62 Yi X = YifBg is consistent (in PC) with (Snj=;1i+1Yj)Sn)), that isSnj=;1i+1YjX6j=PC:((VSn)^). This means that Yi:::Yn;1
Sn6j=PC:B. Hence, #TSi:::Sn 6j=PC :B, and, by Lemma 5.1, #T 6j=CLU Si > ::: > Sn>:B.
Since, #T is an abductive solution that is total w.r.t. S1:::Sn: 2(Si > ::: > Sn > B) 2 #T, which contradicts the initial hypothesis.
Let us now prove (ii). Given Y 2Z +:((VSn)^), by construction Y =Sni=1;1Yi, where YiSi, for all i = 1:::n;1 (note that, for i < j, Sj has higher priority then Si).
We dene an abductive solution (#T#F) for which is total w.r.t. S1:::Sn as follows:
#T =f2(Si> ::: > Sn> A) : A2Yi and i = 1:::n;1g
#F =f2(Si > ::: > Sn> A) : A62Yi and i = 1:::n;1g:
Note that the assumptions on sequences dierent from S1:::Sn are included neither in #T nor in #F. We have to show that (#T#F) is an abductive solution.
We rst verify condition (a) of Denition 2. For all i = 1:::n;1, if 2(Si > ::: > Sn > A) 2
#F then A 62 Yi. Let X = Yi fAg. Since Yi is a maximal consistent subset of Si according to the prioritization, then: Snj=;1i+1YjX j=PC :((VSn)^). Hence Yi:::Yn;1Snj=PC:A, that is, #TSi:::Sn j=PC:A. Hence, by Lemma 5.1, #T j=CLUSi > ::: > Sn>:A.
To verify condition (b) of Denition 2, let us assume that for some i = 1:::n;1,2(Si> ::: > Sn>
A)2#T. Then, by construction A 2Yi. Since Snj=;1i Yj 6j=PC :((VSn)^), that is, Yi is consistent (in PC) withSnj=;1i+1YjSn, and since A 2 Yi, we have Yi:::Yn;1Sn 6j=PC :A, that is,
#TSi:::Sn6j=PC :A. Hence, by Lemma 5.1, #T 6j=CLU Si> ::: > Sn>:A.
The following corollary follows easily from the theorem above.2
Corollary 5.1. Assume thatSn6j=CLU ?. The following statements are equivalent:
for all abductive solutions (#T#F)for that aretotalwith respect toS1:::Sn
#T j=CLUS1 > ::: > Sn> A
A2Z((VSn)^)
whereZ = S1:::Sn;1 is a belief base with priority classesZj=Sn;j,j = 1:::n;1.
Observe that Theorem 5.1 does not hold if Snis not consistent, i.e. if Snj=CLU?. In this case,
Snj=PC ?, hence,
Z((^Sn)^) = ZSn:
From ZSnwe cannot conclude all formulas, since ?is not classical falsity, but we can conclude (for instance) all A2Z. On the other hand, for all abductive solutions (#T#F) for it holds
#T j=CLU S1> ::: > Sn>?:
However, since?blocks the persistency of all the assumptions in the revisable part, we do not necessarily conclude #T j=CLU S1> ::: > Sn> A for all A2Z.