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.