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

The following constraint enforces that no SELECT query degrades by more
than 10% compared with the currently deployed configuration:

FORQinW
WHERE type(Q) = SELECT
ASSERT cost(Q, C) ≤ 1.1 * cost(Q, COrig)

The last constraint enforces that no index can be replaced by the corre-
sponding narrow alternative without at least doubling the cost of some query:

FORIinC
FORQinW
ASSERT cost(Q, C-I+narrow(I))/cost(Q, C) ≤ 2

where narrow(I) results in a single-column index with I 's leading column.
For instance, we have that narrow( R

( a , b , c ) )= R ( a ) .

11.1.3 Language Semantics
Constrained physical design is a multiconstraint, multiobjective optimization
problem (soft constraints naturally lead to multiple optimization functions). A
common approach to handling such problems is to transform constraints into
objective functions (also called c-objectives ) and then to solve a multiobjective
optimization problem. We next explore this approach.

11.1.3.1 From Constraints to C-Objectives
Note that the function-comparison-constant pattern for ASSERT clauses en-
ables us to assign a nonnegative real value to each constraint with respect
to a given configuration. It is in fact straightforward to create a c-objective
that returns zero if the constraint is satisfied and positive values when it is
not (and moreover, the higher the c-objective value, the more distant is the
configuration to one that satisfies the corresponding constraint). Figure 11.1
shows this mapping, where F ) denotes the constraint function over the

current configuration, and K denotes the constant in the ASSERT clause. For
constraints that iterate over multiple ASSERT clauses, we sum the values of
the individual ASSERT clauses.
By proceeding in this way, each configuration is now associated with n s +

( C

n h
values for n s soft constraints and n h hard (i.e., nonsoft) constraints. Mini-
mizing the n h c-objectives down to zero results in a valid configuration that

Constraint C-Objective

F ( C ) ≤ K max ( 0 , F ( C ) − K )

F ( C ) = K | F ( C ) − K |

F ( C ) ≥ K max ( 0 , K − F ( C ))

FIGURE 11.1 Converting constraints into c-objectives .