
74 Automated Physical Database Design and Tuning
set of candidate indexes for query Q, obtained by any of the techniques of
Section 4.1. Let C
i
(i ≥ 0) be a family of candidate indexes defined as follows:
C
0
=
Q∈W
cand(Q)
C
i+1
= C
i
∪
{I
1
⊕ I
2
for each I
1
, I
2
∈ C
i
}∪
{I
1
⊗ I
2
for each I
1
, I
2
∈ C
i
}∪
{ρ(I, K
) for each I = R(K, S) ∈ C
i
, K
⊆ K }∪
{(I) for each I ∈ C
i
}
That is, C
i+1
is obtained by considering all possible merges, splits, reductions,
and promotions of indexes in C
i
. We define closure(W)=C
k
, where k is the
smallest integer that satisfies C
k
=C
k+1
. In words, the closure of a workload W
is the set of all indexes that either are in the candidate set of a query