  **Proof.**  N  $\begin{array}{ccccccccc}&&&&&\Box&&&&\\ &\mbox{N}&&&&H^{\gamma}&B,B_{i}&&H^{\alpha}&B,B_{i}&+H^{\beta}&B,B_{i}\\ i&k&&&&&&i\,j\in i\,i\,j/j&H^{\alpha}&B,B_{i}&+H^{\beta}&B,B_{j}\\ \gamma&\mbox{Fusion}&&\alpha&+&\beta&&&&\gamma\\ &&&&&\alpha&&\beta&&\\ \mbox{fl}&&&&&\{&H^{\alpha}&E,E^{\uparrow}\,\,,\qquad H^{\alpha}&E,E^{\uparrow}\,\}\end{array}$

We now focus on computing the tight answer to premise-restricted complete queries to

$$E\qquad\mathrm{~i~}$$
We may think that the local deduction technique for exact conditional constraint trees

of Section 4.1.1 can easily be generalized to conditional constraint trees. In fact, this is true

as far as the computation of greatest lower bounds is concerned. However, the computation

of least upper bounds cannot be generalized that easily from exact conditional constraint

trees to conditional constraint trees. More precisely, generalizing the computation of least

upper bounds results in solving nonlinear programs. These nonlinear programs and our way

4.1.2 Conditional Constraint Trees general conditional constraint trees. In the sequel, let B; KB be conditional constraint

tree and let E)[ ; x be premise-restricted complete query.
to solve them are illustrated by the following chaining example. Let the conditional constraint tree B; KB be given by B fM; N; O; Pg and KB f N M)[u ; u ; M N)[ ; v ], O N)[ ; x ], N O)[y ; y ], P O)[r ; r ], O P)[s ; s g Let us consider the premise-restricted complete query P M)[z ; z ].

$$y\quad\quad y\ \ ,y\quad\quad r\quad\quad r\ \ ,\ r\quad\quad s\quad\quad s\ \ ,\ s$$

By Theorem 4.2 and some straightforward arithmetic transformations, the requested

least upper bound is the maximum of z sub ject to u u ; u ], ; v ], ; x ],
y y ; y ], r r ; r ], s s ; s ], and the nonlinear inequalities in (1) to (5):
z u + u v ux v + uxr vy z u + ux v uxr vy + uxr vys z u ux v + ux vy uxr vy + uxr vys z uxr vys In this system of nonlinear inequalities, all upper bounds of z are monotonically decreasing in y and s Hence, we can equivalently maximize z sub ject to u u ; u ], ; x ], r r ; r ], and the nonlinear inequalities in (6) to (10):

(2)

(3)

(4)

(5)

$$\begin{array}{c c c}{{}}&{{}}&{{y}}&{{}}\\ {{r}}&{{}}&{{r}}\end{array},\begin{array}{c c c}{{}}&{{}}&{{s}}\\ {{}}&{{}}&{{}}\\ {{}}&{{}}&{{}}\end{array}$$

r ,r $$\begin{array}{cccccccccccccccc}&&z&&&&&&\\ &z&&&&&&u+\frac{u}{v}&\frac{ux}{v}+\frac{u\,yr}{y}&&&&\\ &z&&&&&&u+\frac{u}{v}&\frac{u\,yr}{v}+\frac{u\,yr}{v}&&&&\\ &z&&&&&&u&\frac{ux}{v}+\frac{u\,yr}{v}&\frac{u\,yr}{v}+\frac{u\,yr}{v}&&&&\\ &z&&&&&&\frac{u\,yr}{v}&&&&\\ &&&&&&u&u&&u&&\\ &&&&&&&&&\\ u,&r&r&\cdot&&\cdot&y&&\cdot&s&\left\{\begin{array}{ccc}\cdot&\cdot&\cdot&\cdot\\ u&\cdot&\cdot&\cdot&\cdot\end{array}\right\}&&&&\\ &&&&&&u&\times&\end{array}$$

(7)

(8)

(9)

(10)

$$213$$