K , F
↑ or ↔
K , F
↓ or ↔
Sucient pruning conditions for hard constraints.
constraint ASSERT size(C) ≤ B , the pruning condition reduces to that of
the traditional physical design problem (i.e., if the current configuration is
smaller than the storage constraint, prune it and backtrack to a previous
Soft constraints: In addition to the conditions stated in Figure 11.5,
pruning a configuration C based on a soft constraint additionally re-
quires that C satisfy all the hard constraints (since any value of the
c-objective associated with the soft constraint is acceptable, we might
otherwise miss overall valid solutions).
11.2.3 Additional Search Guidance
We next show how we can alter the default search procedure by modifying
the way we deal with constraints and thus obtain new functionality.
Additional Pruning Guidance
Although the technique described previously safely prunes configurations
guaranteed to be invalid, certain situations require additional support.
Constant: F ≤ K
F ( C ) > K
( C, F ) =
FIGURE 11.6 Sample pruning condition. (Used with permission from
Bruno, N. & Chaudhuri, S. In Proceedings of the VLDB Journal , 19, 1, 2010.)