
## 4.3 Complete Queries

We now show that the problem of computing tight answers to complete queries can be

reduced to the problems of computing tight answers to premise-restricted complete queries

and of computing tight answers to strongly conclusion-restricted complete queries.

$$\mathrm{\sfSTU~MQR}\qquad,$$
In detail, complete query is premise-restricted, it is strongly conclusion-restricted,

or it can be reduced to premise-restricted complete queries and to strongly conclusionrestricted complete queries. For example, given the complete query STU MQR)[ ; x
to the conditional constraint tree in Fig. 2, right side, we rst compute the tight answer fy =u ; y =u g to the premise-restricted complete query MQR O)[y ; y (directed to the corresponding subtree) and the tight answer fz =v ; z =v g to the strongly conclusion-re- stricted complete query O MQR)[z ; z (directed to the corresponding subtree). We then

stricted complete query O MQR)[z ; z (directed to the corresponding subtree). We then generate new conditional constraint tree by replacing the subtree over the nodes M N O Q and R by the pair of conditional constraints B O)[u ; u and O B)[ ; v over the nodes B and O (note that B represents MQR). Finally, we compute the tight answer to the premise-restricted complete query STU B)[ ; x to the new conditional constraint tree. Note that this reduction can always be done, since for each query E)[ ; x ], all paths from basic event in E to basic event in have at least one basic event in common.

Theorem 4.9 Let B; KB be a conditional constraint tree and let E)[ ; x be a complete query that is not premise-restricted and not strongly conclusion-restricted.

a) There exists a basic event G B and two conditional constraint trees B ; KB and B ; KB such that B B fGg, B B B, and G E)[z ; z is a strongly conclusion-restricted complete query to B ; KB .

b) Let the tight answer to the premise-restricted complete query E G)[y ; y to B ; KB
be given by fy =u ; y =u g and let the tight answer to the strongly conclusion-restricted complete query G E)[z ; z to B ; KB be given by fz =v ; z =v g.

(1) If u , then also and the tight answer to the complete query E)[ ; x to B; KB coincides with the tight answer to the premise-restricted complete query B)[ ; x to B fBg; KB f B G)[u ; u ; G B)[ ; v g , where B is a new basic event with B B . In particular, for exact conditional constraint trees B; KB , the tight answer to the complete query E)[ ; x is given by:

f max(0; vv
$\huge\color{green}{\huge\text{!}}\qquad\frac{v}{u}+\frac{v\;\;s}{u}\;\;,$  . 
$\downarrow$ . 

; min(1; + v s

u ; t t s u g ;
where s H  G; G", s H  G; G", and t H G; G"(note that H , H , and H 
are dened like in Section 4.1.1).

(2) If u = 0, = 1, and G , then the tight answer to the complete query E)[ ; x to B; KB is given by f ; g.

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

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