Database Reference
In-Depth Information
bounds in selecting the view. That's mean that they
didn't take into account neither the storage space
constraint. They suppose that there is no limit to
materialize new view but this is not always pos-
sible in the real application.
Our Multi View Materialization Graph is close
to the Multi View Processing Plan that has been
described in (Yang, 1997). However, the evalua-
tion cost of the query is not estimated according
to the operation type. It seems that the estimated
cost of a join is estimated as the same as the cost
of a selection.
The Microsoft Research team presents another
static approach reported in (Agrawal, 2000) by
considering the storage space constraint. This
approach deals with the issue of selecting both
views and indexes to be materialized in order
to optimize the physical design of the workload
by taking into account the interaction between
indexes and materialized views. Once a set of
candidate indexes and candidate materialized
views has been chosen, the system runs the con-
figuration enumeration module to determine the
ideal physical design, called a configuration. The
configurations considered by the configuration
enumeration module are compared for quality
by taking into account the expected impact of
the proposed configurations on the sum of the
cost of queries in the workload. The configura-
tion simulation and cost estimation module is
responsible for providing this support. The goal
of candidate materialized view selection is to
eliminate materialized views that are syntactically
relevant for one or more queries in the workload
but are never used in answering any query, from
entering the configuration enumeration phase in
order to reduce the search space. However, one
of the negative points for this approach is that it
doesn't take the maintenance cost into account
which can efficiently change the configuration.
In (Baril, 2003) the view selection is decided
under space constraint. The framework chosen to
represent the queries workload is The Multi View
Materialization Graph (MVMG) which is similar
to the AND-OR DAG in multi query optimization
(Roy, 2000). Each view of the query tree is associ-
ated to a level. The view selection problem here is
solved in two phases, the first phase depends on
local optimization by taking each query and pre-
select set of views which belong to the same level
and which reduce the query processing cost if it is
materialized without increasing significantly the
view maintenance. While the second phase is the
global optimisation where all the result collected
from the first phase will be merged together and
filtered according to its global benefit.
The authors present two polynomial algorithms
to provide the solution based on the balance be-
tween query processing and maintenance cost.
The first algorithm finds the level of each query
in the workload which provide the minimal sum of
query processing and view maintenance cost. The
treatment is done in two main steps. The first one
carries out a pre-selection of beneficial views. The
second step computes the total cost (query plus
maintenance) for each level of the query graph
and selects the one which has the minimal sum of
query processing and view maintenance cost.
In (Theodoratos, 2001) the dynamic data ware-
house design is modeled as search space problem.
Rules for pruning the search space have been pro-
posed. The first rule relies on favoring the query
rewriting that uses views already materialized.
The second one modifies the previous rule to favor
common sub expression. However, their view
selection algorithm is still in exponential time.
Besides, neither implementation and/or evaluation
of their method have been performed.
The first dynamic approach dealing with the
view materialization in data warehousing was
DynaMat (Kotidis, 1999). This system aimed to
unify the view selection and the view mainte-
nance problems. The principle of this system is
monitoring constantly the incoming queries and
materializing their query results given the space
constraint. During the update only the most ben-
eficial subset of materialized views are refreshed
within a given maintenance window. It provides a
Search WWH ::
Custom Search