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

As an example, consider the following constraint:

ASSERT size(C) - size(COrig) ≤ 200M

In this situation, for any C because any sequence of transfor-

mations starting with C will result in a smaller configuration, and therefore
the value of F always decreases. Although the definition of

D( C , F ) =↓

D is precise, in

practice it might be unfeasible to evaluate D for arbitrary values of F .Ifwe

cannot prove that D( C , F ) ∈{↑ , ↓ , ↔} we return the unknown value “ ? ”. Op-

erationally, we evaluate D in a bottom-up manner. We first assign D values

for the primitive function calls:

D( C , size ( C )) =↓

D( C , size ( Tables [” R ”] )) =↔

D( C , cost ( Q , C )) = if type( Q )is SELECT then ↑ else ?

and then propagate results through operators using rules, such as (1) ↑ +

↑ = ↑ , (2) ↑ + ↓ =?, and (3) max ( ↑ , ↔ ) = ↑ . Consider the following example:

ASSERT cost(W[1], C) / cost(W, COrig) ≤ 0.1

In this case, if W[1] is a SELECT query, then D( C , F ) =↑ . In fact,

D( . Con-

straints with generators and aggregations are handled similarly, but the in-
ference mechanism is generally less accurate. For a constraint of the form FOR
x IN X ASSERT F(x)

C , cost(W[1],C) ) = ↑ , D( C , cost(W,COrig) ) = ↔ , and ↑ / ↔ = ↑

≤

K we need to check both

D( C , F ( x )) for each x and

D( C , | X | ) . For instance, consider a generalization of the previous constraint:

FOR Q in W ASSERT cost(Q, C) / cost(W, COrig) ≤ 0.1

If all queries in the workload are SELECT queries, we would obtain, as before,
that for each Q in W . Also, since transformations do not

change the workload, we have that

D( C , F ( Q )) =↑

D( C , | W | ) =↔ . Combining these facts, we

can infer that overall (recall from Section 11.1.3.1 that in presence of

generators we sum the values of each ASSERT clause).
Using the definition of

D =↑

, Figure 11.5 specifies sucient conditions to prune
the current configuration for a given hard constraint. Consider again the con-
straint

D

ASSERT cost(W[1], C) / cost(W, COrig) ≤ 0.1

and suppose that the current configuration C satisfies F 1 (i.e., C

violates the constraint). We can then guarantee that no element in closure

( C )> 0 .

( C )

C ) obtained by transforming C would ever be feasible, because values of F ( are

for any C transformed from C . Therefore, pruning C
is safe (see Figure 11.6 for an illustration of this reasoning). For a single storage

always larger than F ( C )