Database Reference
In-Depth Information
if it can be computed using solely data in the latter
view.An aggregation query can be answered using
any of its ancestors, i.e., the views it transitively
depends on. With the lattice model at hand, the
benefit of materializing a view v wrt. S , the set
of views already selected, is defined as the gain
in terms of costs:
The interrelationship modeling is further
extended to so-called AND-OR view graphs in
(Gupta, 1997).A lattice is then a special case called
OR view graph, in which each AND-arc consists
of only one edge. Maintenance costs can be incor-
porated into the framework either as constraints
(Gupta and Mumick, 2005), or in the optimization
goal (Gupta, 1997). Gupta and Mumick (2005)
present a relatively complete summary of various
aspects of the general framework.
It is shown that the benefit measure of the
result of the greedy algorithm is at least 63%
of the benefit of the optimal solution without
index selection (Harinarayan et al., 1996), and
46% with index selection (Gupta et al., 1997).
Interestingly, Shukla et al. (1998) show that the
Benefit-Per-Unit-Space (BPUS) greedy strategy
is equivalent to a simpler heuristic algorithm
which picks the view with the smallest size at
each iteration step.
Another line of work (Theodoratos and Sellis,
1997, 1999; Theodoratos et al., 2001; Yang et
al., 1997; Baralis et al., 1997) is influenced by
multiple query optimization techniques (Sellis,
1988; Roy et al., 2000), with the aim of finding
reusable common sub-expressions of queries.
Theodoratos and Sellis (1997) model the problem
as a state space search problem, where each state
is a multi-query graph specifying Select-Join que-
ries. State transitions achieved by cutting edges
or merging nodes represent local modifications of
the candidate views selected. Though the exhaus-
tive search gives the optimal view set regarding
both query evaluation and maintenance costs, it
is exponential and a storage limit is not taken into
account. The work is extended in (Theodoratos
and Sellis, 1999) to incorporate storage limit, and
in (Theodoratos et al., 2001) to allow for projec-
tion in queries.
Yang et al. (1997) consider a slightly broader
range of queries including aggregation. Their
approach proceeds in two steps. The first step
å
BvS
(, )
=
ax(, (,)
0
E wS
-
Ewv
( ,))
wv
where is the partial order represented in the
lattice, E(w;v) is the evaluation cost of query w
using view v , and E(w;S) is the minimal evaluation
cost of w using S , i.e., E(w; S) = min u S {E(w; u)}.
A greedy algorithm is then adopted to select the
most beneficial view per storage space (Benefit-
Per-Unit-Space) up to the storage limit.
Gupta et al. (1997) extend the framework to
accommodate index selection while the query
workload is extended to allow both aggregation
and selection (also called slice (Gray et al., 1997)).
An index, regarded as a special view, is selected
only after the view it is defined over is selected.
A greedy algorithm is employed to choose at each
step a physical structure, either a view or an index,
to maximize the benefit per unit space.
In the above case when slice queries are
considered, the lattice is no longer sufficient to
express the interrelationship of candidate views.
A bipartite query-view graph is used in (Gupta
et al., 1997), in which there are a set of edges
between a query and a view, each labeled with
the evaluation of the query against the view using
a different index.
There is a trade-off between distribution of
storage space between views and indices if there
are global space constraints. Bellatreche et al.
(2000) introduce a procedure that iteratively ap-
proximates a solution and in the dynamic case
maintains it as query workloads change and data
is added or removed.
Search WWH ::




Custom Search