（计算机软件与理论专业论文）冗余数据库设计分析.pdf

冗余数据库设计分析 ( 计算机软件与理论专业) 硕士生：温爱军 指导教师：倪德明副教授 摘要 关系数据库中的数据冗余会导致重复存贮、插入异常、修改异常和 删除异常等问题。数据库的冗余分物理屠面的冗余和逻辑层面的冗佘两 大类。逻辑层瑟鲍冗余主要包括冗佘表、冗余记泶、冗余字段、属性醢 的重复、索引和数据字典的冗余等。数据库设计时如违背了e e c o d d 的 信息原则，造成波的含义重叠，就会产生数据冗余。传统关系数据库设计 璜论利用规范亿去除和避免数据冗余。然而，冗余数据的存在也有其保 谨数据安全、提高牲能等方龋豹好处。 g a r c i a - m o l i n a 和d 。u l l m a n 等人建立的i o 代价模型主要用于数据 席查询求解的代价分析对该模型进行扩充，把对数据库各种操作的使 用频度作为参数引入，可以建立较全面的对数据库资源歼销估算的代价 模型。剥瘸该代份模型哥班分板各种常见数数据冗余对于不嗣数据库应 用的资源开销的影响。代价模型主要仍以磁盘块的i o 数作为代价尺度， 对数据库资源开销估簿时主要考虑查询和厦新代价的影响。分布式数据 库的资源开销还要包括传输代价等。引入冗余设计带来了冗余数据更新 和一致性维护豹闰题。 本论文先根据冗余的定义，对各种冗余做了归纳分类，说明了冗余 摘要 导致的问题，并从c o d d 经典的关系数据库规范化理论出发，分析了规 范化理论是如何消除或减少冗余的。接着，从数据库应用的现实发展分 类出发，阐述了冗余数据的存在是现实数据库应用特别是管理决策类应 用发展带来的必然结果，归纳出采取必要冗余设计的积极意义，并根据 在银行现行信息系统中利用代价模型分析优化设计的经验和实例，总结 出了实践中合理利用冗余设计提高数据库运行性能和运行安全的原则 与方法。 关键词：冗余数据库设计资源开销代价模型性能优化 n a n a l y s i so f r e d u n d a n td a t a b a s ed e s i g n m a j o r ：s o f t w a r ea n dt h e o r y n a m e ：w e na i j u n s u p e r v i s o r ：p r o f e s s o rn id e r n i n g a b s t r a c t r e d u n d a n c yi nr e l a t i o n a ld a t a b a s e r r d b ) m a yr e s u l ti ns o m ep r o b l e m s s u c ha sr e p e t i t i o no f s t o r a g e ，i n s e r ta n o m a l i e s ，u p d a t ea n o m a l i e sa n dd e l e t e a n o m a l i e s r e d u n d a n c yi nr d b i sc l a s s i f i e di n t ot w op a r t s ：p h y s i c a l r e d u n d a n c ya n dl o g i c a lr e d u n d a n c y l o g i c a lr e d u n d a n c ym o s t l yi n c l u d e s r e d u n d a n tt a b l e s ，r e c o r d s ，f i e l d s ，a t t r i b u t ev a l u e s ，i n d e x e s ，d d ( d a t a d i c t i o n a r y ) ，a n ds oo n i fs o m e o n ed i s o b e yt h ei n f o r m a t i o nr u l eo f e f c o d d w h i l ed e s i g n i n gt h er e l a t i o n a ld a t a b a s e i tm a yc a u s eo v e r l a p so f t h et a b l e m e a n i n g sa n dg e n e r a t et h er e d l m d a n c y c l a s s i c a lt h e o r yo f r d bd e s i g n m i l i z e sn o r m a l i z a t i o nt or e m o v ea n da v o i dt h er e d u n d a n c y t h ee x i s t e n c eo f r e d u n d a n c ya l s ob r i n g ss o m eb e n e f i t s ，h o w e v e r ，s u c ha sg u a r a n t e e dd a t a s e c u r i t ya n dp e r f o r m a n c ei m p r o v e m e n t t h ei oc o s tm o d e lb u i l t - u pb yg a r c i a - m o l i n a ，d u l l m a na n do t h e r si s m o s t l yu s e df o rt h ec o s ta n a l y s i sa b o u tg e t f i n ga n s w e r 丘o md a t a b a s eq u e r y e x t e n d i n gt h i s m o d e l t h r o u g ha d d i n gs o m ep a r a m e t e r sm e a n i n gt h e f i e q u e n c yo f a l lk i n d so f d a t a b a s e l o p e r a t i o n ，w ec a r lb u i l du pt h er e l a t i v ea l l a r o u n d c o s tm o d e la b o u tt h ec o s t e v a l u a t i o no fd a t a b a s er e s o u r c e s b yu s i n gt h i sm o d e l ，w ec a r ta n a l y z et h e i n f l u e n c eo fr e s o u r c e sc o s t i n ga b o u td i f f e r e n td a t a b a s ea p p l i c a t i o n sw h i c h t a k e nb ya l lk i n d so ff a m i l i a rr e d u n d a n c y t h ei 0c o u n t so fd i s kb l o c ka r e s t i l lm o s t l yu s e da sc o s ts c a l ei nt h i sm o d e l t h ei n f l u e n c ef r o mc o s to f q u e r ya n du p d a t ei sc o n s i d e r e dm o s t l yw h e ne v a l u a t i n gt h ec o s to f d a t a b a s e r e s o u r c e s t h er e s o u r c ec o s to fd i s t r i b u t e dd a t a b a s e a l s oi n c l u d e st h e t r a n s p o r tc o s t i n g ，e t c t h i sr e d u n d a n td e i g nr a i s e st h en e w i s s u e sa b o u t r e d u n d a n td a t au p d a t ea n dc o n s i s t e n c ym a i n t e n a n c e 。 a c c o r d i n gt o t h ee x p e r i e n c e sa n de x a m p l e sw h i c hc a m ef r o mt h e o p t i m i z a t i o na n a l y s i sd e s i g nb yu s i n gt h ec o s tm o d e li n c u r r e n tb a n k i n g i n f o r m a t i o ns y s t e m ，w es u m m a r i z e dt h ep r i n c i p l e sa n dm e t h o d sa b o u th o w t ou t i l i z er e d u n d a n td e s i g ni nr e a s o nt oi m p r o v et h e d a t a b a s er u n n i n g p e r f o r m a n c ea n ds e c u r i t yi np r a c t i c e 。 k e y w o r d s ：r e d u n d a n c y ；d a t a b a s ed e s i g n ；c o s te v a l u a t i o no fr e s o u r c e s ；c o s tm o d e l ； p e r f o r m a n c eo p t i m i z i n g 1 1 数据冗余的定义以及导致的问题 引言 关系数据库中的数据冗余主要是指关系数据库中同一信息数据的 重复存贮。传统观点认为，数据冗余浪费了宝贵的存储等资源，并带来 维护数据一致性等方面额外的开销，应尽量减少。然而，冗余数据的存 在也有其保证数据安全、提高性能等方面的好处。在存储介质等硬件越 来越便宜的今天，我们需要重新评估分析数据库中的冗余问题。 本论文第一章先根据冗余的定义，对各种冗余做了归纳分类，说明 了冗余导致的问题，并从c o d d 经典的关系数据库规范化理论出发，分 析了规范化理论是如何消除或减少冗余的。 第二章我们从数据库应用的现实发展分类出发，阐述了冗余数据的 存在是现实数据库应用特别是管理决策类应用发展带来的必然结果，归 纳出采取必要冗余设计的积极意义。 第三章是本论文研究工作的主要部分，我们依循g a r c i a m o l i n a 和 d u l l m a n 等人建立i 0 代价模型的思路，对该模型进行了扩充，建立了 较全面的对数据库资源开销估算的代价模型，并利用代价模型系统地分 析归纳了各种常见的数据冗余对于数据库资源开销的影响。对于分布式 数据库的资源开销也做了深入讨论，其中引用了郑振楣等的分布式传输 代价模型。此外，还讨论了引入冗余设计带来了冗余数据更新和一致性 维护问题。 第四章可看作论文的总结部分，我们根据前面章节的讨论总结出实 数据冗余的定义以及导致的问厦 践中合理利用冗余设计提高数据库运行性能和运行安全的原则、经验和 方法。 本论文中采魇的铡子都是作者表中嚣银行现幸亍信息系统应用中的 优化设计经验和应用实倒，部分例子为了叙述的方便徽了籀亿。 数据冗余的定义咀扭导致的问题第1 章关系数据库的数据 余与规范化殴计 第1 章关系数据库的数据冗余与规范化设计 1 1 数据冗余的定义以及导致的问题 定义1 】数据的冗余是稽在数据库中存储了同一信怠的多个拷贝。【1 1 数据冗余会导致重复存贮、插入异常( 特定的信息不能存人，除非 一些其他的信息已经存储在库中) 、修改异常( 所有的拷贝都要被修改) 和删除异常( 删除一些信息将导致其他一些信息的丢失) 等问题。 i 2 冗余的分类 根据数据瘁麴物理和逻辑构成两方西看，数据库妁冗余也可以分嚣 大类：即物理屡面盼冗余帮逻辑藩瑟的冗余。 1 2 i 物理层灏的冗余 物理层面的冗余主要包括数据库存储的硬件资源的冗余如各级存储 设备等的冗余。由于数据库的物理实现是逻辑实现的基础，物理层面的 冗余不但影响物理数据庠设计，也影响着逻辑数据库设计；而且，逻辑 层面的冗余最终也会反映在物理层面上，因此，本文也会讨论些涉及 物理存储的冗余问题；但是，对于数据库运行相关的其他物理资源的冗 余如处理机、嘲络等的冗余阔题( 涉及并行与分布数据库设计) ，本文 不详细讨论。 3 第1 章关系数据库的数据冗余与规范化设计 1 2 2 逻辑层面的冗余 从关系数据库的逻辑构成看，关系数据库由表、索引和数据字典等组 成，其表由属性定义的结构和元组( 记录) 组成 2 】，其属性值域有多种类型， 故关系数据库中的冗余有不同表现形式，主要包括表的重复( 冗余表) 、 元组的重复( 冗余记录) 、属性的重复( 冗余字段) 、属性值的重复掣3 1 ， 此外，索引和数据字典中也有冗余的情况。 冗余表、冗余记录是很常见的冗余，尤其在数据仓库中。冗余表有 一种特别的情况是仅表结构相同而表内数据不相同，例如分割转储的历 史数据表与当前数据表；还有一种是存放一些可以通过其他表中数据运 算出来的字段( 如统计数等) 的表；此外，处理复杂关系运算( 如嵌套 查询) 时引入的临时表也属这类。 属性的重复有不同表的属性重复和同一表内属性重复： ( 1 )不同表中属性重复常用来建立表之间联系；各表间的除主外 键外多余属性应当删除。 ( 2 ) 同一表内有相同属性内容的多个属性。若非数据安全检查的 需要，应删除之。 ( 3 )表内属性冗余有种特殊情况：可以通过其他属性内容计算出 来的属性字段如摘要数据。 属性值的重复按属性值域集合基的特点可以将其分为有限类和无限 类。 ( 1 )无限类属性值的重复。无限类属性值是指其属性值域集合的 基为无限大或者数据库记录数为同一数量级的属性值，如实数、整数、日 d 3c o d d 的信扈规则及茸推论 第1 章关系数据库的数据冗泉与规范化 殳计 期、各种编号。无限类属性值偶尔也可能重复，但这只是巧合，而并非数 据冗余。 ( 2 ) 有限类属性值的重复。有限类属性值是指其属性值域集合的 蕊小于数据库记录数至少一个数量级的属性值，如存款种类名，丽点名，货 币名等。 索引本身就是一种冗余，索引中存放冗余数据的情况包括基于函数 的索引( f u n c t i o n - b a s e d i n d e x ) 与索引组织袭( i n d e x o r g a n i z e dt a b l e ，l o t ) 。 数据字典冗余主要是在数据字典中定义冗余的矮等，例如：定义备 用日志文件等。此外，在数据仓库的元数据中的冗余也属于这类。 还有其他的冗余情况，如实体化视图。 1 3c o d d 的傣息规则及其推论 关系模型的羹基人e f + c o d d 具体地给如了全关系型妁关系系统应 遵循的十二条基本规则h 。其中的规则l 即信息规则是关系数据库设计 的基本准则。 c o d d 信息规则表述为：关系型d b m s 的所有信息都应在逻辑一级 上用唯一一种方法即表中的僮鼹式邈表示。 下面我们讨论c o d d 信息规则的一个藿要推论： 【定义2 】设a 和b 是任意两个基裳，分别县有楣关联的基袁谓词p a 和p b ，当且仅当构造基个r 行，使得p a ( r ) 和p b ( r ) 都是真的，则称a 和b 的含义蓬纛。 第1 章关系数据库的数据冗余与规范化设计1 3c o d d 的信息规则及其推论 推论( 数据库设计中的基本原则) 5 1 ：在一个给定的数据库中，任 意两个不同的基表不能有含义重叠。 例1 假定银行有一个统计客户存款的数据库d e p , 其中每个客户有 客户号( c n o ) 、姓名( c n a m e ) 、网点号( b n o ) $ h 存款( d e p o s i t ) 四列，用 两个基表d e p a 和d e p b 表示，这两个基表有相同的属性( c n o 、 c n a m e 、b n o 、d e p o s i t ) ，其含义分别为“d e p a 基表中只含有在行本 部b l 网点开户的客户行”和“d e p b 基表中含有不在b 1 网点开户的客 户或存款不低于1 0 0 0 0 的客户行”现在，要求将( c 2 ，李四，b 1 ，1 1 0 0 0 ) 行 插入到d e p 数据库中，问题是应该插入到哪一个基表中呢? 如将此行插 入到d e p b 基表中，而不是d e p a 基表中，则意味着客户李四不在b 1 网点 开户，这将与基表含义自相矛盾。对于这个数据库要解决这个矛盾，只能 将此行分别插入到d e p a 和d e p b 基表中。 在上面讨论的问题中，d e p a 和d e p a 两个基表，它们的基表谓词分 别为p a ：a n d ( b n o = b 1 ) a n d ，p b ：a n d ( b n o b 1 ) o rd e p o s i t p l 0 0 0 0a n d 。构造行( c 2 ，李四，b 1 ，l1 0 0 0 ) ，它既满足 p a ，又满足p b ，则说明d e p a 和d e p b 具有含义重叠。这个数据库设计是 不好的，导致了数据冗余；此外，如果在d e p a 基表中对此行进行更新操作， 那么也必须在d e p b 基表中对相应的行进行更新操作，否则将造成数据 的不一致性。口 以上实例，在数据库设计中，由于违背了e f c o d d 的信息原则，造成 表的含义重叠，从而产生了数据冗余。下面我们讨论传统关系数据库设计 理论是如何去除和避免数据冗余的。 三! 羹墨塑塑垦型至! ! 塑! 苎! 雯篓篓茎塑生塑垫望要塞量墨蔓些兰生 1 4 关系数据席规范化设计 数据库设计的个最基本的问题是怎样建立一个好的数据库模式。 关系数据库创始人c o d d 提出了“关系规范化”的理论“，用于指导对数 据库的设计。其基本思想是，每个关系( 或是数据库表) 都篱要在结梅 上满足一定的规范( 范式) ，根据现实世界存在的数据依赖进行关系模 式的规范化处理，从而褥到个好的数据库设计，达到减少冗余，提商 奄询效率的目的。因此，规范化是在关系型数据库中减少数据冗余的过 程。 现实世界存在豹数据依赖( 宠整惶约束) 露：函数依赖、多筐镶鼓、 连接依赖和包含依赖。 规范化理论把关系应满足的规范要求分为几级，满足最低要求的一 级嘲敝第一范式( 1 a 嚣) ，在第一范式的基础上提出了第二藏式( 2 a 弭) ，在 第二范式的基础上又提出了第三范式( 3 n f ) ，以后又提出了b c n f 范式， 4 n f ，5 n f 等。范式的等级越高，应满足的约束集条件也越严椿。规范 的每一级别都依赖于它的前一级剐，饲如若个关系模式满足2 n f ，则 一定满足1 n f 。 荔一范式( 1 n f ) ：在关系模式r 中的每一个具体关系r 中，如果每 个属性值都是不可冉分的最小数据单位，则称r 是第一瓤式的关系，记 为r 1 n f 。 第二范式( 2 n f ) ：如果关系模式r 邮、f ) o 所有非主属歉都完全函数 第1 章关系数据库的数据冗余与规范化设计14 关系数据库规范化设计 依赖于任意一个候选码，则称r 是第二范式的关系，记为r 2 n f 。 第三范式( 3 n f ) ：如果关系模式r ( u 、f ) 中的所有非主属性对任何候 选码都不传递依赖，则称r 是第三范式的关系，记为r 3 n f 。 b o y c e c o d d 范式( b c n f ) ：通常认为b c n f 是修正的第三范式，它比 3 n f 又进一步，就是如果在第三范式中，若每一个决定因素都包含码， 则该关系就是b c n f 。 一个关系所满足的范式是对它所具有的冗余度的一种度量。一个具 有冗余的关系可以通过对其进行分解来降低冗余度，或者用包含同样信 息但没有冗余的较小的关系来代替。规范化过程要保持分解是无损连接 ( 1 0 s s l e s s - j o i n ) 和依赖保持( p r e s e r v a t i o n ) 的。如果我们把仅仅 满足第一范式的关系分解为满足第二范式的几个关系，就可以消除关系 中的部分函数依赖，就不会有数据更新异常问题。第二范式中的关系也 有异常，是插入异常。要想从第二范式关系中消除异常，必须消除传递 依赖。3 n f 和b c n f 是在函数依赖的条件下对模式分解所能达到的分离程 度的测度。一个模式中的关系模式如果都属于b c n f ，那么在函数依赖的 范畴内就已经实现了彻底的分离，已消除了插入和删除异常。3 n f 的不 彻底性表现在可能存在主属性码对码的部分依赖和传递依赖。第四、第 五范式比b c n f 的要求要严格，它们消除了由多值依赖和连接依赖引起 的冗余。此外还有被称为完美范式的域一码范式( d k n f ) 。 例2 我们还是来看看银行客户的例子： a 如果要求一个客户一行，一个客户可在银行开办多种金融业务， 则下面的“客户”表就不满足1 n f ： 4 关系数据库规范化设计第1 章关系数摆库的数据冗采与规范化设计 c u s t o m e r ( c - n o ，c n a m e ，p r o d u c t n o ) 其中：c n o 为客户号，s - n a m e 为窖户姓名，p r o d u c t n o 为金 融产品( 业务类别) 号。因为一个客户可开办多种类另b 业务，所以对应 每个( c - n o ，c - n a m e ) ，p r o d u c t n o 可能有多个值，新以它不符合1 n f 。 规范化就蹩把它分成如下两个表：“客户”表和“客户产品”表， 则这两个表就都满足1 n f 了。 c u s t o m e r ( c - n o ，c 一 1 a m e ) c u s - - p r o d u c t ( c - n o , p r o d u c t n o ) b 。下磁的“客户产品”表，不符合2 n f 。 c u s - - p r o d u c t ( 二! ! ：2 1 1 9 女! 二q p r o d u c t n a m e ) 其中：p r o d u c t n a m e 为金融产晶名称。因为词表豹主码是：客 户号+ 产品号( c n o ，p r o d u c t n o ) ，j 主硝列p r o d u c t h a h e 依戆于组合 主码的一部分p r o d u c t n o ，所以它不符合2 n f 。 对该表规范化也是把它分解成两个表：“客户产品”表和“产 品信息”表，则它们就都满足2 n f 了。 c h s - - p r o d u c t ( c - n _ _ _ _ o q ，p r o d u c t n o ) p r o d u c t i n f o ( 2 1 q d 女! = ! ! ，p r o d u c t n a l l l e ) e 下面的“产品信息”表，不j 毒台3 n f 。 p r o d u c t i n f o ( p r o d u c t - n o ，p r o d u c t n a m e ， p d e p a r t m e n t n o 。p d e p a r t m e n t n a m e ) 其中：p d e p a r t m 6 nt n o 为该产品管理部门号，p d e p a r t m e n t n a m e 为该产品管璁部门名称。因为非主码列p d e p a r t m e n t n a m e 依赖于另一 第1 章关系数据库的数据冗余与规范化髓计 4 关系数捅库规范化设计 菲主码列p d e p a r t m e n t n o ，所以它不符合3 n f 。 其解决办法也是把它分解成两个表：“产品信息”表和“部门”表， 则它们就都满足3 n f 了。 p r o d u c t ( p r o d u c t - - n o ，p r o d u c t - - n a m e ，d e p a r t m e n t n o ) d e p a r t m e n t ( 监p a r t m e n t - n o ld e p a r t m e n t n a m e ) 口 从上面这个例子我们可以看到，规范翦的数据疼设计均存在j 薹：数据 冗余以及更新异常等问题，经过规范化去除和避免了冗余和冗佘带来的 更瓶异常等阉题。 经过关系数据库理论街始人c o d d 等一批学者的努力，数据库设计 已从第一代数据库系统的以经验为主的设计发展为以“关系规范化”理 论为指导的规范设计方法，形成了包括概念结构设计 逻辑缩构设 计 物理结构设计的模式。但是，由于规范化成3 n f 以上的范式的分 解并不总能保持依赖分解，而且如果经常发生对于原关系的查询需要对 分解所霉譬到的关系进行连接查询，鄂么分解所导致的性能损失可能很 大，这在实际应用中是不可接受的；在这种情况下，我们可能会选择保 留一定的冗余两不进行分解。我 将在后蕊详细讨论这个问题。 21 冗余数据对于不j 叫数据库应用的作用 第2 章冗泉设计的优点 第2 章冗余设计的优点 2 1 冗余数据对于不同数据库应用的作用 对于传统关系数据瘴o l t p 系统，我船总蹙按照应翻实俗来建立它 的模型，换言之，o l t p 系统是面向应用实体的。实体化关系模型是面向实 体，反映数据本来的关系，是将现实抽象成一张张数据表。冗余数据有 些是必需的，有些刚是无用酶。倒如，在银行中，一般都舂辩私( 个人储 蓄) 、对公( 企业储蓄) 、信用卡等多种业务系统，它们都是面向上述应用 实体的，所支持的交易类型箍单髓显固定。由于实慈的先羼等原因，这些 系统可能运行在不同的平台上，各系统之间的数据存在冗余，比如每个系 统中都会有客户的数据。在整合成一个逻辑系统的时候，这些冗余很多 都是必须消除的，餐也有些爨于安全、性黥、系统闯联系等纛因是要 保留的。 数据库应用在o l t p 业务系统发展完善后，随之而来的是大量的报 表统诗、管理类、决策类应用需求。在应用发糕的初期，用户一般是在 业务系统上面直接构建管理类、决策类应用。但是，这些管理类、决策 类数据库应用对数据库的资源开销与o l t p 系统有着显著不固，前者对 数据的查询操作频度远比后者简，而修改、删除操作的频度则甚低：后 者则相反，因此在o l t p 上构建的管理类、决策类应用对缀系统的性能 彩响蒸大，因扰数据痒应用发怒文了与o l t p 系统分离的0 l a p 和数掇 第2 锩冗余设| 卜的优点2i 冗余鼗据对于不同数据库应用的作用 仓库应用，这些分离出来的数据库实际上相对于原来o l l p 系统数据来 说趸冗余浆。 而o l a p 和数据仓库则一般按照主题( s u b j e c t ) 来建模，它是西向主 题的：是根据人类不同视角需要抽成张张数据表。冗余是面向主题数 据处理所必须，合理的冗余可以加快响应时间。例如，当针对银行建立 冀数据仓库应雳时，要把冬分离的生产系统中的数据转换到数据仓瘴中 来。从整个银行的角度来看，其数据模型不再狮向个别应用，冠是面向整 个银行的主题，比如客户、产品、渠道等。因此，各个生产系统中与客户、 产品、渠道等相关的信息将分别转换到数据仓库中相应的主题中，从而 在整个银行的韭务界蠢上提供“个一致的信息橇图。这时候大部分针对 不同视角的数据大多是存在冗余的。 分布式数据库为减少传输代价，常对关系进行划分( 分片存储) 和 复制。划分就是将关系分离成若干个小关系或者分片，每个分片( 替代 关系本身) 存储予不掏的场地。前面提到静对历史数据表分割转储就是 对表的水平划分。水平划分时，每个分片是原始关系所有数据行的子集 合：垂直划分时，每个分片是原始关系所有数据列的子集合。复制是分 布式数据席对关系或片在不同场地间的重复存储。因此，分布式数据库 中存在大量表冗佘。分片可班减少遥绩代价。复制其有灌加数据的可用 性和快速的查询处理双熏作用。 22 需要的冗余数据和它们带来的好处 第2 章冗余设计的优点 2 2 嚣要的冗余数据积它们带来的好处 关系数据库中为实现一些功能有些数据冗余是必需的。必需的数据 冗余主要用于以下用途： ( 1 ) 建立数据间联系需要，如两表间通过共同属性建立联系，这是必 需的数据冗余； ( 2 ) 数据安全需要，数据恢复，妇建立备份文件以备正式文件被破坏 时恢复、在冗余磁盘上定义冗余目志文件、r a i d 磁盘阵捌等。这种为 了数据安全的需要制作备份表也是必需的数据冗余。此外，冗余的数据 可以避免数据备份对联机数据库的影响，提高数据库持续可用性，如大 裂机厢的日立h d s 磁盘的f l a s hc o p y 功能，e m c 磁盘的s n a p s h o t 功能等。前面提到分布式数据库在不同场地的复制也有这种作用：由于 复制，当存储数据的某个场地出现故障时，我们可以农其他场地找到需 要的数据；目样地，摇果可以使用本地提供的远理数据的裂本，将能够 盟著减少因网络连接故障雨产生的访闯失效。 ( 3 )数据校验核奁，如设立数据棱验位可阻裣查数据在存贮、传输 等过程中的改变，如在通讯行业中有着广泛应用的t u r b o 编码的基础就 是在将要通过通道传输的数据中引入冗余数据以帮助从接收到的数据 中恢复原始数据，使得编码有助于实现接近香农极限的性“f l a ；r a i d 磁盘 阵列也是利用冗余实现数据校验核查的典型例子。同一表内因数据安全 检查的需要也可以放_ 墅的有媚唰属性内褰的多个斌性。 ( 4 )根据数据的不问缓织需求，为了数据使用的便剥，如数据仓库 为了查看数据的直观，使用数据的方便、商效，通常存储很多可道过其他 f j 菇2 章踅余设汁弛优点2 2 需要冗余数据和它# 带皋瓣好薤 字段或表间关联查询计算重新计算出来的字段或表。 f 5 )可提高性能和效率：联机攀务处理复杂，合理的冗余设计可以 达到提裔效率的目的。如，有限类属性值的重复实际上是由一对多或多 对多的关系引起的，即多表引用属性，有时可作为必需冗余不予处理，这 嚣不需程序就有较好的套看效果声瑟工作效率。又如，为了减少数据通讯 开销，分布式数据库的分片和在不同场地的复制使得可使用数据的本地 副本代替访问远程数据，能够加快查询的执行速度。 仅从冗余的定义来蕾，索弓| 也是一种冗余。索引是为了对数据的操 作方便和高效而引入的，从这个意义上讲，索引完全是为提高数据库性 爱露效率露引入的一群冗余。毫无疑润，适当黔索弓| 是必需鸵。 现实中还有很多利阁冗余提高效率的例子，我们将在下一章通过建 立数据库资源开销估算的代价模型具体分析讨论。 31 数据瘁整源野精估冀盼找衍模型 第3 翥冗金特况下数据痒资源韵开镑 篝分析 第3 章冗余情况下数据库赍源的开销计算分析 要计算数据库资源的开销，我们酋先要建立数据库资源开销估算的 代价模型和相关计算参数，然后利月j 模型参数估算并评价1 2 节提到的各 类冗余情况下数据库的性能的变化( 根据般评价标准，主要考虑通常 豹查询秘典型的更耨操作) 。 3 1 数据库资源开销估算的代徐模型 我 f 知道，使周第二级存储器是数据库管理系统的重要特性之一， 丽第二级存赭嚣几乎都是基于磁盘豹。数据库管理系统出自己管理磁撒 块。由于任何计算都在主存绒高速缓存中进行，有关磁盘我们所关心的 唯一问题是如何在磁盘与主存之间移动数据块。第二级存储器的速度比 典型的内存慢10 5 倍，在磁盘上读绒写一个块大约要花1o 30 毫秒 ( 0 01 o 。03 移) ，在这段时阅由，一台典型的捉器或许能执行1o o 万条指令。因此，通常情况下，读或写一个磁盘块所花的时间，决定 了对这个磁盘块的内窖进行无论什么样的操作所花费的总时间。 3 1 1 计算的i o 模理 下面我们看看g a r c i a m o l i n a 和d u l m a n 等人建立的i o 代价模型。 先定义计算的i o 模型的规则，即i t o 开销的主导地位： 定义3 计算的i o 模型的规购( i o ! 砰销熬主导避位) ：如暴一个块需 笙! 兰堡叁壤煞! 堂望蝥资遵! ! 篓磷计算分柝 3t 救援洋资源开销估算的代瓣模型 要在磁盘与主存之间移动，那么执行读或写所花费的时间或许要比用于 操纵主存中的数据所花费的时间长得多。这样，块访问( 读和翟) 次数 就是算法所需要的时间的近似值，而且应该被最小化。我们稿之为计算 的i o 模型的规则或i o 开销的主导地位。 倒3 假设我钔躬数据瘁有关系盛奄一个对元缱的查握请求，该元 组有一个确定的码值五。 正如我们所看到的，最好要在肚创建一个索引，能够被用于标识带 有码值功元组出现的磁盘块。而索弓 是否告诉我们这个元组出瑷在块 的什么位置通常并不重要。理由是在一个典型的实际系统中读一个4k b 的块大约螫花1 5 毫秒( 此数值的详细估葵参见。1 ) 。在1 5 毫秒内，一个 新式的处理器能执行成百万条指令。然而，一旦块是在主存中，即使采 用最笨的缘陛搜索，搜索码值锵仪执行成千条指令。因此在主存中执 行搜索酶陡船辩闻凑小予块访翊辩润麴1 ，可以有把握翘忽略。口 3 1 2 查询代价的度量 最终衡豢数据库设计好坏的标准蹩，d b m s 程通常的查询窝燕型的 更新操作上的性能【”，因此，我们对数据库资源歼销估算时主瑟考虑查 谗和更耨代价。 查询处理的代价可以通过该查询对各种资源的使用情况进行衡量， 资源包括磁盘存取、执行一个查询所用c p u 时间、在并行分布式数 据疼系统中的逶信开镶( 后蚕讨论) 。假定计算桃中没有其铯任务，查 询执行计划的中应时间( 即执行该计划所需时间) 则包含以上所有类型 3l 数据库瓷潍扦销估算的代价模型 第3 章冗泉情况下嚣据库资源鲍开镨计算分析 的代徐，阉葑雩也可作为查诲执行计翊代价的一个较爵的度量。 然而根据上节的讨论，在传统的集中式大型关系数据库系统中，磁 盘访问( 用从磁盘中传送的块数来度量) 通常是主要的代价，因为磁盘 存取比内存操作的速度慢得多。此外，c p u 速度的提升比磁盘速度提升 要快。这样，花费在磁盘存取上的时闯仍l 西楚整个查询执行时瓣中的主 要部分。并者与磁盘存取代价估计棚比，c p u 时橱的估汁相对较难。嘲 此，磁盘存取代价被认为是查询执行计划代价的一个合理度量。主要的 t ，u # i - 情况是在回答查询需要通过网络进行数据通信时，我们在后面讨论 分布式查询处瑗的代价。 为筠化磁盘存取f 价的计算，假定所有块传送的代馀相同。该假定 忽略由旋转延迟( 等待所需数据旋转到读写头下的时间延迟) 与搜索时 间( 将磁头移到所期望的磁道或柱面的时间) 所引起的差异。虽然这些 因素很重要，假在一个共享系统中它们是缀难估计的。因此，我们简单 地用磁盘块传送数作为实际代狳鲍一个度量。障j 在比较相同操作的算法时，我们假设任何操作符的操作对象都位于磁盘 上，但操作符的结果放在内存中。即我们忽略了将操作的最终结果写回 磁盘的代价。不管采用了什么查询执行计划，这个代价楚不交的，因诧， 忽略它劳不影响查陶计划豹选择。丽且，在许多废用中，结果根本不存 放到磁盘上，丽是打印或传送到某个格式化程序。于是，在输出上耗费 的磁盘i o 或者是零，或者依赖于某个未知的程序对数据所做的操作。 注洪于b o 代啦r 稹型+ 参考文献啦 6 】_ 一 9 均有叙述，有的以磁盘页的f o 数作为评估的代价尺度( 如文献 1 】) 电霄的以磁盘块昀l ，。数作为评倍的代静咒度f 翔文献 7 】、【s 】) ，奉质土没有莲承，奉文采用嚣毒t 羔立兰二坠! ：! 垫工塑塑蓬堑婆塑堑塑i ! ：簦坌篓 ! ：! 墼塑璧墼堡墅塑笪篓堕垡塑堡型 同样，形成一个查谗的部分操作符的结果通常也不写到磁盘上( 特别在 流水线设计中) 。我们所考虑的算法的代价缀大程度上取决予主存中缓 冲区的大小。最好的情形是所有的数据都能读入到缓冲区中，外存不必 再访问。最坏的情形是缓冲区只能容纳数目不多的数据块一大约每个 关系一块。当要进行代价估计时，通常假定是竣坏的情形。 3 1 3 衡莹代价豁参数 现在，让我们引入用来表达个操作符代价的参数。 我们需要一个参数采表达操作符使用的内存大小，还需要其他参数 来衡量它豹操作对象的大小。假设内存被分成缓冲区，缓冲区的大小与 磁盘块的大小相同。那么m 表示一个特定的操作符执行时可敬获得的 内存缓冲区的数目。记住，当估算一个操作符的代价时，我们不考虑产 生输出结果所用内存或磁盘i o 的代价，因而m 仅包含容纳输入和操 作符的所有中间结果使用的空间。 有时候，我们可以认为m 是整个内存或内存的绝大部分。假是， 我们也将看至几个操作共享内存的情况，这时m 比整个内存要小褥多。 事实上，一个操作可德到的缓冲区的数目可能不是一个可以预计的常 数，丽可能在执行过程中根据同时撬行的其饱进程来决定。翔果是这样， m 实际上是对个搡作可得到的缓冲区数目的估计。 我们将做一个简化的假设，即在磁盘上一次访问一个块的数据。实 际上，如果我们能够次读一个关系的许多块，这些块可能来自一个磁 道| 二连续的块，那么某些技术可能会提高算法的速度。有三类参数，b 、 3i 数据库嚣源开销估算的代价模型 第3 章宽采情况下数据库资源的开销计算分析 t 和v ： 当描述一个关系r 的太小时，绝大多数情况下，我们关心包含r 的所有元组所需的块的数目。这个块的数目表示为b ( r ) ，或者如果我 们知道指的是关系r ，就可以仅仅表示为b 。通常，我们假设r 是聚 簇的，即r 存储在b 个块中或近似b 个块中。实际上我们可能希望在保 存r 的每个块中留出一小部分空闲空闻，以各将来向r 中插入数据。 不过，对于为得到完整的r 面需要从磁盥上读取的块数来说，b 道常 是一个足够好的近似。我们将使用b 来作为统一的估计值。 有时候，我们也需要知道r 中的元组的数目，我们将这个数表 示为t 限) ，或在我们知道所指关系为r 时简 汪为t 。如果需要一个块 中能容纳的r 的元组数，我们可以使用比率t b 。此外，有一些情况 下，一个关系分布地存储在若干块中，这些块同时还被其他关系的元组 占用。如果这样，那么一个简化的假设是r 的每个元组要求一个单独 的磁盘读，我们将使用t 作为这种环境下读r 所需磁盘i o 数的估算。 最晤，我们有时候希望参考出现在关系的列中的不同值的数目。 如粜r 是一个关系，它的一个属性是a ，那么v ( r ，a ) 怒r 中a 对应别上 不固僮的数目。更一般地讲，如果【a l ，地，a o 是一个属性列表，那么 v ( r ， a 】，a 2 ，a n 】) 是r 中属性a 1 ，a 2 ，a n 对应剜不同的1 i 元缀的数目。 换言之，它最仃( 万a l ，a 2 , a n ( r ) ) 中的元组数目。 3 1 4 数据库资源开销估算豹一般性模型 上西讨论了单个操作符的代价模型及参数，我们来构造一般的数据 篓3 熏冗余情况下数据库资源的开销计算舟析3 2 几种冗余情况下壹洵运算的代竹估算 艨资源开链模型。 穰提本章前面酶论甑，数据库的资源开效益f o 开镑为主，并可以 以f o 操作的磁盘数据块来表示。2 1 节我们讨论了报袭系统、管理类、 决簸类数据库应用对数据库的资源开销与o l t p 系统的照著不同，前者 对数据的查询操作频度远比后者高，而修改、删除操作的频度则甚低； 蜃者则相反。因此，数据库的资源总开销是与各种数据库操作出现的频 度有关能。g a r c i a m o l i n a 都d 。u l l m a n 等人提出眩代绘模型应用于整个 数据库资源开销估算时并没翁反映出不同应用的这种差异，由此，我们 可以构造以下公式： c = e ( c 。p ( o ，。k i ) ) ， i 1 ，2 ，1 i 公式( 3 一1 ) 其中，c 为数据库的资源总开销，o p o ) 为数据库的各种操作( 包括 增、删、教、查询等，或飕关系代数表示豹各秘操作盯、k 、p 以及 这些操作符的组合运算nu + 一x 等) ，n 为操作种类数，c 叩( j ) 为单个操作o p ( i ) l 拘代价，。州) 为操作o p ( i ) 出现的频度。 利用公式( 3 1 ) 我们可以估算各类数据库应用的资源开销。我们在后 面章节主要分析各种冗余情况下查询与维护的代价。 3 ，2 凡秘冠余情况下紊诲运算的载俊估算 3 2 1 一级存储器( 烹存缓存) 大小以及冗余对奁询代价的影响 3 2 1 1 主存大小对查询代价的影响 作为前面介绍的参数的个简单应用，我们来看著作为大多数查询 3 2 几种冗余懵扰下鸯询运算的代价估算 第3 章冗棠清况下数据库资源的开销计算分析 操作都需要用到的排序，扫撼的代价。如果关系r 是聚簇的，那么表 曩描 操作蟹的磁盘i 0 数目近似为b 。同样，热果r 能够装入全部主存，那么 我们可以透过将r 读入主存并做肉排序，从而实现捧序扫描，所需磁盘 i o 数仍是b 。 如果r 聚簇，但主存不够大，需要两阶段多路合并排序，那么，根据 两阶段多路合并排序算法分析 ”，我们需要大约3 b 次磁盘i 0 ，它们相等 地分布于在子寝中读r 、回骂予表和重读子表的操作中。记住，我们不 将最终结果的驾操作计入，也不计入积累的输出结果所占用的内存空 间。鹾是假设每一个输出块立即被某个其蚀的操作消耗；有可能就是写 回磁盘丽邑。 但是，如采r 不是聚簇的，那么所需的磁盘i o 数通常较高。如巢r 分布在其他关系的元组之间