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

Figure 7. Edit query metadata

housing environment. The static approach as in
(Gupta, 1999; Yang, 1997, Baril, 2003), provide
framework for selecting views to materialize so
as to achieve the best combination of good query
performance and low view maintenance. As they
are static approach, they assume fix workload.
Work reported in (Gupta, 1999) solves the
view selection problem from another point of
view. The principle of the solution is the view
maintenance constraint.
The framework used to represent the queries
is AND-OR View Graph derived from the AND-
OR DAG representation as shown in figure 103,
which is a directed acyclic graph with the base
relations as sinks. However the authors study
also a special case of an AND-OR DAG view
graph, where exactly one view is used to compute
another view. The authors consider the resource
constraint is the maintenance cost, which is the
time required for the incremental maintenance of
views instead of the storage space and they refer
to the problem as the maintenance-cost view-
selection problem. This is more difficult than the
view selection problem with a disk-space con-
straint because of the non-monotonic behaviour
of the benefit function per unit of maintenance
cost. That means that the maintenance cost of a
view may decrease with selection of other views
for materialization and this can prevent using the
simple greedy algorithm for selecting the views.
Therefore, they use the notion of inverted tree

set 1 to develop a greedy heuristic algorithm called
Inverted-tree Greedy Algorithm , which delivers
a near-optimal solution for a special case of OR
view graphs. They prove that in OR view graph,
an arbitrary set O can be partitioned into inverted
tree sets such that the effective maintenance-cost
of O with respect to an already materialized set
M is greater than the sum of effective-costs of
inverted tree sets with respect to M. So the algo-
rithm will consider all the inverted tree set in the
given view graph and selects the inverted tree
set to materialize that has the most query-benefit
per unit effective maintenance-cost. Finally, they
present an optimal solution A* heuristic for the
general case of AND-OR view graphs but it takes
essentially more time than the previous one as it
is exponential in the size of the input graph.
Work reported in (Yang, 1997) provides a static
approach for selecting the appropriate set of views
from the Multiple View Processing Plan (MVPP)
which represents the query processing strategy of
the entire workload. This approach was based on a
cost model and has been implemented. However,
this work focused on view maintenance problem
without considering the query processing cost.
Moreover, common sub-expressions have been
exploited for improving view maintenance cost.
However, the cost of maintenance used is the cost
of reconstructing the view; they didn't take into
account the incremental maintenance. The weak
point of this approach is that there weren't any