
Continuous Physical Database Design 187
Opt-SI (W=(q
1
, ... ,q
n
):workload, C
0
:configuration)
01 i=0
02 while (i<n)
03 if (C
i
=0) // see Cases A1, A2, A3 in Figure 10.6
04 if (Case A1) C
k
=0 for i+1 ≤ k ≤j; i=j
05 else if (Case A2) C
k
=1 for i+1 ≤ k ≤j; i=j
06 else (Case A3) C
k
=0 for i+1 ≤ k ≤n; i=n
07 else // C
i
=1, see Cases B1, B2, B3 in Figure 10.6
08 if (Case B1) C
k
=1 for i+1 ≤ k ≤j; i=j
09 else if (Case B2) C
k
=0 for i+1 ≤ k ≤j; i=j
10 else (Case B3) C
k
=0 for i+1 ≤ k ≤n; i=n
FIGURE 10.5 Optimal algorithm for single-index case. (Used with per-
mission from Bruno, N. & Chaudhuri, S. In Proceedings of the International
Conference on Data Engineering [ICDE], 2007.) ...