
| CVE              | VE    |         |       |          |
|------------------|-------|---------|-------|----------|
| Query Var        | Time  | Size    | Time  | Size     |
| #11(CKND_12_15)  | 15039 | 1327104 | 25368 | 5308416  |
| #13(CBODN_12_15) | 620   | 16384   | 4552  | 442368   |
| #27(CKND_12_45)  | 3808  | 186624  | 53965 | 15925248 |
| #25(CKNI_12_45)  | 1708  | 36864   | 57414 | 7077888  |
| #22(CKNN_12_30)  | 367   | 16128   | 3821  | 442368   |
| #21(CBODN_12_30) | 7953  | 193536  | 13997 | 1769472  |
| #17(CKNI_12_30)  | 742   | 48384   | 3677  | 442368   |
| #22(CKNN_12_30)  | 363   | 16128   | 3846  | 442368   |
| #19(CKND_12_30)  | 7939  | 774144  | 26654 | 2359296  |
| #15(CNON_12_15)  | 8177  | 193536  | 14599 | 1769472  |
| #12(CNOD_12_15)  | 618   | 37044   | 4264  | 442368   |
| #3(CKND_12_00)   | 419   | 29376   | 9414  | 1327104  |
| #16(C_NI_12_30)  | 429   | 28224   | 3799  | 442368   |
| #30(CKNN_12_45)  | 2902  | 112896  | 52648 | 15925248 |
| #4(CNOD_12_00)   | 2496  | 110592  | 42270 | 5308416  |
| #21(CBODN_12_30) | 8042  | 193536  | 13619 | 1769472  |
| #5(CBODN_12_00)  | 992   | 112320  | 3334  | 442368   |
| #19(CKND_12_30)  | 7936  | 774144  | 25637 | 2359296  |
| #11(CKND_12_15)  | 16290 | 1327104 | 24753 | 5308416  |
| #23(CNON_12_30)  | 604   | 37044   | 3535  | 442368   |

Figure 13 shows some of the details of some of the data with no observations. Figures 14 and 15 shows some of the details of some of the data with 5 and 10 observation respectively. These make up the data shown in Figure 10 of the main paper. We show the index of the variable given the ordering in the repository (we started counting at 0).

All of the times are in milliseconds for a Java implementation running on 700 MHz Pentium running Linux with 768 megabytes of memory. In order to allow for the variation in run times due to garbage collection each evaluation was run three times and the smallest time was returned. The space is for the maximum table created in VE or the maximum size of the sum of all of the confactors created during the elimination of one variable.

## A.2 Randomised Experiments

The following procedure was used to generate the random networks. Given the n variables, we impose a total ordering. We build a decision tree for each variable. The leaves of the decision trees correspond to contexts and a variable that the tree is for. We start with the empty decision tree for each variable. We randomly (with uniform probability) choose a leaf and a variable. If the variable is a possible split (i.e., it is a predecessor in the total ordering of the variable the leaf is for and the context corresponding to the leaf doesn't commit a value to that variable), we split that leaf on that variable. This is repeated until we have n + s leaves. Then for each leaf, we built a confactor that has the same context and each predecessor of the variable that the leaf is for is included in the