Constrained Physical Database Design - Automated Physical Database Design and Tuning - page 205

satisfies all hard constraints while minimizing the n s c-objectives results in the
most attractive configuration (which might not satisfy some hard constraint).
Usually, the n h c-objectives are in opposition to the n s c-objectives and also to
each other, and therefore the search problem is challenging.
To solve this multiobjective problem, we can in principle combine all c-
objectives together into a new single-objective function:

i = 1 w i · c-objective i (

n

singleObjective( C ) = C )

where w i is a user-defined weight for the i - th c-objective. While this approach

is universally applicable, it suffers from a series of problems. The choice of
weights is typically a subtle matter, and the quality of the solution obtained
(or even the likelihood of finding a solution whatsoever) is often sensitive to the
values chosen. A deeper problem arises from the fact that usually c-objectives
are noncommensurate , and therefore trade-offs between them range from ar-
bitrary to meaningless.
Therefore, it is not generally a good idea to reduce the original problem
to a single-objective optimization instance. A better choice is to rely on the
concept of Pareto optimality , which looks for the set of solutions with the
“best possible trade-offs.”

11.1.3.2 Pareto Optimality for Configurations

The concept of Pareto optimality can be explained by using the notion of dom-
inance . We say that vector x y n )

if the value of x along each dimension is at least as good as that of y and
strictly better for at least one dimension. Therefore, assuming that smaller
values are better:

= ( x 1 ,..., x n ) dominates vector y = ( y 1 ,...,

y j
An element x is Pareto optimal in a set Y if it is not dominated by any other
element y

x dominates y ⇐⇒ ∀ i : x i ≤ y i ∧∃ j : x j <

Y .
In our scenario, each configuration is associated with a vector of size n s +

∈

n h
for n s soft constraints and n h hard constraints, and thus we can talk about
dominance of configurations. If there is a single soft constraint and all hard
constraints are satisfiable, there must be a unique Pareto optimal solution. In
fact, for a configuration to be valid, each of the n h c-objectives must be zero,
and thus the valid configuration with the smallest c-objective value for the soft
constraint dominates every other configuration. For multiple soft constraints,
the Pareto optimal solutions might not be unique but instead may show the
best trade-offs among soft constraints for the set of valid configurations.
So far we have reduced a specification in the constraint language into a
multiobjective optimization problem without giving an explicit mechanism to
do the optimization. We next adapt the top-down framework of Section 6.2
to solve the constrained version of the problem.