Database Reference
In-Depth Information
Denoting
V
M
=
. Using index
promotion, we now define the merging of two indexes over views as follows:
V
1
⊕
V
2
, we then have that
V
1
(
x
)
↑
V
M
=
V
M
(
x
,
a
)
V
1
(
C
1
)
⊕
V
2
(
C
2
)
=
(
V
1
(
C
1
)
↑
V
M
)
⊕
(
V
2
(
C
2
)
↑
V
M
),
where
V
M
=
V
1
⊕
V
2
That is, we first promote the original indexes to the merged view and then
perform the original index merging operation.
8.2.4.2
Unified Reduction Operator
We similarly adapt the reduction operator so that it operates over indexes on
materialized views. The extended reduction operator takes as inputs an index
on a materialized view
V
, a set of tables
T
, and a set of columns
K
as
inputs and returns a new index
(
C
)
T
,
K
)
ρ(
V
(
C
),
. For an index
V
(
C
)
, where
T
,
K
)
V
=
(
S
,
T
,
J
,
R
,
Z
,
G
)
, we define
ρ(
V
(
C
),
as follows:
T
)
is undefined, the reduction is ill-defined and we stop. Other-
wise, we obtain the reduced version of
V
,
V
=
ρ(
1. If
ρ(
V
,
T
)
.
2. We obtain
C
from
C
by first removing all columns that do not belong
to tables in
T
and then by adding all columns in
S
of
V
(this step is
analogous to
I
V
,
V
).
↑
3. If
K
C
, the reduction is ill-defined and we stop. Otherwise,
⊆
T
,
K
)
=
V
(
K
)
.
ρ(
V
(
C
),
8.2.5 Characterizing the Search Space
We can characterize the extended search space of indexes and materialized
views without
explicitly
considering materialized views by extending the ap-
proach in Section 4.3. Specifically, let
cand(
)
be the set of candidate indexes
over base tables and materialized views for query
Q
, obtained by any of the
techniques of Sections 4.1 and 8.2.1. Let
C
i
Q
(
i
≥
0
)
be a family of indexes
defined as follows:
-
VC
0
=
Q
∈
W
cand
(
Q
)
-
VC
i
+
1
=
VC
i
∪
{
V
1
(
C
1
)
⊕
V
2
(
C
2
)
for each
V
1
(
I
1
),
V
2
(
I
2
)
∈
VC
i
}∪
T
,
K
)
K
⊆
T
⊆
{
ρ(
V
(
C
),
for each
V
(
C
)
∈
VC
i
,
keys(V(C))
,
tables(V)
}∪
{
V
(
C
1
)
⊗
V
(
C
2
)
for each
V
(
C
1
),
V
(
C
2
)
∈
VC
i
}∪
VC
i
}
That is,
VC
i
+
1
is obtained by considering all possible index merges, reductions,
and promotions for indexes in
VC
i
, and index splits for indexes in
VC
i
defined
{
(
V
(
C
))
for each
V
(
C
)
∈
Search WWH ::
Custom Search