Making views self-maintainable for data warehousing.
A data warehouse stores materialized views over data from one or more sources in order to provide fast access to the integrated data, regardless of the availability of the data sources. Warehouse views need to be maintained in response to changes to the base data in the sources. Except for very simple views, maintaining a warehouse view requires access to data that is not available in the view itself. Hence, to maintain the view, one either has to query the data sources or store auxiliary data in the warehouse. We show that by using key and referential integrity constraints, we often can maintain a select-project-join view without going to the data sources or replicating the base relations in their entirety in the warehouse. We derive a set of auxiliary views together are  self-maintainablethey can be maintained without going to the data sources or replicating all base data. In addition, our technique can be applied to simplify traditional materialized view maintenance by exploiting key and referential integrity constraints.
Introduction
The problem of materialized view maintenance has
received increasing attention recently [6, 7, 11], particularly
due to its application to data warehousing
[3, 14]. A view is a derived relation defined in
terms of base relations. A view is said to be materialized
when it is stored in the database, rather
than computed from the base relations in response to
queries. The materialized view maintenance problem
is the problem of keeping the contents of the stored
view consistent with the contents of the base relations
as the base relations are modified.
Data warehouses store materialized views in order
to provide fast access to information that is integrated
from several distributed data sources [3]. The data
sources may be heterogeneous and/or remote from the
warehouse. Consequently, the problem of maintaining
a materialized view in a data warehouse differs from
the traditional view maintenance problem where the
view and base data are stored in the same database.
In particular, when changes are reported by one data
This work was supported by Rome Laboratories under Air
Force Contract F30602-94-C-023 and by equipment grants from
Digital and IBM Corporations.
source it may be necessary to access base data from
other data sources in order to maintain the view [9].
For any view involving a join, maintaining the view
when base relations change may require accessing base
data, even when incremental view maintenance techniques
are used [5, 8]. For example, for a view R 1 S,
when an insertion to relation R is reported it is usually
necessary to query S in order to discover which tuples
in S join with the insertion to R. In the warehousing
scenario, accessing base data means either querying
the data sources or replicating the base relations in the
warehouse. The problems associated with querying
the data sources are that the sources may periodically
be unavailable, may be expensive or time-consuming
to query, and inconsistencies can result at the warehouse
unless care is taken to avoid them through the
use of special maintenance algorithms [14]. The problems
associated with replicating base relations at the
warehouse are the additional storage and maintenance
costs incurred. In this paper we show that for many
views, including views with joins, if key and referential
integrity constraints are present then it is not necessary
to replicate the base relations in their entirety at
the warehouse in order to maintain a view. We give
an algorithm for determining what extra information,
called auxiliary views, can be stored at a warehouse
in order to maintain a select-project-join view without
accessing base data at the sources. The algorithm
takes key and referential integrity constraints into ac-
count, which are often available in practice, to reduce
the sizes of the auxiliary views. When a view together
with a set of auxiliary views can be maintained at the
warehouse without accessing base data, we say the
views are self-maintainable.
Maintaining materialized views in this way is especially
important for data marts-miniature data warehouses
that contain a subset of data relevant to a particular
domain of analysis or geographic region. As
more and more data is collected into a centralized
data warehouse it becomes increasingly important to
distribute the data into localized data marts in order
to reduce query bottlenecks at the central warehouse.
When many data marts exist, the cost of replicating
entire base relations (and their changes) at each data
mart becomes especially prohibitive.
1.1 Motivating example
We start with an example showing how the amount
of extra information needed to maintain a view can
be significantly reduced from replicating the base relations
in their entirety. Here we present our results
without explanation of how they are obtained. We
will revisit the example throughout the paper.
Consider a database of sales data for a chain of
department stores. The database has the following
relations.
store(store id, city, state, manager)
sale(sale id, store id, day, month,
line(line id, sale id, item id,
sales price)
item(item id, item name, category,
supplier name)
The first (underlined) attribute of each relation is a
key for the relation. The store relation contains the
location and manager of each store. The sale relation
has one record for each sale transaction, with the store
and date of the sale. A sale may involve several items,
one per line on a sales receipt, and these are stored in
the line relation, with one tuple for every item sold
in the transaction. The item relation contains information
about each item that is stocked. We assume
that the following referential integrity constraints
hold: (1) from sale.store id to store.store id, (2)
from line.sale id to sale.sale id, and (3) from
line.item id to item.item id. A referential integrity
constraint from S:B to R:A implies that for
every tuple s 2 S there must be a tuple r 2 R such
that
Suppose the manager responsible for toy sales in the
state of California is interested in maintaining a view
of this year's sales: "all toy items sold in California in
1996 along with the sales price, the month in which
the sale was made, and the name of the manager of
the store where the sale was made. Include the item
id, the sale id, and the line id."
SELECT store.manager, sale.sale id, sale.month,
item.item id, item.item name, line.line id,
line.sales price
FROM store, sale, line, item
WHERE store.store
line.sale id and
line.item
The question addressed in this paper is: Given a view
such as the one above, what auxiliary views can be
materialized at the warehouse so that the view and
auxiliary views together are self-maintainable?

Figure

shows SQL expressions for a set of
three auxiliary views that are sufficient to maintain
view cal toy sales for insertions and deletions to
each of the base relations, and are themselves self-
maintainable. In this paper we give an algorithm
for deriving such auxiliary views in the general case,
along with incremental maintenance expressions for
maintaining the original view and auxiliary views.
Materializing the auxiliary views in Figure 1 repre-
store AS
SELECT store id, manager
FROM store
SELECT sale id, store id, month
store id IN (SELECT store id FROM aux store)
item AS
SELECT item id, item name
FROM item

Figure

1: Auxiliary Views for Maintaining the
cal toy sales View
sents a significant savings over materializing the base
relations in their entirety, as illustrated in Table 1.
Suppose that each of the four base relations
contain the number of tuples listed in the first
column of Table 1. Assuming that the selectivity
of store.state="CA" is .02, the selectivity
of sale.year=1996 is .25, the selectivity of
item.category="toy" is .05, and that distributions
are uniform, the number of tuples passing local selection
conditions (selection conditions involving attributes
from a single relation) are given in the second
column of Table 1. A related proposal by Hull and
Zhou [10] achieves self-maintainability for base relation
insertions by pushing down projections and local
selection conditions on the base relations and storing
at the warehouse only those tuples and attributes of
the base relations that pass the selections and projec-
tions. Thus, their approach would require that the
number of tuples appearing in the second column of

Table

1 is stored at the warehouse to handle insertions.
We improve upon the approach in [10] by also taking
key and referential integrity constraints into ac-
count. For example, we don't need to materialize any
tuples from line, because the key and referential integrity
constraints guarantee that existing tuples in
line cannot join with insertions into the other rela-
tions. Likewise we can exclude tuples in sale that
do not join with existing tuples in store whose state
is California, because we are guaranteed that existing
tuples in sale will never join with insertions to store.
Using our approach can dramatically reduce the number
of tuples in the auxiliary views over pushing down
selections only. The number of tuples required by our
approach to handle base relation insertions in our example
appears in the third column of Table 1.
Tuples in Tuples Passing Tuples in Auxiliary
Base Relation Base Relation Local Selection Conditions Views of Figure 1
store
sale 80,000,000 20,000,000 400,000
line 800,000,000 800,000,000 0
item 1,000 50 50
Total 880,003,000 820,000,090 400,090

Table

1: Number of Tuples in Base Relations and Auxiliary Views
We can similarly use key constraints to handle deletions
to the base relations without all the base relations
being available. We can determine the effects
of deletions from sale, line, and item without referencing
any base relations because cal toy sales includes
for these relations. We simply join the
deleted tuples with cal toy sales on the appropriate
key. Even though the view does not include a key for
store, store is joined to sale on the key of sale, so
the effect of deletions from store can be determined
by joining the deleted tuples with sale and joining
the result with cal toy sales on the key of sale.
Now consider updates. If all updates were treated
as deletions followed by insertions, as is common in
view maintenance, then the properties of key and referential
integrity constraints that we use to reduce
the size of auxiliary views would no longer be guaranteed
to hold. Thus, updates are treated separately
in our approach. Note that in data warehousing environments
it is common for certain base relations not to
be updated (e.g., relations sale and line may be append
only). Even when base relations are updateable,
it may be that not all attributes are updated (e.g.,
we don't expect to update the state of a store). If
updates to the base relations in our example cannot
change the values of attributes involved in selection
conditions in the view, then the auxiliary views of Figure
are sufficient (even if attributes appearing in the
view may be updated). If, on the other hand, updates
to sale may change the year (for example), then an
additional auxiliary view:
line AS
line id, sale id, item id, sales price
FROM line
WHERE item id IN (SELECT item id FROM aux item)
would need to be materialized, which would have
40,000,000 tuples. That is, we would need to store
all purchases of items whose category is "toy," in case
the year of the corresponding sales record is changed
later to 1996. Further, if updates may change the category
of an item to "toy", we would need to keep all
of the line relation in order to maintain the view.
In practice we have found that the attributes appearing
in selection conditions in views tend to be attributes
that are not updated, as in our example. As
illustrated above and formalized later on, when such
updates do not occur, much less auxiliary information
is required for self-maintenance. Thus, exploiting
knowledge of permitted updates is an important feature
of our approach.
1.2 Self-Maintenance
Self maintenance is formally defined as follows.
Consider a view V defined over a set of base relations
R. Changes, ffi R, are made to the relations in R
in response to which view V needs to be maintained.
We want to compute ffi V , the changes to V , using as
little extra information as possible. If ffi V can be computed
using only the materialized view V and the set
of changes ffi R, then view V alone is self-maintainable.
If view V is not self-maintainable, we are interested in
finding a set of auxiliary views A defined on the same
relations as V such that the set of views fV g[A is
self-maintainable. Note that the set of base relations
R forms one such set of auxiliary views. However, we
want to find more "economical" auxiliary views that
are much smaller than the base relations. The notion
of a minimal set of auxiliary views sufficient to maintain
view V is formalized in Section 3.
A more general problem is to make a set
Vn of views self-maintainable, i.e., find auxiliary
views A such that A[V is self-maintainable. Simply
applying our algorithm to each view in V is not
since opportunities to "share" information
across original and auxiliary views will not be
recognized. That is, the final set A[V may not be
minimal. We intend to investigate sets of views as
future work.
1.3 Paper outline
The paper proceeds as follows. Section 2 presents
notation, terminology, and some assumptions. Section
3 presents an algorithm for choosing a set of auxiliary
views to materialize that are sufficient for maintaining
a view and are self-maintainable. Section 4
shows how the view is maintained using the auxiliary
views. Section 5 explains that the set of auxiliary
views is itself self-maintainable. Related work appears
in Section 6.
Preliminaries
We consider select-project-join (SPJ) views; that is,
views consisting of a single projection followed by a
single selection followed by a single cross-product over
a set of base relations. As usual, any combination of
selections, projections, and joins can be represented in
this form. We assume that all base relations have
but that a view might contain duplicates due to the
projection at the view. In this paper we assume single-attribute
and conjunctions of selection conditions
(no disjunctions) for simplicity, but our results carry
over to multi-attribute keys and selection conditions
with disjunctions. In Section 3 we will impose certain
additional restrictions on the view but we explain how
those restrictions can be lifted in the full version of the
paper [12]. We say that selection conditions involving
attributes from a single relation are local conditions;
otherwise they are join conditions. We say that attributes
appearing in the final projection are preserved
in the view.
In order to keep a materialized view up to date,
changes to base relations must be propagated to the
view. A view maintenance expression calculates the
effects on the view of a certain type of change: in-
sertions, deletions, or updates to a base relation. We
use a differential algorithm as given in [5] to derive
view maintenance expressions. For example, if view
then the maintenance expression calculating
the effect of insertions to R (4R) is
represents the tuples to insert
into V as a result of 4R.
Since in data warehousing environments updates
to certain base relations may not occur, or may not
change the values of certain attributes, we define each
base relation R as having one of three types of updates,
depending on how the updateable attributes are used
in the view definition:
ffl If updates to R may change the values of attributes
involved in selection conditions (local or
join) in the view, then we say R has exposed updates

ffl Otherwise, if updates to R will not change the values
of attributes involved in selection conditions
but may change the values of preserved attributes
(attributes included in the final projection), then
we say R has protected updates.
ffl Otherwise, if updates to R will not change the
values of attributes involved in selection conditions
or the values of preserved attributes, then
we say R has ignorable updates.
Ignorable updates cannot have any affect on the view,
so they do not need to be propagated. From now on
we consider only exposed and protected updates. Exposed
updates could cause new tuples to be inserted
into the view or tuples to be deleted from the view, so
we propagate them as deletions of tuples with the old
values followed by insertions of tuples with the new
values. For example, given a view
if the value of R:A for a tuple in R is changed from
9 to 10 then new tuples could be inserted into V as
a result. Protected updates can only change the attribute
values of existing tuples in the view; they cannot
result in tuples being inserted into or deleted from
the view. We therefore propagate protected updates
separately. An alternate treatment of updates is considered
in Section 4.1.2.
In addition to the usual select, project, and join
symbols, we use ?! to represent semijoin, ] to represent
union with bag semantics, and \Gamma \Delta to represent
minus with bag semantics. We further assume that
project (-) has bag semantics. The notation 1X represents
an equijoin on attribute X, while 1 key(R) represents
an equijoin on the key attribute of R, assuming
this attribute is in both of the joined relations. Insertions
to a relation R are represented as 4R, deletions
are represented as 5R, and protected updates
are represented as -R. Tuples in -R have two attributes
corresponding to each of the attributes of R:
one containing the value before update and another
containing the value after update. We use - old to
project the old attribute values and - new to project
the new attribute values.
3 Algorithm for determining auxiliary
views
We present an algorithm (Algorithm 3.1 below)
that, given a view definition V , derives a set of auxiliary
views A such that view V and the views in A
taken together are self-maintainable; i.e., can be maintained
upon changes to the base relations without requiring
access to any other data. Each auxiliary view
is an expression of the form:
That is, each auxiliary view is a selection and a projection
on relation R i followed by zero or more semijoins
with other auxiliary views. It can be seen that the
number of tuples in each AR i is never larger than the
number of tuples in R i and, as we have illustrated in
Section 1.1, may be much smaller. Auxiliary views of
this form can easily be expressed in SQL, and they
can be maintained efficiently as shown in [12].
Intuitively, the first part of the auxiliary view ex-
pression, (-oeR i ), results from pushing down projections
and local selection conditions onto R i . Tuples
in R i that do not pass local selection conditions cannot
possibly contribute to tuples in the view; hence
they are not needed for view maintenance and therefore
need not be stored in AR i at the warehouse. The
semijoins in the second part of the auxiliary view expression
further reduce the number of tuples in AR i
by restricting it to contain only those tuples joinable
with certain other auxiliary views. In addition, we
will show that in some cases the need for AR i can be
eliminated altogether.
We first need to present a few definitions that are
used in the algorithm.
Given a view V , let the join graph G(V ) of
a view be a directed graph hR; Ei. R is the
set of relations referenced in V , which form
the vertices of the graph. There is a directed
edge contains
a join condition R i and A is
a key of R j . The edge is annotated with RI if
there is a referential integrity constraint from
R i :B to R j :A.
We assume for now that the graph is a forest (a set
of trees). That is, each vertex has at most one edge
leading into it and there are no cycles. This assumption
still allows us to handle a broad class of views
that occur in practice. For example, views involving
chain joins (a sequence of relations R
where the join conditions are between a foreign key
of R i and a key of R n) and star joins
(one relation R 1 , usually large, joined to a set of relations
usually small, where the join conditions
are between foreign keys in R 1 and the keys of
In addition, we assume
that there are no self-joins. We explain how each of
these assumptions can be removed in [12].
The following definition is used to determine the set
of relations upon which a relation R i depends-that
is, the set of relations R j in which (1) a foreign key in
R i is joined to a key of R j , (2) there is a referential
integrity constraint from R i to R j , and (3) R j has
protected updates.
with RI and R j does not have exposed updates g
determines the set of auxiliary views to
which R i is semijoined in the definition of the auxiliary
view AR i for R i , given above. The reason for
the semijoins is as follows. Let R j be a member of
G). Due to the referential integrity constraint
from R i to R j and the fact that the join between R i
and R j is on a key of R j , each tuple t i 2 R i must join
with one and only one tuple does
not pass the local selection conditions on R j . Then
cannot contribute to tuples in the
view. Because updates to R j are protected (by the
definition of Dep(R never
contribute to tuples in the view, so it is not necessary
to include t i in AR i at the warehouse. It is sufficient
to store only those tuples of R i that pass the local selection
conditions on R i and join with a tuple in R j
that passes the local selection conditions on R j (i.e.,
the semijoin condition is the
same as the join condition between R i and R j in the
view). That R i can be semijoined with AR j , rather
than oeR j , in the definition of AR i follows from a similar
argument applied inductively.
The following definition is used to determine the
set of relations upon which relation R i transitively depends

(R is the transitive closure of Dep(R
(R is used to help determine whether it
is necessary to store AR i at the warehouse in order to
maintain the view or whether AR i can be eliminated
altogether. Intuitively, if Dep (R includes all relations
referenced in view V except R i , then AR i is not
needed for propagating insertions to any base relation
onto V . The reason is that the key and referential integrity
constraints guarantee that new insertions into
the other base relations can join only with new insertions
into R i , and not with existing tuples in R i . This
behavior is explained further in Section 4.
line
RI
RI
RI
store
item

Figure

2: Join Graph G(cal toy sales)
The following definition is used to determine the
set of relations with which relation R i needs to join so
that the key of one of the joining relations is preserved
in the view (where all joins must be from keys to foreign
keys). If no such relation exists then Need(R
includes all other relations in the view.
OE if the key of R i is preserved in
if the key of R i is not preserved
in V but there is an R j such
that
otherwise
Note that because we restrict the graph to be a forest,
there can be at most one R j such that e(R j ; R i ) is in
used to help determine whether
it is necessary to store auxiliary views. In particular,
an auxiliary view AR j is necessary if R j appears in
the Need set of some R i . Intuitively, if the key of R i
is preserved in view V , then deletions and protected
updates to R i can be propagated to V by joining them
directly with V on the key of R i . Otherwise, if the
key of R i is not preserved in V but R i is joined with
another relation R j on the key of R i and V preserves
the key of R j , then deletions and protected updates
to R i can be propagated onto V by joining them first
with R j , then joining the result with V . In this case R j
is in the Need set of R i , and hence AR j is necessary.
More generally, if the key of R i is not present in V
but R i joins with R j on the key of R i , then auxiliary
views for R j and each of the relations in Need(R
are necessary for propagating deletions and protected
updates to R i . Finally, if none of the above conditions
hold then auxiliary views for all relations referenced in
other than R i are necessary.
To illustrate the above definitions we consider again
the cal toy sales view of Section 1.1. Figure 2 shows
the graph G(cal toy sales). The
Need functions for each of the base relations are given
in

Table

2. Assume for now that each base relation has
protected updates.
Algorithm 3.1 appears in Figure 3. We will
explain how the algorithm works on our running
cal toy sales example. The auxiliary views generated
by the algorithm are exactly those given in Figure
1 of Section 1.1. They are shown in relational
algebra form in Table 3.
Algorithm 3.1
Input
View V .
Output
Set of auxiliary view definitions A.
Method
Let R be the set of relations referenced in V
Construct graph G(V )
for every relation R i
Construct (R
for every relation R i
(R
R such that R i
then AR i is not needed
else
P is the set of attributes in R i that are preserved in V , appear in join conditions, or are
a key of R i ,
S is the strictest set of local selection conditions possible on R i ,
C l is the join condition R i a key of R k l , and
Figure

3: Algorithm to Derive Auxiliary Views

Table

2: Dep and Need Functions for Base Relation

For each relation R i referenced in the view V , the
algorithm checks whether Dep (R includes every
other relation referenced in V and R i is not in
any relation R j referenced in V . If
so, it is not necessary to store any part of R i in order
to maintain V . Relation line is an example where an
auxiliary view for the relation is not needed.
Otherwise, two steps are taken to reduce the
amount of data stored in the auxiliary view AR i for
R i . First, it is possible to push down on R i local selection
conditions (explicit or inferred) in the view so
store id; manager oe state=CA store
oe year=1996 sale) ?! store id A store

Table

3: Auxiliary Views for Maintaining the
cal toy sales View
that tuples that don't pass the selection conditions
don't need to be stored; it is also possible to project
away all attributes from R i except those that are involved
in join conditions, preserved in V , or are a key
of R i . Second, if Dep(R i ; G) is not empty, it is possible
to further reduce the tuples stored in AR i to only
those tuples of R i that join with tuples in other auxiliary
views ARk where R k is in Dep(R i ; G). The auxiliary
view for sale is an example where both steps
have been applied. A sale is restricted by the semijoin
with A store to include only tuples that join with tuples
passing the local selection conditions on store.
The auxiliary views for store and item are examples
where only selection and projection can be applied.
Although view definitions are small and running
time is not crucial, we observe that the running time
of Algorithm 3.1 is polynomial in the number of re-
lations, and therefore is clearly acceptable. We now
state a theorem about the correctness and minimality
of the auxiliary views derived by Algorithm 3.1.
Theorem 3.1 Let V be a view with a tree-structured
join graph. The set of auxiliary views A produced
by Algorithm 3.1 is the unique minimal set of views
that can be added to V such that fV g[A is self-
maintainable. 2
The proof of Theorem 3.1 is given in [12]. By minimal
we mean that no auxiliary view can be removed
from A, and it is not possible to add an additional
selection condition or semijoin to further reduce the
number of tuples in any auxiliary view and still have
fV g[A be self-maintainable. We show in Section 4
how V can be maintained using A, and we explain in
Section 5 that we can maintain A without referencing
base relations.
3.1 Effect of exposed updates
Recall that so far in our example we have considered
protected updates only. Suppose sale had exposed
updates (i.e., updates could change the values of year,
sale id, or store id). We note that the definition of
Dep does not include any relation that has exposed
updates. Thus, the Dep function for line will not
include sale, and we get:
in which case an auxiliary view for line would be
created as:
line ?! item id A item
No selection or projection can be applied on line in
A line because there are no local selections on line in
the view and all attributes of line are either preserved
in the view or appear in join conditions. Section 4.1
explains why exposed updates have a different effect
on the set of auxiliary views needed than protected
updates.
4 Maintaining the view using the auxiliary
views
Recall that a view maintenance expression calculates
the effects on the view of a certain type of change:
insertions, deletions, or updates to a base relation.
View maintenance expressions are usually written in
terms of the changes and the base relations [5, 2]. In
this section we show that the set of auxiliary views
chosen by Algorithm 3.1 is sufficient to maintain the
view by showing how to transform the view maintenance
expressions written in terms of the changes and
the base relations to equivalent view maintenance expressions
written in terms of the changes, the view,
and the auxiliary views.
We give view maintenance expressions for each type
of change (insertions, deletions, and updates) sepa-
rately. In addition, for each type of change we apply
the changes to each base relation separately by
propagating the changes to the base relation onto the
view and updating the base relation. The reason we
give maintenance expressions of this form, rather than
maintenance expressions propagating several types of
changes at once, is that maintenance expressions of
this form are easier to understand and they are sufficient
for our purpose: showing that it is possible to
maintain a view using the auxiliary views generated
by Algorithm 3.1. View maintenance expressions for
insertions are handled in Section 4.1, for deletions are
handled in Section 4.2, and for protected updates are
handled in Section 4.3. Since exposed updates are
handled as deletions followed by insertions, they are
treated within Sections 4.1 and 4.2.
4.1 Insertions
In this section we show how the effect on a view
of insertions to base relations can be calculated using
the auxiliary views chosen by Algorithm 3.1. The view
maintenance expression for calculating the effects on
an SPJ view V of insertions to a base relation R is obtained
by substituting 4R (insertions to R) for base
relation R in the relational algebra expression for V .
For example, the view maintenance expressions calculating
the effects on our cal toy sales view (Sec-
tion 1.1) of insertions to store, sale, line, and item
appear in Table 4.
(- store id;manager oe state=CA 4St
store id - sale id;store id;month oe year=1996 Sa
1 item id - item id;item name oe category=toy I)
(- store id;manager oe state=CA St
store id - sale id;store id;month oe year=1996 4Sa
1 item id - item id;item name oe category=toy I)
(- store id;manager oe state=CA St
store id - sale id;store id;month oe year=1996 Sa
1 item id - item id;item name oe category=toy I)
(- store id;manager oe state=CA St
store id - sale id;store id;month oe year=1996 Sa
1 item id - item id;item name oe category=toy 4I)

Table

4: Maintenance Expressions for Insertions
A few words of explanation about the table are in
order.
ffl For convenience, in the table and hereafter we
abbreviate store, sale, line, and item as St,
Sa, L, and I, respectively.
ffl We abbreviate view cal toy sales as V .
ffl We have applied the general rule of "pushing selections
and projections down" to the maintenance
expressions.
ffl We use the notation 4VR to represent the insertions
into view V due to insertions into base relation
R. For example, 4V St represents insertions
into V due to insertions into St.
ffl Each of the maintenance expressions of Table 4
calculates the effect on view V of insertions to one
of the base relations. We show in Section 4.1.3
that even if insertions to multiple base relations
are propagated at once, the auxiliary views generated
by Algorithm 3.1 are still sufficient.
From the expressions of Table 4 it would appear
that beyond pushing down selections and projections,
nothing can be done to reduce the base relation data
required for evaluating the maintenance expressions.
If there are no referential integrity constraints, that
is indeed the case. However, referential integrity constraints
allow certain of the maintenance expressions
to be eliminated, requiring less base relation data in
the auxiliary views. Maintenance expressions are eliminated
due to the following property and corresponding
rule.
Property 4.1 (Insertion Property for Foreign
Keys) If there is a referential integrity constraint
from R j :B to R i :A (R j :B is the "foreign key"), A is
a key of R i , and R i does not have exposed updates,
In general, if the above
conditions hold then the following is true.
Property 4.1 holds because the referential integrity
constraint requires that each tuple in R j join with an
existing tuple in R i , and because it joins on a key of
R i it cannot join with any of the tuples in 4R i , so the
join of 4R i with R j must be empty.
Rule 4.1 (Insertion Rule for Foreign Keys) Let
G(V ) be the join graph for view V . The maintenance
expression calculating the effect on a view V of insertions
to a base relation R i is guaranteed to be empty
and thus can be eliminated if there is some relation R j
such that R i
Rule 4.1 is used to eliminate the maintenance expression
that calculates the effect on a view V of insertions
to a base relation R i if there is another relation
R j in V such that R i
the join graph for V . The rule holds because, by the
definition of Dep, R i is in Dep(R when the view
equates a foreign key of R j to the key of R i , there is a
referential integrity constraint from the foreign key in
R j to the key of R i , and R i has protected updates (the
effect of exposed updates is discussed in Section 4.1.2).
Since the maintenance expression that calculates the
effect of insertions to R i includes a join between 4R i
and R j , it must be empty by Property 4.1 and therefore
can be eliminated. Joins and referential integrity
constraints between keys and foreign keys are common
in practice, so the conditions of Rule 4.1 are often met.
Being able to eliminate certain maintenance expressions
when calculating the effect on a view V of insertions
to base relations can significantly reduce the cost
of maintaining V . Although view maintenance expressions
themselves are not the main theme of this paper,
nevertheless this is an important stand-alone result.
4.1.1 Rewriting the maintenance expressions
to use auxiliary relations. Eliminating certain
maintenance expressions using Rule 4.1 allows us to
use the auxiliary views instead of base relations when
propagating insertions. After applying Rule 4.1, the
remaining maintenance expressions are rewritten using
the auxiliary views generated by Algorithm 3.1
by replacing each -oeR i subexpression with the corresponding
auxiliary view AR i for R i .
For example, assuming for now that the base relations
have protected updates, the maintenance expressions
for 4V St , 4V Sa , and 4V I , in Table 4
can be eliminated by Rule 4.1 due to the referential
constraints between sale.store id and
store.store id, line.sale id and sale.sale id,
and line.item id and item.item id, respectively.
Only 4VL , the expression calculating the effect of insertions
to L, is not guaranteed to be empty. The
maintenance expression 4VL is rewritten using auxiliary
views as follows. Recall that the auxiliary views
are shown in Table 3.
Notice that the base relation L is never referenced
in the above maintenance expression, so an auxiliary
view for L is not needed. In addition, Sa is joined with
St in the maintenance expression, which is why it is
acceptable to store only the tuples in Sa that join with
existing tuples in St-tuples in Sa that don't join with
existing tuples in St won't contribute to the result. A
proof that the auxiliary views are sufficient in general
to evaluate the (reduced) maintenance expressions for
insertions appears in [12].
4.1.2 Effect of exposed updates. Suppose the
view contains a join condition R j A is a
key of R i , there is a referential integrity constraint
from R j :B to R i :A, but R i has exposed, rather than
protected, updates. Dep(R thus does not contain
R i . Recall that exposed updates can change the values
of attributes involved in selection conditions (local
or join). We handle exposed updates as deletions of
tuples with the old attribute values followed by insertions
of tuples with the new attribute values, since
exposed updates may result in deletions or insertions
in the view. Thus, if R i has exposed updates then
may include tuples representing the new values
of exposed updates. Because these tuples can join with
existing tuples in R j (without violating the referential
integrity or key constraints), Property 4.1 does not
hold and Rule 4.1 cannot be used to eliminate the
maintenance expression propagating insertions to R i .
For example, suppose updates may occur to the
year attribute of Sa. Then an auxiliary view for L
would be created as I as shown in
Section 3.1. We cannot semijoin L with A Sa in the
auxiliary view for L because new values of updated
tuples in Sa could join with existing tuples in L, where
the old values of the updated tuples didn't pass the
local selection conditions on Sa and hence weren't in
A Sa . That is, suppose the year of some sale tuple t was
changed from 1995 to 1996. Although the old value
of t doesn't pass the selection criteria year=1996 and
therefore wouldn't appear in A Sa , the new value of t
would, and since it could join with existing tuples in
L we cannot restrict AL to include only those tuples
that join with existing tuples in A Sa .
In this paper we assume that it is known in advance
whether each relation of a view V has exposed or protected
updates. If a relation has exposed updates, we
may need to store more information in the auxiliary
views in order to maintain V than if the relation had
protected updates. For example, we had to create an
auxiliary view for L when Sa had exposed updates,
where the auxiliary view for L wasn't needed when
Sa had protected updates.
An alternate way to consider updates, which
doesn't require advance knowledge of protected versus
exposed, is to assume that every base relation has
protected updates. Then, before propagating updates,
the updates to each base relation are divided into two
classes: updates that do not modify attributes involved
in selection conditions, and those that do. The
first class of updates can be propagated as protected
updates using the expressions of Section 4.3. Assuming
the second class of updates is relatively small, updates
in the second class could be propagated by issuing
queries back to the data sources.
4.1.3 Propagating insertions to multiple relations
at once. Maintenance expressions of the form
used in Table 4 propagate onto the view insertions to
one base relation at a time. To propagate insertions to
multiple base relations using the formulas in Table 4,
when 4VR i is calculated we assume that the insertions
to base relations R j (j ! i) have already been applied
to the base relations.
In [5, 8], maintenance expressions are given for
propagating changes to all base relations at once.
We consider the one relation at a time case because
the maintenance expressions are easier to explain;
the amount of data needed in the auxiliary views is
the same whether insertions (or deletions or updates)
are propagated one relation at a time or all at once
(see [12]).
4.2 Deletions
In this section we show how the effect on a view
of deletions to base relations can be calculated using
the auxiliary views. The view maintenance expression
for calculating the effects on an SPJ view V of
deletions to a base relation R is obtained similarly to
the expression for calculating the effects of insertions:
we substitute 5R (deletions to R) for base relation R
in the relational algebra expression for V . For exam-
ple, the view maintenance expressions for calculating
the effects on our cal toy sales view of deletions to
store, sale, line, and item appear respectively as
5V St , 5V Sa , 5VL , and 5V I in Table 5. We use the
notation 5VR to represent the deletions from view V
due to deletions from base relation R.
Often we can simplify maintenance expressions for
deletions to use the contents of the view itself if keys
(- store id;manager oe state=CA 5St
store id - sale id;store id;month oe year=1996 Sa
1 item id - item id;item name oe category=toy I)
(- store id;manager oe state=CA St
store id - sale id;store id;month oe year=1996 5Sa
1 item id - item id;item name oe category=toy I)
(- store id;manager oe state=CA St
store id - sale id;store id;month oe year=1996 Sa
1 item id - item id;item name oe category=toy I)
(- store id;manager oe state=CA St
store id - sale id;store id;month oe year=1996 Sa
1 item id - item id;item name oe category=toy 5I)

Table

5: Maintenance Expressions for Deletions
are preserved in the view. We do this using the following
properties and rule for deletions in the presence of
keys.
Property 4.2 (Deletion Property for Keys)
Given view
the key of a relation R i is preserved in V then the
following equivalence holds:
Consider the join graph G(V ) of view V . Property
4.2 says that if V preserves the key of some relation
then we can calculate
the effect on V of deletions to R i by joining V with
5R i on the key of R i . The property holds because
each tuple in V with the same value for the key of
R i as a tuple t in 5R i must have been derived from
t. Conversely, all tuples in V that were derived from
tuple t in 5R i must have the same value as t for the
key of R i . Therefore, the set of tuples in V that join
with t on the key of R i is exactly the set of tuples in
V that should be deleted when t is deleted from R i . A
similar property holds if the key of R i is not preserved
in V , but is equated by a selection condition in V to
an attribute C that is preserved in V . In this case the
effect of deletions from R i can be obtained by joining
V with 5R i using the join condition
Property 4.2 is used in [4] to determine when a view
is self-maintainable with respect to deletions from a
base relation. We extend their result with Property
4.3.
Property 4.3 (Deletion Property for Key
Joins) Given a view
satisfying the following
conditions:
1. V contains join conditions R i
2. attribute A is a key for R i+j (0 != j != k), and
3. R i+k :A is preserved in V ,
then the following equivalence holds (even without referential
Let G(V ) be the join graph for view V . Property
4.3 generalizes Property 4.2 to say that if V
preserves the key of some relation R i+k and R i
joins to R i+k along keys (that is, Need(R
and does not include all the base
relations of V ), then we can calculate the effect on V
of deletions to R i by joining 5R i with the sequence
of relations up to R i+k and then joining R i+k with
. The property holds because tuples in V with the
same value for the key of R i+k as a tuple t in R i+k
must have been derived from t as explained in Property
4.2. Furthermore, since the joins between R i+k
and R i are all along keys, each tuple in R i+k can join
with at most one tuple t 0 in R i , which means that tuples
in V that are derived from tuple t in R i+k must
also be derived from tuple t 0 in R i . Conversely, if a
tuple in V is derived from t 0 in R i , then it must have
the same value for the key of R i+k as some tuple t in
R i+k that t 0 joins with. Therefore, the set of tuples
in V that join on the key of R i+k with some tuple t
in R i+k that joins along keys with a tuple t 0 in R i is
exactly the set of tuples in V that should be deleted
when t 0 is deleted from R i . As before, a similar property
also holds if a key of R i+k is not preserved in
V but is equated by a selection condition in V to an
attribute C that is preserved in V . In this case the effect
of deletions from R i can be obtained by joining V
with R i+k using the join condition
Rule 4.2 (Deletion Rule) Let V be a view
with a tree structured join graph G(V ), and let
maintenance expression calculating the effect on a
view V of deletions to a base relation R i may be simplified
according to Property 4.3 to reference V unless
includes all the base relations of V except
R i . fi
Rule 4.2 is used to simplify maintenance expressions
for deletions to use the contents of the view and fewer
base relations. This allows us to rewrite the maintenance
expressions for deletions to use the auxiliary
views instead of base relations.
4.2.1 Rewriting the maintenance expressions
to use auxiliary relations. After simplifying the
maintenance expressions according to Rule 4.2, the
simplified expressions are rewritten to use the auxiliary
views generated by Algorithm 3.1 by replacing
each -oeR i subexpression in the simplified maintenance
expression with the corresponding auxiliary
view AR i for R i .
The maintenance expressions of Table 5 are simplified
using Rule 4.2 as follows.
A proof that the auxiliary views are sufficient in general
to evaluate the (simplified) maintenance expressions
for deletions appears in [12].
4.3 Protected updates
In this section we show how the effect on a view
of protected updates to base relations can be calculated
using the auxiliary views. (Recall that exposed
updates are treated separately as deletions followed
by insertions.) We give two maintenance expressions
for calculating the effect on a view V of protected updates
to a base relation R: one returning the tuples to
delete from the view (denoted as 5 - VR ) and another
returning the tuples to insert into the view (denoted
as 4 - VR ). In practice, these pairs of maintenance expressions
usually can be combined into a single SQL
update statement.
The view maintenance expression for calculating
the tuples to delete from an SPJ view V due to protected
updates to a base relation R is obtained by
substituting - old -R (the old attribute values of the
updated tuples in R) for base relation R in the relational
algebra expression for V . (Recall that -R, - old ,
and - new were defined in Section 2.) The view maintenance
expression for calculating the tuples to insert
is obtained similarly by substituting - new -R (the new
attribute values of the updated tuples in R) for base
relation R in the relational algebra expression for V .
For example, the view maintenance expressions calculating
the tuples to delete from our cal toy sales
view due to protected updates to each of the base relations
are given in Table 6. Expressions calculating
the tuples to insert into the view cal toy sales are
not shown but can be obtained by substituting - new
for - old in the expressions of Table 6. Note that the

Table

6 expressions are similar to the deletion expressions
of Table 5.
We simplify the maintenance expressions for protected
updates similarly to the way we simplify
the maintenance expressions for deletions, by using
the contents of the view itself if keys are preserved
in the view. We give the following properties
and rule for updates in the presence of
preserved keys. In the following let P (-R
(- old
store id;manager oe state=CA -St
store id - sale id;store id;month oe year=1996 Sa
1 item id - item id;item name oe category=toy I)
(- store id;manager oe state=CA St
store id - old
sale id;store id;month oe year=1996 -Sa
1 item id - item id;item name oe category=toy I)
(- store id;manager oe state=CA St
store id - sale id;store id;month oe year=1996 Sa
line id;sale id;item id;sales price -L
1 item id - item id;item name oe category=toy I)
(- store id;manager oe state=CA St
store id - sale id;store id;month oe year=1996 Sa
item id;item name oe category=toy -I)

Table

Maintenance Expressions for Removing
Old Updates
use
old
and - new
to project the old and new attribute
values respectively of preserved attributes in
-R i and the (regular) attribute values for preserved
attributes of other relations in V . We use 1oldkey(R
to denote joining on the attribute in which the key
value before the update is held.
Property 4.4 (Protected Update Property for
Keys) Given a view
the key of a
relation R i is preserved in V , then the following equivalences
hold:
new
Property 4.5 (Protected Update Property for
Key Joins) Given a view
satisfying the following
conditions:
1. view V contains join conditions R i
R i+k :B
2. attribute A is a key for R i+j (0 != j != k), and
3. R i+k :A is preserved in V ,
then the following equivalences hold (even without referential
1- old oe-R i 1-oeR
1- new oe-R i 1-oeR
new
Properties 4.4 and 4.5 are similar to the corresponding
properties for deletions. Attributes of R i that are
involved in selection conditions are guaranteed not to
be updated, so it does not matter whether we test
the old or new value in selection conditions. Property
4.4 is used in [4] to determine when a view is
self-maintainable for base relation updates.
Consider the join graph G(V ) of view V . Property
4.5 generalizes Property 4.4; Property 4.5 says
that if V preserves the key of some relation R i+k and
joins to R i+k along keys (that is, Need(R
and does not include all the base relations
of V ), then we can calculate the effect on V of
protected updates to R i by joining -R i with the sequence
of relations up to R i+k and then joining R i+k
with V . As for deletions, a similar property also holds
if a key of R i+k is not preserved in V but is equated
by a selection condition in V to an attribute C that
is preserved in V . In this case the effect of updates to
R i can be obtained by joining V with R i+k using the
join condition
Rule 4.3 (Protected Update Rule) Let V be a
view with a tree structured join graph G(V ), and let
maintenance expressions calculating the effect on a
view V of protected updates to a base relation R i can
be simplified according to Property 4.5 to reference V
includes all the base relations of
Similar to the rule for deletions, Rule 4.3 is used
to simplify the maintenance expressions for 5 - VR and
4 - VR to use the contents of the view and fewer base
relations so that the maintenance expressions can be
rewritten in terms of the auxiliary views.
4.3.1 Rewriting the maintenance expressions
to use auxiliary relations. After simplifying the
maintenance expressions according to Rule 4.3, the
simplified expressions are rewritten to use the auxiliary
views generated by Algorithm 3.1 by replacing
each -oeR i subexpression in the maintenance expression
with the corresponding auxiliary view AR i for R i .
The rewriting is similar to the rewriting for insertions
and deletions. An example and proof that the auxiliary
views are sufficient in general to evaluate the
maintenance expressions are given in [12].
5 Maintaining auxiliary views
Due to space constraints we give only an intuitive
argument, based upon join graphs, for why the set of
auxiliary views is itself self-maintainable. Details on
maintaining the auxiliary views efficiently and a proof
that the set of auxiliary views is self-maintainable appear
in the full version of the paper [12].
Recall that the auxiliary views derived by Algorithm
3.1 are of the form:
where C i equijoins a foreign key of R with the corresponding
for relation R i . Because the joins are
along foreign key referential integrity constraints, each
semijoin could be replaced by a join. Thus, each auxiliary
view is an SPJ view, and its join graph can be
constructed as discussed in Section 3. Further, note
that the join graph for each auxiliary view is a sub-graph
of the graph for the original view, because each
join in an auxiliary view is also a join in the original
view. Thus, the information needed to maintain the
original view is also sufficient to maintain each of its
auxiliary views.
6 Related work
The problem of view self-maintainability was considered
initially in [1, 4]. For each modification type
(insertions, deletions, and updates), they identify
of SPJ views that can be maintained using only
the view and the modification. [1] states necessary and
sufficient conditions on the view definition for the view
to be self-maintainable for updates specified using a
particular SQL modification statement (e.g., delete all
tuples where R:A ? 3). [4] uses information about key
attributes to determine self-maintainability of a view
with respect to all modifications of a certain type.
In this paper we consider the problem of making a
view self-maintainable by materializing a set of auxiliary
views such that the original view and the auxiliary
views taken together are self-maintainable. Although
the set of base relations over which a view
is defined forms one such set of auxiliary views, our
approach is to derive auxiliary views that are much
smaller than storing the base relations in their en-
tirety. Identifying a set of small auxiliary views to
make another view self-maintainable is an important
problem in data warehousing, where the base relations
may not be readily available.
In [10], views are made self-maintainable by pushing
down selections and projections to the base relations
and storing the results at the warehouse. Thus,
using our terminology, they consider auxiliary views
based only on select and project operators. We improve
upon their approach by considering auxiliary
views based on select, project, and semijoin operators,
along with using knowledge about key and referential
constraints. We have shown in Section 1.1
that our approach can significantly reduce the sizes
of the auxiliary views. We show in [12] that auxiliary
views of the form our algorithm produces can be
(self-)maintained efficiently.
In [13], inclusion dependencies (similar to referential
integrity constraints) are used to determine when
it is possible to answer from a view joining several re-
lations, a query over a subset of the relations; e.g.,
given V is a view joining R and other relations, when
R. We on the other hand, use similar
referential integrity constraints to simplify view
maintenance expressions.



--R

Updating derived relations: Detecting irrelevant and autonomously computable updates.
Algorithms for deferred view maintenance.
IEEE Data Engineering Bulletin
Data integration using self-maintainable views
Incremental maintenance of views with duplicates.
Maintenance of Materialized Views: Problems
Materialized Views.
Maintaining views incrementally.
The Stanford Data Warehousing Project.
A framework for supporting data integration using the materialized and virtual approaches.
The Rejuvenation of Materialized Views.

The GMAP: A versatile tool for physical data independence.
View maintenance in a warehousing envi- ronment
--TR

--CTR
Lyman Do , Pamela Drew , Wei Jin , Vish Jumani , David Van Rossum, Issues in Developing Very Large Data Warehouses, Proceedings of the 24rd International Conference on Very Large Data Bases, p.633-636, August 24-27, 1998
Mala Rajamani , Karen C. Davis, Partitioned auxiliary views for self-maintainable data warehouse, Proceedings of the 1st ACM international workshop on Data warehousing and OLAP, p.66-71, November 02-07, 1998, Washington, D.C., United States
Wen-Syan Li , Daniel C. Zilio , Vishal S. Batra , Calisto Zuzarte , Inderpal Narang, Load balancing and data placement for multi-tiered database systems, Data & Knowledge Engineering, v.62 n.3, p.523-546, September, 2007
S. Samtani , V. Kumar , M. Mohania, Self maintenance of multiple views in data warehousing, Proceedings of the eighth international conference on Information and knowledge management, p.292-299, November 02-06, 1999, Kansas City, Missouri, United States
Kenneth Salem , Kevin Beyer , Bruce Lindsay , Roberta Cochrane, How to roll a join: asynchronous incremental view maintenance, ACM SIGMOD Record, v.29 n.2, p.129-140, June 2000
Hoshi Mistry , Prasan Roy , S. Sudarshan , Krithi Ramamritham, Materialized view selection and maintenance using multi-query optimization, ACM SIGMOD Record, v.30 n.2, p.307-318, June 2001
Goretti K. Y. Chan , Qing Li , Ling Feng, Design and selection of materialized views in a data warehousing environment: a case study, Proceedings of the 2nd ACM international workshop on Data warehousing and OLAP, p.42-47, November 02-06, 1999, Kansas City, Missouri, United States
Jens Lechtenbrger , Hua Shu , Gottfried Vossen, Aggregate Queries Over Conditional Tables, Journal of Intelligent Information Systems, v.19 n.3, p.343-362, November 2002
Toby Bloom, Data warehousing: data cleaning and loading, Handbook of data mining and knowledge discovery, Oxford University Press, Inc., New York, NY, 2002
Avigdor Gal, Obsolescent materialized views in query processing of enterprise information systems, Proceedings of the eighth international conference on Information and knowledge management, p.367-374, November 02-06, 1999, Kansas City, Missouri, United States
D. Agrawal , A. El Abbadi , A. Singh , T. Yurek, Efficient view maintenance at data warehouses, ACM SIGMOD Record, v.26 n.2, p.417-427, June 1997
Nam Huyn, Multiple-View Self-Maintenance in Data Warehousing Environments, Proceedings of the 23rd International Conference on Very Large Data Bases, p.26-35, August 25-29, 1997
Wang , Maria Orlowska , Weifa Liang, Efficient refreshment of materialized views with multiple sources, Proceedings of the eighth international conference on Information and knowledge management, p.375-382, November 02-06, 1999, Kansas City, Missouri, United States
Stphane Lopes , Jean-Marc Petit , Farouk Toumani, Discovering interesting inclusion dependencies: application to logical database tuning, Information Systems, v.27 n.1, p.1-19, March 2002
Themistoklis Palpanas , Richard Sidle , Roberta Cochrane , Hamid Pirahesh, Incremental maintenance for non-distributive aggregate functions, Proceedings of the 28th international conference on Very Large Data Bases, p.802-813, August 20-23, 2002, Hong Kong, China
Hector Garcia-Molina , Wilburt Labio , Jun Yang, Expiring Data in a Warehouse, Proceedings of the 24rd International Conference on Very Large Data Bases, p.500-511, August 24-27, 1998
H. Engstr , S. Chakravarthy , B. Lings, Maintenance policy selection in heterogeneous data warehouse environments: a heuristics-based approach, Proceedings of the 6th ACM international workshop on Data warehousing and OLAP, November 07-07, 2003, New Orleans, Louisiana, USA
Jens Lechtenbrger , Gottfried Vossen, On the computation of relational view complements, ACM Transactions on Database Systems (TODS), v.28 n.2, p.175-208, June
Laks V. S. Lakshmanan , Jian Pei , Yan Zhao, QC-trees: an efficient summary structure for semantic OLAP, Proceedings of the ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California
Dimitri Theodoratos , Timos K. Sellis, Data Warehouse Configuration, Proceedings of the 23rd International Conference on Very Large Data Bases, p.126-135, August 25-29, 1997
Hongsong Li , Houkuan Huang , Youfang Lin, DSD: maintain data cubes more efficiently, Fundamenta Informaticae, v.59 n.2-3, p.173-190, February 2004
Hongsong Li , Houkuan Huang , Youfang Lin, DSD: Maintain Data Cubes More Efficiently, Fundamenta Informaticae, v.59 n.2-3, p.173-190, April 2004
Xin Zhang , Lingli Ding , Elke A. Rundensteiner, Parallel multisource view maintenance, The VLDB Journal  The International Journal on Very Large Data Bases, v.13 n.1, p.22-48, January 2004
Dimitri Theodoratos , Timos Sellis, Incremental Design of a Data Warehouse, Journal of Intelligent Information Systems, v.15 n.1, p.7-27, JulyAug. 2000
Yingwei Cui , Jennifer Widom , Janet L. Wiener, Tracing the lineage of view data in a warehousing environment, ACM Transactions on Database Systems (TODS), v.25 n.2, p.179-227, June 2000
Inderpal Singh Mumick , Dallan Quass , Barinderpal Singh Mumick, Maintenance of data cubes and summary tables in a warehouse, ACM SIGMOD Record, v.26 n.2, p.100-111, June 1997
Songting Chen , Bin Liu , Elke A. Rundensteiner, Multiversion-based view maintenance over distributed data sources, ACM Transactions on Database Systems (TODS), v.29 n.4, p.675-709, December 2004
Arvind Arasu , Brian Babcock , Shivnath Babu , Jon McAlister , Jennifer Widom, Characterizing memory requirements for queries over continuous data streams, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin
Amit Manjhi , Anastassia Ailamaki , Bruce M. Maggs , Todd C. Mowry , Christopher Olston , Anthony Tomasic, Simultaneous scalability and security for data-intensive web applications, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA
Dimitri Theodoratos , Mokrane Bouzeghoub, A general framework for the view selection problem for data warehouse design and evolution, Proceedings of the 3rd ACM international workshop on Data warehousing and OLAP, p.1-8, November 06-11, 2000, McLean, Virginia, United States
D. Laurent , J. Lechtenbrger , N. Spyratos , G. Vossen, Monotonic complements for independent data warehouses, The VLDB Journal  The International Journal on Very Large Data Bases, v.10 n.4, p.295-315, December 2001
Bin He , Rui Wang , Ying Chen , Ana Lelescu , James Rhodes, BIwTL: a business information warehouse toolkit and language for warehousing simplification and automation, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China
Nick Bassiliades , Ioannis Vlahavas , Ahmed K. Elmagarmid , Elias N. Houstis, InterBase-KB: Integrating a Knowledge Base System with a Multidatabase System for Data Warehousing, IEEE Transactions on Knowledge and Data Engineering, v.15 n.5, p.1188-1205, September
Himanshu Gupta , Inderpal Singh Mumick, Incremental maintenance of aggregate and outerjoin expressions, Information Systems, v.31 n.6, p.435-464, September 2006
Yannis Kotidis, Aggregate view management in data warehouses, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
Shivnath Babu , Jennifer Widom, Continuous queries over data streams, ACM SIGMOD Record, v.30 n.3, September 2001
S. B. Davidson , J. Crabtree , B. P. Brunk , J. Schug , V. Tannen , G. C. Overton , C. J. Stoeckert, Jr., K2/Kleisli and GUS: experiments in integrated access to genomic data sources, IBM Systems Journal, v.40 n.2, p.512-531, February 2001
Ladjel Bellatreche , Kamalakar Karlapalem , Mukesh Mohania, Some issues in design of data warehousing systems, Data warehousing and web engineering, IRM Press, Hershey, PA, 2002
Stefano Rizzi , Alberto Abell , Jens Lechtenbrger , Juan Trujillo, Research in data warehouse modeling and design: dead or alive?, Proceedings of the 9th ACM international workshop on Data warehousing and OLAP, November 10-10, 2006, Arlington, Virginia, USA
Brian Babcock , Shivnath Babu , Mayur Datar , Rajeev Motwani , Jennifer Widom, Models and issues in data stream systems, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin
Zhiyuan Chen , Chen Li , Jian Pei , Yufei Tao , Haixun Wang , Wei Wang , Jiong Yang , Jun Yang , Donghui Zhang, Recent progress on selected topics in database research: a report by nine young Chinese researchers working in the United States, Journal of Computer Science and Technology, v.18 n.5, p.538-552, September
select-project-join view;warehouse view;materialized views;data integrity;key integrity constraints;auxiliary data storage;materialized view maintenance;fast integrated data access;referential integrity constraints;data source querying;auxiliary views;self-maintainable views;data warehousing