[Next] [Up] [Previous]
Next: An Example Up: Generating Query DAGs Previous: The Clustering Algorithm

Generating Q-DAGs

To generate Q-DAGs using the clustering method, we have to go through two steps. First, we have to modify the initialization of potential functions so that the join tree is quantified using Q-DAG nodes instead of numeric probabilities. Second, we have to replace numeric addition and multiplication in the algorithm by analogous functions that operate on Q-DAG nodes. In particular:

  1. Numeric multiplication * is replaced by an operation tex2html_wrap1404 that takes Q-DAG nodes tex2html_wrap1084 as arguments, constructs and returns a new node tex2html_wrap1406 with label tex2html_wrap1407 and parents tex2html_wrap1084.
  2. Numeric addition + is replaced by an operation tex2html_wrap1409 that takes Q-DAG nodes tex2html_wrap1084 as arguments, constructs and returns a new node tex2html_wrap1406 with label tex2html_wrap1412 and parents tex2html_wrap1084.
Therefore, instead of numeric operations, we have Q-DAG-node constructors. And instead of returning a number as a computation result, we now return a Q-DAG node.

Before we state the Q-DAG clustering algorithm, realize that we now do not have evidence tex2html_wrap1049, but instead we have a set of evidence variables tex2html_wrap1048 for which we will collect evidence. Therefore, the Q-DAG algorithm will not compute an answer to a query tex2html_wrap1336, but instead will compute a Q-DAG node that evaluates to tex2html_wrap1336 under the instantiation tex2html_wrap1049 of variables tex2html_wrap1048.

In the following equations, potentials are mappings from variable instantiations to Q-DAG nodes (instead of numbers). For example, the matrix for variable tex2html_wrap1335 will map each instantiation of tex2html_wrap1335's family into a Q-DAG node tex2html_wrap1079 instead of mapping it into the number tex2html_wrap1423. The Q-DAG operations tex2html_wrap1404 and tex2html_wrap1409 are extended to operate on these new potentials in the same way that tex2html_wrap1407 and tex2html_wrap1412 are extended in the clustering algorithm.

The new set of equations is:

Here tex2html_wrap1447 is a potential that maps each instantiation tex2html_wrap1334 of variable tex2html_wrap1335 into the Q-DAG node tex2html_wrap1450 which evaluates to tex2html_wrap1336 for any given instantiation tex2html_wrap1049 of variables tex2html_wrap1048.

Hence, the only modifications we made to the clustering algorithm are (a) changing the initialization of potential functions and (b) replacing multiplication and addition with Q-DAG constructors of multiplication and addition nodes.


[Next] [Up] [Previous]
Next: An Example Up: Generating Query DAGs Previous: The Clustering Algorithm

Darwiche&Provan