
## Appendix D. Proofs For Section 4.3

Lemma D.7 Let [0; 1] and v; [0;1 . For al l probabilistic interpretations Pr with Pr G , the conditions Pr EG , Pr G Pr EG , Pr G Pr GF , and Pr G Pr GF are equivalent to:

![0_image_0.png](0_image_0.png)

Proof. The claim can be veried by straightforward arithmetic transformations based on the properties of probabilistic interpretations. 2 Proof of Theorem 4.9. a) By the denition of queries to conditional constraint trees, all paths from basic event in E to basic event in have at least one basic event in common.

In this section, we give the proof of Theorem 4.9.

The next lemma will help us to show the global tightness of the computed lower bound

in the case (3) of Theorem 4.9 b).

We are now ready to prove Theorem 4.9.

Hence, we can choose the basic event G from all such basic events in common such that G E)[z ; z is strongly conclusion-restricted complete query to subtree. b) For u 0, the claim follows from Theorem 4.7 a) to c). For the special case of exact conditional constraint trees B; KB), the claim then follows from Theorems 4.3 and :5. Let u 0, 1, and G It holds Pr E Pr EF for all models Pr of KB Moreover, by Theorem 3.2, there exists model Pr of KB with Pr E 0. Let u 0, 0, and G It is easy to see that by (1) and Theorem 4.7 d), the tight upper answer is given by f g We now show that the tight lower answer is given by f g By Theorem 4.3 b), there exists model Pr of KB with Pr E 0, Pr G 0, and Pr EG 0. By Theorem 3.2, there exists model Pr of KB with Pr G 0. By Lemma 3.1, we can choose Pr and Pr with Pr G Pr G and Pr E G Pr GF ). By Lemmata A.1 and D.7, we can choose the probabilistic interpretation Pr over fE ; G; F g with Pr A Pr A and Pr A Pr A for all atomic events A and A over fE ; Gg and fG; F g respectively, such that: Pr EGF max(0; Pr GF Pr E G)) Pr EGF : By Lemma A.2, there exists probabilistic interpretation Pr over B with (12) for all atomic

Pr EGF : By Lemma A.2, there exists probabilistic interpretation Pr over B with (12) for all atomic events H H H A and A over the sets of basic events fGg fEg f g B fGg and B fGg respectively. Hence, Pr is model of KB with Pr E and Pr EF 0. For u and not G the claim follows from (1) and Theorem 4.7 d). 2

238