基于Dwarf的语义OLAP关键技术研究与实现

论文摘要

OLAP技术是决策支持系统中的一种重要技术,用于管理人员决策分析。为了提高响应速度,需要对数据立方进行预计算。数据立方的计算在数据仓库中是非常必要但代价很大的操作。有效的数据立方（CUBE）计算成为研究的热点之一。 CUBE计算是OLAP即席查询分析的基础。CUBE操作内在的困难是计算代价和存储大小问题。一些文献提出了对CUBE计算的操作,包括并行性的应用、字符型映像到整型等,都是为了减少存储。但是随着新的应用,问题加剧了。比如,维数的增加和由此导致的CUBE大小爆炸性增长问题。其它文献已经提出了一些办法解决存储大小问题,而压缩的CUBE能同时减少计算时间和占用的空间。 Dwarf数据立方是一种高度的压缩结构,同时保持CUBE的语义,使OLAP查询易于实现。Dwarf数据方体将具有相同前缀和后缀的数据元素（Cell）压缩存储在一起。一般来说,数据方体在数据密集的地方前缀冗余比较多,数据稀疏的地方后缀冗余比较多。Dwarf数据方体存储时,消除了这两种类型的冗余,大大缩减了数据方体的存储空间。将一个完全实例化的数据方体缩减到一个非常紧凑的数据结构中。 本文研究了基于Dwarf的语义CUBE压缩技术。针对现有的Dwarf结构在实现过程中遇到的频繁I/O访问问题提出了改进算法—Q-Dwarf。另外,在实现基本Dwarf数据立方的基础上,进一步研究了以下几个问题。（1）为了更好的支持范围查询,研究并实现了聚簇算法。（2）实现了Dwarf数据立方的增量维护,研究并实现了基于三角形的增量更新算法。（3）为了更好的支持OLAP操作,研究并实现了基于文件的索引技术,实现其点查询和范围查询。大量实验表明,Q-Dwarf算法较原算法性能有明显提高,而且无论是在元组数较多的情况下还是在维数较多的情况下,我们算法的实现性能都较好。

论文目录

• 独创性声明
• 学位论文版权使用授权书
• 摘要
• Abstract
• 目录
• 第一章 前言
• 1.1 课题的来源
• 1.2 问题的提出
• 1.3 本文的研究目标和内容
• 1.4 本文的组织结构
• 第二章 相关工作
• 2.1 数据仓库简介
• 2.1.1 数据仓库概念和现状
• 2.1.2 数据仓库特征
• 2.1.3 数据仓库体系结构
• 2.2 OLAP的关键技术
• 2.2.1 多维数据模型
• 2.2.2 多维数据存储
• 2.2.3 CUBE计算问题
• 2.2.4 数据方体的查询
• 2.2.5 数据方体的更新维护
• 2.2.6 对流数据的联机分析处理
• 2.3 语义压缩存储技术
• 2.3.1 语义压缩简介
• 2.3.2 语义压缩存储技术
• 2.3.3 Dwarf存储结构
• 2.4 小结
• 第三章 Q-Dwarf:Dwarf构建优化
• 3.1 改进的动机
• 3.2 Chunk块
• 3.3 Q-Dwarf构建算法
• 3.4 性能分析与评价
• 3.5 小结
• 第四章 Dwarf CUBE增量维护
• 4.1 增量维护基本概念
• 4.2 增量维护策略
• 4.3 基于三角形的增量更新算法
• 4.3.1 三维的更新算法示意图
• 4.3.2 四维的更新算法示意图
• 4.3.3 增量维护算法
• 4.4 更新后的聚簇维护
• 4.5 试验测试与分析
• 4.6 小结
• 第五章 Dwarf查询技术与聚簇优化查询
• 5.1 OLAP分析介绍
• 5.2 Dwarf查询算法
• 5.2.1 Dwarf查询定义
• 5.2.2 查询条件的选取
• 5.2.3 查询算法描述
• 5.3 Dwarf文件的索引结构
• 5.4 Dwarf的聚簇优化查询
• 5.4.1 聚簇优化的提出
• 5.4.2 格的结构
• 5.4.3 聚簇优化算法
• 5.4.4 迭代优化视图
• 5.5 实验测试与分析
• 5.6 小结
• 第六章 总结与展望
• 6.1 本文的主要贡献和创新
• 6.2 进一步的工作
• 参考文献
• 致谢
• 攻硕期间参加的项目与发表的论文