`
sogotobj
  • 浏览: 617544 次
  • 性别: Icon_minigender_2
  • 来自: 北京
文章分类
社区版块
存档分类
最新评论

一种有效的关系数据库压缩方法 选择自 l1t 的 Blog

Blog数据挖掘算法F#设计模式 
阅读更多
Vol.16, No.2 ©2005 Journal of Software 软 件 学 报 1 000-9825/2005/16(02)0205
一种有效的关系数据库压缩方法∗
骆吉洲1+, 李建中1,2
1(哈尔滨工业大学 计算机科学与技术学院,黑龙江 哈尔滨 150001)
2(黑龙江大学 计算机科学与技术学院,黑龙江 哈尔滨 150080)
An Efficient Compression Method of Relational Database
LUO Ji-Zhou1+, LI Jian-Zhong1,2
1(School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China)
2(School of Computer Science and Technology, Heilongjiang University, Harbin 150080, China)
+ Corresponding author: Phn: +86-451-86415872, Fax: +86-451-86415827, E-mail: luojizhou@hit.edu.cn
Received 2003-11-14; Accepted 2004-06-10
Luo JZ, Li JZ. An efficient compression method of relational database. Journal of Software, 2005,16(2): 205−214. http://www.jos.org.cn/1000-9825/16/205.htm
Abstract: There usually are many attributes, called small-range attributes, with small number of different values in massive relations. The number of combination values of these attributes is also very few in massive relations so that there are a lot of repeated combination values of these attributes in massive relations. It is important to remove the repeated combination values to improve the efficiency of storing and querying massive relations. A compression method for removing the repeated combination values is proposed in this paper. To compress a massive relation, the method partitions the relation into two small relations: one consists of the small-range attributes and the other consists of the rest attributes. The key problem is to identify the small-range attributes. The NP-hardness of this problem is proved, and two approximate algorithms are proposed to solve this problem. The compression algorithms and the query processing based on the compressed method are also discussed. Experimental results show that the compression method has high compression ratio and enhances the query processing performance.
Key words: massive relation; compressed database; small-range attributes’ combination; NP-complete problem
摘 要: 海量关系中经常存在小值域属性,关系不仅在这些属性上的互不相同的值的数量很小,而且在这些属性的组合上的值域也很小.因此,海量关系在这些属性上有很多重复的组合值.一种提高数据库的存储和查询效率的重要方法就是消除这些重复取值.为此,提出了拆分压缩技术,它将海量关系拆分成两种较小的关系,其中一种关系的属性由小值域属性组组成,而另一种关系的属性是海量关系的其他属性.该方法的关键是小值域属性
∗ Supported by the National Natural Science Foundation of China under Grant No.69873014 (国家自然科学基金); the National High-Tech Research and Development Plan of China under Grant No.2001AA444110 (国家高技术研究发展计划(863)); the National Grand Fundamental Research 973 Program of China under Grant No.G1999032704 (国家重点基础研究发展规划(973)); the Natural Science Foundation of Heilongjiang Province of China under Grant Nos.F0208, zjg03-05 (黑龙江省自然科学基金)
作者简介: 骆吉洲(1975－),男,重庆人,博士生,主要研究领域为压缩数据库技术;李建中(1951－),男,博士,教授,博士生导师,主要研究领域为数据库技术,数据仓库,半结构化数据,Web信息集成,数据流,传感器网络,数据挖掘,压缩数据库技术.

206 Journal of Software 软件学报 2005,16(2)
组的识别问题.在证明了这个问题的NP-完全性后,给出了两种在海量关系中识别小值域属性组合的算法,并在此基础上提出了海量关系拆分压缩技术,讨论了压缩关系的查询处理方法.实验结果表明,拆分压缩技术可以取得较好的压缩效果,并可以提高数据库查询处理的整体性能.
关键词: 海量关系;压缩数据库;小值域属性组;NP-完全问题
中图法分类号: TP311 文献标识码: A
1 问题提出
信息技术的发展使得各领域的信息量都爆炸性地增长,高于1012字节的海量数据层出不穷.为了有效地管理海量数据,人们提出了压缩数据库技术[1−15].压缩数据库技术可以提高海量数据的存储效率,也是提高数据库性能的重要途径[3−5].目前,压缩数据库技术的研究主要包括适应于数据库随机存取特征的数据压缩方法、压缩数据上的操作算法、压缩数据库的查询优化技术等.本文研究数据库压缩算法.
经过大量调查研究,我们发现海量关系中常存在一些属性,关系在这些属性上的投影结果非常小.我们称这样的属性组为小值域属性组(small-range attributes’ combination,简称SRAC).例如,在码头的货物运输管理数据库中有一个记录接/发货物情况的关系,它记录运输合同号、货物名称编号、货物供应商编号、货物运送任务编号、货物数量、附加费、折扣、返回标识、货运状况、发货日期、到达日期、签收日期、押运负责人、备注等诸多属性的值.在这个关系中,由货物运送任务编号、发货日期、到达日期、押运负责人、运货方式、返回标识等属性构成了一个SRAC.我们考察了3 000万条记录在这组属性上的投影,其结果低于1 000万条记录.再如,在移动通信公司的数据库中,通话详单这个关系包含了约40多个属性,其中业务服务类型、业务服务号码、用户类型、费用类型、归属地区号、到访地区号等等10多个属性也构成一个SRAC.在大型商场的交易详单中,商品名称、生产厂家、零售价、销售员等属性也构成一个SRAC.事实上,海量关系常包含几十个甚至上百个属性,其中往往有多个属性的值域较小并导致小值域属性组的出现.
显然,SRAC的存在使得海量关系中产生大量数据冗余.若能将SRAC从海量关系中分离出来,并将原关系拆分成多个小关系,就可以消除由SRAC引起的数据冗余.同时,由于拆分后元组长度减小,每个物理存储块中可以容纳更多元组,则可以减小查询操作时的I/O次数,进而改善数据库的性能.如何消除由SRAC引起的数据冗余,实现对海量关系的压缩,是一个新的数据库压缩问题.本文旨在研究针对海量关系常存在SRAC这个特点的数据压缩方法.
本文首先研究了SRAC的识别问题,它是拆分压缩的关键,并证明了这个问题是NP-完全的,然后给出了近似求解这个问题的贪心算法和遗传算法.进而,提出了海量关系拆分压缩方法.最后,讨论了基于海量关系拆分压缩方法的查询处理技术.
2 相关工作
压缩数据库技术可以提高存储效率并改善数据库的整体性能,故该技术已受到工业界和学术界的重视.事实上,Oracle的开发者已将成熟的字典压缩技术整合到数据库物理层中,改善了数据库的存储效率和数据库的整体性能[6].另一些数据库压缩技术已广泛地被商用数据库采用,其中包括缩写、空值悬挂、游程编码、差值压缩等.迄今为止,已有的压缩数据库实验系统包括IMS[7],AODB [8]和NDB[9],这些系统均是将成熟的压缩技术应用到数据库系统中构建的原型系统.
目前,数据库压缩技术的研究主要集中在以下4个方面:(1) 数据库压缩方法的研究,包括使用已有的数据压缩算法压缩数据库和研究新的适应于数据库存取模式的数据压缩方法.被应用于数据库压缩的传统数据压缩方法包括字典压缩技术、游程压缩技术、算术压缩和LZ压缩技术[3],提出的适应于数据库存取模式的数据压缩方法包括索引压缩方法[10]、保序压缩技术[11]、基于语义的压缩技术[12]、面向块的增量压缩方法[13]、映射完全的数据压缩算法[9].(2) 压缩数据上的操作算法的研究,主要是在压缩数据上无须解压缩或解压代价极小

骆吉洲等:一种有效的关系数据库压缩方法 207
的数据操作算法[2,9,14].(3) 压缩数据库上的查询优化处理技术的研究.目前的研究结果很少,只有文献[4,15]研究了数据压缩技术对查询优化技术的影响,提出了适合于压缩数据库的查询优化策略以提高数据库的性能.(4) 压缩数据库的自动设计技术的研究.文献[15]提出了一种压缩数据库的自动设计方法.这种方法根据给定的数据库、数据库上常执行的查询及其被执行的概率,从可用的压缩方法集合中挑选一组方法来压缩给定的数据库,使得这些查询效率最高.
在这方面的所有研究中,压缩方法的研究是最活跃的,特别是针对海量数据及其操作的具体特点来研究数据库压缩算法.文献[12]根据海量关系中一些元组在某些属性上取值的相似性,提出了一种有损的语义压缩方法.作者将海量关系的元组分类并为每类选取一个代表元组.对每类的任意元组,均用代表元组表示,除非它与代表元组的误差超出了指定范围.文献[9]为了在压缩数据库中实现无须解压缩的连接操作,将关系拆分成二元关系,并用MASK方法实现了数据库的压缩存储.文献[10]根据高维数据的特点,提出了一种有效的索引压缩方法.文献[13]中针对统计数据库中元组的聚类性质提出了面向块的增量压缩方法.
本文根据海量关系中经常存在小值域属性组这个特征,提出了海量关系的拆分压缩方法.实验结果表明,拆分压缩技术可以取得较好的压缩效果,并可以提高数据库查询处理的整体性能.
3 小值域属性组识别问题的NP-完全性
3.1 问题的定义
设R?X1,X2 ,…,Xn?是一个n元关系,其中Xi标识R的第i个属性.如果{,,…,}⊂{X1iX2iXkiX1,X2,…,Xn},则我们将R在{,,…,}上的投影结果关系记为R?,,…,?.在下面的讨论中,我们用m和m′分别表示R的元组数和R?,,…,?中的元组数. 1iX2iXkiX12iX1iX2iXkiXiXkiX
定义1. 设α∈(0,1),{,,…,}⊂{X1iX2iXkiX1,X2,…,Xn},如果m′/m≤α,则称{,,…,}是关系R的一个α-小值域属性组.1−α称为小值域属性组的冗余度. 1iX2iXkiX
设{,,…,}⊂{X1iX2i2iXkiXkiXX1,X2,…,Xn},{Y1,Y2,…,}={XkinY−1,X2,…,Xn}−{,,…,},我们可以考虑将关系拆分成两个关系R?,,…,?和R?Y1iXkiX2iXkiX1i2iXkiX1,Y2,…,?.这样,我们就消除了关系R中由小值域属性组{,,…,}引起的数据冗余.读者可能会问,如何从R?,,…,?和R?YkinY−1iXX1iX2iX1,Y2,…,?恢复关系R?我们将在第5节给出解决这个问题的方法. kinY−
为了便于讨论,假设R的所有属性都是定长的,属性Xi的宽度为wi,i=1,2,…,n.这样,存储整个关系所需要的空间为,而存储R?,,…,?和R?YΣ=niiwm11iX12iX2iXkiXk1,Y2,…,Y?的空间分别为m和.这样,如果对R的存储改为对R?,,…,?和R?Ykin−kiΣ=′niiw1Σ−∈},...,{},...,1{1kiiniiwmiXiX1,Y2,…,Y?的存储,则节省的空间可以表示为 n−
(1) ΣΣΣΣ=−∈==′−=????????+′−kkkiiiiiniiiiiniiwmmwmwmwm1},...,{},...,1{11)(1
如果式(1)大于0,则这种策略可以达到压缩效果.我们的问题是如何在关系R上找到某个小值域属性组,使得式(1)达到最大.于是,我们得到下述的小值域属性组识别问题:
输入:关系R?X1,X2 ,…,Xn?,属性Xi的存储空间wi,i=1,2,…,n;
输出:{X1,X2,…,Xn}的子集A,使得达到最大. Σ=′−kiiiwmm1)(
3.2 极大向量问题的NP-完全性
为证明海量关系中小值域属性组识别问题是NP-完全问题,我们定义极大向量问题,并证明其NP-完全性.
定义2. 设?v1,v2,…,vn?∈{0,1}n,?t1,t2,…,tn?∈{0,1}n.若vi≤ti,i=1,2,…,n,则称向量?v1,v2,…,vn?和?t1,t2,…,tn?满足关系≤.
定义3. 设W=?w1,w2,…,wn?是任意向量,其中wi∈N+.∀V=?v1,v2,…,vn?∈{0,1}n,定义V与W的⋅运算为

208 Journal of Software 软件学报 2005,16(2)
V⋅W=. Σ=niiiwv1
注意到,关系≤是{0,1}n上的偏序关系.为了简单计,我们将?1,1,…,1?∈{0,1}n记为e.
定义4. 如下问题称为极大向量问题:给定n维向量空间中的权值向量W=?w1,w2,…,wn?,投影函数f(V): {0,1}n→N+,且f是增函数(即若V1≤V2,则f(V1)≤f(V2)),找出V0∈{0,1}n,使得[f(e)−f(V0)](V0⋅W)=[f(e)−f(V)] (V⋅W). nV}1,0{max∈
引理1. 设a>0,b>0且a+b=c(c是常数),则ab≤c2/4且等号成立,当且仅当a=b=c/2.
定理1. 极大向量问题是一个NP-完全问题.
证明:极大向量问题是一个NP问题,因为我们可以使用非确定的图灵机在多项式时间内枚举{0,1}n的每个向量V,并通过计算[f(e)−f(V0)](V0⋅W)来判断V是否为问题的解.
下面将集合划分问题归约到极大向量问题.设(S,g)是集合划分问题的任意实例.取n=|S|并建立S到集合{1,2,…,n}的一一映射map,称这个映射为S到集合{1,2,…,n}上的索引函数,并将其逆函数记为map−1.
令权值向量W=?g(map−1(1)),g(map−1(2)),…,g(map−1(n))?,投影函数f(V)=V⋅W.这样,得到极大向量问题的一个实例(n,W,f).显然,上述过程可在多项式时间内完成.注意,极大向量问题实例(n,W,f)中,[f(e)−f(V)]+(V⋅W)= f(e)=(常数). Σ∈Sxxg)(
下面证明(S,g)有解当且仅当(S,w,f)有解.
(1) 设A⊆S是(S,g)的一个解.于是ΣΣ−∈∈=ASxAxxgxg)()(.根据索引函数得到{1,2,…,n}的一个子集{map(x)|x∈ A}.进而得到向量V=?v1,v2,…,vn?∈{0,1}n,其中vi=1,若i∈{map(x)|x∈A},否则vi=0.于是,
V⋅W=f(V)=====Σ=niiiwv1Σ∈Axxmapxmapwv)()(Σ∈Axxmapw)(Σ∈−Axxmapmapg))(((1Σ∈Axxg)(,
f(e)−f(V)=−=Σ=niiw1Σ=niiiwv1iniiwveΣ=−1)(=Σ−∈ASxxmapw)(== Σ−∈−ASxxmapmapg))(((1Σ−∈ASxxg)(.
从而,f(e)−f(V)=V⋅W.根据转换过程的说明和引理1可知,V就是极大向量问题实例(n,W,f )的一个解.
(2) 设极大向量问题实例(S,w,f)的解为V=?v1,v2,…,vn?.由V得到S的子集A={x∈S|vmap(x)=1}.类似于式(1)中的计算可以得到f(e)−f(V)=Σ−∈ASxxg)(和V⋅W=,判断f(e)−f(V)=V⋅W是否成立.我们断言:当该等式成立时,A是(S,g)的解;否则,(S,g)无解.前半部分结论显然,现用反证法证明后半部分结论.设(S,g)的一个解为B,由式(1)的过程得到(n,w,f)的另一解VΣ∈Axxg)(B,它使[f(e)−f(VB)](VB⋅W)最大且f(e)−f(VB)=VB⋅W.由f(e)−f(V)≠V⋅W和引理1可知,[f(e)−f(V)](V⋅W)<[f(e)−f(VB)](VB⋅W),这与V是(S,w,f)的解矛盾.
显然,可在多项式时间内把极大向量问题实例(S,w,f)的解转换为集合划分问题实例(S,g)的解. □
3.3 小值域属性组识别问题的NP-完全性
给关系R的所有属性规定一个顺序(如R的第i个属性就是Xi),则属性集合{X1,X2,…,Xn}的任意子集A可表示为{0,1}上的一个n维向量?x1,x2,…,xn?∈{0,1}n,其中xi=1表示Xi在A中,xi=0表示Xi不在A中.进而,R在A上的投影结果R?A?可表示为R?x1,x2,…,xn?.在寻找关系R的小值域属性组时,确定子关系R?x1,x2,…,xn?的元组数必须扫描关系R.下面将证明:即使关系扫描可以“有效完成”,小值域属性组识别问题也是NP-完全的.所谓“有效完成”是指存在一个函数f:{0,1}n→N+,使子关系R?x1,x2,…,xn?的元组数可以通过计算f在(?x1,x2,…,xn?)的函数值来获得.若A,B是关系R的属性集的两个子集且A⊆B(这意味着A的向量表示?x1,x2,…,xn?和B的向量表示?y1,y2,…,yn?满足{0,1}n上的偏序关系≤),则子关系R?A?的元组数不超过子关系R?B?的元组数.于是,如果上面的函数f存在,则f(?x1,x2,…,xn?)≤f(?y1,y2,…,yn?),即f是一个增函数.
基于上面的讨论,小值域属性组识别问题可以重新表述为:
输入:关系R的属性个数n,各个属性的存储空间wi构成的向量W=?w1,w2,…,wn?,计算子关系R?x1,x2,…,xn?

骆吉洲等:一种有效的关系数据库压缩方法 209
的元组数的增函数f:{0 , 1}n→N+;
输出:V0∈{0,1}n使得[f(e)−f(V0)](V0⋅W)=[f(e)−f(V)](V⋅W). nV}1,0{max∈
重新表述的问题是极大向量问题,我们已经证明它是NP-完全的.这说明求解小值域属性组识别问题时需要的扫描数据库的遍数不可能表达成属性个数n的多项式,除非NP=P.于是,我们得到如下结论.
定理2. 小值域属性组识别问题是一个NP-完全问题.
4 小值域属性组的识别算法
从第3节我们看到,即使假定扫描数据中海量关系的过程可以“有效完成”,小值域属性组的识别问题也是NP完全的.现在我们给出两种近似算法来求解这个问题.为了有效控制算法扫描海量关系的遍数,算法要求用户指定小值域属性组的冗余度下限1−α.事实上,如果用于拆分压缩的小值域属性组的冗余度过低,拆分压缩的效果将很差.因此,用于拆分压缩的小值域属性组的冗余度应该高于某个下界.值得注意的是,输出集合中属性的个数与α直接相关,α越大,输出的属性集合中属性的个数越多,但是压缩的效果不一定好.因此,怎样设置α的一个恰当的值,是一个值得关注的问题.下面我们分别给出这两种算法.
4.1 基于贪心策略的小值域属性组识别算法
算法的输入是数据库、各个属性的存储空间及冗余度的下限1−α(即α的上限),其输出为小值域属性组A.算法开始时置A为空集,然后每次选择当前A的最优扩充属性X加入A,直到A的冗余度超过设定的上限α.这里需要指出两点:(1) 作为α的上限是通过经验得出的;(2) 最优扩充是指把X加入A后所节省的空间最大的扩充.下面是这种算法的描述:
算法. Recon-greedy
输入:数据库R?X1,X2,…,Xn?,各个属性的宽度W[i],上限α.
输出:一个小值域属性组A,使得最大,其冗余度以1−α为下界. Σ=′−kiiiwmm1)(
1. A←∅,Freq←0,m←R?X1,X2,…,Xn?中的元组数;
2. WHILE (Freq<α) DO
3. Temp←$; W[Temp]←∞, mTemp←m;
4. FOR {X1,X2,…,Xn}\A中的每个属性X DO /*确定最优扩充属性*/
5. 扫描数据库R确定子关系R?A∪{X}?的元组数m′;
6. IF m′/m<α 且(m−m′)(w+W[X])<(m−mTemp)(w+W[Temp]) THEN
7. Temp←X, mTemp←m′;
8. Freq←mTemp/m; /*根据最终找到的属性做扩充*/
9. IF (Freq<α) THEN
10. A←A∪{Temp}, w←w+W[Temp];
11. 返回A.
算法中第2步的WHILE循环至多为n次,且每次WHILE循环中第4步的FOR循环至多执行n次,每次FOR循环中都包含了一次数据库扫描.因此扫描数据库的次数最坏情况是O(n2).虽然如此,对于海量关系,扫描O(n2)次关系的时间仍是惊人的.对此,有如下两方面的考虑:(1) 压缩数据库通常是一次压缩多次使用,压缩数据库的时间复杂度常放到次要的地位来考虑.(2) 对海量数据关系,可先通过随机抽样获得适量的元组,再在样本上运行上面的算法,以节省扫描数据库需要的时间;然后还可以对在样本上得到的小值域属性组作进一步修改,得到更准确的小值域属性组.
4.2 基于遗传算法的小值域属性组识别算法
为了进一步减少识别小值域属性组的时间复杂性,本节给出一种遗传算法.小值域属性组识别问题是一个

210 Journal of Software 软件学报 2005,16(2)
组合优化问题,而且第3节中描述的属性集合的向量表示自然地实现了这个问题的解空间的编码.将编码后的解空间{0,1}n视为种群空间,将任意属性集合的编码向量?x1,x2,…,xn?视为种群空间中的个体染色体.于是,可以用遗传算法来求解.这里采用杰出遗传算法.初始时,把冗余度未超过冗余度下限的单属性的向量表示选入初始种群.种群中个体?x1,x2,…,xn?的适应度就是利用该属性组进行拆分压缩所能够节省的空间的大小.然后,在种群中按照适应度大小随机选择母体进行杂交、变异产生新的种群,并在新种群中保留上一代种群中适应度最大的个体,重新计算各个个体的适应度.重复上述过程,直到下述条件之一成立:(1) 连续N代种群中适应度最大的个体不发生变化;(2) 种群中个体数低于某下限;(3) 总循环次数超过指定上界.最后所得适应度最好的属性组作为小值域属性组输出.
算法. Recon-Gen.
输入:数据库R?X1,X2,…,Xn?,各个属性宽度W[i],α,N.
输出:一个小值域属性组A,使得最大,其冗余度以1−α为下界. Σ=′−kiiiwmm1)(
1. 将冗余度不超过α的单属性的向量表示加入初始种群Q[],并计算初始种群中各个体的适应度F[];
2. fit_count←0,loop_count←0;
3. WHILE ((loop_count≤循环上界)且(fit_count≤N)且(Q[]中的个体数≥下限)) DO
4. k←Q[]中个体的总数,f← Σ=kiiF1][;
5. FOR i=1 TO k−1 DO
6. 随机从Q[]中选取个体?x1,x2,…,xn?和?y1,y2,…,yn?; /* Q[t]被选中的概率为F[t]/f */
7. 将选中的两个个体在随机选定的位置杂交得到个体?z1,z2,…,zn?;
8. 将?z1,z2,…,zn?的每个基因位等概率(取0.1)地变异;将新得到的个体插入下一代种群Q′[]中,并计算其适应度;
9. 将Q[]中适应度最大的个体插入Q′[]中,并得到相应的适应度;
10. 删除Q′[]中冗余度超过α的个体;
11. IF (Q[]中适应度最大的个体与Q′[]中适应度最大的个体相同) THEN fit_count++;
ELSE fit_count←0;
12. 删除Q[]中所有个体并调换Q[]和Q′[]的角色;
13. 输出Q[]中适应度最大的个体.
算法Recon-gen的时间复杂度取决于算法的3个终止条件中使用的参数.我们的实验结果表明,上述算法的运行时间低于基于贪心策略的算法,并能够获得更好的结果.
5 海量关系的拆分压缩方法
给定海量关系R和冗余度下限1−α,利用第4节中描述的算法,可以得到关系R的α小值域属性组A={,,…,}(R?,,…,?的元组数为m′).令{Y1iX1iX2iX2kiXki1iX2iXn−kiX1,Y2,…,Y}={Xkin−1,X2,…,Xn}−{,,…,}.关系R的拆分压缩十分简单,只需将R拆分成两个关系R1iX2iXkiX1和R2,使得R1和R2的属性集合分别是包含{,,…,}和{YiXX1,Y2,…,Y}的最小属性集合.在拆分过程中,我们需要考虑下面的两个问题:(1) 如何保证关系R=Join(Rki1,R2)?Join表示两个关系的连接操作;(2) 易知,关系R的t(≥1)个元组对应关系R1中的一个元组和关系R2的t个元组.拆分压缩时如何反映这种对应关系?
为解决上述两个问题,引入单射φ:R?,,…,?→N1iXjix????|,2iX1iXXkiXjX+,并用它作为R1和R2之间的连接属性(如,可以具体定义为φ(,,…,)=其中||表示属性的值域大小,是数值化后的属性值.)于是,可以把R拆分为R1ix2ixkixnkjijnXΣΠ=−=????110|iX2ijiXjix1和R2,其模式为R1＝R(,,…,,φ)和Rki2＝R(φ,Y1,Y2,…,Y),并将属性φ定义为关系Rkin−1的主键.

骆吉洲等:一种有效的关系数据库压缩方法 211
设新增属性φ的宽度为v.结合第3节的讨论,我们知道存储整个关系所需要的空间为,而存储RΣ=niiwm11和R2的空间分别为和.故,通过拆分压缩方法压缩掉的空间为 ????????+′Σ=kiiivwm1????????+Σ∈},...,{\},...,1{1kiiniivwm
−+= (2) Σ=niiwm1????????????+′Σ=kiiivwm1????????????+Σ∈},...,{\},...,1{1kiiniivwmvmmwmmkiii)()(1′+−′−Σ=
由于m′/m≤α,压缩比的下限为(vwiiik)1()1,...,1αΣα+−−=.拆分压缩前,需要由此估算拆分压缩的压缩比.如果这个压缩比是合理的,则对关系R进行拆分压缩;否则,放弃拆分压缩.
拆分压缩时,对于关系R的每个元组,我们首先分别计算它在属性集合{,,…,}和{Y1iX2ix2iXkixkiX1,Y2,…,}上的投影(,,…,)和(,,…,);然后计算=φ(,,…,);最后将(,, ,…,)和(,,…,,)分别插入关系RkinY−)k1iy1ixkin−kix2ix(Nkix1x),...,kx1iyx2iykikiny−,...,,21kxx),...,,(21kxxxN1ix,...,,(21xxxN2iy1ixyix,21x2i)(xN1和R2.由于φ是关系R1的主键,当(,,…,,)在关系R2ixx1中已经存在时,后一个插入操作自动失败.下面是拆分压缩算法.
算法. Splitting-Compression.
输入:关系R,R各属性的宽度,R的一个α小值域属性组{,,…,},ε >0. 1ix<span st
分享到：
| 强烈推荐:销售经理的七大定理
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

Magicbox
Global site tag (gtag.js) - Google Analytics