Figure: Reduced and unreduced Q-DAGs for the car diagnosis example.
After generating a Q-DAG, one proceeds by reducing it using graph rewrite rules. Figure 16 shows an example of such reduction with a Q-DAG that is restricted to one query node for simplicity. To give an idea of the kind of reduction that has been applied, consider the partial Q-DAG enclosed by dots in this figure. Figure 17 compares this reduced Q-DAG with the unreduced one from which it was generated. Given our goal of generating Q-DAGs that (a) can be evaluated as efficiently as possible and (b) require minimal space to store, it is important to see, even in a simple example, how Q-DAG reduction can make a big difference in their size.
Figure: Reduced and unreduced Q-DAGs for the car diagnosis example.