（计算机软件与理论专业论文）基于元组聚类的关系数据库压缩.pdf

摘要 数据库的压缩技术是数据压缩领域的一个重要研究分支。传统的数据库压缩方 法基本都是按照流模式对数据库进行压缩处理，未考虑数据库数据的冗余分布，也 没有考虑压缩后数据的存储规律问题，针对这一状况本文在分析了传统数据库压缩 方法的基础上，并从元组角度出发，将聚类算法引入数据库压缩，提出了一种基于 元组聚类的数据库压缩方法，并对该方法进行了较为深入的研究，所做的主要工作 及取得的成果主要体现在以下几个方面： 首先，构建了基于元组聚类的数据库压缩机制，设计了基于元组聚类的数据库 压缩体系结构。将数据库的压缩过程分解为两个相对独立的阶段，先通过元组聚类 将数据元组按照冗余度高低进行分组，在分组的基础上再进行元组压缩。 其次，考虑到关系数据库的实际情况为了使k - m e a n s 聚类算法能够运用于数据 库元组的聚类，对k - m e a n s 算法的初始条件进行了优化改进，提出并设计了聚类代 价函数并给出了优化k 值的优化算法，改进了k - m e a n s 算法的初始中心元组的生成 算法，使得到的初始中心元组更适合于数据库的元组压缩。 再次，在元组聚类的基础上，提出了组中心的参照模式，依据参照关系将聚类 组中的元组联系起来，在此基础上设计了一种数据库元组级别的差分压缩算法，对 数据库中的元组数据进行压缩，并利用参照关系，对压缩后的数据采用参照树模式 进行存储，定义了参照树存储的相关操作。同时保留了参照关系及数据库的相关信 息以便于解压缩。 关键字：数据库压缩；元组聚类；差分压缩：参照树 a b s t r a c t d a t a b a s ec o m p r e s s i o ni s8 1 1 i m p o r t a n tb r a n c hi nd a t ac o m p r e s s i o nf i e l d c l a s s i c a l d a l a b a s ec o m p r e s s i o nm e t h o d sc o m p r e s sd a m b a s ei ns t r e a mm o d e ，t a k i n gn oa c c o u n to f t h ed i s t r i b u t i o no ft h er e d u n d a n c ya n dt h eo r d e r l ys t o r i n gp r o b l e mo fd a t u ma f t e r c o m p r e s s i n g i nt h i st h e s i s ，b a s e do nt h ea n a l y s i so fc l a s s i c a ld a t a b a s ec o m p r e s s i o n m e t h o d s ，ad a t a b a s ec o m p r e s s i o nm e t h o db a s e do nt u p l e s - e l u s t e r i n gi sp r e s e n t e da n d s t u d i e d t h em a i nw o r ka n dt h eo u t c o m ea r ea sf o l l o w s ： f i r s t l y , ad a t a b a s ec o m p r e s s i o nm e c h a n i s mb a s e d0 1 1t u p l e sc l u s t e r i n gi se s t a b l i s h e d , a n dad a t a b a s ec o m p r e s s i o ns y s t e mi sd e s i g n e d t h ed a t a b a s ec o m p r e s s i o np r o c e d u r ei s d i v i d e di n t ot w os e p a r a t ep h a s e si nt h ec o m p r e s s i o ns y s t e m , t h et u p l e si nd a t a b a s ea r e g r o u p e da c c o r d i n gt ot h er e d u n d a n c yf o r 触t h e nc o m p r e s s e d s e c o n d l y , c o n s i d e r i n gt h ea c t u a li n s t a n c eo f d a t ai nd a t a b a s e s ，f o rt h es a k eo f m a k i n g k - m e a n sa l g o r i t h ms u i tt od a t a b a s et u p l e sc l u s t e r i n g , w ei m p r o v ea n do p t i m i z et h ei n i t i a l p a r a m e t e r so f k - m e a n sa l g o r i t h m w ep r o p o s ea n dd e s i g nac l u s t e r i n gc o s tf u n c t i o n , a n d p r e s e n ta no p t i m i z a t i o na l g o r i t h mt oo p t i i i l i z et h ekv a l u e ，t h e ni m p r o v e dt h ei n i t i a l c e n t e rt u p l e sc r e a t i o na l g o r i t h m 鹪w e l l s oa st ok - m e a n sc l u s t e r i n gu s i n gt h ei n i t i a l c e n t e rt u p l e sc a nb es u i t a b l ef o rd a t a b a s et u p l e sc o m p r e s s i o n f i n a l l y , b a s e do nt h et u p l e sc l u s t e r i n g , g r o u p c e n t e rr e f e r e n c em o d ei sp r o p o s e d , a n d t h ec l u s t e r i n gr e s u l t sa r el i n k e db yr e f e r e n c er e l a t i o n t h e nw ed e s i g nad e f f e r e n c e c o m p r e s s i o na l g o r i t h mo n 呻l e sl e v e lt oc o m p r e s st h et u p l e si nd a t a b a s e w i t ht h e r e f e r e n c er e l a t i o n , t h ed a t u ma f t e rc o m p r e s s i n ga r es t o r e di nr e f e r e n c et r e em o d e , s o m e o p e r a t i o n so f r e f e r e n c et r e ea r ed e f i n e d , a n dt h er e f e r e n c er e l a t i o na n ds o m ei n f o r m a t i o n o f d a t a b a s e sa k e p td o w nt oh e l pd e c o m p r e s s i o n k e y w o r d s ：d a t a b a s ec o m p r e s s i o n ，t u p l e sc l u s t e r i n g , d i f f e r e n c ec o m p r e s s i o n ， r e f e r e n c et r e e i i 原创性声明 本人郑重声明：本人所呈交的学位论文，是在导师的指导下独立进 行研究所取得的成果。学位论文中凡引用他人已经发表或未发表的成 果、数据、观点等，均已明确注明出处。除文中已经注明引用的内容外， 不包含任何其它个人或集体已经发表或撰写过的科研成果。对本文的研 究成果做出重要贡献的个人和集体，均己在文中以明确方式标明。 本声明的法律责任由本人承担。 论文作者签名：i 趋，i l 直j 日期：业2 竺j 二 关于学位论文使用授权的声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归属 兰州大学。本人完全了解兰州大学有关保存、使用学位论文的规定，同 意学校保存或向国家有关部门或机构送交论文的纸质版和电子版，允许 论文被查阅和借阅；本人授权兰州大学可以将本学位论文的全部或部分 内容编入有关数据库迸行检索，可以采用任何复制手段保存和汇编本学 位论文。本人离校后发表、使用学位论文或与该论文直接相关的学术论 文或成果时，第一署名单位仍然为兰州大学。 保密论文在解密后应遵守此规定。 论文作者签名：速杰兰6 导师签名：篮垒叁日期：率可 兰州大学硕士学位论文 基于元组聚类的关系数据库压缩 1 1 研究背景 第一章绪论 多年来数据压缩一直是学术界和工业界研究的热点，从本质上讲，数据压缩的目的就是要消除 信息中的冗余l “。目前大多数数据压缩方法是按照流模式工作，即编码器读入一个或多个字节进行 处理，直到检测到一个e n d - o f - f i l e 字符还有一些方法如b u r r o w s - w h e e l e r 4 i 作在块模式下，逐块 读入数据，每块单独编码，此时块长极大地影响着压缩性能此外，大部分的压缩方法都是物理 ( p h y s i c a l ) 上的：只关注输入流中的位而忽略输入流中数据项的含义。这种方法把一个位流转换成另 一个更短的位流。而逻辑( 1 0 9 i c a l ) 上的压缩方法则观察源流中的各个数据项，将经常出现者用短码代 瞢。这种方法通常是专用的，只对某些特定的数据类型有好的效果。 s h a n n o n 的信息论! i 】告诉我们，对信息的先验知识知道得越多，就可以把信息压缩得越小换 句话说，如果压缩算法的设计目标不是任意的数据源，丽是基本属性已知的特种数据，压缩的效果 就会进一步提高。这提醒我们，在发展通用压缩算法之余，还必须认真研究针对各种特殊数据的专 用压缩算法。本文研究关系数据库的压缩方法 为了有效地管理数据库，人们提出了压缩数据库技术1 5 - 2 6 。压缩数据库技术可以提高数据的存 储效率，也是提高数据库性能的重要途径。目前对数据库压缩方法的研究包括各种经典压缩算法在 数据库压缩中的应用以及数据库专用压缩方法的研究等。文献【1 3 】提出了用二进制位流压缩数据库 成对属性字段的方法，文献【1 2 】和文献f 3 9 】分别研究了l z w 算法和算术编码( a r i t h m e t i ce n c o d i n g ) 韬e 数据库属性列级上的应用，这些都是对经典压缩算法在数据库压缩中应用的研究，其压缩方法简单， 但压缩效率低在数据库专用压缩方法的研究方面，b e r c h t o l d 提出了一种基于索日l o n d e x ) 和独立量 化树( i q t r 嘲的数据库压缩方法f ，b a b u 提出了用衰退树( r e g r e s s i o n 灯e 嘲来压缩数值型数据库的 方法刚，这两种方法在压缩过程中利用了新的专有结构来帮助压缩。文【1 4 】提出了在元组级别上采 用矢量量化压缩数据库的无损压缩方法，文0 9 对数据库中的属性字段进行分类压缩，对数值型属 性和字符串型属性分别采用不同的压缩算法，同时对字符串型属性进行细粒度压缩，文【3 0 】提出了 海量关系的拆分压缩技术，将小值域属性分离进行二次压缩，c h a k r a b a r t i 提出了用小波( w 机l e t ) 技 术压缩数据库的方法【柏l ，此类方法没有采用新的结构，而是利用了其他的成熟技术或方法，压缩效 率高。 兰州大学硕士学位论文 基于元组聚类的关系数据库压缩 从上述数据库压缩方法的研究现状可以看出，目前已有的数据库压缩方法仍存在一些缺点和不 足，主要有：第一，采用经典压缩算法的数据库压缩方法忽视了数据库元组数据的结构化特性，将 数据库按流模式进行压缩，压缩后仍然按流模式输出，对压缩后的数据只是简单地按位流存放，使 压缩后的数据不具有结构化特性。第二，采用专有结构的数据库压缩方法比较复杂，不对数据库做 预处理，不考虑冗余情况直接进行压缩，可能导致压缩效率低。第三，综合采用多种技术方法的数 据库压缩方法计算量大，压缩代价过高，同时解压缩过程复杂且开销大。 1 2 本文主要工作及取得成果 元组是数据库数据的结构化特性的体现，本文研究元组级别上数据库的压缩。压缩依靠消除冗 余来实现，一般数据库中的元组没有规律，元组问的相邻关系组织并没有按照数据冗余程度进行编 捧。因此在压缩之前，若能先将元组按照相互闻的冗余程度进行分类，使冗余程度高的元组在同一 类别中，那么就会提高数据的压缩率由于聚类技术可以较好地根据数据对象间的相似性将数据对 象进行分类，使得处于同一聚类簇中的对象达到某种程度的相似。因此我们将聚类方法引入数据库 元组压缩过程，按照元组的冗余程度对数据库元组进行聚类，在此基础上压缩时通过消除同一聚类 簇中元组间的冗余的达到压缩元组数据的目的 根据以上分析。本文在以前工作刚并借鉴文献【1 4 1 压缩算法的基础上，将聚类方法引入数据库 压缩。构造了一种基于元组聚类的数据库压缩机制，并设计了其压缩模型，所做的主要工作和取得 的成果如下： 深入分析了已有的数据库压缩方法，提出并构建了一种基于元组聚类的数据库压缩体系， 将数据库压缩分为两个步骤：元组聚类和压缩存储，并分别分析了各自的功能和设计目标 为了便于压缩，将聚类引入到数据库压缩中，采用的聚类算法是k - n u x m s 算法由于 k - m m s 算法应用于数据库压缩的局限性，对k - m e a n s 算法的初始k 值问题进行了较为深入的研究， 定义了k 值代价函数，并提出了基于代价函数的k 值优化算法；同时就k - m e a n s 算法中心元组初始 化方法的不确定性，提出了基于捧序的k - m e , a n s 中心元组初始化算法，克服了k - m e a n s 算法的应用 局限性，使k - m e a n s 算法能够适合于数据库压缩。 为了在元组级别上进行压缩，本文借助参照关系来帮助压缩。在分析了传统参照方法的优 缺点的基础上，提出了组中心参照关系，并将该参照关系作为数据库元组压缩的依据，继而提出了 以元组为压缩粒度的基于元组聚类和参照关系的数据库差分压缩算法，利用该算法对数据库元组进 行压缩。 2 兰州大学硕士学位论文基于元组聚类的关系数据库压缩 最后，研究了压缩后的数据存放规律问题，提出了参照树的存储模式，充分利用参照关系， 将压缩后的数据采用参照树模式存储，并讨论了参照树的不同节点结构的设计，优化压缩后的数据 存储结构。 1 3 本文组织结构 除本章外，本文其它内容按照以下顺序组织： 第二章相关理论和技术。介绍了数据库数据组织及访问方式、常规数据库压缩方法及其缺点、 聚类基本理论和k - m e a n s 算法及其应用于数据库元组聚类的局限。 第三章基于元组聚类的数据库压缩存储体系的构建。提出了基于k - m e a n s 元组聚类的数据库 压缩存储体系，并对其中的各个部分进行了简要论述 第四章数据库元组聚类的研究。讨论了k - m e a n s 算法在数据库元组聚类中的应用，包括对 k - m e a n s 算法的初始中心元组的创建及分组数目k 值的生成方法的优化，k - m e a n s 算法的聚类过程 等。 第五章元组粒度的数据库压缩存储方法研究提出了改进的参照关系，并在此基础上提出适用 于数据库元组的差分压缩方法及相应的参照树存储模式。 第六章总结与展望。对全文进行了总结，讨论并给出了下一步的工作目标 兰州大学硕士学位论文基于元组聚类的关系数据库压缩 第二章相关理论与技术 本文研究数据库压缩方法，本章介绍与本文数据库压缩相关的理论与技术，包括关系数据库的 数据组织及访问方式、关系数据库中的数据冗余、常见冗余的度量、数据库压缩的般方法以及聚 类理论和k - m o a n s 算法等。 2 1 数据库的数据组织及访问方式 2 1 1 关系数据库的数据组织 关系数据库的主要特点之就是用二维表的方式组织数据，无论是实体还是实体问的联系都采 用二维表二维表也是s q l 语言存放数据、查找数据以及更新数据的基本数据结构。数据是二维表 中的元素，而该二维表就是其关系。二维表的每一行称为关系的一个元组。每一列称为关系的一个 属性二维表中的记录数随实体的增减而变化，但字段个数却是相对固定的。因此所有记录的长度都 是相同的。二维表之间的数据联系通过一个表的码与另一个表的外码的连接来体现脚l 。 2 1 2 关系数据库的一般访闯方式 关系数据库最经常的访问是s q l 语句的访问【3 3 】。s q l 语句对数据库的访问是以元组行的方式 访问，这种方式被称为s q l 硬编码式，将数据访问脚本直接嵌入到数据库中。另一种数据库访问方 式称为代理式州”，在业务对象和关系数据库之问增加一些成为代理的对象每个业务对象对应一 个代理，每当业务对象需要访闯数据库对，就恕代理对象发出请求，然后由代理对象去访问数据库。 图2 - i 表示的是代理式访问方式的流程。 图2 - 1 中数据库访坶代理层对上层的业务逻辑层的访问请求进行分析，将需要的数据库信息传 递给访问接口层。访问接口层通常配有各种数据库的驱动程穿，当接到访坷代理层传递盼要访问的 数据库信息时，访问接口层调用相应数据库的驱动程序，将待访问数据库打开，建立底层数据库与 访问代理的连接。数据库代理式访问方式增强了业务逻辑层代码的可重用性，因此代理式数据库访 问方式在目前的各种数据库应用领域都有广泛的应用，常见的o d b c 数据源、j d b c 数据源、a d o 技术都是采用代理式访问数据库。 4 兰州大学硕士学位论文基于元组聚类的关系数据库压缩 图2 - 1 数据库代理式访问方式的流程嗍 2 2 关系数据库的数据冗余与冗余的度量 2 2 1 关系数据库中的数据冗余类型 冗余的存在是运行压缩的条件之一。通常情况下，冗余主要是指数据的重复。关系数据库的数 据重复主要有表的重复、属性的重复，元组的重复、属性值的重复4 类： ( 1 ) 表的重复：为了数据安全的需要制作备份表，当主表被破坏时可用此恢复数据。分布式数 据库为减少数据通讯开销也常重复放表，这种数据冗余在这里是必需数据冗余，不能删除。若是因 其他原因产生的非必要的重复表则应予以删除。消除表的重复所引起的数据冗余为磁盘文件级的操 作。 ( 2 ) 属性重复：有不同表的属性重复和同一表内属性重复2 种情况不同表中属性重复常用来 建立表之间联系。这只需要一个公共属性，这是必器数据冗余，不能删除；各表间的多于一个的属 性应当删除。同一表内有相同属性内容的多个属性，若非数据安全检查的需要，应删除之。属性的 重复所引起的数据冗余的消除为对数据库结构修改的操作 ( 3 ) 元组的重复：表内不同记录内容有时会完全相同，若非必要，应予以删除。元组的重复所 引起的数据冗余的消除由记录级的操作完成 ( 4 ) 属性值的重复：按属性值域集合基的特点可以将其分为有限类和无限类。无限类属性值是 指其属性值域集合的基为无限大或者与数据库记录数为同一致量级的属性值，如实数、整数、日期、 各种编号。有限类属性值的重复。有限类属性值是指其属性值域集合的基小于数据库记录数至少一 5 兰州大学硕士学位论文基于元组聚类的关系数据库压缩 个数量级的属性值，有限类属性值的重复实际上是由一对多或多对多的关系引起的，有时可作为必 需冗余不作处理。但当重复量很大时，应当对所引起的数据冗余进行压缩 以上数据库的各种重复的值是完全相同的然而在实际的数据库表中，还存在着另一种数据部 分数据的重复，例如，一张数据库表中的属性字段“学号”的两个值 0 4 2 0 1 6 0 8 8 ”和 0 4 2 0 1 6 0 8 9 ”，这 两个属性值不同但是值的前8 位却是相同的。这种数据冗余在数据库中普遍存在。因此针对这种 类型的数据冗余，需要有专门的度量方法来描述冗余情况。 2 2 2 冗余的度量 常见的冗余度量p 1 概括起来有以下几种： ( 1 ) 冗余度：冗余度是指两个数据对象之间数据相同的程度。两个数据对象a 和b 之间的冗余 度r 定义为a 与b 中相同数据的长度比长度较长的a 或b 的长度，设h 表示a 与b 相同数据的 长度，j a j 和蚓分别表示a 与b 的长度，则a 与b 问的冗余度r ( a ，b ) 可用下式2 - 1 计算： 触驴翻 倍1 ) 通常冗余度的值不大于1 冗余度越高，表明两个数据对象的重复越多，可压缩的数据越多， 压缩后的压缩比越大。当冗余度等于1 时，表明两个数据对象完全相同。 需要说明的是，冗余度是人们根据日常生活的经验总结的度量方法，能直观表示冗余存在的程 度，但是在计算机中，冗余度的计算却不容易实现。因为计算机中数据的长度与人们e t 常生活中的 长度存在很大差异，往往计算机得到的冗余度与人们根据经验得到的冗余度不相同。例如：两个人 的名字“薛磊”与“薛永磊”，按照人们的日常习惯，这两个名字有两个字是相同的，其冗余度为0 6 6 7 ， 而在计算机中，这两个名字只有第一个字是相同的，所以这两个字符串的冗余度则为0 3 3 3 可见冗 余度的度量方法不具有权威性，一般不用冗余度来表示信息的冗余。 c 2 ) 距离度量：在实际应用中，常见的方法是利用距离对两个数据对象之间的冗余进行度量， 即距离度量距离度量法通常采用各种空问距离进行度量，用于进行冗余度量的距离有： 明考斯基距离( m i n & j w a k id i s t a n c e ) ：两个n 维数据对象i = ( x i l ，x i 2 , ，) 和j 气x j l ，x 皿，列间的 明考斯基距离d 0 , j ) 可按下式2 - 2 得到： d ( i ，歹) = l 置，一z ，1 9 + l x 。：一z ，：1 9 + + i z 。一x 如l 叮岱2 ) 其中q 是一个正整数： 当q = l 时，明考斯基距离就是曼哈顿距离( m a n h a t t a nd i s t a n c e ) 6 兰州丈学项士学位论文基于元组聚类的关系数据库压缩 d o , j ) = l x , ，一置肛陬- 彤| + + 陬一以i ( 2 - 3 ) 当q = 2 时，明考斯基距离称为欧几里德距离( e u c l i d d i s t a n c e ) d ( i ，力= ( 置。一i ) 2 + ( 五2 一2 ) 2 + + ( 瓦一矗) 2 ( 2 - 4 ) 无论是明考斯基距离、曼哈顿距离还是欧几里德距离，距离越短，表示两个空间对象的冗余越 多，可压缩的数据越多。若距离的值为0 ，则说明两个空间对象完全相同。距离度量在空间数据对 象的度量方面有广泛的应用 ( 3 ) 相似度度量：相似度度量主要是在向量空间对特征向量进行度量。相似度是表征两个向量 相似程度的量，对于向量空间中的两个n 维向量i = ( x i l ，x 矗， ) ( 0 和j 气x j l 尥，) ，它们之间的相 似度s i m ( i j ) 可按下式2 - 5 求得： $ i m 【t j ) = ( 2 - s ) 其中，w t 和w 孟分别是向量i 和向量j 的第k 维。一般情况下，两个向量的相似度越高，存在 的冗余越多。若两个向量间的相似度为0 ，则表示两个向量完全不同，不存在冗余；若相似度等于1 ， 则表示两个向量完全相同。 上述的三种方法中，冗余度会产生不一致，不能采用，而距离度量和相似度度量都是适合于向 量空问，由于数据库数据的非空间性，上述度量不适合于数据库数据冗余的度量 2 3 数据库压缩的一般方法 早期的数据库压缩大多数是以属性列为压缩粒度，采用一些经典的无损压缩算法如字典压缩、 h u f f n m a 编码【，珂等通用算法进行压缩。这种压缩方法的缺点是不考虑数据库中数据的结构性，将数 据库以数据流的形式进行压缩，压缩率不高。直到近几年，对数据库压缩方法的研究才转向数据库 专用压缩方法的研究，目前已出现的成果有： ( 1 ) 面向块的增量( a u g m e n t 憎t o r ) 压缩方法【1 趣：该方法将数据库数据分块。每个块中序号居中的 元组为代表元组，块内其他元组可以用代表元组加增量的方式表示其压缩方法是对块内的元组用 矢量量化( v e c t o rq u a n t i z a t i o n ) 的方法进行量化，压缩时用由矢量量化产生的码书和每个元组与其代表 元组的增量共同组成的有序对来压缩元组，进而实现数据库的压缩。其中采用的矢量量化方法在语 音和图像压缩领域有着广泛的应用，但不能直接应用于数据库压缩，因为矢量量化的方法是一种有 7 兰州大学硕士学位论文基于元组聚类的关系数据库压缩 损压缩方法，而数据库的压缩要求无损压缩。面向块的数据库增量压缩方法则打破了矢量量化方法 的应用局限，实现了采用矢量量化的无损压缩。面向块的增量压缩方法的优点是能够有效压缩数据 库并能够执行压缩数据库的查询操作，缺点是采用了矢量量化的有损压缩过程计算量大，压缩速 度缓慢。此外分块方法简单，块内元组问的数据冗余可能不高，影响了压缩效率。面向块的增量压 缩方法可归纳为图2 - 2 所示的过程。 图2 - 2 面向块的增量压缩方法的压缩流程i 川 ( 2 ) 保序( o r d e rp 托鲫啊l 囝压缩技术l l ，l ：该方法最初是采用压缩字典编码对数据库的多个字符串 属性值进行压缩。它将字符串拆分为多个小字符串，利用变长的字典编码法对这些小字符串压缩， 其拆分的方法依赖于编码字典的编码顺序，而与编码字典具有相同顺序的序号编码表则保证了保序 的实现。由于保序压缩简单易于实现，随后许多通用编码方式如h u t j b n a n 编码、算术编码( a r i t h m e t i c e n c o d i n g ) 都被应用到保序压缩技术中。保序压缩技术的优点在于易于实现，缺点是压缩率不高。图 2 - 3 描述了采用字典编码的保序压缩技术的压缩过程。 图2 - 3 采用字典编码的保序压缩技术的压缩过程 ( 3 ) 基于语义的压缩技术【2 0 】：这是一种利用属性的语义和数据挖掘模型来实现压缩的方法。该方 法利用可预见的数据关系和为个别属性指定的容错方式来为整个数据表的所有行构建分类衰退树模 s 兰州大学硕士学位论文基于元组聚类的关系数据库压缩 型，压缩时选择属性集的一个特定子集，该子集中没有已经压缩过的值，而衰退树则采用一定的学 习方法和组合优化算法来对这些值进行预计，并产生预计结果，即压缩值。通过不断更新衰退树的 属性集子集来实现整个数据库的压缩。其可预见的数据关系是基于属性语义的关系，而数据挖掘则 应用在衰退树的预见运算中基于语义的压缩技术是有损的数据库压缩方法。由于利用了属性的语 义，在衰退树进行压缩前需要首先分析属性字段的语义信息，因而该压缩方法复杂而不易实现，且 压缩率也不高图2 - 4 表示了包含x i 、x 2 、x 3 、x 4 、x 5 、x 6 、x 7 的数据库表t 的衰退树的构建 及压缩过程。 1 曲l e 图2 - 4 基于语义的数据库压缩方法的处理过程例 ( 4 ) 海量关系拆分压缩技术删：这种方法是针对目前不断出现的海量关系数据库提出的一种专 用压缩方法该方法从海量关系数据库中分离出小值域属性组，将海量关系拆分，然后对小值域属 性组所在的新关系进行压缩。压缩时需要先估计拆分压缩的压缩比，如果压缩比合理则进行拆分压 缩，否则放弃拆分压缩。海量关系拆分压缩技术对海量数据库的压缩及二次压缩有较好的效果，但 是由于小值域属性组的识别问题的n p - 完全性，使得拆分压缩复杂，代价过大 以上几种方法在数据库专用压缩领域具有一定的代表性。也各有优缺点当然，数据库压缩方 法还有其它一些方法，但都不具有代表性，这里不再描述。 2 4 聚类理论简介 聚类是将一个对象的集合分割成几个簇，每个簇内的对象之间是相似的。但与其它簇的对象是 不相似的。由于聚类方法具有高效性和高可靠性的优点，目前已被应用于许多学科领域，如数据挖 9 兰州大学硕士学位论文基于元组聚类的关系数据库压缩 掘、模式识别、图像处理、医疗科学和情报学等。 在计算机领域，聚类方法主要应用在数据挖掘领域，作为其它数据算法的预处理步骤，由聚类 算法获得数据分布状况，其它数据算法则集中对特定的类做进一步的研究刚。数据库元组压缩也是 一种数据算法，可以在聚类方法之后使用。另一方面，数据库之所以能够被压缩，是因为数据库中 存在冗余。由于数据库元组的分布一般没有规律可循，若直接对无规律的元组进行压缩一般不能最 大限度地消除元组间的数据冗余，也无法获得高效的压缩。因此在压缩前需要对数据库元组进行某 种分类，使冗余程度高的元组在同一个类中而聚类正好可以帮助解决元组的分类问题。由此为了 方便压缩，我们在压缩前按照冗余程度对元维进行聚类处理，以帮助压缩的实现。 2 4 1 聚类基本算法 聚类算法主要包括分割聚类方法、层次聚类方法、基于密度的聚类方法和基于网格的聚类方法， 以下分别描述各种聚类算法的主要思想。 ( 1 ) 分割聚类方法o 懒i i f l ga l g o r i t h m s ) f 1 2 l ：分割聚类方法主要思想是选择初始区域，反复在 类之间移动数据点，使得目标函数最优。通常会采用一个划分准则( 通常称为相似度函数) 例如距 离，以便在同一个簇中的对象是相似的，在不同簇中的对象是相异的。分割聚类方法代表性的算法 有k - m e a n s 、k = m e d o i d 、c l a r a n $ 等。k - m e a n s 方法把类的中心作为类的代表，k - m e d o i d 则把类 的某一中心位置上的点作为代表点分割聚类方法的聚类结果是局部最优。分割聚类方法的聚类过 程如图2 - 5 所示。 图2 - 5 分割聚类方法的- 缎聚类过程 分割聚类方法具有收敛速度快、能对给定参数找到局部最优解、容易实现的优点，缺点是对孤 立点敏感。 c 2 ) 层次聚类方法l ：层次聚类方法的基本思路是合并最相似的部分，或者分割最不相似的部 分。如果合并最相似的部分，那么从每一个对象作为一个类开始，逐层向上进行聚结；如果分割最 1 0 兰州大学硕士学位论文基于元组聚类的关系数据库压缩 不相似的两个部分，那么从所有的对象归属在唯一的一个类中开始，逐层向下分解。比较传统的层 次聚类基本算法有a g n e s ( a g g l o m e r a t i v en e s t i n g ) 算法和d i a n a ( d i v i s i v ea n a l y s i s ) - 算法，分别为 聚结型层次聚类算法和分解型层次聚类算法 ( 3 ) 基于密度的聚类方法 t s l ：基于密度的聚类方法的基本思路是对于给定类中的每个数据点， 在一个给定范围的区域中必须包含至少某个数目的点，因此可以过滤孤立点和噪音基于密度的聚 类算法有：d b s c a n 算法及其改进算法、w a v e c l u s t e r 算法、d e n c l u e 算法、c l i q u e 算法和o p t i c s 算法等 ( 4 ) 基于网格的聚类方法1 4 d ：基于网格的方法把对象空问量化为有限数目的单元，形成了一个 网格结构，所有的操作在网格结构上进行由于基于网格的聚类方法与网格数目有关，而不依赖于 对象的数目，因此处理速度一般比较快。比较典型的基于网格的聚类方法有：s t r n g ，b a n g ，s t i n g + 等。另外，还可以将数学模型用于聚类，例如采用神经网络模型进行聚类处理。 2 4 2k - m e a n s 算法 k m e s 算法是一种分割聚类方法，由j b m q u 。于1 9 6 7 年提出f 2 】。k - m e a n s 算法的主要 目标是在大量同型对象中找出具有代表性的对象，这些代表性对象称为聚类中心点，然后再根据这 些聚类中心点，进行后续的处理。 在本文中，我们用k - m e a n s 算法来对数据库元组进行聚类，使相互同冗余程度高的元组在同一 个聚类簇中，目的在于利用k n l e 柚s 算法聚类的结果来帮助压缩。下面简单介绍k - m e a n s 算法。 2 4 2 1k - m e a n s 算法流程 k - m e a n s 算法接受输入量k ，然后将n 个数据对象划分为k 个聚类，使得所获得的聚类簇满足： 同一聚类簇中的对象相似程度较高，而不同聚类中的对象相似程度较低。k - m e a n s 算法包括以下三 个步骤： ( 1 ) 初始化：选择i 个划分的初始中心； ( 2 ) 分配：将满足给定准则的数据点放入相应中心所在的划分，通常给定的准则是一个数据点与 中心的关系； ( 3 ) 中心优化：对每一个划分，聚簇中心被重新赋值以优化准则； 重复步骤2 和步骤3 ，直到聚簇中心不再变化或达到错误阈值。 兰州大学硕士学位论文基于元组聚类的关系数据库压缩 2 4 2 2k - m e a n s 直接用于数据库压缩的局限性 目前在数据库领域k - m e a n s 算法主要被应用于数据挖掘，在数据库元组聚类方面的应用则是 k - m e a n s 应用研究和数据库研究的新方向。理论上k - m e a n s 算法能对给定准则找到局部最优解，但 是由于存在着一定的局限性“圳，还不能将k - m e a n s 算法直接应用到数据库元组聚类中，这些局限 性主要表现在： ( 1 ) 初始化中心点的方法不明确，常用的方法是随机选取。初始中心点的选择在k - r a e a a s 算法 中非常重要，通常希望找到散布较大的点作为初始中心点。但是在一般的基予贪心算法的初始中心 点搜索过程中，由于仅仅基于距离因素，往往找到许多孤立点作为中心点，且初始中心点选择的随 机性较强，导致聚类结果的随机性 ( 2 ) 不同的初始中心点可能得到不同的结果，导致得到的最终结果可能并不是最佳结果。且初始 中心点的输入顺序也影响聚类的效果。 ( 3 ) k - m e a n s 算法的聚类结果严重依赖于k 值的选择。k - m e a n s 算法一般需要事先给定聚类数k ， 但多数情况下，聚类数k 事先无法确定，因此需要对最佳聚类数k 进行优化处理目前已提出了一 些检验聚类有效性的函数，使用聚类有效性函数计算合适的聚类数k ，即最佳聚类数l ( o 。但是，由 于这些构造函数自身的缺陷，一般难以直接找到最佳聚类数l o 。，因此需要先确定一个搜索范围， 就是要设定一个k 。，使得k 。鲰。对于如何确定k 。，目前尚无明确的理论指导，多数学者使 用的经验规则为：k m n 。这限制了k - m e a n s 算法的应用合理性。由于无法用理论获得k “而使 l c 目的选择成为了k o m o a n s 算法的最大问题所在 由于这些局限性的存在，k - m e a n s 算法还不能直接用于数据库元组的聚类，必须先消除这些局 限性。本文第四章将如何消除这些局限及k - m e a n s 算法的应用进行详细讨论 1 2 兰州大学硕士学位论文 善于元组聚类的关系数据库压缩 第三章基于元组聚类的数据库压缩存储体系的构建 3 1 基于元组聚类的数据库压缩存储体系的构建 为了有效压缩数据库元组，我们将k - m e a n s 聚类引入数据库压缩，先利用聚类产生压缩需要的有 用元组聚簇组，再在聚类的基础上进行压缩。由此本文基于k - m e a n s 元组聚类的数据库压缩包括两个 步骤：第一步利用k - m e a n s 算法对元组进聚类分组，第二步对聚类后的元组进行差分压缩。考虑到数 据库元组的特殊性，我们对k - m e a n s 算法的初始条件进行了相应的优化和改进，以期聚类结果更为准 确可靠并有利于第二步压缩。基于以上的分析本文基于k - m e a n s 元组聚类的数据库压缩的体系结构 设计如下图3 1 所示。 图3 - i 基于元组聚类的数据库压缩体系 从图3 1 中也可以看出，该体系主要包括两个核心组成部分：元组聚类和元组压缩及存储，在元 1 3 兰州大学硕士学位论文 基于元组聚类的关系数据库压缩 组聚类部分采用的聚类算法是k m e a n s 算法。以下我们对这两个部分进行进一步的讨论。 3 2 元组聚类 经典k - m e a n s 算法有两个初始输入参数：初始聚类中心和聚类数目k ，这两个初始参数是k _ 俩e a 璐 算法性能的主要影响因素为 j - 使k - i n e a n s 算法能够有效地对数据库元组进行聚类，k - m e a n s 算法的 初始条件必须要加以优化，以适于数据库元组的聚类。因此我们在k - m e a n s 算法进行聚类之前，先对 它的两个初始条件分别进行优化处理，再进行元组聚类。在整个体系的第一步k - m e a n s 元组聚类中包 括四个处理：表元组识别统计、初始聚类中心获取、k 值优化和k m 锄s 聚类。下面分别对这四个部 分进行详细设计 ( 1 ) 表元组识别是将处理对象由数据库细化到表元组，将数据库中的多个表分别识别。并统计每 个表中的元组数目，为初始聚类中心的获取和k 值的优化提供所需的元组数据及表元组数目 我们将聚类引入数据库压缩中，目的是要利用聚类将元组按照冗余程度分类，便于压缩时去除 冗余。可见聚类对象是数据库中的元组，因此在将数据库输入后需要对数据库进行元组级别的访问 代理式数据库访问方式可以避免对数据库的直接修改，提高代码的可重用性，因此本文压缩方法对 数据库的访问也采用代理式访闯。代理式数据库访问方式参见2 1 2 ，本文将不再讨论。表元组识别 统计的详细结构如下图3 - 2 所示 统计及表信息缓冲区 元组数据缓冲区 图3 - 2 表元识别统计的详细结构 ( 2 ) 初始聚类中心获取是通过执行一定的算法生成k - m e a n s 聚类时需要的初始中心元组，由于初 始聚类中心的选择霸j k - m e a n s 算法的性能有很大影响，因此初始聚类中心获取也具有很重要的作用 下圈3 - 3 表示的是初始聚类中心获取的内部流程。其中的元组数据缓冲区是图3 - 2 中的元组数据缓冲 区，而数字1 6 表示各个模块对公用缓冲区的访问顺序。 兰州大学硕士学位论文 基于元组聚类的关系数据库压缩 1 元组排序 i 元组分组 r | l 排序规则i h 1 分组规则j l 2 i 3 5 1， l + 生成候选中心元组 l 候选生成规则l 元组数据缓冲区” i k - m 锄s 聚类k 个初始 筛选初始中心元组 i处理中心元组 i筛选规则l 图3 - 3 初始聚类中心获取的内部流程 ( 3 ) k 值是k - m e m s 聚类的另一个初始条件，k 值优化中配备k 值优化算法，完成k 值的精确选择， 在k - n m u s 聚类时无需进行多个可能k 值的不断测试。图3 - 4 是k 值优化的处理流程。 代价函数值数组 图3 4 k 值优化的内部流程 “) k - m e 孤s 聚类用来实现元组聚类，由初始聚类中心获取和l ，值优化为其提供初始输入条件其 算法的流程同经典k - m e a n s 算法的流程相同，参见图2 - 5 聚类的应用主要是为了服务压缩，通过以上各部分的协同处理工作，利用聚类将元组按照冗余 程度分类，以实现高效的压缩。 本文将在第四章对上述的元组聚类进行详细的研究，包括初始聚类中心的获取算法、k 值优化算 法以及k - m e a n s 算法的实现等，在此就不再详述。 3 3 元组压缩及存储 压缩是本文基于k m 硼元组聚类的数据库压缩体系的另一个核心内容，而元组聚类和压缩存储 兰州大学硕士学位论文基于元组聚类的关系数据库压缩 具有明显的先后顺序，压缩依赖于第一部分元组聚类的结果。在压缩存储部分要解决数据库的压缩 以及压缩后的存储问题，主要内容包括以下的三个方面： ( 1 ) 参照生成是按照一定的参照关系原则，根据聚类结果为元组找到一个参照元组，以备在压缩 和存储的过程中使用。参照生成的结果是参照关系表，数据库中每一张二维表都有一个参照关系表 与之对应。下图3 - 5 表示了参照生成的过程 墨耋堡銎 的k 个组 参照关系表 图3 - 5 参照生成的内部流程 ( 2 ) 差分压缩处理借助参照关系，运用一定的差分压缩算法对聚类得到的元组进行压缩。下图3 - 6 为差分压缩的处理流程。 聚类得到的k 个组 元组差分压缩l l 压缩算法ii 。l 参照：接系表 f 表信息数据 图3 - 6 差分压缩处理的流程 ( 3 ) 参照树存储处理的主要任务是把差分压缩处理的压缩结果以参照树的模式进行存储，存储时 保留参照关系以便于解压缩。下图3 7 表示了参照树存储处理的流程 兰州大学硕士学位论文基于元组聚类的关系数据库压缩 监瑁下点 0 ， 参照树初始化 非 首要元组 首 罂 7 1 3 组 。 非根节点插入 7 参照树 参照关系表 图3 - 7 参照树存储的处理流程 本文第五章将对本节基于聚类的数据库压缩存储进行详细的论述 1 7 兰州大学硕士学位论文基于元组聚类的关系数据库压缩 第四章初始优化的k