Handling Materialized Views - Automated Physical Database Design and Tuning - page 155

mergeViews (C:candidate views)
return merged views
1 R=C
2

while |R| > 1

M = { M1 ⊕ M2 : M1, M2 ∈ R and "M1 ⊕ M2 is not too large" }
// V m is too large if size ( V m )>α · V ∈ ancestors( V m ) size ( V ) ,
for 1 ≤ α ≤ 2

3

if (M = ∅ ) break

4

R=R ∪ M 5

foreach view (M1 ⊕ M2) ∈ M

6

R=R- { M1, M2 }

7

return R ∪ C

8

FIGURE 8.1 Generation of a controlled subset of merged views.

define the ancestors of a materialized view V to be all the views in
the original candidate set that were merged together to produce V .
The algorithm to produce a restricted set of merged views is given in
Figure 8.1. The idea is to keep adding merged views to the subset as
long as the increase in size is not large. Note that it is possible for a
merged materialized view generated in line 3 to be merged again in a
subsequent iteration of the outer loop (lines 2-7). This allows more than
two views in M to be combined into one merged view even though the
merging is done pairwise. Although the number of new merged views
explored by this algorithm can be exponential in the size of C in the
worst case, much fewer merged materialized views are explored in prac-
tice because of the size restriction in line 3. Note that the set of merged
views returned by the algorithm does not depend on the exact sequence
in which views are merged.

8.5 Summary

• After indexes, materialized views are the most common redundant data

structure that is used in database systems to improve query perfor-
mance.

• In addition to speeding up queries, materialized views use storage and

need to be maintained for UPDATE statements.

• The traditional physical database design problem can be generalized to

consider the space of indexes over base tables and materialized views.
Although different components in techniques that handle indexes need
to be extended to handle materialized views, the general architecture of
existing solutions remains unchanged.