Like in the proof of Theorem 4.12, the query is reduced to complete query according

plete query is premise-restricted or strongly conclusion-restricted, then the claims follow

immediately from Lemma 4.13.

$$G$$
$$O\ n$$

$${\boldsymbol{B}}$$

$\uparrow$  . 
Otherwise, the generated complete query is reduced to premise-restricted and strongly

conclusion-restricted complete queries according to Section 4.3. Again, this reduction can

straint trees can be done by the classical linear programming approach (Paa, 1988; van

detail, the requested greatest lower and least upper bound are given by the optimal values

linear programs with 512 variables and 34 linear inequalities.

$$l_{\mathrm{{u}}}$$

Finally, note that lu is very rough upper bound for l in many conditional constraint
trees (especially in those that branch very rarely), l is much lower than lu For example,
taking complete binary tree with n 127 nodes, we get only l 19 964 compared to

$\square$
lu 260 161 024. In the example of Section 4.1.2 with n nodes, we get only l 72
compared to lu 6 660. Another example is tree that is degenerated to chain of basic
events. In this case, we even get l n + 1, that is, the overall number of generated linear

inequalities is linear in n 2

to Section 4.4. This reduction can be done in time O n). Now, if the generated combe done in time O n), since the basic event G in Theorem 4.9 a) is computable in time O n).

Thus, the claims follow from Theorem 4.9 and Lemma 4.13. Note that in Theorem 4.9 b) (1),

the tight lower answer to B)[ ; x can be computed without u and 2
der Gaag, 1991; Amarger et al. 1991; Hansen et al. 1995). In the sequel, let E)[ ; x
be query to an exact or general conditional constraint tree B; KB over n nodes.
The tight answer to E)[ ; x can be computed by solving two linear programs. In
of the following two linear programs with A A B and opt fmin; maxg
$${\mathcal{B}},\;K B\qquad\qquad n$$
$${\boldsymbol{E}}$$
$\uparrow$  . 

$${}^{A}$$
opt

P

$$A\!\in\!A\!\mathrm{g}\,,A\!\Rightarrow\!E F\quad A$$
P

P

P

$A\!\in\!A_{B}\,,A\!\Rightarrow\!GH\quad A\qquad u\qquad A\!\in\!A_{\mathbb{B}}\,,A\!\Rightarrow\!G\quad A\qquad H\ G\ u\,\ u\qquad KB$  $A\!\in\!A_{\mathbb{B}}\,,A\!\Rightarrow\!GH\quad A\qquad u\qquad A\!\in\!A_{\mathbb{B}}\,,A\!\Rightarrow\!G\quad A\qquad H\ G\ u\,\ u\qquad KB$
$$A\in A\mathbf{g}\;,A\Rightarrow E\;\;\;\;A$$
$$E_{}^{}$$
$$\mathit{l}$$
 E $$ l_u$$ $$ l$$ $$ l$$ $$ l$$ ... 
$$\mathit{l}$$
$$\,n$$

Theorem 4.14 a) The tight lower answer to a query can be computed in linear time in n.

b) The tight upper answer to a query can be computed in polynomial time in n.

Proof. We assume that the set of basic events B is totally ordered and that the basic events in the conjunctive events E and of the query E)[ ; x are written in this order.

4.6 Comparison with the Classical Linear Programming Approach and n linear inequalities. For example, the tight answer to the premise-restricted As comparison, we now brie y describe how probabilistic deduction in conditional con-
That is, the tight answer is computed by solving two linear programs with n variables complete query QRSTU M)[ ; x to the conditional constraint trees in Fig. yields two