[学习笔记] - 数据库系统

Everything Over DB

            graph LR
            离散数学-->数据结构;
数据结构--内存中操作-->数据库系统;
离散数学--应用-->数据库系统;

仅为个人笔记，因为已经实际使用过很多数据库了，这里系统的过一遍

什么是数据库

定义：将信息规范化并使之电子化，形成电子信息库，以便利用计算机对这些信息进行快速有效的存储、检索、统计与管理

数据库是电子化信息的集合

            graph LR
            数据库--管理数据库的一种系统软件-->数据库管理系统;
数据库管理系统-->数据库应用程序;

Schema（模式）

对数据库中数据所进行的一种结构性的描述所观察到的数据的结构信息

三层模式
- External Schema
  - External View
  - 某一用户能够看到与处理的数据的结构描述
- Conceptual Schema
  - Conceptual View
  - 从全局角度理解/管理数据的结构描述，含相应的关联约束体现在数据之间的内在本质联系
- Internal Schema
  - Internal View
  - 储存在介质上的数据的结构描述，含存储路径，存储方式，索引方式等
两层映像
- E-C Mapping
  - 将外模式映射位概念模式，从而支持实现数据概念视图向外部视图的转换
- C-I Mapping
  - 将概念模式映射位内模式，从而支持实现数据概念视图向内部视图的转换

            graph TD
            External-View-A--External-Conceptual丨MappingA-->Global-View
External-View-B--External-Conceptual丨MappingB-->Global-View
Global-View--Conceptual-Internal丨Mapping-->Internal-Schema
subgraph Internal View
Internal-Schema--Conceptual-Internal丨Mapping-->Stored-Database
end

三层模式，两层映像实现了逻辑独立性+物理独立性（和设计软件一个意思）

数据模型

规定模式统一描述方式的模型，包括：数据结构，操作和约束
数据模型是对模型本身结构的抽象，模式是对数据本身结构形式的抽象

            graph LR
            关系模型-->模式;
Table-->具体表;

三大模型
- 关系模型
  - 表
- 层次模型
  - 树
- 网状图形
  - 图

数据库类型

关系数据库
- 按行按列形式组织数据
- 数据项的不可再分特性
- 关系运算
  - 关系代数
  - 元组演算
  - 域演算
- 关系数据库设计理论
面向对象数据库
- 面向对象技术与集合/聚集操作技术的结合
- 支持复制的数据类型，数据封装与抽象数据结构
- 支持面向对象的一些特性：类、继承、封装、多态
XML数据库
- XML文件（HTML）

关系模型

            graph LR
            关系--概念实际---表;
subgraph Relation
关系-->域和域值
关系-->元组
关系-->笛卡尔积
关系-->关系模式
关系-->属性与属性值
end
subgraph Table
表-->表丨标题
表-->列名与列值
表-->行丨记录
end

一个关系就是一个Table
关系模型就是处理Table的，它由三个部分组成
- 描述DB各种数据基本结构形式
- 描述Table与Table之间所可能发生的各种操作
- 描述这些操作所应遵循的约束条件（完整性约束）

关系

域：一组值的集合，这组值具有相同的数据类型
关系：
- 一组域 $D_1, D_2, \cdots, D_n$ 的笛卡尔积的子集
- 具有意某一方面义的组合称为一个关系
- 关系的不同列可能来自同一个域。为区分起名记为属性名

关系可用

R(A_1:D_1, A_2:D_2,\cdots,A_n:D_n)

表示，这种描述又被称为关系模式，如：家庭(丈夫:男人, 妻子:女人, 子女:儿童)
关系模式中属性向域的映象在很多DBMS中一般直接说明为属性的内心、长度（例：SQL定义数据库）

关系模式与关系
- 同一关系模式下，可能有很多的关系
- 关系模式是关系的结构，关系是关系模式在某一时刻的数据
- 关系模式是稳定的，而关系是某一时刻的值，是随时间可能变化的

关系的一些概念

候选码：关系中的一个属性组，其值能够唯一标识一个元组，若从该属性组中去掉任意一个属性，他就不具有这一性质了
主键：当有多个候选码时，可以选定一个作为主键
主属性：包含在任何一个候选码中的属性被称作主属性，而其他属性被称作非主属性
外键(Forgign Key)：关系R中的一个属性组，他不是R的候选码，但它与另外一个关系S的候选码相对应，则称这个属性组为R的外码（可以参考Django等MVC框架里面的模型的关系外键）

关系模型的完整性

实体完整性：候选码/主键
- 关系的主码中的属性值不能为空值
  - 空值：不知道或无意义的值
参照完整性：外键
- 如果关系R1的外码FK与关系R2的主码Pk相对应，则R1中的每一个元组Fk值或者等于R2中某一个元组的Pk值，或者为空值
用户自定义完整性：属性与属性组合
- 用户针对具体的应用环境定义的完整性约束条件

关系代数的基本操作

关系元组演算是以元组变量作为谓词变量的基本对象
所有使谓词P为真的元组x的集合

\lbrace x | P(x) \rbrace

三种原子公式
- $s \in R$
- $s[A] ? c$
- $s[A] ? s[B]$
- 可以参考离散数学

关系域演算是以域变量作为谓词变量的基本对象

\lbrace x_1, x_2, \cdots, x_n \rbrace | P(x_1, x_2, \cdots, x_n)

并相容性

参与运算的两个关系及其相关属性之间有一定的对应性，对可比或意义关联性
定义：关系R与关系S存在相容性，当且仅当

关系R和关系S的属性数目相同
对于任意 $i$ ，关系R的第 $i$ 个属性的域必须和关系D的第 $i$ 个属性的域相同

并（Union）

定义：假设关系R和关系S时并相容的，则关系R域关系S的并运算结果也是一个关系（就是集合的并 $R \cup S$ ）

差（Difference）

定义： $R - S = \lbrace r | r \in R \text{且} r \notin S \rbrace$

广义积（Cartesian Product）

定义： $R \times S$ ，关系R中的元组与关系S中的元组的进行所有的组合的结果

选择（Select）

定义： $\sigma_{com} = \lbrace x | x \in R \cap con(x) = True \rbrace$

投影（Project）

定义：给定一个关系R，投影运算结果也是一个关系，基座 $\prod_A(R)$ ，它从关系R中选出属性包含在A中的列构成

就是选出几列形成一个新的关系，但是要消除重复的行

交（Intersection）

定义： $R \cap S = \lbrace x | x \in R \cap t \in S \rbrace$

连接（Join）

定义：给定关系R和关系S，R与S的连接运算结果也是一个关系，它由关系R和关系S的广义积中，选取R中属性A与S中属性B之间满足 $\theta$ 条件的元组构成

就是进行有条件的广义积

自然连接（Natural-Join）

定义：给定关系R和关系S，R与S的连接运算结果也是一个关系，它由关系R和关系S的广义积中，它由关系R和关系S的广义积中选取相同属性组B上值相等的元组所构成

除（Division）

条件：给定关系R是n度关系和关系S是m度关系，若能进行除运算，则S的属性集为R的属性的真子集
定义：结果剩余R中S没有的属性，且剩余的每一个元组，与S进行组合后的元组，都属于R

\forall i \in (R/S \times S) \rightarrow i \in R

查询选修了全部的课程的同学

外连接（Outer-Join）

\text{外连接} = \text{自然连接} + \text{失陪的元组}

左外连接： $= \text{自然连接} + \text{左侧失陪的元组}$
右外连接： $= \text{自然连接} + \text{右侧失陪的元组}$
全外连接： $= \text{自然连接} + \text{两侧失陪的元组}$

列出所有老师的所教课程和信息，且不丢失信息（不匹配）

例子

1
2
3

Student(id, name, age, sex, class)
Course(id, name, hours, redit, teacher)
SC(Student_id, Course_id, score)

            graph LR
            老师--一对多-->课程1
老师--一对多-->课程2
课程1--多对多---学生A
课程2--多对多---学生A
课程2--多对多---学生B

求学过某老师讲授所有课程的学生姓名

\pi_{Student.name}(\frac{\prod(Student, SC, Course)}{Course.teacher == x})

求没有学过某老师讲授的课程的学生姓名

\pi_{Student.name}(Student) - \sigma_{(Course.teacher == x)}(\prod(Student, SC, Course))

求至少学过一门老师讲授的课程的学生姓名

\pi_{Student.name}(\sigma_{(Course.teacher == x)}(\prod(Student, SC, Course)))

求至少没学过一门老师讲授的课程的学生姓名

\pi_{Student.name}(Student) - \pi_{Student.name}(\frac{\prod(Student, SC, Course)}{Course.teacher == x})

关系运算的安全性

不产生无限关系和无穷运算的运算被称为使安全的

需要对关系演算世家约束条件，即任何公式都在一个集合范围内操作，而不是无限范围，才能保证其安全性

SQL语句

CREATE TABLE "student" (
 "id"     INTEGER NOT NULL,
 "name"   VARCHAR(10),
 "sex"    VARCHAR(2),
 "age"    INTEGER,
 "dept_id"  VARCHAR(2),
 "class"  VARCHAR(6),
 PRIMARY  KEY("id")
);

CREATE TABLE "course" (
 "id"          INTEGER NOT NULL,,
 "name"        INTEGER,
 "hours"       INTEGER,
 "credit"      FLOAT(1),
 "teacher_id"  INTEGER,
);

CREATE TABLE "student_course_score" (
 "srudent_id"  INTEGER,
 "course_id"   INTEGER,
 "score"       INTEGER,
);

CREATE TABLE "teacher" (
 "id"     INTEGER,
 "name"   INTEGER,
 "dept_id"  VARCHAR(2),
 "salary" INTEGER,
);

-- 查询student表中所有的数据
SELECT * FROM student;
-- 查询student表中姓名和年龄
SELECT name, age FROM student;
-- 查询student表中姓名和年龄且小于18岁
SELECT name, age FROM student WHERE age < 18;
-- 查询学过1号课程或2号课程的学生的学号
SELECT DISTINCT srudent_id FROM student_course_score
WHERE course_id = 1 OR course_id = 2;
-- 按照学号升序输出姓名和学号
SELECT name, id FROM student ORDER BY id ASC;

模糊查询

%：匹配零个或多个字符
_：匹配任意单个字符
\：转移字符

SELECT name, age FROM student WHERE name LIKE `李%`;
SELECT name, age FROM student WHERE name NOT LIKE `李%`;
-- 2个下划线表示一个汉字
SELECT name, age FROM student WHERE name LIKE `李____`;

多表联合查询

-- 按1号课程的成绩降序输出学生姓名（2表查询）
SELECT name FROM student, student_course_score
WHERE (student.id = student_course_score.srudent_id)
AND student_course_score.course_id = 1
ORDER BY student_course_score.score DESC;

-- 按照`数据库`课的成绩降序输出学生姓名
SELECT name FROM student, student_course_score, course
WHERE (student.id = student_course_score.srudent_id)
AND (student_course_score.course_id = course.id)
AND (course.name = `数据库`)
ORDER BY student_course_score.score DESC;

-- 求薪水不同的任意2位教师（对同一个表）
SELECT t1.name as teacher1, t2.name as teacher2 FROM teacher t1, teacher t2
WHERE t1.salary > t2.salary;

-- 求1号课程成绩不同的任意2位同学
SELECT sc1.name, sc2.name  FROM student_course_score sc1, student_course_score sc2
WHERE sc1.course_id = sc2.course_id
AND sc1.score > sc2.score
AND sc1.course_id = 1;

-- 求学过1号课程和2号课程的学生的学号
SELECT sc1.id FROM student_course_score sc1, student_course_score sc2
WHERE sc1.srudent_id = sc2.srudent_id
AND s1.course_id == 1
AND s2.course_id == 2;

-- 求1号课程比2号课程成绩高的学生的学号
SELECT sc1.id FROM student_course_score sc1, student_course_score sc2
WHERE sc1.srudent_id = sc2.srudent_id
AND s1.course_id == 1
AND s2.course_id == 2
AND s1.score > s2.score;

选择插入

1 2	INSERT INTO St (id, name) SELECT `id`, `name` FROM student WHERE name LIKE `李%`;

子查询

集合成员资格
- 某一元素是否是某一个集合的成员
集合之间的比较
- 某一个集合是否包含另一个集合
集合基数的测试
- 测试集合是否为空
- 测试集合是否存在重复元组

IN子查询

-- 列出A，B两位同学的所有信息
SELECT * FROM student WHERE name IN (`A`, `B`);

-- 列出选修了1号课程的学生的学号和姓名
SELECT id, name FROM student WHERE id IN
(SELECT student_id FROM student_course_score WHERE course_id = 1);

-- 求学过1号课程和2号课程的学生的学号
SELECT student_id FROM student_course_score
WHERE course_id = 1 AND srudent_id IN
(SELECT student_id WHERE course_id = 2)

-- 求没学过某老师的课程的所有学生的姓名
SELECT name FROM student
WHERE id NOT IN
(SELECT student_id FROM student_course_score sc, course c, teacher t
WHERE t.name = 'x' AND sc.course_id = c.id AND t.id = c.teacher_id)

子查询分外层查询和内层查询

非相关子查询
- 内层查询独立进行，没用设计任何外层查询相关信息的子查询
相关子查询
- 内层查询依靠外层查询的某些参量作为限定条件才能进行的查询

相关子查询只能由外层向内存传递参数，称为变量的作用域原则

-- 列出选修了1号课程的学生的姓名
SELECT name FROM student s WHERE id IN
(SELECT student_id FROM student_course_score WHERE
course_id = 1 AND s.id = student_id);

some all子查询

\begin{aligned} \text{表达式}\ \theta&\ some\ (\text{子查询}) \\ \text{表达式}\ \theta&\ all\ (\text{子查询}) \end{aligned}

如果表达式的值至少与子查询结果的某一个值相比较满足 $\theta$ 关系，则表达式 $\theta\ some$ 的结果便为真
如果表达式的值与子查询所有结果相比较满足 $\theta$ 关系，则表达式 $\theta\ all$ 的结果便为真

-- 找出工资最低教师名字
SELECT name FROM teacher
WHERE salary <= all(SELECT salary FROM teacher);

-- 找出1号课程成绩不是最高的所有学生学号
SELECT srudent_id FROM student_course_score
WHERE course_id = 1
AND score < some(SELECT score FROM student_course_score WHERE course_id = 1);

-- 找出所有课程成绩都不及格的学生姓名
SELECT name FROM student s
WHERE 60 > all(SELECT score FROM student_course_score sc WHERE s.id = sc.id);

-- 找出1号课程成绩最高的学生学号
SELECT id FROM student_course_score
WHERE course_id = 1
AND score >= all(SELECT score FROM student_course_score WHERE course_id = 1)

-- 找出学号1的学生成绩最低的课程号
SELECT course_id FROM student_course_score
WHERE student_id = 1
AND score <= all(SELECT score FROM student_course_score WHERE student_id = 1)

-- 找出x的学生成绩最低的课程号
SELECT course_id FROM student_course_score sc, student s
WHERE s.id = sc.student_id AND s.name = `x`
AND score <= all(SELECT score FROM student_course_score WHERE student_id = sc.student_id)

下面的表达方式是等价的

\begin{aligned} \text{表达式}\ \theta& = \ some(\text{子查询}) \\ \text{表达式}\ \theta& \ \text{IN}\ (\text{子查询}) \end{aligned}

\begin{aligned} \text{表达式}\ \theta& \text{<>} \ all(\text{子查询}) \\ \text{表达式}\ \theta& \text{NOT}\ \text{IN}\ (\text{子查询}) \end{aligned}

exists子查询

意义：子查询结果中有无元组存在

\text{EXISTS}\ (\text{子查询})

-- 列出选修了x老师主讲课程的所有同学的姓名
SELECT DISTINCT name FROM student s
WHERE EXISTS (SELECT * from student_course_score sc, course c, teacher t)
WHERE sc.course_id = course.id
AND sc.student_id = s.id
AND c.teacher = t.id
AND t.name = `x`);
-- 等价于
SELECT DISTINCT name FROM student s, student_course_score sc, course c, teacher t
WHERE sc.course_id = course.id
AND sc.student_id = s.id
AND c.teacher = t.id
AND t.name = `x`);

-- 列出选修了所有1号老师主讲课程的所有同学的姓名
-- 不存在有一门1号老师的课程该同学没有学过
SELECT name FROM student s
WHERE NOT EXISTS ( -- 不存在
  SELECT * FROM course c
  WHERE c.teacher_id = 1 AND NOT EXISTS -- 有一门1号老师的课程
  (
    SELECT * FROM student_course_score sc
    WHERE sc.student_id = s.id AND sc.course_id = c.id -- 该同学没有学过
  )
)

-- 列出没有选修任何一门x老师主讲课程的所有同学的姓名
-- 不存在有一门x老师的课程该同学学过
SELECT name FROM student s
WHERE NOT EXISTS (
  SELECT * FROM course c, student_course_score sc, teacher t
  WHERE c.teacher_id = t.id
  AND t.name = `x`
  AND sc.student_id = s.id
  AND sc.course_id = c.id
);

-- 列出学过1号同学所属学过所有课程的同学的学号
-- 不存在有一门1号同学所属学过的课程该同学没有学过
SELECT student_id FROM student_course_score sc1
WHERE NOT EXISTS ( -- 不存在
  SELECT * FROM student_course_score sc2
  WHERE sc2.student_id = 1 AND NOT EXISTS -- 1号同学所属学过的课程
  (
    SELECT * FROM student_course_score sc
    WHERE sc.course_id = sc2.course_id AND sc.student_id = sc1.srudent_id -- 该同学没有学过
  )
)

双重NOT EXISTS表示肯定

结果计算

-- 求出有差额的任意2位老师的薪水差额
SELECT t1.name, t2.name, t1.salary - t2.salary FROM teacher t1, teacher t2
WHERE t1.salary > t2.salary;

-- 根据学生年龄求出生年份
SELECT s.id, s.name, 2020 - s.age + 1 as year FROM student s;

聚集函数

COUNT
SUM
AVG
MAX
MIN

聚集函数不允许用于WHERE中，WHERE是对每一元组进行条件过滤，而不是对集合进行条件过滤

分组查询

            graph LR
            分组查询-->分组过滤

SQL可以将检索到的元组按照某一条件进行分类，具有相同条件值的元组划到一个组或一个集合中，同时处理多个组或集合的聚集运算

\text{GROUP}\ \text{BY}\ \text{分组条件}

-- 求每一个学生的平均成绩
SELECT student_id, AVG(score) FROM student_course_score GROUP BY student_id
-- 求每一门课的平均成绩
SELECT course_id, AVG(score) FROM student_course_score GROUP BY course_id

分组过滤

\text{GROUP}\ \text{BY}\ \text{分组条件}\ \text{HAVING}\ \text{过滤条件}

-- 求不及格课程超过2门的学生学号
SELECT student_id FROM student_course_score
WHERE score < 60
GROUP BY student_id HAVING COUNT(*) > 2;
-- 求有10人以上不及格的课程号
SELECT course_id FROM student_course_score
WHERE score < 60
GROUP BY course_id HAVING COUNT(*) > 10;
-- 求不及格课程超过2门的学生学号和平均成绩
SELECT student_id, AVG(score) FROM student_course_score
WHERE student_id IN (
  SELECT student_id FROM student_course_score
  WHERE score < 60
  GROUP BY student_id HAVING COUNT(*) > 2;
)
GROUP BY student_id;

关系代数操作

\text{子查询}\ \text{UNION}\ |\ \text{INTERSECT}\ |\ \text{EXCEPT}\ |\ \text{子查询}

UNION: 并
- ALL: 出现m + n次
INTERSECT: 交
- ALL: 出现min(m, n)次
EXCEPT: 差
- ALL: 出现max(0, m - n)次

默认删除重复元组，若要保留则标记ALL

-- 求学过2号课的同学或学过3号课的同学学号
SELECT student_id FROM student_course_score WHERE course_id = 2
UNION
SELECT student_id FROM student_course_score WHERE course_id = 3

-- 求学过2号课的同学又学过3号课的同学学号
SELECT student_id FROM student_course_score WHERE course_id = 2
INTERSECT
SELECT student_id FROM student_course_score WHERE course_id = 3

-- 求没有学过2号课的同学
SELECT student_id FROM student_course_score
EXCEPT
SELECT student_id FROM student_course_score WHERE course_id = 2

空值

1 2	IS NULL IS NOT NULL

除IS [NOT] NULL之外，空值不满足任何查找条件
NULL若参与算术运算，则该运算表达式的值为NULL
NULL若参与比较运算，则结果可视为为false
NULL若参与聚集运算，则结果除COUNT之外都忽略

连接

\text{JOIN}\ \text{[TABLEs]} \quad \text{ON}\ \text{[CON]}

4种类型的JOIN
- INNER JOIN
- LEFT OUTER JOIN
- RIGHT OUTER JOIN
- FULL OUTER JOIN
3种条件
- NATURAL
  - 出现在结果关系中的两个连接关系的元组在公共属性上取值相等，且公共属性只出现一次
- ON <连接条件>
  - 出现在结果关系中的两个连接关系的元组取值满足连接条件，且公共属性出现两次
- USING (col, col...)
  - 元组在col, col...上取值相等，且col, col...只出现一次

-- 求所有教师的任课情况并按教师号排序（没有任课的教师不需要显示）
SELECT t.id, t.name, c.name FROM teacher t INNER JOIN course c on teacher.id = course.teacher_id
ORDER BY t.id ASC;

-- 求所有教师的任课情况并按教师号排序（没有任课的教师也需要显示）
-- LEFT <- 会输出teacher表中所有的元素
SELECT t.id, t.name, c.name FROM teacher t LEFT OUTER JOIN course c on teacher.id = course.teacher_id
ORDER BY t.id ASC;

视图（View）

对应概念模式的数据在SQL中被称为基本表，而对应外模式的数据称为视图，视图不仅包含外模式，而且包含其E-C映像

基本表：实际存储于存储文件中的表，基本表中的数据是需要储存的
视图：只储存其由基本表导出视图所需要的公式，即由基本表产生视图的映像信息，其数据并不存储，而是运行过程中动态产生与维护的

对视图数据的更改最终要反映在对基本表的更改上

定义视图

CREATE VIEW view_name col, col, ... as 子查询 [with check options]

-- 定义一个计算机系的学生的表
CREATE VIEW computer_student AS
(
  SELECT * FROM student WHERE dept_id IN
  (
    SELECT id FROM dept WHERE name = '计算机'
  )
);

-- 定义教师教学科目和学分
CREATE VIEW teach AS
(
  SELECT t.name,c.name, c.credit FROM teacher t, course c WHERE t.id = c.teacher_id
);

视图可以作为table一样使用

视图的更新

视图不保存数据，对视图的更新最终要反映到对基本表的更新上，而有时，视图定义的映射是不可逆的
比如：聚集函数

如果视图的SELECT目标列包含聚集函数，则不能更新
如果视图的SELECT子句使用了UNIQUE或DISTINCT，则不能更新
如果视图中包括了GROUP BY子句，则不能更新
如果视图中包括经算术表达式计算出来的列，则不能更新
如果视图是由单个表的列构成，单并没有包括主键，则不能更新

数据库完整性

数据库完整性是指DBMS应保证的DB的一种特性，在任何情况下的正确性、有效性和一致性

广义完整性
- 语义完整性
- 并发控制
- 安全控制
- DB故障恢复
狭义完整性
- 专指语义完整性，DBMS通常有专门的完整性管理计值与程序来处理语义完整性问题

为什么会引发数据库完整性的问题

不正当的数据库操作，如输入错误，操作失误，程序处理失误，删库

其实就是验证机制

Intergrity Constraint

O: 数据集合，约束的对象
P: 谓词条件，什么样的约束
A: 触发条件，什么时候检测
R: 响应动作，不满足时怎么办

完整性分类

域完整性约束条件
- 施加于某一列上，对给定列上所有更新的某一候选值是否可以接受进行约束条件判断，这是孤立进行的
关系完整性约束条件
- 施加于关系/table上，对给定table上所要更新的某一候选元组是否可以接受进行约束条件判断，或是对一个关系中的若干元组和另一个关系中的若干元组见的联系是否可以接受进行约束条件判断
结构约束
- 来自于模型的约束，例如函数依赖约束，主键约束
内容约束
- 来自于用户的约束，如用户自定义完整性，属性的取值范围
静态约束
- 要求DB在任一时候均应满足的约束，例如年龄在任何时候都应该满足大于0小于150
动态约束
- 要求DB从一状态变为另一状态时应满足的约束，例如工资只能增加。

完整性定义

CREATE TABLE "student" (
 "id"     INTEGER NOT NULL,
 "name"   VARCHAR(10),
 "sex"    VARCHAR(2) Constraint ctsex check (sex='男' or sex='女'),
 "age"    INTEGER check(age >= 1 and age < 150),
 "dept_id"  VARCHAR(2) references dept(id) on delete cascade,
 "class"  VARCHAR(6),
 PRIMARY  KEY("id")
);

不同软件增加约束有差别，具体查看文档

断言

一个断言就是一个谓词表达式，他表达了希望数据库总能满足的条件
表约束和列约束就是一些特殊的断言
当一个断言创建后，系统将检测其有效性，并在每一次更新中测试更新是否违反该断言

1	CREATE ASSERTION <assertion-name> CHECK <predicate>

断言测试增面积数据库维护的负担

触发器

CREATE TABLE中的表约束和列约束基本上都是静态约束，也基本上都是单一列或单一元组的约束(尽管有参照完整性)，为实现动态约束以及多个元组之间的完整性约束，需要触发器技术

Trigger是一种过程完整性约束，是一段程序，该程序可以在特定的时刻被自动触发执行，比如在一次更新操作之前执行，或者更新操作之后执行

CREATE TRIGGER <trigger-name> BEFORE|AFTER
[INSERT|DELETE|UPDATE] [OF col, col, ...]
on table REFERENCING col_name, col_name, ...
[FOR EACH ROW| FOR WACH STATEMENT]
...
WHER (search_condition)
[statement|BEGIN ATOMIC statement; statement; ... END]

当某一事件发生时BEFORE|AFTER，对该事务产生的结果（或是每一元组，或是整个操作的所有元组，检测条件search_condition，如果满足条件，则执行后面的程序段，条件或程序段中引用的变量可用col_name来限定

触发器事件

每当一个事件INSERT, DELETE, UPDATE发生，可以在发生之前(before))，或者发生之后(after)触发
可以参考git库的hook，事件发生后，触发器需要处理两组值，一个是更新前的值，一个是更新后的值，这2割值使用col_name进行区分

OLD [ROW] [AS] old_row_corr_name
NEW [ROW] [AS] new_row_corr_name
OLD TABLE [AS] old_table_corr_name
NEW TABLE [AS] new_table_corr_name

例子：工资只能增加

CREATE TRIGGER teacher_chgsal BEFORE UPDATE OF salary ON teacher
REFERENCING NEW x, OLD y
FOR EACH ROW WHEN (x.salary < y.salary)
BEGIN
  raise_application_error(-20004, 'invalid salary on update');
  ...
END

例子：学生已经学习课程的门数

CREATE TRIGGER sumc AFTER INSERT ON student_course_score
REFERENCING NEW row newi
FOR EACH ROW
BEGIN
  UPDATE student set SumCourse = SumCourse + 1
  WHERE id = newi.id;
END

例子：删除被开除学生已经的选课

CREATE TRIGGER dels AFTER INSERT ON student
REFERENCING OLD oldi
FOR EACH ROW
BEGIN
  DELETE student_course_score WHERE id = oldi.id;
END

数据库安全性

数据库安全性是指DBMS应该保证的数据库的一种特性（机制或手段）：免受非法，非授权用户的使用，泄露，更改或破坏
数据库安全性管理涉及许多方面

社会法律及伦理方面：私人信息受到保护，未授权人员访问私人信息会违法
公共政策/制度方面：例如，政府或组织的信息公开或非公开制度
安全策略：政府，企业或组织所实施的安全性策略，如集中管理和分散管理，最少特权策略
数据的安全级别：绝密（Top Secret），机密（Secret），可信（Confidential）和无分类（Unclassified）
数据库系统DBS的安全级别：物理控制，网络控制，操作系统控制，DBMS控制

安全性访问规则

DBMS讲权力和用户结合在一起，形成一个访问规则表，依据该规则表可以实现对数据库的安全性控制

AccessRule
- S: 请求主体
- O: 访问对象
- t: 访问权力
- P: 谓词

用户与权力

级别1
- SELECT
级别2
- INSERT
- UPDATE
- DELETE
级别三
- CREATE
- ALTER
- DROP

授权命令

1
2
3

GRANT [ALL PRIVILEGES|PRIVILEGES, PRIVILEGES, ...]
ON [TABLE] [table_name|view_name] TO [public|user, user, ...]
WITH GRANT OPTION;

SELECT
INSERT
UPDATE
DELETE
ALL PRIVILEGES

收回授权

1 2	REVOKE [ALL PRIVILEGES\|PRIVILEGES, PRIVILEGES, ...] ON [TABLE] [table_name\|view_name] FROM [public\|user, user, ...]

事务

SQL语句在执行过程中，必须有提交和撤销才能确认其操作结果

是数据库管理系统提供的控制数据操作的一种手段，通过这一手段，应用程序员将一些列的数据库操作合作在一起作为一个整体进行操作和控制，以便数据库管理系统能狗提供一致性状态转换的保证

事务的宏观性：是一个存取或改变数据库内容的程序的一次执行，或者说一条或多条SQL语句的一次执行被看作一个事务
事务的微观性：对数据库的一系列基本操作的一个整体性的执行

事务的特性

原子性：保证事务的一组更新操作时原子不可分的，即对DB而言，要么全做，要么全不做
一致性：保证书屋的操作状态时正确的，符合一致性的操作规则，他是进一步由隔离性来保证的
独立性：保证并发执行的多个事务之间互相不受影响，例如两个事务T1和T2，即使并发执行，也相当于先执行了T1，再执行T2，或者先执行了T2，再执行T1
持久性：一旦事务提交后，它所做的修改将会永久的保存在数据库上，即使出现宕机也不会丢失。被撤销事务的影响是可恢复的

事务涉及

数据库通常由元素构成
每个事务都会读写某些元素
- READ(X, t)：将元素X读到事务的局部变量t中
- WRITE(X, t)：将事务的局部变量t写回元素X
- INPUT(X, t)：将元素X从磁盘读入到内存缓冲区中
- OUTPUT(X, t)：将元素X写回到磁盘中
每个事务都以提交或者撤销结束
- COMMIT：提交事务
- ABOUT：事务撤消

数据建模与数据库设计

表达计算机世界的模型称为数据模型，表达信息世界的模型称为概念数据模型，简称概念模型。

抽象是理解-区分-命名-表达

E-R模型

世界是由一组称作实体的基本对象和这些对象之间的联系构成的

实体
- 客观存在并可相互区分的事务（不是instance）
属性
- 实体所具有的某一方面特性
- 单一属性/复合属性（住址）
- 单值属性/多值属性（电话号码）
- 可空值属性/非空值属性
联系
- 指一个实体的实例和其他实体实例之间所可能发生的联系
- 一对一（One-to-one，OneToOneField）
- 一对多（Many-to-one，ForeignKey）
- 多对多（Many-to-many，ManyToManyField）
关键字
- 实体中能够用其值唯一区分开每一个实例的属性或属性的组合

Chen方法

Crow’s foot方法

Crow’s foot

数据库设计过程

需求分析
- 收集需求和理解需求
概念数据库设计
- 建立概念模型
逻辑数据库设计
- 建立逻辑模型，关系模式，包括全局模式和用户模式
物理数据库设计
- 建立物理模型，包括物理数据组织，依赖于具体的DBMS

函数依赖

设 $R(U)$ 是属性集合 $U = \lbrace A_1, A_2, \cdots, A_n \rbrace$ 上的一个关系模式， $X, Y$ 是 $U$ 上的两个子集，若对 $R(U)$ 的任意一个可能的关系 $r$ ， $r$ 在不可能由两个元组满足在 $X$ 中的属性值相等而在 $Y$ 中的属性值不等，则称X函数决定Y或者Y函数依赖于X，记作 $X \rightarrow Y$

学号 $\rightarrow$ {姓名，年龄}
学号, 课程 $\rightarrow$ 成绩

函数依赖的特性

对 $X \rightarrow Y$ ，但 $Y \subsetneq X$ ，则称 $X \rightarrow Y$ ：非平凡的函数依赖
若 $X \rightarrow Y$ ，则任意两个元组，若 $X$ 上值相等，则 $Y$ 上值必然相等，则称 $X$ 为决定因素
若 $X \rightarrow Y$ ， $Y \rightarrow X$ ，则记作 $X \leftrightarrow Y$
若 $Y$ 不函数依赖于 $X$ ，则记作 $X \nrightarrow Y$
$x \rightarrow Y$ ，有基于模式R的，则要求对任意的关系 $r$ 成立，有基于具体关系 $r$ 的，则要求对某一关系 $r$ 成立
如一关系 $r$ 的某属性集 $X$ ， $r$ 中根本没有 $X$ 上相等的两个元组存在，则 $X \rightarrow Y$ 恒成立

部分或完全函数依赖：在R(U)中，若 $X \rightarrow Y$ 并且对于 $X$ 的任何真子集 $X'$ 都有 $X' \nrightarrow Y$ ，则称 $Y$ 完全函数依赖于 $X$ ，记为： $X \xrightarrow{f} Y$ ，否则称 $Y$ 部分函数 $X$ ，记为： $X \xrightarrow{p} Y$
传递函数依赖：在R(U)中，若 $X \rightarrow Y, Y \rightarrow Z$ ，且 $Y \subsetneq X, Z \subsetneq Y, Z \subsetneq X, Y \nrightarrow X$ ，则称 $Z$ 传递函数依赖于 $X$

候选键：设 $K$ 为 $R(U)$ 中的属性或属性组合，若 $K \xrightarrow{f} U$ ，则称 $K$ 为 $R(U)$ 上的候选键

可任选一候选键作为 $R$ 的主键
包含在任一候选键中的属性称主属性，其他属性，其他属性称为非主属性
若 $K$ 是 $R$ 的一个候选键， $S \supset K$ ，则称 $S$ 为 $R$ 的一个超键

外来键：若 $R(U)$ 中的属性或属性组合 $X$ 并非 $R$ 的候选键，但 $X$ 却是另一关系的候选键，则称 $X$ 为 $R$ 的外来键
逻辑蕴含：设 $F$ 是关系模式 $R(U)$ 中的一个函数依赖集合， $X,Y$ 是 $R$ 的属性子集，如果从 $F$ 中的函数依赖能推导出 $X \rightarrow Y$ ，则称 $F$ 逻辑蕴含 $X \rightarrow Y$ ，或称 $X \rightarrow Y$ 是 $F$ 的逻辑蕴含，记作 $F \models X \rightarrow Y$

设 $F$ 是关系模式 $R(U)$ 的函数依赖集， $X \rightarrow Y$ 是一个函数依赖，若对 $R$ 中的每个满足 $F$ 的关系 $r$ ，能够用形式逻辑推理的方法推出 $r$ 也满足 $X \rightarrow Y$ ，则称 $F \models X \rightarrow Y$
若满足 $F$ 的每个关系均满足 $X \rightarrow Y$ ，则说 $F$ 逻辑蕴含 $X \rightarrow Y$

闭包：被 $F$ 逻辑蕴含的所有函数依赖集合称为 $F$ 的闭包，记作 $F^+$

$X$ 包含 $A$ ，而 $Y$ 任意，如 $ABC \rightarrow AB, A \rightarrow C, AB \rightarrow BC$
$X$ 包含 $B$ 但不包含 $A$ 且不含 $A$ ，如： $BC \rightarrow B, B \rightarrow C, B \rightarrow \phi$
$X \rightarrow Y$ 是 $C \rightarrow C$ 或 $C \rightarrow \phi$

函数依赖的Armstrong公理

设 $R(U)$ 是属性集 $U=\lbrace A_1, A_2, \cdots, A_n \rbrace$ 上的一个关系模式， $F$ 为 $R(U)$ 的一组函数依赖，记为 $R(U, F)$ ，则有一下规则成立

自反律：若 $Y \subseteq X \subseteq U$ ，则 $X \rightarrow Y$ 被 $F$ 逻辑蕴含
增广律：若 $X \rightarrow Y \in F$ ，且 $Z \subseteq U$ ，则 $XZ \rightarrow YZ$ 被 $F$ 逻辑蕴含
传递率：若 $X \rightarrow Y \in F$ ，且 $Y \rightarrow Z$ ，则 $X \rightarrow Z$ 被函数逻辑蕴含

由Armstrong’s Axiom可推出如下结论

合并率：若 $X \rightarrow Y$ 且 $X \rightarrow Z$ ，则 $X \rightarrow YZ$
伪传递率：若 $X \rightarrow Y$ 且 $WY \rightarrow Z$ ，则 $XW \rightarrow Z$
分解率：若 $X \rightarrow Y$ 且 $Z \subseteq Y$ ，则 $X \rightarrow Z$

公理的作用是由已知的函数依赖推导出隐含的函数依赖

属性闭包

对 $R(U, F), X \subseteq U, U = \lbrace A_1, A_2, \cdots, A_n \rbrace$ ，令：

X^+_{F} = \lbrace A_i | \text{用}Armstrong\ Axiom\ A_1, A_2, A_3\text{可从}F\text{导出}X\rightarrow A_i \rbrace

称 $X^+_F$ 为 $X$ 关于 $F$ 的属性(集)闭包

闭包就是由一个属性直接或间接推导出的所有属性的集合

覆盖：对 $R(U)$ 上的两个函数依赖集合 $F, G$ ，如果 $F^+ = G^+$ ，则称 $F$ 和 $G$ 是等价的，也称 $F$ 覆盖 $G$ 或者 $G$ 覆盖 $F$

F^+ = G^+ \Leftrightarrow F \subseteq G^+ \cap G \subseteq F^+

每个函数依赖集 $F$ 可被一个其右端至多有一个属性的函数依赖之集G覆盖

最小覆盖

若 $F$ 满足以下条件，则称 $F$ 为最小覆盖或最小依赖集

$F$ 中每个函数依赖的右部是单个属性
对任何 $X \rightarrow A \in F$ ，有 $F - \lbrace X \rightarrow A \rbrace$ 不等价于 $F$
对任何 $X \rightarrow A \in F, Z \subset X, (F - \lbrace X \rightarrow A \rbrace) \cup \lbrace Z \rightarrow A \rbrace$ 不等价于 $F$

每个函数依赖集 $F$ 都有等价的最小覆盖 $F'$

范式

第一范式

若关系模式 $R(U)$ 中关系的每个分量都是不可分的数据项，则称 $R(U)$ 属于第一范式，记为： $R(U) \in 1NF$

第二范式

若 $R(U) \in 1NF$
$U$ 中的每一个非主属性完全函数依赖于候选键，则称 $R(U)$ 属于第二范式，记为 $R(U) \in 2NF$
简单话：候选键完全决定每一个非主属性
第二范式消除了非主属性对候选键的部分依赖

可能会存在问题：

数据冗余:，每条记录都含有相同信息；
删除异常：删除所有学生成绩，就把课程信息全删除了；
插入异常：学生未选课，无法记录进数据库；
更新异常：调整课程学分，所有行都调整。

第三范式

若 $R(U, F) \in 2NF$ 且 $R$ 中不存在这样的情况：候选键 $X$ ，属性组 $Y \subset U$ 和非主属性 $A$ ，且 $A \notin X, A \notin Y, Y \subsetneq X, Y \nrightarrow X$ ，使得 $X \rightarrow Y$ ， $Y \rightarrow A$ 成立，满足以上条件则称 $R(U)$ 属于第三范式，记为： $R(U) \in 3NF$
简单话：没有传递函数依赖
第三范式消除了非主属性对候选键的传递依赖
分解规则
- 讲每一个函数依赖单独组成一个关系
- A->B, A->B, C->D, C->E, E->FG
  - A->B | A->C | C->D | C->E | E->F->G
  - A->B->C | C->D->E | E->F->G

可能会存在问题：

数据冗余:有重复值；
更新异常：有重复的冗余信息，修改时需要同时修改多条记录，否则会出现数据不一致的情况。

BCNF范式

若 $R(U, F) \in 1NF$ ，若对于任何 $X \rightarrow Y \in F$ (或 $X \rightarrow A \in F$ )，当 $Y \subsetneq X$ (或 $A \subsetneq X$ )时， $X$ 必含有候选键，则称 $R(U)$ 属于Boyce-Codd范式，记为： $R(U) \in BCNF$
简单话：没有依赖于候选键的函数依赖存在
例子：（城市，街道，邮政编码）
- （城市，街道）-> 邮政编码
- 邮政编码 -> 城市
分解规则
- 将左侧不含候选键的函数依赖单独组成一个关系，将包含候选键的组成一关系
- A->B, A->B, C->D, C->E, E->FG
  - C, D | C, E | E, F, G | A, B, C

函数依赖， $X$ 相等 $Y$ 值一定相等

多值依赖：有一组 $Y$ $Y$ 值与 $X$ $X$ 值对应
- 对 $R(U)$ ，设 $X, Y \subset U$ ，若对于 $R(U)$ 的任一关系 $r$ ，若元组 $t \in r, s\in r, t[X] = s[X]$ ，则必有 $u \in r, v \in r$ 使得
- $u[X] = v[X] = t[X] = s[X]$
- $u[Y] = t[Y]$ 且 $u[U-X-Y]=s[U-X-Y]$
- $v[Y]=s[Y]$ 且 $v[U-X-Y]=t[U-X-Y]$
- 均成立，则称 $Y$ 多值依赖于 $X$ ，或说 $X$ 多值决定 $Y$ ，记作 $X\rightarrow\rightarrow Y$

多值依赖特性

直观的，对于 $X$ 给定值， $Y$ 有一组值与之对应(0或n个)，且这组 $Y$ 值不以任何方式与 $U-X-Y$ 中属性值相联系，有 $X\rightarrow\rightarrow Y$
若交换 $t,s$ 的 $Y$ 值而得到新的元组仍在 $r$ 中，则 $X \rightarrow\rightarrow Y$
$X, Y$ 不必不相交， $u,v$ 可以与 $t,s$ 相同
函数依赖是多指依赖的特例
令 $Z = U-X-Y$ ，有 $X \rightarrow\rightarrow Z$ ，若 $Z = \phi$ ，则必有 $X \rightarrow\rightarrow Y$

第四范式

设 $R(U) \in 1NF$ ， $D$ 是其上的一组依赖（函数依赖，多值依赖），对任意 $X \rightarrow\rightarrow Y \in D$ ，若 $Y = \phi$ ， $Y \subsetneq X, XY \neq U$ ，必有 $X$ 为超键，则称 $R(U)$ 满足第四范式，记为 $R(U)\in 4NF$

第四范式消除了非主属性对候选键以外属性的多值依赖
如果有多值依赖，则一定依赖于候选键

若 $R$ 上仅存在函数依赖，则若有 $R \in BCNF$ 既有 $R \in 4NF$ ，反之若 $R \in 4NF$ ，也有 $R \in BCNF$

弱第四范式

设 $R(U)\in 3NF$ ，若 $R$ 上的任何互补多值依赖 $X \rightarrow\rightarrow Y(XY \neq U, Y-X\neq\phi)$ 和 $X \rightarrow\rightarrow (U-X-Y)$ 中必有一个是函数依赖，则称 $R$ 是弱第四范式的，记为 $R \in W4NF$

多值依赖的Armstrong公理

设 $R(U), X, Y$ ，对于 $R(U)$ 的任一关系，有以下规则

多值依赖互补律/对称性：若 $X\rightarrow\rightarrow Y$ ，则 $X \rightarrow\rightarrow U-X-Y$
多值依赖增广律：若 $X\rightarrow\rightarrow Y$ 且 $V \subseteq W$ ，则 $WX \rightarrow\rightarrow VY$
多值依赖传递律：若 $X\rightarrow\rightarrow Y$ ， $Y\rightarrow\rightarrow Z$ ，则 $X \rightarrow\rightarrow Z-Y$
若 $X\rightarrow\rightarrow Y$ ，则 $X\rightarrow\rightarrow Y$
若 $X\rightarrow\rightarrow Y$ ， $Z \subseteq Y$ 对于某个与 $Y$ 不相交的 $W$ 有 $W \rightarrow Z$ ， $W \cap Z = \phi$ ，则有 $X \rightarrow Z$

由多值依赖的公理可推出以下结论

多值依赖的合并律：若 $X \rightarrow\rightarrow Y$ 且 $X \rightarrow\rightarrow Z$ ，则 $X \rightarrow\rightarrow YZ$
多值依赖的伪传递律：若 $X \rightarrow\rightarrow Y$ 且 $WY\rightarrow\rightarrow Z$ ，则 $X\rightarrow\rightarrow Z-WY$
混合伪传递律：若 $X\rightarrow\rightarrow Y, XY \rightarrow Z$ ，则 $X \rightarrow Z-Y$
多值依赖的分解律：若 $X \rightarrow\rightarrow Y, X\rightarrow\rightarrow Z$ ，则 $X\rightarrow\rightarrow Y-Z, X\rightarrow\rightarrow Z-Y, X\rightarrow\rightarrow Y\cap Z$

模式分解

关系模式 $R(U)$ 的分解是指用 $R$ 的一组子集 $\rho = \lbrace R_1(U_1), \cdots, R_k(U_k) \rbrace$ 来代替它，其中

U = U_1 \cup U_2 \cup \cdots \cup U_k

$R$ 与 $\rho$ 在数据内容方面是否等价：分解的无损连接性
$R$ 与 $\rho$ 在数据依赖方面是否等价：分解的保持依赖性

引理：设 $R(U)$ 为一关系模式， $\rho = \lbrace R_1, R_2, \cdots, R_K \rbrace$ 是 $R(U)$ 的一个分解， $r$ 是 $R$ 的任一个关系， $r = \pi_{R_i}(r)$ ，则有规则成立

分解的关系链接起来会产生多余的信息
链接起来的表在分解的关系上投影，和原来的关系相同
不能无限分解产生多的信息

分解以后是否有约束丢失

无损链接分解

对于关系模式 $R(U, F)$ ， $U$ 是属性全集， $F$ 是函数依赖集合， $\rho = \lbrace R_1, R_2, \cdots, R_k \rbrace$ 是 $R(U)$ 的一个分解，如果对于 $R$ 的任何满足函数依赖集 $F$ 的关系 $r$ ，有

r = m_{\rho}(r)

则称 $\rho$ 是 $R$ 相对于 $F$ 的一个无损连接分解

分解后连接的结果和原来结果相同

无损连接性检验算法

输入：关系模式 $R = A_1A_2\cdots A_n$ ，函数依赖集 $F$ ，分解 $\rho = \lbrace R_1, R_2, \cdots, R_k \rbrace$

构造一k行n列的表，对其中 $j$ 列对应于 $A_j$ ，第 $i$ 行对应于 $R_i$ ，若 $A_j \in R_i$ ，则 $R_{\rho}$ 表中第 $i$ 行第 $j$ 列位置填写符号 $a_j$ ，否则填写 $b_{ij}$

	$A_1$	$\cdots$	$A_j$	$\cdots$	$A_n$
$R_1$
$\cdots$
$R_i$			$a_j$ 或 $b_{ij}$
$\cdots$
$R_k$

$A_j$ ：属性
$a_j$ 属于 $R_i$ 时填写 $R_i$
$a_j$ 不属于 $R_i$ 时填写 $b_{ij}$

根据每一个函数依赖 $X \rightarrow Y$ $X \to Y$ ，对 $R_{\rho}$ $R_{ρ}$ 表进行修改
1. 给定 $X \rightarrow Y$ ，在表中寻找对应于 $X$ 中所有属性分量之列上符号完全相同的行，若能找到，则在这些行的对应于 $Y$ 中属性的那些列上置相同符号，
2. 若其中有一个行之相应列上为 $a_j$ ，则使其他行同一列上置 $a_j$
3. 若相应列上均为 $b$ ，则使其他行同一列上置换某一个 $b$
在上述修改的表中，如果发现有一行变成 $a_1, a_2, \cdots, a_n$ ，则 $\rho$ 是无损连接分解，否则是有损

例子：已知 $R = \lbrace ABCDE \rbrace$ ， $F = \lbrace A \rightarrow C, B \rightarrow C, C \rightarrow D, DE \rightarrow C, CE \rightarrow A \rbrace$ ， $\rho = \lbrace R_1(AD), R_2(AB), R_3(BE), R_4(CDE), R_5(AE) \rbrace$

	$A$	$B$	$C$	$D$	$E$
$R_1$	$a_1$	$b_{12}$	$b_{13}$	$a_4$	$b_{15}$
$R_2$	$a_1$	$a_2$	$b_{23}$	$b_{24}$	$b_{25}$
$R_3$	$b_{31}$	$a_2$	$b_{33}$	$b_{34}$	$a_5$
$R_4$	$b_{41}$	$b_{42}$	$a_3$	$a_4$	$a_5$
$R_5$	$a_1$	$b_{52}$	$b_{53}$	$b_{54}$	$a_5$

用 $A \rightarrow C$ 修改，可以选任意一个值

	$A$	$B$	$C$	$D$	$E$
$R_1$	$a_1$	$b_{12}$	$\color{red}b_{13}$	$a_4$	$b_{15}$
$R_2$	$a_1$	$a_2$	$\color{red}b_{13}$	$b_{24}$	$b_{25}$
$R_3$	$b_{31}$	$a_2$	$b_{33}$	$b_{34}$	$a_5$
$R_4$	$b_{41}$	$b_{42}$	$a_3$	$a_4$	$a_5$
$R_5$	$a_1$	$b_{52}$	$\color{red}b_{13}$	$b_{54}$	$a_5$

用 $B \rightarrow C$ 修改

	$A$	$B$	$C$	$D$	$E$
$R_1$	$a_1$	$b_{12}$	$b_{13}$	$a_4$	$b_{15}$
$R_2$	$a_1$	$a_2$	$\color{red}b_{13}$	$b_{24}$	$b_{25}$
$R_3$	$b_{31}$	$a_2$	$\color{red}b_{13}$	$b_{34}$	$a_5$
$R_4$	$b_{41}$	$b_{42}$	$a_3$	$a_4$	$a_5$
$R_5$	$a_1$	$b_{52}$	$b_{13}$	$b_{54}$	$a_5$

用 $CE \rightarrow A$ 修改

	$A$	$B$	$C$	$D$	$E$
$R_1$	$a_1$	$b_{12}$	$b_{13}$	$a_4$	$b_{15}$
$R_2$	$a_1$	$a_2$	$b_{13}$	$b_{24}$	$b_{25}$
$R_3$	$\color{red}a_1$	$a_2$	$b_{13}$	$b_{34}$	$a_5$
$R_4$	$b_{41}$	$b_{42}$	$a_3$	$a_4$	$a_5$
$R_5$	$\color{red}a_1$	$b_{52}$	$b_{13}$	$b_{54}$	$a_5$

用 $C \rightarrow D$ 修改

	$A$	$B$	$C$	$D$	$E$
$R_1$	$a_1$	$b_{12}$	$b_{13}$	$\color{red}a_4$	$b_{15}$
$R_2$	$a_1$	$a_2$	$b_{13}$	$\color{red}a_4$	$b_{25}$
$R_3$	$a_1$	$a_2$	$b_{13}$	$\color{red}a_4$	$a_5$
$R_4$	$b_{41}$	$b_{42}$	$a_3$	$a_4$	$a_5$
$R_5$	$a_1$	$b_{52}$	$b_{13}$	$\color{red}a_4$	$a_5$

用 $DE \rightarrow C$ 修改

	$A$	$B$	$C$	$D$	$E$
$R_1$	$a_1$	$b_{12}$	$\color{red}a_3$	$a_4$	$b_{15}$
$R_2$	$a_1$	$a_2$	$\color{red}a_3$	$a_4$	$b_{25}$
$R_3$	$a_1$	$a_2$	$\color{red}a_3$	$a_4$	$a_5$
$R_4$	$b_{41}$	$b_{42}$	$\color{red}a_3$	$a_4$	$a_5$
$R_5$	$a_1$	$b_{52}$	$\color{red}a_3$	$a_4$	$a_5$

因为 $b_{13}$ 被置换为 $a_3$ 了，所以剩余的 $b_{13}$ 也可以置换

	$A$	$B$	$C$	$D$	$E$
$R_1$	$a_1$	$b_{12}$	$a_3$	$a_4$	$b_{15}$
$R_2$	$a_1$	$a_2$	$a_3$	$a_4$	$b_{25}$
$R_3$	$\color{red}a_1$	$\color{red}a_2$	$\color{red}a_3$	$\color{red}a_4$	$\color{red}a_5$
$R_4$	$b_{41}$	$b_{42}$	$a_3$	$a_4$	$a_5$
$R_5$	$a_1$	$b_{52}$	$a_3$	$a_4$	$a_5$

出现了一行全是 $a$ ，此分解为无损分解

简单的情况：设 $F$ 是关系模式 $R$ 上的一个函数依赖集合。 $\rho = \lbrace R_1, R_2 \rbrace$ 是 $R$ 的一个分解，则当且仅当 $R_1 \cap R_2 \rightarrow R_1 - R_2$ 或者 $R_1 \cap R_2 \rightarrow R_2 - R_1$ 属于 $F^+$ 时， $\rho$ 是关于 $F$ 无损连接的

在无损分解基础上，对某一个关系再做无损分解，整体还是无损分解
对于无损分解基础上，加上一些其他的模式，整体还是无损分解

保持依赖分解

对于关系模式 $R(U, F)$ ， $U$ 是属性全集， $F$ 是函数依赖集合， $\rho = \lbrace R_1, R_2, \cdots, R_k \rbrace$ 的一个分解，如果 $\pi_{R_i}(F)$ 中的所有依赖之并集 $i=1,2,\cdots,k$ 逻辑蕴含 $F$ 的每个依赖，则称分解 $\rho$ 保持依赖集 $F$ 。其中 $\pi_{R_i}(F)$ 是 $F$ 在 $R_i$ 上的投影，即 $F$ 中的任一投影 $X \rightarrow Y$ ，如果 $X, Y$ 均包含于 $R_i$ ，则 $X \rightarrow Y \in \pi_{R_i}(F)$ 。 $R_i$ 指 $R_i$ 的属性集

人话：如果 $F$ 上的每一个函数依赖都在其分解后的某一个关系上成立，则这个分解是保持依赖的（这是一个充分条件）。

保持依赖的分解可能不是无损连接
无损连接的分解可能不是保持依赖

保持依赖性的检验算法

输入：关系模式 $R = A_1A_2\cdots A_n$ ，函数依赖集 $F$ ，分解 $\rho = \lbrace R_1, R_2, \cdots, R_k \rbrace$

令 $G$ 等于 $F$ 在分解上的投影，投影后再并起来的东西，只需要检查 $G$ 是否覆盖 $F$ 即可

首先对每个 $X \rightarrow Y \in F$ 计算 $G$ 中的 $X^+_G$ ：如果 $X$ 不包含于 $R_i$ 则不需计算

Z = X
while Z发生变化
  for i in range(1, k + 1):
    Z = Z ∪ ((Z ∩ R_i)^+ ∩ R_i)

判断 $G$ 是否逻辑蕴含 $X \rightarrow Y$ ：前面计算的结果 $Z$ 便是 $X^+$ ，如果 $Z$ 包含 $Y$ ，则 $G$ 逻辑蕴含 $X \rightarrow Y$ ，否则便不逻辑蕴含
判断 $\rho$ 是否保持依赖：如果 $G$ 逻辑蕴含 $F$ 中的每一个函数依赖，则说 $\rho$ 是保持依赖的分解，否则便不是保持依赖的分解

例子：已知 $R = \lbrace ABCDE \rbrace$ ， $F = \lbrace A \rightarrow C, B \rightarrow C, C \rightarrow D, DE \rightarrow C, CE \rightarrow A \rbrace$ ， $\rho = \lbrace R_1(AC), R_2(BC), R_3(CDE) \rbrace$

$\pi_{R_1}(F) = \lbrace A \rightarrow C \rbrace$
$\pi_{R_2}(F) = \lbrace B \rightarrow C \rbrace$
$\pi_{R_3}(F) = \lbrace C \rightarrow D, DE \rightarrow C \rbrace$

并起来 $G = \lbrace A \rightarrow C, B \rightarrow C, C \rightarrow D, DE \rightarrow C\rbrace$ 不保持依赖

对函数依赖 $A \rightarrow C \in F$ $A \to C \in F$ 计算 $G$ $G$ 中的 $X^+$ $X^{+}$ ：
- $Z = \lbrace A \rbrace \cup \lbrace C \rbrace \cup \lbrace \rbrace \cup \lbrace \rbrace = \lbrace A, C \rbrace$ ， $C$ 包含于 $Z$ 中，所以 $A \rightarrow C$ 被 $G$ 逻辑蕴含
对函数依赖 $DE \rightarrow C \in F$ $D E \to C \in F$ 计算 $G$ $G$ 中的 $X^+$ $X^{+}$ ：
- $Z = \lbrace D,E \rbrace \cup \lbrace \rbrace \cup \lbrace \rbrace \cup \lbrace C, D \rbrace = \lbrace C, D, E \rbrace$ ， $C$ 包含于 $Z$ 中，所以 $A \rightarrow C$ 被 $G$ 逻辑蕴含
对函数依赖 $CE \rightarrow A \in F$ $C E \to A \in F$ 计算 $G$ $G$ 中的 $X^+$ $X^{+}$ ：
- $Z = \lbrace C,E \rbrace \cup \lbrace \rbrace \cup \lbrace \rbrace \cup \lbrace D \rbrace = \lbrace C, E, D \rbrace$ ， $A$ 不包含于 $Z$ 中，所以不被 $G$ 逻辑蕴含

左端属性必须是某一个关系模式的属性
求关于 $G$ 的属性闭包，结果属性也必须是此关系模式的属性

关系模式分解成BCNF

例子： $R(A,B,C,D,E,F,G)$ ，函数依赖集合 $\lbrace A \rightarrow B, A \rightarrow C, C \rightarrow D, C \rightarrow E, E \rightarrow FG \rbrace$ ，候选键： $A$ ，有不依赖于候选键的其他函数依赖， $R$ 不满足BCNF

将左侧不含候选键的函数依赖单独组成一个关系，将包含候选键的组成一关系

\rho = \lbrace R_1(CD), R_2(CE), R_3(EFG), R_4(ABC) \rbrace

可以看出他们满足BCNF，也可以 $\rho = \lbrace R_1(CDE), R_3(EFG), R_4(ABC) \rbrace$

无损连接分解成BCNF算法

例子： $R(U, F)$

令 $\rho = \lbrace R \rbrace$
对每个模式 $s \in \rho$ ，若 $s \notin BCNF$ ，则 $s$ 上必有 $X \rightarrow A$ 成立，且 $X$ 不是 $s$ 的超键且 $A \notin X$ ，此时用模式 $s_1, s_2$ 替代 $\rho$ 中的模式 $s$ ，其中 $s_1$ 由 $A$ 和 $X$ 构成， $s_2$ 由 $s$ 中除 $A$ 以外的所有属性构成（ $s_1 \in BCNF$ ）
重复上诉步骤，直到全部分解为BCNF

保持依赖分解成3NF的算法

例子： $R(U, F)$ ， $F$ 是函数依赖集的最小覆盖

把 $R$ 中不出现在 $F$ 中的属性去掉并单独组成一模式
对 $\forall X \rightarrow A \in F$ ，则以 $XA$ 组成一模式，若有 $X \rightarrow A_1, X \rightarrow A_2 \cdots, X \rightarrow A_m$ 都属于 $F$ ，则以 $XA_1A_2\cdots A_m$ 组成一模式
取 $\rho$ 为上述模式之集合，则 $\rho$ 即为所求之分解

保持依赖且无损连接的分解

设 $\sigma$ 是按前述算法构造的 $R$ 的一个第三范式分解， $X$ 是 $R$ 的候选键，则 $\tau = \sigma \cup \lbrace X \rbrace$ 将是 $R$ 的一个分解，且改分解中的所有关系模式是第三范式的， $\tau$ 有保持依赖和无损连接性

人话：把一个关系模式按照保持依赖的方式分解为第三范式之后，如果有某一关系模式保留了候选键所有属性。则这个分解保持依赖且无损连接

例子： $R(ABCDEFG)$ ，函数依赖： $A \rightarrow B, A \rightarrow C, C \rightarrow D, C \rightarrow E, E \rightarrow FG$
保持依赖的分解成3NF的集合

$\rho = \lbrace R_{12}(ABC), R_{34}(CDE), R_5(EFG) \rbrace$

保持依赖分解成4NF的算法

例子： $R(U, D)$ ， $D$ 为 $R$ 上的一个依赖集（多值，函数依赖）

令 $\rho = \lbrace R \rbrace$
对每个模式 $s \in \rho$ ，若 $s \notin 4NF$ ，则 $s$ 上必有 $X \rightarrow\rightarrow Y$ 成立，且 $X$ 不是 $s$ 的超键且 $Y-X \neq \phi, XY \neq s$ ，令 $Z = Y - X$ ，显然有 $X \rightarrow\rightarrow Z$ ，此时用模式 $s_1, s_2$ 替代 $\rho$ 中的模式 $s$ ，其中 $s_1$ 由 $Y$ 和 $X$ 构成， $s_2$ 由 $Y - X$ 构成
重复上诉步骤，直到全部分解为4NF

连接依赖

设 $R$ 为一关系模式， $\rho = \lbrace R_1, R_2, \cdots, R_n \rbrace$ 为 $R$ 的一个分解，若对 $R$ 的任一关系 $r$ 均有 $r$ 在分解上的每一个投影，再连接起来的，则称 $R$ 满足 $n$ 目连接依赖，记为 $JD[R_1, \cdots, R_n]$ ，或记为 $n-JD$

人话：连接依赖要保证无损连接性

多值依赖是连接依赖的特例，2-JD就是多值依赖

5NF

当且仅当关系模式 $R$ 的每个连接依赖均按其候选键进行连接运算时（均由 $R$ 的候选键所隐含），则称 $R$ 是第五范式的，记为 $R \in 5NF$

第五范式消除了不按照候选键连接的连接依赖（R的无损连接分解中各模式必含有一个候选键），但其语境背景抽象
$5NF \subset 4NF$ ，第五范式也称投影连接范式，即 $PJNF$
虽然总能把一个关系无损分解成多个 $5NF$ 的关系，但由于目前尚不清楚如何找到所有JD，故不清楚如何确定5NF关系（只能用穷举法）

数据库设计一般指考虑到3NF或BCNF
遵循关系范式虽然避免了冗余，但是由于联结运算的低效率，需要折中考虑

范式	描述
1NF	关系的每个分量都是不可分的数据项，
2NF	候选键完全决定每一个非主属性
3NF	没有传递函数依赖
BCNF	没有不依赖于候选键的函数依赖存在
4NF	如果有多值依赖，则一定依赖于候选键
5NF	消除了不按照候选键连接的连接依赖

索引

索引是定义在储存表基础之上，有助于无需检查所有记录而快读定位记录的一种辅助储存结构，由一系列储存在磁盘上的索引项组成，每一索引项又由两部分组成。

索引字段：由Table中某些列中的值串接而成，索引中通常储存了索引字段的每一个值，索引字段类似词典中的词条
行指针：指向table中包含索引字段值的记录在磁盘上的储存位置，类似于词条在书籍中的页码

储存索引项的文件为索引文件，相对应，储存表又称为主文件
索引文件是一种辅助储存结构，其存储与否不改变储存表的物理储存结构，然而其存在，可以明细提高储存表的访问速度

排序索引文件：按索引字段值的某一种顺序组织储存
散列索引文件：依据索引字段值使用散列函数分配散列筒的方式储存

在一个表上可以针对不同的属性或属性组合建立不同的索引文件，可以建立多个索引文件，索引字段的值可以是Table中的任何一个属性的值或任何多个属性值的组合值

索引文件比主文件小很多，通常检索一个小的索引文件，快速定位后，在有针对性的读取非常大的主文件中的有关记录

索引技术应用使检索效率大幅提高，但是同时增加了储存空间，使维护负担加重。

访问时间
插入时间
删除时间
空间负载
支持存取有效性

SQL中的索引

定义Table后，如果定义了主键，则系统将自动创建主索引，利用主索引对Table进行快读定位，检索与更新操作
当索引被创建后，无论是主索引还是用户创建的索引，DBMS都将自动维护所有的索引，使其与Table保存一致，即当一条记录被插入到Table中后，所有所有也自动的被更新

当Table被删除后，所有也会被自动的删除

1 2	CREATE [unique] INDEX index_name ON table_name(col [asc\|desc], col, ...) CREATE INDEX idxname ON student(name)

稠密索引/稀疏索引

稠密索引: 对于主文件中每一个记录，都有一个索引项和它对应，指明该记录所在的位置（全单射）
- 主键的稠密索引
  - 字段值没有重复
- 非主键的稠密索引
  - 字段值可以有重复
稀疏索引: 对于主文件中部分记录，都有一个索引项和它对应
- 定位索引字段值为K的记录
  - 首先找相邻的小于K的最大索引字段值所对应的索引项
  - 从该索引项所对应的记录开始顺序进行Table的检查
- 稀疏索引的使用要求：主文件必须是按对应索引字段属性排序储存
- 相对稠密索引：空间占用更少，维护任务更轻，但速度更慢
- 平衡: 索引项不指向记录指针，而是指向记录所在储存块的指针，即每一储存块有一个索引项，而不是每条记录都有一索引项（主索引）

主索引

主索引通常是对每一储存块都有一个索引项，索引项的总数和储存表所占的储存块数目相同，储存表的每一储存块的第一条记录，又被称为锚记录

主索引的所有字段值为块锚的索引字段值，而指针指向其所在的存储块
主索引是按索引字段值进行排序的一个有序文件，通常建立在有序主文件的基于主码的排序字段上，即主索引的索引字段与主文件的排序码有对应关系

辅助索引

辅助索引是定义在主文件的任一或多个非排序字段商店辅助存储结构

辅助索引通常是在某一非排序字段上的每一个不通风值有一个索引项：索引字段即是该字段的不同值，而指针则指向包含该记录的块或该记录本身
当非排序字段为索引字段时，如该字段值不唯一，则要采用一个类似链表的结构来保存包含该字段值的所有记录的位置（指针筒，hash表）
辅助索引时稠密索引，其检索效率有时相当高的

	主索引	辅助索引
数量	一个	多个
建立属性	主键	任何属性
主文件结构	可重新组织	无影响
类型	稀疏索引	稠密索引

其他索引

聚簇索引：索引中邻居的记录在主文件中也是临近存储的
- 如果主文件的某一排序字段不是主键，则该字段上每一个记录取值便不唯一，此视该字段被称为聚簇字段，聚簇索引通常定义在聚簇字段上
- 聚簇索引通常实对聚簇字段商店每一个不同值有一个索引项，索引字段即使聚簇字段的不同值，由于有相同的聚簇字段值的记录可能储存于若干块中，则索引项的指针指向其中的第一个块
- 一个主文件只能有一个聚簇索引文件、
- 主索引通常是聚簇索引
- 主索引/聚簇索引时能够记录存储位置的索引
非聚簇索引：索引中邻居的记录在主文件中不是临近存储的
- 一个主文件可以有多个非聚簇索引文件
- 辅助索引通常时非聚簇索引
- 非聚簇索引只能够用于查询，指出储存记录的位置

倒排索引
- 用于文档查询
- 正排：Doc(word, word, …)：一个文档包含了哪些词汇
- 倒排：word(Doc, Doc, …)：一个词汇在哪些文档中
多级索引
- 当索引项比较多时，可以对索引再建立索引
- 常见多级索引：B树/B+数索引
多属性索引
- 索引字段由Table的多个属性值组合在一起形成的索引
散列索引
- 使用散列技术组织的索引
网格索引
- 使用多索引字段进行交叉联合定位与检索

B+树索引

B+树索引是以树形数据结构来组织索引项的多级索引

存储块
- $K_i$ ：索引字段值
- $P_j$ ：指向索引块或数据块或数据块中记录的指针
根节点
- 非叶节点
  - 叶子节点
    - 指向主文件数据块
每一个节点都是一个存储块

B树是平衡树，每个索引块的指针利用率都在50%-100%之间

为了保存平衡

插入/删除记录时，伴随这结点的分类与合并

	B树	B+树
索引字段值	仅出现一次在叶节点或者非叶节点（卫星字段）	仅叶节点
主文件指针	出现于叶节点或非叶节点	仅叶节点
覆盖	所有节点才能覆盖	叶节点可全部覆盖
操作	原理一致，细节不同	原理一致，细节不同

数据库操作算法

数据库三大操作

一次单一元组的一元操作
- SELECT
整个关系的一元操作
- GROUP bY
整个关系的二元操作
- JOIN

不开发数据库，这里简单了解不记录

查询优化

语义优化
- 利用模型的语义及完整性规则，优化查询
语法优化
- 逻辑层优化：利用语法结构，优化操作执行顺序
- 尽可能早做选择运算
- 尽可能早做投影运算
- 次序改变后等价性问题
执行优化
- 物理层优化：存取路径和执行算法的选择与执行次序优化
- 获取数据库相关信息
- 选取相应的执行层例行程序
- 依据相关信息选择代价最小的程序
- 确定执行顺序

尽可能地早做选择和投影：可使中间结果变小，节省几个数量级的时间
把选择与投影串接起来：一元运算序列可一起执行，只需对整个关系扫描一遍
把投影与其前或后的二元运算结合起来：在第一次用关系时去掉一些无关属性，可以避免多次扫描整个关系
把某些选择与其前的广义积合并成一个连接：当 $R \times S$ 前有选择运算其其中有条件时 $R, S$ 属性间比较的运算时，可将其转化为连接运算可节省时间
执行连接运算前对关系做适当预处理：文件排序，建立临时索引，可使两关系公共值高效联结
找出表达式里的公共子表达式：若公共子表达式结果不大，则预先计算，以后可读入此结果

关系操作交换次序

并
差
积
选择
投影

定义 $E_1, E_2$ 是两个关系操作表达式，若 $E_1, E_2$ 表示相同的映射，即当 $E_1, E_2$ 的同名变量带入相同关系后产生相同的结果，则说 $E_1, E_2$ 是等价的，记为 $E_1 = E_2$

$E_1 Join E_2 = E_2 Join E_1$
$(E_1 Join E_2) Join E_3 = E_1 Join (E_2 \Join E_3)$
$E_1 \times E_2 = E_2 \times E_1$
$(E_1 \times E_2) \times E_3= E_1 \times (E_2 \times E_3)$
2次投影操作 $\Leftrightarrow$ $\Leftrightarrow$ 做较少属性那次的投影操作
- 两遍扫描变为一遍扫描
- 属性扩展便于投影操作的移动
2次选择操作 $\Leftrightarrow$ 一次选择操作并上2个条件
选择操作和投影操作可以进行互换
选择操作和乘积操作，可以先乘积后选择，也可以先选择其中一个再乘积
- 尽量把选择操作移动到乘积操作前
投影操作和乘积操作可以进行互换
并运算和选择操作可以互换
差运算和选择操作可以互换

尽可能的早做选择

关系操作优化算法

把复杂的选择操作进行分解，变为多次选择操作
根据上面的定理，尽可能的把选择操作移动到底部
对于投影操作，也尽可能的把移动到底部，如果是对所有属性进行投影，则去掉
把选择和投影组合为单个选择、单个投影，或者一个选择后跟一个投影
对修改后的语法树，将其内结点按以下方式分组
1. 对每个二元运算节点（积，并，差，连接）和其他所有一元运算直接祖先节点放在一组
2. 对于其后代节点，若后代节点是一串一元运算且以树叶为终点，则将这些一元运算节点放在该组中
3. 若该二元运算节点是广义积，且其后代节点不能和它组合成等连接，则不能将后代节点归入改组

例子

并发控制

并发控制就是通过事务微观交错执行次序的正确安排，保证事务宏观的独立性，完整性和正确性

保持一致性
保证并发度
降低机制复杂性

没有保证线程安全可能产生以下结果

丢失修改
不能重复读
脏读

方法：

基于封锁
基于撤回

#事务

事务管理器
- 产生事务
- 管理事务的时间戳
- 管理事务的一系列操作

事务调度

一组事务的基本步骤（读，写，加锁，解锁…）的一种执行顺序称为对这组事务的一个调度
并发/并行调度：多个事务从宏观上看是并发执行的，但其微观上的基本操作是交叉执行的

并发调度的正确性：当且仅当在这个并发调度下所得到的新数据库结果与分别串行地运行这些事务所得的新数据库完全一致时，则说调度是正确的
可串行性：如果不管数据库初始状态如何，一个调度对数据库状态的影响都是和某个串行调度相同，则我们说这个调度是可串行化的（serializable）或具有可串行性的（serializability）
冲突：调度中一对连续的动作，它们满足如果它们的顺序交换，那么涉及的事务中至少有一个事务的行为会改变

\text{并发调度的正确性} \supseteq \text{可串行性} \supseteq \text{冲突可串行性}

有冲突的两个操作时不能交换次序的，没有冲突的两个事务时可交换的
- 同一个事务的任何2个操作都是冲突的
- 不同事务对同一个事务的两个写操作是冲突的
- 不同事务对同一个事务的一读一写操作是冲突的

冲突可串行性：一个调度，如果通过交换相邻的两个无冲突的操作能够转换到某一个串行的调度，则称次调度为冲突可串行化的调度

冲突可串行是比可串行性更严格的概念
满足冲突可串行性，一定满足可串行性，反之不然

冲突可串行性判别算法

构造一个前驱图
节点是每一个事务 $T_i$
如果 $T_i$ 的一个操作与 $T_j$ 的一个操作发生冲突，且 $T_i$ 再 $T_j$ 执行，则绘制一条边，由 $T_i$ 指向 $T_j$ ，表征 $T_i$ 要在 $T_j$ 前执行
如果此有向图没有环，则是冲突可串行化的

锁

控制并发的一种手段
每一数据元素都有一唯一的锁
每一事物读写数据元素前，要获得锁
如果被其他事务持有该元素的锁，则要等待
事务处理完成后要释放锁

排他锁（X写锁）
- 只有一个事务能读、写、其他任何事务都不能读、写
共享锁（S读锁）
- 所有事务都可以读，旦任何事务都不能写
更新锁（U锁）
- 初始读，以后可以升级为写
增量锁
- 增量更新，区分增量更新和其他类型的更新

封锁协议之相容性矩阵：当某事务对一数据对象持有一种锁时，另一事务在申请对该对象加某一类型的锁，是允许还是不允许

加锁解锁时机问题

0级协议
- 事务T在修改数据R之前必须先对其加X锁，不在访问后立刻释放。事务结束包括正常结束（COMMIT）和非正常结束（ROLLBACK）。
- 不能保证可重复读和不读“脏”数据。
1级协议
- 事务T在修改数据R之前必须先对其加X锁，直到事务结束才释放。事务结束包括正常结束（COMMIT）和非正常结束（ROLLBACK）。
- 一级封锁协议可以防止丢失修改，并保证事务T是可恢复的。使用一级封锁协议可以解决丢失修改问题。
- 在一级封锁协议中，如果仅仅是读数据不对其进行修改，是不需要加锁的，它不能保证可重复读和不读“脏”数据。
2级协议
- 一级封锁协议加上事务T在读取数据R之前必须先对其加S锁，读完后方可释放S锁。
- 二级封锁协议除防止了丢失修改，还可以进一步防止读“脏”数据。但在二级封锁协议中，由于读完数据后即可释放S锁，所以它不能保证可重复读。
3级协议
- 一级封锁协议加上事务T在读取数据R之前必须先对其加S锁，直到事务结束才释放。
- 三级封锁协议除防止了丢失修改和不读“脏”数据外，还进一步防止了不可重复读。
- 上述三级协议的主要区别在于什么操作需要申请封锁，以及何时释放。

读未提交：相当于0级协议
读已提交：相当于1级协议
可重复读：相当于2级协议
可串行化：相当于3级协议

	脏读	重复读错误	幻读
读未提交	✔	✔	✔
读已提交	❌	✔	✔
可重复读	❌	❌	✔
可串行化	❌	❌	❌

幻读：指的是事务不是串行发生时的一种现象，是事务A读取了事务B已经提交的新增数据。例如第一个事务对一个表的所有数据进行修改，同时第二个事务向表中插入一条新数据，那么操作第一个事务的用户就发现表中还有没有修改的数据行，就像发生了幻觉一样，解决幻读的方法是增加范围锁或者表锁

封锁力度

封锁粒度是指封锁数据对象的大小
粒度单位：属性值->元组->元组集合->整个关系->整个DB->某索引项->整个索引
又前往后：并发度小，封锁开销小
由后往前：并发度大，封锁开销也大

两端封锁协议

读写数据之前要获得锁，每个事务中所有封锁请求先于任何一个解锁请求
两阶段：加锁段，解锁段。加锁段中不能有解锁操作，解锁段中不能有加锁操作

可能产生死锁

时间戳

事务的时间戳：

事务T启动时，系统将该时刻赋予T，为T的时间戳
时间戳可以表征一系列事务的先后次序，时间戳小的事务先执行，时间戳大的事务后执行
利用时间戳，可以不用锁，来进行并发控制

基于时间戳的并发控制

借助于时间戳，强制使一组并发事务的交叉执行，等价于一个时间戳由小到大顺序的串行执行
执行时判断冲突
- 若无冲突，则执行
- 如有冲突，则撤销事务，并重启该事务
- 此时该事务获得了一个更大是时间戳，表明是后执行的事务
有哪些冲突
- 读-读不冲突
- 读-写/写-读有冲突
- 写-写有冲突

对DB中的每个数据元素x，系统保留其上最大的时间戳

RT(x)：读过该数据事务中最大的时间戳
WT(x)：写过该数据事务中最大的时间戳
TS(T)：事务的时间戳

一种简单的调度规则

读-写并发
- 若T事务读x，则将T的时间戳TS(T)与WT(x)比较
  - 若TS(T)大（T后执行），则允许T操作，并且更改RT(x)为max(RT(x), TS(T))
  - 否则，有冲突，撤回T，重启T
- 若T事务写x，则将T的时间戳TS(T)与RT(x)比较
  - 若TS(T)大（T后执行），则允许T操作，并且更改RT(x)为max(WT(x), TS(T))
  - 否则，有冲突，撤回T，重启T
写-写并发
- 若T事务写x，则将T的时间戳TS(T)与WT(x)比较
  - 若TS(T)大（T后执行），则允许T操作，并且更改WT(x)为TS(T)
  - 否则，有冲突，撤回T，重启T

另一种调度规则

C(x)：x的提交位
- 该位为真，当且仅当最近写x的事务已经提交
- C(x)的目的是避免出现事务读另一事务U所写数据然后U终止这样的情况

对于事务T的读写请求，调度器可以

同意请求
撤销/终止T，并重启具有新时间戳的T（终止+重启，被称为回滚）
推迟T，并在以后决定是终止T还是同意请求（如果请求时读，此时读可能是脏读）

调度规则

假设调度器收到读请求R
- 如果TS(T) >= WT(x)，此读事实上可实现（但可能因为撤销造成脏读）
  - 如果C(x)为真（已经提交了），同意请求，如果TS(T) > RT(x)，置RT(x) := TS(T)，否则不改变RT(x)
  - 如果C(x)为假，推迟T直到C(x)为真或写x的事务终止
- 如果TS(T) < WT(x)，此读事实上不可实现
  - 终止并重启T（过晚的读）
假设调度器收到写请求W
- 如果TS(T) >= RT(x)，且TS(T) >= WT(x)，此写事实上可实现
  - 为x写入新的值，置WT(x) := TS(T)，置C(x) := False
- 如果TS(T) >= RT(x)，且TS(T) < WT(x)，此写事实上可实现（但x已经有一个更晚的值）
  - 如果C(x)为真，那么前一个x的写已提交，则忽略T的写，继续进行（托马斯写规则）
  - 如果C(x)为假，那么前一个x的写未提交，则推迟T的写直到C(x)为真或写x的事务终止
- 如果TS(T) < RT(x)，此写事实上不可实现
  - 终止并重启T（过晚的写）
假设调度器收到提交T请求
- 必须找到T所写的所有数据库元素x，并置C(x) := True
- 如果有任何等待x被提交的事务，这些事务就被允许继续进行
假设调度器收到终止T请求
- 像前步骤一样确定回滚T，那么任何等待T所写元素x的事务必须重新尝试读或写，看这一动作现在T的写被终止后是否合法

基于有效性确认的并发控制

事务在启动时刻被赋予唯一时间戳，以示启动顺序
为每一活跃事务保存其读写数据的集合
- RS(T)：事务T读数据的集合
- WS(T)：事务T写数据的集合
通过对多个事务的读写集合，判断是否有冲突（存在事实上不可实现的行为），即为有效性确认，来完成事务的提交与回滚，强制事务以可串行化的方式执行

基于有效性确认的调度器

事务分三个阶段进行
- 读阶段：事务从数据库中读取读集合中的所有事务，事务还在其局部地址空间计算他将要写的所有值
- 有效性确定阶段：调度器通过比较该事务与其他事务的读写集合来确认该事务的有效性
- 写阶段：事务往数据库中写入其写集合中元素的值
每个成功确认的事务都是在其有效性确认的瞬间执行的
每个事务串行的顺序即事务有效性的确认的顺序

调度器维护三个集合

START集合
- 已经开始但尚未完成有效性确定的事务集合。对此集合中的事务，调度器维护START(T)，即事务开始的时间
VAL集合：已经确认有效性但尚未完成第三阶段写的事务，对此集合中的事务，调度器维护START(T)和VAL(T)，即T确认的时间
FIN集合：已经完成第三阶段的事务，对这样的事务T，调度器记录START(T)，VAL(T)和FIN(T)，即T完成的时间

冲突一
- 假设存在事务U和T满足
  - U在VAL或FIN中，即U已经经过有效性确认
  - FIN(U) > START(T)，即U在T开始前没有完成
  - RS(T) $\cap$ WS(U)非空，特别地，设其均包含数据元素为x
- 则T和U的执行存在冲突，T不应进行有效性确认

如果一个较早的事务现在正在写入T应该读过的某些对象，则T的有效性不能确认

冲突二
- 假设存在事务U和T满足
  - U在VAL中，即U已经经过有效性确认
  - FIN(U) > VAL(T)，即U在T进入其有效性确认以前没有完成
  - WS(T) $\cap$ WS(U)非空，特别地，设其均包含数据元素为x
- 则T和U的执行存在冲突，T不应进行有效性确认

如果T在有效性确认后可能比一个较早的事务先写某个对象，则T的有效性不能确认

有效性确认规则

对于所有已经过有效性确认，且在T开始前没有完成的U，即对于满足FIN(U) > START(T)的U，检查
- RS(T) $\cap$ WS(U)是否是空
- 若为空，则确认，否则不通过
对于所有已经过有效性确认，且在T有效性确认前没有完成的U，即对于满足FIN(U) > VAL(T)的U，检查
- WS(T) $\cap$ WS(U)是否是空
- 若为空，则确认，否则不通过

故障分析

事务故障
- 某一个程序(事务)自身运行错误所引起的故障
- 影响程序事务本身
系统故障
- 由于掉电，非正常关机等引起的故障
- 影响正在运行的事务以及数据库缓冲区，数据库缓冲区将涉及正在运行和已经运行的事务
介质故障
- 由于介质损耗等所引起的故障
- 影响是全面的，即影响内存中的数据，又影响介质中储存的数据

数据库故障恢复

把数据库由当前不正确状态恢复到已知为正确的某一状态
需要保证事务的
- 原子性
- 持久性

事务故障的恢复
- 事务故障可通过重做事务和撤销事务来恢复，重做事务可保证以提交事务的持久性，而撤销事务则消除未提交事务的影响
系统故障的恢复
- 运行日志是DBMS维护的一个文件，该文件以流水方式记录了每一个事务对数据库的每一次操作及操作顺序
- 运行日志直接写入介质存储上，会保持正确性
- 当事务对数据库进行操作时，先运行日志，写成功后，再与数据库缓冲区进行信息交换
- 系统故障可通过运行日志来恢复
  - 按照运行日志记录的事务操作顺序重做事务（事务再发生故障时已正确结束）或撤销事务（事务再发生故障时未结束）
- 故障恢复时需要时间的，SBMD再运行日志中定期的设置和更新检查点
  - 在检查点，DBMS强制内存使内存DB Buffer中的内容与介质DB中的内容保持一致，即将DB Buffer更新的所有内容写回DB中
  - 检查点表征了：再检查点之间内存中数据与介质中数据使保持一致的
- 检查点之前结束的事务不需要恢复
- 检查点之后结束或发生的事务需要依据运行日志进行恢复
介质故障恢复
- 在某一时刻，对数据库在其他介质储存上产生的另一份同等记录
- 用副本替换被损坏的数据库
- 如何确定备份的时刻：转储点
  - 过频：影响系统工作效率
  - 过疏：会造成运行日志过大，也影响系统运行性能
- 备份转储周期与运行日志的大小密切相关，应注意防止接触不畅而引起的漏洞

缓冲区处理策略

Force：内存中的数据最晚在commit的时候写入磁盘
No steal：不允许在事务Commit之前把内存中的数据写入磁盘
No force：内存中的数据可以一致保留，在commit之后过一段时间再写入磁盘（此时在系统崩溃的时候可能还没写入到磁盘，需要redo）
steal：允许事务commit之前把内存中的数据写入磁盘（此时若系统在commit之前崩溃时，已经由数据写入到磁盘了，要恢复到崩溃前的状态，需要undo）

日志

一个包含日志记录的只能追加记录的顺序文件，不同事务的日志记录交错存储，按发生时间存储

发生系统故障时，使用日志进行恢复
- 故障时已提交的事务，重做
- 故障时未提交的事务，撤销
三种日志
- Undo型
- Redo型
- Undo/Redo型日志

读写性能

	No steal	steal
No force		最快
force	最慢

日志/恢复策略

	No steal	steal
No force	只需redo	需要redo，undo
force		只需undo

Undo型日志（提前输出型日志）

对于任意事务T，按下列顺序向磁盘输出T的日志信息

首先: (T, X, v)被写入到日志中
其次：OUTPUT(X)
最后：(COMMIT T)或(ABOUT T)被写入到日志中

Undo型日志保留旧值，(T, X, v)中v为X原来的值
将事务改变的所有数据写道磁盘前不能提交该事务

利用undo型日志进行恢复
- 确认事务是否完成
  - start t - commit t $\rightarrow$ 完成
  - start t - abort t $\rightarrow$ 已结束，但未完成
  - start t - $\rightarrow$ 未完成

检查点

静止检查点：周期性地对日志设置检查点
- 停止接受新的事务，等到所有当前活跃事务提交或终止，并在日志中写入了COMMIT或ABORT记录后
- 将日志刷新到磁盘，写入日志记录CKPT，并再次刷新日志
非静止检查点
- 在设置检查点时不必关闭系统，允许新事务进入
- 写入一条START CKPT(T1,…,Tk)
- 继续正常的操作，直到T1,…Tk都完成时，写入END CKPT

Redo型日志（提前记录型日志）

对于任意事务T，按下列顺序向磁盘输出T的日志信息

首先: (T, X, v)被写入到日志中
COMMIT(T)被写入到日志中
最后：OUTPUT(X)

Undo型日志保留新值，(T, X, v)中v为X更新后的值
与undo差别：在后两步，先写提交记录后输出，还是先输出，在写提交记录

利用redo型日志进行恢复
- 确认事务是否完成
  - start t - commit t $\rightarrow$ 完成
  - start t - abort t $\rightarrow$ 已结束，但未完成
  - start t - $\rightarrow$ 未完成
- 从日志的起始位置开始按照日志记录的正序处理每一条日志记录，重做已提交的事务的所有修改
  - COMMIT T：标记T已完成
  - ABOUT T：标记T已结束但未完成
  - (T, X, v)：如果T已完成，则将X=v写回磁盘，否则跳过
  - START T：跳过

检查点

非静止检查点
- 在设置检查点时不必关闭系统，允许新事务进入
- 写入一条START CKPT(T1,…,Tk)
- 将所有已提交的事务写会磁盘
- 继续正常的操作，直到T1,…Tk都完成时，写入END CKPT

Undo/Redo型日志

Undo型日志
- OUTPUT必须先做
- 如果COMMIT T可见，T确定地已将所有其数据写回磁盘，因此不必重做，但可能引起性能下降（频繁写磁盘）
Redo型日志
- OUTPUT必须后做
- 如果COMMIT T不可见，T确定地没有将任何数据写回磁盘，因此无需撤销，但灵活性差（数据必须commit后才可见）

对于任意事务T，按下列顺序向磁盘输出T的日志信息

首先: (T, X, u, v)被写入到日志中
第2/3步：COMMIT(T)被写入到日志中
第2/3步：OUTPUT(X)

保留新值，(T, X, u, v)即保留新值v，也保留旧值u

利用Undo/Redo型日志进行恢复
- 确认事务是否完成
  - start t - commit t $\rightarrow$ 完成
  - start t - abort t $\rightarrow$ 已结束，但未完成
  - start t - $\rightarrow$ 未完成
- 自前向后地，按日志记录的正序，重做所有已提交的事务
- 自后向前地，按日志记录的反序，撤销所有未完成事务的所有修改
  - COMMIT T：标记T已完成
  - ABOUT T：标记T已结束但未完成
  - (T, X, u, v)：如果T已完成，则将X=u写回磁盘，否则将X=v写回磁盘
  - START T：跳过

参考

数据库系统（哈尔滨工业大学）