基于列数据库存储稀疏数据压缩算法研究（可编辑）

基于列数据库存储稀疏数据压缩算法研究（可编辑） 基于列数据库存储稀疏数据压缩算法研究 天津师范大学 硕士学位论文 基于列数据库存储稀疏数据压缩算法的研究 姓名:乔晓丽 申请学位级别:硕士 专业:计算机应用技术 指导教师:孙华志 20100401天津师范大学硕士学位论文 摘要 随着数据仓库、决策支持等技术的广泛应用,数据库系统对执行引擎 查询效率的要求越来越高,因此人们提出了一种的新的数据库系统设计理念, 即 以列为基本存储单位的列存储数据库系统。 本文首先将列存储数据库系统与行存储数据库系统之间在存储结构、查询效 率上进行对比,得出列存储数据库系统在查询执行效率上优于行存储数据库 系统 的结论。研究了列存储数据库系统中的所适宜采用的字典编码、行程编码以 及位 向量编码等压缩技术。通过分析查询过程中不同属性列连接的时机的特点, 研究 后物化技术对于列存储数据库系统查询效率的影响,并进一步研究采取直接访问 压缩态数据的策略对数据库系统性能的影响。 结合列存储数据库系统与稀疏数据自身的特点,本文提出了一种列存储数据 库系统适宜存储稀疏数据的观点,并给出稀疏数据库的设计方式。通过研究稀疏 数据的应用场景,分析稀疏数据的存储结构特点,给出稀疏数据库常见的数据模 型。 最后本文着重研究了字典编码压缩算法中的.,分析并比较其两种 分支算法和各自的优缺点,提出了一种基于和算法的改 进算法,以便利用两者各自的优点提高算法的性能。进而通过实验,将改进后的 算法在压缩率和压缩时间上与和算法相比较,得出改进后算法在整 体上的性能优于和。 关键词:列存储数据库系统;稀疏数据库;压缩技术;锄一;查询效率天津师范大学硕士学位论文 蹦硒 缳, 锄锄巧吼百. 印 盟 晌 】治础 , . ? 硼%叫百, 百 】? 蚯 . 百 ,叮 髓 吐 ,? . 耐 叮 目. 嘶’ , 曲, 百 . ? 印’西. ? , 铆 , 锄?,锄 百. 锄缸曲 , . 咖 :嘶 % , 鼢 】?,巧 ?天津师范大学硕士学位论文 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我 所知,除了文中特别加以标注和致谢的地方外,论文中不包含其他人已经发表或撰写过的研 究成果,也不包含为获得苤壅竖垫盘堂或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 签名:李些日期:幽 学位论文版权使用授权书 本人完全了解天津师范大学有关保留、使用学位论文的规定,即:学校有权将学位论文 的全部或部分内容编入有关数据库进行检索,并采用影印、缩印或扫描等复制手段保存、汇 编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。 保密的论文在解密后应遵守此规定 期: 导师签名: 签名:盔哓豳 ?天津师范大学硕士学位论文 第一章 引言 .列存储数据库系统产生的背景 从逻辑层上看,关系数据库系统是以一张二维表的形式存储数据的,每行代 表着现实世界中的一个实体,每列都是这些实体的一个属性,例如,在一个顾客 信息表中,每行代表一个不同的顾客,每列代表某个顾客的一个属性,如姓名、 住址、电话等等。但是这种二维表只是存在于数据存储的逻辑层次上,在实际存 储数据的物理层次上,由于计算机的物理存储设备在读写数据时都是按线性的结 构进行的,于是便为数据库的存储结构提供了两种可能,按行存储和按列存储。 现今的关系数据库系统大多衍生于年代的锄项目原型和黟项 目原型,但是随着应用和硬件技术的发展,的需求不仅仅满足于锄 和黟设计面向数据处理的初衷,而更多的是地球科学【,、医学等数 据仓库以及决策支持系统等的的数据处理需求,而在这些应用中,大多数 信息都是散乱的、稀疏的,并且需要对数据进行大量的查询处理,以便对其进行 数据有效的分析处理;同时由于硬件技术的发展,传统的高性能硬件逐渐大众化, 使得数据仓库等应用得更加普遍。因此为了满足该类应用场景的需求,数据 库系 统发展的方向由满足数据处理的需求转向满足数据处理的需求, 是对列进行操作的,于是便衍生出面向分析处理的列存储数据 库系统。 . 软件的特点 在数据仓库中,将操作型系统数据库系统中的数据关系转变成数据仓库 模型,需要对操作型数据模型做一定的修改。数据仓库过程中的数据查询与事务 过程中的数据查询有很大的不同,主要表现在: 可预测性小。在数据处理过程中,因为数据库用于自动化业务 任务,查询是由一系列预定义的具体动作来初始化的,因此,应用于此查询的基 本结构是被提前编码的,而数据仓库中的查询伸缩性比较大,他们可以人为的初 始化。 持续时问长。事务查询语句比较短、简单,例如,添加客户信息,查 询账户余额等,而数据仓库中的查询语句因为其本身用于分析处理和决策,需要天津师范大学硕士学位论文 读取比较多的数据产生复杂的信息,如:一个分析客户属性和贷款风险之间关系 的查询语句需要查询客户与贷款 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 的很多条记录。 读操作比写操作多。在数据仓库中,写数据都是批量进行的,大部分 都是查询操作。 更关注属性而不是实体。在数据仓库中,通常不查询单个实体信息, 而是查询多个实体,并对它们进行聚集,如查询客户的平均账户余额等。同 时, 在一次查询中只关注少数属性列。 .列存储数据库系统的发展现状 列存储数据库的研究可以追溯到二十世纪七十年代,从开始研究置换文件开 始,紧接着,可以研究对表中属性聚集技术进行垂直分割。直到八十年代中 期, ,列存储数据库 中说明已分解的存储模型 系统的前身相对于传统的行存储数据库的优点,随后开始研究相对 于模型,模型在连接和列族索引方面的优势。由于市场的需求,以及 没有新技术的出现,使得行数据库系统成为主流。但从年开始,列数据库 的研究及其在商业中的应用开始成为一种趋势。 在此过程中,比较著名的列数据库系统有开源项目.【,是由麻省理工、 耶鲁大学、布朗大学等合作研发的,并于年发布第一版本,年升级为 第二版本。在.的研究基础上,又衍生出来商业化的缸以及内存数 据库系统。应用于哲的也是一种面向列存储的数据库系 统,该系统是舀内部开发用来处理大数据量的系统,罾的很多项目包 括网索引、哲 砷和谷歌财务都是建立在该系统基础上的,但与传统的关 系数据库不同之处在于其不支持任意 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 的查询,所以还不能是 完全意义上列存储数据库系统,但是的广泛应用显示了列存储数据库 发展的广阔前景。数据库大师 曾在一篇博客上写到,“在不 久的将来,列存储数据库系统将会占领数据仓库市场,完全取代行存储数据库系 统,因为现今的数据库系统不支持即席查询,除非升级设备,不然不能提高系统 的执行效率【,因此可以看出列存储数据库存储系统成为数据库发展的趋势。 .稀疏数据的应用场景 稀疏数据广泛存在于各种应用场景中,如:在分布式管理系统中, 天津师范大学硕士学位论文 用户可以自己定义新的属性,因此,在一个数据集中很多属性几乎都是空值;同 时,稀疏数据还大量存在于电子商务的应用中,每位商家都可以定义自己商品或 者订单特有的属性,从而使得数据有成千上万的属性值,如【】中有个属性, 但是对于每个元组,这些属性值几乎都是空值;在医掣、地球科学?等领域, 存在着大量的稀疏数据。 为了满足现今的需求,由于存储稀疏数据的表都具有至少几千个属 性,即宽表,而每次执行查询时并不需要读取表中的所有属性,显然,采用传统 的行数据库存储稀疏数据性能比较低下,因此,列数据库成为人们存储稀疏数据 的一种选择趋势,如现今流行的’就是采用列式存储。 .本文的主要贡献 本文中指出后物化技术对于列存储数据库查询效率的重要作用,并通过实验 对其进行分析,本文的实验是在的基础上实现的。在第二章将简述列 存储数据库系统研究的相关技术,本部分实验数据采用数据模型;第三 章将研究直接对压缩态数据进行访问的技术;第四章主要介绍稀疏数据库系统的 设计及其数据存储特点;第五章主要研究列数据库中采用的.压缩算 法及其改进;第六章提出本文中一些技术难点的研究方向。天津师范人学硕士学位论文 第二章列存储数据库系统研究的相关技术 .列存储数据库系统与行存储数据库系统比较 在传统的关系数据库中,用户可以方便的进行插入、删除及修改等更新操作, 因其存储结构是按行进行存储的,只要进行一次寻址操作,便可完成此操 作,所以行存储数据库系统非常适用于频繁进行更新操作的数据库系统中。但是 随着数据仓库、数据挖掘、决策支持‘和地理信息系统【】等查询密集型系统的发 展,关系数据库已不能满足企业的需求,因此,人们提出了一种基于列进行存储 的数据库系统,即列存储数据库系统。 ..列存储数据库的优势 列存储数据库与行存储数据的本质区别在于其存储结构的不同,在行存储数 据库中,数据是以记录或行为单位进行存储的,而在列存储数据库中,数据是 以 关系数据库中属性或列为单位进行存储的,数据表记录中同一属性的值都存 储在 一起,而同条记录中不同的属性值则分别存放于不同的文件中,以职工表为 例, 其存储结构如图.所示。 姓名 生日 工资 部门..叭王娟 信息 李红 ..儿 技术 杨阳 .. 信息 .. 姓名 王倩 研发 .儿. 王娟 王旭 技术 .. 李红 李情 研发 任娜 .. 信息 生日 娜 .. .. 行存储数据库数据存储结构 列数据库敦据存储结构 图.行存储数据库与列存储数据库存储结构比较 因为与行存储数据库的存储结构不同,列存储数据库系统中的列具有数据独 立性和操作独立性,可以支持独立的数据存储、数据压缩和数据操作,列存储数 天津师范大学硕士学位论文 据库有许多优势?: 一个语句可以分解为若干个可独立执行的、基于列的原子操作, 即,,??,列数据库只需要从磁盘读取相 关的属性,以节省/带宽。列数据库执行引擎访问数据的基本单位是单个属性 值,与行数据库对记录进行按顺序的逐条访问不同,列数据库对属性值的访问有 种方式:顺序访问、跳跃访问和随机访问。 例如:假设有表锄,,印,和查询语句,,哆。经过查询分析器的优化,执行引擎首先会访问属性,对于的行, 再访问属性,经筛选得到满足谓词条件的行号集合,然后根据的值将 这些行号排序,最后按这些有序的行号集合访问锄,而避免对属性印 的访问。在上例中,执行引擎对属性进行了顺序访问,对属性进行 了跳跃访问,对属性进行了随机访问,而对属性印饥则未访问。实 际上,列数据库的执行引擎在执行过程中,只对其中的一列进行顺序访问,而对 于其他列的数据都是按跳跃或随机的方式访问. 同一个文件中的数据具有相同的数据类型,相邻数据之间的相似性比 较大,增加了数据压缩比率【。 由于数据都以列的形式存储,在语句执行过程中,节省了行数据 库中映射运算的开销。 列存储数据库中可以进行轻量级的压缩,从而可以在不解压的情况下 直接对压缩态的数据进行操作。 通过执行查询语句,我们可以看出列存储数据库的查询执行效率要高 于行存储数据库,其性能对比如图.。 天津师范大学硕士学位论文 熏鬟 . . . . . 够均皴 图.行数据库与列数据库性能对比图 但是,列存储数据库系统也存在以下的缺点: 增加的磁盘寻址的时间。当并行读取多列时,需要从磁盘读取多个数 据块的数据,但是,增加预取数据的磁盘空间,可以降低这种代价。 增加了插入数据时的花费。在列数据库中插入需要寻找每个属性列的 位置,执行效率非常低,但是可以通过批量插入数据来消除此花费。 增加了元组重构的代价。为了给列数据库提供一个标准的通用关系数 据库接口,如、等,必须在查询 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 中将不同的属性列重组成元组, 虽然可以在内存中进行该操作,但是执行该操作的代价非常高。通常情况 下,采用后物化技术可以将该操作的代价达到最低。 ..研究列数据库的技术 随着数据库技术在商业分析、决策以及智能方面的应用,目前对列存储数据 库的研究越来越多,人们一般采用三种方法对其进行研究【刀。 在行存储数据库中,对表进行纵向划分,一张表被划分成多张只包含 ,两个属性列的小表【,源表中除了主键之外的所有的属性 列都对应一张小表,其分割结构图如.。 天津师范大学硕士学位论文姓名姓名生日 工资翻 生日 工资 。一. 信息 王娟 . 王娟 映 ?一 】.. 按术 挛红 孪红 射 ? 杨阳 .信息 杨阳 . 一 ..叭 研发 王倩 ..王倩 图.行存储数据库中表的划分图 执行查询语句时,只访问相关属性列所在的小表,并通过主键将其连 接,对相关属性进行投影,来执行查询操作。该方法对于含有属性越少的查询语 句执行效率越高。 第二种方法强调修改传统的行数据库的存储层结构,不改变其逻辑层 结构‘。在物理层,记录表是以列为单位进行存储,而不是以行为单位进行存 储的。该方法与第一种方法的区别在于:不是将主键与每个属性值存储在一起, 每列中的第个属性值与其他列中的第个属性值相关联。与第一种方法类似, 在执行查询语句时,只读取与查询相关的属性列,然后将其连接成一张记 录表,然后由传统的执行引擎来处理该查询语句。【中已经证明单纯的改变行 数据库的存储层结构并不能完全提高查询执行效率。 第三种方法是在存储层和执行引擎层次上改变行存储数据库【】,在物 理层上,数据以列为单位进行存储,同时执行引擎也是将数据以列为单位进行处 理。该方法能够在很大程度上提高数据库的查询效率,其执行过程如图.。 图.列数据库中查询执行过程及其优点 对列存储数据库中存储层和逻辑层的设计有详细的说明,】中对以上三 种方法做了对比实验,得出完第三种方法,即列存储数据库,在查询执行效率上 天津师范大学硕士学位论文 要明显优于其他两种方法。 .压缩技术 目前,压缩技术广泛应用图像存储中,因为其相邻像素之间以及色彩组成部 分的相关性,数据的相似度很大,使得采用数据压缩技术并不会影响图像的视觉 效果。随着对数据库技术的不断研究,人们也将数据压缩技术广泛的应用于数据 库技术中。压缩技术分为有损压缩和无损压缩,主要采用无损压缩技术压缩文本 和数据,被压缩的数据能够恢复,因此,在数据库中,采用的主要的是无损压缩 技术。 在传统的行数据库中,压缩技术对于提高数据的查询效率有很大贡献【】:压 缩技术减少了数据大小,降低了磁盘寻址时间以及数据传输时间,增加了缓冲区 的命中率,从而提高了/的效率。在传统的行数据库中,通常采用字典编码压 缩技术将编码比较长的数据转换成编码比较短的数据,如:“红色”一“,“黄 色”一“”,“绿色一“”等。在行数据库中,还经常采用哈夫曼编码等技 术。 除了上述特点外,列存储数据库还非常适宜于同时压缩多列的压缩模式,所 以列存储数据库可采用的压缩算法种类更多,如行程编码等,也可采用 对传统压缩算法改进后的算法。由于数据在列存储数据库中是以列为单位进 行存 储的,相邻数据间的相似性比行数据库中的大,所以数据的压缩率比较高【。其 次,内存中列属性值的迭代次数要比记录行的迭代少,从而可以通过矢量编码来 增加解压缩的速率。同时,列数据库中的每列都可以按不同的方式排序,而有序 数据有利于数据压缩。 列存储数据库还允许执行引擎直接对压缩数据操作,尤其是在行程编码等压 缩技术中,如:对某个属性列进行求和运算,已知值“”在该列中连续出现 次,在求和运算过程中,不必对该列解压缩,可以直接用×求出该 列的数值和。 显然,压缩技术能够提高磁盘的利用率,对/操作有很大益处。首先,访 问压缩数据时,降低了寻址空间和寻址时间;每个磁盘页中存储的数据增多,使 得更多相关对象的聚类存储在临近的位置;空闲磁盘可以用于磁盘映射,提高数 据的可靠性、易访问性以及/效率;压缩数据传输的更快,即能够增加磁盘的 天津师范大学硕士学位论文 带宽,能够缓解数据库系统的/瓶颈;在分布式系统中,压缩数据传输的效率 更高;同时缓存中可以存储较多压缩态的数据,因此能够增加缓存的命中率,减 少数据/的次数。同时列数据库有利于对压缩态数据进行操作,从而避免了解 压缩对系统性能的消耗,使得数据压缩技术的优势在列数据库中得到充分的发 挥。因此,本文在该章节中研究列数据库中主要采用的几种压缩算法。 ..消零或空格符法 该算法有很多变体,但是其基本的思想为:去掉连续出现的空值或者零,用 出现的次数和出现的位置来描述该列中所有的空值,如表示个连续的零, 表示个连续的空值,是行程编码的一种特例。 ..字典编码 字典编码属于无损压缩算法,其基本思想就是标识经常出现的符号模式,保 存于字典中,对这些经常出现的模式采用更有效的编码方式,即用其在字典中的 索引为码字,而其他部分采用缺省的编码方式。 字典编码包括静态字典编码、半适应字典编码以及自适应字典编码三种形 式。字典编码中最简单的形式是静态字典编码,该类字典中通常包含任意长度的 字段,以一种已经存在的编码形式为基础,如码,可以非常容易的建立该 字典,但是该类算法的压缩率不高,也有可能会导致压缩后数据的长度增加。而 半适应字典编码可克服该缺点,但是需要同时存储字典与数据信息,并需要在数 据上建立两条路径,一条是建立字典,一条是用来压缩数据。但是自适应字典 编 码完全克服了上述两种编码方式的缺点。 实用的字典编码,即自适应字典编码,核心是如何动态形成字典以及如何有 效的选择输出 格式 pdf格式笔记格式下载页码格式下载公文格式下载简报格式下载 ,以减小冗余。其编码思路为:利用数据本身包含许多重复的 字符串特性,例如:吃葡萄不吐葡萄皮,不吃葡萄到吐葡萄皮。如果用一些简 单的代号代替这些字符串,就可以实现压缩,实际上就是利用了信源符号之间的 相关性,其中字符串与代号之间的对应表就是字典。和是两种常用 的字典编码算法,其存在很多变种,是很多主流压缩算法的基础,我们将在第四 章中着重介绍该类算法。 在列数据库中,字典编码算法会先计算某个属性列所需要的字符数目,然后 根据具体的个数确定需要的字符位数,如表.。 天津师范大学硕士学位论文 表.职表格信息 姓名 年龄 工资 部门王娟 信息李红 信息杨阳 研发王倩 技术研发 信息 其中“部门”的属性值的种类是有限的,假如该公司中含有信息、研发、技 术、人事以及财务五个部门,则我们可以采用个比特位进行编码, 其编码如 表.。 表.字典编码表 信息 研发 技术 人事 财务表.就构成了一个字典,这样在数据被编码时,遇 到已经在字典中出现的 属性值时,编码器就输出该属性值所对应的位串,而不是属性值本身。假如该 公 司增加了销售部,则可以将销售部添加到字典中,用‘’来代替销售部。 ..行程编码 行程编码, 是一种最简单、最古老的数据压缩 技术,它视数据信息为无语义的字符序列字节流,基于简单的编码数据原则, 即重复的数据值序列或称为“流用一个重复次数和单个数据值来代替。这 里,重复的值称为一个“连续’’。实际应用时,采用多种形式的编码。 如: 未压缩数据: 其编码为: 对比该数据编码前后的代码数可以发现,在编码前要用个代码表示的数 据,而编码后只要用个代码,压缩比为.:。这说明确实是~种有效 的压缩技术,而且这种编码技术相当直观,也非常经济。所能获得的压缩 比有多大,这主要取决于数据本身的特点。 天津师范大学硕士学位论文 在数据库中,其常用的格式是由一个起位,止位和属性值构成的,如表.。 表. 虎编码格式图 该算法广泛用于图像的存储,也非常适用于列数据库,因为在列数据库中, 同一属性列中可能会连续出现某个值,同时可以对每列采用不同的排序方式, 所 以非常适宜采用此算法。 例如,在列数据库中,由于不同列中的属性值可以按不同的顺序排序,若表 .中“年龄”和“工资’’列分别按升序排序,其中年龄属性列经过压缩后可 以 变为,,,;工资列可以压缩为,,,,。当压缩 的数据少于个时,就没有必要再对数据进行压缩。 ..位向量编码 当列中的属性值的种类一定时,非常适合采用位向量编码。在该编码中,用 一个位向量表示该属性列,若含有某个值,将位向量中相应的位置“”,否则 置 “”,如下: , , , , , , 则的位向量为:,的位向量为:,的位向量为:。 .. 压缩算法 锄?编码是一种广泛应用的无损压缩算法,锄,简称, 拥有,,几种不同的演变算法。是一种典型的字典型压缩算法, 巧妙的利用字典,减少信息量。例子: 原始编码为: 现在有空字典一个,首先由第一的开始,索引对应,因为字典中没 有这个元素,所以索引对应,第三个,已经出现在字典中,我们推后一 位,没有出现在字典中,因此索引为加入字典。以此类推 索引最终用二进制方式表示,我们得到,,,,,,, 这个字典项,用位码可以表示,扩展了一位已表示各个元素间关系。 .物化技术 在列数据库中,数据以列为单位进行存储的,所以在数据输出时要对各列进 天津师范大学硕士学位论文 行重构成元组。每个列数据库体系都采用将元组的或者位置与属性值存储在 一起的策略,在重构的过程中,数据库根据来对各列进行连接操作。 在查询执行过程中,元组重构可以在任何不同的时间点进行,我们把在查询 耐, 执行计划开始时,进行元组重构的策略称为先物化技术耐 简称,而在查询执行计划后期,甚至是元组输出之前进行元组重构的策略 称为后物化技术 ,简称【】。 ..查询处理和优化 首先我们来看一下在数据库中查询处理的步骤,如图.【们。 语法分析器与翻 ’ 译器 ’关系代数表达式 查询 有关数据的统 计信息 图.查询处理步骤 对于给出的查询,一般都会有多种计算结果的方法,例如,已知在中, 一个查询能够用几种不同的方式表示,每个查询可以用其中的一种方式翻 译成关系代数表达式,以职工表为例,如 姓名 职工表 工资 其关系代数表达式可以表达如下: 天津师范大学硕士学位论文 吒瓷。姓名职工表 ?姓名仃工资。职工表 对于上述两个关系代数表达式,在执行查询的过程中,可以采取不同的执行 策略,对于每种查询的代价,我们可以通过该查询对各种资源的使用情况进 行度 量,这些资源包括磁盘存取、执行一个查询所用时间、还有在并行/分布式 数据库系统中的通信开销等。 在列数据库中,数据是以列为单位进行存储的,这样在进行查询操作时,需 要对每列数据进行连接。在数据库中,数据连接可以发生在不同的时刻,通常 会 嘶和 击两种物化方式。 采用 .. 与物化技术比较 物化技术的特点:在查询执行的任何时刻,当所访问的属性列被 后续的执行引擎访问或者被包含在输出序列中时,就将其属性值添加到元组 中, 这样能够减少查询执行引擎对磁盘的访问次数。 但是,在列数据库中,物化技术并不完全适用于任何场合。如:一个查 询计划中需要对三个属性列尺。,心,,分别做选择操作仃。,盯:,仃:,在 物化策略中,其执行顺序如图.。 曰曰回 图.执行引擎采用物化技术的执行过程 在此过程中,连接操作先于选择操作,因为对,垦,所有数据做连接 操作,的代价较高。 后物化技术的特点:执行引擎能够直接对压缩数据、面向列的数据进 行操作,避免了解压缩,提高了查询执行效率,同时推迟了查询计划中的元组 重 构,从而减少了数据连接的次数。以中的例子为例,其执行过程如图.。 天津师范大学硕士学位论文 读 图.执行引擎采用物化技术的执行过程 因此,两种物化技术并没有优劣,而是适用于不同的场景,但是在】已经 证明物化技术在列数据库中具有更大的优势,这是由列数据库的存储特点所 决定的。在列数据库中,数据是以列为单位进行存储的,在查询执行过程中, 若 先做选择操作,可以减少记录连接的条数,提高查询执行的效率。 .分布式特点 在列数据库中,引入了“列族’’的概念,列族是建立在一个特定的逻辑表 上的,包含该表中一个或者多个属性值。此外,列族也可以包含其他表中的任 意 属性,只要其与基表之间存在:,的关即可。例如:有关系 锄,,,,锄,我们可以将其 分解为以下几个列族: 绵锄, 邑:垄咒印,,. 假锄, 正锄, 列族中的元组是按列进行存储的,因此,如果一个列族中含有个属性, 将会存在种数据结构,每种数据结构存储一列数据,所有的列都是按同一个 排序键进行排序。如上述列族可以按下列键进行排序: 上互织锄, . 上:咒,,. 天津师范大学硕士学位论文 织锄,拶 巧 尸正锄, 列族是访问控制的基本单位,每一列可以存储在不同的列族中,这与集中式 数据库系统尽量降低冗余的特点不同,在列数据库中,数据冗余是所必需的,列 存储数据库系统通常都是分布式系统,可以将这种数据库系统看作是一系列集中 式数据库系统的集合,它们在逻辑上属于同一个系统,但在物理结构上是分布式 的。分布式数据库系统具有以下优点: 更适合分布式的管理与控制。分布式数据库系统的结构更适合具有地 理分布特性的组织或机构使用,允许分布在不同区域、不同级别的各个部门对其 自身的数据实行局部控制。 具有灵活的体系结构。集中式数据库系统强调的是集中控制,物理数 据库是存放在一个场地上的,由一个集中管理。多用户只可以通过近程 或远程终端在多用户操作系统支持下运行该来共享集中式数据库中的数 据。 在一定的条件下响应速度加快。如果存取的数据在本地数据库中,那 么就可以由用户所在的计算机来执行,速度就快。 可扩展性好,易于集成现有系统,也易于扩充。 同一列族可以分布在不同的结点,即同一列族会在不同的结点有多个副本, 如果一个结点发生故障时,可以在其它结点上到该结点存储的信息,尽管一个结 点发生故障,系统仍可以继续处理该列族的查询。如果绝大部分对关系的范 文都只会导致对关系的查询,可以对关系中的各个列族做并行处理。但是分布式 数据库系统也存在缺点,当数据进行更新时,需要更新所有副本的数据,使得所 有数据保持一致,因此增加了系统的开销。 分布式数据库系统已经成为信息处理学科的重要领域,正在迅速发展,随着 云计算技术的广泛应用,分布式数据库系统将会得到更广泛的应用,就 是一个已经广泛使用于网络的分布式列数据库系统,分布式数据库系统执行查询 操作的过程如图.。 天津师范大学硕士学位论文 系统 图.分布式查询执行过程 天津师范大学硕士学位论文 第三章压缩态数据访问 在列存储数据库系统中,采用压缩技术能够减少数据的存储空间,也降低了 数据从磁盘读入到内存时的空间消耗,但是在读入数据后,对数据进行解压缩消 耗的时间可能就会抵消,并不能达到压缩数据的目的。】中的研究已经证明直 接访问态数据,可以大大的提高数据库的执行效率,因此,在数据库体系的构 造 过程中,我们尽量采用直接对压缩数据进行操作的策略,使得查询执行引擎 直接 访问压缩态数据。 但是,对于不同的压缩算法,执行引擎直接操作压缩态数据的能力是不一样 的,对于.节中的压缩算法,执行引擎直接访问字典编码中的数据的效率比较 高,有两种方法可对其进行访问,一种是直接从一个位的字典压缩记录中提 取单个编码,通过在这些属性上执行 操作来计算总数,然后将每个编码 还原成原来的值,可将还原后的值求和。例如,表示数值,表示数值, 表示数值,假设聚合器接收下列字符串: ,,,,, 接着聚合器就会计算每个字典输入流中数值的个数::;:;: ,然后再对数据进行解码并计算数据的和,输出,,。 另一种方法与第一种方法相似,除了在解码之前,对所有的输入流进行分组, 并计算出包含特定值的每个输入流的个数,并在解码时做 “咒×?觑操作。 除了可以直接对字典编码数据进行直接访问之外,还可以直接访问行程编码 以及位向量编码数据,我们可以发现直接对压缩态数据操作可以使执行 引擎的查询效率比较高。在接下来的章节中,我们分别研究在存储层以及逻 辑层 数据压缩及其访问的过程,其中以压缩整数访问以及数据仓库中采取的压缩 态访 问为例进行研究。 .压缩态整数访问 本节中我们主要来分析整数的压缩结构和压缩态数据访问,以此来了解压缩 数据的访问过程及其原理,压缩整数的本质其实就是对二进制流的压缩过程。 天津师范人学硕士学位论文 ..整数压缩流程 整数压缩采用空格或者零消除算法,针对.间的 位无符号整数,而大于的整数不能压缩,为了将整数压缩用于数据 库,首先对其可压缩范围进行扩充,使其能够对任意的位无符号整数进行压 缩。 压缩后的数据依照压缩前的顺序连续存放在一起,并且压缩后整数各字节的 顺序与内存中整数的存放顺序相反,即高地址为最低位,低地址为最高位。定位 压缩态数据是指一个在包含个整数的压缩态数据块中,假设其大小是字节, 对于给定的任意整数?,?,找出第个整数在压缩态数据中的首地址。例如: 第个整数在压缩态数据中的首地址是,如果它占个字节,则第个整数在压缩 态数据中的首地址即为,依次类推。因此,只要找到了某个整数在压缩态数据 中的首地址,就可以不用解压整块数据而直接取出其值,扩展后的定位算法如下 【】: :整数个数;:待定位的位置号;.压缩态数据首地址 仃【】 //臼最高位是 //第个整数占个字节 /胁次高位是 ‖第个整数占个字节 //缸第最高位是 //第个整数占个字节 缸办娜第最高位是 //第个整数占个字节 ‖第个整数占个字节 天津师范大学硕士学位论文 冱 ‖第个整数的首地址 最坏情况下比较次数为其中循环控制也需要次比较运算, 位运算次数为,加法运算次数为,共次运算。其平均运算次数为次比 较、次位运算和/次加法,共.次运算。 ..访问定位方式 由.节中的算法可知,对于包含个整数的压缩态数据,只能从前向后逐个 计算每个整数压缩后的长度,才能找到第个整数的地址或者偏移量,而不能 采 用逆向的顺序即从后向前逆向定位。下面对压缩格式进行改进,使压缩后的 整数 不仅可以从前向后定位,同时还能从后向前定位。将所有的标志位集中,行程 一 个印作为头部。其中,每一位表示对应压缩态数据中特定的字节是否为某个 整数的最高字节。如压缩后需要个字节的整数其头部就是,表示前两个字节 不是最高字节,第个字节是最高字节,而第个字节是,压缩后不存储。并对 其标志位进行定长编码:对每个压缩态的整数,头部用两位表示其长度,表示 个字节,表示个字节,表示个字节而表示个字节。其特点是通过集中 标志位能够直接定位数据,其算法如下: ‖从前向后定位 ./ 币一 / 仃× ×针】 仃:× ×】 %瓜 ‖第个压缩态整数的首地址相对压缩态数据首址 ‖的偏移量 ‖从后向前定位 ; ? : 天津师范大学硕士学位论文 【】中已经证明该算法的对数据的访问效率要高于传统的解压缩方法。 . 压缩态数据访问 在多维数据仓库中,多维数据占用的数据空间很大,并且数据的稀疏度很高, 需要通过数据压缩来提高数据的密度,进而减小数据的存储空间。 ..压缩原理 本节中主要研究数据仓库中多维数据的压缩流程,在心多维数据仓库 中,采用多维数组替代存储维度值的形式存储记录集,并将多维数组转换成 线性 数据,最后采用一种完全映射的压缩方式压缩线性数组。 一个维数组,,??,;,,??,,其中,,??, 表示维度,,,??,表示值,中度量值分别存储在一个单独 的数组中,的每个维度数组组成维数组的一个维度,并不存储总的维度 值,而是存储决定维度值位置的数组索引,最后将维数组映射成一个线性数 组‘?。 在直接访问压缩数据的研列中,提供了两种映射方式,向前映射和向后映 射。向前映射是指计算源数据集中给定位置的数据在压缩数据集中的位置, 而向 后映射指计算压缩数据集中给定位置的数据在源数据集中的位置。而如果算 法提 供两种映射方式,则称之为完全映射。 ..聚集算法访问流程 假设数据以压缩多维数组的方式存储,每个数据集只含有一个度量。若 ,,??,;是一个多维数据集,在中的维度顺序,如?, 的度量值存储在一个线性数组中,并且,表示第.个维度,不同纬度顺序产 生不同的度量值顺序,假设的存储为??。 一个聚集算法的输入内容包括一个数据集,,??,;,一 个纬度集,并且满足,,??,,,??,,一 个聚集函数。输出内容包括一个数据集,,??,;,其 中是通过聚集函数计算中的度量值得到的值。 算法的流程可分两步,首先是位置转换,将多维数据集中的维度顺序转天津 师范大学硕士学位论文 换成~个聚集器可以比较容易计算的顺序,例如,,,,;是一 个四维度的数据集,从的顺序存储在一个线性数组中,假设按,进 行分组,则和是比较理想的顺序。第二步是聚集阶段,算法计算 转换后中的聚集函数值,其过程如图.所示。 ,狞 《 ’\\ ? ? ,,/ 转挽 一 ? , 多鼢;一 艇九。,; .; 图.聚集算法流程 天津师范大学硕士学位论文 第四章稀疏数据库的设计 随着信息技术的发展,在商业、医疗和科学等领域所产生和使用的数据量越 来越大,而在这些海量的数据中,很多数据都是稀疏的。 .稀疏数据 ..稀疏数据 稀疏数据是什么首先来看一下我们所熟知的稀疏矩阵的描述。 假设在聊×厅的矩阵中,有个元素为非空。令万上,称万为矩阵的稀 ,竹×, 疏因子,通常万?.时称为稀疏矩阵【。 在关系数据库中,由于数据在逻辑层上,其结构也是一个二维表,其与稀疏 矩阵结构相似,我们可以通过稀疏矩阵的描述来理解稀疏数据。在数据库中, 稀 疏数据就是在二维表中含有大量的空值。 ..稀疏模式 为了降低存储成本,传统的行数据库也提供了一些对稀疏数据处理的特殊方 法以降低数据库所用空间,如 中推出了一个与定位可 ? 为空字段的技术,即稀疏列,它为可为空字段提供了最佳的存储, 不会为稀疏列中的空值分配空间,但是在使用这个特性时会增加对非空值数 据提 取的代价。 接下来,我们来研究稀疏数据库的相关设计,稀疏模式的定义如下: 定义设关系彳。,,??,彳。是满足的关系模式,其中彳。是 主关键字:彳:,??,彳。是的属性,且元组中爿:,??,彳。对应值的空值 存在,则称产生的数据库为稀疏数据库,称为稀疏模式?。例如,宾馆管 理系统中收银子系统中的记账模式:账号,日期,房租,餐费,洗衣,电话, 场租,:天津师范大学硕士学位论文 表.稀疏模式表 账号 日期 房租 髻赘 洗衣 电话 场租 叭 .. .. .. 其中洗衣、电话等属性对应值有空值存在,当我们用行数据库存储稀疏数据 时就会有大量的存储空间被浪费,而且还增加了管理的困难,又大大降低了 处理 的效率。采用该数据存储模式,会出现大量的数据冗余,另外,这种模式在增 加 /删除属性时也带来了很多麻烦。 在我们对稀疏数据库进行改进前,先介绍一下数据库代价模型。 ,,??,尺。是源数据表。 ,,??,是定义在上的一组查询。 。,,??,。是查询频率。 ,疋,??,只是源数据表变化传播频率。 总的查询代价?,木 总的维护代价?;枣圪 目标是总的查询代价?用户给定的值情况下,使得可维护的总代 价最小【】。 而将该稀疏数据表存储在列数据库中,具有以下优点: 可以采用.节中介绍的数据压缩算法,提高了数据的密度,从而减 少了数据的存储空间,其存储模式如图.。天津师范大学硕士学位论文 、 八 厂 电话 。日期 房租’ 餐费 洗衣 场租’ 网 ,, ,, 匝司 .. 耐 ,, 卜???? .?一 .................一 图.稀疏数据在列数据库中的存储结构 其中,表示终止位置,在上图中,以日期列为例,该列中的数据压缩率 可计算为: 一竺:丝型望竺丝?兰丝型垒丝丝×% 毒 其中表示不同的日期个数,表示记录的总条数,在行数据库中存储 该表需要幻砌,木昆卿口把大小的空间,而在列数据库中,同期的存储格式如图 .,所以该表需要肌毒彪咖以胞木昆,鼢砌?大小的空间。 我们可以用一个简单的关系来表示消费项目的域,如消费项目, 则增加或删除消费项目时,不需要改变数据模式,可以直接添加消费项目列,因 为在列数据库中,数据以列为单位进行存储,不同的列可以存储在不同的磁盘块, 大大的提高了数据的可靠性,降低了编码难度。 在执行查询操作时,只读取相关的属性列,如“账号,金 额 账号”,只读取账号与金额两列即可。 综上所述,列数据库存储稀疏数据,不仅降低了存储空间,而且还有利于数 据的维护,是一种比较有优势的存储方式。 .稀疏数据的应用场景 除了数据仓库和领域中,非常适宜采用列存储数据库系统来存储之 外,由一些半结构化的语言如、等转化为稀疏数据后,也非常适宜于天津师范大学硕士学位论文 存储在列数据库系统中。 ..资源描述框架 资源描述框架 嘶 ,简称国用于描述曲 站点和页面,是语义网络中用于实现不同应用程序之间信息共享和集成的数据模 型。其设计目的是提供一种强有力的表述、交换与利用元数据的机制,通过对一 般意义上的语义、语法和结构的支持,提供在各种不同的元数据体系之间的互操 作性,使不同的用户和团体能够在这一框架下应用他们自己的元数据元素。 在描述资源网站,网页,甚至于一个不存在于网络中的对象时, 采用资源,属性,命 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 的结构,如: ://阳...,作者,天津师范大学 其中印://、矾棚,肌..是所描述的资源,“天津师范大学是其作者。 在行数据库中,一般采用资源,属性,命题的三元结构存储数据 【,但是在进行数据查询时,需要进行很多次自连接,这样降低了查询的效率。 而为了减少自连接的次数,可以将同一资源的所有属性放在同一行中,其中未定 义的属性值置为,这样形成的表称为属性表或者资源一属性矩阵物化连接视 图,即水平行表示。 图.存储结构 在水平行表示中,会出现很多空值,数据是稀疏的,同时不同的资源可能会 添加属性,使得?非常符合列数据库存储数据的特点,即可以采用压缩技术天津师范大学硕士学位论文 提高数据的存储密度,以及数据以列为单位存储,比较容易扩展表,即添加新的 属性列。 目前由百内部开发就是列存储数据库系统的一个具体应用, 酉将其定义为一种用于管理超大规模结构化数据的分布式存储系统,可以 管理分布在数以千计服务器上的以计的数据。只有在以下情况下使用 远才能带来益处:需要伸缩到巨量的用户数;更新与读操作相比比例很小。 为了优化读取速度和可伸缩性,所采取的理论路线与关系数据库中做法存在根本 的分歧,关系数据库是以防止错误为主要目标,以正规化为工具消除重复和防止 更新异常,而为了提高可伸缩性,数据应该重复而非正规化,虽然非正规化违背 了关系数据库的理论,却是数据范式不可缺少的组成部分。 .. 可扩展标记语言 ,简称,是一种半结构 化的语言。的用途,一是可以作为元置标记语言,用来定义各种实例置标 语言,二是可以作为标准交换语言,用来描述交换数据,在网络环境中有着广 泛 的应用。主要是为网页创建者或出版者元数据信息使用,而数字图书馆的 编目员和其他信息组织工作者对网络信息资源编目一般则通过??来进行。 由于】?的层次结构与行数据库的扁平结构不一致,很多存储策略中,都 是根据模式映射成关系数据库中的表模式,同时将的属性作为关系 表的属性,的节点元素作为属性值进行存储,同时将父子关系和兄弟间的 信息也作为不同的属性列进行存储,如图.和图.。 图. 的和文档 天津师范大学硕士学位论文 划 划 嗽 眇 . 纪锨伦 巴黎嫩 .挣钆每 沙‘,海 ’程溉 ;嘲 .如?缸 姆, 天话浸汁蠖。? 图. 在行数据库中的存储 但是,在上述存储模式中查找某本书的信息时需要做大量的连接,同时因为 的一个特点,就是用户可以定义属性,如果某用户给书添加一个属性,如 出版日期,就需要修改表的设计模式,数据库的维护代价比较高。 因此,如果我们采用传统的方法定义表的关系模式,将中同一父节点 的所有属性和元素都存储在一条记录里,这样有利于用户对??文件进行扩展, 用户添加新的属性或者元素后,需要重新定义表的关系模式,修改表的结构,并 重新存储表中的数据。但是,如果我们采用列数据库来存储这些信息,在用户动 态添加新的属性或者元素时,并不需要修改原来表的结构,同时也不需要重新创 建表及存储表中数据。同时文档对应的关系表中会出现很多空值,即稀疏 数据表,该表的特点正好适宜存储在列数据库中,采用适当的压缩技术,可以提 高了数据的存储密度。 .. 模型 觚曾在】中指出,“关系模型的局限性在于它缺少语义,使得不能对 关系模式完全进行建模,不能完全表达出自然界中关系以及实体间的联系。因 此他提出一种可扩展的关系模型,使得在同一个概念模式中具有泛化、设置属性 值以及稀疏属性等特点,与实体其它的属性一样。 如:一个银行账户含有如客户姓名、分行名称等属性,同时它可能是一个支 取账号或者是一个存储账号,每种不同的账号含有不同的属性,如存储账号可能 有利率属性,而支取账号可能含有年费,于是,就分解成三个表:银行账号表、 支取账号表和存储账号表。 传统的思想是给每~个泛化类型添加一个表,如一个支取账号表和一个存储 账号表,但是,对于同一个泛化添加多张表会降低查询效率,例如:当查询存储 账号表中的利率时,可能需要与账号表做连接操作,增加了系统的额外开销。而 天津师范大学硕士学位论文 指出,这样会导致不正常的模式,将银行账号作为一个实体存储在一张表 中会更好。同时,在一张表中表示泛化会增加表的宽度,同时也引入了空值,如 支取账号在所有存储账号的属性上都是空值。如果采用列数据库来存储,会降低 增加表的宽度和稀疏程度给系统造成的不利。 设置属性值会增加表的宽度,稀疏属性会增加表的稀疏程度,所以也非常适 合采用列数据库来存储。 目前,并未广泛使用模型,因为行数据库系统中数据存储依赖与系统 本身,限制了这种模型的使用,但是在列数据库中,这种模型有望会得到广泛的 使用。 .数据模型 在传统的关系数据库设计过程,关系数据库中的关系要满足一定的要求即规 范约束条件,数据规范化的优点就是减少数据冗余,节约了存储空间,相应 逻辑和物理/次数减少,同时加快了增、删、改的速度。数据库的规范化提高 了系统的性能,但是不是单纯的为了规范化而规范化,一个完全规范化的设计并 不能总能生成最优的性能,因为使数据库规范化的方法是把表拆分成相关列最少 的表,在进行数据库查询时,通常需要更多的复杂的联结操作,这样查询时就需 要用较多的资源和输入输出操作,才能查到客户端所需的数据,这会导致 复杂度的增加和性能的下降,从而影响查询的速度。 基于列数据库和稀疏数据本身的特点,为了提高数据库的查询效率,增加数 据的存储密度,其数据存储结构也有自己特有的特点。接下来,我们将结合列数 据库和稀疏数据的特点,介绍稀疏数据的数据存储结构。 在列存储数据库系统中,数据以列为基本单位进行存储,而每列数据可以采 取不同的数据压缩方式,即其数据存储结构可以不同,从某些方面看,列数据库 中的数据存储结构更加复杂、多样化。我们分别以采用列表形式、位串形式以及 段长表示三种形式,说明列存储数据库系统中数据结构的特点。 采用列表的形式。 天津师范大学碘士学位论文 团圃 罐盘存储格式 : 圈磁盘中以?结构存储数据 采用结构来存储数据,对于每个属性列,在文件头中包含三个信息,文 件的起始位置,记录总条数,以及含有的非零值的个数,如图中的第一行:然 后 按顺序存储非零值如图.中的第二行,接下来存储非零值的位置,如图中的第 三行。在含有大量空值,印稀疏数据袁中,这样存储数据大大的提高数据的存 储 密度,提高数据的压缩率。 此结构非常适合存储空值比较多的数据,数据含量比较少的情况下.其存储 结构表示如下: 帅哦 缸:?起始位置 砷:?记录总条数 妇?矾‖非零僮个数 : 卯哦 曲 ‖文件头 日舶蛳嘲瑚‖用于存储非零元素 对?‖用于存储非零元素位置 畴 挣天津师范太学硬士学位论文 采用此结构数据的压缩率为: 一型』型型塑咝粤婴驾冬型堑堂皇型幽。% ,?砌聊 其中,姗朋表示非零值的个数,表示记录总数,目衄表示敷 据类型。 采用位串的形式。 洱敷据 琏盘存储式 件? 革零值 非霉值 仃置 图 磁盘中以硫形式存储 采用位串结构来存储数据,对于每个属性刊,在文件头中包含三个信息,文 件的起始位置.记录总条数。以及含有的非零值的个数,与列表的存储头文件 结 构一样;然后按顺序存储非零值,接下来存储