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

All 1

A 20 B 60 C 40

AB 400 AC 900 BC 700

ABC 2,000

Fig. 7.9 Dependency lattice. Initially, the only view materialized is ABCD

The set S contains the views already materialized. In each one of the k itera-
tions, the algorithm computes the benefit produced by the materialization of
each of the views not yet in S . The one with the maximum benefit is added
to S , and a new iteration begins.
Let us apply the algorithm to the lattice in Fig. 7.9 . In addition to the
node label, beside each node we indicate the cost of the view that the node
represents. Assume that we can materialize three views and that the bottom
view is already materialized.
Let us show how to select the first view to materialize. We need to compute
the benefit of materializing each view, knowing that S = { ABC } .Westart
with node AB , which is a good candidate, since it offers a cost reduction of
1,600 units for each view that depends on it. For example, node A depends
on AB . Currently, computing A has cost 2,000 since this is performed from
ABC . If we materialize AB , the cost of computing A will drop to 400.
The benefit of materializing AB given S is given by
B ( AB ,S )= w AB Bw.

Thus, for each view w covered by AB , we compute C ( ABC ) −C ( AB ), because

ABC is the only materialized view when the algorithm begins. That is,
C ( ABC ) − C ( AB ) is the benefit of materializing AB for each view covered

by AB . For example, to compute B without materializing AB , we would need
to scan ABC at cost 2,000. With AB being materialized, this reduces to 400.
The same occurs with all the views that have a path to All that passes through
AB ,thatis, A , B , All ,and AB itself. For C , AC ,and BC , the materialization
of AB is irrelevant. Then,

B ( AB ,S )=1 , 600 + 1 , 600 + 1 , 600 + 1 , 600=6 , 400 .