We now focus on the technical details. We present the functions H  H  H  and H  which compute the described greatest lower and least upper bounds. For this purpose, we need the following denitions. Let Pr C B denote u for all C B)[u; u KB node B is leaf if it does not have any children. For all leaves B let B" B For all the other nodes B let B" be the conjunction of all the children of B For all leaves C let L C C For all the other conjunctive events C let L C be the conjunction of all the leaves that are in C or that are descendants of node in C In the sequel, let B be node and let C B" The case C B refers to the initialization of the leaf B the case C B with node B B to the chaining of the arrow B B and subtree via the common node B and the case C B1 B2 : : : Bk with k nodes B ; B ; : : : ; Bk to the fusion of k subtrees via the common node B We dene the function H  for computing greatest lower bounds: let H  B ; C  (note that  will coincide with the greatest lower bound of Pr BL C )) Pr B sub ject to Pr KB and Pr B 0), where  in Leaf C B), Chaining C B ), and Fusion C B1 B2 : : : Bk with k 1) is given as follows:

Leaf

 CHAINING $$\alpha\quad\quad\quad\quad\quad\quad\quad,\,Pr\,\,\,C\,\,B\quad\quad\quad+\,\frac{{H}^{\alpha}\,\,\,C,\,{C}^{\dagger}\,\,-\,\,}{Pr\,\,\,B\,|C}$$  'USION $$\cdot$$ . 

Fusion  max(0; k + P k i=1 H  B ; Bi)) To express that H  computes greatest lower bounds, we need the following denitions. Let B B ; C comprise B all nodes in C and all descendants of node in C Let KB B ; C be the set of all conditional constraints of KB over B B ; C). Let Mo B ; C be the set of all models of KB B ; C that are dened on the atomic events over B B ; C). Now, the function H  is sound and globally complete with respect to B and C i H  B ; C  is the greatest lower bound of Pr BL C )) Pr B sub ject to Pr Mo B ; C and Pr B 0. Thus, the next theorem shows soundness and global completeness of H 

Theorem 4.1 a) For al l probabilistic interpretations Pr Mo B ; C , it holds  Pr B Pr BL C)). b) There exists a probabilistic interpretation Pr Mo B ; C with Pr B ,  Pr B
Pr BL C )), and Pr BL C)) i L C B.

  **  N  $H^{\alpha}$$H^{\beta}$  $H^{\gamma}$  $H^{\alpha}$$H^{\beta}$  $H^{\gamma}$  $H^{\alpha}$$H^{\beta}$  $H^{\gamma}$  $H^{\alpha}$$H^{\beta}$  $H^{\gamma}$  $H^{\alpha}$$H^{\beta}$  $H^{\gamma}$  $H^{\alpha}$$H^{\beta}$  $H^{\gamma}$  $H^{\alpha}$$H^{\beta}$  $H^{\gamma}$  $H^{\gamma}$  $H^{\alpha}$$H^{\beta}$  $H^{\gamma}$  $H^{\gamma}$  $H^{\gamma}$  $H^{\gamma}$  $H^{\gamma}$  $H^{\gamma}$  $H^{\gamma}$  

for computing least upper bounds. Note

show the crucial result that for exact conditional constraint trees,

there are local probabilistic deduction techniques that are sound and globally complete.

$$\mathrm{N}$$