A general framework for the view selection problem for data warehouse design and evolution

A Data Warehouse (DW) can be seen as a set of materialized views defined over remote source relations. During the initial design and evolution of a DW, the DW designer is faced, on many occasions, with the problem of selecting views to materialize in the DW. The problem has been addressed for different classes of queries/views, and with different design goals. In this work we unify these approaches in a general framework for materialized view selection for Data Warehousing. We first identify and analyze different design goals. A design goal can be the minimization of a cost function or a constraint of different types. We then define the general view selection problem that aims at satisfying all these goals together. This definition of the problem allows us to deal not only with the static design of a DW, but also with its evolution. We use expression AND/OR dags to represent alternative ways of evaluating multiple queries and views, and subexpression sharing. Our formalism is general enough to allow the representation of complex queries including grouping/aggregation queries, necessary in DW applications. We show how the design goals can be mapped into conditions on expression AND/OR dag structures. Using this mapping, we determine the search space for the general view selection problem, and we discuss algorithms for exploring it. Our approach can be used as is but it can be also applied to particular DW design cases where not all the design goals are required.