Stanford InfoLab Publication Server

Selection of Views to Materialize Under a Maintenance-Time Constraint

Gupta, H. and Mumick, I. (1998) Selection of Views to Materialize Under a Maintenance-Time Constraint. Technical Report. Stanford InfoLab. (Publication Note: International Conference on Database Theory (ICDT 1999), Jerusalam, Israel, January 10-12, 1999)




A data warehouse stores materialized views derived from one or more sources for the purpose of efficiently implementing decision-support or OLAP queries. One of the most important decisions in designing a data warehouse is the selection of materialized views to be maintained at the warehouse. The goal is to select an appropriate set of views that minimizes total query response time and/or the cost of maintaining the selected views, given a limited amount of resource such as materialization time, storage space, or total view maintenance time. In this article, we develop algorithms to select a set of views to materialize in a data warehouse in order to minimize the total query response time under the constraint of total view maintenance time. As the view-selection problem for general AND-OR graphs is intractable, we design approximation algorithms for OR view graphs, a special case of AND-OR view graphs. The OR view graphs arise in many practical applications, e.g.,\ data cubes. We present a greedy heuristic that delivers a near-optimal solution. We prove that the query benefit of the solution delivered by the proposed greedy heuristic is within 63\% of that of the optimal solution. Our performance studies indicate that the proposed greedy algorithm almost always delivers an optimal solution. We also design an $A^*$ heuristic for the general case of AND-OR view graphs.

Item Type:Techreport (Technical Report)
Uncontrolled Keywords:view selection, maintenance cost constraint, data warehouse
Subjects:Computer Science > Data Warehousing
Related URLs:Project Homepage
ID Code:338
Deposited By:Import Account
Deposited On:25 Feb 2000 16:00
Last Modified:29 Dec 2008 10:52

Download statistics

Repository Staff Only: item control page