基础

关系模型是人们为了描述关系而建立的一种二维表，这个二维表叫做关系。

关系模型中的一些术语：

属性：列名，例如图中title、year、length等
模式：关系名和属性集合叫做这个关系的模式。例如Movies(title, year, length, genre).模式中的属性其实是集合
元组：除了首行外的其他行叫元组。每个元组中的各个分量都对应各个属性。
域：其实也就是数据类型，如果上面的域分别是string、 Integer、 integer、 string。因此也可以加上域来描写模式Movies(title: string, year: integer, length: integer, genre: string)
键：键是区分该行和其他行的唯一标识。例如title和year构成了一个键。也就是说没有两部电影的制作年份和名字都相同（当然这种键并不好，可能会有冲突）。也可以只使用一列构成一个键，例如我们的身份证号。它的模式可以表示为： Movies(title, year, length, genre)

在SQL中定义关系

SQL中有三种关系：表、视图、临时表.MySQL使用

代数查询语言

投影

投影包含原有关系中的部分列（也就是一个子集），表示为$\pi{A{1}A{2}…A{n}}(R)$

选择

选择就是按照一定条件对集合进行筛选，返回一个子集。符号位：$\sigma_{C}(R)$,其中C就是条件。

例如：$\sigma_{length \ge 100}(Movies)$,返回就只剩两行了。

笛卡尔积

笛卡尔积也就是A表和B表每一行相乘，例如:

自然联结

自然联结就是将具有公共属性并且属性值相同的元组配对，符号表示为： $R \Join S$。

例如： A和B中都有Name属性并且这两个表中的Name有相同内容，也就是A表中有张三B表中也有张三，对这两个表用Name进行连接的话结果就是name加上其他两个表所有的其他属性。

也可以用数学符号表达：

R(A, B)和S(B, C, D)，两者交集为{B}，产生联结的点就是交集, 两者并集为{A, B, C, D}，联结的结果就是并集.因此自然联结可以表示为：

$\{ ( l_A, l_B , l_C , l_D ) \, | \, (l_A , l_B ) \subseteq R , (l_B , l_C , l_D ) \subseteq S \}$

例如上面S表中B属性中的9，虽然在第二个表中满足第二个条件，但是不在第一个表中，因此不是联结元组中的一部分

$\theta$联结

$\theta$联结构造过程为：

先得到R 和 S的笛卡尔积
然后在笛卡尔积中找到符合条件C的元组

符号为： $R \Join_{C} S$

例如： $R \Join_{ A < D} S$。这个因为都满足，所以结果就是笛卡尔积

命名和重命名

例如上图中两个都有B，当进行联结操作时为了区分不得不使用关系名.属性名的方式。这时可以将其中一个表属性名重命名，例如将第二个关系中的B重命名为X这样就可以简化书写。

约束

约束一般有两种表示方法。

如果R是关系代数，那么$R = \oslash$表示R的值必须为空
2。 $R \subseteq S$,表示R中出现的元组都在S中出现了

引用完整性约束

引用完整性约束表示在某个上下文（关系）中出现的值必须在另外一个相关的上下文中出现。

例如，在Movies中，所有演员信息单独列一个表，如果某一个演员的名字P在另一张表MovieStar（参演明星）中没有出现，那么就可以怀疑P是否是一个演员。

表示为： $\pi{A} (R) \subseteq \pi{B} (S)$.或者等价的写为：

$\pi_{A} (R) - \pi_{B} (S) = \oslash$

键约束

键约束就是没有两个元组有相同的键。因此构造这种约束时可以从反向来看，没有键相同而其他值不同的。

例如name是键，也就是说name是唯一的，因此我们可以断言没有键name相同而address不同的。因此可以让自己对自己做笛卡尔积。选出两个name相同而address不同的，结果必定是空集。可以用数学语言表述为：

$\sigma_{(MS1.name = MS2.name \, AND \, MS1.address != MS2.address)} (MS1 \times MS2) = \oslash$

函数依赖

函数依赖（FD）定义：如果R的两个元组在属性 $A{1} , A{2}, A{3}, … A{n}$ 上一致，那么他们在 $B{1} ,B{2} ,B{3} ,…, B{n}$ 上也必定保持一致

如果关系R上的每个实例都能使一个FD为真，那么成R满足函数依赖f。

如图： title year -> length genre studioName是一个函数依赖。因为前面说过title和year结合起来是一个键，而title year相同可以唯一的确定一部电影，电影相同时长类型也就必定相同。

title year -> starName不是一个函数依赖。因为同一部电影下有不同明星

可以看到即使是键也不能保证可以推出关系依赖。

关系的键

想成为关系的键要满足以下条件：

假设{A1, A2, …, An}是关系的键

这些属性可以决定其他属性。也就是说不存在两个不同的元组有相同A1， A2…值
在{A1, … An}的真子集中，没有一个能决定R的其他属性，也就是说键必须是最小的

键可能有许多

超键

超键不需要满足键的第二个条件，也就是说它不一定是最小的。

函数依赖推导

一些规则

分解结合规则： $A_{1}A_{2}A_{3}...A_{n} -> B_{1}B_{2}B_{3}...B_{n}\\ = A_{1}A_{2}..A_{n}->B_{1},\quad ... \quad ,A_{1}A_{2}A_{3}..A_{n}->B_{n}$
平凡依赖：

${B{1}, B{2}…, B{m}} \subseteq {A{1}, A{2}…, A{n}}$。也就是说，平方函数右边是左边的子集。例如：

$title \quad year -> title$

传递规则：

若$A{1}A{2}A{3}…A{n} -> B{1}B{2}B{3}…B{n} , B{1}B{2}B{3}…B{n} -> C{1} C{2} … C_{k}$ 成立，

则 $A{1}A{2}A{3}…A{n} -> C{1} C{2} … C_{k}$成立。

闭包

算法描述：

给出属性集合${A{1},A{2},A{3}, …,A{n}}$ FD(函数依赖）的集合S.它的一个子集的闭包为：${A{1},A{2},A{3}, …,A{t}}^{+}$

分解FD中的依赖，使得依赖的右边只有一个属性
初始化闭包为${A{1},A{2},A{3}, …,A{t}}$,记作X
寻找这样的依赖， $C_1 ,C_2, …, C_m -> H, 其中C_1 , C_2 ,…, C_m \in X$。然后把H加入到X中，重复查找依赖，直到所有符合条件的值都被加入到闭包中

例如：

有五个属性A, B, C, D, E, F该关系包含以下FD： AB->C, BC->AD, D->E CF->B.求{A, B}的闭包

AB->C, BC->A, BC->D, D->E, CF->B

1. AB->C. AB在闭包中，将C加入闭包，现在闭包中的元素有{A, B, C}
2. BC->D, 将D加入闭包
3. D->E 将E加入闭包。结束

{A, B}的闭包为{A, B, C, D, E}

通过计算闭包，我们可以知道某个关系是否可以由初始集合推断而来。例如给出一个FD：$A_1 ,A_2 ,…, A_n -> B$，如果B在A集合的闭包里，那么就可以推断而来.

并且通过闭包我们可以推断出属性集是否是键。如果某个属性集的闭包可以包括所有元素，那么他就是超键。

求键的方法：

首先将属性分为4个集合L，R，N，LR。其中L是只出现在FD左边的属性，R是只出现在FD右边的属性，N是两边都没有出现的属性，LR是两边都出现的属性。

让X = L+N， Y=LR。其中X表示一定会出现在键中的属性，Y表示有可能添加到键中的属性。

如果X的闭包包含所有元素，则X是唯一的键
否则，从Y中挑选出一个元素A，计算${XA}^+$。如果是闭包，则将A排除出可选择范围
否则使用两个元素，使用三个元素直至使用完所有属性。

第二点和第三点可以看个例子

假设依赖集为{A→BC,BC→A,BCD→EF,E→C}

L = D
R = F
LR = A, B, C, E

X = D, Y = A, B, C, E

首先X的闭包不是键

之后计算{DA}, {DB}, {DC}, {DE}。发现DA的闭包包含所有元素，因此AD是键

现在还有Y中还有三个元素。分别计算{BC D}, {BE D}, {CE D}，发现{BCD}和{BDE}都是键，现在Y中没有剩余属性，结束算法

基本集和投影

给定一个FD集合S，任何和S等价的集合都称为基本集

等价也就代表可以通过上面这些定律推导得出S，他表示了S的简化形式。

最小基本集的定义：

B中所有FD右边都是单一属性
从B中删去任何一个FD后，该集合不再是基本集（因此可以排除平凡依赖，因为删去平凡依赖后没有变化）
对于B中任何一个FD，左边删去任意数量的属性后，B不再是基本集

例：

属性A,B,C, 他们中任何一个元素都可以决定另外两个元素，则可以推断出A->B, A->C, B->A, B->C, C->A, C->B, AB->C, AC->B, BC->A.另外还有A->BC等

则最小化基本集为：{A->B, B->C, C->A}或{A->B, B->A, B->C, C->B}等

求最小化基本集方法：

首先进行分解，使得右边都只有一个元素
假设FD集中含有依赖X -> Y,将X->Y删去再用剩下的元素求闭包$X^+$，如果$X^+$中包含Y的话则这个依赖可以由其他依赖推导得到，故删去。进行完这一步后由传递无法再删去依赖
分解左边的属性，例如AB->C,分解成A->C和B->C，看这两个是否可以由其他依赖推导得到，如果可以则删去AB->C

投影

假设$R_1 = \pi_L (R)$，则R1中有哪些FD成立？

计算过程

设T为$R_1$中成立的FD集合，初始化为空集
对于$R_1$中的每一个子集X, 计算$X^+$（如果有n个元素，总共需要计算$2^n$个$X^+$, 也就是幂集的闭包）.然后将FD集合中对应FD添加入T
然后将所有FD进行合并为T并且变成最小化基本集
1. 如果T中的FD F可以从T中的其他FD推断而来，则删除F
2. 如果 Y->B是T中的一个FD，且Y至少有两个属性，从Y中删除一个属性并记为Z，如果Z->B可以从T中的FD推断而来，则用T->B代替Y->B
3. 重复上述步骤直到不再变化

例：

设A, B, C, D中有FD： A->B, B->C,C->D.假设需要投影到A, C, D.

${A}^+$ = {A, B, C, D}。则FD A->C和A->D成立,注意到A->B也成立，但是由于B不再投影集合中，所以没有意义，也就不用添加
${C}^+$ = {C， D}。 C->D 可以添加
${D}^+$ = {D}，没有依赖可以添加
${A, D}^+$ = {A, B, C, D}
${A, C}^+$ = {A, B, C, D}
${A, D, C}^+$ = {A, B, C, D}
${D, C}^+$ = {C, D}.

所以最后得到的FD集合为{A->C, A->D, C->D}

现在求最小化基本集。我们可以看到A->D可以由A->C, C->D推断而来，所以删除A->D

最小化基本集为{A->C, C->D}

第一二三范式

第一范式

第一范式强调列的原子性，也就是说每个列不能再划分成两列。

例如【联系人】（姓名，性别，电话），电话可能是家庭电话和工作电话，这时我们就需要把电话进行拆分

第二范式

第二范式首先是第一范式。其次还要满足一个表中必须要有一个主键，并且没有包含在主键中的列必须完全依赖于主键，而不能依赖于主键的一部分（部分依赖）。

例如：

表：学号、课程号、姓名、学分;

这个表明显说明了两个事务:学生信息, 课程信息;由于非主键字段必须依赖主键，这里学分依赖课程号，姓名依赖于学号，不是全部依赖于主键，而只依赖于主键的部分，所以不满足第二范式。

如果主键只有一个属性，则必定满足完全依赖

如果不满足第二范式，则很容易产生冗余。

第三范式

第三范式首先是第二范式，并且没有传递依赖，即非主属性不依赖于其他非主属性。

如果一个属性是某个键的成员，那么可以称它为主属性。3NF条件也可以表述成要么FD左边是超键，要么右边全是主属性

具有无损连接和依赖保持性质的3NF关系综合算法

首先对于关系R和上面的FD集 F

寻找F的一个最小基本集，记作G（求最小基本集的方法在投影中说了)
对于G中每一个FD X -> A, 将XA作为某个关系的模式
如果2中的模式不包含R的超键，则增加一个关系，它的模式为R中任何一个键

例如：

R(A, B, C, D, E) 
AB -> C
C->B
A -> D

首先它是一个最小基本集。因为不能通过传递规则删除某一个FD并且关系左边缩减后也无法得到。

然后分解关系得到{A, B, C}, {B, C}, {A, D}.第一个和第二个重叠，删除第二个得到
{A, B, C} {A, D}

由于这两个关系中没有超键，因此需要再任意添加一个键。这里的键有{A, B, E}和{A, C, E}.所以最终答案可以为{A, B, C}, {A, C}, {A, B, E}

BCNF范式

BCNF范式条件：如果R中非平凡的FD $A_1 A_2 … A_n -> B_1 B_2 … B_m$成立，则${A_1 ,A_2 ,.. A_n}$是R的超键

也就是说R中所有FD左边都必须是超键

如果${A_1 ,A_2 ,.. A_n}$的闭包可以包含所有元素，则可以认为这是一个超键。

任何二元关系都属于BCNF

证明：

没有非平凡FD
A->B成立，但B->A不成立。这种情况下，A是键
B->A成立，但A->B不成立，和第二种情况类似
A->B, B->A都成立，则A和B都是键。

BCNF分解算法

过程：

根据R函数依赖集S，检查R是否属于BCNF，属于则终止，不属于进行下一步
如果存在BCNF违例（即某个关系左边不是超键），设这个关系为X -> Y,则计算$X^+$（X的闭包）。选择$R_1 = X^+$为一个关系，$R_2 = X和不在X^+ 中的元素$，这样就把R分解成了$R_1 和 R_2$
计算$R_1 和 R_2$在R上的投影，分别记作$S_1 和 S_2$
在$S_1 和 S_2$上继续使用上面的算法，直到所有都满足BCNF范式

例：

R(A,B,C,D) FD{AB→C,C→D,D→A}

AB的闭包包括所有元素，因此AB是超键，C->D和D->A都是BCNF违例
以C->D进行第二步。C的闭包为{C, D, A},因此得到{C, D, A}和{C, B}
{C, D, A}的FD集为{C->D, D->A}, {C, B}只有两个元素因此结束
{C, D, A}中C的闭包可以包括所有元素，因此C是超键，但是D不是，因此D->A违反BCNF
D的闭包为{A, D}，因此可以得到{A, D}, {C, D}，因为都是两个元素，结束

第四范式

多值依赖（MVD）

多值依赖定义：

$A_1 ,A_2 ,A_3 ,…,A_n ->-> B_1 ,B_2 ,B_3 ,…,B_n$

对于每个A属性上一致的元组(t, u)，能在R中找到满足以下条件的元组v:

A属性和B属性与t相同
除了A和B之外的属性都和u相同

例如：

name	street	city	title	year
fisher	123	hollywood	star wars	1977
fisher	5	malibu	empire strikes back	1980
fisher	123	hollywood	empire strikes back	1980
fisher	5	malibu	star wars	1977

我们可以定义一个多值依赖name ->-> street city

首先假设第一行是t，第二行是u。因为name相同，所以可以得知必定有一行name,street, city和第一行相同，而title，year和第二行相同。也就是图中的第三行。

然后让第二行是t，第一行是u。也可以得知一定有一行name, street, city和第二行相同，而title, year和第一行相同。也就是图中第四行。

以此类推，我们可以发现最终形成了一个闭包。

推导关系

传递规则： …
FD升级规则：每个FD都是MVD（多值依赖）。也就是说若$A_1 ,A_2 ,A_3 ,…,A_n -> B_1 ,B_2 ,B_3 ,…,B_n$成立，则$A_1 ,A_2 ,A_3 ,…,A_n ->-> B_1 ,B_2 ,B_3 ,…,B_n$成立
互补规则：如果关系上存在MVD$A_1 ,A_2 ,A_3 ,…,A_n ->-> B_1 ,B_2 ,B_3 ,…,B_n$，则必定存在$A_1 ,A_2 ,A_3 ,…,A_n ->-> C_1 ,C_2 ,C_3 ,…,C_n$.其中c是除a和b之外的其他元素

第四范式的概念及求解

第四范式条件本质上就是BCNF条件，但他应用于MVD而非FD。它主要是消除由MVD带来的冗余。

定义：如果对于R中每个非平凡MVD$A_1 ,A_2 ,A_3 ,…,A_n ->-> B_1 ,B_2 ,B_3 ,…,B_n$，其中A都是超键，则R属于第四范式。

第四方式的求解和BCNF类似，就是注意现在除了找FD（FD一定是MVD）之外还要找MVD

分解的优劣

例如：把R(A, B, C)分解成R1(A, B) 和 R2(B, C)，这种分解是否可以保证恢复到原始关系呢？

如果对于R中的两个实例a(1, 2, 3) 和 b(4, 2, 5)，则$\pi{A, B}(b) \pi{B,C}(a)$ = (4, 2) (2, 3)

之后对两个关系进行自然联结，结果为(4, 2, 3)，并不存在于原始关系中，也就是对于原始关系造成了损失。

但是如果B是主键，则为无损连接，因为B相同其他元素一定相同，这也就说明了BCNF范式可以通过自然联结无损回复到原始关系。

分解的好坏主要考虑三个性质：

消除异常(Elimination of Anomalie): 包括更新异常，删除异常，冗余
信息可恢复(Recoverability of Information): 也就是无损连接。可以从分解后的各个元组恢复原始关系
依赖保持(Preservation of Dependencies): 如果FD的投影在分解后的关系上成立，是否可以保证分解后的关系用连接冲过获取原始关系仍然满足原来的FD

如图所示，3NF不能有效消除异常，但是3NF可以同时满足无损连接和依赖保持。而BCNF和4NF不能同时满足无损连接和依赖保持性质

无损连接的chase检验

问题：假设将R分解成若干个关系，他们的属性集为S1, S2, S3… R上成立的FD集合为F. 能否通过这些分解关系的自然联结来恢复R？

一些性质

自然连接满足结合律和交换律。
自然连接后的每个结果属于R，R也要属于自然连接后的结果。也就是说两个集合要相等

大致过程：

首先建立一个表格，表格的行数为分解出的关系的数目，列数为总的属性的个数。每一行代表一个分解的属性集
初始化表格。一行行的填写，将该行关系中属性用小写字母填进去，而其他关系用小写字母加数字填进去（待会看例子就清楚了）
按照R的FD进行推导。例如FD： X->Y，如果两列在X上相同，那么在Y上一定相同
一直推导下去，知道某一行都是不带下标的小写字母

R(A, B, C, D) FD: A->B, B->C, CD->A。分解为三个关系,属性集分别为{A, D}, {A, C}, {B, C, D}

初始化，如果属性集中有，那么直接添加不带下标的小写字母，否则添加带下标的。带下标也就表示这个是不确定的。

属性集	A	B	C	D
{A, D}	a	$b_1$	$c_1$	d
{A, C}	a	$b_2$	c	$d_2$
{B, C, D}	a3	b	c	d

推导：

首先由 A->B可以推得a相同，b一定相同，因此b的符号要相同

属性集	A	B	C	D
{A, D}	a	$\mathbf{b_1}$	$c_1$	d
{A, C}	a	$\mathbf{b_1}$	c	$d_2$
{B, C, D}	$a_3$	b	c	d

B->C

属性集	A	B	C	D
{A, D}	a	$\mathbf{b_1}$	c	d
{A, C}	a	$\mathbf{b_1}$	c	$d_2$
{B, C, D}	$a_3$	b	c	d

CD->A

属性集	A	B	C	D
{A, D}	a	$B_1$	c	d
{A, C}	a	$b_1$	c	$d_2$
{B, C, D}	a	b	c	d

这时候我们可以看到第三行全部是小写字母了。