学位论文 > 优秀研究生学位论文题录展示

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

作 者: 贾均刚
导 师: 高宏
学 校: 哈尔滨工业大学
专 业: 计算机科学与技术
关键词: 海量数据 高频度关系数据 压缩数据库 数据操作 按列压缩存储系统
分类号: TP311.13
类 型: 硕士论文
年 份: 2008年
下 载: 43次
引 用: 0次
阅 读: 论文下载
 

内容摘要


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

全文目录


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

相似论文

  1. 海量数据压缩、操作和处理方法的研究,TP311.13
  2. 基于逻辑卷的分级存储系统设计与实现,TP333
  3. 云环境下MapReduce容错技术的研究,TP302.8
  4. 磁约束聚变实验海量数据检索分析研究,TP391.3
  5. 非平衡数据集分类方法研究及其在电信行业中的应用,TP311.13
  6. 面向海量数据的云存储系统实现与应用研究,TP333
  7. 面向大型商业网站复杂业务的IT资源监控系统的研究与开发,TP277
  8. 三维体数据生成及三维缓冲区分析,TP391.41
  9. 基于云计算的海量数据存储技术的研究及应用,TP333
  10. 海量数据存储与全文检索,TP333
  11. 云计算中MapReduce性能优化及应用,TP3
  12. 林业海量数据的存储和传输方法研究,S712
  13. VRGIS中海量数据绘制关键技术与算法研究,TP391.41
  14. 基于HDFS的多用户并行文件IO的设计与实现,TP338.6
  15. 多输出函数逻辑综合的理论研究与程序实现,TN47
  16. 海量激光扫描测量数据的处理,TN249
  17. 网络存储在高校数字图书馆的设计与实现,G250.76
  18. 大型呼叫系统中数据管理分析平台的设计与实现,TP311.52
  19. 面向海量数据的分布式文件系统设计和实现,TP316.4
  20. 数据挖掘技术在电信业针对性营销系统中的应用,TP311.13

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 计算机软件 > 程序设计、软件工程 > 程序设计 > 数据库理论与系统
© 2012 www.xueweilunwen.com