Database Reference
In-Depth Information
Suppose that we want to minimize the cost of a workload with updates using
the following constraint:
SOFT ASSERT cost(W, C) 0
Since the workload has updates, D(
)) =?. However, suppose that
the initial configuration does not contain any index on table R and that all
update queries refer exclusively to table R . In this situation we know that
the cost of the workload would always increase as we apply transformations,
but the inference system might not reach the same conclusion. To address
such scenarios, we augment the constraint language with annotations that
override the default pruning behavior. Specifically, by adding the keyword
MONOTONIC UP (respectively, MONOTONIC DOWN ) before the ASSERT clause, we
specify that the respective constraint function F satisfies
C
,
cost
(
W
,
C
D(
C
,
F
) =↑
(respec-
tively,
). Of course, the framework has no way to verify whether
the annotation is correct (otherwise it would have used this knowledge up
front!) and implicitly trusts the annotation as being correct. The previous
example can then be augmented as follows:
D(
C
,
F
) =↓
SOFT MONOTONIC UP ASSERT cost(W,C) 0
11.2.3.2
Heuristic Pruning
To allow for additional flexibility in defining the search strategy, there are
annotations that heuristically restrict the search space. In contrast to the
previous section, these annotations result in a trade-off between search space
coverage and the eciency of the search procedure and are interesting when at
least one constraint satisfies
?. The search strategy keeps applying
transformation rules to the current configuration with the objective to ob-
tain the best configuration that satisfies all constraints. Since c-objectives are
usually conflicting, a configuration that improves some objectives might move
away from others. However, if the transformed configuration does not im-
prove any objective, there might be no incentive to continue exploring beyond
that point (of course, this is a heuristic and as such might prune valid solu-
tions). We might then consider such a configuration a dead end and backtrack
to a previously seen configuration. This pruning condition can be succinctly
expressed using the notion of dominance. Suppose that the current configu-
ration, C , was obtained by using some transformation over configuration C p .
Then, whenever C p dominates C , we prune C .
Two additional annotations alter how pruning is handled for individual
constraints that satisfy
D(
C
,
F
) =
D(
C
,
F
) =
?. We can specify the following behaviors:
HILL CLIMB: If a constraint is marked as HILL CLIMB , any transformation
from C p to C that results in a value of the constraint in C that is worse
than that of C p gets pruned, even though C p does not dominate C .
Search WWH ::




Custom Search