Database Reference
In-Depth Information
7: end for
8: if goodness(q) ≥
goodness(CV
C
) then
9: V
C
← q
10: else
11: V
C
← CV
C
12: end if
13: return V
C
size of V
-
C
is much larger than the size of v
new
.
This means that not all views in V
-
C
have to be
dematerialized; just enough to materialize v
new
. In
the second stage of the algorithm (lines 11-14), we
use knapsack algorithm to choose a subset V
-
of
views from V
-
C
which have to be dematerialized
in order to free the necessary space for v
new
. The
views left in V
-
C
remain materialized.Algorithm
2: Benefit (
v
new
)
Materialization Decision
As it was said in the previous section, the final
decision to materialize the candidate views is
performed according to the storage space and the
existing materialized views. Our general strategy
is divided in two phases.Phase 1: While there is
enough storage space, all the candidate views
will be materialized.Phase 2: If the storage limit
is reached, a candidate view will be materialized
only if it proofs to be more beneficial than those
which are already materialized. If so, these views
should be removed to free the necessary storage
space for materializing the new candidate.
Require:
v
new
, s, V
M
1: V
−
←
ϕ
2: s
max
← totalspace(s) −
size(
v
new
)
3: for all
v
∈
V
M
do
4: if goodness(v) <
goodness(
v
new
) then
5:
V
c
−
← V
c
−
∪
{v}
6:
else
7:
s
max
← s
max
−
size(
v
)
8: end if
9: end for
10: if V
−
=
ϕ
then
11:
Replacement Policy
b ← −∞
12: else
13:
V
−
← V
c
− knapsack(V
The final decision is based on the notion of benefit
to materialize view v.benefit(v) = goodness(v) -
goodness(V
-
)
V
-
is the set of already materialized views to
be removed in order to free the necessary stor-
age space.
The Benefit(v
new
) algorithm evaluates the ben-
efit of materializing v versus the loss of removing
the views belonging to V
-
.
, s
max
)
14: b ← goodness(
v
new
) −
goodness(V
−
) - MaterCost (
v
)
15: end if
16: return b
c
The following notations are used:
•
V
M
is the set of materialized views, which
are currently stored in space s.
totalspace(s) returns the total capacity of
Replacement Algorithm
•
s, and freespace(s) indicates the available
space.
V
The Benefit algorithm is called once for every
view v
new
from the set of views V selected by
the BestViews algorithm from any query. At
the first stage (lines 4-10), the algorithm selects
all materialized views v with a lower goodness
value than v
new
and adds these views to a set of
candidate (for removal) views V
-
C
. In general the
•
C
is the subset of materialized views, V
-
C
⊂ V
M
, candidate for deletion.
V
-
•
-
is a subset of materialized views, V
-
⊂
V
-
C
, to be deleted for storing v
new
in its
place.
Search WWH ::
Custom Search