数据库期末

第六章

关系模式表示

五元组 R(U,D,DOM,F)

1. R是元组名（学生）
2. U为属性（学号，姓名，专业）
3. D为属性的域（整数，字符串，字符串）
4. DOM为属性到域的映射（001，李明，计算机）
5. F为属性上的数据依赖

数据依赖：

函数依赖（FD）

有R(U)，设X，Y为U的子集，若对于R(U)的任意一个可能的关系r，r中不可能存在两个元组在X上属性值相同，而在Y上属性值不同，称X->Y（X决定Y，Y依赖于X）

下表不属于函数依赖，因为两个元组学号相同但是姓名不同

学号	姓名
001	张三
001	李四

函数依赖类型：

1. 非平凡函数依赖
       X->Y，但Y⊊X，则称X->Y是非平凡函数依赖（本身推其他）

2. 平凡函数依赖
       X->Y，但Y⊆X，则称X->Y是平凡函数依赖（本身推本身）

---

1. 完全函数依赖
       如果X->Y，并且对于X的任意真子集X’，都有X’-/->Y，则称Y对X完全函数依赖，写做X-F>Y（若不存在子集则一定是完全函数依赖）

2. 部分函数依赖
        如果X->Y，但Y不完全依赖于X，则称Y对X部分函数依赖，记作X-P>Y

---

1. 传递函数依赖
           如果X->Y(Y⊊X)，Y-/->X，Y->Z(Z⊊Y)，则Z对X传递函数依赖，记作X-传递>Z

码（关键字，键）

1. 简单来说，给定一个属性值，能够确定一行，就是候选码（给定张三和李四，可以分别确定二者所在的一行）

学号	姓名	…
001	张三
002	李四

2. 若关系模式中有多个候选码，则选定其中的一个作为主码（一表一主码，主码可以为属性组）
3. 关系模式R中，属性或属性组X并非R的码，但X是另一个关系模式的码，则X为R的外码

范式

5NF C 4NF C 3NF C 2NF C 1NF

1NF

二维表符合每个分量是不可分开的数据项的关系模式属于第一范式(1对1，合并单元格不符合定义)

2NF

R∈1NF，且每个非主属性都完全函数依赖与任何一个候选码，则R∈2NF
    用于消除部分函数依赖

如何将1NF转化为2NF：
将部分函数依赖的非主属性单独建立一个表，然后加入一个码，使其与其他表联系起来

3NF

R∈1NF，若R中不存在码X、属性组Y以及非主属性Z，使得X->Y,Y->Z成立，则称R∈3NF
    用于消除传递依赖
   
如何消除传递依赖：
将含传递依赖的表拆开。如（Sno,Sdept,Sloc）中，Sno->Sdept，Sdept->Sloc，将Sdept和Sloc拆开，成为(Sno,Sdept)，(Sdept,Sloc)

BCNF

认为是修正的第三范式
若R∈1NF，若X->Y，且Y⊊X时X必含有码(候选码也可以)，则R∈BCNF
换言之，如果每一个决定属性集都属于候选码

多值依赖

在关系数据库中，假设 R(A, B, C) 是一个表，其中 A、B、C 是属性，多值依赖表示为：如果属性 A 确定了属性集 B 的值，并且同时 A 确定了另一个属性集 C 的值，那么在给定的 A 的条件下，B 和 C 彼此独立，且它们的值可以是多对多的关系，写作A->->B（一对多，比如（CTB，课程C，教师T，参考书B））

1. 平凡多值依赖
       A->->B，B含于A
2. 非平凡多值依赖
       否则称为非平凡多值依赖

4NF

对于每个非平凡多值依赖X->->Y，若X都含有码则符合第四范式
第四范式仅允许存在非平凡多值依赖且为函数依赖但关系

如何将多值依赖转化为4NF：
假设有关系WSC，W->->S,w->->C,都是非平凡多值依赖，且W不是码，WSC的码为(W,S,C)，可以将WSC分解为WS(W,S)，WC(W,C)此时WS和WC都属于第四范式

---

数据依赖的公理系统

逻辑蕴含

设，对于满足一组函数依赖F的关系模式R<U,F>，存在X->A,X->B，且根据已有的函数依赖可以推出X->A∩B，成为F逻辑蕴含X->A∩B

Armstrong公理系统

推理规则

通俗的写：【X】【Y】【Z】都代表关系模式的子集

1. 自反律：若Y是X的子集，则X→Y为F所蕴含
2. 增广律：如果X→Y为F所蕴含，则XZ→YZ（X∪Z→Y∪Z）
3. 传递律：如果X→Y，Y→Z为F所蕴含，则X→Z

根据上述三个规则可以推出以下规则

1. 合并规则：由X->Y，X->Z，则X->YZ
2. 伪传递规则：由X->Y，WY->Z，有XW->Z（替换）
3. 分解规则：由X->Y，Z∈Y，有X->Z

闭包

1. 函数依赖的闭包：
       在关系模式R<U,F>中F所逻辑蕴含的函数依赖的全体叫做F的闭包，记作F+
2. 属性的闭包：
       设F为属性集U上的一组函数依赖，X、Y∈U，X+F={A|X->A能由Armstrong公理推出}，X+F称为属性集X关于函数依赖集F的闭包，即指所有能由X决定的属性集合

候选码的求解方法

属性的分类

1. L：仅出现在函数依赖集F左部的属性
2. R：…右部…
3. LR：…左右都出现…
4. N：…左右都未出现…

根据上述有以下结论：

1. 若X是L类属性，则X必为R的任意候选码的成员（必定有一个候选码包含X）。若X+F=U，则X必为R的唯一候选码
2. 若X是R类属性，则X不是R的任一候选码成员
3. 若X是N类属性，则X必为R的任一候选码成员

求解方法

1. 将所有属性分类
2. 将所有L类和N类属性组合起来，设为P，求其闭包P+F，如果是全集U，则为候选码
3. 如果不是全集U，则依次将LR类属性跟P组合起来求闭包，只要闭包是全集U，则为候选码

最小函数依赖集

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

1. F中的任一函数依赖的右部仅有一个属性，即无多余的属性
2. F中不存在这样的函数依赖X→A,使得F与F-{X-→A}等价，即无多余的函数依赖
3. F中不存在这样的函数依赖X→A,X有真子集Z使得F与F-{X→A]U{Z→A]等价，即去掉各函数依赖左边的多余属性。
   即：
   (1)所有函数依赖的右侧只有一个属性。
   (2)没有冗余的函数依赖。
   (3)所有函数依赖的左侧没有冗余的属性。

最小函数依赖:右拆单，逐个删。能推右，立即移。左非单，删一左求另一包，推出就真删。

模式分解

第七章——数据库设计

三个步骤：

1. 概念设计——ER图
2. 逻辑设计——确定关系模式
3. 物理设计

概念设计和逻辑设计

1. 实体(矩形表示)：现实中客观存在的
 2. 属性(椭圆表示)：每个实体固有的属性和特征
 3. 联系(菱形表示)：实体和实体间的联系
   4. 关系
1. 一对一![[一对一ER图.png]]
    2. 一对多![[一对多ER图.png]]对多端的关系模式来说，一端的主码需要放到多端合成关系模式；联系若有属性，则该属性需要放入多端才能合成关系模式
      3. 多对多![[多对多ER图.png]]联系需要取多端的主码+自己本身的属性才能合成关系模式

物理设计

数据库的物理设计是指为了将数据库的逻辑模型在计算机的物理存储设备上实现，如何组织和存取数据，以建立起一个既节省存储空间，又有较高存取速度、性能良好的物理数据库。

物理结构设计主要包括:

1. 确定数据的存储结构(逻辑设计→物理设计)
2. 确定存储方法
3. 确定存取方法
4. 确定数据的存取路径

MySQL语句

建表

create table tbl_1
(姓名 varchar(10) primary key not null
 学号 char(10)，
 成绩 int,
 选修课程号 char(10),
 性别 CHAR(1) CHECK (性别 IN ('M', 'F'))
 ///primary key(学号)，
 foreign key(选修课程号) references tbl_2(课程号)  //外码为tbl_2的课程号
)

列级完整性约束

primary key  //主码
not null  //非空
unique  //唯一值，该列属性只能取唯一值
check(条件)  //检查是否满足条件

表级完整性约束

primary key(列名1，列名2)
foreign key(列名1) references tbl_name(列名1)

select查询

一般格式

select distinct/all 目标列表达式    //要显示的属性列  distinct去掉重复列，默认为all
from 表名/视图名    //要查询的对象
where 条件表达式    //查询条件
group by 列名 having 条件表达式    //查询结果分组
order by 列名 次序    //最终查询结果排序  asc升序 desc降序

聚集函数（只能用在select后或group by的having字句 ）

count(* )   //统计元组个数（多少行）
count(distinct/all 列名)  //统计某一列值的个数（多少行）
avg(distinct/all 列名)  //计算某一列的平均数（必须为数值型）
sum(distinct/all 列名)  //计算某一列的总和（必须为数值型）
max/min(distinct/all 列名)  //计算某一列最大/最小值

where条件表达式

比较大小
where 列名 (not) between 最小值 and 最大值  //确定范围
where 列名 (not) in (‘列名1’,‘列名n’)  //判断某个字段值是否属于一个集合中的元素
    eg.在SC表的dept列查找属于cs，ma专业的学生的姓名
    select s.name
    from sc
    where dept in (‘cs’,‘ma’)
        等价于dept=‘cs’ or dept=‘ma’
where 列名 is (not) null  //查询为空/不为空的值

GROUP BY … HAVING …

group by 列名    //SELECT 中出现的列（除了聚集函数里的），必须出现在 GROUP BY 中
    eg.求SC表中，各个课程号Cno下相应的选课人数Sno
    select Con,COUNT(Sno)
    from SC
    group by Cno;  //表示具有相同的Cno值的元组为一组，对每组用COUNT，得每组的人数

group by 列名 having 筛选条件    //having用于从组中选择符合条件的组
    eg.在SC表中查询平均成绩大于等于90的学生学号Sno和平均成绩Grade （求平均成绩要先按照      学号分组，使每个学生的不同科的成绩成一组然后再求平均）
    select Sno，Grade
    from SC
    group by Sno
    having avg（Grade）>=90

ORDER BY

order by 列名 ASC/DESC  //以列名升/降序

触发器

CREATE TRIGGER 触发器名
{BEFORE | AFTER} {INSERT | UPDATE | DELETE}
ON 表名
FOR EACH ROW
BEGIN
   -- 要执行的SQL语句,被修改的数据需要添加old/new
END;

关键字	使用场景	含义
OLD	DELETE, UPDATE	表示修改之前的那一行
NEW	INSERT, UPDATE	表示插入/修改之后的那一行

第十章——查询优化处理

顺序:

1. 写出查询要求的SQL语句
2. 写出查询要求的关系代数表达式
3. 画出用关系代数表示的语法树
4. 画出优化后的标准语法树

例题见学习通作业第十章

第十一章——数据库恢复

故障前发生的，已经提交的事务重做(redo)，未提交的撤销(undo)
eg.

序号	日志	序号	日志
1	<T1 start>	8	<T2 commit>
2	<T1, A, 20, 50>	9	<T3, B, 50, 60>
3	<T2 start>	10	<T4 start>
4	<T2, B, 60, 70>	11	<T4, A, 50, 40>
5	<T3 start>	12	<T4, C, 100, 120>
6	<T3, A, 50, 55>	13	<T4 commit>
7	<T2, C, 80, 90>

若系统在13之后崩溃，请判断那些事务需要重做，哪些需要撤销，并写出恢复后变量的值
redo:T2 T4  //崩溃前已提交
undo:T1 T3  //崩溃前未提交
ABC分别为40 70 120

做题思路：确定好redo和undo之后，直接从头遍历一遍redo的事务，得到确定的变量值，然后找undo的事务，然后再确定剩余变量值

第十二章——并发控制/事务调度

封锁

X锁/排他锁：某事务上锁后，只有该事务可读取和修改该数据对象，其他事务不可再对该数据对象上锁。Xlock()上锁，Unlock()释放锁

S锁/共享锁：某事务上锁后，可读取但不可修改该数据对象，其他事务可以对该数据添加S锁但不能添加X锁。Slock()上锁，Unlock()释放锁

封锁协议

一级封锁协议：写前加写锁，事务结束释放写锁，，可防止丢失修改

二级封锁协议：写前加写锁，读前加读锁，读完释放读锁，事务完成释放写锁，防止丢失修改和读取脏数据

三级封锁协议：写前加写锁，读前加读锁，事务结束后释放各锁，可防止丢失修改，读脏数据和不可重复读

如果所有事务均遵守三级封锁协议，由于其隔离级别高，无论怎么交叉并行，都是可串行化调度

两段锁协议

两阶段锁协议是一种用于保证事务并发执行时一致性和隔离性的方法。
它将事务分为两个阶段：加锁阶段和解锁阶段。
在加锁阶段，事务可以申请任意数量的锁，但在解锁阶段，事务不能再申请新的锁，只能释放已持有的锁。这样可以确保事务在执行过程中不会出现死锁

例题

例一

T1	T2
X = Read(A);
Y = Read(B);
	X = Read(A);
	X = X - 10;
X = X + Y;
	Write(A, X);
	Y = Read(B);
Write(A, X);
	Y = Y * X;
	Write(B, Y);

右图所示为两个事务 T1 和 T2 的一个并发调度。其中，数据项 A 的初值为 20，B 的初值为 10。变量 X、Y 为事务中的局部变量。语句：
 X = Read(A); 表示读取数据项 A 的值到变量 X
Write(A, X); 表示将变量 X 的值写入数据项 A 中

注意：AB为数据项，是全局变量，XY是事务的局部变量，互相独立

T1T2并行：A=30，B=100
T1T2串行：T1->T2：A=20,B=200
          T2->T1：A=110,B=100
并行串行结果不一样，所以T1T2不是可串行调度

例二

今有三个事务的一个调度r3(B)r1(A)w3(B)r2(B)r2(A)w2(B)r1(B)w1(A)，该调度是冲突可串行化的调度吗？为什么？

步骤：交换非冲突操作，构造一个串行调度
冲突操作：当两个事务操作相同数据项且 至少有一个是写操作时冲突

例如
r1(A) 和 w2(A) → 冲突
r1(A) 和 r2(A) → 不冲突
w1(A) 和 w2(A) → 冲突

我们一步步把 r1(A) 向后移动，每次只交换与之不冲突的操作，最终构成
r3(B) w3(B) r2(B) r2(A) w2(B) r1(A) r1(B) w1(A)
T3->T2->T1，是冲突可串行化调度