View Management Techniques and Their Application to Data Stream Management - Evolving Application Domains of Data Warehousing and Mining - page 86

V ′ 1 = V 1 − V 1, del ∪ V 1, ins

checking for relational databases (e.g., (Buneman
and Clemons, 1979; Bernstein et al., 1980; Ni-
colas, 1982)). Early works on view maintenance
were based on Select-Project-Join (SPJ) queries
expressed in relational algebra (Blakeley et al.,
1986; Hanson, 1987) or even only project queries
(Shmueli and Itai, 1984).
In the context of deductive databases, Datalog
and its variants have been used to study incremental
view maintenance (Gupta et al., 1992; Harrison
and Dietrich, 1992; Urpí and Olivé, 1992). The
counting solution presented by Gupta et al. (1992)
counts the number of alternative derivations for
a tuple in a view. The view is maintained by up-
dating the counts incrementally using rewritten
rules of the original Datalog program. However,
this method does not work for recursive Datalog
programs, as a tuple might have infinitely many
derivations in this case. The DRed algorithm
(Gupta et al., 1993; Toroslu and Kocabas, 1997)
can be used also for the maintenance of recursive
views. It first computes all the tuples which are
potentially deleted by an update of the base rela-
tions and then tries to rederive these tuples using
the new state of the database. Finally, all inserted
tuples are computed using a method similar to the
method sketched above.
The maintenance of views including aggrega-
tion has been studied especially in the field of data
warehouses. Gray et al. (1997) introduced the cube
operator and also distinguished between types of
aggregation functions: distributive, algebraic, and
holistic. Distributive aggregate functions can be
also computed by combining results from disjoint
sets. For example, MIN, MAX and SUM are dis-
tributive functions. COUNT is distributive unless
DISTINCT is used. Algebraic functions can be
computed by some combination of distributive
aggregate functions, e.g., AVG can be expressed
as SUM/COUNT. The remaining aggregate func-
tions are called holistic functions, as their value
can only be computed taking the whole relation
into account (e.g., median) (Mumick et al., 1997).
Therefore, most view maintenance methods just

This principle of using the delta relations in
a semi-naive method (Ullman, 1989) to compute
the resulting changes in the view is the basis for
most view maintenance methods which we will
discuss in more detail in the following.

classification of view
Maintenance techniques

View maintenance techniques can be distinguished
according to several criteria. So far, we have
considered only the relational model with expres-
sions in relational algebra. There are approaches
which consider other query languages and data
models for view maintenance. Furthermore,
even in the relational case, we can consider more
complex operators in the query language such as
aggregation. These issues will be discussed in
Section 3.2.1.
View maintenance approaches can be also
distinguished by the type of information they re-
quire to maintain a view. A classical example are
self-maintainable views which can be maintained
using only the update information (i.e., without ac-
cessing the original base relations). In the example
above, we could maintain the view only using the
modified tuples and the materialized view if there
is a foreign key constraint between R.cust and
C.custkey . Self-maintainable views and similar
methods will be discussed in Section 3.2.2.
Finally, the desired quality of the material-
ized view is also an important issue. Some view
maintenance approaches relax certain quality
constraints (such as the timeliness of the view
or the accuracy of the result) in order to optimize
the view maintenance process. We discuss these
methods in Section 3.2.3.

Query Language and Data Model

Algorithms related to view maintenance have been
first studied in the context of integrity constraint