Stanford InfoLab Publication Server

Storing Auxiliary Data for Efficient Maintenance and Lineage Tracing of Complex Views

Cui, Y. and Widom, J. (1999) Storing Auxiliary Data for Efficient Maintenance and Lineage Tracing of Complex Views. Technical Report. Stanford InfoLab. (Publication Note: 2nd International Workshop on Design and Management of Data Warehouses (DMDW 2000), Stockholm, Sweden, June 2000)




As views in a data warehouse become more complex, the view maintenance process can become very complicated and potentially very inefficient. Storing auxiliary views in the warehouse can reduce the complexity and improve the efficiency of view maintenance, and the same auxiliary views can help in efficiently answering lineage tracing queries over the warehouse views. In this paper, we study the problem of selecting auxiliary views to materialize in order to minimize the total view maintenance and lineage tracing cost. We consider relational views with arbitrary use of aggregation operators, and we define an initial search space for our optimization problem based on a normal form for such view definitions. We present several auxiliary view selection algorithms, and to study their performance we conduct experiments using the TPC-D benchmark in addition to synthetic view definitions and statistics. The results of our experiments show: (1) the exhaustive algorithm that selects the optimal set of auxiliary views is far too expensive in many cases; (2) two heuristic algorithms that we present select good (often optimal) sets of auxiliary views in a much shorter time; (3) even auxiliary views selected by a very simple algorithm can significantly reduce the overall view maintenance and lineage tracing cost.

Item Type:Techreport (Technical Report)
Uncontrolled Keywords:auxiliary view, maintenance procedure, view data lineage
Subjects:Computer Science > Data Warehousing
Related URLs:Project Homepage
ID Code:401
Deposited By:Import Account
Deposited On:25 Feb 2000 16:00
Last Modified:28 Dec 2008 08:54

Download statistics

Repository Staff Only: item control page