Database Reference
In-Depth Information
idea was to merge them into a new view that might be smaller than the com-
bined inputs but at the same time less ecient to answer queries. In this
section we generalize the notion of index reduction to work over materialized
views. Specifically, we exploit the fact that when a query optimizer attempts
to match a query expression
q
, it will consider not only views that subsume
q
completely but also views that subsume some of the subexpressions of
q
.As
a simple example suppose that the optimizer is matching the following query
expression:
=
R
.
a
,
R
.
b
,
S
.
c
σ
R
.
a
=
15
(
)
q
R
R
.
x
=
S
.
y
S
In this case, the view-matching engine would consider all available views
V
that subsume query expression
q
. If some view
V
matches
q
, the expres-
sion is rewritten using
V
and compensating actions (e.g.,
q
=
σ
R
.
a
=
15
(
V
)
for
R
.
x
=
S
.
y
S
). However, query optimizers would also consider views that
subsume subexpressions of
q
that omit table
S
but additionally project col-
umn
R
V
=
R
.
x
so that a compensating join can be applied, as follows:
q
=
R
.
a
,
R
.
b
,
R
.
x
σ
R
.
a
=
15
(
R
)
, we can recreate
q
from any view
V
that
matches
q
by additionally performing a join with the primary index of
S
.In
general, we can restrict an index over a view with some of its subexpressions
and then apply compensating actions to recreate the original structure. Given
V
, we denote
V
R
q
q
.
x
=
S
.
y
S
Since
q
=
q
.
a
,
q
.
b
,
S
.
c
(
)
=
ρ(
)
V
as a reduction of
V
when the following properties
hold:
1.
C
.
2. If the view-matching algorithm matches
V
for a query expression
q
,it
will attempt (and succeed) matching
V
R
for a subquery of
q
.
For eciency purposes, query optimizers restrict the subqueries that are
considered for view matching for a given query expression
q
. Most often, these
optimizers consider only subexpressions
q
with fewer joins than
q
but contain-
ing all applicable predicates in
q
that affect the tables in the subexpression
q
.
In these common scenarios, the reduction operation takes a view
IV
and a set
of tables
T
and returns a new view
(
V
R
)
≡
V
for some
SQL
fragment
C
(
V
R
)
T
)
ρ(
V
,
. For a view
V
=
(
S
,
T
,
J
,
R
,
Z
,
G
)
and
T
⊆
T
)
=
(
S
,
T
,
J
,
R
,
Z
,
G
)
T
, we define
ρ(
V
,
, where:
J
⊆
J
,
R
⊆
R
, and
Z
⊆
•
Z
, where each base table column referenced
in
J
,
R
, and
Z
refers exclusively to tables in
T
.
S
contains the subset of columns in
S
that belong to tables in
T
plus
all columns in
T
referenced in
J
•
J
,
R
R
, and
Z
Z
.
−
−
−
,
G
contains all the columns in
G
that belong to tables in
T
plus all columns in
S
−
•
If
G
=∅
S
. Otherwise,
G
=
G
=
∅
.
Search WWH ::
Custom Search