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

In an analogous way,
B ( BC ,S )= w BC Bw =1 , 300 × 4=5 , 200 ,

which is the benefit of materializing BC for the computation of B , C , All ,and
BC itself. If we continue in this fashion, we will find that AB is the view to
materialize because it yields the maximum benefit. Thus, when we start the
second iteration, we have S = .

We now explain the second iteration. The benefit of materializing BC is

{ ABC , AB }

B ( BC ,S )= w BC Bw =1 , 300 + 1 , 300 = 2 , 600, corresponding to C and
BC itself since materializing BC has no effect on the nodes that reach All
through AB because they can be computed from AB at a cost of 400. For
example, B can be computed from AB at cost 400; therefore, materializing
BC yields no benefit for the computation of B . On the other hand, the benefit

of materializing B is B ( B ,S )= w B Bw = 340

× 2sinceboth B and All can

be computed from AB at a cost Bw = 400 − 60 each. Also note that the benefit

of materializing C is B ( C ,S )= w C Bw =1 , 960 + 400

− 40 = 2 , 320 since

the benefit for computing All is just 400 40 because All can be computed

from AB at a cost of 400. We will eventually choose BC in the second iteration
with a benefit of 2 , 600.
Finally, the three views to materialize will be AB , BC ,and AC , with a total
benefit of 10,100. The following table shows the complete computation. Each
cell in the table shows the benefit of selecting a given view in an iteration.

−

View First Iteration Second Iteration Third Iteration

AB 1,600 × 4 = 6,400

AC 1,100 × 4 = 4,400 1,100 × 2 = 2,200 1,100 × 1 = 1,100

BC 1,300 × 4 = 5,200 1,300 x 2 = 2,600

A 1,980 × 2 = 3,960 380 × 2 = 760 380 × 2 = 760

B 1,940 × 2 = 3,880 340 × 2 = 680 340 × 2 = 680

C 1,960 × 2 = 3,920 1,960 + (400 - 40) = 2,320 660 + 360 = 1,020

All 1,999 × 1 = 1,999 399 × 1 = 399 399 × 1 = 399

It can be proved that the benefit of this greedy algorithm is at least 63%
of the benefit of the optimal algorithm. On the other hand, even this is a
classic algorithm, pedagogically interesting for presenting the problem, a clear
drawback is that it does not consider the frequency of the queries over each
view. Thus, in our example, even though the sum of the benefit is maximum,
nothing is said about the frequency of the queries asking for A or B .This
drawback has been addressed in several research papers.