知识

概述

1. 数据库设计又叫数据库逻辑设计、数据库建模
2. 研究数据项的基本属性以及它们之间的相互关系，目标是用数据库的基本数据结构表示现实世界中的这些数据项，具有不用数据模型的数据库表示这些数据项的数据结构是不同的
3. 关系数据库中，表示数据的数据结构是关系表
4. 对象-关系模型的方法研究仍然处于初级阶段
5. 数据库设计是产生详细模型的过程
6. 逻辑数据库设计是DBA的责任，他使用一种方法将数据库中相关联的数据项分配到表的不同列上去，这种方法应当能够保持所期望的性质
7. 逻辑数据库的设计最重要的衡量标准是：表和属性如实地反映现实世界对象的相互关系，并且将来在对数据库做任何可能的更新后，依然保持着一点
8. 逻辑数据模型包含了所有需要的逻辑和物理设计选择，以及用数据定义语言生成一个设计时所需要的设计存储参数，这些可以用来被创建一个数据库
9. 一个完整的属性数据模型包含了每个实体的细节属性
10. 如何进行关系数据库设计
    分析一个企业
    列出数据库的数据项
    决定如何在关系表中放置这些数据项
11. 案例：学生课程数据库
    attributes of student: sno, sname, dept, sage
    attributes of course: cno, cname
    attributes of student&course: grade
    可以将这些属性放到同一张表中获得表R
    
    观察学生课程DB，发现问题：
    – 数据冗余(redundency)：可看到有大量的冗余数据（红色部分），浪费磁盘空间，属于不良设计
    – 修改异常/更新异常(abnormality of update)：如果更改表所对应的某个实体实例或者关系实例的单个属性时，需要更多的新行；该表存在修改异常/更新异常，浪费时间，用户还可能得到错误；考虑上图中蓝色背景部分，如果要修改学生s0002的信息，改一个信息要改两行
    – 删除异常(abnormality of delete)：通过删除表的某一行来表示某个实体实例或关系实例消失时，会导致丢失另一个实体实例或关系实例的信息（这是不希望丢失的），这就是删除异常
    如下，删除学生s0003，但是c107这门课程的信息也一起被删除
    
    
    – 插入异常(abnormality of insert)：无法在缺少某个实体实例或关系实例的情况下表示某个实体实例或关系实例的信息；如上图，除非知道s0003学生的选课信息，否则无法将其插入表中
    为了解决这些问题，将这一张表拆成三张表
    
    这样，冗余问题和几种异常就都消失了
12. 本章介绍如何完成表的拆分，如何设计数据库的表才能使他没有数据冗余及异常

E-R概念介绍

概述

1. E-R模型（实体关系模型）是一种描述数据库的抽象方法
2. E-R模型包含三种基本的数据分类对象：实体(entity)、属性(attribute)、关系(relationship)
3. 关注问题：实体、属性、简单E-R图；如何将实体、属性转化为关系，实体之间的关系

实体，属性和E-R图

1. 实体：实体就是具有公共性质的可区别的显示对象集合
   如大学注册数据库中有5个实体：学生、教师、教室、课程、课时段；以表现不同时间、不同教室提供不同的课程选择
   一般而言，一个实体被映射到一张关系表中，代表一组对象的集合；表中的每一行是实体发生，或者称为实体实例，它代表一个特定的对象
   注：关系实例指元组的集合，也就是二维表
2. 属性：属性是描述实体或关系的性质
   如下图，是一张具体实体与属性的E-R图
   
   在该E-R图中：
   实体Student包含：sid, student_name(lname, fname, midinitial)等属性，其中student_name为复合属性，由三个属性组成
   实体Employees包含：eid, emp_addr(staddress, city, state, zipcode), hobbies等属性，其中前二者是单值属性，hobbies是多值属性，emp_addr是复合属性
3. 特定属性的特定术语
   标识符：又称候选键，一个标识符是一个能唯一识别一个实体实例的属性/属性集（即键的定义，再少一个属性就无法唯一标识行了）
   主键：表T的主键是被数据库设计者选择出来的作为表T中特定行的唯一性标识符的候选键
   一个实体可以定义多个标识符
   当DBM选择一个属性/属性集作为整个数据库实体实例的标识方法时，他就被称为实体的主标识符，实体的主标识符被映射成主键
   描述符：一个描述性的非键属性（如student.age, employee.name）（不是标识符的描述性属性）
   复合属性：一组共同描述一个性质的简单属性（如student.student_name, employee.emp_addr）
   多值属性：一个实体实例中可以取多个值的属性（如employee.hobbies）
   主键、主标识符都可以是属性集
4. E-R图的几个部分
   实体——矩形
   单值属性——椭圆（附加一条指向实体的直线）
   复合属性——椭圆（附加一条指向实体的直线）；组成复合属性的简单属性通过直线指向复合属性的椭圆
   多值属性——椭圆，通过兑现连接到实体
   主标识符——加下划线表示
5. 如何转换实体、属性到规则
   – 转换规则1:
   E-R图中每个实体映射到关系数据库中的一个表，并用实体名来命名这个表
   表的列代表所有连接到实体的简单单值属性（可以是通过复合属性连接到实体上，但是复合属性本身并不变成表的列（复合属性只留下他下属的简单属性作为列，他自己显示不出来））
   实体的标识符映射为该表的候选键
   实体的主标识符映射为主键（实体的主标识符可以为一个复合属性，这时变为关系表中的一个属性集合）
   实体实例映射为该表中的行
   上面的E-R图，映射成表
   
   – 转换规则2:（处理实体转化成表过程中的多值属性）
   给定一个实体e，主标识符是p，一个多值属性a在E-R途中连接到e，a会映射成自身的一个表，该表以复数形式的多值属性命名
   新表的列为p和a（p和a都有可能由几个属性组成），新表的行为(p, a)值对，表示与p的实体实例（主结果表中的实例）关联的a的属性值对（每个p值都拥有那些属性a的值）
   新表的主键属性是p与a中列的集合
   示例
   
   
   注：对象-关系模型并非这样转换
6. 实体间的联系
   给定M个实体的有序列表E₁, E₂, …, E_m，列表中同一个实体可以出现多于一次，一个联系R定义这些实体实例之间对应规则
   特别地，R代表一个M元组集合，他是笛卡尔积E₁ $\times$ E₂ $\times$ … $\times$ E_m的子集
   实例：具有联系的E-R图
   
   教师实体通过教授联系到课程
   
   雇员实体通过workon联系到项目
   percent是二元联系workon的自然属性（此处表示一个雇员的一个工作周有多少百分比的时间投入到这个项目上）
   如果percent属性被附加在Employees或Projects实体下，那么它将是多值的
   属性percent只有描述一个特定的雇员-项目对时才有意义
   
   联系一个实体到这个实体自身的二元联系叫环（有时也叫递归联系）
   通常在连接线上写出所涉及的实体实例扮演的角色
7. 联系在E-R图中用菱形框表示，并且用连接线连结到对应实体上；对环，写实体实例在连接中扮演的角色名
8. 注意：CAP数据库中的orders表不代表一个联系，因为(cid, aid, pid)不能确定笛卡尔积Customers $\times$ Agents $\times$ Products的一个子集；相反地，根据语义，(cid, aid, pid)的相同值可以重复出现

E-R模型的细节

1. 联系中实体的基数
   最大基数max-card，最小基数min-card
   图示（这个并不是E-R图）
   实体E，F，联系R
   点表示：实体实例；线表示联系R的实例
   线代表实例之间的联系
   
   max-card只有两种取值情况；min-card也只有两种取值情况
   如果实体E中对每一个点最多只有1条线连出去，那么max-card(E, R) = 1
   如果对实体E中每个点，有可能有多条线从一个点连出去，那么max-card(E, R) = n（只用n表示，不是具体数字）
   如果实体E中的所有点都至少有一条线连出去，那么min-card(E, R) = 1
   如果存在没有线连出去的点，那么min-card(E, R) = 0
   上图中：
   max-card(E, R) = n, min-card(E, R) = 0
   max-card(F, R) = 1, min-card(F, R) = 1
2. 一个实体E参与联系R，并且min-cart(E, R) = x(x可以取0或1), max-card(E, R) = y(y可以取1或n), 那么在E-R图中，E与R之间的连接线可以用有序对(x, y)来标记（先小后大），使用新标记来表示该最大有序对(x, y)，即Card(E, R) = (x, y)
   这东西用来标记单个实例参与的联系，具体的基数为何根据语义判断
   如上例
   Card(E, R) = (0, n), Card(F, R) = (1, 1)
   如图，上面的E-R图的E-R关系被标记后
   
   以图中的环为例
   
   manager-of角色的雇员可以不管理任何人，也可以管理多人——Card(Employees 1, manage) = (0, n)
   reports-to角色可以不向任何人报告，也可以向最多一个管理者报告——Card(Employees 2, manage) = (0, 1)
3. 单值参与、多值参与；强制参与、可选参与
   如果max-card(X, R) = 1，那么X被称为单值参与联系R
   如果max-card(X, R) = n，那么X被称为多值参与联系R
   如果min-card(X, R) = 1，那么X被称为强制参与联系R
   如果min-card(X, R) = 0，那么X被称为可选参与联系R
4. 一对一联系、一对多/多对一联系、多对多联系（只考虑两个实体的max-card）
   一对一联系：两个实体均单值参与联系
   多对一联系：一个实体多值参与，一个实体单值参与（通常不分别一对多联系或多对一联系）
   多对多联系：两个实体均多值参与联系
   示例见下
5. 联系中的多方
   多对一联系中的多方是max-card值取一的一方
6. 二元联系如何转化为关系
   – 转换规则3：（针对多对多联系）
   当两个实体E、F参与一个多对多二元联系R时，在相关的关系数据库设计中，联系与映射成一个表T，这个表包括从实体E、F转化而来的2个表的主键的所有属性，这些列构成了表T的主键；表T还包含连结到联系的所有属性的列，联系实例用表行表示，相关连的实体实例可由这些行的主键值唯一地标识出来
   总结：多对多联系生成一个新表，主键是两个实例的表的所有主键，其他属性是（如果有的话）连接在联系上的属性
   – 转换规则4:（针对多对一关系）
   当两个实体E、F参与一个多对一的二元联系R时，这个联系在关系数据库设计中不能被映射成自身的一个表；相反，如果假设实体F具有max-card(F, R) = 1（即表示联系中的多方），那么从实体F转化成的关系表T（即多方对应表）中，应当包括从实体E转化出的关系表的主键属性列（这被称为T的外键）
   max-card(F, R) = 1，T的每一行都通过一个外键只联系到实体E的一个实例；如果F在R中是强制参与的，那么它必须恰恰与E的一个示例相联系，这意味着表T的上述外键不能取空值；如果F在R中是选择参与的，那么T与不与E的实例相关联的行在外键可以取空值
   总结：多对一联系不生成新表；在多方转化出的表中添加外键（一方的主键）（到此为止的部分都是根据max-card值进行判断的，值为1的是多方）；（接下来的部分根据min-card值来做判断）如果多方强制参与，那么外键不能取空值；如果选择参与，那么不相关连的外键位置可以取空值
   –转换规则5:（针对一对一关系）
   如果该一对一联系是可选参与的：
   给定两个实体E、F，他们参与一对一二元联系R，两者参与都是可选的；首先按照转换规则1建立表S来表示实体E，表T来表示实体F；然后到表T中添加一组列作为外键：这些列在表S中构成主键；如果愿意，还可以在表S中加入一组外键列（即表T中的主键列）；对于R的任何联系实例都有唯一一个E的实例联系到唯一一个F的实例；在S与T的对应行中，外键列填写的值引用另一张表的相应行，这一联系使R的实例确定
   如果该一对一联系的一侧是可选参与的：
   在强制参与的实体表中添加外键时，这些列被定义成是非空的
   若两边均强制参与：
   最好将两个实体对应的两个表合并成一个表，避免了使用外键
   总结：
   都可选参与：两实例各转化表，可以彼此添加外键（但添加一个就行）
   一侧可选一侧强制：强制那方添加外键，外键列需要非空
   两侧强制：结果只有一张表

其他E-R概念

1. 属性的基数（就是上述的实体的基数概念，属性也同样拥有）
   给定一个实体E与隶属于它的属性A，用min-card(A, E) = 0来表示属性A是可选的，用min-card(A, E) = 1来表示A是强制的
   一个强制的属性应该与一个列相对应，这个列在实体E对应的表中声明而且不能取空值
   用max-card(A, E) = 1来表示属性是单值的，max-card(A, E) = n来表示属性是多值的
   一个属性A当min-card(A, E) = x, max-card(A, E) = y时，写为Card(A, E) = (x, y)，可以用来标记E-R图中属性实体之间的连接，以显示这个属性的基数
   示例
   
   如图中midinitial属性的基数为(0, 1)，意味中间名是可选属性，成表时可以为空值
2. 弱实体
   如果实体的所有实例都通过一个联系R依赖另一个实体的实例而存在，那么这个实体就称为弱实体
   示例
   
   通过创建表Orders来连接Customers与Agents的行，表Items包含了每个产品的购买记录，表Items的多个行对应一个Orders实例
   可见，实体Ordrs在与Items的联系中是可选的（因为每个订单开始时总是空白的），Line_items在联系中是强制的，因为一个订购条目不能独立于指定了他的顾客与代理商而存在（订购条目不能没有订单而单独存在）
   如果Orders实例不存在了，那么弱实体Line_items的所有实例也将消失
   弱实体的消失说明Line_items的主标识符LineNumber只存在于某个订单中时才是有意义的，实际上这意味着弱实体Line_items的主标识符必须包括实体Orders的主标识符中的属性
   像Line_items这样的属性叫做外标识符属性
   当弱实体Line_items映射为一个关系表line_items时，按照转换规则4，一个名为ordno的属性会被加入进来作为外键（来表示联系has_item），故表line_items的主键由外属性ordno与弱实体标识符lineno组成
3. 泛化层次与泛化联系
   一个对应于对象关系继承特性的E-R概念
   思想：多个有公共属性的实体可以泛化为一个更高层次的超类型实体（或相反，一个一般化实体可以分解为低层次的子类型实体），目的是让属性隶属于适当的层次，以避免使用一个每个实例都要使用大量空值的公共实体的属性
   示例
   
   例如，将manager与non-manager区别为超类型实体的不同子类型实体，像expenseno（开销报告）这样的属性可以只隶属于manager，而像union-no这样的非管理员属性可以只隶属于非管理员
   consultant是另一个实体类型，与employees有许多共通性质，可以建立一个新的超类型实体person来包含两者
   一个显式泛化层次的E-R图要用箭头，箭头不命名，从子类型实体指向超类型实体，子类型与超类型实体的箭头联系经常被称为is-a联系，如“consultant is a person"
4. 根据描述转化为关系表的考虑角度
   有哪些实体
   有哪些联系
   联系上的函数对应关系
   有哪些属性？属性与实体/联系的依附关系

规范化基础知识

1. 规范化是关系数据库设计的逻辑设计的另一种方法，他与E-R模型不太相似，但是一个基于规范化的设计和一个由E-R设计转化成的关系设计几乎可以得到相同结果
2. 事实上，二者具有互补性
3. 规范化方法中，设计者从一个将被建模的现实世界出发，列出将成为关系表中列名的候选数据项，以及这些数据项之间关系的规则列表。这样做的目的是将所有这些数据项表示成为符合限制条件的表的属性，这些限制条件与我们所称的范式相关。这些范式定义限制着表可以接受的形式，使它具有所期望的特定性质，并且避免各种各样的异常行为
4. 目前存在着一系列的范式定义，他们一个比一个限制地更严格
   第一范式，第二范式，第三范式，BCNF范式（后述）
5. 首先，符合第一范式(1NF)的表就是没有多值字段的表（同第二章所述第一范式规则，不能有多值属性），与对象-关系模型介绍的不同（对象-关系模型允许复合类型与汇集类型的值出现在表中），以后默认表示符合1NF的
6. 第二范式(2NF)看起来像是过时的东西，做到了第二范式总会去继续做到第三范式的
7. 从一个将所有数据项包含在一个表（有时称为全局表）中的初始数据库以及这些数据项的相关性规则出发，可以通过一定的过程创建一个具有多个表的等价数据库，这些表均符合第三范式
8. 任何不符合第三范式的表都能够分解为几个不同的表，并具有以下性质：
   第一，每个分解出的表都是一个有效的第三范式表
   第二，所有分解出来的表的连接恰恰包含原始表的信息
   注：从原始全局表分解出的3NF表集合被称为数据库的一个3NF无损分解
   第三，（向3NF分解中的一个表添加一行（或者更新一行）是，可能有一个错误的更新打破数据项相关规则，这些规则是先前数据库设计时输入的一部分；我们希望对插入和更新施加一个限制，以使这些错误不会破坏数据），当对一个表做插入或者更新操作时，通过验证被作用的表中数据项的有效性，可以检查是否破坏了相关性规则，而不必进行表的连接操作
   具有这三个期望性质的3NF分解通常被认为是可以接受的数据库设计
9. 规范化方法的输入：全局表和数据项相关规则
10. 如图，将三个实体的属性列举在一起，得到一个没有规范化的库源信息数据项集合
    
    这样设计的表产生异常：
    – 更新异常——如更新某个雇员的电话号要改变多行
    – 删除、插入异常——如某个雇员技能没了，就没有任何关于他的信息剩下；除非一个雇员已经收获某技能，否则它将不能被收入表中

函数依赖

1. 函数依赖：给定一个至少包含2个属性集A、B的表T，A函数决定 B（B函数依赖于A），记作A$\to$B，当且仅当，设计者希望对表T的任何可能内容（即行集合），T中的两行不能在A上取相同的值而在B上取不同的值
   形式化说法：给定T的两行r₁, r₂, 如果r₁(A) = r₂(A), 那么r₁(B) = r₂(B)

2. 示例：下列函数依赖成立
   
   emp_id $\to$emp_name
   emp_id $\to$emp_phone
   emp_id$\to$dept_name

3. 函数依赖的图形描述
   如果A$\to$B，那么A的每个值对应B中的唯一的值
   
   如果A不函数决定B，那么A的某些值与B的多余一个值可能对应
   
   示例：SCG数据库
   
   sno $\to$ sname，成立
   sno $\to$ dept，成立
   sno $\to$ cno，不成立，因为每个学生可以选好多不同的课

4. 示例
   
   A对B：一对一；B对A：一对多，故仅是A$\to$B，这样的关系称为一对多关系
   
   都是一对一，A$\to$B、B$\to$A都成立，这样的关系称作一对一关系
   若两属性彼此互不函数依赖，那么这样的关系称为多对多关系

5. Armstrong公理
   从已知的一些函数依赖可以推导出另外一些函数依赖，需要一系列的推理规则
   Armstrong公理就是描述这些推理规则的，有三条基本规则，可扩充成多条扩充规则

6. 基本Armstrong：假定给定一个表T，如果Head(T)的子集{X, Y, Z}（X，Y，Z都是属性集），那么有下面的规则
   规则1: 包含规则
   如果 Y $\subseteq$ X ，那么X$\to$Y

   证明：
   
   注：只要证明出给定T的两行r₁, r₂, 如果r₁(A) = r₂(A), 那么r₁(B) = r₂(B)就完成了证明

   规则2: 传递规则
   如果X$\to$Y，Y$\to$Z，那么X$\to$Z

   证明：
   

   规则3: 增广规则
   如果X$\to$Y，那么XZ$\to$YZ（表示X与Z、Y与Z两个属性集的并集）

   证明：

7. Armstrong公理的蕴含
   规则4: 合并规则
   如果X$\to$Z，X$\to$Y，那么X$\to$YZ

   证明：
   

   规则5: 分解规则
   如果X$\to$YZ，那么X$\to$Y而且X$\to$Z

   证明：
   

   规则6: 伪传递规则
   如果X$\to$Y，WY$\to$Z，那么WX$\to$Z

   证明：
   

   规则7: 聚积规则
   如果X$\to$YZ，Z$\to$W，那么X$\to$YZW

   证明：
   

8. 求出表满足的函数依赖最小集的过程
   首先考虑决定因素与依赖因素都是单个属性的情况
   再考虑决定因素是多个属性的情况
   例题见下

9. 函数依赖集F的闭包，记为F⁺
   给定一个函数依赖集F，他作用表T的属性上
   定义F的闭包为可以从F中推导出的所有函数依赖的集合，记为F⁺
   任何函数依赖都可以推导出平凡依赖

10. 平凡依赖：A$\to$A这类的

11. 函数依赖集的覆盖
    表T上两个函数依赖集f和g，如果g可以从f用蕴含规则推导出来（即g $\subseteq$ f⁺），那么f覆盖g

12. 函数依赖集的等价
    如果f覆盖g，g覆盖f，那么二者等价，记作f $\equiv$ g

13. 属性集的闭包
    给定表T的函数依赖集F和T中包含的属性集X
    定义X的闭包X⁺作为由X函数决定的最大属性集合Y，则该最大集合Y满足X $\to$ Y存在于F⁺中
    注意，根据包含规则，Y一定包含X的所有属性，但是可以不包含任何其他属性

14. 计算属性集闭包的算法
    需要已知给定属性集，该属性集的函数依赖集
    算法为
    
    第一步，属性集的闭包在该属性集本身的基础上扩展
    接着遍历函数依赖集，对每个函数依赖，若被依赖属性（集）在当前半成品闭包之内，那么就将他决定的那个属性加入当前半成品；对新的半成品继续做此工作
    直到再怎么遍历结束再也加不进去
    注意是反复做遍历而不是一次遍历就结束
    例题见下

15. 最小覆盖：构造最小函数依赖集
    构造最小函数依赖集M来覆盖一个给定的函数依赖集F，M是F的最小覆盖
    最小覆盖的特点：没有冗余的函数依赖；每个函数依赖的左边都没有多余属性

16. 非关键函数依赖：一个函数依赖X$\to$Y在一个函数依赖集 上是非关键的，当且仅当去掉X$\to$Y剩下的函数依赖集仍与原本的函数依赖集等价（有跟没有一样）
    计算非关键函数依赖

17. 构造最小函数依赖集的算法
    第一步，根据给定函数依赖集F创建一个等价的函数依赖集H，H中函数依赖们右边只有单个属性
    第二步，从H中顺次去掉在H中非关键的单个函数依赖
    第三步，从函数依赖集H中顺次用左边具有更少属性的函数依赖替换原来的函数依赖（只要不发生H⁺的改变）
    第四步，从剩下的函数依赖集中收集所有左边相同的函数依赖，使用联合规则创建一个等价的函数依赖集M，M中的函数依赖左边都是唯一的

无损分解

1. 规范化过程：将表分解成几张更小的表（投影到多个覆盖所有列的子集，并有些公共列）但当将分解的表连接起来时并不是总能获得原始表的所有信息，总能得到原表的所有行，但可能得到更多的行
   如
   
2. 无损分解：对任何表T及其函数依赖集F，T的一个分解是一个表的集合{T₁, T₂, …, T_k}，该集合具有两个性质：
   对该集合中的每一个表T_j，Head(T_j)是Head(T)的一个子集
   Head(T) = ${\bigcup }_{j=1}^k$ Head(T_j)
   给定表T的特定内容（T的行被投影到某个T_j的列上），做为分解的结果，如果对表T的任何内容，F中的函数依赖都能保持如下关系成立，则称表T的一个分解相对于函数依赖集是一个无损分解（无损连接分解）
   T = T₁ $\infty$ T₂ $\infty$ … $\infty$ T_k
3. 有损分解：
   分完之后 T $\subset$ T₁ $\infty$ T₂ $\infty$ … $\infty$ T_k
   示例
   
   注意，对无损分解的要求是在任意元组值是都要成立，下图也不是无损分解
   
   因为不对任意的行内容满足条件
4. 数据库模式
   数据库模式是数据库中所有表标题的集合，以及设计者希望在表的连接上成立的所有函数依赖的集合
   示例
   
   在AB join BC中加入(a4, 200, c4)不可以，因为不满足该数据库模式的函数依赖要求
5. 一个定理
   给定表T和T的属性集X，下面两个描述是等价的
   X是T的一个超键；X$\to$Head(T)（即$X_F^{+}$ = Head(T)）
6. 给定表T和他的有效函数依赖集，一个把T分解成两个表T₁、T₂的分解是T的一个无损分解，当且仅当Head(T₁)与Head(T₂)都是Head(T)的真子集，而且Head(T₁) $\cup$ Head(T₂) = Head(T)（即T的所有属性在T₁、T₂中全部出现），同时如下函数依赖之一可以通过F推导出
   Head(T₁) $\cap$ Head(T₂) $\to$ Head(T₁)
   Head(T₁) $\cap$ Head(T₂) $\to$ Head(T₂)
7. 多个表的无损连接分解
   T $\Rightarrow$ {T₁, T₂, …, T_k}可以通过递归地使用两张表连接的结果展示无损性

范式

1. 示例
   

2. 定义：依赖保持性
   给定一个数据库模式和一个通用表T，函数依赖集合F；表T₁, …, T_k是T的一个无损分解，那么对于F的一个函数依赖X$\to$Y，如果对分解中的某个表T_j有X $\cup$ Y $\subseteq$ Head(T_j)，则称“该函数依赖在T的分解中被保持”，或称“T的分解保持了函数依赖X$\to$Y”，或称“函数依赖X$\to$Y在T_j中被保持”，或称“函数依赖X$\to$Y存在于T_j中”
   设关系模式R上的函数依赖集为F，将关系模式分解为T₁, …, T_k这k个子关系模式，从函数依赖集F中可以推导出在子关系模式T_j之上所存在的函数依赖集合为F_j
   如果函数依赖集F和${\bigcup }_{j=1}^k$F_j等价，即F⁺ = { ${\bigcup }_{j=1}^k$F_j }⁺，则称该分解具有依赖保持性
   以上面的例子（将通用表分成4个表）
   函数依赖1存在于表emps中，函数依赖2存在于表depts中，函数依赖3存在于表skills中，函数依赖4存在于表emp_skills中；因为F的每个函数依赖在4个表中的一个保持，所以无论何时模式中的一个表被更新，都可以验证任何被这个更新影响的函数依赖仍然有效，可以通过在那个表中检验他的有效性来验证，而不需要连接操作

3. 发现候选键的算法（原理上是去除非关键的属性，即去掉之后不影响属性集闭包的属性，这与候选键的定义吻合）
   给定表T以及函数依赖集F
   
   示例见下

4. 主属性
   表T中A属性为主属性，当且仅当A存在于表的某个键k之中（该键没有必要是主键）

5. 非主属性
   不存在于键k之中的属性

6. 第二范式(2NF)
   数据库模式中表T和函数依赖集F被称为满足第二范式，如下条件：
   对于存在于T中由F推导的任何函数依赖X$\to$A（这里A是一个不在X中的单一属性而且是非主属性），X不是T的任何键K的真子集
   当一个数据库模式包含的所有表都符合2NF时，这个数据库被称为是符合2NF的

7. 第三范式(3NF)
   当数据库模式中表T和函数依赖集F满足下列条件时，被称为符合第三范式：
   对任何由F推导并存在于表T中的函数依赖X$\to$A（这里A是单个属性而且不在X中），下面两个性质之一必须成立：X是T的一个超键或者A是T的一个主属性
   当一个数据库模式包含的所有表都符合3NF时，这个数据库模式被称为符合3NF

8. BCNF
   当下面性质成立时，一个数据库模式中的表T和函数依赖集F被称为符合BCNF：
   任何F可推导出的函数依赖X$\to$A都在T中，这里A是不在X中的单一属性，X必须是T的一个超键
   当一个数据库模式包含的所有表都符合BCNF时，这个数据库被称为符合BCNF

9. 三个范式的要求
   基础要求：F可推导出的依赖X$\to$A，A是单个属性而且不在X中

	对X的要求	对A的要求
第二范式	X不是T的任何键K的真子集	A不在X中，A为非主属性
第三范式	X是T的一个超键	A是T的一个主属性（这两条满足一个就好）
BCNF	X必须是T的一个超键	X$\to$A在T中

注：X$\to$A在T中是指X $\cup$ A$\subseteq$ Head(T)

10. 生成良好的3NF分解的算法
    

注意到函数Heading(K)生成一个集合，包含属性集合K，他可以被加入到集合S中，S是一个属性集合的集合

例题

e.g. 1. 如图

max-card(E, R) = n
max-card(F, R) = 1
min-card(E, R) = 0
min-card(F, R) = 1

e.g. 2. 如图

第一对：一对一联系
第二对：多对一联系
第三对：多对多联系

e.g. 3. 转换下列联系成关系

max-card(Employees, works_on) = n
max-card(Projects, works_on) = n
此联系是多对多联系，适用于转换规则3
Employees(eid, straddr, city, …)
Projects(pid, proj_name, due_data)
works_on(eid, pid, percent)

e.g. 4. 转换下列联系称为关系

max-card(Instructors, teaches) = n
max-card(Course_sections) = 1
此联系是多对一联系，多方是Course_sections
Instructors(insid, Iname)
Course_sections(insid, secid, course, …)

e.g. 5. 图书借阅管理

各实例

各联系

将E-R图转化为关系模型

e.g. 6. 篮球联赛信息管理

e.g. 7. 聊天论坛管理


结果为
USERS(user_name, email, tel, add)
POSTS(ID, user_name, rep_ID, title, content)

e.g. 8. 邮件信息管理


联系人（email，用户名，电话，地址）
邮件（ID，发送人email，被回复的邮件ID，内容，标题）
接收（接受人email，邮件ID）
抄送（抄送人email，邮件ID）

e.g. 9. 列出下面表T满足的函数依赖的最小集

1. 单个属性的情况
   A$\to$B成立
   C$\to$B成立
   D$\to$A成立
   D$\to$B成立
   D$\to$C成立
2. 多个属性情况
   D$\to$ABC成立
   A$\to$B成立
   C$\to$B成立
   最后手动检查一下AC$\to$D（因为这是唯一剩下的可能，还没被推出来的），发现成立
3. 得到最终答案
   
   注意：
   第二部中：不用考虑D在左边的情况，因为已知D决定了所有人；不用考虑B在右侧的情况，因为已知B被所有人决定
   答案中不写不必要的函数依赖左侧的合并，因为这是可以被推导来的，而这里求的事最小集

e.g. 10. 求函数依赖集F的闭包

e.g. 11. 考虑属性A，B，C，D组成的集合上的两个函数依赖集

1. F中
   B $\to$ C, B $\to$ D, B $\to$ B, B $\to$ A $\Rightarrow$ B $\to$ ABC
   B $\to$ A, B $\to$ D $\Rightarrow$ B $\to$ AD, AD $\to$ E $\Rightarrow$ B $\to$ E, B $\to$ CD $\Rightarrow$ B $\to$ CDE
   所以F覆盖G成立
2. G中
   B $\to$ CDE $\Rightarrow$ B $\to$ C, B $\to$ D, B $\to$ E $\Rightarrow$ B $\to$ CD
   B $\to$ ABC $\Rightarrow$ B $\to$ A
   所以G覆盖F也成立

故有F $\equiv$ G

e.g. 12. F = {B $\to$ CD, AD $\to$ E, B $\to$ A}，计算{B}⁺
{A, B, C, D, E}

e.g. 13. 构造函数依赖集F的最小覆盖M
F = {ABD $\to$ AC, C $\to$ BE, AD $\to$ BF, B $\to$ E}

1. H = {ABD$\to$A, ABD$\to$C, C$\to$B, C$\to$E, AD$\to$B, AD$\to$F, B$\to$E}
2. 去除非关键依赖
   – 首先假设ABD$\to$A是非关键函数依赖，去掉ABD$\to$A，H₁ = {ABD$\to$C, C$\to$B, C$\to$E, AD$\to$B, AD$\to$F, B$\to$E}
   计算(ABD)_H1⁺: X(0) = ABD
   计算X(1): 遍历H₁，顺次找左部为ABD或ABD子集的函数依赖，找到ABD$\to$C、AD$\to$B、AD$\to$F、B$\to$E，故X(1) = X(0) $\cup$ CBFE = ABDCFE
   计算X(2): 遍历H₁，顺次找到左部为ABDCFE或其子集的函数依赖，找到C$\to$B、C$\to$E，故X(2) = X(1) $\cup$ BE = ABCDEF，有X(2) = X(1)，算法终止，而(ABD)_H1⁺ = ABCDEF包含A，故ABD$\to$A是非关键的函数依赖，删除，得到H₁ = {ABD$\to$C, C$\to$B, C$\to$E, AD$\to$B, AD$\to$F, B$\to$E}
   – 接着假设ABD$\to$C是非关键函数依赖，去掉后得到H₂ = {C$\to$B, C$\to$E, AD$\to$B, AD$\to$F, B$\to$E}
   计算(ABD)_H2⁺: X(0) = ABD
   计算X(1): 遍历H₂，顺次找左部为ABD或ABD子集的函数依赖，找到AD$\to$B、AD$\to$F、B$\to$E，故X(1) = X(0) $\cup$ BFE = ABDFE
   计算X(2): 遍历H₂，顺次找到左部为ABDFE或其子集的函数依赖，找不到这样的函数依赖，算法终止，而(ABD)_H2⁺ = ABDEF，不包含C，故ABD$\to$C不能删除，得到H₂ = {ABD$\to$C, C$\to$B, C$\to$E, AD$\to$B, AD$\to$F, B$\to$E}
   – 接着假设C$\to$B是非关键函数依赖，将它去掉，得到H₃ = {ABD$\to$C, C$\to$E, AD$\to$B, AD$\to$F, B$\to$E}
   计算(C)_H3⁺: X(0) = C
   计算X(1): 遍历H₃，顺次找左部为C或C子集的函数依赖，找到C$\to$E，故X(1) = X(0) $\cup$ E = CE
   计算X(2): 遍历H₃，顺次找到左部为CE或其子集的函数依赖，找不到这样的函数依赖，算法终止，(C)_H3⁺ = CE，不包含B，故C$\to$B不能删除，得到H₃ = {ABD$\to$C, C$\to$B, C$\to$E, AD$\to$B, AD$\to$F, B$\to$E}
   …
   最终得到H = {ABD$\to$C, C$\to$B, AD$\to$B, AD$\to$F, B$\to$E}
3. 从H中顺次用左边含有更少属性的函数依赖来替换原来的函数依赖（在不改变H⁺的情况下）
   根据一些Armstrong定理，得到H = {AD $\to$ C, C $\to$ B, AD $\to$ F, B $\to$ E}
4. 保证每个函数依赖的左边都是独有的
   最终答案H = {AD $\to$ CF, C $\to$ B, B $\to$ E}

e.g. 14. 判断下列分解是不是无损分解

1. 两表拥有原表所有属性，各自属性集都是原表属性集的真子集，且A$\to$AB成立（因为A$\to$A、A$\to$B都成立）
2. 是
3. 不是
4. 不是

e.g. 15. 此分解是否无损

1. 先看T₁T₂
   可以
2. 可以（比较的是(A, B, C)与(A, D)）

e.g. 16. 找出R的候选键

1.
K = {A, B, C, D}
loop 1: {K - A}⁺ = {B, C, D}⁺ = {B, C, D} $\ne$ R
loop2: {K - B}⁺ = {A, C, D}⁺ = {A, C, D} $\ne$ R
loop3: {K - C}⁺ = {A, B, D}⁺ = {A, B, C, D} = R $\Rightarrow$ K = {A, B, D}
loop4: {K - D}⁺ = {A, B}⁺ = {A, B, C, D} = R $\Rightarrow$ {A, B}
2. {B}
3. {A, D}

e.g. 16.