Database Systems Design Part III : Normalization

Presentation on theme: "Database Systems Design Part III : Normalization"— Presentation transcript:

1 Database Systems Design Part III : Normalization
CSEE in Hunan University Jin-Min Yang

2 Database Design Flow Diagram
Investigation, analysis, research Modeling (identify, deduce refine, abstract) , Individual Part 1 ER-diagram Requirements Individual Part n View Stored procedure Transformation User view 1 Rational Relations Relations User view n Normalization Implement in particular DBMS

3 期望的关系模式特性 设计得好的关系模式具有如下3个重要的属性：
1) 一个关系是由一组逻辑上相关联的属性构成，也就是说，一 个关系（relation）的属性是指一个实体（Entity）或者一个 关系（Relationship）的属性. 2) 无损联接性是指将一个关系分解成2个或多个关系之后，原有 的关系能够通过做自然联接来复原，这一点是从关系实例来讲 的，也就是从元组来说的，其具体情形看ER建模中的裂口陷进 和后面的5范式。 3) 依赖保留性指将一个关系分解成2个或多个关系，分解前的函 数依赖性在分解之后仍然存在，其具体情况看后面的BC范式。

4 函数依赖理论及其在数据库设计合理性验证中的应用
已知： 对于一个关系R, 它的属性集合A＝ (A1, A2, …, An)， 有函数依赖集F = {X1 → Y1, …, Xj → Yj },其中Xk  A，Yk  A， 1 k  i； 应用： 判断函数依赖Xt→ Yt是否成立； 判断Xt是否是R的候选键； 计算F的闭包F+，推理出其隐含的所有其它函数依赖(放大) 构建F的最小集，也即特征集（精简）；. 判断两个函数依赖集F和E是否等价；

5 解决问题的关键策略 对于属性集合 X， Xk  A, 在函数依赖集F下的X的闭包X+ : 是指使用F能确定的所有属性的集合；
必须掌握的内容： X+的计算； F+的计算； Let X+ = X Repeat 如果F中有某个FD，它的左边是X+的子集. 添加该FD 的右边的属性到 X+. Until ( X+ 不发生改变 or X+ 包含了R得所有属性)

6 判断属性集Xk是否是R的候选键的方法 对于关系R，它的属性集合A，函数依赖集F，对于属性集合 Xk， Xk  A：
如果 Xk+ = A；然后计算Xk的所有真子集的闭包，如果它们都不等于A；那么Xk是R的候选键，否则不是；

7 两个函数依赖集F和E 的等价性 对于两个函数依赖集F和E，如果E中的每一个函数依赖都在F+中，那么就说F覆盖E； F覆盖E 的判定方法：
对E中的每一个函数依赖X → Y ，基于F，计算X＋，然后检查Y是否在X+中； 如果全部成立，那么F覆盖E； 如果 F覆盖E， F也覆盖E，那么就说E和F等价( equivalent）； F和E等价，那么E+ = F+.

8 函数依赖集的最小集（缩减函数依赖，减炼的过程）
对函数依赖集F，如果满足如下三个条件，那么它就是最小集： F中的每一个函数依赖X → Y，Y只含一个属性；. F的任意真子集，都与F不等价； 对F中的任意函数依赖X → A，设X的真子集Y，对于F，当用Y → A替换X → A后得到的函数依赖集E，F和E不等价； 对于一个函数依赖集，它的最小集，可以说是它的一个特征集； 对于一个函数依赖集，它的最小集可能有多个，也即并不唯一；

9 完全函数依赖（Full FD） 定义: 对于函数依赖A → B，如果从A中去掉任一个属性，依赖关系不再成立，那么 A → B是一个完全函数依赖。 也说，B完全函数依赖于A； 如果从A中去掉任一个属性，依赖关系依然成立，那么就说 B部分函数依赖于A； 例子: eno → ename (完全FD) eno, ename → salary, title (部分 FD, 只依赖eno) eno, pno → hours, resp (完全 FD)

10 作业 13.16－13.20； 其中13.19中有关4NF部分的判定基于扇子陷进来思考；

11 范式（Normal Forms） 就关系(Relation)的模式(Schema)合理性而言，可从5个层面来检 测关系是否会存在有潜在的冗余和更新异常。当达到第5个层面时， 则不会有潜在的冗余和更新异常. 共有6个范式: 1NF, 2NF, 3NF, BCNF ( Boyce-Codd) , 4NF, 5NF; 特征：6个范式中，后面范式比前面范式更严格； 比如, 3NF 比 2NF更严格，它对关系(Relation)的模式(Schema)， 相对于2NF，能够更进一步去除冗余和操作异常。

12 第一范式（First Normal Form ）(1NF)
一个关系，对它的任意元组，其所有属性的取值都是原子型 (atomic)时，就说它满足第一范式。 也就是说，满足1NF的关系，它的任意元组的任意属性的取值不 能是多个值的集合（即为多值属性），或者是元组的集合； 在关系型DBMS中，1NF 是基本要求. 不满足1NF的关系是一个不规范(unnormalized)的关系.

13 使一个不满足1NF的关系满足1NF的处理方法
1) 拆分(Splitting)法： 把一个不满足1NF的关系R拆分成2个关系R1和R2： 关系R1：由R中满足1NF的属性构成； 关系R2：由R1的主键属性和R中不满足1NF的属性构成，重新确立R2的主键； R1的主键肯定是R2的主键的构成部分，对否？ 为什么R2中要包含R1的主键属性？ 2) 膨胀(Flattening )方法：把一行扩展成多行，重新确立关系的 主键.

14 拆分法 注意： 拆分后的表，要重新确立其主键！ Analyst ENo PNo Resp Duration E1 P1 Manager 12
EName PNo Resp Duration E1 J. Doe P1 Manager 12 E2 M. Smith P2 Analyst 24 6 E3 A. Lee P3 P4 Consultant Engineer 10 48 E4 J. Miller Programmer 18 E5 B. Casey E6 L. Chu E7 R. Davis 36 拆分法 注意： 拆分后的表，要重新确立其主键！ ENo PNo Resp Duration E1 P1 Manager 12 E2 Analyst 24 P2 6 E3 P3 Consultant 10 P4 Engineer 48 E4 Programmer 18 E5 E6 E7 36 ENo EName E1 J. Doe E2 M. Smith E3 A. Lee E4 J. Miller E5 B. Casey E6 L. Chu E7 R. Davis

15 膨胀法 膨胀后的表，要重新确立其主键！ ENo EName PNo Resp Duration E1 J. Doe P1 Manager
12 E2 M. Smith Analyst 24 P2 6 E3 A. Lee P3 Consultant 10 P4 Engineer 48 E4 J. Miller Programmer 18 E5 B. Casey E6 L. Chu E7 R. Davis 36

16 第二范式( Second Normal Form) (2NF)
一个关系R满足2NF，当且仅当： 满足1NF； 它的所有非主键属性都完全函数依赖于它的主键；

17 Second Normal Form (2NF)
对于不满足2NF的关系R，进行拆分： 对 违背2NF的FD X → Y : 计算 X+； 将关系R 拆分成： R1 = X+ 和 R2 = (R - X+) U X 注意： X 是R的主键属性集的真子集.

18 Third Normal Form (3NF) 3NF是基于传递依赖概念而来的.
传递依赖：是指函数依赖：A → C 是基于 FD： A → B 和FD： B → C推理出来的. 一个关系R满足3NF，当且仅当： 满足2NF； 不存在非主键属性传递依赖于它的主键；

19 Third Normal Form (3NF) 处理方法：按照去除传递依赖的策略是拆分关系R：
对于R中的所有传递依赖X → Y，构建新关系Ri（X，Y）； 去除R中的属性集Y；

20 更完备的2NF和3NF 前面的 2NF and 3NF 仅就关系的主键而言，其实还可以考虑所有的候选键（ candidate keys）
对关系R，满足1NF；它的任意候选键X，其它不在X中的属性都完全函数依赖于X；. 完备的3NF: 对关系R，满足2NF；它的任意候选键X，对其它不在X中的属性，不存在传递依赖于X情况；

21 更完备的3NF例子 . Emp relation: fd1 fd2 根据3NF的定义，此例不满足3NF，原因是SSN属性不是主键属性；
ENo EName BDate Title Salary SuperNo DNo SSN fd1 fd2 根据3NF的定义，此例不满足3NF，原因是SSN属性不是主键属性； 但是满足完备的3NF，因为SSN 属性是候选键； .

22 回答问题 关系R(A, B, C, D, E, F, G, H, I, J) ，
函数依赖集F= { A,B → C ; A → D, E ; B → F ; F → G,H ; D → I,J } 求出R的候选键； 把R分解成第二范式和第三范式.

23 Boyce-Codd Normal Form (BCNF)
一个关系满足 BCNF，当且仅当：任一确定因子(determinant)都是候选键; 对关系R, FD: X → Y ，那么X就为确定因子； 3NF 和 BCNF 的差异在于： 对FD: X → Y，如果Y是一个主键的成员属性，并且X不是候选键，3NF对该情况是允许的； BCNF 要求X是一个候选键; BCNF 比 3NF 更严格.

24 不满足BCNF的基本条件 满足3NF而不满足BCNF的情况非常少见； 满足3NF而不满足BCNF的基本条件是：
至少有两个或以上的组合性候选键； 候选键之间存在交集，即它们之间有公共属性。

25 BCNF versus 3NF 分解到BCNF时，不能保证函数依赖性保留（即dependency preservation 不能保证），即对FD: X → Y，BCNF分解后可能会出现X，Y分别位于不同的关系中，即失去了函数依赖约束； 而对于3NF，就不会出现该情况，它能保持住函数依赖性（dependency preservation） ； 满足3NF而不满足BCNF的情况非常非常少见； 就是存在，也可以不考虑；

26 无损联接依赖Lossless-join Dependency
无损联接依赖Lossless-join Dependency 无损联接属性是指，当分解一个关系后，原有的关系能够通过联接运算复原； 无损联接依赖是指，当分解一个关系后，原有的关系能够通过联接运算复原，不会导致多余的元组（即行）出现； 要保障无损联接属性，有时有必要把一个关系分解成两个以上的关系.

27 4NF and 5NF in Practice In practice, 4NF and especially 5NF are rare.
在ER建模中，注意了Fan trap, 就能满足4NF； 在ER建模中，注意了Chasm trap, 就能满足5NF；

28 4NF 答疑 老师，在书上第四范式给出的例子中 BranchStaffOwner(branchNo, sName, cName)中的主键是哪一个 呢？该关系有多值依赖如下：brachNo->>sName, brachNo- >>oName, 如果是这样的，那么它的主键应该就是branchNo啊？ 可是看书上它的关系表觉得应该又是(sName, cName).而它满足 第四范式后就变成了BranchStaff(branchNo, sName)和 BranchOwner(branchNO, oName)同样看其关系表，主键也不是 branchNo, 对应的应该分别是sName,oName。这是为什么呢？求 解

29 答疑解答 brachNo->>sName是一对多关系, 即一个分支机构有多个员工， brachNo->>oName也是一对多关系, 即一个分支机构接待有多个房 东。而实际业务需求中，要求关注员工和他负责接待的房东。刚 好满足扇子陷阱，因此拆分成BranchStaff(branchNo, sName)和 BranchOwner(branchNO, oName)后还不够，没有精准表达 （sName, oName)之间的关系，即哪个员工负责接待哪个房东，因 此还需要StaffOwner(sName, cName)关系。当然这里有一个假设， 也就是branchNO, sName, oName分别充当了实体分支机构，员工， 房东的主键。

30 答疑解答 在这个多值依赖branchNo->>sName中branchNo是键吗？ 答： 键是就关系而言的，基本准则就是关系中的元组具有唯 一性，唯一性又要根据语义来判断，对 BranchStaffOwner(branchNo,sName,cName)而言，键自 然是(branchNo,sName,cName)；

31 范式和ER建模 规范化和ER建模是两个独立的概念
对一个已经上线的，设计得很差的数据库进行改造时，通常使用范式化理论来检测原有数据库，把它改造成合理的数据库；