
$$\mathbf{v}=\mathbf{v}-\mathbf{B}_{1}\mathbf{B}_{2}+\mathbf{v}+\mathbf{B}_{k}\mathbf{v}=-\mathbf{v}_{k}$$

C B), Chaining C B ), and Fusion C B1 B2 : : : Bk with k 1) is given as follows (note that H C; C"and H  B ; Bi are dened like in Section 4.1.2):

We are now ready to give the following characterization of tight answers to strongly

conclusion-restricted complete queries to conditional constraint trees.

Leaf

Chaining H C; C"(1 + Pr BjC 

$$+~{\frac{P r\quad B|C\,-\,}{H^{\alpha}\,\ C,C^{\uparrow}}}$$
Fusion   B B @ + min i2[1:k H  B;Bi (1=H  B;Bi 1) C C k P k A i=1 H  B;Bi By induction on the denition of H  is dened and that  (note that H  B ; C  in Leaf Chaining and Fusion is dened like in Section 4.1.2). In this case, H  to B and C i H  B ; C  is the greatest lower bound of Pr BL C )) Pr L C)) sub ject to Pr Mo B ; C and Pr L C)) 0. Thus, the next theorem shows soundness and global completeness of H  It also shows that, for C B1 B2 : : : Bk with k 1, the least upper bound of Pr BL C )) Pr L C)) sub ject to Pr Mo B ; C and Pr L C)) is given by 1.

 $$\begin{array}{cccc}Pr\;\;BL\;C&\;\;\;Pr\;\;L\;\;C\\ \\ C&B_{\,l}\;B_{\mathcal{Z}}\;.\;.\;B_{k}&\;\;\;\;k\\ Pr&Mo\;\;B_{\,,}\;C&\;\;\;Pr\;\;L\;\;C\end{array}$$

it is easy to see that H  B ; C entails that 
is sound and globally complete with respect

## Theorem 4.7

a) If  , then for al l Pr Mo B ; C , it holds  Pr L C)) Pr BL C)).

b) If  , then there is a probabilistic interpretation Pr Mo B ; C with Pr B ,
Pr L C)) ,  Pr L C)) Pr BL C)), and  Pr B Pr BL C )).

c) If  and C B1 B2 : : : Bk with k , then there is some Pr Mo B ; C with Pr B , Pr L C)) , Pr L C)) Pr BL C)), and  Pr B Pr BL C )).

d) If  = 0 and C B1 B2 : : : Bk with k , then for each " > there is some Pr Mo B ; C
with Pr B , Pr L C)) , Pr L C)) Pr BL C)), and " Pr B Pr BL C )).

Proof. The proof is given in full detail in Appendix C. 2 Theorem 4.8 Let B; KB be a conditional constraint tree and let E)[ ; x be a strongly conclusion-restricted complete query. Let the tight lower answer to the premiserestricted complete query E )[y ; y be given by fy =u g.

(1) If u , then the tight answer to E)[ ; x is given by f H F; F "; g.

(2) If u and E , then the tight answer to E)[ ; x is given by f ; g.

(3) Otherwise, the tight answer to E)[ ; x is given by f ; g.

Proof. The proof is given in full detail in Appendix C. 2
