Physical Data Warehouse Design - Data Warehouse Systems: Design and Implementation - page 248

The algorithm also requires knowing the expected number of rows for each
view in the lattice. Finally, it is assumed that the lowest node in the lattice
(typically, the base fact table) is always materialized.
The goal of the algorithm is to minimize the time taken to evaluate a
view, constrained to materialize a fixed number of views regardless of the
space available, a problem known to be NP-complete. The greedy algorithm
we present below uses a heuristic that selects a sequence of views such that
each choice in this sequence is the best, given what was selected before.
Let us call C ( v ) the cost of view v , k the number of views to materialize,
and S a set of materialized views. The benefit of materializing a view v not
in S , relative to the materialized views already in S , is denoted B ( v,S ), and
it is computed as follows:

View Materialization Benefit Algorithm
INPUT: A lattice L , each view node labeled with its expected number of rows
Anode v , not yet selected to materialize
Aset S containing the nodes already selected to materialize
OUTPUT: The benefit of materializing v given S
BEGIN
For each view w v , w ∈ S , Bw is computed by
Let u be the view of least cost in S such that w u
If C ( v ) <C ( u ) , Bw = C ( u ) − C ( v ) ,otherwise Bw =0

B ( v,S )= wv Bw
END

The algorithm above works as follows. Given a view w (not yet material-
ized), let us denote u the (materialized) view of minimum cost from which w
can be computed. Given a candidate view v selected for materialization, for
each view w that depends on v , the benefit of materializing w (denoted Bw )
is computed as the difference between the costs of v and u . If computing w
from v is more expensive than doing it from u ( C ( v ) >C ( u )), materializing
the candidate view does not benefit the computation of w ( Bw =0).The
algorithm iterates over all views w , and finally, the benefit of materializing v

is the sum of all individual benefits ( wv Bw ).
The view selection algorithm computes, in each iteration, the view v whose
materialization gives the maximum benefit. The scheme of the algorithm is
given next:

View Selection Algorithm
INPUT: A lattice L ,eachviewnode v labeled with its expected number of rows
The number of views to materialize, k
OUTPUT: The set of views to materialize
BEGIN
S = The bottom view in L}

FOR i =1TO k DO
Select a view v not in S such that B ( v,S ) is maximized
S = S ∪{v}
END DO
S is the selection of views to materialize
END

{