一种基于属性划分的数据库压缩技术研究

论文摘要

当今时代,随着各个领域信息量呈爆炸式的速度增长,用于存储和管理信息的数据库系统面临着巨大的挑战,将数据压缩与数据库管理系统相结合的压缩数据库技术也就应运而生。对压缩数据库技术的研究主要集中在增大压缩效率的同时,尽量减小对数据查询效率的影响。本文的主要工作如下：本文首先深入研究了现有的数据库压缩方法,进而研究了Bit级数据压缩算法和数据库查询的相关技术,然后分析了当前按行压缩数据库系统和按列压缩数据库系统中存在的缺陷。为本文的研究工作提供了基础理论。本文针对按列压缩数据库系统存在查询效率比较低的问题,使用Bit级编码方法,设计了一种基于属性划分采用同质属性策略的压缩存储模型(SPCS模型),即对关系进行属性划分,将具有某种共同性质的属性分别进行Bit级压缩编码,从而实现对数据的压缩,该压缩方法使得在数据查询时无需进行解压缩操作。结合Bit编码方法和数据库查询相关技术,本文设计了应用于SPCS模型的数据库查询算法,其中包括数据库的选择操作、投影操作、单表等值连接以及多表等值连接等算法,并设计了应用于SPCS模型的查询优化算法。基于SPCS模型,本文实现了SPCSDB数据库系统,并对该系统进行了测试。测试结果显示,当关系中以第一类同质属性为主时,SPCSDB相比于按行压缩数据库系统,增大压缩效率的同时,也提高了查询效率。

论文目录

• 摘要
• ABSTRACT
• 目录
• 第1章 绪论
• 1.1 研究背景及意义
• 1.2 研究历史与现状
• 1.2.1 不同粒度的数据库压缩方法研究现状
• 1.2.2 压缩数据库上的索引研究现状
• 1.2.3 压缩数据库上查询处理技术研究现状
• 1.3 本文的主要研究工作
• 1.4 本文的组织结构
• 第2章 压缩数据库相关基础理论
• 2.1 Bit级编码方法
• 2.1.1 K-of-N编码
• 2.1.2 Unary编码
• 2.2 查询操作相关技术
• 2.2.1 基于排序的投影
• 2.2.2 嵌套循环连接
• 2.2.3 排序归并连接
• 2.3 本章小结
• 第3章 基于属性划分的压缩存储模型设计
• 3.1 SPCS模型总体方案设计
• 3.2 SPCS模型的设计思想
• 3.2.1 基于属性划分压缩模型的设计
• 3.2.2 同质属性压缩策略的设计
• 3.3 SPCS模型的详细设计
• File数据结构的设计'>3.3.1 Bit_File数据结构的设计
• 3.3.2 DoubleKey-Btree数据结构的设计
• 3.3.3 TupleID-Btree数据结构的设计
• 3.3.4 SPCS模型元数据的设计
• 3.3.5 SPCS模型批量压缩算法的设计
• 3.4 本章小结
• 第4章 SPCS模型查询操作与查询优化设计
• 4.1 查询操作的代价分析
• 4.1.1 投影操作的代价
• 4.1.2 I/O的代价
• 4.2 选择操作的设计
• 4.2.1 DoubleKey-Btree和TupleID-Btree的选择操作设计
• File的选择操作的设计'>4.2.2 Bit_File的选择操作的设计
• 4.3 投影操作的设计
• 4.4 连接操作的设计
• P_Join的设计'>4.4.1 P_PJoin的设计
• C_Join的设计'>4.4.2 P_CJoin的设计
• T_Join的设计'>4.4.3 P_TJoin的设计
• C_Join的设计'>4.4.4 T_CJoin的设计
• 4.5 查询优化的设计
• 4.5.1 投影操作上推
• 4.5.2 单表选择操作处理顺序
• 4.5.3 多表等值连接操作的设计
• 4.6 本章小结
• 第5章 SPCS模型的实现与测试
• 5.1 实现一个压缩数据库原型系统SPCSDB
• 5.1.1 SPCSDB的系统架构
• 5.1.2 扩充关键字COMPRESSED
• 5.2 SPCSDB系统的测试
• 5.2.1 批量压缩时间效率比较
• 5.2.2 批量压缩空间效率比较
• 5.2.3 选择操作比较
• 5.2.4 投影操作比较
• 5.2.5 等值连接操作比较
• 5.3 本章小结
• 第6章 结论与展望
• 6.1 本文结论
• 6.2 展望与下一步研究方向
• 参考文献
• 致谢