Research On Query Optimization In Data Warehouses

Data warehouses stores volumes of historical data, and OLAP applications involve complex queries on these data. Since response time should be small, query optimization is critical. Increasing amount of summary data is the most effective way at present to reduce response time, but the limited spaces restrict the amount of summary data. This dissertation studies it deeply from the aspects of data warehouses' concept model and logical implementation.From the aspect of data warehouses' concept model, it has been proved firstly in the dissertation that the structure of multidimensional data model is a bounded lattice when all dimension's structure are bounded lattices. This established the foundation for the optimizing method that is based on search lattice.A multi-medium and variable granularity storage method has been presented in this dissertation. The detail data that are seldom visited directly by OLAP are stored in low-speed medium (such as magnetic tape) to reduce data warehouses size, and the data stored in low-speed medium are aggregated to summary data to store in data warehouses for OLAP analysis. Several dynamic modulation algorithms have been provided to choose detail data to be stored in low-speed medium and to determine what kind of summary data the detail data stored in low-speed medium should be aggregated to. Experiments in the dissertation show this method can efficiently decrease the storage space and reduce response time of OLAP.Under the situation of limited storage space, reducing data cube size can increase the amount of summary data to be materialized. From the angle of data warehouses' logical implementation, the base single tuple problem, which commonly exists in data warehouses, has been analyzed and an XML-based method named X-OLAP, which use XML's structure to express the aggregation relationship among tuples in data cube, has been proposed in this dissertation in order to implement OLAP. It hasalso shown that all operations of OLAP can be executed in X-OLAP, the completeness and closure of algebra operation has been proved. This implementation method can reduce data cube size efficiently.Finally, the conclusion of this dissertation has been given and the development trend of OLAP has been predicted.