View Selection and Materialization - Data Warehousing Design and Advanced Engineering Applications - page 121

Figure 3. Example of view subsumption

didate views for materialization. The decision for
materializing them definitely is done according to
the available storage space and regarding also the
benefit of already materialized views. This is the
task of the replacement algorithm, discussed in the
second part. The algorithm requires a set of source
relations V R to answer q. The algorithm starts at
the top of the query graph of q, but recursively
builds from the bottom up a set of child nodes
CV C containing the best sub queries (nodes) for
query q. At each iteration, the goodness of query
q, is compared to the goodness of its candidate
views CV C . The result of the comparison is as-
signed to V C .
For simplification we use the following nota-
tions:

costly views in order to save work of frequently
asked queries.
Furthermore, views may be selected for mate-
rialization even if it is the first time the query is
executed. This is because some of its views could
be shared with other queries, which have already
been processed.
Let us illustrate this heuristic by considering
the query Q depicted in Figure 3, which includes
four views. Let us assume that V 3 is already ma-
terialized. Then, materializing V 1 or V 2 will not
reduce the query processing time of Q.

• q represents the query as well as the view

defined by this query.
children(q) is the set of direct children of •

query q.

Complexity of the BestViews Algorithm

The algorithm performs a simple depth-first tra-
versal of the query tree. Therefore, its complexity
is O(n) where n is the number of nodes. Compared
to our previous work, LevelSelection (Baril, 2003),
the complexity of the BestViews(q) algorithm
is similar to LevelSelection algorithm. Both the
methods guarantee that no selected view can be
subsumed by another one. However, BestViews(q)
provides a better solution than LevelSelection
in sense of goodness criteria (i.e., TotalCost in
LevelSelection) since this algorithm was able to
find only views to materialize at the same level
of the query tree.Algorithm 1 BestViews(q)

OVERVIEW OF THE VIEW
SELECTION ALGORITHMS

We present in the first part of this section the view
selection algorithm, which allows selecting the
best views for materialization. In the second part,
we will discuss the replacement policy of already
materialized views.

Require: q, V R ≠ ϕ
1: if q ∈ V R then
2: V C ← {q}
3: else
4: CV C ← ∅
5: for all q' ∈ children(q) do
6: CV C ← ∪ BestViews(q')

Pre-Selection Algorithm

The BestViews(q) algorithm, which is described
below, provides for a given query q a set of can-