| Decision support, also known as On-Line Analytical Processing (OLAP) is a rapidly growing application of databases. OLAP systems involve processing complex aggregate queries on very large databases commonly called "data warehouses." Query response times can thus be very large for OLAP queries. However, since OLAP is an interactive process, small query response times are required. Query processing and optimization are thus critical to the success of OLAP systems, and in this thesis we develop efficient query processing and optimization techniques for OLAP.; Precomputing frequently-used aggregates is the most commonly used approach to improving query performance. Since the available resources are usually limited, it is important to precompute the right set of aggregates. In this thesis, we give greedy algorithms that select the set of aggregates to precompute based on the available resources. We show that the benefit given by these greedy algorithms is close to that given by the optimal choice. Further, it has recently been shown that no polynomial-time algorithm can hope to do better than the greedy algorithm for this problem.; OLAP queries make heavy use of aggregations, and so to derive algorithms for OLAP query processing, we need to reason about aggregation. In this thesis, we present an intuitive framework that treats aggregation as an extension of the classical duplicate-elimination operator. Our framework enables us to derive rules to move aggregates around in a query tree. These move-around rules form the basis for query optimization of OLAP queries. We then use these rules as building blocks in deriving algorithms for more complex problems. In particular, we provide a powerful solution to the problem of aggregate-navigation: how to use an aggregate view to answer an aggregate query, a very important problem in OLAP. |
