Tracing the lineage of view data in a warehousing environment.
We consider the view data lineageproblem in a warehousing environment: For a given data item in a materialized warehouse view, we want to identify the set of source data items that produced the view item. We formally define the lineage problem, develop lineage tracing algorithms for relational views with aggregation, and propose mechanisms for performing consistent lineage tracing in a multisource data warehousing environment. Our result can form the basis of a tool that allows analysts to browse warehouse data, select view tuples of interest, and then drill-through to examine the exact source tuples that produced the view tuples of interest.
Introduction
In a data warehousing system, materialized views over source data are defined, computed, and
stored in the warehouse to answer queries about the source data (which may be stored in distributed
and legacy systems) in an integrated and efficient way [Wid95]. Typically, on-line analytical
processing and mining (OLAP and OLAM) systems operate on the data warehouse, allowing
users to perform analysis and predictions [CD97, HCC98]. In many cases, not only are the views
themselves useful for analysis, but knowing the set of source data that produced specific pieces of
view information also can be useful. Given a data item in a materialized view, determining the
source data that produced it and the process by which it was produced is termed the data lineage
problem. Some applications of view data lineage are:
ffl OLAP and OLAM: Effective data analysis and mining needs facilities for data exploration
at different levels. The ability to select a portion of relevant view data and "drill-down"
to its origins can be very useful. In addition, an analyst may want to check the origins of
suspect or anomalous view data to verify the reliability of the sources or even repair the
source data.
ffl Scientific Databases: Scientists apply algorithms to commonly understood and accepted
source data to derive their own views and perform specific studies. As in OLAP, it can be
useful for the scientist to focus on specific view data, then explore how it was derived from
the original raw data.
This work was supported by Rome Laboratories under Air Force Contract F30602-96-1-0312, and by the
Advanced Research and Development Committee of the Community Management Staff as a project in the MDDS
Program.
ffl On-line Network Monitoring and Diagnosis Systems: From anomalous view data computed
by the diagnosis system, the network controller can use data lineage to identify the faulty
data within huge volumes of data dumped from the network monitors.
ffl Cleansed Data Feedback: Information centers download raw data from data sources and
"cleanse" the data by performing various transformations on it. Data lineage helps locate
the origins of data items, allowing the system to send reports about the cleansed data back
to their sources, and even link the cleansed items to the original items.
Materialized View Schema Evolution: In a data warehouse, users may be permitted to
change view definitions (e.g., add a column to a view) under certain circumstances. View
data lineage can help retrofit existing view contents to the new view definition without
recomputing the entire view.
ffl View Update Problem: Not surprisingly, tracing the origins of a given view data item
is related to the well-known view update problem [BS81]. In Section 8.2, we discuss this
relationship, and show how lineage tracing can be used to help translate view updates into
corresponding base data updates.
In general, a view definition provides a mapping from the base data to the view data. Given a
state of the base data, we can compute the corresponding view according to the view definition.
However, determining the inverse mapping-from a view data item back to the base data that
produced it-is not as straightforward. To determine the inverse mapping accurately, we not only
need the view definition, but we also need the base data and some additional information.
The warehousing environment introduces certain challenges to the lineage tracing problem,
such as how to trace lineage when the base data is distributed among multiple sources, and what
to do if the sources are inaccessible or not consistent with the warehouse views. At the same time,
the warehousing environment can help the lineage tracing process by providing facilities to merge
data from multiple sources, and to store auxiliary information in the warehouse in a consistent
fashion.
In this paper, we focus on the lineage problem for relational Select-Project-Join views with
aggregation (ASPJ views) in a data warehousing environment. Our results extend to additional
relational operators as we show in [CWW98]. In summary, we:
ffl Formulate the view data lineage problem. We give a declarative definition of tuple derivations
for relational operators, and inductively define view tuple derivations based on the
tuple derivations for the operators (Section 4).
ffl Develop derivation tracing algorithms, including proofs of their correctness (Sections 5
and 6).
ffl Discuss issues of derivation tracing in a warehousing environment, and show how to trace
tuple derivations for views defined on distributed, legacy sources consistently and efficiently
(Section 7).
We first discuss related work in Section 2. We then motivate the lineage problem using detailed
examples in Section 3. After defining the lineage problem and presenting our solutions as summarized
above, in Section 8 we revisit some related issues (e.g., the view update problem) in detail.
Conclusions and future work are covered in Section 9. All proofs are provided in the Appendix.
Related Work
There has been a great deal of work in view maintenance and related problems in data warehous-
ing, but to the best of our knowledge the lineage problem has not been addressed. Overviews
of research directions and results in data warehousing can be found in [CD97, Wid95, WB97].
specifically covers view maintenance problems in data warehousing. Incremental view
maintenance algorithms have been presented for relational algebra views [QW91], for aggregation
[Qua96], and for recursive views [GMS93]. View "self-maintainability" issues are addressed
in [QGMW96]. Warehouse view consistency is studied in [ZGMW96, ZWGM97], to ensure that
views in the warehouse are consistent with each other and reflect consistent states of the sources.
All of these papers consider computing warehouse views but do not address the reverse problem
of view data lineage.
OLAP systems, usually sitting on top of a data warehouse, allow users to perform analysis
and make predictions based on the warehouse view information [Col96, HCC98]. The data
cube is a popular OLAP structure that facilitates multi-dimensional aggregation over source
data [GBLP96]. Cube "rolling-up" and "drilling-down" enable the user to browse the view data
at any level and any dimension of the aggregation [HRU96, MQM97]. However, data cubes are
based on a restricted form of relational views, and usually only allow drilling down within the
warehouse, not to the original data sources.
Metadata for warehouse views can be maintained to record lineage information about a particular
view column [CM89, HQGW93]. However, this approach only provides schema-level lineage
tracing, while many applications require lineage at a finer (instance-level) granularity. Some
scientific databases use tuple-level annotations to keep track of lineage [HQGW93], which can
introduce high storage overhead in warehousing applications.
introduces "weak inversion" to compute fine-grained data lineage. However, not all
views have an inverse or weak inverse. Also, the system in [WS97] requires users to provide a
view's inverse function in order to compute lineage, which we feel is not always practical. Our
algorithms trace tuple-level lineage automatically for the user and maintain the necessary auxiliary
information to ensure view invertibility.
The problem of reconstructing base data from summary data is studied in [FJS97]. Their
statistical approach estimates the base data using only the summary data and certain constraints;
it does not guarantee accurate lineage tracing. In this paper, we focus on accurate lineage tracing
with the base data available either in remote sources or stored locally in the warehouse.
The view update problem [DB78, Kel86] is to translate updates against a view into updates
against the relevant base tables, so that the updated base tables will derive the updated view.
View data lineage can be used to help solve the view update problem, employing a different
approach from previous techniques; see Section 8.
Finally, Datalog can perform top-down recursive rule-goal unification to provide proofs for a
goal proposition [Ull89]. The provided proofs find the supporting facts for the goal proposition,
and therefore also can be thought of as providing the proposition's lineage. However, we take an
approach that is very different from rule-goal unification; a detailed comparison is presented in
Section 8.
item id item name category
binder stationery
stationery
shirt clothing
pants clothing
pot kitchenware

Figure

1: item table
store id store name city state
004 Macy's New York City NY

Figure

2: store table
store id item id price num sold

Figure

3: sales table
Motivating Examples
In this section, we provide examples that motivate the definition of data lineage and how lineage
tracing can be useful. Consider a data warehouse with retail store data over the following base
tables:
item(item id, item name, category)
store(store id, store name, city, state)
sales(store id, item id, price, num sold)
The item and store tables are self-explanatory. The sales table contains sales information,
including the number and price of each product sold by each store. Example table contents are
shown in Figures 1, 2, and 3.
Example 3.1 (Lineage of SPJ View) Suppose a sales department wants to study the selling
patterns of California stores. A materialized view Calif can be defined in the data warehouse for
the analysis. The SQL definition of the view is:
SELECT store.store-name, item.item-name, sales.num-sold
FROM store, item, sales
The view definition also can be expressed using the relational algebra tree in Figure 4. The
materialized view for Calif over our sample data is shown in Figure 5.
The analyst browses the view table and is interested in the second tuple !Target, pencil,
3000?. He would like to see the relevant detailed information and asks question Q1: "Which base
data produced tuple !Target, pencil, 3000? in Calif?" Using the algorithms we present in
Section 5, we obtain the answer in Figure 6. The answer tells us that the Target store in Palo
Alto sold 3000 pencils at a price of 1 dollar each.
sales
store
store_name, item_name, num_sold
item
Calif

Figure

4: View definition for Calif
store name item name num sold
Target binder 1000
Target pencil 3000
Target pants 600
Macy's shirt 1500
Macy's pants 600

Figure

5: Calif table
store
s id s name city state
item
stationery
sales
s id i id price num sold

Figure

Calif lineage for !Target, pencil, 3000?
Example 3.2 (Lineage of Aggregation View) Now let's consider another warehouse view
Clothing, for analyzing the total clothing sales of the large stores (which have sold more than
5000 clothing items).
Clothing AS
SELECT sum(num-sold) as total
FROM item, store, sales
GROUP BY store-name
The relational algebra definition of the view is shown in Figure 7. We extend relational algebra
with an aggregation operator, denoted ff G;aggr(B) , where G is a list of groupby attributes, and
aggr(B) abbreviates a list of aggregate functions over attributes. (Details are given in Section 4.1.)
The materialized view contains one tuple, !5400?, as shown in Figure 8.
The analyst may wish to learn more about the origins of this tuple, and asks question Q2:
"Which base data produced tuple !5400? in Clothing?" Not surprisingly, due to the more
complex view definition, this question is more difficult to answer than Q1. We develop the
appropriate algorithms in Section 6, and Figure 9 presents the answer. It lists all the branches of
Macy's, the clothing items they sell (but not other items), and the sales information. All of this
information is used to derive the tuple !5400? in Clothing.
Questions such as Q1 and Q2 ask about the base tuples that derive a view tuple. We call
these base tuples the derivation (or lineage) of the view tuple. In the next section, we formally
define the concept of derivation. Sections 5, 6, and 7 then present algorithms to compute view
tuple derivations.
a
item sales
store_name, sum(num_sold) as total
s
total
total > 5000
store
Clothing

Figure

7: View definition for Clothing
total
Figure

8: Clothing table
store
s id s name city state
004 Macy's New York City NY
item
shirt clothing
pants clothing
sales
s id i id price num sold

Figure

9: Clothing lineage for !5400?
4 View Tuple Derivations
In this section, we define the notion of a tuple derivation, which is the set of base relation tuples
that produce a given view tuple. Section 4.1 first introduces the views on which we focus in
this paper. Tuple derivations for operators and views are then defined in Sections 4.2 and 4.3,
respectively.
We assume that a table (or relation) R with schema R contains a set of tuples
with no duplicates. (Thus, we consider set semantics in this paper. We have adapted our work
to bag semantics as well; please see [CWW98].) A database D contains a list of base tables
view V is a virtual or materialized result of a query over the base tables in D.
The query (or the mapping from the base tables to the view table) is called the view definition,
denoted as v. We say that
4.1 Views
We consider a class of views defined over base relations using the relational algebra operators
selection (oe), projection (-), join (./), and aggregation (ff). Our framework applies as well to set
union ([), set intersection ("), and set difference (\Gamma), however these operators are omitted in
this paper due to space constraints. Please see [CWW98] for details.
We use the standard relational semantics, included here for completeness:
Base case:
ffl Projection: -A
ig.
We consider the multi-way natural join
Thus, the grammar of our view definition language is as follows:
where R is a base table, are views, C is a selection condition (any boolean expression)
on attributes of V 1 , A is a projection attribute list from V 1 , G is a groupby attribute list from V 1 ,
and aggr(B) abbreviates a list of aggregation functions to apply to attributes of V 1 .
For convenience in formulation, when a view references the same relation more than once, we
consider each relation instance as a separate relation. For example, we treat the self-join R ./ R
as (R as R 1 (R as R 2 ), and we consider R 1 and R 2 to be two tables in D. This approach
allows view definitions to be expressed using an algebra tree instead of a graph, while not limiting
the views we can handle.
Any view definition in our language can be expressed using a query tree, with base tables as
the leaf nodes and operators as inner nodes. Figures 4 and 7 are examples of query trees.
4.2 Tuple Derivations for Operators
To define the concept of derivation, we assume logically that the view contents are computed by
evaluating the view definition query tree bottom-up. Each operator in the tree generates its result
table based on the results of its children nodes, and passes it upwards. We begin by focusing on
each operator, defining derivations of the operator's result tuples based on its input tuples.
According to relational semantics, each operator generates its result tuple-by-tuple based on
its operand tables. Intuitively, given a tuple t in the result of operator Op, only a subset of the
input tuples produce t. We say that the tuples in this subset contribute to t, and we call the entire
subset the derivation of t. Input tuples not in t's derivation either contribute to nothing, or only
contribute to result tuples other than t.

Figure

illustrates the derivation of a view tuple. In the figure, operator Op is applied to
tables T 1 and T 2 , which may be base tables or temporary results from other operators. (In general,
we use R's to denote base tables and T 's to denote tables that may be base or derived.) Table T
is the operation result. Given tuple t in T , only subsets T
2 of T 1 and T 2 contribute to t.
called t's derivation. The formal definition of tuple derivation for an operator is given
next, followed by additional explanation.
Definition 4.1 (Tuple Derivation for an Operator) Let Op be any of our relational operator
(oe, -, ./, ff) over tables T be the table that results
from applying Op to T Given a tuple t 2 T , we define t's derivation in T
according to Op to be Op \Gamma1
are maximal subsets
of
Op
T1* T2*

Figure

10: Derivation of tuple t
(a) Op(T
(b) 8T
Also, we say that Op \Gamma1
i is t's derivation in T i , and each tuple t   in T
i contributes to t,
can be extended to represent the derivations of a set of tuples:
where
S represents the multi-way union of relation lists. 1
In Definition 4.1, requirement (a) says that the derivation tuple sets (the T i
's) derive exactly
t. From relational semantics, we know that for any result tuple t, there must exist such tuple
sets. Requirement (b) says that each tuple in the derivation does in fact contribute something
to t. For example, with requirement (b) and given base tuples that do not satisfy the
selection condition C and therefore make no contribution to any view tuple will not appear in any
view tuple's derivation. By defining the T i \Lambda 's to be the maximal subsets that satisfy requirements
(a) and (b), we make sure that the derivation contains exactly all the tuples that contribute to
t. Thus, the derivation fully explains why a tuple exists in the view. Theorem 4.2 shows that
there is a unique derivation for any given view tuple. Recall that all proofs are provided in the


Appendix

.
Theorem 4.2 (Derivation Uniqueness) Given t 2 Op(T is a tuple in the
result of applying operator Op to tables T there exists a unique derivation of t in
according to Op.
Example 4.3 (Tuple Derivation for Aggregation) Given table R in Figure 11(a), and tuple
Figure 11(b), the derivation of t is
R
sum(Y)1(b) a
(a) R X, sum(Y) (R)
R
(c) a -1 (<2, 8>
R

Figure

Tuple derivations for aggregation
shown in Figure 11(c). Notice that R's subset fh2; 3i, h2; 5ig also satisfies requirements (a) and
(b) in Definition 4.1, but it is not maximal. Intuitively, h2; 0i also contributes to the result tuple,
since computed by adding the Y attributes of h2; 3i, h2; 5i, and h2; 0i
in R.
From Definition 4.1 and the semantics of the operators in Section 4.1, we now specify the
actual tuple derivations for each of our operators.
Theorem 4.4 (Tuple Derivations for Operators) Let be tables and t be a result
tuple.
-A
4.3 Tuple Derivations for Views
Now that we have defined tuple derivations for the operators, we proceed to define tuple derivations
for views. As mentioned earlier, a view definition can be expressed as a query tree evaluated
bottom-up. Intuitively, if a base tuple t   contributes to a tuple t 0 in the intermediate result of a
view evaluation, and t 0 further contributes to a view tuple t, then t   contributes to t. We define
a view tuple's derivation to be the set of all base tuples that contribute to the view tuple. The
specific process through which the view tuple is derived can be illustrated by applying the view
query tree to the derivation tuple sets, and presenting the intermediate results for each operator
in the evaluation.
Definition 4.5 (Tuple Derivation for a View) Let D be a database with base tables
be a view over D. Consider a tuple t 2 V .
1. contributes to itself in V .
2. is a view definition over D,
contributes to t according to the operator Op (by Definition 4.1), and t   2 R i contributes to
according to the view v j (by this definition recursively). Then t   contributes to t according
to v.
R
Y
(b)2
Y
a
(c)
s
(R)
R
(a) 0
Figure

12: Tuple derivation for a view
We define t's derivation in D according to v to be v \Gamma1
are
subsets of R Rm such that t   2 R
contributes to t according to v, for
Also, we call R
derivation in R i according to v, denoted as v Finally, the derivation
of a view tuple set T contains all base tuples that contribute to any view tuple in the set T :
(v
Theorem 4.2 can be applied inductively in the obvious way to show that a view tuple's derivation
is unique.
Example 4.6 (Tuple Derivation for a View) Given base table R in Figure 12(a), view
Figure 12(c), and tuple is easy to see that tuples h2; 3i
and h2; 5i in R contribute to h2; 3i and h2; 5i in oe Y 6=0 (R) in Figure 12(b), and further contribute
to h2; 8i in V . The derivation of t is v \Gamma1
R as shown in Figure 12(d).
We now state some properties of tuple derivations to provide the groundwork for our derivation
tracing algorithms.
Theorem 4.7 (Derivation Transitivity) Let D be a database with base tables R
and let be a view over D. Suppose that v can also be represented as
(D) is an intermediate view over D, for
derivation in V j according to v 0 . Then t's derivation in D according to v is the concatenation of
derivations in D according to v j ,
(v
where
represents the multi-way concatenation of relation lists. 2
Theorem 4.7 is a result of Definition 4.5. It shows that given a view V with a complex definition
tree, we can break down its definition query tree into intermediate views, and compute a tuple's
derivation by recursively tracing the hierarchy of intermediate views.
2 The concatenation of two relation lists relations
are renamed so that the same relation never appears twice.
Since we define tuple derivations inductively based on the view query tree, an interesting
question arises: Are the derivations of two equivalent views also equivalent? Two view definitions
(or query trees) v 1 and v 2 are equivalent iff 8D: v 1 We prove in Theorem 4.8
that given any two equivalent Select-Project-Join (SPJ) views, their tuple derivations are also
equivalent.
Theorem 4.8 (Derivation Equivalence after SPJ Transformation) Tuple derivations of
equivalent SPJ views are equivalent. In other words, given equivalent SPJ views v 1 and v 2 ,
According to Theorem 4.8, we can transform an SPJ view to a simple canonical form before
tracing tuple derivations. Unfortunately, views with aggregation do not have this nice property,
as shown in the following example.
Example 4.9 (Tuple Derivations for Equivalent Views with Aggregation) Let
are equivalent, since
Given base table R in Figures 11(a) and 12(a), Figures 11(b) and 12(c) show
that the contents of the two views are the same. However, the derivation of tuple
according to v 1 (shown in Figure 11(c)) is different from that according to v 2 (shown in Figure
12(d)).
Given Definition 4.5, a straightforward way to compute a view tuple derivation is to compute
the intermediate results for all operators in the view definition and store them as temporary
tables, then trace the tuple's derivation in the temporary tables recursively, until reaching the
base tables. Obviously, this approach is impractical due to the computation and storage required
for all the intermediate results. In the next two sections, we separately consider SPJ views and
views with aggregation (ASPJ views). We show in Section 5 that one relational query over the
base tables suffices to compute tuple derivations for SPJ views. A recursive algorithm for ASPJ
view derivation tracing that requires a modest amount of auxiliary information is described in
Section 6.
5 SPJ View Derivation Tracing
Derivations for tuples in SPJ views can be computed using a single relational query over the base
data. In this section, we first define the general concept of a derivation tracing query, which
can be applied directly to the base tables to compute a view tuple's derivation. We then specify
tracing queries for SPJ views, and discuss optimization issues for tracing queries.
5.1 Derivation Tracing Queries
Sometimes, we can write a query for a specific view definition v and view tuple t, such that if we
apply the query to the database D it returns t's derivation in D (based on Definition 4.5). We
call such a query a derivation tracing query (or tracing query) for t and v. More formally, we
Definition 5.1 (Derivation Tracing Query) Let D be a database with base tables
Given view definition v over R
a derivation tracing query for t and v iff:
D (t) is t's derivation over D according to v, and TQ t;v is independent of database
instance D. We can similarly define the tracing query for a view tuple set T , and denote it as
TQ T;v (D).
5.2 Tracing Queries for SPJ Views
All SPJ views can be transformed into the form -A (oe C (R 1 ./ using a sequence of SPJ
algebraic transformations [Ull89]. We call this form the SPJ canonical form. From Theorem 4.8,
we know that SPJ transformations do not affect view tuple derivations. Thus, given an SPJ
view, we first transform it into SPJ canonical form, so that its tuple derivations can be computed
systematically using a single query. We first introduce an additional operator used in tracing
queries for SPJ views.
Definition 5.2 (Split Operator) Let T be a table with schema T. The operator Split breaks
T into a list of tables; each table in the list is a projection of T onto a set of attributes A i ' T,
h- A 1
Theorem 5.3 (Derivation Tracing Query for an SPJ View) Let D be a database with
base tables R be an SPJ view over D. Given
derivation in D according to v can be computed by applying the following
query to the base tables:
Given a tuple set T ' v(D), T 's derivation tracing query is:
where n is the semi-join operator.
Example 5.4 (Tracing Query for Calif) Recall Q1 over view Calif in Example 3.1, where
we asked about the derivation of tuple !Target, pencil, 3000?. Figure 13(a) shows the tracing
query for !Target, pencil, 3000? in Calif according to Theorem 5.3. The reader may verify
that by applying the tracing query to the source tables in Figures 1, 2, and 3, we obtain the
derivation result in Figure 6.
5.3 Tracing Query Optimization
The derivation tracing queries in Section 5.2 clearly can be optimized for better performance.
For example, the simple technique of pushing selection conditions below the join operator is
especially applicable in tracing queries, and can significantly reduce query cost. Figure 13(b)
shows the optimized tracing query for the Calif tuple.
If sufficient key information is present, the tracing query is even simpler:
store sales store sales
item item
store, item, sales
s
TQ <Target, pencil, 3000>, Calif
s
store, item, sales
<Target, pencil, 3000>, Calif
s
(b) Optimized
(a) Unoptimized

Figure

13: Derivation tracing query for !Target, pencil, 3000?
Theorem 5.5 (Derivation Tracing using Key Information) Let R i be a base table with
attributes K i include the base keys (i.e.,
derivation is hoe K 1
(R
According to Theorem 5.5, we can use key information to fetch the derivation of a tuple directly
from the base tables, without performing a join. The query complexity is reduced from O(n m ) to
O(mn), where n is the maximum size of the base tables, and m is the number of base tables on
which v is defined.
We have shown that tuple derivations for SPJ views can be traced efficiently. For more
complex views with aggregations we cannot compute tuple derivations by a single query over the
base tables. In the next section, we present a recursive tracing algorithm for these views.
6 Derivation Tracing Algorithm for ASPJ Views
In this section, we consider SPJ views with aggregation (ASPJ views). Although we have shown
that no intermediate results are required for SPJ view derivation tracing, some ASPJ views are
not traceable without storing certain intermediate results. For example, in Q2 in Example 3.2
the user asks for the derivation of tuple in the view Clothing. It is not possible to
compute t's derivation directly from store, item, and sales, because total is the only column
of view Clothing, and it is not contained in the base tables at all. Therefore, we cannot find
t's derivation by knowing only that t:total = 5400. In order to trace the derivation correctly,
we need tuple hMacy's, 5400i in the intermediate aggregation result to serve as a ``bridge'' that
connects the base tables and the view table.
We introduce a canonical form for ASPJ views in Section 6.1. In Section 6.2, we specify the
derivation tracing query for a simple one-level ASPJ view. We then develop a recursive tracing
algorithm for complex ASPJ views and justify its correctness in Section 6.3. As mentioned above,
intermediate (aggregation) results in the view evaluation are needed for derivation tracing. These
intermediate results can either be recomputed from the base tables when needed, or they can be
stored as materialized auxiliary views in a warehouse; this issue is further discussed in Section 7.1.
In the remainder of this section we simply assume that all intermediate aggregation results are
available.
6.1 ASPJ Canonical Form
Unlike SPJ views, ASPJ views do not have a simple canonical form, because in an ASPJ view definition
some selection, projection, and join operators cannot be pushed above or below the aggregation
operators. View Clothing in Figure 7 is such an example, where the selection total ? 5000
cannot be pushed below the aggregation, and the selection category = "clothing" cannot be
pulled above the aggregation. However, by commuting and combining some SPJ operators [Ull89],
it is possible to transform a general ASPJ view query tree into a form composed of ff-oe ./ operator
sequences, which we call ASPJ segments. Each segment in the query tree except the topmost
must include a non-trivial aggregation operator. We call this form the ASPJ canonical form.
Definition 6.1 (ASPJ Canonical Form) Let v be an ASPJ view definition over database D.
1. R is a base table in D, is in ASPJ canonical form.
2. is in ASPJ canonical form if v j is an ASPJ view in
ASPJ canonical form,
6.2 Derivation Tracing Queries for One-level ASPJ Views
A view defined by one ASPJ segment is called a one-level ASPJ view. Similar to SPJ views, we
can use one query to compute a tuple derivation for a one-level ASPJ view.
Theorem 6.2 (Derivation Tracing Query for a One-Level ASPJ View) Given a one-level
derivation in T according to v can be computed by applying the following
query to the base tables:
Given tuple set derivation tracing query is:
Here too, evaluation of the actual tracing query can be optimized in various ways as discussed in
Section 5.3.
6.3 Recursive Derivation Tracing Algorithm for Multi-level ASPJ Views
Given a general ASPJ view definition, we first transform the view into ASPJ canonical form,
divide it into a set of ASPJ segments, and define an intermediate view for each segment.
Example 6.3 (ASPJ Segments and Intermediate Views for Clothing) Recall the view
Clothing in Example 3.2. We can rewrite its definition in ASPJ canonical form with two seg-
ments, and introduce an intermediate view AllClothing as shown in Figure 14.
We then trace a tuple's derivation by recursively tracing through the hierarchy of intermediate
views top-down. At each level, we use the tracing query for a one-level ASPJ view to compute
derivations for the current tracing tuples with respect to the view or base tables at the next level
below. Details follow.
Clothing
a store_name, sum(num_sold) as total
AllClothing
s total > 5000
total
segment 1
segment 2
item
store sales

Figure

14: ASPJ segments and intermediate views for Clothing
6.3.1 Algorithm

Figure

presents our recursive derivation tracing algorithm for a general ASPJ view.
Given a view definition v in ASPJ canonical form, and tuple t 2 v(D), procedure
TupleDerivation(t; v; D) computes the derivation of tuple t according to v over D. The main al-
gorithm, Procedure TableDerivation(T ; v; D), computes the derivation of a tuple set T ' v(D)
according to v over D. As discussed earlier, we assume that
a one-level ASPJ view, and available as a base table or an intermediate view,
1::k. The procedure first computes T 's derivation hV
using the
one-level ASPJ view tracing query TQ(T i) from Theorem 6.2. It then calls procedure
which computes (recursively) the
derivation of each tuple set V
j according to v j , concatenates the results to form the
derivation of the entire list of view tuple sets.
Example 6.4 (Recursive Derivation Tracing) We divided the view Clothing into two segments
in Example 6.3. We assume that the contents of the intermediate view AllClothing are
available (shown in Figure 16). According to our algorithm, we first compute the derivation T  of !5400? in AllClothing to obtain T
trace T
's derivation to the
base tables to obtain the derivation result in Figure 9.
Note that we do not necessarily materialize complete intermediate aggregation views such as
AllClothing. In fact, there are many choices of what (if anything) to store. The issue of storing
versus recomputing the intermediate information needed for derivation tracing is discussed in
Section 7.1.
6.3.2 Correctness
To justify the correctness of our algorithm, we claim the following:
1. Transforming a view into ASPJ canonical form does not affect its derivation.
We can "canonicalize" an ASPJ view by transforming each segment between adjacent aggregation
operators into its SPJ canonical form. The process consists only of SPJ transformations
[Ull89]. Theorem 4.8 shows that derivations are unchanged by SPJ transformations.
procedure TupleDerivation(t; v; D)
begin
return (TableDerivation(ftg;v; D));
procedure TableDerivation(T; v; D)
begin
is a one-level ASPJ view,
(D) is an intermediate view or a base table,
return (TableListDerivation(hV
procedure
begin
do
return (D

Figure

15: Algorithm for ASPJ view tuple derivation tracing
store name total
Target 1400
Macy's 5400

Figure

AllClothing table
2. It is correct to trace derivations recursively down the view definition tree.
From Theorem 4.7, we know that derivations are transitive through levels of the view definition
tree. Thus, when tracing tuple derivations for a canonicalized ASPJ view, we can
first divide its definition into one-level ASPJ views, and then compute derivations for the
intermediate views in a top-down manner.
Our recursive derivation tracing algorithm can be used to trace the derivation of any tuple
in any ASPJ view in a conventional database. However, certain additional issues arise when
performing derivation tracing in a multi-source warehousing environment, which we proceed to
discuss in the next section.
7 Derivation Tracing in a Warehousing Environment
In Sections 5 and 6 we presented algorithms to trace view tuple derivations. Our algorithms
assume that all of the base tables as well as the intermediate views are accessible, and that they
are consistent with the view being traced. These assumptions may not hold when we are tracing
derivations for a warehouse view defined on remote distributed sources. The following problems
may arise:
1. Efficiency problem: Querying remote sources and performing selections and joins (in the
tracing queries) over them for each tuple derivation trace can be very inefficient. Also,
recomputing intermediate views for tracing multi-level ASPJ views can be expensive.
2. Consistency problem: The warehouse may not refresh its views in real time, which means
that warehouse views can become out of date. Thus, we cannot always compute the derivation
of tuples in the "old" view from the "new" source base tables. For example, if a base
tuple in the derivation of a view tuple has just been deleted from the source, but the change
has not yet been propagated to the view, then the user sees the view tuple but cannot
correctly trace its derivation since a relevant base tuple is gone.
3. Legacy source problem: Views defined on inaccessible legacy sources are not traceable because
the base tables are not available.
Storing auxiliary views in the warehouse to reduce computation cost and to avoid querying
the sources [QGMW96] is a solution that solves all three of the above problems. The price
is extra storage and view maintenance costs. In Section 7.1, we consider the trade-offs between
materializing and recomputing intermediate results, and propose to store intermediate aggregation
results to improve overall performance. In Section 7.2, we introduce derivation views, which store
information about sources so that view derivations always can be computed without querying the
sources.
7.1 Materializing vs. Recomputing Intermediate Aggregate Results
In Section 6, we saw that intermediate aggregation results are needed for derivation tracing
in the general case. There are two ways to obtain such information. One is to recompute the
intermediate result during the tracing process. This approach requires no permanent extra storage,
but the tracing process takes longer, especially when the recomputation may require querying the
sources. The other way is to maintain materialized auxiliary views containing the intermediate
results. In this case, less computation is required at tracing time, but the auxiliary views must be
stored and kept up-to-date. Due to the characteristics of warehousing environments, we suggest
warehouses maintain the intermediate aggregation results as materialized auxiliary views rather
than recomputing them [QGMW96].
Example 7.1 (Materialized View for AllClothing) To improve the efficiency of the tracing
process in Example 6.4, we materialize auxiliary view AllClothing (in Figure 14) with the contents
shown in Figure 16.
Note that when materializing AllClothing, tuple hTarget, 1400i is not used when tracing
tuple derivations for Clothing. In fact it is filtered out by the selection condition oe total?5000
in Clothing's definition. In this case, materializing the result of V
instead of storing AllClothing seems to be a better choice. However, notice that V 0 is not incrementally
maintainable without storing AllClothing. Thus we would either need to recompute
for each relevant update, which would incur a high maintenance cost, or we need to store
AllClothing in any case in order to maintain V 0 . Therefore, materializing V 0 is not actually
likely to be an improvement. In general, given a view definition tree where selections are pushed
down as far as possible, all selection conditions above an aggregate must be on the summary at-
tributes, and therefore are not incrementally maintainable without storing the entire aggregation
results.
7.2 Storing Derivation Views in a Multi-Source Warehouse
The problems described earlier (e.g., inefficiency, inconsistency) in warehouse view derivation
tracing arise when we apply our tracing queries to remote sources. We therefore may prefer to store
auxiliary information about the sources in the warehouse, in order to avoid source queries during
each derivation trace. Note that these auxiliary views may be in addition to the intermediate
views for aggregate view tracing discussed in Section 7.1.
There are various strategies for storing such auxiliary views. A simple extreme solution is to
store a copy of each source table in the warehouse. Our algorithm will then query the base views
as if they are the sources. However, this solution can be costly and wasteful if a source is large,
especially if much of its data does not contribute to the view. Also, computing selections and joins
over large base views each time a tuple's derivation is traced can be expensive. Other solutions
can in some cases store much less information and still enable derivation tracing without accessing
the sources, but the maintenance cost is much higher. We propose an intermediate scheme that
achieves low tracing query cost with modest extra storage and maintenance cost.
After adding auxiliary views as described in Section 7.1, the view definition is broken down
into multiple ASPJ segments. Only views defined by the lowest-level segments are directly over
the source tables, and it is these views that are of concern. Let be such a
view. Based on V , we introduce an auxiliary view, called the derivation view for V . It contains
information about the derivation of each tuple in V over R as specified in Definition 7.2
given next. Theorem 7.3 then shows that any V tuple's derivation in R can be computed
with a simple selection and split operation over the derivation view.
Definition 7.2 (Derivation View) Let
Rm ))) be a one-level ASPJ view over the source tables. The derivation view for V , denoted as
DV (v), is
Theorem 7.3 (Derivation Tracing using the Derivation View) Let V be a one-level
ASPJ view over base tables:
DV (v) be v's derivation view as defined in Definition 7.2. Given a tuple t derivation can
be computed using DV (v) as follows:
Given tuple set derivation is:
Example 7.4 (Derivation View for AllClothing) The view AllClothing in Example 7.1 is
defined on base tables store, item, and sales. Suppose these base tables are located in remote
sources that we cannot or do not wish to access. In order to trace tuple derivations for
AllClothing, we maintain a derivation view DV AllClothing. Figure 17 shows the derivation
view definition, and Figure shows its contents. The derivation tracer need only to query
DV AllCothing to compute view AllClothing's tuple derivations, as shown in Figure 17.
Using known techniques, the auxiliary intermediate views and derivation views can be maintained
consistently with other views in the warehouse [ZGMW96, ZWGM97]. Note that in cases of
warehousing environments where the sources are inaccessible, the auxiliary views themselves need
to be made self-maintainable. Known techniques can be used here as well [GJM96, QGMW96].
s
a store_name,
s
sum(num_sold) as total
DV_AllClothing
AllClothing

Figure

17: View definition for DV AllClothing
store id store name city state item id item name category price num sold
001 Target Palo Alto CA 0004 pants clothing
Albany NY 0004 pants clothing 35 800
003 Macy's San Francisco CA 0003 shirt clothing 45 1500
003 Macy's San Francisco CA 0004 pants clothing
004 Macy's New York City NY 0003 shirt clothing 50 2100
004 Macy's New York City NY 0004 pants clothing 70 1200

Figure

AllClothing table
7.3 A Warehousing System Supporting Derivation Tracing

Figure

19 illustrates an overall warehouse structure that supports tuple derivation tracing with
materialized intermediate aggregation results and derivation views. Recall question Q2 from Example
3.2. The query tree on the left side of Figure 19 is the original definition of view Clothing.
In order to trace Clothing's tuple derivations, an auxiliary view AllClothing is maintained to
record the intermediate aggregation results (as discussed in Section 7.1). Furthermore, to trace tuples
in AllClothing, derivation view DV AllClothing is maintained (as discussed in Section 7.2).
The final set of materialized views is:
AllClothing = ff store name, sum(num sold) as total
(DV AllClothing)
Each view can be computed and maintained based on the views (or base tables) directly
beneath it using warehouse view maintenance techniques [QGMW96, ZWGM97]. Solid arrows
on the right side of Figure 19 show the query and answer data flow. Ordinary view queries are
sent to the view Clothing, while derivation queries are sent to the Derivation Tracer module.
The tracer takes a request for the derivation of a tuple t in Clothing and queries auxiliary view
AllClothing for t's derivation T 1 in AllClothing as specified in Theorem 5.3. The tracer then
queries DV AllClothing for the derivation T 2 of T 1 over D as specified in Theorem 7.3. T 2 is t's
derivation over D.
There are alternative derivation views to the one we described that trade tracing query cost for
store item sales Sources
Warehouse
Clothing
User
s
store item sales
AllClothing
derivation over D
derivation
over AllClothing
Clothing
DV_AllClothing
Derivation Queries:
View Queries
Derivation Tracer
s total > 5000
store_name,
sum(num_sold) as total
a
total total
total > 5000
store_name,
sum(num_sold) as total
a

Figure

19: Derivation tracing in the warehouse system
storage or maintenance cost. One simple option is to split the derivation view into separate tables
that contain the base tuples of each source relation that contribute to the view. This scheme may
reduce the storage requirement, but tracing queries must then recompute the join. Of course if
accessing the sources is cheap and reliable, then it may be preferable to query the sources directly.
However, a compensation log [HZ96] may be needed to keep the tracing result consistent with the
warehouse views. Determining whether it is better to materialize the necessary information for
derivation tracing or query the sources and recompute information during tracing time in a given
setting (based on query cost, update cost, storage constraints, source availability, etc.) is an
interesting question left open for future work, and is closely related to results in [Gup97, LQA97].
8 Related Work Revisited
In this section, we revisit some related topics, including top-down Datalog query processing and
the view update problem, and examine the differences between those problems and ours. We also
show how lineage tracing can be applied to the view update problem.
8.1 Top-down Datalog Query Processing
In Datalog, relations are represented as predicates, tuples are atoms (or facts), and queries or
views are represented by logical rules. Each rule contains a head (or goal) and a body with some
subgoals that can (possibly recursively) derive the head [Ull89].
There are two modes of reasoning in Datalog: the bottom-up (or forward-chaining) mode and
the top-down (or backward-chaining) mode. The top-down mode proves a goal by constructing a
rule-goal graph with the goal as the top node, scanning the graph top-down, and recursively applying
rule-goal unification and atom matching until finding an instantiation of all of the subgoals
in the base data. Backtracking is used if a dead-end is met in the searching (proving) process.
Top-down evaluation of a Datalog goal thus provides information about the facts in the base
data that yield the goal; in other words, it provides the lineage of the goal tuple. Our approach
to tracing tuple lineage is obviously different from Datalog top-down processing. Instead of
performing rule-goal unification and atom matching one tuple at a time, we generate a single
query to retrieve all lineage tuples of a given tuple (or tuple set) in an SPJ or one-level ASPJ
view. Our approach is better suited to tracing query optimization (as described in Section 5.3),
and we support lineage tracing for aggregation views, which are not handled in Datalog. We do
not handle recursion in this paper, although we believe our approach can be extended to recursive
views while maintaining efficiency.
8.2 View Update Problem
The well-known view update problem is to transform updates on views into updates against the
base tables, so that the new base tables will continue to derive the updated view. The problem
was first formulated in [DB78].
A view update can be an insertion, deletion, or modification of a view tuple. [Mas84] deduced a
set of view update translation rules for different view update commands against select, project, and
join views. Given a view update command, in some cases more than one set of base table updates
can achieve the same view update effect. Much effort has been focused on finding appropriate
translations for specific cases [BS81, CM89, Kel86, LS91]. In general, extra semantic information
is needed to choose a translation.
View update algorithms cannot be used directly to compute view tuple derivations. First,
none of the algorithms we know of consider aggregation. Second, although the algorithms do
identify a set of base tuples that can affect a view tuple, the base tuples identified may not even
derive the view tuple, and therefore do not satisfy our Definition 4.5 of a view tuple derivation.
In general, the view update approach and the derivation tracing approach answer two different
questions: "Which base tuples can affect a view tuple?" and "Which base tuples exactly derive
a view tuple?", respectively. The two questions are not equivalent, but they are related to each
other. Our derivation tracing algorithms can be used to guide the view update process to find an
appropriate view update translation in some cases. For deletions and modifications, our derivation
tracing algorithms can directly identify an appropriate set of base relation tuples to modify, as
shown in the following example.
Example 8.1 (View Update: Deletion) In Example 4.6 (Figure 12), we illustrated the
derivation for h2; 8i in view (R)). When the view update command "delete
h2; 8i from V " is issued, we can use the tuple derivation to determine that h2; 3i and h2; 5i
should be deleted, and these should be the only changes. The updated base table will be
which derives the updated view fh1; 6ig. Note that without using tuple
derivation tracing, a more naive algorithm might choose also to delete h2; 0i, which maintains
"correctness" but deletes more than necessary.
For insertions, the problem is harder, since the view tuple being inserted as well as its derivation
do not currently exist. Our derivation tracing algorithms can be adapted to identify some
components of the possible derivations of a view tuple being inserted, thereby guiding the base
tuple insertions. Any attribute that is not projected into the view must be guessed using extra
semantics, such as user instructions or base table constraints, or left null. Even here, derivation
tracing can help in the "guessing" process in certain cases, as shown in the following example.
Example 8.2 (View Update: Insertion) Suppose view update "insert h3; 2i into V " is issued
to the view in Example 4.6 (Figure 12). Since h3; 2i is not in view V , we cannot ask for its
current derivation. We only know that after we update R, R should produce a new view with h3; 2i
in it. According to the tracing query for V (as specified in Theorem 6.2), we can guess that after
the update, the derivation R   of h3; 2i must satisfy the condition: 8t 2 R
Assuming a constraint that R:Y attributes are positive integers, and considering the requirement
sum(R   :Y 2, we can also assert that 8t 2 R  2. By further assuming a constraint that
R has no duplicates, we can assert that Putting all these assertions
together, the only potential derivation of h3; 2i is h3; 2i, so an appropriate base table update is to
insert h3; 2i into R.
Notice that the inserted tuple in Example 8.2 was carefully chosen. If h3; 8i were inserted
instead, we would have to randomly pick a translation from the reasonable ones or ask the user
to choose. Even in this case, lineage tracing techniques incorporated with base table constraints
can be very useful in reducing the number of possible translations.
9 Conclusions and Future Work
We formulated the view data lineage problem and presented lineage tracing algorithms for relational
views with aggregation. Our algorithms identify the exact subset of base data that produced
a given view data item. We also presented techniques for efficient and consistent lineage tracing in
a multi-source warehousing system. Our results can form the basis of a tool by which an analyst
can browse warehouse data, then "drill-down" to the source data that produced warehouse data
of interest. Follow-on and future work includes the following.
ffl We have extended the results in this paper to view definitions that use bag (instead of set)
semantics, and to additional relational operators including [ and \Gamma. Please see [CWW98].
We also plan to extend our work to handle recursive views.
ffl Tuple derivations as defined in this paper explain how certain base relation tuples cause
certain view tuples to exist. As such, derivation tracing is a useful technique for investigating
the origins of potentially erroneous view data. However, in some cases a view tuple may
be erroneous not (only) because the base tuples that derive it are erroneous, but because
base relation tuples that should appear in the derivation are missing. For example, a base
tuple may contribute to the wrong group in an aggregate view because its grouping value is
incorrect. We plan to explore how this "missing derivation data" problem can be addressed
in our lineage framework.
ffl In Sections 7.1 and 7.2 we discussed trade-offs associated with materializing versus recomputing
intermediate and derivation views, and we mentioned briefly self-maintainability of
auxiliary views. We are in the process of conducting a comparative performance study of
the various options.
ffl We will apply our derivation tracing techniques to the view schema evolution problem, as
motivated in Section 1.
ffl We will further study how lineage tracing can be incorporated with existing techniques to
help solve the view update problem. As seen in Example 8.2, one interesting problem is to
extend our derivation tracing algorithms to handle tuples not yet in the view.
Most importantly, we are implementing a lineage tracing package within the WHIPS data
warehousing prototype at Stanford[WGL + 96]. Once the basic algorithms are completed,
we plan to experiment with appropriate user interface tools through which an analyst can
obtain and browse derivation information. For example, the analyst may wish to see not
only the base derivation data itself, but also a representation of the process by which the
view data item was derived.
In summary, data lineage is a rich problem with many interesting applications. In this paper
we provide an initial practical solution for lineage tracing in data warehouses, and we plan to
extend our work in the many directions outlined above.

Acknowledgements

We are grateful to Sudarshan Chawathe, Himanshu Gupta, Jeff Ullman, Vasilis Vassalos, Yue
Zhuge, and all of our WHIPS group colleagues for helpful and enlightening discussions.



--R

Update semantics of relational views.
An overview of data warehousing and OLAP technology.
Derived data update in semantic databases.

A complete solution for tracing the lineage of relational view data.
On the updatability of relational views.
Recovering information from summary data.
Data cube: A relational aggregation operator generalizing group-by
Data integration using self-maintainable views
Maintenance of materialized views: Problems
Maintaining views incrementally.
Selection of views to materialize in a data warehouse.
Issues for on-line analytical mining of data warehouses
Managing derived data in the Gaea scientific DBMS.
Implementing data cubes effi- ciently
A framework for supporting data integration using the materialized and virtual approaches.
Choosing a view update translator by Dialog at view definition time.
Physical database design for data ware- housing
Updating relational views using knowledge at view definition and view update time.
A relational database view update translation mechanism.
Maintenance of data cubes and summary tables in a warehouse.
Making views self-maintainable for data warehousing
Maintenance expressions for views with aggregation.
Incremental recomputation of active relational expres- sions
Database and Knowledge-base Systems (Vol <Volume>2</Volume>)
Research issues in data warehousing.
A system prototype for warehouse view maintenance.
Research problems in data warehousing.
Supporting fine-grained data lineage in a database visualization environment
The Strobe algorithms for multi-source warehouse consistency
Multiple view consistency for data warehousing.


--TR
Principles of database and knowledge-base systems, Vol. I
Research problems in data warehousing
A framework for supporting data integration using the materialized and virtual approaches
An overview of data warehousing and OLAP technology
Update semantics of relational views
The Strobe algorithms for multi-source warehouse consistency
Making views self-maintainable for data warehousing
Implementation of integrity constraints and views by query modification
Data Integration using Self-Maintainable Views
Supporting Fine-grained Data Lineage in a Database Visualization Environment
Multiple View Consistency for Data Warehousing
Physical Database Design for Data Warehouses
Data Cube
Concurrency Control Theory for Deferred Materialized Views
Selection of Views to Materialize in a Data Warehouse
Managing Derived Data in the Gaea Scientific DBMS
Aggregate-Query Processing in Data Warehousing Environments
Recovering Information from Summary Data

--CTR
Ling Wang , Elke A. Rundensteiner , Murali Mani , Ming Jiang, HUX: a schemacentric approach for updating XML views, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA
Hao Fan , Alexandra Poulovassilis, Using AutoMed metadata in data warehousing environments, Proceedings of the 6th ACM international workshop on Data warehousing and OLAP, November 07-07, 2003, New Orleans, Louisiana, USA
Laura Chiticariu , Wang-Chiew Tan, Debugging schema mappings with routes, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
Deepavali Bhagwat , Laura Chiticariu , Wang-Chiew Tan , Gaurav Vijayvargiya, An annotation management system for relational databases, Proceedings of the Thirtieth international conference on Very large data bases, p.900-911, August 31-September 03, 2004, Toronto, Canada
Yingwei Cui , Jennifer Widom, Lineage Tracing for General Data Warehouse Transformations, Proceedings of the 27th International Conference on Very Large Data Bases, p.471-480, September 11-14, 2001
Gao Cong , Wenfei Fan , Floris Geerts, Annotation propagation revisited for key preserving views, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA
Y. Cui , J. Widom, Lineage tracing for general data warehouse transformations, The VLDB Journal  The International Journal on Very Large Data Bases, v.12 n.1, p.41-58, May
Peter Buneman , Wang-Chiew Tan, Provenance in databases, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China
Todd J. Green , Grigoris Karvounarakis , Val Tannen, Provenance semirings, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China
James Annis , Yong Zhao , Jens Voeckler , Michael Wilde , Steve Kent , Ian Foster, Applying Chimera virtual data concepts to cluster finding in the Sloan Sky Survey, Proceedings of the 2002 ACM/IEEE conference on Supercomputing, p.1-14, November 16, 2002, Baltimore, Maryland
Peter Buneman , Sanjeev Khanna , Wang-Chiew Tan, On propagation of deletions and annotations through views, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin
Alon Halevy , Michael Franklin , David Maier, Principles of dataspace systems, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.1-9, June 26-28, 2006, Chicago, IL, USA
Michael Bhlen , Johann Gamper , Christian S. Jensen, An algebraic framework for temporal attribute characteristics, Annals of Mathematics and Artificial Intelligence, v.46 n.3, p.349-374, March     2006
Omar Benjelloun , Anish Das Sarma , Alon Halevy , Jennifer Widom, ULDBs: databases with uncertainty and lineage, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
Rajendra Bose , James Frew, Lineage retrieval for scientific data processing: a survey, ACM Computing Surveys (CSUR), v.37 n.1, p.1-28, March 2005
David T. Liu , Michael J. Franklin, GridDB: a data-centric overlay for scientific grids, Proceedings of the Thirtieth international conference on Very large data bases, p.600-611, August 31-September 03, 2004, Toronto, Canada
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
lineage;materialized views;data warehouse;derviation