【作者】 陈佳；

【导师】 董红斌；

【作者基本信息】 武汉大学 ， 计算机软件与理论， 2010， 博士

【摘要】 数据仓库是一个面向主题的、集成的、不可更新的且随时间不断变化的数据集合,主要用于有效地支持决策支持查询。随着数据仓库的规模不断增加,这种涉及大量数据的复杂决策查询是非常耗时的。数据处理的低效意味着资源的浪费,因此,较高的数据查询效率对数据仓库来说是很重要的,是数据仓库系统设计的一大系统目标。为了提高查询性能,一种有效的方法就是使用辅助数据回答查询。在现代数据仓库系统中,一种常用的辅助数据就是实视图：将用户常用的查询或最可能的查询模式计算出来的结果或者中间结果的物理存储。有了实视图,基本上不再需要对原始数据进行处理,而只需要在实视图的基础上进行一些简单的计算便可以完成复杂的查询。在使用实视图提高查询效率的时候,必须解决两个重要的问题：实视图选择和实视图最优重写。本文就这两个问题进行分析研究并提出了详细的解决方案。实视图选择：实视图选择就是针对一个查询集,在给定的某些资源约束下选择一个视图集进行实化,使得该查询集的查询响应时间最小。首先,全面分析了数据仓库系统中实视图选择的特点、难点以及传统实视图选择方法的弊端之后,系统地介绍了分布估计算法的特性、方法,并采用分布估计算法从“宏观”层面上对群体建立数学模型来解决实视图选择问题；同时,提出两种混合遗传算法GEDA和BMUTGA,在后代的产生过程中同时利用全局统计信息以及局部信息来克服GA和EDAs的缺点,从而更有效地解决复杂的实视图选择问题。通过实验来验证所引入的UMDA以及所提出的GEDA和BMUTGA算法的求解质量和求解效率。测试数据及来自TPC-D的基准测试数据以及多种模拟数据集。实验结果表明,在不同的空间约束,不同的查询分布和视图大小分布下,本文所引入和提出的算法优于经典遗传算法。实视图最优重写：实视图最优重写问题就是对于给定的一个用户查询Q和实视图集V,找到Q的一个最优(等价)重写R。首先,与传统的查询优化进行了对比,全面分析了数据仓库中实视图最优查询重写的特点、难点以及传统的使用实视图最优查询重写方法的弊端之后,系统地介绍了启发式方法和遗传程序设计的特性,并分析了用启发式方法和遗传程序设计有效地解决利用实视图最优查询重写问题的可能性。其次,提出了两种新颖的基于实视图最优查询重写的算法BSHS以及SRGP来解决这个问题,主要贡献如下：(1)这两种算法基于包-集语义,这种语义被广泛的应用于当今的关系型数据库。在这个语义下,基本关系并不包含重复元组,而查询结果可能包含重复元组；(2)本文的算法不仅能处理合取(选择-连接-投影)查询还可以处理聚集(SUM/COUNT)查询；(3)所提出的算法不仅可以使用多个实视图重写还可以使用单个实视图重写,从而保证所产生的重写的近似最优性。通过模拟数据集,从求解质量和运行时间两个方面对算法进行了比较,验证了本文提出的启发式方法BSHS以及基于规则的遗传程序设计SRGP的有效性。更多还原

【Abstract】 A data warehouse is, by definition, a subject-oriented, integrated, time-variant collection of data, with the purpose of efficiently supporting decision support queries. As data warehouse keep growing in size, these complex decision queries which involve large volumes of stored data are very time-consuming. Inefficient data processing means of waste of resources, therefore, higher efficiency of data query is very important to data warehouse, also is a major goal in designing data warehouse.In order to improve query performance, it is an effective method to use auxiliary data to answer queries. In modern data warehouse systems, a common type of auxiliary data is materialized views:relations that are computed by answering certain queries on the (original) stored data in the database and that can be used to provide, without time-consuming runtime transformations, "precompiled" information that is relevant to the user query.To improve the efficiency of queries based on materialized views, there are two important issues:view-selection problem and optimal rewritten query using materialized views. This doctoral thesis focuses on these two issues and presents comprehensive solutions to both problems.View-selection problem:Given a set of queries to be supported, the view selection problem is to select a set of views to materialize minimizing the query response time given some resource constraint. Firstly, this thesis generally analyses the characteristic of view-selection problem in data warehouse system, the principle and the difficulty of the optimization, and malpractice of the traditional view selection methods, systematically introduces the characteristics and methods of estimation of distribution algorithms, and from the "macro" level, builds a mathematical model of population in the view-selection problem; meanwhile, two hybrid genetic algorithm are proposed, during the process of generate offspring, we can take advantage of the global statistical information and local information to overcome the shortcomings of GA and EDAs to more effectively address the complex view-selection problem. We ran some experiments to determine the quality of the solution delivered and the efficiency of the UMDA, GEDA and BMUTGA algorithms. Three algorithms named as UMDA, GEDA and BMUTGA are proposed in this paper, and ran them on the dataset in TPC-D benchmark and a variety of synthetic datasets. The experimental results show that the proposed algorithms outperform canonical genetic algorithm under different space constraints, different queries distributions and view size distributions.Optimal rewritten query using materialized views:This problem is, given a user’s query Q and a set of materialized views V, to find an optimal (equivalent) rewriting R of Q that is composed of views in V. Firstly, compared with the traditional query optimization, this thesis roundly analyses the characteristic of using materialized views to optimal (equivalent) rewriting in data warehouse system, the principle and the difficulty of the optimization, and malpractice of the traditional methods to the optimal query rewriting using materialized views, systematically introduce the characteristics of heuristic method and genetic programming, and analyzes the possibility with the heuristic method and genetic programming in optimal query rewriting using materialized views. Secondly, we propose two novel view-based optimal query rewriting algorithms BSHS and SRGP to address this problem, and make the following contributions. (1) The algorithms proposed in this paperunder bag-set semantic that have been widely used in today’s relational databases. Under this semantic, the base relations (i.e., data tables) do not contain duplicate tuples, while the query results may contain duplicate tuples. (2) The algorithms proposed in this paper for a large and practically important subset of SQL queries, which includes not only conjunctive (Select-Project-Join) queries but also aggregate (SUM/COUNT) queries. (3) The algorithms proposed in this paper explore multiple-view rewritings as well as single-view rewritings of the query to guarantee the approximate optimality of the rewritings they produce. This paper ran some experiments to determine the quality of the solution delivered and the time taken in practice by the heuristic method BSHS and rule-based genetic programming (SRGP) algorithms. We implemented both the algorithms, and ran them on a variety of synthetic datasets. The experimental results show that the proposed algorithms are effective.更多还原