精华内容
下载资源
问答
  • 数据库压缩

    2013-01-24 10:53:34
    数据库文件分为2个 数据库名_Data.MDF --数据文件 数据库名_Log.LDF --日志文件 数据文件可以收缩,减少数据库未使用的空间。 操作方法,资源管理器--》数据库--》右键--》任务--》收缩--》数据库 通过...

    数据库文件分为2个

    数据库名_Data.MDF   --数据文件

    数据库名_Log.LDF --日志文件


    数据文件可以收缩,减少数据库未使用的空间。

    操作方法,资源管理器--》数据库--》右键--》任务--》收缩--》数据库

    通过选择进行收缩。


    日志文件随着使用时间增长,如果没有设置最大限制的话,会产生很大的文件。通过重置清楚日志,释放硬盘空间

    將復原模式切換為簡易,壓縮後,再將復原模式切換為完整 

    USE dbname
    GO
    
    -- Truncate the log by changing the database recovery model to SIMPLE.
    ALTER DATABASE dbname SET RECOVERY SIMPLE;
    GO
    
    
    --有时出现建立数据库时,文件名称与数据库名称不一致,需要查询系统表确认日志名称
    select name from sys.database_files
    where type_desc='log'
    -- Shrink the truncated log file to 1 MB.
    DBCC SHRINKFILE (logname, 1);
    
    GO
    -- Reset the database recovery model.
    ALTER DATABASE dbname SET RECOVERY FULL;
    
    GO

    处理完毕后 日志文件变为1m

    展开全文
  • 一种有效的关系数据库压缩方法

    千次阅读 2006-02-23 14:38:00
    Vol.16, No.2 ©2005 Journal of Software 软 件 学 报 1 000-9825/2005/16(02)0205 一种有效的关系数据库压缩方法∗ 骆吉洲1+, 李建中1,2 1(哈尔滨工业大学 计算机科学与技术学院,黑龙江 哈尔滨 150001) 2(黑龙江...
    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个属性.如果{,,…,}⊂{X 1 i X 2 i X k i X1,X2,…,Xn},则我们将R在{,,…,}上的投影结果关系记为R〈,,…,〉.在下面的讨论中,我们用m和m′分别表示R的元组数和R〈,,…,〉中的元组数. 1 i X 2 i X k i X 12 i X 1 i X 2 i X k i X i X k i X
    定义1. 设α∈(0,1),{,,…,}⊂{X 1 i X 2 i X k i X1,X2,…,Xn},如果m′/m≤α,则称{,,…,}是关系R的一个α-小值域属性组.1−α称为小值域属性组的冗余度. 1 i X 2 i X k i X
    设{,,…,}⊂{X 1 i X 2 i 2 i X k i X k i XX1,X2,…,Xn},{Y1,Y2,…,}={X k in Y 1 ,X2,…,Xn}−{,,…,},我们可以考虑将关系拆分成两个关系R〈,,…,〉和R〈Y 1 i X k i X 2 i X k i X 1 i 2 i X k i X1,Y2,…,〉.这样,我们就消除了关系R中由小值域属性组{,,…,}引起的数据冗余.读者可能会问,如何从R〈,,…,〉和R〈Y k in Y 1 i XX 1 i X 2 i X1,Y2,…,〉恢复关系R?我们将在第5节给出解决这个问题的方法. k in Y
    为了便于讨论,假设R的所有属性都是定长的,属性Xi的宽度为wi,i=1,2,…,n.这样,存储整个关系所需要的空间为,而存储R〈,,…,〉和R〈Y Σ =nii wm 1 1 i X 12 i X 2 i X k i X k1 ,Y2,…,Y〉的空间分别为m和.这样,如果对R的存储改为对R〈,,…,〉和R〈Y k in− k i Σ = nii w 1 Σ −∈},...,{},...,1{ 1k iinii wm i X i X1,Y2,…,Y〉的存储,则节省的空间可以表示为 n−
    (1) ΣΣΣΣ =−∈== ′−=+′− kkk iiiiiniiiiinii wmmwmwmwm 1},...,{},...,1{11 )( 1
    如果式(1)大于0,则这种策略可以达到压缩效果.我们的问题是如何在关系R上找到某个小值域属性组,使得式(1)达到最大.于是,我们得到下述的小值域属性组识别问题:
    输入:关系R〈X1,X2 ,…,Xn〉,属性Xi的存储空间wi,i=1,2,…,n;
    输出:{X1,X2,…,Xn}的子集A,使得达到最大. Σ = ′− k iii wmm 1 )(
                  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=. Σ =niii wv 1
    注意到,关系≤是{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). n V}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)=(常数). Σ ∈Sx xg)(
    下面证明(S,g)有解当且仅当(S,w,f)有解.
    (1) 设A⊆S是(S,g)的一个解.于是 ΣΣ −∈∈ = ASxAx xgxg)()(.根据索引函数得到{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)===== Σ =niii wv 1 Σ ∈Axxmapxmap wv )()( Σ ∈Axxmap w )( Σ ∈−Ax xmapmapg))((( 1 Σ ∈Ax xg)(,
    f(e)−f(V)=−= Σ =nii w 1 Σ =niii wv 1inii wve Σ = 1 )(= Σ −∈ASxxmap w )( == Σ −∈−ASx xmapmapg))((( 1 Σ −∈ASx xg)(.
    从而,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)= Σ −∈ASx xg)(和V⋅W=,判断f(e)−f(V)=V⋅W是否成立.我们断言:当该等式成立时,A是(S,g)的解;否则,(S,g)无解.前半部分结论显然,现用反证法证明后半部分结论.设(S,g)的一个解为B,由式(1)的过程得到(n,w,f)的另一解V Σ ∈Ax xg)(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). n V}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−α为下界. Σ = ′− k iii wmm 1 )(
    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−α为下界. Σ = ′− k iii wmm 1 )(
    1. 将冗余度不超过α的单属性的向量表示加入初始种群Q[],并计算初始种群中各个体的适应度F[];
    2. fit_count←0,loop_count←0;
    3. WHILE ((loop_count≤循环上界)且(fit_count≤N)且(Q[]中的个体数≥下限)) DO
    4. k←Q[]中个体的总数,f← Σ =ki iF 1 ][;
    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′).令{Y 1 i X 1 i X 2 i X 2k i X k i 1 i X 2 i X n− k i X1,Y2,…,Y}={X k in−1 ,X2,…,Xn}−{,,…,}.关系R的拆分压缩十分简单,只需将R拆分成两个关系R 1 i X 2 i X k i X1和R2,使得R1和R2的属性集合分别是包含{,,…,}和{Y i XX1,Y2,…,Y}的最小属性集合.在拆分过程中,我们需要考虑下面的两个问题:(1) 如何保证关系R=Join(R k i1 ,R2)?Join表示两个关系的连接操作;(2) 易知,关系R的t(≥1)个元组对应关系R1中的一个元组和关系R2的t个元组.拆分压缩时如何反映这种对应关系?
    为解决上述两个问题,引入单射φ:R〈,,…,〉→N 1 i X j i x|, 2 i X 1 i XX k i X j X+,并用它作为R1和R2之间的连接属性(如,可以具体定义为φ(,,…,)=其中||表示属性的值域大小,是数值化后的属性值.)于是,可以把R拆分为R 1 i x 2 i x k i x n kjijn X ΣΠ =−=  110 | i X 2 i j i X j i x1和R2,其模式为R1=R(,,…,,φ)和R k i2 =R(φ,Y1,Y2,…,Y),并将属性φ定义为关系R k in−1 的主键.

    骆吉洲等:一种有效的关系数据库压缩方法 211
    设新增属性φ的宽度为v.结合第3节的讨论,我们知道存储整个关系所需要的空间为,而存储R Σ =nii wm 11 和R2的空间分别为和.故,通过拆分压缩方法压缩掉的空间为 +′ Σ = k iii vwm 1 + Σ ∈},...,{/},...,1{ 1k iinii vwm
    −+= (2) Σ =nii wm 1 +′ Σ = k iii vwm 1 + Σ ∈},...,{/},...,1{ 1k iinii vwmvmmwmm k iii )()( 1 ′+−′− Σ =
    由于m′/m≤α,压缩比的下限为(vw iii k )1()1 ,...,1 αΣα+−− = .拆分压缩前,需要由此估算拆分压缩的压缩比.如果这个压缩比是合理的,则对关系R进行拆分压缩;否则,放弃拆分压缩.
    拆分压缩时,对于关系R的每个元组,我们首先分别计算它在属性集合{,,…,}和{Y 1 i X 2 i x 2 i X k i x k i X1,Y2,…,}上的投影(,,…,)和(,,…,);然后计算=φ(,,…,);最后将(,, ,…,)和(,,…,,)分别插入关系R k in Y −) k1 i y 1 i x k in− k i x 2 i x ( N k i x 1 x ),..., k x 1 i yx 2 i y k i k in y −,...,, 21k xx),...,,( 21k xxx N 1 i x ,...,,( 21 xxx N 2 i y 1 i xy i x , 21 x 2 i)(x N1和R2.由于φ是关系R1的主键,当(,,…,,)在关系R 2 i x x1 中已经存在时,后一个插入操作自动失败.下面是拆分压缩算法.
    算法. Splitting-Compression.
    输入:关系R,R各属性的宽度,R的一个α小值域属性组{,,…,},ε >0. 1 i x 2 i x k i x
    输出:关系R的拆分R1和R2.
    1. 估算压缩比下限Ratio;
    2. IF Ratio<ε,返回;
    3. 建立关系模式R1=R(,,…,,φ)和R 1 i X 2 i X k i X2=R(φ,Y1,Y2,…,Y); k in−
    4. FOR R的每个元组T DO
    5. 计算T在{,,…,}和{Y 1 i X 2 i X k i X1,Y2,…,Y}上的投影(,,…,)和(,,…,); k in− 1 i x 2 i x k i x 1 i y 2 i y k in y
    6. 计算φ; ),...,,( 21k xxx N=),...,,( 21k iii xxx
    7. 将(,,,…,)插入关系R ),...,,( 21k xxx N 1 i y 2 i y k in y 2 ,将)插入关系R k iii xxx,...,,( 21 ),...,,( 21k xxx N1.
    显然,算法Splitting_Compression仅需要扫描一遍关系R.
    定理3. R=Join(R1,R2),其中R1=R(,…,,φ),R 1 i X 2 i X k i X2=R(φ,Y1,Y2,…,Y). k in−
    证明:根据小值域属性组的定义和拆分压缩算法,直接验证R⊆Join(R1,R2)和R⊇Join(R1,R2)即可. □
                  6 基于压缩方法的查询处理
     
    拆分压缩后,对原关系R的查询变成了对关系R1和R2 的查询,这涉及到Join操作.完成此查询有两种方法:
    方法1. 直接在上述两个关系上进行连接操作.
    方法2. 按照下面的3个步骤进行:(1) 将原查询q分解为在关系R1上的查询q1和在关系R2上的查询q2;
    (2) 分别执行查询q1和q2;(3) 将由(2)得到的结果执行以φ为连接属性的自然连接,得到最终结果.
    数据库的查询优化器对这两种方法的代价进行比较,选择代价较小的方法进行操作.另外,还可以在φ上建立索引以提高Join操作的效率.
    我们将在另文中详细讨论拆分压缩后的关系上的查询优化与处理方法.
                  7 实验结果
     
    我们实现了小值域属性组的提取算法和海量关系的压缩算法,下面是我们的实验结果.实验运行于Linux6.2平台上的Oracle数据库,服务器是配置为PIV2.0GHz、内存256Mb的PC机.实验数据采用TPC-H生成的4G的数据量.压缩的关系是TPC-H中的LINEITEM关系,因为该关系的数据量占整个数据库数据量的约80%,其中包含30 007 486条记录.实验主要包含以下3方面的内容.
    第1组实验研究小值域属性组识别算法中不同的冗余度下限对算法输出结果的影响.实验中,多次在关系

    212 Journal of Software 软件学报 2005,16(2)
    LINEITEM上运行算法Recon-greedy,每次设置不同的冗余度下限.表1给出了实验结果.表中前3列分别给出了列名、各列值域的大小和各列的存储空间大小.表的后3列中为1的单元分别给出了冗余度下限分别为0.3,0.5和0.7时算法提取的SRAC中包含的属性.当1−α=0.3时,SRAC上的不同取值的数量是7 103 769.当1−α=0.5或0.4时,SRAC上的不同取值的数量是10 032 094.此外,当向这个0.5SRAC添加任意其他属性时,冗余度都在0.2以下.因此,适于SRAC识别算法的冗余度下限的合理的范围是[0.4,0.6].因此,在后面的实验中,始终设置冗余度的下限为0.5.
    Table 1 The identification of SRAC
    1 小值域属性组的识别
    Attribute name
    Range size of attribute
    Storage space of attribute
    Selected attributes by algorithm
    α=0.5
    α=0.3
    α=0.7
    Orderkey
    7 500 000
    21
    0
    0
    0
    Partkey
    5 960 934
    21
    0
    0
    0
    Suppkey
    300 000
    21
    0
    0
    0
    Linenumber
    7
    38
    1
    1
    1
    Quantity
    50
    21
    1
    0
    1
    Extendedprice
    2 093 773
    21
    0
    0
    0
    Discount
    11
    21
    1
    1
    1
    Tax
    9
    21
    0
    0
    0
    Returnflag
    3
    1
    1
    0
    1
    Linestatus
    2
    1
    1
    0
    1
    Shipdate
    2 526
    7
    1
    1
    1
    Commitdate
    2 466
    7
    0
    0
    0
    Reciptdate
    2 555
    7
    0
    0
    0
    Shipinstruct
    4
    25
    1
    1
    1
    Shipmode
    7
    10
    1
    1
    1
    Commit
    11 466 069
    44
    0
    0
    0
     
    第2组实验是两个SRAC识别算法性能的比较.置冗余度下限为0.5,然后分别执行算法Recon-greedy和Recon-gen.图1给出了两种算法识别的SRAC时属性个数随扫描数据库的遍数的变化情况.两条曲线基本呈阶梯状变化,这是由于,在遗传算法中要等到每一代种群处理完之后才可能引起频繁属性的个数的变化,而贪心算法中每次循环完成后才引起小值域属性组的一次扩充.其次,在得到SRAC的过程中,遗传算法的收敛速度较贪心算法快很多,这主要是因为遗传算法在连续两代种群的变化过程中可能向SRAC中引入多个属性,且淘汰机制的引入使得种群规模逐渐减小.最后,两种算法得出的SRAC之间没有严格的包含关系.
    Fig.1 The comparison of SRAC identification algorithms
    图1 小值域属性组识别算法的比较
    第3组实验研究拆分压缩对数据库性能的影响.设置冗余度上限为0.5,由算法Recon-gen得到一个0.5小值域属性组,它包含Linenumber,quantity,discount,shipdate,shipinstruct,shipmode等6个属性,由此按照第5节中的方法将关系拆分成两种关系,压缩掉的空间是原表所用空间的21%.然后,从TPC-H的查询中挑选了8个sql语句在压缩后的数据库中执行,结果见表2.第1列给出了sql语句的编号;第2列是相应语句在未压缩的数据库中的执行时间;第3、第4列是相应语句在压缩数据库中的执行时间,两列的区别为是否使用了新增属性上的索引.注意,第8个sql语句是一个嵌套的sql语句,且内层sql语句的select分句中出现了表达式l_extendedprice∗(1−l_discount)−ps_supplycost∗l_quantity,这个表达式中的属性被拆分到两种关系中,而查询处
    理时未能将表达式分解成两种关系上的子表达式,这导致操作时间的增加.
    Table 2 The performance of the compressed database
    2 压缩数据库的性能
    Query
    Original relation
    Compressed relation without new index
    Compressed relation with new index
    sql1
    155.533
    90.457
    87.364
    sql2
    158.157
    130.115
    132.158
    sql3
    145.331
    180.627
    160.151
    sql4
    281.164
    177.572
    160.771
    sql5
    223.532
    108.787
    106.844
    sql6
    667.95
    878.063
    424.218
    sql7
    1 459.428
    1 083.628
    1 060.685
    sql8
    5 427.895
    6 194.844
    5 947.602
     
    此外,文献[21]中也讨论了LINEITEM关系的压缩.在压缩比方面,Oracle的压缩方法的压缩比为38%.但是,Oracle的压缩方法本质上是将字典压缩方法整合到数据库的物理层实现上,故拆分压缩后的海量关系仍然可以用Oracle的压缩方法进一步压缩.从数据库整体性能上来看,Oracle的压缩方法使得数据库整体性能提高了约10%.如果将拆分压缩后的关系用Oracle的压缩方法作进一步压缩,压缩比和数据库整体性能均有可能进一步提高.目前,Oracle的这种压缩方法还不可得,也很难从底层直接实现,因此,关于这两种压缩方法的结合还无法进行讨论.
                  8 结 论
     
    本文根据海量关系中经常出现小值域属性组这一特点提出了拆分压缩技术.本文给出了两种在海量关系中识别小值域属性组合的算法,实验表明,算法中使用的冗余度下限的合理范围应该在0.4~0.6之间.实验结果表明,拆分压缩技术可以取得较好的压缩效果,并能够提高数据库查询处理的性能.
    References :
      [1] Margritis D, Faloutsos C, Thrun S. Netcube: A scalable tool for fast data mining and compression. In: Apers PMG, ed. Proc. of the 27th Int’l Conf. on Very Large Data Bases. Mumbai: Morgan Kaufmann Publishers, Inc, 2001. 311−320.
      [2] Gao H, Li JZ. Cube algorithms for very large compressed data warehouse. Journal of Software, 2001,12(6): 830~839 (in Chinese with English abstract).
      [3] Westmann T, Kossmann D. The implementation and performance of compressed database. ACM SIGMOD Record, 2000,29(3): 55−67.
      [4] Chen ZY, Gehrke J, Korn F. Query optimization in compressed database systems. In: Sellis T, ed. Proc. of the ACM SIGMOD Int’l Conf. on the Management of Data. New York: ACM Press, 2001. 271−282.
      [5] Ray G, Harisa JR, Seshadri S. Database compression: A performance enhancement tool. In: Chaudhuri S, Deshpande A, Krishnamurthy R, eds. Proc. of the Conf. on Management of Data. India: Tata McGraw-Hill, 1995. 106−125.
      [6] Poess M, Potapov D. Data compression in oracle. In: Freytag JC, Lockemann PC, eds. Proc. of the 29th Int’l Conf. on Very Large Data Bases. Mumbai: Morgan Kaufmann Publishers, Inc, 2003. 937−947.
      [7] Cormack GC. Data compression on a database system. Communications of the ACM, 1985,28(12):1336−1342.
      [8] Westmann T, Kossmann D. The implementation and performance of compressed database. ACM SIGMOD Record, 2000,29(3): 55−67.
      [9] O’Connell SJ, Winterbottom N. Performing joins without decompression in a compressed database system. ACM SIGMOD Record, 2003,32(1):55−67.
      [10] Berchtold S. Independent quantization: An index compression technique for high dimensional data space. In: Proc. of the 16th Int’l Conf. on Data Engineering. New Orleans: IEEE Computer Science Society Press, 2000. 577−588.
      [11] Antoshenkov G, Lomet D, Murry J. Order preserving string compression. In: Su YW, ed. Proc. of the 12th Int’l Conf. on Data Engineering. New Orleans: IEEE Computer Science Society Press, 1996. 655−663.
      [12] Jagadish HV, Ng RT, Ooi BC, Tung AKH. ItCompress: An iterative semantic compression algorithm. In: Su YW, ed. Proc. of the 16th Int’l Conf. on Data Engineering. New Orleans: IEEE Computer Science Society Press, 2004. 646−657.

    214 Journal of Software 软件学报 2005,16(2)
      [13] NG WK, Ravishhankar CV. Relational database compression using augmented vector quantization. In: Yu PS, ed. Proc. of the 16th Int’l Conf. on Data Engineering. New Orleans: IEEE Computer Science Society Press, 1995. 540−549.
      [14] Li JZ, Rotem D, Srivastava J. Aggregation algorithms for very large compressed data warehouses. In: Atkinson MP, Orlowska ME, eds. Proc. of the 29th Int’l Conf. on Very Large Data Bases. Mumbai: Morgan Kaufmann Publishers, Inc, 1999. 651−662.
      [15] Chen ZY. Building compressed database system [Ph.D. Thesis]. New York: Connell University, 2002.
     
    附中文参考文献:
    [2] 高宏,李建中.超大型压缩数据仓库上的CUBE算示.软件学报,2001,12(6):830−839.
    展开全文
  • Vol.16, No.2 ©2005 Journal of Software 软 件 学 报 1 000-9825/2005/16(02)0205 一种有效的关系数据库压缩方法∗ 骆吉洲1+, 李建中1,2 1(哈尔滨工业大学 计算机科学与技术学院,黑龙江 哈尔滨 150001) 2(黑龙江...
      
     
    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个属性.如果{,,…,}⊂{X 1 i X 2 i X k i X1,X2,…,Xn},则我们将R在{,,…,}上的投影结果关系记为R?,,…,?.在下面的讨论中,我们用m和m′分别表示R的元组数和R?,,…,?中的元组数. 1 i X 2 i X k i X 12 i X 1 i X 2 i X k i X i X k i X
    定义1. 设α∈(0,1),{,,…,}⊂{X 1 i X 2 i X k i X1,X2,…,Xn},如果m′/m≤α,则称{,,…,}是关系R的一个α-小值域属性组.1−α称为小值域属性组的冗余度. 1 i X 2 i X k i X
    设{,,…,}⊂{X 1 i X 2 i 2 i X k i X k i XX1,X2,…,Xn},{Y1,Y2,…,}={X k in Y 1 ,X2,…,Xn}−{,,…,},我们可以考虑将关系拆分成两个关系R?,,…,?和R?Y 1 i X k i X 2 i X k i X 1 i 2 i X k i X1,Y2,…,?.这样,我们就消除了关系R中由小值域属性组{,,…,}引起的数据冗余.读者可能会问,如何从R?,,…,?和R?Y k in Y 1 i XX 1 i X 2 i X1,Y2,…,?恢复关系R?我们将在第5节给出解决这个问题的方法. k in Y
    为了便于讨论,假设R的所有属性都是定长的,属性Xi的宽度为wi,i=1,2,…,n.这样,存储整个关系所需要的空间为,而存储R?,,…,?和R?Y Σ =nii wm 1 1 i X 12 i X 2 i X k i X k1 ,Y2,…,Y?的空间分别为m和.这样,如果对R的存储改为对R?,,…,?和R?Y k in− k i Σ = nii w 1 Σ −∈},...,{},...,1{ 1k iinii wm i X i X1,Y2,…,Y?的存储,则节省的空间可以表示为 n−
    (1) ΣΣΣΣ =−∈== ′−=????????+′− kkk iiiiiniiiiinii wmmwmwmwm 1},...,{},...,1{11 )( 1
    如果式(1)大于0,则这种策略可以达到压缩效果.我们的问题是如何在关系R上找到某个小值域属性组,使得式(1)达到最大.于是,我们得到下述的小值域属性组识别问题:
    输入:关系R?X1,X2 ,…,Xn?,属性Xi的存储空间wi,i=1,2,…,n;
    输出:{X1,X2,…,Xn}的子集A,使得达到最大. Σ = ′− k iii wmm 1 )(
                  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=. Σ =niii wv 1
    注意到,关系≤是{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). n V}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)=(常数). Σ ∈Sx xg)(
    下面证明(S,g)有解当且仅当(S,w,f)有解.
    (1) 设A⊆S是(S,g)的一个解.于是 ΣΣ −∈∈ = ASxAx xgxg)()(.根据索引函数得到{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)===== Σ =niii wv 1 Σ ∈Axxmapxmap wv )()( Σ ∈Axxmap w )( Σ ∈−Ax xmapmapg))((( 1 Σ ∈Ax xg)(,
    f(e)−f(V)=−= Σ =nii w 1 Σ =niii wv 1inii wve Σ = 1 )(= Σ −∈ASxxmap w )( == Σ −∈−ASx xmapmapg))((( 1 Σ −∈ASx xg)(.
    从而,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)= Σ −∈ASx xg)(和V⋅W=,判断f(e)−f(V)=V⋅W是否成立.我们断言:当该等式成立时,A是(S,g)的解;否则,(S,g)无解.前半部分结论显然,现用反证法证明后半部分结论.设(S,g)的一个解为B,由式(1)的过程得到(n,w,f)的另一解V Σ ∈Ax xg)(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). n V}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−α为下界. Σ = ′− k iii wmm 1 )(
    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−α为下界. Σ = ′− k iii wmm 1 )(
    1. 将冗余度不超过α的单属性的向量表示加入初始种群Q[],并计算初始种群中各个体的适应度F[];
    2. fit_count←0,loop_count←0;
    3. WHILE ((loop_count≤循环上界)且(fit_count≤N)且(Q[]中的个体数≥下限)) DO
    4. k←Q[]中个体的总数,f← Σ =ki iF 1 ][;
    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′).令{Y 1 i X 1 i X 2 i X 2k i X k i 1 i X 2 i X n− k i X1,Y2,…,Y}={X k in−1 ,X2,…,Xn}−{,,…,}.关系R的拆分压缩十分简单,只需将R拆分成两个关系R 1 i X 2 i X k i X1和R2,使得R1和R2的属性集合分别是包含{,,…,}和{Y i XX1,Y2,…,Y}的最小属性集合.在拆分过程中,我们需要考虑下面的两个问题:(1) 如何保证关系R=Join(R k i1 ,R2)?Join表示两个关系的连接操作;(2) 易知,关系R的t(≥1)个元组对应关系R1中的一个元组和关系R2的t个元组.拆分压缩时如何反映这种对应关系?
    为解决上述两个问题,引入单射φ:R?,,…,?→N 1 i X j i x????|, 2 i X 1 i XX k i X j X+,并用它作为R1和R2之间的连接属性(如,可以具体定义为φ(,,…,)=其中||表示属性的值域大小,是数值化后的属性值.)于是,可以把R拆分为R 1 i x 2 i x k i x n kjijn X ΣΠ =−= ???? 110 | i X 2 i j i X j i x1和R2,其模式为R1=R(,,…,,φ)和R k i2 =R(φ,Y1,Y2,…,Y),并将属性φ定义为关系R k in−1 的主键.

    骆吉洲等:一种有效的关系数据库压缩方法 211
    设新增属性φ的宽度为v.结合第3节的讨论,我们知道存储整个关系所需要的空间为,而存储R Σ =nii wm 11 和R2的空间分别为和.故,通过拆分压缩方法压缩掉的空间为 ????????+′ Σ = k iii vwm 1 ????????+ Σ ∈},...,{/},...,1{ 1k iinii vwm
    −+= (2) Σ =nii wm 1 ????????????+′ Σ = k iii vwm 1 ????????????+ Σ ∈},...,{/},...,1{ 1k iinii vwmvmmwmm k iii )()( 1 ′+−′− Σ =
    由于m′/m≤α,压缩比的下限为(vw iii k )1()1 ,...,1 αΣα+−− = .拆分压缩前,需要由此估算拆分压缩的压缩比.如果这个压缩比是合理的,则对关系R进行拆分压缩;否则,放弃拆分压缩.
    拆分压缩时,对于关系R的每个元组,我们首先分别计算它在属性集合{,,…,}和{Y 1 i X 2 i x 2 i X k i x k i X1,Y2,…,}上的投影(,,…,)和(,,…,);然后计算=φ(,,…,);最后将(,, ,…,)和(,,…,,)分别插入关系R k in Y −) k1 i y 1 i x k in− k i x 2 i x ( N k i x 1 x ),..., k x 1 i yx 2 i y k i k in y −,...,, 21k xx),...,,( 21k xxx N 1 i x ,...,,( 21 xxx N 2 i y 1 i xy i x , 21 x 2 i)(x N1和R2.由于φ是关系R1的主键,当(,,…,,)在关系R 2 i x x1 中已经存在时,后一个插入操作自动失败.下面是拆分压缩算法.
    算法. Splitting-Compression.
    输入:关系R,R各属性的宽度,R的一个α小值域属性组{,,…,},ε >0. 1 i x 2 i x k i x
    输出:关系R的拆分R1和R2.
    1. 估算压缩比下限Ratio;
    2. IF Ratio<ε,返回;
    3. 建立关系模式R1=R(,,…,,φ)和R 1 i X 2 i X k i X2=R(φ,Y1,Y2,…,Y); k in−
    4. FOR R的每个元组T DO
    5. 计算T在{,,…,}和{Y 1 i X 2 i X k i X1,Y2,…,Y}上的投影(,,…,)和(,,…,); k in− 1 i x 2 i x k i x 1 i y 2 i y k in y
    6. 计算φ; ),...,,( 21k xxx N=),...,,( 21k iii xxx
    7. 将(,,,…,)插入关系R ),...,,( 21k xxx N 1 i y 2 i y k in y 2 ,将)插入关系R k iii xxx,...,,( 21 ),...,,( 21k xxx N1.
    显然,算法Splitting_Compression仅需要扫描一遍关系R.
    定理3. R=Join(R1,R2),其中R1=R(,…,,φ),R 1 i X 2 i X k i X2=R(φ,Y1,Y2,…,Y). k in−
    证明:根据小值域属性组的定义和拆分压缩算法,直接验证R⊆Join(R1,R2)和R⊇Join(R1,R2)即可. □
                  6 基于压缩方法的查询处理
     
    拆分压缩后,对原关系R的查询变成了对关系R1和R2 的查询,这涉及到Join操作.完成此查询有两种方法:
    方法1. 直接在上述两个关系上进行连接操作.
    方法2. 按照下面的3个步骤进行:(1) 将原查询q分解为在关系R1上的查询q1和在关系R2上的查询q2;
    (2) 分别执行查询q1和q2;(3) 将由(2)得到的结果执行以φ为连接属性的自然连接,得到最终结果.
    数据库的查询优化器对这两种方法的代价进行比较,选择代价较小的方法进行操作.另外,还可以在φ上建立索引以提高Join操作的效率.
    我们将在另文中详细讨论拆分压缩后的关系上的查询优化与处理方法.
                  7 实验结果
     
    我们实现了小值域属性组的提取算法和海量关系的压缩算法,下面是我们的实验结果.实验运行于Linux6.2平台上的Oracle数据库,服务器是配置为PIV2.0GHz、内存256Mb的PC机.实验数据采用TPC-H生成的4G的数据量.压缩的关系是TPC-H中的LINEITEM关系,因为该关系的数据量占整个数据库数据量的约80%,其中包含30 007 486条记录.实验主要包含以下3方面的内容.
    第1组实验研究小值域属性组识别算法中不同的冗余度下限对算法输出结果的影响.实验中,多次在关系

    212 Journal of Software 软件学报 2005,16(2)
    LINEITEM上运行算法Recon-greedy,每次设置不同的冗余度下限.表1给出了实验结果.表中前3列分别给出了列名、各列值域的大小和各列的存储空间大小.表的后3列中为1的单元分别给出了冗余度下限分别为0.3,0.5和0.7时算法提取的SRAC中包含的属性.当1−α=0.3时,SRAC上的不同取值的数量是7 103 769.当1−α=0.5或0.4时,SRAC上的不同取值的数量是10 032 094.此外,当向这个0.5SRAC添加任意其他属性时,冗余度都在0.2以下.因此,适于SRAC识别算法的冗余度下限的合理的范围是[0.4,0.6].因此,在后面的实验中,始终设置冗余度的下限为0.5.
    Table 1 The identification of SRAC
    1 小值域属性组的识别
    Attribute name
    Range size of attribute
    Storage space of attribute
    Selected attributes by algorithm
    α=0.5
    α=0.3
    α=0.7
    Orderkey
    7 500 000
    21
    0
    0
    0
    Partkey
    5 960 934
    21
    0
    0
    0
    Suppkey
    300 000
    21
    0
    0
    0
    Linenumber
    7
    38
    1
    1
    1
    Quantity
    50
    21
    1
    0
    1
    Extendedprice
    2 093 773
    21
    0
    0
    0
    Discount
    11
    21
    1
    1
    1
    Tax
    9
    21
    0
    0
    0
    Returnflag
    3
    1
    1
    0
    1
    Linestatus
    2
    1
    1
    0
    1
    Shipdate
    2 526
    7
    1
    1
    1
    Commitdate
    2 466
    7
    0
    0
    0
    Reciptdate
    2 555
    7
    0
    0
    0
    Shipinstruct
    4
    25
    1
    1
    1
    Shipmode
    7
    10
    1
    1
    1
    Commit
    11 466 069
    44
    0
    0
    0
     
    第2组实验是两个SRAC识别算法性能的比较.置冗余度下限为0.5,然后分别执行算法Recon-greedy和Recon-gen.图1给出了两种算法识别的SRAC时属性个数随扫描数据库的遍数的变化情况.两条曲线基本呈阶梯状变化,这是由于,在遗传算法中要等到每一代种群处理完之后才可能引起频繁属性的个数的变化,而贪心算法中每次循环完成后才引起小值域属性组的一次扩充.其次,在得到SRAC的过程中,遗传算法的收敛速度较贪心算法快很多,这主要是因为遗传算法在连续两代种群的变化过程中可能向SRAC中引入多个属性,且淘汰机制的引入使得种群规模逐渐减小.最后,两种算法得出的SRAC之间没有严格的包含关系.
    Fig.1 The comparison of SRAC identification algorithms
    图1 小值域属性组识别算法的比较
    第3组实验研究拆分压缩对数据库性能的影响.设置冗余度上限为0.5,由算法Recon-gen得到一个0.5小值域属性组,它包含Linenumber,quantity,discount,shipdate,shipinstruct,shipmode等6个属性,由此按照第5节中的方法将关系拆分成两种关系,压缩掉的空间是原表所用空间的21%.然后,从TPC-H的查询中挑选了8个sql语句在压缩后的数据库中执行,结果见表2.第1列给出了sql语句的编号;第2列是相应语句在未压缩的数据库中的执行时间;第3、第4列是相应语句在压缩数据库中的执行时间,两列的区别为是否使用了新增属性上的索引.注意,第8个sql语句是一个嵌套的sql语句,且内层sql语句的select分句中出现了表达式l_extendedprice∗(1−l_discount)−ps_supplycost∗l_quantity,这个表达式中的属性被拆分到两种关系中,而查询处
    理时未能将表达式分解成两种关系上的子表达式,这导致操作时间的增加.
    Table 2 The performance of the compressed database
    2 压缩数据库的性能
    Query
    Original relation
    Compressed relation without new index
    Compressed relation with new index
    sql1
    155.533
    90.457
    87.364
    sql2
    158.157
    130.115
    132.158
    sql3
    145.331
    180.627
    160.151
    sql4
    281.164
    177.572
    160.771
    sql5
    223.532
    108.787
    106.844
    sql6
    667.95
    878.063
    424.218
    sql7
    1 459.428
    1 083.628
    1 060.685
    sql8
    5 427.895
    6 194.844
    5 947.602
     
    此外,文献[21]中也讨论了LINEITEM关系的压缩.在压缩比方面,Oracle的压缩方法的压缩比为38%.但是,Oracle的压缩方法本质上是将字典压缩方法整合到数据库的物理层实现上,故拆分压缩后的海量关系仍然可以用Oracle的压缩方法进一步压缩.从数据库整体性能上来看,Oracle的压缩方法使得数据库整体性能提高了约10%.如果将拆分压缩后的关系用Oracle的压缩方法作进一步压缩,压缩比和数据库整体性能均有可能进一步提高.目前,Oracle的这种压缩方法还不可得,也很难从底层直接实现,因此,关于这两种压缩方法的结合还无法进行讨论.
                  8 结 论
     
    本文根据海量关系中经常出现小值域属性组这一特点提出了拆分压缩技术.本文给出了两种在海量关系中识别小值域属性组合的算法,实验表明,算法中使用的冗余度下限的合理范围应该在0.4~0.6之间.实验结果表明,拆分压缩技术可以取得较好的压缩效果,并能够提高数据库查询处理的性能.
    References :
      [1] Margritis D, Faloutsos C, Thrun S. Netcube: A scalable tool for fast data mining and compression. In: Apers PMG, ed. Proc. of the 27th Int’l Conf. on Very Large Data Bases. Mumbai: Morgan Kaufmann Publishers, Inc, 2001. 311−320.
      [2] Gao H, Li JZ. Cube algorithms for very large compressed data warehouse. Journal of Software, 2001,12(6): 830~839 (in Chinese with English abstract).
      [3] Westmann T, Kossmann D. The implementation and performance of compressed database. ACM SIGMOD Record, 2000,29(3): 55−67.
      [4] Chen ZY, Gehrke J, Korn F. Query optimization in compressed database systems. In: Sellis T, ed. Proc. of the ACM SIGMOD Int’l Conf. on the Management of Data. New York: ACM Press, 2001. 271−282.
      [5] Ray G, Harisa JR, Seshadri S. Database compression: A performance enhancement tool. In: Chaudhuri S, Deshpande A, Krishnamurthy R, eds. Proc. of the Conf. on Management of Data. India: Tata McGraw-Hill, 1995. 106−125.
      [6] Poess M, Potapov D. Data compression in oracle. In: Freytag JC, Lockemann PC, eds. Proc. of the 29th Int’l Conf. on Very Large Data Bases. Mumbai: Morgan Kaufmann Publishers, Inc, 2003. 937−947.
      [7] Cormack GC. Data compression on a database system. Communications of the ACM, 1985,28(12):1336−1342.
      [8] Westmann T, Kossmann D. The implementation and performance of compressed database. ACM SIGMOD Record, 2000,29(3): 55−67.
      [9] O’Connell SJ, Winterbottom N. Performing joins without decompression in a compressed database system. ACM SIGMOD Record, 2003,32(1):55−67.
      [10] Berchtold S. Independent quantization: An index compression technique for high dimensional data space. In: Proc. of the 16th Int’l Conf. on Data Engineering. New Orleans: IEEE Computer Science Society Press, 2000. 577−588.
      [11] Antoshenkov G, Lomet D, Murry J. Order preserving string compression. In: Su YW, ed. Proc. of the 12th Int’l Conf. on Data Engineering. New Orleans: IEEE Computer Science Society Press, 1996. 655−663.
      [12] Jagadish HV, Ng RT, Ooi BC, Tung AKH. ItCompress: An iterative semantic compression algorithm. In: Su YW, ed. Proc. of the 16th Int’l Conf. on Data Engineering. New Orleans: IEEE Computer Science Society Press, 2004. 646−657.

    214 Journal of Software 软件学报 2005,16(2)
      [13] NG WK, Ravishhankar CV. Relational database compression using augmented vector quantization. In: Yu PS, ed. Proc. of the 16th Int’l Conf. on Data Engineering. New Orleans: IEEE Computer Science Society Press, 1995. 540−549.
      [14] Li JZ, Rotem D, Srivastava J. Aggregation algorithms for very large compressed data warehouses. In: Atkinson MP, Orlowska ME, eds. Proc. of the 29th Int’l Conf. on Very Large Data Bases. Mumbai: Morgan Kaufmann Publishers, Inc, 1999. 651−662.
      [15] Chen ZY. Building compressed database system [Ph.D. Thesis]. New York: Connell University, 2002.
     
    附中文参考文献:
    [2] 高宏,李建中.超大型压缩数据仓库上的CUBE算示.软件学报,2001,12(6):830−839.
    展开全文
  • 实时数据库中的数据压缩技术

    千次阅读 2016-05-25 18:31:28
    实时数据库中的数据压缩技术 标签: 数据库算法磁盘网络图形工作 2009-09-21 11:22 2715人阅读 评论(0) 收藏 举报  分类:   实时数据库(4)  版权声明:本文为博主原创文章,未经博主允许不得转载...

    http://blog.csdn.net/gjack/article/details/4575380

    标签: 数据库算法磁盘网络图形工作
      2715人阅读  评论(0)  收藏  举报
      分类:
     

    实时数据库中的数据压缩技术很高深很神秘。 转(bbs.51cto.com)
    现在的数据压缩理论和技术已经很成熟,大家可以看看我转摘的博文《数据压缩技术简史》,该文章浅显易懂,是一篇很好的关于数据压缩的科普文章。
    在不同的应用领域,又可以针对不同的数据应用特征,引用不同的数据压缩技术,比如,图形处理领域的JEPG压缩技术,声音处理中的MP3压缩技术等。在流程工业行业中,工业实时数据也有一定的变化规律,可以针对这些规律,研究特定的数据压缩算法。
    下面是工业实时数据的一些特征:

    工业实时数据的数据变化具有一定波形规律; 
    工业实时数据中只有一小部分测点的值经常发生改变; 
    工业实时数据中很多测点的数值都具有慢变化的特征; 
    数值变化与时间变化具有共同变化特性; 
    用户在一定范围内,能够允许数据的精度损失; 
    在工业应用领域中,常用的压缩算法分为三类:

    无损压缩; 
    有损压缩; 
    二级压缩; 
    其中,无损压缩一般以通用压缩理论为基础,采取哈佛曼算法等经典的压缩算法;而有损压缩而更多地考虑了工业实时数据的特征,而采取的一些特殊舍点算法;二级压缩技术,则是同时利用了这两种数据压缩技术。
    实时数据库的无损压缩以通用压缩理论为基础,随便找一本大学教材就能看懂,在此不再多说。
    目前比较著名的有损压缩算法,有PI中使用的旋转门压缩算法,IH中使用的死区压缩算法,以及一些变通压缩算法(如在旋转门算法基础上改用二次均方差作为偏差比较,以提高数据还原精度),这些算法原理都比较简单。网上有很多相关的文章,我在前几篇文章中提到的变化压缩算法,是死区压缩算法的简化变种,而liyaoer123同学在他的博客上帖出了osisoft关于旋转门压缩的技术文章,大家有兴趣可以去看看。
    总而言之,实时数据库的压缩算法真的不难理解,只是实时数据库重多技术中的一种而已。
    2.只要搞清楚数据压缩算法,就能编写好的实时数据库了。
    这个问题要从两方面来分析。
    首先要说明,数据压缩只是实时数据库中一个技术点,这个技术点相对于实时数据库其它技术点而言,难度和工作量是非常小的,我在《实时数据库的理论与技术》中,列出了实时数据库需关心的技术点,大家可以看看。只搞清数据压缩算法,是不能编写良好的实时数据库的。
    另一个方面,只从数据压缩这个角度来看,只考虑算法也是不行的。
    在实时数据库的数据压缩模块中,除了要考虑压缩算法之外,还要考虑以下内容:

    变量ID、时间戳、质量戳、值四个字段在压缩算法中的数据组织,包括逻辑组织和空间组织; 
    压缩算法与内存缓冲区的配合; 
    压缩算法与磁盘文件的配合; 
    特殊情况的数据处理,如,启动、停止、备份、恢复等时的数据压缩状态。 
    3.实时数据库中,数据压缩的压缩率越高越好。
    刚才提到,实时数据库中的数据压缩算法都是非常简单,这是由实时数据库的应用特点决定的。
    要考虑一个实时数据库的数据压缩技术技术,需要从以下几方面考虑:

    数据压缩率; 
    压缩数据的检索和定位速度; 
    数据压缩时间; 
    数据解压时间; 
    压缩数据在内存和磁盘的组织结构,以便更方便地利用内存和磁盘的特性; 
    数据解压后的还原精度; 
    数据压缩率只是其中一个指标,实时数据库追求的是综合性能指标,不能只看某一项指标。
    从某个角度而言,在实时数据库的应用中,数据的压缩和解压时间的指标,要优先于数据压缩率指标。但是,在设计良好的系统中,这两个指标之间并不矛盾。
    4.无损压缩比有损压缩要好
    在两个洋品牌PI和eDNA之间,经常会就无损压缩和有损压缩哪个更好这个问题产生争执。
    基本上,在此争执中,eDNA的无损压缩处于攻势,而PI则见招折招处处守势。总的来说,eDNA的市场宣传做得很不错,很多用户都是这样评价:eDNA比PI相比有很多优点,它采用了无损压缩技术,还有......,而且,它的价格比PI便宜多了。
    客观地讲,无损压缩有其好处,它在某些方面保证了数据的精度,但是,这并不能说,无损压缩一定比有损压缩好。
    采用无损压缩算法的实时数据库厂家,不能回避以下两个问题:
    采用无损压缩算法的压缩率比采用有损压缩算法要低得多,针对工业实时数据的特征信息提取的无损压缩,是不可能达到10:1的。
    采用无损压缩算法的实时数据库,单机总处理点数会存在性能瓶颈,以目前主流的计算机而言,采用无损压缩算法的实时数据库,平均只能处理2万左右的历史点。
    另外,无损压缩所宣称的100%保持数据不丢失,只是一句话宣传词,在计算机上处理工业实时数据,本身就存在大量的数据信息丢失:

    数据采集传感器存在采集误差; 
    数据采集是实时数据趋势变化的采样和数字化的过程,采集周期之间的特征波型已经丢失; 
    计算机处理和网络传输造成的延时和不确定,也会造成采集波型的失真; 
    传感器和计算机的数据类型字节限制,也会造成数据的失真。 
    在存在多处无法控制的失真环节的情况下,只强调保存数据的完全不失真,是没有意义的,只是商务宣传的需要,只要是数字化和计算机化处理,所有的数据就是近似的处理过程。
    有人会说,这也失真、那也失真,还处理个屁呀。这其实是一种处女情结,是在无意义地追求某个特定的指标而不考虑系统整体性能。如果实时数据库在采用无损压缩的同时,还能保证很快的解压缩速度和较高的压缩率,当然无可厚非,但目前的理论和技术条件下,这些指标是矛盾的。而采取有损压缩技术,是在不影响整体精度情况下的性能指标的综合平衡。
    5.实时数据库中,数据压缩不重要,要不要数据压缩没关系。
    关于这一论点,有两种不同的观点。
    第一种观点认为,现在的计算机硬盘很便宜了,磁盘容量不够,大不了多买几块磁盘。
    第二种观点认为,实时数据库的重点是上层功能和应用,在工业应用中,数据压缩费力又不讨好,还不如将精力放在其它功能上。
    这两种观点都不正确,实时数据库的市场存在意义,是因为现在的其它数据库产品,不能地处理大量工业实时和历史数据。这里说不能处理,包括处理速度和磁盘容量。
    在我的文章《实时数据库历史数据容量的计算方法》中计算得出,用关系数据库保存10000个每秒钟变化一次的双精度数,同时建立一个索引,保存一年需要磁盘空间为:12922G,而用实时数据库保存,则只需103G,大家可以换算一下,12922G,需要多少块磁盘?
    磁盘容量只是问题的一个方面,另一方面,数据的高压缩率意味着整个系统的数据处理速度更快,这体现在三个方面:高压缩率的数据,占用磁盘空间小,将数据从磁盘读入内存的速度快,网络传输的速度快,数据在内存中占用的空间小。而这三个因素,是实时数据库提高系统整体运行速度很重要的几个因素。
    一个良好的实时数据库,必须要处理好实时压缩问题,只有处理好数据压缩问题,才能使系统的整体性能达到某个可用性指标。
    以下有一个对是否选用实时数据库和数据压缩技术的简单判断:

    关系数据库只能处理5000点每秒变化的工业实时数据,在此范围内,可以不考虑选用实时数据库。 
    在5000点至10000点的系统内,需要抛开关系数据库,重新设计自己的数据存贮系统,但是,在这个领域,是不太需要考虑数据压缩技术的。 
    当系统的历史点数在10000点以上时,必须要考虑数据压缩技术和专门的实时数据库了。 
    很多朋友告诉我,他们的系统不采用数据压缩技术,他们也不关心数据压缩技术,他们认为,良好的上层应用软件比数据压缩更重要。我要对他们说:不同的行业,不同的系统规模,对实时数据库的性能指标要求是不一样的。实时数据库系统是一个综合性的应用系统,设计良好的底层模块是其它模块良好运行的基础,数据压缩技术与其它数据库技术一起,对整个系统的运行提供了很底层但很重要的环境,大型实时数据库系统中,数据压缩技术是必须考虑的,另一方面,实时数据库中,数据压缩技术只是实时数据库系统中一个重要的技术点,但不是全部。

    展开全文
  • 数据库MySQL详解

    万次阅读 多人点赞 2018-07-24 20:03:47
    什么是数据库管理系统 数据库管理系统(DataBase Management System,DBMS):指一种操作和管理数据库的大型软件,用于建立、使用和维护数据库对数据库进行统一管理和控制,以保证数据库的安全性和完整性。...
  • 十分钟看懂时序数据库(III)- 压缩

    千次阅读 2017-05-27 15:20:55
    物联网邻域近期如火如荼,互联网和传统公司争相布局物联网。作为物联网邻域数据存储的首选时序数据库也越来越多进入人们的视野,而早...压缩对于时序数据库是至关重要的。因为时序数据库面对的物联网场景每天都会产...
  • 数据库

    千次阅读 2017-03-25 18:08:20
    关系完整性是为保证数据库中数据的正确性和相容性,关系模型提出的某种约束条件或规则。完整性包括: 1、域完整性: 域完整性是保证数据库字段取值的合理性。包括限制类型(数据类型),格式(通过检查约束和规则),...
  • 数据库 - 数据库系统结构

    千次阅读 2015-05-03 12:47:08
    数据库系统结构从数据库管理系统角度看,数据库系统通常采用三级模式结构,是数据库系统内部的系统结构 从数据库最终用户角度看(数据库系统外部的体系结构) ,数据库系统的结构分为: 单用户结构 分布式结构 ...
  • 1.实时数据库中的数据压缩技术很高深很神秘?  现在的数据压缩理论和技术已经很成熟,在不同的应用领域,又可以针对不同的数据应用特征,引用不同的数据压缩技术,比如,图形处理领域的JEPG压缩技术,声音处理中的...
  • ORACLE数据库的逻辑备份分为三种模式:表备份、用户备份和完全备份  1.表模式 备份某个用户模式下指定的对象(表)。业务数据库通常采用这种备份方式。 若备份到本地文件,使用如下命令: exp icdmain/icd rows...
  • nosql数据库与内存数据库

    千次阅读 2015-09-29 11:27:45
    1. nosql NoSQL = Not Only SQL,泛指非关系型的数据库。NoSQL数据库的产生就是为了解决大规模数据集合多重数据种类带来的挑战,尤其是大数据应用难题。NoSQL数据库没有标准的查询语言...3、对数据库性能要求较高; 4
  • 数据库原理之数据库概述(下)

    千次阅读 2021-03-31 21:36:48
    文章目录数据库原理之数据库概述(下)数据库系统结构数据库系统模式的概念数据库系统的三级模式结构模式(Schema)外模式...从数据库最终用户角度看(数据库系统外部的体系结构),数据库系统的结构分为: 单用户
  • MySQL数据库

    千次阅读 2019-11-22 17:34:58
    数据库作为程序中数据的主要载体,在整个项目中扮演着重要的角色。PHP自身可以与大多数数据库进行连接,但MySQL数据库树开源界所公认的与PHP结合最好的数据库,它具有安全、跨平台、体积小和高效等特点,可谓PHP的...
  • MySQL数据库引擎

    万次阅读 2016-02-26 11:25:07
    经常用MySQL数据库,但是,你在用的时候注意过没有,数据库的存储引擎,可能有注意但是并不清楚什么意思,可能根本没注意过这个问题,使用了默认的数据库引擎,当然我之前属于后者,后来成了前者,然后就有了这篇...
  • Oracle数据库数据的导入导出imp/exp就相当与oracle数据还原与备份 假定: 将数据库orcl导出,用户名:test,密码:test 一. 导出文件:通过exp导出 1. 用户模式: 导出用户所有对象以及对象中的数据 将数据库中...
  • 数据库中间件

    千次阅读 2017-12-11 23:52:49
    这里主要介绍互联网行业内有关数据库的相关中间件。数据库相关平台主要解决以下三个方面的问题: 为海量前台数据提供高性能、大容量、高可用性的访问为数据变更的消费提供准实时的保障高效的异地数据同步 应用层...
  • MySQL数据库存储引擎与数据库优化

    千次阅读 2016-06-26 21:09:02
    事务(包含一连串的操作,事务(Transaction)是一个对数据库执行工作单元)是为了保护数据的完整性。几个过程作为整体即事务 每个过程出现错误都恢复到原来的数据 1. 原子性 (Atomicity):确保工作单位内的...
  • 实时数据库

    千次阅读 2015-09-28 23:23:16
    公司要做一个自动控制流水线系统,查阅了不少资料,考虑用实时数据库+关系数据库来实现。先说说概念。 一、概念 实时数据库系统是开发实时控制系统、数据采集系统、CIMS系统等的支撑软件。在流程行业中,大量使用...
  • 数据库切片

    千次阅读 2018-05-02 13:28:38
    一、 概述 随着业务的扩大,数据量呈...数据的切分,根据切分规则的类型,可以分为两种切分模式。一种是按照不同的表来切分到不同的数据库,这种称为垂直切分或纵向切分。另一种是根据表中数据的逻辑关系,将同一...
  • 时序数据库

    千次阅读 2019-05-31 18:15:33
    时序数据库(Time Series Database)是用于存储和管理时间序列数据的专业化数据库,为时间序列数据提供高性能读写和强计算能力的分布式云端数据库服务。时序数据库特别适用于物联网设备监控和互联网业务监控场景。 ...
  • 关系数据库还是NoSQL数据库

    千次阅读 2015-08-10 14:51:47
    原文地址:...在过去,我们只需要学习和使用一种数据库技术,就能做几乎所有的数据库应用开发。因为成熟稳定的关系数据库产品并不是很多,而供你选择的免费版本就更加少
  •  说到非关系型数据库,就要简单的介绍一下关系型数据库,是建立在关系模型基础上的数据库,借助于集合代数等数学概念和方法来处理数据库中的数据,我们平常使用的数据库,像MySQL,Oracle,S...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 83,912
精华内容 33,564
关键字:

对数据库的压缩分为