数据库五课件

讲授：麻淑芳时间：2012年2月《数据库实用教程》第五章规范化设计5.1关系模式的设计问题5.2函数依赖5.3关系模式的分解特性5.4关系模式的范式5.5模式的进一步规范化*第五章规范化设计

本章讨论如何设计关系数据库，设计关系数据库的核心问题是关系模式的设计。关系数据库的规范化设计理论即“模式设计理论”数据依赖――研究数据之间的联系范式――关系模式的标准模式设计方法――规范化的方法5.1关系模式的设计问题一个关系模型包括外延和内涵两个方面内容：

外延就是通常所说的关系、表或当前值。

内涵是对数据的定义以及数据完整性约束的定义，一般把内涵成为关系模式。

数据的定义包括对关系、属性、域的定义和说明。

数据完整性约束包括静态约束（涉及数据依赖、主键、值域的设计）和动态约束（定义各种操作对关系值得影响）。泛关系模式与数据库模式

关系模式的一般形式:R<U,D,Dom,F>其中：U为组成关系R的全部属性的集合，即U＝{A1,…An}。

D为域的集合，即属性的取值范围的集合。

Dom为U与D之间的映象。

F为属性U上的一组约束，即数据依赖集。例：学习关系SC(SNO,CNO,GRADE)中存在如下数据依赖： （SNO,CNO）GRADE

泛关系模式与数据库模式由于D和Dom对关系模式设计影响不大,故关系模式的一般形式可简化为：

R<U,F> 称为：泛关系模式

其中：属性集U中的每个属性Ai对应一个值域Di，而不同的属性可以有相同的值域。满足上述制约条件F的关系用符号r表示，关系r是关系模式的当前值，是元组的集合。

r表示的关系称为：泛关系

例如，在关系模式STUDENT<U,F>中: U={SNO,SNAME,CNO,CNAME,GRADE} F={(SNO,CNO)GRADE,SNOSNAME,CNOCNAME}泛关系模式与数据库模式在实际使用时，R（U）和r可能不是恰当的形式，需要将R（U）替换为一个关系模式的集合：

ρ={R1，…，Rk} 称为：数据库模式

其中，每个Ri的属性是U的子集,且有R1∪R2∪…∪Rk=U；对数据库模式的每一个关系模式Ri赋予一个当前值，就得到了一个数据库实例σ。

例：关系模式STUDENT(U)可替换为ρ={R1，R2，R3} U={SNO,SNAME,CNO,CNAME,GRADE}R1={SNO,SNAME}R2={CNO,CNAME}R3={SNO,CNO,GRADE}关系模式的冗余和异常问题如果一个关系模式设计的不好，就会出现数据冗余、异常、不一致等问题，常见的有：数据冗余：是指同一个数据在系统中多次重复出现。在数据库管理中，数据冗余一直是影响系统性能的大问题。操作异常：修改异常、插入异常、删除异常。5.2函数依赖关系可定义为笛卡儿积的一个子集，要使这个子集有意义，需要对关系的值作各种限制，这种限制称为数据完整性约束条件。数据完整性约束主要有两种：值域的限制：由DBMS完整性子系统实现。数据依赖：描述了数据之间存在的联系，即属性与属性之间的对应关系。在数据库规范化设计中起着关键的作用。其中，函数依赖是基本的一种依赖，它是关键码概念的推广。函数依赖的定义定义5.1：设有关系模式R（U），X和Y是属性集U的子集，如果对于R的任何一个关系r中的任意两个元组t和s，对应于X的属性分量的值相等时，对应于Y的属性分量的值也相等，即：只要有t[X]=t[X]，就有s[Y]=s[Y]，则称“X函数决定Y”或称“Y函数依赖于X”,其符号表示为：XY。对于R上的每一个XY都称为一个函数依赖（简称FD）。FD也可以描述为：对于r中属性或属性组X的每一个值，r中属性或属性组Y只有一个值与之对应。函数依赖的逻辑蕴涵定义5.2：设F是关系模式R(U)上成立的函数依赖集，X和Y是属性集U的子集。如果从F推导出的X→Y也在R（U）上成立，那么称F逻辑蕴涵X→Y，记为：F⊨X→Y定义5.3：设F是关系模式R（U）上成立的函数依赖集，X和Y是属性集U的子集。F的所有逻辑蕴涵组成的集合称为函数依赖集F的闭包,记为：F+。 F+=｛X→Y|F⊨X→Y｝即：从给定的函数依赖集合F推出的所有函数依赖组成的集合，称为F的闭包。函数依赖的推理规则设U是关系模式R的属性集，F是R上成立的一组函数依赖集，X、Y分别是U上的子集，则存在如下推理规则：FD公理（函数依赖公理）：自反性：若YXU，则X→Y在R上成立。增广性：若X→Y在R上成立，且ZU，则XZ→YZ在R上成立。传递性：若X→Y和Y→Z在R上成立，则X→Z在R上成立。定理5.1：如果X→Y是从F用推理规则导出，那么X→Y在F+中。函数依赖的推理规则例：已知关系模式R(ABC),F=｛A→B，B→C｝,求F+根据FD推理规则，可推出F的F+有43个FD。其中：①据自反性可得出27个FD：函数依赖的推理规则②据增广性可得出7个FD：③据传递性可得出9个FD：函数依赖的推理规则

定义5.4：对于函数依赖X→Y，如果YX，那么称X→Y是一个“平凡的FD”；否则称为“非平凡的FD”。 平凡的FD没有实际意义，根据自反性就可推出。我们感兴趣的是非平凡的FD，只有非平凡的FD才和“真正的”完整性约束条件相关FD公理是FD的一个正确的、完备的推理规则集。函数依赖的推理规则FD推理规则

①合并性：若X→Y，X→Z，则X→YZ。

②分解性：若X→Y，ZY，则X→Z。

③伪传递性：若X→Y，YW→Z，则XW→Z。

④复合性：若X→Y，W→Z，则XW→YZ。

⑤通用一致性定理：若X→Y，W→Z，则X∪（W－Y）→YZ。从并规则和分解规则可得到下面的定理。定理5.2：如果A1…An是关系模式R的属性集，那么X→A1…An成立的充分必要条件是X→Ai（i=1，…，n）成立。FD和关键码的联系定义5.5：设有关系模式R(U),X是属性集U的一个子集。如果X→U在R上成立，那么称X是R的一个超键。如果X→U在R上成立,但对于X的任一真子集X1都有X1→U不成立，那么称X是R的一个候选键。

另，如果A是关系模式R的候选键X中属性，那么称A是R的主属性；否则称A是R的非主属性。属性集的闭包实际使用中，经常要判断能否从已知的FD集F推导出FDX→Y，那么可先求出F的闭包F+，然后再看X→Y是否在F+中。定义5.6：设F是属性集U上的FD集,X是U的子集，那么（相对于F）属性集X的闭包用X+表示，它是一个从F集使用FD推理规则推出的所有满足X→A的属性A的集合：

X+=｛A|AU，X→AF+｝定理5.3：X→Y能用FD推理规则推出的充分必要条件是YX+FD集的最小依赖集关系模式R(U)上的两个函数依赖集F和G，如果有F+=G+，则称F和G是等价的函数依赖集。定义5.7设F是属性集U上的FD集，如果Fmin为F的一个最小依赖集，那么Fmin应满足下列四个条件：F+min=

F+

每个FD的右边都是单属性——右端无冗余属性

对于F中任一函数依赖X→A，其F－{X→A}与F不等价；——Fmin中没有冗余的FD对于F中任一函数依赖X→A，对于任意ZX，F－{X→A}∪{Z→A}与F不等价。——每个FD左端无冗余属性。显然，任何一个F至少存在一个最小依赖集Fmin。5.3关系模式的分解特性定义5.8：设有关系模式R（U），R1、…、Rk都是R的子集,U=R1∪…∪Rk,关系模式R1、…、Rk的集合用ρ表示，ρ=｛R1,…,Rk｝,用ρ代替R的过程称为关系模式R的分解。ρ称称为R的一个分解,ρ也称为数据库模式。

泛关系模式数据库模式 Rρ={R1，…，Rk} rσ=＜r1，…，rk＞泛关系(元组的集合）数据库实例（数据库）模式分解的问题把R分解成ρ的目的:为了消除数据冗余和操作异常现象。对于分解的意义，可以从两个角度来考虑：①σ和r是否等价，即是否表示同样的数据?——用“无损分解”特性表示。②在模式R上有一个FD集F，在ρ的每一个模式Ri上也有一个FD集Fi，那么｛F1，…，Fn}与F是否等价?——用“保持依赖”特性表示。无损分解定义5.9：设R是一个关系模式,F是R上的一个FD集，数据库模式ρ={R1，…，Rk}是R的一个分解。如果在R中满足F的每一个关系r，都有下式成立：则称分解ρ相对于F是“无损联接分解”简称“无损分解”，否则称为“损失分解”。其中符号πRi（r）表示：关系r在模式Ri属性上的投影。r的投影联接表达式πR1(r)…⋈πRk(r)用符号mρ(r)表示：无损分解设ρ={R1,R2,…，Rk}是关系模式R上的一个分解，r是R上的任一关系，ri=πRi(r)（1≤i≤k）,则有下列性质：

①rmρ(r) ②若s=mρ(r),则πRi(s)=ri

③mρ(mρ(r))=mρ(r)——幂等性

注：上述性质的先决条件：r是R的一个关系另：模式分解能消除数据冗余和操作异常，并能使数据库中存储悬挂元组，即存储泛关系中无法存储的信息。无损分解的测试方法算法5.1（追踪算法）：

输入：关系模式R（A1,…An）,R上成立的FD集F，R的一个分解ρ={R1，…，Rk}。输出：判断ρ相对于F是否具有无损分解特性具体步骤:①构造一张k行n列的表格,每列对应一个属性Aj(1≤j≤n)，每行对应一个模式Ri(1≤i≤k)：如果Aj在Ri中，那么在表格的第i行第j列处填上符号aj，否则填上符号bij无损分解的测试方法算法5.1（追踪算法）：

②反复检查F中的每一个FD,并修改表格中的元素,修改方法是：取F中的一个FDX→Y，如果表格中有两行在X分量上相等,在Y分量上不相等，那么修改Y，使这两行在Y分量上也相等。修改原则是：i）如果Y的分量中有一个是aj，那么另一个也修改成aj

ii）如果没有aj，那么用其中一个bij替换另一个符号（尽量把下标ij改成较小的数）。一直到表格不能修改为止，这个过程称为Chase过程③若修改到最后一张表格中有一行是全a，即a1a2…an,那么ρ相对于F是无损联接分解。无损分解的测试方法定理5.4：设ρ={R1,R2}是R上的一个分解，F是R上的FD集，那么分解ρ相对于F是无损分解的充分必要条件是：

R1∩R2→R1-R2或R1∩R2→R2-R1例：设R（ABC），F={A→B}在R上成立，ρ1={AB，AC}。试分析此分解是否为无损分解。 ∵R1∩R2=AB∩AC=A； R1-R2=AB-AC=B； 满足A→B； ∴模式ρ1={AB，AC}是无损分解。保持函数依赖的分解如果关系模式在分解后不能保持FD，那么在数据库中就会出现异常现象。因此，关系模式R到ρ={R1，…，Rk}的分解，应使FD集F被F在这些Ri上的投影所逻辑蕴涵。定义5.10设F是属性集U上的FD集,Z是U的一个子集,F在Z上的一个投影用πZ（F）表示，定义为：定义5.11设ρ={R1,…Rk}是R的一个分解，F是R上FD集，如果有那么称分解ρ保持函数依赖集F。保持函数依赖的分解从定义5.10可知 ，从定义5.11可知 。因此，在分解ρ保持函数依赖情况下有 根据定义5.11，测试一个分解是否保持FD，比较可行的方法是： 逐步验证F中每个FD是否被 逻辑蕴涵。保持函数依赖的分解如果F的投影不蕴涵F，而我们又用ρ=｛R1，…，Rk｝表达R，很可能会有一个数据库实例σ满足投影后的依赖，但不满足F。对σ的更新也就有可能使r违反FD。如果某个分解能保持FD集，那么在数据输入或更新时，只要每个关系模式本身的FD约束被满足，就可以确保整个数据库中数据的语义完整性不受破坏，显然这是一种良好的特性。小结本节讨论的关系模式分解的两个特性实际上涉及到两个数据库模式的等价性问题。包括:

数据等价和依赖等价两个方面。

数据等价是指两个数据库实例应表示同样的信息内容,用“无损联接”来衡量。如果是无损联接分解，那么反复投影和自然联接都不会丢失信息。

依赖等价是指两个数据库模式应有相同的依赖集闭包。在依赖集闭包相同的情况下，数据的语义是不会出差错的。5.4关系模式的范式关系模式设计的好与坏，用什么标准来衡量？——这个标准就是关系模式的范式(NormalForms,简记为NF)。范式有1NF、2NF、3NF、BCNF等多种。范式的种类与数据依赖（FD）有着直接的联系。第一范式定义5.12：如果关系模式R的每个关系r的属性值都是不可分的原子值,那么称R是第一范式(FirstNormalForm，简称1NF)的模式。满足1NF的关系称为规范化的关系，否则称为非规范化的关系。关系数据库研究的关系都是规范化的关系。既使关系模式是1NF，但很可能具有数据冗余和操作异常现象。因此需把关系模式作进一步的规范化。第二范式定义5.13对于FDW→A，如果存在XW有X→A成立，那么称W→A是局部依赖（A局部依赖于W）；否则成W→A是完全依赖，也称“左部不可约依赖”。定义5.14如果A是关系模式R的候选键中的属性，那么称A是R的主属性；否则称A是R的非主属性。定义5.15如果关系模式R1NF,并且R中每个非主属性都完全函数依赖于R的候选键，称R是第二范式（2NF）的模式。如果数据库模式中每个关系模式都是2NF，则称数据库模式为2NF的数据库模式。第二范式在关系模式R中消除非主属性对候选键的局部依赖的方法：算法5.2分解成2NF模式集的算法 设关系模式R（WXYZ），主键是WX，R上还存在FDX→Z（也就是WX→Z是一个局部依赖）。此时应把R分解成两个模式：R1（XZ）主键是XR2（WXY）主键是WX,外键是X（ReferencesR1） 如果R1和R2还不是2NF，则重复上述过程，一直到数据库模式中每一个关系模式都是2NF为止。第三范式定义5.16如果XY,YA,且不存在YX和AY，则称XA是传递依赖(A传递依赖于X)。定义5.17如果关系模式R1NF,并且R中每个非主属性都不传递依赖于R的候选键,那么称R是第三范式(3NF)的模式,如果数据库模式中每个关系模式都是3NF，则称其为3NF的数据库模式。第三范式在关系模式R中消除非主属性对候选键的传递依赖的方法：算法5.3分解成3NF模式集的算法 设关系模式R（WXY），主键是W，R上还存在FDX→Y,这样W→Y就是一个传递依赖。此时应把R分解成两个模式：R1（XY）主键是XR2（WX）主键是WX,外键是X（ReferencesR1） 如果R1和R2还不是3NF，则重复上述过程，一直到数据库模式中每一个关系模式都是3NF为止。第三范式由5.13和定义5.16可以知道,局部依赖的存在必定蕴含着传递依赖的存在。也就是，如果R是3NF模式，那么R也是2NF模式。局部依赖和传递依赖是模式产生冗余和异常的两个重要原因。由于3NF模式中不存在非主属性对候选键的局部依赖和传递依赖，因此消除了很大一部分存储异常，具有较好的性能。定义5.18设F是关系模式的FD集，如果对F中每个非平凡的FDX→Y，都有X是R的超键，或者Y的每个属性都是主属性，那么称R是3NF的模式。——3NF的等价定义BC范式在3NF模式中，并未排除主属性对候选键的传递依赖，仍有可能有冗余和异常现象。为了规范化这种情况，提出了“BCNF”。定义5.19如果关系模式R1NF，并且R中每个属性都不传递依赖于R的候选键,那么称R是BCNF的模式。如果数据库模式中每个关系模式都是BCNF，称其为BCNF的数据库模式。BC范式从定义5.17和定义5.19可以知道，如果R是BCNF模式，那么R也是3NF模式。定义5.20设F是关系模式的FD集，如果对F中每个非平凡的FDX→Y，都有X是R的超键，那么称R是BCNF的模式。——BCNF的等价定义由BCNF的定义也可得出如下结论： 1.非主属性对关键码完全函数依赖； 2.主属性对不包含它的关键码也是完全 函数依赖； 3.没有属性完全依赖非关键码的任何属 性组。分解成BCNF模式集的方法输入：关系模式R的属性集合U，R上成立的FD集F。输出：R的一个无损分解ρ={R1，…，Rk}，满足每个Ri相对πRi（F）是BCNF模式集。方法： ①置初值：ρ={R}； ②如果ρ中所有模式都是BCNF，则转④； ③如果ρ中有一个关系模式Ri不是BCNF，根据定义5.20，知Ri中必存在一个非平凡FDX→A，有X不包含Ri的超键,且AX。此时把Ri分解成Ri1=XA和Ri2=Ri-A，即用分解{Ri1，Ri2}代替Ri，转②; ④分解结束，输出ρ。这样得到的ρ能保证是无损分解，并且每个Ri都是BCNF，但不一定保证ρ能保持FD。分解成3NF模式集的方法输入：关系模式R的属性集合U，R上成立的FD