Improving Materialized View Selection under Storage Constraint

论文摘要

数据仓库和OLAP:在存储约束条件下改进物化视图选择数据仓库和联机分析处理（OLAP）已经渐渐成为数据库行业的中心,它们的能力和保障大大的提高了公司活动的成功率。数据仓库开发的一个重要的问题是物化视图集的选择,为了加快联机分析处理查询速度,需要限制空间和维护时间。另一方面,物化视图选择问题是一个NP问题,在三维模型中,视图的数目随着属性的增加而爆炸性的增长,并且高存储成本和高计算成本使它对于任何系统来说,要物化所有可能的视图都是不可行的。因此,物化所有的视图成为OLAP研究领域中的一个重要挑战。为了解决视图数目和存储成本的问题,本文提出了一种改进的贪婪算法,该算法在基于权重的情况下,选择最佳的视图进行物化。本文的第一部分首先回顾了数据仓库方面的基本概念,然后介绍联机分析处理的架构以及视图选择策略的处理。第二部分回顾了关于物化视图选择的相关工作,包括数据仓库和OLAP技术领域的许多研究成果,以及OLAP查询优化方面取得的成就,特别是物化视图选择的使用方面。第三部分提出了一种针对视图选择和物化的改进算法,在某些存储限制的情况下,该算法从候选视图集中选择一个最大程度利用单位空间的视图进行物化,一旦达到空间限制约束条件,并得到一个新的查询频率,就把物化视图集中最小花费的视图删除,重复执行该操作直到选择了一个最佳的物化视图集为止。最后,本文给出了该算法的仿真实验和查询结果。为了测试本算法的有效性,本文选择那些来自TPC-H基准查询集的查询作为我们的候选视图,因为这些查询结构都是由该候选视图集的第13次查询（视图）得到,本文添加了顶部视图,从而使其不能进行其他的查询。在本文的测试平台上,我们使用了复杂的SQL标准查询,查询集包含选择、映射、连接、存在或者不存在、外部连接,并且涵盖所有的常规聚合函数。我们在Windows Sever 2003操作系统上进行实验,内存为512兆,利用Microsoft SQL Server 2005查询生成器生成每一个查询结果,然后,利用Harinarayan等人提出的线性成本模型计算出每个查询的成本。根据实验结果的分析可以知道在进行第一次视图选择时,本文的算法和Harinarayan等人以及Chandrashekhar A. Dhote, Dr. M. S. Ali等人提出的经典贪婪算法具有同样的性能,然而,当在物化集中删除和添加新的视图时,本文的算法提高了物化视图选择的效率。

论文目录

• Abstract
• LIST OF FIGURES
• LIST OF TABLES
• CHAPTER 1:INTRODUCTION
• 1.1 Decision support Overview
• 1.2 Data warehouses and OLAP:Basic concepts
• 1.2.1 Different schema models in Data warehouse
• 1.2.2 Online Analytical Processing （OLAP）
• 1.2.3 Data Cube
• 1.3 Materializing views
• 1.4 Selection of views to Materialized
• 1.5 Motivation and Contribution of the Thesis
• 1.6 Outline of the Thesis
• CHAPTER 2:LITERATURE REVIEW
• 2.1 Deterministic Algorithms
• 2.2 Randomized Algorithm
• 2.3 Evolutionary Algorithm
• 2.5 Retrieval Queries in SQL
• 2.5.1 Basic SQL Queries
• 2.5.2 More Complex SQL Queries
• CHAPTER 3:IMPROVING MATERIALIZED VIEW SELECTION UNDER STORAGECONSTRAINT
• 3.1 The Proposed Strategy
• 3.2 Problem Formulation
• 3.3 Improving the BPUS heuristic algorithm
• 3.4 Limitations of the Proposed Strategy
• CHAPTER 4:EXPERIMENTAL RESULTS
• 4.1 TPC-H Benchmark and a Query Set
• 4.1.1 Queries used for performance evaluation of the algorithm
• 4.1.2 An OUTER JOIN Operation
• 4.1.3 The EXISTS and NOT EXISTS Functions in SQL
• 4.1.4 The IN Operator in SQL
• 4.2 Implementation of our improved heuristic algorithm
• ACKNOWLEDGEMENTS
• 附录A:详细的中文摘要
• APPENDIX B:FIGURES FROM THE SIMULATION PROCESS