A natural way to capture interactive evaluation strategies is by representing the Boolean expression as a
Binary Decision Diagram [1]}. Intuitively, BDDs are acyclic graphs where each (inner) node corresponds to a variable to be probed next, where edges correspond to possible probe answers,
and where leaves give the result of evaluating the function. The worst-case number of probes for a given strategy is the depth (i.e. longest root-to-leaf path) of the BDD representation of the strategy. Worst-case optimization for interactive evaluation then amounts to finding a BDD with minimal depth for the given provenance expressions. We can always find a trivial BDD where this depth is the number of variables of the expression, by asking about all variables, but in some cases we may be able to achieve a lower depth.
