The Two-stage Stochastic View Selection Problem in OLAP Systems: Models and Algorithms.

摘要

We consider the problem of selecting views in an OLAP data-analysis system and propose a new paradigm to study this problem in a two-stage probabilistic environment, rather than the conventional one-stage environment. The objective is to minimize the processing time of a given collection of queries (first stage), plus the expected processing time of a (probabilistic) collection of future queries (second stage), while allowing for a partial replacement of the views in the second stage. We present a stochastic programming model for this problem and show that it is equivalent to an integer programming (IP) model. We study the structure of this IP model and reduce its size accordingly to the extent that it can be solved using available IP solvers. We then evaluate the benefits of this two-stage approach versus a comparable one-stage approach, and determine the value of perfect information in this context. In order to solve both the one-stage view selection problem and the two-stage stochastic view selection problem more efficiently, we define the cost-benefit ratio of each view which is a measure of effectiveness of the view. We conduct a theoretical analysis of the properties of the cost-benefit ratio, and employ this concept to develop exact and inexact methods to further prune the search spaces of potentially beneficial views so that we are able to solve larger instances of the problems.