（测试计量技术及仪器专业论文）关系数据库数据组织中无α环的分解问题的研究.pdf

关系数据库数据组织中无旺环的分解问题的研究 摘要 计算机技术的快速发展使数据存储的问题得到一定程度的解决，数据 库出现了海量数据的大型和超大型数据库，它们广泛的应用于c i m s 、g i s 等领域；数据库的数据类型也出现如流媒体、空间、时态等多种复杂的数据 形式，产生了网络、并行、移动、分布式等数据库的多种组织形式。因此近 些年来在数据库的设计与应用中的查询异常问题逐渐成为数据库研究的热 点。无环数据库模式的设计理论研究，已成为了当前数据库研究的一个新的 重要分支。 数据库理论与图论的结合产生了无环数据库模式设计理论。数据库模 式分解是使数据库模式设计更加规范化，可以减少冗余，减少存储异常和查 询异常。通过图论中图的方式比较直观的表达数据库的数据模式，这种方法 与数据规范化理论和函数依赖对数据库的数据多样性语义描述相结合，产生 了一个针对复杂数据库的设计研究的新方法。由于无环数据库模式本身具有 很多优良的特性，这些特性解决了数据库研究中以往一些难以解决的问题， 因此数据库的无环性已经成为判断数据库模式优劣的一个重要特性。 本文是基于无环数据库模式，对数据库数据组织中数据模式无a 环分 解问题展开研究。通过关系数据库的函数依赖集的归并依赖集对数据库模式 是否存在函数依赖冲突进行讨论，研究数据库的数据模式中是否存在环，数 据库模式是否满足无a 环分解，以及如何在各种数据库模式的规范化的范 式级别上判断环的存在和迸行无a 环分解的问题。 1 、基于数据库超图的无a 环的特性。分析了求解归并依赖集和最小归 并依赖集的算法，提出了归并依赖集的二元组集合闭包的求解算法。并对归 并依赖集的左部集及子集的求解算法进行了系统的整理。 2 、结合数据库超图、f d 超图从微观讨论函数依赖蕴涵关系的特点， 分析了归并f d 超图对应的关系模式中存在的各种内部冲突。在此基础上， 对f d 集f 存在内部冲突的特征和条件进行讨论，提出了判定定理和判定算 法；同时在广义左部冲突和右部冲突概念的基础上，提出了数据库模式月 ( 阢f ) 分解为满足岛( 保持函数依赖、无损连接、第三范式) 分解时f 是否存在的广义左部冲突和右部冲突的判定定理和算法。 3 、在对有内部冲突的归并依赖集中的函数依赖关系进行分析的基础 上，提出满足b c n f 的分解条件和满足p 2 且无d 环分解的充要条件并进行 了证明。给出了条件的判定算法和数据库模式的分解算法。 4 、提出初等归并依赖集和初等最小归并依赖集的概念，定义初等最小 规并依赖集的弱左部冲突和弱右部冲突，讨论了初等最小归并依赖集下的冲 突问题，给出了在f d 集，其初等最小归并依赖集d 中存在弱左，右部冲 突时模式分解为满足p e k 为有吐环的结论，并给出了初等最小归并依赖集的 求解方法，冲突的判定算法。最后给出了数据库模式分解满足p e k 和无a 环 分解算法。 5 、在研究简单范式( s n f ) 的数据库模式无n 环分解时，基于最小归 并依赖集关联度的基础上，提出了简单范式的数据库模式无a 环的分解条 件。证明了在f d 集f 的最小归并依赖集d 中存在弱左、右部冲突以及d 不满足条件时模式分解为满足风为有a 环的这一充分必要的结论。给出了 数据库模式满足无环的条件判定定理及算法和数据库模式满足尽和无环 分解的算法。 关键词数据库模式分解；规范化；超图；无n 环；冲突 r e s e a r c ho fs c h e m ad e c o m p o s i t i o no nn a c y c l e i nt h ec r e a t i o nr e l a t i o nd a t a b a s e a b s t r a c t d u et ot h er a p i dd e v e l o p m e n to fc o m p u t e rt e c h n o l o g y ，t os o m ed e g r e et h e s t o r a g ep r o b l e mo fd a t ah a sb e e ns o l v e d l a r g e s c a l e a n ds u p e rl a r g e s c a l e d a t a b a s e so ft h em a g n a n i m i t yd a t at h a ta r ew i d e l yu s e di nt h ep r o d u c t i o nf i e l d s u c ha sc i m s ，g i sh a v ep r e s e n t e d t h et y p eo ft h ed a t ab e c o m em o r ea n dm o r e c o m p l i c a t e d ，s u c ha st h es t r e a mm e d i a ，s p a t i a ld a t a ，t e m p o r a ld a t ae t c a n dm a n y d i f f e r e n tt y p eo fd a t ao r g a n i z a t i o no fd a t a b a s es u c ha sn e t w o r k ，p a r a l l e la n d m o b i l eh a v eb e e np u tf o r w a r d d e s i g na n di n q u i r yb e c o m et h ef o c u si nd a t a b a s e r e s e a r c ha sw e l la si na p p l i c a t i o n t h e r e f o r ea tp r e s e n tt h et h e o r yo fa c y c l i c d a t a b a s es c h e m ad e s i g nh a sb e c o m ean e wi m p o r t a n tb r a n c ho f d a t a b a s es t u d y “ c o m b i n i n gt h ed a t a b a s ea n dg r a p ht h e o r yp u tt h et h e o r yo fa c y c l i cd a t a b a s e s c h e m af o r w a r d d e c o m p o s i t i o no fd a t a b a s es c h e m am a k e st h ed e s i g no f d a t a b a s em o r es t a n d a r d a n dr e d u c e st h er e d u n d a n c ea n dt h ea b n o r m a l i t yo f i n q u i r ya n ds t o r a g e a c c o r d i n gt ot h eg r a p ht h e o r y , r e l a t i o ns c h e m a si nd a t a b a s e s c h e m at a i lb ee x p r e s s e dc l e a r l y t h i sm e t h o dc o m b i n e st h en o r m a l i z a t i o nt h e o r y a n dt h es e m a n t i cd e s c r i p t i o no ft h ev a r i e t yo fd a t au s i n gf u n c t i o n a ld e p e n d e n c y ， f o r m san e wt e c h n i q u ei nc o m p l i c a t e dd a t a b a s ed e s i g nr e s e a r c h s i n c ea c y c l i c d a t a b a s es c h e m ah a sal o to ff i n ep r o p e r t i e s ，w h i c hh a ss o l v e dt h ep r o b l e m st h a t w e r er a t h e rd i f f i c u l ti nt h ep a s t ，t h ea c y c l i c i t yt u r n st oa ni m p o r t a n tc h a r a c t e r i s t i c o f j u d g i n gad a t a b a s es c h e m a t h i sd i s s e r t a t i o ns t u d i e st h eu - a c y c l i cd e c o m p o s i t i o no fd a t a b a s es c h e m ai n t h ed a t ao r g a n i z a t i o no fd a t a b a s e s y s t e m sb a s e do na c y c l i ed a t a b a s et h e o r y t h r o u g ht h ed i s c u s s i o no f t h ee x i s t e n c eo ft h ec o n f l i c t si nt h em e r g ed e p e n d e n c y s e to ft h ef u n c t i o n a ld e p e n d e n c ys e t t h ee x i s t e n c eo fc y c l e sa n da c y c l i cd a t a b a s e s c h e m a d e c o m p o s i t i o n a r e s t u d i e d m o r e o v e r , h o wt o a d dt h ea a c y c l i c c h a r a c t e r i s t i ci n t ot h ed a t a b a s es c h e m a so fs e v e r a ll e v e l so fn o r m a if o r ma n d w h e t h e ri th a saa c y c l i co rh a saa c y c l i cd e c o m p o s i t i o na r ed i s c u s s e d f i r s t l y , b a s e do nt h et y p e so ft h ec y c l e si nt h ed a t a b a s eh y p e r g r a p h ，t h e m e r g ed e p e n d e n c ys e tw h i c hi sd e f i n e df o re x a m i n i n gt h ec o n f l i c t si nd a t a b a s e m = ：= ：一一：一：堕堡茎些兰些型鲨兰一：= ：= ：= ： s c h e m aa n di t sp r o p e r t i e sa r ee x p o u n d e d t h r o u g ht h ea n a l y s i so nt h ea l g o r i t h m s o fc a l c u l a t i n gt h em e r g ed e p e n d e n c ys e ta n dt h em i n i m u mm e r g ed e p e n d e n c ys e t , t h ea l g o r i t h mo fc a l c u l a t i n gt h ec l o s u r eo f2 - t u p l es e to ft h em e r g ed e p e n d e n c y s e ti sp u tf o r w a r d t h ea l g o r i t h m st oc a l c u l a t et h es u b s e to fl e f t s i d es e to ft h e m e r g ed e p e n d e n c ys e ta r es y s t e m a t i c a l l ys o r t e do u t s e c o n d l y ，i n t e g r a t i n g t h ec h a r a c t e r i s t i c st h a t h y p e r g r a p h a n df d h y p e r g r a p hd i s c u s st h ei m p l i c a t i o no ff u n c t i o n a ld e p e n d e n c ys e ti nm i c r o s c o p i c v i e w 也ed i f f e r e n tt y p e so fi n s i d ec o n f l i c t si nt h er e l a t i o ns c h e m aa c c o r d i n gt o t h em e r g ef dh y p e r g r a p ha r ea n a l y z e d b a s e do nt h ed e f i n i t i o no fg e n e r a l i z e d l e f t s i d ec o n f l i c ta n dg e n e r a l i z e dr i g h t s i d ec o n f l i c t ，t h ed e t e r m i n a n tt h e o r e m so f g e n e r a l i z e dl e f t s i d ec o n f l i c ta n dg e n e r a l i z e dr i g h t s i d ec o n f l i c ta n dt h ea l g o r i t h m s o f t h et h e o r e m sa r ep r e s e n t e d t h i r d l y ，w h e nt h e f ds e th a si n s i d ec o n f l i c t s ，i no r d e rt o g e t a d e c o m p o s i t i o nm e e t i n gb c n f , t h em e t h o dt od e c o m p o s ead a t a b a s es c h e m ai n t o o n eo n l ym e e t sk e e pf d ，b c n fa n da a c y c l i ca r ep u tf o r w a r d b a s e do nt h e a n a l y s i so ft h e f u n c t i o n a ld e p e n d e n tr e l a t i o ni nt h em e r g ed e p e n d e n c ys e tw i t h i n s i d ec o n f l i c t s ，t h es u f f i c i e n ta n dn e c e s s a r yc o n d i t i o nt h a te n s u r et h ed a t a b a s e c a l lb ed e c o m p o s e di n t oo n em e e t i n gp 2a n da - a c y c l i ci sg i v e na n dp r o v e d f i n a l l y , t h ec o n d i t i o ne x a m i n i n ga n ds c h e m ad e c o m p o s i t i o na l g o r i t h ma r eg i v e n f o u r t h l y , t h e d e f i n i t i o n so fe l e m e n t a r y m e r g ed e p e n d e n c y s e ta n d m i n i m u me l e m e n t a r ym e r g ed e p e n d e n c ys e ta f ep u tf o r w a r d t h ew e a kl e f t s i d e c o n f l i c ta n dw e a kr i g h t s i d ec o n f l i c ti nt h em i n i m u me l e m e n t a r ym e r g e d e p e n d e n c ys e ta r ed e f i n e d t h ec o n c l u s i o nt h a tw h e nt h em i n i m u me l e m e n t a r y m e r g ed e p e n d e n c ys e th a sw e a kl e f ts i d ec o n f l i c t so rw e a kr i g h ts i d ec o n f l i c ti s r e a c h e d ，t h ed e c o m p o s i t i o nm e e t i n gp z x i sq c y c l i ci sg i v e n t h ea l g o r i t h m so f c a l c u l a t i n gt h em i n i m u me l e m e n t a r ym e r g ed e p e n d e n c ys e ta n de x a m i n i n gt h e c o n f l i c t sa r eg i v e n f i n a l l y , t h ea l g o r i t h mt od e c o m p o s ead a t a b a s es c h e m ai n t o o n em e e t i n g - p e ga n d 旺一a c y c l i ci sg i v e n f i f t h l y , d u r i n gt h er e s e a r c ho nt h ed e c o m p o s i t i o nm e e t i n gs n f ( s i m p l e n o r m a lf o r m ) a n da a c y c l i c ，b a s e do nt h ec o r r e l a t i o nd e g r e eo ft h em i n i m u m m e r g ed e p e n d e n c ys e t ，t h ec o n d i t i o nw h i c he n s u r e sa d a t a b a s es c h e m ac a nb e d e c o m p o s e di n t oo n em e e t i n gs n fa n d 一a c y c l i ei sg i v e n t h es u f f i c i e n ta n d n e c e s s a r yc o n c l u s i o nt h a tw h e ndh a sw e a kl e f ts i d ec o n f l i c t so rw e a kr i g h ts i d e - 一 c o n f l i c to rn o tm e e tt h ec o n d i t i o na b o v e ，t h ed e c o m p o s i t i o nm e e t i n g 只i sd c y c l i ci sp r o v e d t h ea l g o r i t h mt oe x a m i n ew h e t h e rt h ed a t a b a s es c h e m am e e t i n g t h ec o n d i t i o na n dt h e d e c o m p o s i t i o na l g o r i t h mo ft h ed a t a b a s e s c h e m at h a t m e e t i n gp sa n dc t - a c y c l i ca l eg i v e n k e y w o r d sd a t a b a s es c h e m ad e c o m p o s i t i o n ，n o r m a l i z a t i o n ，h y p e r g r a p h ，a a c y c l i c ， c o n f l i c t s v - 哈尔滨理工大学博士学位论文原创性声明 本入郑重声明：此处所提交的博士学位论文关系数据库数据组织中无o r , 环的分解阿题的研究，是本人在导师指导下，在哈尔滨理工大学攻读博士学位 期间独立进行研究工作所取得的成果。据本人所知，论文中除己注明部分外不包 含他人己发表或撰写过的研究成果。对本文研究工作做出贡献的个人和集体，均 己在文中以明确方式注明。本声明的法律结果将完全由本人承担。 作者签名：丧爹金强日期：2 0 0 7 、1 月1 3 日 哈尔滨理工大学博士学位论文使用授权书 关系数据库数据组织中无c t 环的分解问题的研究系本人在哈尔滨理工大 学攻读博士学位期间在导师指导下完成的博士学位论文。本论文的研究成果归哈 尔滨理工大学所有，本论文的研究内容不得以其它单位的名义发表。本人完全了 解哈尔滨理工大学关于保存、使用学位论文的规定，同意学校保留并向有关部门 提交论文和电子版本，允许论文被查阅和借阅。本人授权哈尔滨理工大学可以采 用影印、缩印或其他复制手段保存论文，可以公布论文的全部或部分内容。 本学位论文属于 ，保密口，在年解密后适用授权书。 不保密冈 ( 请在以上相应方框内打4 ) 作者签名：是兰铝 弓交日期：2 0 0 7 年1 月1 3 日 导师签名：都塞、妻 日期：2 0 0 7 年1 月1 3 日 第1 章绪论 第1 章绪论 1 1 本文研究的背景及目的和意义 本课题来源于黑龙江省自然科学基金资助的( n o ：f 0 0 0 6 ) “数据库数据 组织的无环性理论与应用”的基金项目。 关系数据库数据组织的过程中数据库模式分解的无环性理论的研究，是 数据库理论与图论相结合而产生的，是数据依赖与数据规范化理论研究中由 于数据语义的多样性而产生的一个复杂的数据库设计问题，在数据库的应用 设计时，使数据库的关系模式不但符合各个范式及依赖关系的规范化要求， 同时保证查询的无二义性具有无a 环，无卢环或无r 环的良好特性；因而不 仅具有理论价值，而且能够指导数据设计的实践，是数据库理论与应用研究 中一个重要分支。 自二十世纪8 0 年代c b e e d 等人提出了无环数据库模式的特性以来， 无环成为判断数据库模式优劣的另一重要特性”1 。这是因为在对无环的研究 过程中，发现数据库模式存在着不同级别的无环性，f a g i n 在文献中描述了 3 种重要的无环类型：无a 环、无声环、无r 环。无a 环数据库模式具有： l 、连接依赖与一组多值依赖的特性。2 、第四范式分解的唯一性。3 、数据 库状态的总体一致性与其中所含关系的两两一致性。4 、单调的顺序连接表 达式的存在性等优良的特性。无声环数据库模式具有比无a 环数据库模式更 高一级的特性：数据库模式的泛关系超图及每个子图都是无a 环的，都具 备无a 环数据库模式所有特性。无r 环数据库模式是无a 环数据库模式的一 个真子集，除具有无a 环数据库模式所有特性外，无7 环数据库模式还有特 殊的特性：1 、每一个连通的连接表达式都是单调的。2 、数据库模式的整体 连接无损性蕴涵着它的每一个连通子集都是连接无损的。3 、数据库模式的 每一个一致的数据库状态，每一个属性集的各属性之间具有唯一的联系等特 性嘲。 这些无环数据库模式的特性，一方面，为数据库的优化设计提供了理论 和方法。例如：在无c t 环数据库模式的多个关系模式连接查询时，无论对 于时间性还是空间性都存在一个比较优化的查询路径来完成查询。在分布式 数据库环境下，如果数据库模式是无a 环的，则当查询涉及多个场点的关 系的连接时，必定可以产生一个完全缩减程序，使网络上的数据传输压缩到 仅仅包含那些不可缺少的数据元素。另一方面，解决了在规范化理论中难以 解决的一些问题。例如：数据库模式状态的总体一致性等价于关系的两两一 致性的特性，对于数据库的许多研究常常是以假定泛关系存在为前提，当对 数据库中的某个关系作插入、删除或修改时，往往需要对其他的关系作相应 的调整，以维护数据库状态的总体一致性。而在数据依赖、关系规范化理论 中，这一问题是n p 一完全问题，实际上很难实施口4 1 。而无a 环数据库模式 的总体一致性等价于关系的两两一致性的特性，使总体一致性的维护从实际 上成为了可能。 针对数据依赖与关系规范化理论，对数据库模式性能与数据依赖之间的 联系问题上进行了深入的研究和描述，形成了一系列不同的数据库范式的概 念以及以这些为目标的关系数据库设计和查询的算法。由于数据依赖和规范 化理论中，数据库的设计和应用本身存在许多难以解决的复杂问题，而从数 据库模式的子类入手，以超图的方法来描述数据库模式，定义数据库模式及 数据库模式分解的无环性，利用无环性的一些良好的特性通过超图某些特 征，很方便地解决了数据库模式设计中的一些问题。 本文在数据库的数据组织过程中，对数据库模式的分解分别在满足第三 范式( 3 n f ) 、初等范式( e k n f ) 、简单范式( s n f ) 、b c 范式( b c n f ) 和 保持函数依赖( f d ) 、多值依赖( m v d ) 、连接依赖( j d ) 的同时【5 ，9 l ，对满 足无a 环分解的数据模式的有环判定、无a 环分解条件和分解算法的理论 进行研究。给出了数据库模式有a 环、无a 环条件的判定方法，对数据库 模式的无环分解与有n 环改造进行算法设计。为设计一个优秀的数据库 模式奠定理论基础。 1 2 国内外无环数据库模式研究的现状 1 2 1 数据库数据规范化设计理论的研究现状 数据库技术从2 0 世纪6 0 年代末产生到今天已经有4 0 年的历史，历经 了三代演变【l “，已经发展成为以数据建摸和d b m s 技术的核心，内容丰富 的- - j 7 学科。数据库技术是计算机信息系统和应用系统的核心技术和重要基 础。随着人工智能与数据库理论的结合和并行计算技术等的发展，数据库逻 辑演绎和知识推理、数据库中的知识发现( k n o w l e d g ed i s c o v e r yf r o m d a t a b a s e ) 并行计算等技术成为新的理论研究方向”1 。 第1 章绪论 关系数据库应用数学方法来处理数据库中的数据。系统、严格地提出关 系模式的是美国i b m 公司e f c o d d 在七十年代初，在美国计算机学会会刊 c o m m u n i c a t i o no ft h ea c m 上发表的题为“ar e l a t i o n a lm o d e lo fd a t a f o rs h a r e dd a t ab a n k s ”的论文中提出来的，此后，人们在关系数据库理论 方面作了大量的研究工作”，随着关系数据库理论的不断完善以及计算机 技术的发展，关系数据库的技术也趋于成熟，先后出现许多关系型的数据库 系统，例如d b 2 t 2 “， o r a c l e t 2 ”，i n f o r m i x t 2 ”，m ss q ls e r v e r t 2 3 1 等。关系 型的数据库代表了数据库技术发展的一种趋势，并且现在已经成为数据库中 的主流产品。关系数据库之所以重要主要是因为除了它具有单一的数据结 构，数据独立性强与操作简单优点外，还具有以关系代数与逻辑为手段的严 密的理论基础。关系数据库之后，又出现了面向对象数据库系统( o b e c t o r i e n t e dd a t a b a s es y s t e m ) ，分布式数据库系统，并行数据库系统等肚4 。“。 但目前运行的数据库系统大部分仍是关系型的，这说明关系数据库具有长远 的生命力，关系数据库规范化和设计理论的研究仍具有理论和实际意义。因 此，关系数据库理论一直是数据库中的一个重要的研究领域。 数据库理论的研究主要集中在关系的规范化理论、关系数据的数据组 织理论等方面。在关系数据库中数据之间的联系是通过他们之间的逻辑关系 联系的，这些逻辑关系将数据库中所有数据构成一个完整的数据模型即：关 系模型。是由关系数据结构、关系操作集合和关系完整性约束三个部分组成 的。各种联系在关系数据库理论中称之为数据依赖【2 ”，数据依赖是关系中 数据之间固有语义联第的一种约束，数据依赖包括函数依赖f d ( f u n c t i o n a l d e p e n d e n c y ) ，多值依赖m v d ( m u l t i v a l u e dd e p e n d e n c y ) ，连接依赖j d ( j o i nd e p e n d e n c y ) 等。而函数依赖f d ( f u n c t i o n a ld e p e n d e n c y ) 在关系 数据库中是最常见，是最重要的一种数据依赖，对它的研究也最深入，最广 泛。在函数依赖的研究中，为了唯一地表示某一记录，每个关系模式必须有 一个关键字，使得候选关键字在关系数据库中成为一个非常重要的概念，人 们对它进行了深入的研究；给出了基于基数和基于消元法的候选关键字求解 方法”。 在关系数据库的数据模式规范化的组织中，关系模式中信息冗余和数 据的更新异常问题是数据库模式规范化研究要解决的主要问题。 关系数据库理论通过数据之间的依赖关系的相互联系，研究数据依赖 可能逻辑地蕴涵其他数据依赖。a r m s t r o n g 提出了f d 公理系统。从理论上 证明了该推导规则集的有效性和完备性。由此引出了闭包问题，成员籍问 题，最小覆盖问题。解决了关系模式中信息冗余等问题”。 数据库的更新异常的产生是因为在关系模式中存在性质不好的数据库 依赖关系( 属性对候选关键字的部分函数依赖和传递函数依赖) 。在一个关 系模式中，一个属性如果包含在某个侯选关键字中，则称该属性为主属性， 否则称为非主属性。为了消除任何非主属性传递函数依赖于某个侯选关键 字，出现了第三范式的概念。为了消除任何属性传递函数依赖于r 的某个 侯选关键字，定义了b c 范式。为此，在数据库模式规范化的问题上，以前 做了许多大量的研究工作，相继提出了分解一个数据库模式达到各种范式的 算法”。 范式的方法是将一个规范化程度较低的关系模式分裂为两个或者两个 以上的关系模式。设r ( w ) 是一个关系模式，p = ( r i ( 矾) ，r 2 ( w 2 ) ，取( w k ) ) 是一个关系模式的集合。如果u u uw k = 阢称p 是r ( ) 的一个分解。关系模式的分解必须从实际出 发，并不是范式等级越高，分解得越细就越好。一个关系分解成多个关系， 要使得分解有意义，必须是分解后不丢失原来的信息。这些信息不仅包括数 据本身，而且包括由函数依赖所表示的数据之间的相互制约。进行分解的目 标是达到更高一级的规范化程度，但是分解的同时必须考虑两个问题：无损 连接性和保持函数依赖。( 无损分解的概念：设关系模式r ，f 是r 上的f d 集，p = ( r ，m ) 是胄的一个分解。如果对r 中满足f 的每一关系， 都有，= i = i k 闻“r ( r ) ，那么称分解p 相对f 是“无损分解”) ”，当分解具 有连接无损性与保持函数依赖性时，称为等价分解。 规范化理论的研究的目的是为了优化数据库的设计。数据库设计是整 个信息系统成功与否的关键；分为概念设计、逻辑设计、物理设计、概念模 式设计是数据库设计中的一个详细步骤。设计人员仅从用户角度看待数据和 处理要求的约束，产生一个反映用户观点的模式。逻辑设计又称为实现设 计，它的目的是从概念d b m s 可处理的数据库逻辑结构，在这一阶段，就 可以充分利用关系理论。对其规范化程度，包括无环程度在内进行判断检 测，并做出适当修改。而物理设计是为给定的逻辑结构选取一个最适合应用 环境的物理结构的过程，是逻辑设计的完善”1 。 随着应用的发展，数据库规模越来越大。为了更好地进行数据库设计， 人们开始了数据库设计辅助工具的开发，现在很多研究者把精力放在数据库 设计的自动化上。基于人工智能原理，开发了各种专家系统工具和计算机辅 助软件工程工具，这些系统工具的目标是帮助最终用户进行数据库辅助设 第1 章绪论 计，使得数据库更加规范化，尽量避免数据库设计的错误。 1 2 2 连接超图的有关理论 线图( l i n e a rg r a p h ) 是图论中分析研究数据模型应用最广的一种线型 结构1 。线图中每条边只与两个结点相连接。但是，在现实世界中，存在 着各种各样的多元联系，由于线图中限定每条这样的关联结点为两个，多元 联系难以用线图直观地表达，这就限制了线图的表达能力。超图 ( h y p e r g r a t h ) 中的边是把属于同一边的点由一条封闭的曲线围起来的方法 来表示的，这个边称为超边。一条超边可以有多个结点，因而，在数据库的 实际应用中，可以用来表示事物之间更多更为复杂的联系，使数据库的关系 模型的表示更为直观”一。 一个数据库的关系模式r = 五i ，五2 ，娜) 可以用超图来直观表 示。一个超图日是一个有序二元组= ，其中v 是一个有限集， 矿中的元素称为日的结点，e 是一个超边( 或简称边) 的集合。e 中每一条 超边都是矿的一个非空子集，并使得矿中每个结点至少属于e 中的一条超 边。数据库模式的对应超图为h r ，1 - i r = ，v 是结点的集合，e 是 日中边的集合。关系模式r 中的每一个属性a ，对应于胁中的一个结点k ； r 中的每一个关系模式r ，对应于王& 中的一条超边e p 即v f c _ e j 当且仅当4 f 在关系模式尼中。， 例1 1 设数据库模式r = “b c ，c d e ，a e f ，a c e ) ，数据库模式的对 应超图为h r ，i - i r = ，肛埘，b ，c ，d ，e ，f ，) ，e = e l ，e 2 ， e 3 ，e 4 ) ，其中e l = 似，b ，c ) ，e 2 = c ，d ，e ) ，e 3 = a ，e ，毋，e 4 = a ，c ， 目，数据库模式的超图表示为图形如图1 1 所示。 图1 - 1 例1 - 1 对应的超图 f i g 1 1h y p e r g r a p hf o re x a m p l e1 1 = ：= = ：一：堕堡篓! 兰三奎兰三茎矍圭兰堡垒圣：一：= ：一：一：= ： 函数依赖可以由有向超图来表示即f d 超图，关系模式r ( w ，f ) 对 应的f d 超图应当是二元组a ( ne ) ，其中y = r ? 删( a 八r 2 例( ) 八a r 。俐) a a r 。f 叫( ) a b 在实际的数据库应用中，有时进行某些查询时，查询的表达式可能得不 到任何查询结果。原因是经由不同的连接路径却可能产生不同的结果，从而 导致查询的“二义性”。 例1 2 一个教学数据库，它包含属性c ( 课程) ，s ( 学生) ，t ( 学生 s 课程c 的任课教师) ，p ( 谋程c 必要的先修课程) ，y ( 学生s 通过课程 p 的年份) 。 可以分为以下三个原子语义： p l ( 一丁) 语义是：学生s 上课程c 的教师乃 p 2 ( s p - - * y ) 语义是：学生s 通过课程c 必要的先修课程尸的年份是 y ： p 3 ( c 一一s z p ) 语义是：上课程c 的分别是学生s 、先修课程，、教 师n 这个教学数据库属性上的数据依赖集为( c 跏r ，舻一y ， n s ) ，按照规范化理论，这个教学数据库的模式应为r = ( r 1 ( s p y ) ，r 2 ( c s r ) ，r 3 ( c 尸) ) ，其中r l ，五2 ，飓的实际关系，。、r 2 、 如 表1 1 ( 口) ，( b ) ，( c ) 所示。 很容易证明r 是连接无损，保持持依赖的，并且每一个关系模式都是 4 n f 的。 哈尔滨理工大学工学博士学位论文 但是，在这样一个数据库中进行某些查询时将产生某种异常情况。在 上例的数据库中，查询“教师周树玉所授课程的先修课程有哪些”时存在两 条查询路径7 c t p ( 6t 。月树( r 2 ) l q r 。) 和兀冲( 6t 用* i ( r 2 ) m r 3 ) ，但二者的 结果是不同的，分别为表1 1 ( d ) ，( p ) 所示。 表1 - 1 例1 2 对应的数据库表 t a b e l l l 。1d a t a b a s et a b l eo fe x a m p l e l 2 ( 曲( e ) 查询时存在两条查询路径兀”( 6 弘月辩 e ，2 ) 酗r ，) 和7 t p ( 6t ；月树i ( ，：) 1 4 r 。) ，在数据库的模式中可以视为有一个回路。所以用超图来表示一 个数据库模式可以更为直观表示出回路。从而一种称作无环数据库模式的概 念被引入，在1 9 8 1 年，c b e c d 等人将超图的概念引入到关系数据库理论的 研究中，提出了无环数据库的概念，此后，人们对无环数据库给予极大的关 注，相继发表了一些论文，这些论文阐述了数据库模式的无环程度，以及无 环数据库模式的各种优良特性，并且指出这些优良特性与某种无环性是等价 的。这样我们得到衡量数据库模式性能的两个重要标志，即规范化的程度与 无环程度，从而明确了无环数据库的重要性，这就要求我们在关系规范化的 第1 章绪论 过程中需要考虑数掘库的无环性。 设，是超图日= 的一个投影，e f ，e j f ，q = p ，一钉，如果从 f 的每一条超边中删去q 后，所得到的结果图中连通支的个数比f 增多， 则称结点q 是f 的一个关节集。若f 是连通的并且其中不含有任何关节集 则称f 是日的一个块。在一个化简超图中，如果它的所有块都只含有单一 边，则该超图称为一个无a 环超图，否则称为有a 环超图。如果一个数据 库模式的对应化简超图是无a 环的，则称该数据库模式为无d 环数据库模 式；反之，如果一个数据库模式的对应化简超图是有a 环的，则称该数据 库模式为有环数据库模式。 如果一个块只含有一条边，则称这个块是平凡的。如果一个化简超图是 无a 环的，则它的所有块都是平凡的；反之是有a 环的。 因无a 环的易满足性，很多文献也都集中在无a 环的研究上，但是无 环有一个很大的缺陷，那就是无a 环的子图可能是有环的。后来很多学者 又给出了不同环的定义，来描述不同的无环程度，如最著名的r ，f a g i n 的 q ，p ，y 环的分类，b e r g e 环，还有b 环，t 环，h 环等，但其中分类最具 代表性的还是a ，t 3 ，丫的分类，其中无1 3 环具有子图的无环性和比无丫环的 限制条件宽松等优势。 无论是无1 r 环，还是无p 环和无a 环，都具有很多理想特性： l 、联结依赖与一组多值依赖的等价性。 判断某个j d 的满足性问题的时间复杂度一般来说是指数级的，只有j d 的一个特殊子类小4 v d ，其满足性才具有多项式时间的算法。当关系模 式集合p 满足无环条件时，可以证明，在这一条件下，关系模式p 等价于一 个m v d 的集合。对于给定的关系模式集合p = ( r j ，彤，如) 是数据 库模