数据库系统原理

发表于 2021-06-18 分类于 CS ， Exam Waline：

本文字数： 5.1k 阅读时长 ≈ 5 分钟

理论

求属性集X关于F的闭包$X_F^+$

闭包就是X可以推出来的属性集合，最开始只有X（X也是属性集，不一定是单个属性）

如果F里存在$X\rightarrow Y$，那么就可以把Y加进来，现在就是$X \cup Y$，然后如果有$Y \rightarrow Z$，那么Z也可以加进来了。

不断重复，最后没有新的属性可以加入时结束。

求最小依赖集（最小覆盖）$F_m$

对于F里的数依赖：

如果有类似于$X \rightarrow A_1 A_2...A_n$，也就是右边有多项的，就分成$X \rightarrow A_1$，$X \rightarrow A_2$...。
简记为分右（把右边分开）
如果有$X\rightarrow B$，$B\rightarrow C$，$C\rightarrow A$，那么$C\rightarrow A$显然就是多余的，可以去掉。但是有时这样的传递依赖不好看出来，所以可以先尝试把$C \rightarrow A$从F里去掉，然后看还能不能由C推出来A。规范的做法是：
记$G=F - \{ C \rightarrow A \}$，然后求C在G上的闭包$C^+_G$，如果$A \in G_G^+$，那么说明C还是可以推出A，$C \rightarrow A$的确是多余的，可以去掉。
F里的每个依赖都这么过一遍。
简记为去传（去除传递依赖）
如果有$B_1B_2...B_n \rightarrow A$，那么左边这些B可能有多余的，比如尝试把$B_1$去掉，就要看现在$B_2B_3...B_n$还能不能推出A，如果能的话，就真的可以去掉$B_1$。规范做法是：
求出去掉$B_1$后的闭包$(B_2B_3...B_n)_F^+$，如果$A \in (B_2B_3...B_n)_F^+$，那么就可以去掉$B_1$。
其它几个B也要这样过一遍。
简记为分去左（把左边分开再去掉）

求候选码

候选码K是属性集，并且$K\stackrel{F}{\rightarrow} U$。K里的属性就都是主属性。
如果是$K\stackrel{P}{\rightarrow} U$，那么K是超码。

给定关系R和函数依赖集F，首先把其中属性分成四类：

L类，只在函数依赖的左边出现的属性
R类，只在函数依赖的右边出现的属性
LR类，在函数依赖的左边和右边都出现了的属性
N类，没有在函数依赖里的属性

L类和N类属性都一定是在候选码里的，先尝试求闭包$(L \cup N)_F^+$

如果这个闭包里已经包含了所有属性了，那么候选码就是这个L和N的并集。

否则就把LR里的属性逐个加进来，再求闭包，看是否包含所有属性，是的话那就候选码就是L和N的并集再加上这个属性。要是还不行，就再多加几个属性，尝试所有组合（注意L和N开始就已经算进来了，R里的是一定不需要组合进来的）。

最后候选码也可能有多个。

求模式分解

保持函数依赖，可达3NF，不一定是BCNF
保持函数依赖又具有无损连接性，可达3NF，不一定是BCNF
具有无损连接性，可达4NF

三个算法，书上P198。

需要注意的是，第三个算法（分解法）在每次分解之后都要重新求各子的码！

判断分解的无损连接性

比如关系R，函数依赖集F，属性集$U=\{U_1,U_2..,U_n \}$被分解成了$R_1,R_2..R_n$。

先画表格：

	$U_1$	$U_2$	...	$U_n$
$R_1$
$R_2$
...
$R_n$

然后填表格：对于$i$行$j$列的格子，如果$U_j \in R_i$，那么就填入 $a_j$ ，否则填入$b_{ij}$。

最后更新表格：对于F里的每个函数依赖，比如$X_1X_2...X_n \rightarrow Y$，先找到$X_1X_2...X_n$对应的列，在表格里看有没有这几列都相同的行。

如果有的话，就看这几行的Y列：

要是这几行的Y列里有a，那就全部改成a（下标是Y对应的列号）
否则全部改成b（第一个下标是这些行的最小行号，第二个是Y的列号）

要是找不到这几行就算了，然后检查表格：

如果表格里出现了一行全是a的，那么就说明此分解具有无损连接性。
如果对F的每个函数依赖对处理一遍后表格没变，那就可以结束了，否则再继续更新。

快速判断二元分解的无损连接性

R分解为了$R_1$和$R_2$，对应属性集为$U_1$和$U_2$。这个分解具有无损连接性的充要条件是：
函数依赖$U_1 \cap U_2 \rightarrow U_1-U_2$或者$U_1 \cap U_2 \rightarrow U_2-U_1$属于$F^+$。

比如：U={A,B,C},F={A→B}，分解为$U_1$=AB和$U_2$=BC

那么$U_1 \cap U_2 ={B}$，$U_1-U_2={A}$, $U_2-U_1={C}$，但是$BA $和$BC $都不在$F^+$里（这里只有$AB$），所以此分解有损。

证明Armstrong公理有效性（正确）

证明F根据Armstrong公理推出的一定都在闭包$F^+$里，也就是证明A1,A2,A3的正确性。主要是靠一条定理，比如要证$X \rightarrow Y$成立，就证明“如果t[X]=s[X]，则t[Y]=s[Y]”就可以了。

具体来说是，对R<U,F>中任一关系r的任意两个元组t，s：

证明自反率：
若t[X]=s[X]，由于$Y \subseteq X$，所以必有t[Y]=s[Y]，因此$X \rightarrow Y$为$F^+$所蕴含。
证明增广率：
若t[XZ]=s[XZ]，则t[X]=s[X]且t[Z]=s[Z]，由于有$X \rightarrow Y$，所以有t[Y]=s[Y]，也就有t[YZ]=s[YZ]，因此$XZ \rightarrow YZ$为$F^+$所蕴含。
证明传递率：
若t[XZ]=s[XZ]，由于$X \rightarrow Y$，所以有t[Y]=s[Y]，又由于$Y \rightarrow Z$，所以有t[Z]=s[Z]，所以$X \rightarrow Z$为$F^+$所蕴含。

证毕。

证明Armstrong公理完备性（够用）

证明$F^+$中每一个函数依赖都可以由F根据Armstrong公理推导出来。一般是证明其逆否：若$X \rightarrow Y$不能由F...推导出来，则一定不为$F^+$所蕴含。

书上P192，定理6.2。

依赖闭包相互覆盖（等价）的证明

证明$F^+=G^+$，思路就是根据给定条件去证明$F^+\subseteq G^+$和$G^+\subseteq F^+$。

$G\subseteq F^+$，则$X^+_G \subseteq X_F^+$
任取$X\rightarrow Y\in G^+$，则有$Y\subseteq X^+_G\subseteq X_{F^+}^+$，所以$X\rightarrow Y\in(F^+)^+=F^+$，所以$G^+\subseteq F^+$

同理可证$F^+\subseteq G^+$。

范式相关证明

1NF：R里每个分量都是不可分的数据项
2NF：$R\in 1NF$，并且每个非主属性完全函数依赖于任何一个候选码
3NF：$R\in 1NF$，并且不存在码X，属性组Y($Y \nrightarrow X$)和非主属性Z($Z\notin Y$)，使得$XY $，$YZ$
BCNF：$R\in 1NF$，并且若$X\rightarrow Y$($Y \notin X$)时X必含有码

3NF一定是2NF

假设不为2NF，则存在$X\stackrel{P}{\rightarrow}Y$，所以存在X的真子集$X^{'}$，$X^{'}\rightarrow Y$。

又因为显然有$X\rightarrow X'$，且$X' \nrightarrow X$

所以由$X\rightarrow X'$，$X'\rightarrow Y$，可知存在传递依赖于码，与满足3NF矛盾，假设不成立。

所以一定是2NF。

2NF不一定是3NF

举例：Sinfo(Sno, Sdept, Sloc)，有Sno→Sdept，Sno→Sloc，Sdept→Sloc，码为Sno，显然是2NF。但存在传递函数依赖于码，所以不是3NF。

BCNF一定是3NF

假设不为3NF，则存在$X\rightarrow Y$（$Y\nrightarrow X$），$Y\rightarrow Z$（$Z\notin Y$），其中X为码，Y为任意属性组，Z是非主属性。

因为$Y\nrightarrow X$，所以Y中不含码，但$Y\rightarrow Z$，与满足BCNF矛盾，假设不成立。

所以一定是3NF。

3NF不一定是BCNF

举例：$A \leftrightarrow B$（两条依赖合并写了），$(A,C)\rightarrow D$，$(B,C)\rightarrow D$，显然是3NF，但是码为ABC，$A \leftrightarrow B$其中都不包含码，所以不是BCNF。

任何二目关系都是3NF和BCNF

设R(A,B)

A或者B是码，不妨假设A是码，则$F={A\rightarrow B}$，显然3NF且BCNF
(A,B)是码，则$F={(A,B)\rightarrow (A,B)}$，同样显然

仅一个候选码的3NF是BCNF的

R必为$R(K,A_1,A_2...)$，K是唯一候选码，则$F={K\rightarrow A_1, K\rightarrow A_2...}$，显然。

全码是3NF和BCNF的

$F={(A_1,A_2...)\rightarrow (A_1,A_2...)}$，显然。

SQL

视图&授权

--增删查改自己管理的学生
create view V1 as
    select * from Students
    where leader = user
with check option

grant select, update, insert, delete
on V1
to public

触发器

create trigger OnDeleteWriteLog on Students for delete as
    insert into StuDeleteLog
        select user, getdate(), Sno, Sname
        from deleted

-- 如果是update或insert，可以用inserted获取插入的数据

函数

create function MyAdd(@i int, @j int) returns int as begin
    return @i + @j
end

--调用
dbo.MyAdd(1, 2)

存储过程

create procedure PrintStuInfo(@Sdept varchar(10) ='CS') as begin
    select * from Students
    where Sdept = @Sdept
end

-- 调用
execute PrintStuInfo 'IS'

游标

declare @Sno char(20), @Sname char(20)

declare cur1 cursor for select Sno, Sname from Students
open cur1

fetch next from cur1 into @Sno, @Sname
while(@@fetch_status = 0) begin
    declare @output char(max)
    set @output = '学号:' + @Sno + ',姓名:' + @Sname
    print @output

    fetch next from cur1 into @Sno, @Sname
end
close cur1; deallocate cur1;

系统函数

--子串
substring('第三12', 2, 2) = '三1'

--随机抽取3个
select top 3 * from Students order by newid()

参考

[1] 数据库系统概论（第5版） - 王珊、萨师煊

	\(U_1\)	\(U_2\)	...	\(U_n\)
\(R_1\)
\(R_2\)
...
\(R_n\)

Vulxin's Blog