192 Automated Physical Database Design and Tuning
some indexes can help implement additional requests, but we consider these
cases only to keep the overhead low. As an example, consider I
1
=R(a, b, c) and
I
2
=R(a, c). The usefulness level of I
1
with respect to I
2
is 1, and the usefulness
level of I
2
with respect to I
1
is −1. This means that all the requests whose
costs were stored in (O
0
, N
0
) or (O
1
, N
1
) for I
2
can also take advantage of I
1
.
Suppose that we create index I in the current configuration. We need to
update the values for the remaining indexes that we consider to reflect that
the current configuration contains I . Then, for each index I
j
,we:
1. Find l
j
, the usefulness level of I with respect to I
j
.
2. For each level l≤l
j
, set O
l
to min(O
l
,α
j
·N
l