基于BAP的数据压缩、操作与查询处理系统的实现

论文摘要

随着信息技术的发展及其在金融、交通、军事、生态环境检测、Web等领域的应用日益深入,海量数据大量涌现,这就要求数据库管理系统能够存储和处理上G、上T、甚至上P的海量数据。存储介质的价格/容量比的迅速下降使得海量数据的存储本身并不是问题,问题是如何有效存储和管理海量数据,并高效地支持上层查询处理。海量高频度数据中存在着大量的数据冗余,即同一数值会在同一属性列中多次出现。这不仅浪费了存储空间,也大大降低了查询效率。利用压缩数据库技术可以有效节省存储空间和I/O带宽。压缩数据库技术的研究内容包括:数据压缩算法以及压缩数据上的数据操作算法。近来,智能决策支持、在线智能商务以及数据仓库等新应用的出现要求数据库管理系统更好地适应主要面向数据读取应用的新特点。针对这个特点,数据库研究者们进一步审视传统数据库管理系统面向行存储的机制,开始研究并重新架构面向列存储的数据库管理系统。显然,面向列存储对于只读查询来说,因为仅仅从磁盘上读取与查询相关的属性列数据而不是整个元组的数据而大大节省了磁盘I/O。本文以现有关系数据库为基础,主要研究了适合于海量高频度关系数据的压缩算法以及存储结构和适合于压缩数据上的查询处理技术,包括数据操作算法和查询优化策略。本文的主要研究结果如下:提出了适合海量高频度关系数据的无损压缩存储算法TIDC。TIDC是一种基于属性划分的面向列存储的数据压缩方法。它通过整列数据的位置信息(TupleID)把按列存储的各属性列联系起来。对每一属性列的数据用其位置信息和相应的非常量值进行存储,实现了原始数据和压缩后数据的完全映射,有效去除常量数据,能够进行不解压(回算)而直接查询,达到了压缩存储、提高查询效率的目的。针对TIDC压缩存储策略提出了相应的数据操作算法包括选择、投影和连接,并给出了TIDC压缩数据上查询的部分优化策略。实现了BAP方法的压缩存储算法,给出了BAP压缩方法的数据操作算法包括选择、投影和连接,同时给出了部分查询优化策略。根据TIDC和BAP压缩存储方法的特点,设计并实现了一个海量高频度关系数据压缩存储原型系统。理论分析和初步实验表明:通过对原始数据进行属性划分,按列压缩存储,可以有效地减少存储空间,节省磁盘I/O,明显提高查询效率,而且,TIDC查询效率受数据量增加的影响不大。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 课题研究的背景和意义
• 1.2 国内外研究现状
• 1.2.1 数据库中数据压缩方法的研究
• 1.2.2 压缩数据库中的数据操作算法
• 1.2.3 压缩数据库中查询处理技术
• 1.3 本文的主要研究内容
• 1.4 本文的组织结构
• 第2章 预备知识
• 2.1 Golomb编码
• 2.2 BAP压缩方法
• 2.2.1 压缩存储结构
• 2.2.2 压缩常量获得
• 2.2.3 压缩效率
• 2.2.4 双向映射算法
• 2.3 本章小结
• 第3章 TIDC压缩存储方法
• 3.1 引言
• 3.2 压缩存储结构
• 3.3 元数据
• 3.4 压缩存储步骤
• 3.4.1 TIDC压缩存储步骤
• 3.4.2 BAP压缩存储步骤
• 3.5 无损性
• 3.6 压缩效率
• 3.7 本章小结
• 第4章 压缩数据操作算法
• 4.1 引言
• 4.2 TIDC压缩数据操作算法
• 4.2.1 选择操作
• 4.2.2 投影操作
• 4.2.3 连接操作
• 4.3 BAP压缩数据操作算法
• 4.3.1 选择操作
• 4.3.2 投影、连接操作
• 4.4 查询优化策略
• 4.4.1 投影操作推迟
• 4.4.2 涉及集合操作的优化
• 4.4.3 中间结果的优化
• 4.5 本章小结
• 第5章 原型系统实现及实验
• 5.1 原型系统
• 5.1.1 系统构架
• 5.1.2 模块功能实现
• 5.2 实验
• 5.2.1 实验条件
• 5.2.2 实验内容设计
• 5.2.3 压缩时间比较
• 5.2.4 压缩比比较
• 5.2.5 双向映射时间比较
• 5.2.6 选择操作时间比较
• 5.2.7 投影操作时间比较
• 5.2.8 等值连接操作时间比较
• 5.3 本章小结
• 结论
• 参考文献
• 攻读硕士学位期间发表的学术论文
• 致谢