[Next] [Up] [Previous]
Next: References Up: Query DAGs: A Practical Previous: Acknowledgements


Proof of Theorem 


Without loss of generality, we assume in this proof that all variables are declared as evidence variables. To prove this soundness theorem, all we need to show is that each Q-DAG potential will evaluate to its corresponding probabilistic potential under all possible evidence. Formally, for any cluster tex2html_wrap1752 and variables tex2html_wrap1335, the matrices of which are assigned to tex2html_wrap1752, we need to show that
for a given evidence tex2html_wrap1755. Once we establish this, we are guaranteed that tex2html_wrap1450 will evaluate to the probability tex2html_wrap1336 because the application of tex2html_wrap1404 and tex2html_wrap1409 in the Q-DAG algorithm is isomorphic to the application of * and + in the probabilistic algorithm, respectively.

To prove Equation 1, we will extend the Q-DAG node evaluator tex2html_wrap1760 to mappings in the standard way. That is, if tex2html_wrap1706 is a mapping from instantiations to Q-DAG nodes, then tex2html_wrap1762 is defined as follows:
That is, we simply apply the Q-DAG node evaluator to the range of mapping tex2html_wrap1706.

Note that tex2html_wrap1764 will then be equal to tex2html_wrap1765. Therefore,
Note also that by definition of tex2html_wrap1767, we have that tex2html_wrap1768 equals tex2html_wrap1769. Therefore,