关系数据理论概述

数据库逻辑结构设计的任务：为数据库应用构造良好的数据库模式

关系模式中的异常问题

数据冗余
更新异常
插入异常
删除异常

出现异常的原因：

关系模式中存在不合适的数据依赖

解决方式：

通过分解，消除不合适的数据依赖（规范化）

函数依赖

关系模式

一个关系模式可以表示为一个五元组R(U,D,DOM,F)；

R：关系名称
U：R中所有属性的集合
D：U中属性所来自的域的集合、
DOM：属性到域的映射
F：U中属性间的数据依赖的集合

模式涉及重点关注U和F

数据依赖

是一个关系中的属性之间的某种语义约束关系

知道A可以确切的找到B，这样的函数叫做函数依赖。其实就是单值函数

函数依赖

分类一：

平凡函数依赖：任何情况下都成立
例如：在一个职工关系中,职工号总能函数决定它本身,记作“职工号→职工号”,对于任一个给定的职工号,都有它本身的职工号值唯一对应,此为平凡函数依赖。又如:职工号和性别构成的属性子集总是能够函数决定其中的职工号或性别属性,可分别记作为“(职工号,性别)→职工号”和“(职工号,性别)→性别”,因为对于任何给定的一个元组中的职工号和性别的组合值,都唯一对应一个职工号值或性别值,不可能出现其他的职工号值或性别值,此种也为平凡函数依赖。
非平凡函数依赖
如在职工关系中,职工号函数决定其他每个属性都是非平凡函数依赖,另外“(职工号,姓名)→性别”也是非平凡函数依赖,虽然在这里由决定因素中所含的职工号单属性就能够函数决定性别,而带有的姓名属性有些多余。

分类二：

完全函数依赖：记作是f

设R（U）是属性集U上的关系，x、y是U的子集，x’是x的真子集。若对于R（U）的任何一个可能的关系，有x→y但x’→y，则称y完全函数依赖于x，记作X→^F^Y。
所谓完全依赖是说明在依赖关系的决定项（即依赖关系的左项）中没有多余属性，有多余属性就是部分依赖。
部分函数依赖：记作是p

设R（U）是属性集U上的关系，x、y是U的子集，x’是x的真子集，若x→y且x’→y，则称y部分依赖x，记作X→^P^Y。显然，当且仅当x为复合属性组时，才有可能出现部分函数依赖。

例如：职工号姓名性别年龄职务
1001 张三男 36 正处
1002 李四男 38 副处
1003 王五男 50 正科
1004 赵六女 38 副处
1005 孙七女 49 科员
职工号和其他的属性之间的函数依赖都是完全函数依赖。因为职工号是一个单属性决定因素，他不可能在包含其他任何属性，那么就不存在真子集函数决定其他每个属性的情况存在，如（职工号，性别）的值虽然能够决定相应职工的年龄，但其中的真子集“职工号”就能够函数决定其年龄，所以（职工号，性别）到年龄之间的函数为部分函数依赖（因为只通过“职工号”就可以决定）。（简单的说：真子集可以决定结果）

假设存在：“学号→系号”、“系号→系名”和“系号→系主任名”
那么存在：“学号→系名”和“学号→系主任名”这两个函数依赖是传递函数依赖。

分类三：

传递函数依赖

一个关系R（U），X,Y,Z为属性集U上的子集，其中存在X→Y和Y→Z，但Y不决定X，同时Y不包含Z，则存在X→Z，即X传递函数决定Z，Z传递函数依赖于X。

有关码的术语

码：一个关系的所有属性

码为单个属性，称为单属性码
码为多个属性，称为多属性码
码为全部属性，称为全码
包含一个码的属性组，称为超码。
包含在任何一个码中的属性，称为主属性
不包含在任何一个码中的属性，称为非主属性

候选码： 唯一标识一个关系的属性组
主码： 候选码多于一个，从候选码中选出的一个码作为主码。
主属性： 候选码的所有属性。
非主属性： 不包含在任何候选码中的属性
全码： 极端情况下，整个属性组都是码。
外码： X不是该关系模式的码，但是X是另一个关系模式的码。比如(Sno,Cno,Grade)中的Sno不是码，但Sno是(Sno,Sname,Sage)的码，则Sno是外码

1NF、2NF、3NF和BCNF

参考文章

规范化

是为了减少数据冗余和消除各种异常。

范式：满足规范化要求的关系模式

范式分类：

第一范式：满足最基本的规范化要求的关系模式
第二范式：在第一范式的基础上，进一步满足一些要求
依次类推：第三范式、BC范式、第四范式等

第一范式（1NF）：无重复列

1NF的定义为：符合1NF的关系中的每个属性都不可再分。

第一范式（1NF）是指数据库表的每一列都是不可分割的基本数据项，同一列中不能有多个值，即实体中的某个属性不能有多个值或者不能有重复的属性。如果出现重复的属性，就可能需要定义一个新的实体，新的实体由重复的属性构成，新实体与原实体之间为一对多关系。在第一范式（1NF）中表的每一行只包含一个实例的信息。简而言之，第一范式就是无重复的列。

　　说明：在任何一个关系数据库中，第一范式（1NF）是对关系模式的基本要求，不满足第一范式（1NF）的数据库就不是关系数据库。

问题：可能会出现：数据冗余、更新异常、插入异常、删除异常

第二范式（2NF）：属性完全依赖于主键【消除部分子函数依赖】

满足第二范式（2NF）必须先满足第一范式（1NF）。第二范式（2NF）要求数据库表中的每个实例或行必须可以被唯一地区分。为实现区分通常需要为表加上一个列，以存储各个实例的唯一标识。例如员工信息表中加上了员工编号（emp_id）列，因为每个员工的员工编号是唯一的，因此每个员工可以被唯一区分。这个唯一属性列被称为主关键字或主键、主码。

　　第二范式（2NF）要求实体的属性完全依赖于主关键字。所谓完全依赖是指不能存在仅依赖主关键字一部分的属性，如果存在，那么这个属性和主关键字的这一部分应该分离出来形成一个新的实体，新实体与原实体之间是一对多的关系。为实现区分通常需要为表加上一个列，以存储各个实例的唯一标识。简而言之，第二范式就是属性完全依赖于主键。

比如给出一个表：
$$
(Sno,Sdept,Sloc,Cno,Grade)
$$
其中Sno学号，Sdept是系，Sloc是寝室地址，Cno是课程号，Grade是该学生某个课程的成绩。
$$
(Sno,Cno)\stackrel{F}{\longrightarrow}Grade\Sno→Sdept, (Sno,Cno)\stackrel{P}{\longrightarrow}Sdept\
Sno→Sloc, (Sno,Cno)\stackrel{P}{\longrightarrow} Sloc
$$
那么上述存在了部分函数依赖，需要把部分函数依赖的进行消除：
$$
Sno→Sdept \
Sno→Sloc
$$
因此得出新的关系模式：
$$
(Sno,Sloc,Sdept)\
(Sno,Cno,Grade)
$$
判断的方法是：

第一步：找出数据表中所有的码。
第二步：根据第一步所得到的码，找出所有的主属性。
第三步：数据表中，除去所有的主属性，剩下的就都是非主属性了。
第四步：查看是否存在非主属性对码的部分函数依赖。

问题：可能会出现：数据冗余、更新异常、插入异常、删除异常

结论：对码的传递依赖不友好

第三范式（3NF）属性不依赖于其它非主属性[消除传递依赖]

https://blog.csdn.net/qq_43371004/article/details/88970261

第三范式（3NF） 3NF在2NF的基础之上，消除了非主属性对于码的传递函数依赖。

第三范式（3NF）要求一个数据库表中不包含已在其它表中已包含的非主关键字信息。

例如，存在一个部门信息表，其中每个部门有部门编号（dept_id）、部门名称、部门简介等信息。那么在的员工信息表中列出部门编号后就不能再将部门名称、部门简介等与部门有关的信息再加入员工信息表中。如果不存在部门信息表，则根据第三范式（3NF）也应该构建它，否则就会有大量的数据冗余。简而言之，第三范式就是属性不依赖于其它非主属性。

结论：主属性对码的不良函数依赖也会导致异常

BC范式（BCNF）消除主属性对于码的部分与传递函数依赖

所有非主属性对每一个码都是完全函数依赖；
所有的主属性对每一个不包含它的码，也是完全函数依赖；
没有任何属性完全函数依赖于非码的任何一组属性。

多值依赖和4NF

多值依赖

多值依赖：设R(U)是属性集U上的一个关系模式，X,Y,Z是U的子集，且Z=U−X−Y。当且仅当R(U)的任一关系r，给定的一对(x,y)值，有一组Y的值，这组值仅仅取决于X的值而与Z的值无关，则成R(U)中的多值依赖$X\rightarrow \rightarrow Y$成立。

判定方法：对于任意关系中，如果存在两个元组（就是行），记为A,B，如果他们的某一属性X的值相等，那么我们交换它们另外的属性Y的值后，得到的新的两个元组，在表中是可以在原来的表中找到与它们相匹配的元组的。

平凡多值依赖：若$X \rightarrow \rightarrow Y$，而$Z=\empty$，则称$X\rightarrow \rightarrow Y$为平凡多值依赖。

非平凡多值依赖：若$X \rightarrow \rightarrow Y$，而$Z\neq\empty$，则称$X\rightarrow \rightarrow Y$为非平凡多值依赖。

多值依赖的性质

（1）多值依赖具有对称性

若X→→Y，则X→→Z，其中Z＝U－X－Y

（2）多值依赖具有传递性

若X→→Y，Y→→Z，则X→→Z –Y

（3）函数依赖是多值依赖的特殊情况。

若X→Y，则X→→Y。

（4）若X→→Y，X→→Z，则X→→YU Z。

（5）若X→→Y，X→→Z，则X→→Y∩Z。

（6）若X→→Y，X→→Z，则X→→Y-Z，X→→Z -Y。

多值依赖和函数依赖的对比

1）若函数依赖X→Y在R（U）上成立，则对于任何Y’ 属于Y均有X→Y’ 成立

2）多值依赖X→→Y若在R(U)上成立，不能断言对于任何Y’ 属于Y有X→→Y’ 成立，因为多值依赖中，其实就是一对一组，一个老师可能交多门课，所以不同老师可能有教相同的课，所以不能推出X→→Y’ 成立。我们可以看出，如果把一组改为一个，实际上就是函数依赖，所以所函数依赖是多值依赖的特例，多值依赖不一定是函数依赖，但函数依赖一定是多值依赖。

4NF

关系模式$R<U,F>\in 1NF$，如果对于R的每个非平凡多值依赖$X\rightarrow \rightarrow Y(Y \nsubseteq X)$，X都含有码，则$R<U,F>\in 4NF$。

1）不允许有非平凡且非函数依赖的多值依赖

2）允许的非平凡多值依赖是函数依赖

3）平凡的多值依赖属于第四范式

关系规范化小结

ArmStrong公理系统

逻辑蕴涵和闭包

函数依赖:

属性集 α 决定属性集 β ,则称有函数依赖 α→β

逻辑蕴含:

F能推出原不直观存在于函数依赖集F 中的函数依赖 α → β,则成α→β被函数依赖集F逻辑蕴含

函数依赖的闭包 F^+^:

由关系模式R直观得到的函数依赖F所推出的所有隐含的或未隐含的(直观的)函数依赖的集合
举例:

F中有α–>β,β–>ω
则函数闭包F^+^中存在α–>ω

若F=F^+^，则称F是函数依赖的完备集

理论上，如果能求出F的闭包，就能求出R的所有码

Armstrong公理系统

设关系模式R<U,F>，其中U为属性集，F是U上的一组函数依赖，Y,X,Z⊆U那么有如下推理规则：

自反律(叫大推小更确切):
$若Y⊆X⊆U，则X→Y$
增广律(加了也不影响)
$若X->Y,则XZ–>YZ$
传递律(一传十十传百)
$X->Y,Y->Z,则X->Z$

Armstrong公理的推论

合并规则（合并右边）：
$X->Y,X->Y,则X->YZ$
分解规则（分解右边）：
$X->YZ,则X->Y,X->Z$
伪传递规则（左边加一点）：
$X->Y,YW->Z则XW->Z$

引理：$X→A_1A_2…A_k成立的充分必要条件是X→A_i成立(i=1,2,…,k)。$

Armstrong公理系统的证明

1、自反律：若Y,X⊆U，则X→Y为F所蕴含
证明:

设Y⊆X⊆U。
对R<U,F>的任一关系r中的任意两个元组t,s：
若t[X]=s[X]，由于Y X，则有t[Y]=s[Y]，所以X→Y成立，自反律得证。

2、增广律：若X→Y为F所蕴含，且Z U，则XZ→YZ为F所蕴含
证明:

设X→Y为F所蕴含，且Z⊆U。
对R<U,F>的任一关系r中的任意两个元组t,s：
若t[XZ]=s[XZ]，由于X ⊆XZ，Z⊆ XZ，根据自反律，则有t[X]=s[X]和t[Z]=s[Z]；
由于X→Y，于是t[Y]=s[Y]，所以t[YZ]=s[YZ]；所以XZ→YZ成立，增广律得证。

3、传递律：若X→Y，Y→Z为F所蕴含，则X→Z为F所蕴含
证明：

设X→Y及Y→Z为F所蕴含。
对R<U,F>的任一关系r中的任意两个元组t,s：
若t[X]=s[X]，由于X→Y，有t[Y]=s[Y]；
再由于Y→Z，有t[Z]=s[Z]，所以X→Z为F所蕴含，传递律得证。

4、合并规则：若X→Y，X→Z，则X→YZ为F所蕴含
证明：

因X→Y ，所以X→XY （增广律 XX→XY即X→XY）
因X→Z ，所以XY→YZ （增广律）
因X→XY，XY→YZ
故X→YZ （传递律）

5、伪传递规则：若X→Y，WY→Z，则XW→Z为F所蕴含

证明：

因X→Y ，所以WX→WY （增广律）
因WY→Z ，所以XW→Z （传递律）

6、分解规则：若X→Y，Z∈Y，则X→Z为F所蕴含

证明：

因Z∈Y 　所以Y→Z （自反律）
因X→Y 所以X→Z （传递律）

属性闭包

在关系模式R所对应的F^+^中,有α→β ,则所有β组成的集合αF^+^ 叫做属性集α关于F的属性闭包

属性闭包算法:

result=A //此处A是一个属性集,result就是要计算的属性闭包
for each α-->β in F:
    if α in result:   //α已经在属性闭包里了,即A-->α是成立的
    result=result+β   //增加属性闭包

正则覆盖 F^+^

将原函数依赖集F中的函数依赖α–>β中的部分(α或β属性中)冗余属性删除。F^+^ 和 F 的函数依赖的闭包是相同的

属性是否冗余判断条件,对于α–>β函数依赖(哪边冗余F在哪边)

1、α属性集中有属性A是冗余的,$(α−A)→β$成立:
F 逻辑蕴含 $(F−(α→β))∪((α−A)→β)$

2、β属性集中有属性b是冗余的,$α→(β−b)$成立
$(F−(α→β))∪(α→(β−b))$ 逻辑蕴含 F

无损分解

将关系模式R分解成关系模式R1和R2,则:

$R_1∩R_2→R_1或R_2$ ;即$R_1$和$R_2$的交集是R1或R2的super key

最小函数依赖集

函数依赖集的等价

定义：设F和G是关系模式R的两个函数依赖集，如果F^+^=G^+^,则称F和G等价。也称F是G的覆盖，或G是F的覆盖。

定理：设F和G是R的两个函数依赖集，则F和G等价的充要条件是F⊆G^+^且G⊆F^+^.

问题：给定两个函数依赖集G和F，判断F和G是否等价？

方法：

1、对于F中的每个函数依赖X->Y,求XG^+^，若都有Y⊆XG^+^，则说明F⊆XG^+^

2、对于G中的每个函数依赖X->Y,求XF^+^，若都有Y⊆XF^+^，则说明G⊆XF^+^

最小函数依赖集（最小覆盖）

1、定义：

如果函数依赖集F满足以下条件，则称F为一个极小函数依赖集。也称为最小依赖集或最小覆盖。

(1)F中任一函数依赖的右部仅含有一个属性（右部都是单属性）。

(2)F中不存在这样的函数依赖X→A，使得F与F-{X→A}等价（没有多余的依赖）。

(3)F中不存在这样的函数依赖X→A，X有真子集Z使得(F-{X→A})U{Z→A}与F等价（左部不存在多余属性）。

最小依赖集通用算法

① 用分解的法则，使F中的任何一个函数依赖的右部仅含有一个属性；

② 去掉多余的函数依赖：从第一个函数依赖X→Y开始将其从F中去掉，然后在剩下的函数依赖中求X的闭包X+，看X+是否包含Y，若是，则去掉X→Y；否则不能去掉，依次做下去。直到找不到冗余的函数依赖；

③ 去掉各依赖左部多余的属性。一个一个地检查函数依赖左部非单个属性的依赖。例如XY→A，若要判Y为多余的，则以X→A代替XY→A是否等价？若A属于(X)+，则Y是多余属性，可以去掉。（以上步骤中，求出关系依赖集F,此时，再F的基础上，求出X或者Y的闭包，是否包含A）

反复执行步骤2、3，直至F不再变化

注意：最小函数依赖集不是唯一的。

模式分解概述

参考文章

当模式不符合关系范式时，需要进行模式分解。

模式分解

函数依赖的投影

投影的计算方法

分解正确性检验

无损连接性

分解所得到的各个关系模式，经过自然连接可以还原成被分解的关系模式。

算法

参考文章

参考

对于一个分解，有k个子集，n个属性，建立一张k行n列的初始表，对于每一行也就是分解的每个子集，把该分解子集出现的属性对应的列写上aj，否则写上bij
对于每一个依赖，找到左部属性对应的列，根据行的值分组，对于行的值相同的这些行，查看对应右部属性的列，如果这些格子里有a值，那把所有这些格子改成a值，如果没有，改成行最小的b值。如果某个b值改成a值，那么其他行(不属于当前操作的行)的相同b值也要改成a值。
如果不变则停止，如果出现有一行为a1 a2 … an，那么说明该连接为无损连接。