数据库系统概念

第1章引言

数据抽象：

物理层：描述数据如何存储；
逻辑层：描述数据类型和数据间的相互关系；
视图层：负责如何展示数据给普通用户；

分层可以实现解耦，让某个层面的变动，尽量不会影响到其他层面；

数据库实例：特定时刻存储在数据库中所有信息的集合；内容经常会频繁发生变化

数据库模式：数据库的总体设计；较少发生变化；

数据模型：用来描述数据语义、数据关系、以及数据约束的工具；

几种数据模型：

关系模型：使用最广泛的模型；
实体-关系模型
基于对象的模型
半结构化数据模型：通常使用 xml 来表示数据；

数据库语言

数据库语言一般包含两部分的功能，一是用于定义数据库模式的数据定义语言 DDL，一是用于查询和更新数据的数据操纵语言 DML；例如常用的 SQL 语言即同时包含以上两部分功能；

数据定义语言可用来表达数据的一致性约束，包括：

域约束：所有可能取值的范围，例如整数、日期、字符等；
引用完整性：例如某个属性的值取值于另外一个表，该值必须在另外一个表中存在；
断言：满足预设的条件，例如值小于等5，大于等于0；
授权：只读，可读可写等；

DDL 的输出放在数据字典中，数据字典中保存着表的元信息，以便数据库程序能够基于这些元信息来管理表；

关系数据库

关系数据库基于关系模型，使用一系列的表，来表达数据和数据之间的关系；

DML 语句一般写在宿主语言中，分别 C、Java 等；这些 DML 语句有两种执行方式：

由宿主语言将 SQL 语句发送给数据库程序执行；
宿主语言定义自己的语法，自行生成 SQL 语句，再发送给数据库程序执行；

映射基数：一个实体关联另外一个实体的数量，例如1对1，1对多，多对多等；

存储管理部件

存储管理部件的功能：

权限和完整性检查
事务管理
文件管理：管理磁盘空间的分配和使用；
缓冲区管理：让数据在内存和磁盘之间的移动最小化；

查询处理器

DDL 解释器
DML 编译器
查询执行引擎

事务管理

事务：用于完成某个指定功能涉及的多个操作的集合；事务需要具备原子性，即这些集合中的操作要么全部完成，要么全部没有完成，而不能只完成部分操作；同时还必须确保数据的更新是正确一致的，而不是与输入的数据不相符；另外，即使数据库系统发生了故障，也不会造成已成功存储的数据的丢失；

故障恢复：虽然概率很小，但数据库发生故障是不可避免的，因此需要确保故障恢复后，数据库的数据仍然处于完整和一致的状态；假设故障前刚好有部分事务进行到一半，此时就需要回滚该事务，以便保持原子性；

并发控制：确保多个并发的事务不会相互影响进而导致数据出现不一致；

第2章关系模型介绍

关系数据库的结构

关系数据库由多张表组成；所谓的关系，指的即是“表”；

元组：多个值组成的一个序列；对应于表中的一行记录；所以表在本质上是元组的集合；

表中的每一列，即一个属性，通常对应一种数据类型，该数据类型有相应的取值范围，例如类型为“数字”的列，无法存入字符串；取值范围即所谓的“域”；

数据库模式

数据库实例是指某个时刻，数据库中所有数据的一份快照；而数据库模式是指数据库的逻辑设计；

关系有点像是变量，而关系模式有点像是类型，例如 Integer a = 10，类型是 Integer，变量是 a，值是 10；值是经常变化的，但类型不常变化；

码

在一张表中，至少需要有一个属性，能够用来区分不同的元组（行）；

超码是一个或多个属性的组合，这个组合可用来唯一标识元组的唯一性；如果某个属性能够唯一区分元组，那么它就是一个超码；

最小超码：即超码的任意子集，都不会是超码；此时的超码称为候选码；候选码可能有多组；被数据库设计者选中的，用来区分不同元组的那个候选码，称为主码；

一个关系模式（表1）中的某个属性，可能是另外一个关系模式（表2）的主码，那么该属性在表1中称为表2 的外码（外键，foreign key）；

外码是一种参照完整性的约束。这种约束有助于保证数据间的完整性，但也要付出代价；而且在某些特定情况下，这种代价还很大；

模式图

当两张表有主码和外码关系时，可以用模式图来直接的展示它们；

关系查询语言

查询语言用来从数据库中查询数据，有两种类型：

过程化语言：告诉数据库怎么做
非过程化语言：告诉数据库自己想要什么，怎么做则不管；

SQL 语言同时包含以上两个要素，既有过程化的部分，也有非过程化的部分；关系代数则是过程化的；元组关系演算和域关系演算则是非过程化的；

关系代数：以一个或多个关系做为输入，产生一个新的关系做为结果；

关系运算

自然连接运算：只匹配两张表共同属性相同的行；

笛卡尔积运算：全连接，相当于行与行的所有组合；

关系本质上是一种集合，因此也适用于集合的一些运算，例如并集、交集，差集；

第3章 SQL

SQL 查询语言概览

SQL 语言有如下一些功能：

定义数据结构
操纵数据，例如增删改查；
添加完整性约束；
定义视图；
事务控制；
支持嵌入到其他编程语言中；
控制访问权限；

注：不同数据库软件对 SQL 的支持和实现不完全相同；例如 MySQL 并不支持所有的 SQL 语法；

SQL 数据定义

DDL 涉及的定义内容包括：

表的模式
属性的取值类型
完整性约束；
索引
访问权限
在磁盘上的存储结构；

常用基本类型

char，固定长度的字符串
varchar，变动长度的字符串；
int：整数
smallint，小整数
numeric(p, d)，定点数，总共 p 位，有 d 位在小数点右边；
real：浮点数
float(n)，n 位精度的浮点数；

基本模式定义

create table department (
	dept_name varchar(20),
    building varchar(15),
    budget numeric(12, 2),
    primary key (dept_name)
);

完整性约束：

primary key，主码必须唯一且非空
foreign key references，指明该属性的值，必须是另外一个表的主键；
not null，要求该属性非空；

注：对于破坏完整性约束的 SQL 语句，数据库会拒绝执行和报错；

-- 插入数据
insert into instructor values (10211, 'Smith', 'Biology', 66000);

-- 删除表中的所有数据
delete from student;

-- 删除整张表
drop table student;

-- 表中添加两个新属性
alter table stuent add A D;

-- 表中删除一个属性
alter table student drop A;

SQL 查询的基本结构

查询的基本结构，由 selete from … where … 组成；

单关系查询

select name from instructor;

-- 去除重复项
select distinct dept_name from instructor; 

-- select 语句支持运算符，如加减乘除
select ID, name, salary * 1.1 from instructor;

-- 使用逻辑运算符，如 and, or, not
select name from instructor where dept_name = 'Comp' and salary > 7000;

多关系查询

-- 直接使用 from 实现联表查询
select name, instructor, dept_name, building
from instructor, department
where instructor.dept_name = department.dept_name;

用嵌套循环来表示联表查询

通常来说，SQL 查询可按以下模式进行逻辑上的理解：

以 from 语句中涉及的表为基础，生成笛卡尔乘积；
使用 where 中的条件，对乘积进行筛选；
对筛选结果，只输出 select 提及的属性；

注：以上只是逻辑理解，并不一定是数据库在执行 SQL 时的底层实现；

自然连接

自然连接是一种运算，运算的输入是两个表，运算的结果是一个新表；

笛卡尔积是取两个表的所有可能组合，自然连接只考虑在两个表中的共同属性上，取值相同的记录组合；

select id, name, dept_name
from teacher natural join department;

-- 以上语句要成功运行，有个前提是数据库需要知道 teacher 表和 department 表通过哪个属性建立了关系
-- 但仅从语句上面看不出来它们的关系，猜测需要在定义表的时候，明确的将关系表达出来，不然猜测无法按预期执行

-- 以下两个语句并不会产生相同的结果，因为第二个语句存在不同的意思
-- 原因在于 natural join 默认要求匹配所有共同的属性，因此它的范围比语句1更小

-- 语句1
select name, title
from instructor natural join teaches, course -- 先 natural join，再计算笛卡尔积
where teaches.course_id = course.course_id;

-- 语句2
select name, title
from instructor natural join teaches natural join course; -- 两次 natural join


-- 为了避免语句2产生的过度匹配问题，引入了join...using 语法，用来指定要匹配的列
select name, title
from (instructor natural join teaches) join course using (course_id)

附加的基本运算

更名运算

SQL 使用 as 关键字来为表或者属性起别名

select name as instructor_name, course_id
from instructor, teaches
where instructor.ID = teaches.ID;

select T.name, S.course_id
from instructor as T, teaches as S
where T.ID = S.ID;

-- 当进行表内查询比较时，重命名可避免歧义
select distinct T.name
from instructor as T, instructor as S
where T.salary > S.salary and S.dept_name = 'Biology';

字符串运算

SQL 使用单引号来表示字符串，如果字符串本身包含单引号，则需要使用两个单引号来进行转义；

一般来说，数据库会有一些支持字符串操作的函数，例如大小写转换、去除头尾空格等；不同数据库提供的函数集有所不同；

字符串支持模糊匹配：

% 百分号：表示匹配任意子串，有点类似正则里面的 * 星号；
_ 下划线：表示匹配一个字符，有点类似正则里面的？问号；

-- 建筑名称包含 Watson 子串的所有系名
select dept_name
from departments
where building like '%Watson%';

SQL 也支持使用 escape 关键字来定义转义字符，分别使用反斜线 \ 作为转义字符；

1 2	`-- 匹配所有以 ab%cd 开头的字符串 like 'ab\%cd%' escape '\'`

1 2	`-- 匹配所有以 ab\cd 开头的字符串 like 'ab\\cd%' escape '\'`

select 子句中的属性说明

星号 * 可用来表示表中的所有属性；

1
2
3

select instructor.*
from instructor, teaches
where instructor.ID = teaches.ID;

排列元组的显示次序

SQL 使用 order by 关键字来控制查询结果的顺序

select name
from instructor
where dept_name = 'Physics'
order by name;

SQL 默认使用升序 asc，如果要降序，则需要使用 desc 关键字

-- 工资降序，姓名升序
select *
from instructor
order by salary desc, name asc;

where 子句谓词

SQL 使用 between…and… 来表示范围；

1
2
3

select name
from instructor
where salary between 9000 and 10000;

SQL 支持使用元组来合并多个条件，以简化 where 条件语句，示例如下：

select name, course_id
from instructor, teaches
where (instructor.ID, dept_name) = (teaches.ID, 'Biology');

-- 等同于如下意思
select name, course_id
from instructor, teaches
where instructor.ID = teaches.ID and dept_name = 'Biology';

集合运算

三种集合运算符：

union，并集
intersect，交集；
except，差集；

并运算

union 运算会自动去除重复项，如果想保留重复项，则可以使用 union all；

1
2
3

(select course_id from section where semester = 'Fall' and year = 2009)
union
(select course_id from section where semester = 'Spring' and year = 2010);

交运算

intersect 运算也会自动去除重复；如果想保留重复，则使用 intersect all；

1
2
3

(select course_id from section where semester = 'Fall' and year = 2009)
intersect
(select course_id from section where semester = 'Spring' and year = 2010);

差运算

except 运算也会自动去除重复；如果想保留重复，则使用 except all；

1
2
3

(select course_id from section where semester = 'Fall' and year = 2009)
except
(select course_id from section where semester = 'Spring' and year = 2010);

空值

空值 null 相当于 unknown，无法参与运算符的正常计算，因为会带来不可知的结果；

空值的布尔运算：

true and unknown，结果 unknown
false and unknown，结果 false
unknown and unknown，结果 unknown
true or unknown，结果 true
false or unknown，结果 unknown
unknown or unknown，结果 unknown；
not unknown，结果 unknown；

聚集函数

聚集函数：输入多个值，返回一个值，例如：

求平均 avg
最小值 min
最大值 max
求和 sum
计数 count

基本聚集

-- 求 Comp.Sci 部门教师的平均工资
select avg (salary) as avg_salary
from instructor
where dept_name = 'Comp.Sci';

做聚集计算时，一般是不删除重复项的，因为重复项很可能具备统计学意义；但如果有些特殊场景确实需要删除重复项，那么可以使用 distinct 关键字

1
2
3

select count (distinct ID)
from teaches
where semester = 'Spring' and year = 2010;

分组聚集

SQL 使用 group by 关键字来实现分组；

-- 按 dept_name 分组计算各部门的平均工资
select dept_name, avg(salary) as avg_salary
from instructor
group by dept_name;

-- 计算每个系在 2010 年春季学期讲授一门课程的教师人数
-- 此处需要特别小心，select 中只允许填写已经出现在 group by 中的属性，除非该属性作为聚集函数的参数
select dept_name, count (distinct ID) as instr_count
from instructor natural join teaches
where semester = 'Spring' and year = 2010
group by dept_name;

having 子句

having 用于对分组后的结果进行过滤；

-- 同 select 子句，having 子句中的属性也需要出现在 group by 中，除非作为聚集函数的参数；
select dept_name, avg (salary) as avg_salary
from instructor
group by dept_name
having avg_salary > 42000;

同时包含聚集、group by、having 等关键字时，其操作顺序如下：

根据 from 提取关系；
根据 where 条件筛选关系；
根据 group by 进行分组；（如果没有 group by，则上一步的结果直接作为一个分组）；
根据 having 条件筛选分组后的结果；
根据 select 语句从以上结果读取需要的字段；

select course_id, semester, year, sec_id, avg(tot_cred)
from takes natural join student
where year = 2009
group by course_id, semester, year, sec_id
having count(ID) >= 2;

对空值和布尔值的聚集

当字段中存在空值时，聚集计算的结果有可能跟预期不符。除了 count 函数外，其他聚集函数会忽略空值（例如 sum）；

由于 null 会被忽略，因此聚集函数的参数，有可能会出现空集合的情况；此时 count 的计算结果为 0，其他聚集函数的计算结果返回 null；

嵌套子查询

子查询可以嵌套在 where 子句中，也可以嵌套在 from 子句中；

集合成员资格

关键字 in 可用来判断某个记录是否为某个集合中的成员；当前，要使用 in，意味着得先生成一个集合；

select distinct course_id from section
where semester = 'Fall' and year = 2009
and course_id in ( -- 创建集合
	select course_id from section
	where semester = 'Spring' and year = 2010;
)

集合也可以使用枚举来表示

1 2	`select distinct name from instructor where name not in ('Mozart', 'Einstein');`

可以同时检查多个属性是否在集合中，示例如下：

select count (distinct ID) from takes
where (course_id, sec_id, semester, year)
in (
	select course_id, sec_id, semester, year 
    from teaches
	where teaches.ID = 10101
);

集合的比较

集合之间可以进行比较，有点类似 js 里面的 some, all，示例如下：

-- 找出满足下面条件的所有教师，他们的工资至少比 Biology 系的某一个教师的工资要高
select name from instuctor
where salary > some ( -- 注意此处的关键字 some
	select salary from instuctor
	where dept_name = 'Biology'
);

-- 找出平均工资最高的系
select dept_name from instuctor
group by dept_name
having avg (salary) >= all ( -- 注意此处的 all
	select avg (salary) from instructor
	group by dept_name
);

空关系测试

exists 关键字是一个布尔函数，它可放在 where 子句中，用来判断某条纪录是否在一个集合中，它会返回一个布尔值；

-- 找出在 2009 秋季和 2010 春季同时开课的所有课程
select course_id
from section as S -- 此处的 S 可用在子查询中
where semester = 'Fall' and year = 2009 and 
exists (
	select course_id
    from seciton as T
    where semester = 'Spring' and year = 2010 and S.course_id = T.course_id
);

-- 找出选修了 Biology 系所有课程的学生
select S.ID, S.name
from student as S
where not exists (
    -- 找出 Biology 系的所有课程
	(select course_id
        from course
        where dept_name = 'Biology') 
    -- except 用于计算差集
    except
    -- 找出每个学生选修的所有课程
    (select T.course_id
    	from takes as T
    	where S.ID = T.ID)
)

问： in 和 exists 的区别是什么？

答：in 后面一般接一个静态的数组，例如 field in (a, b, c)；如果 in 后面是要接一个集合，那么一般可以用 join；但对于很多最新版本的数据库引擎来说，不管是使用 in 还是 join，引擎很可能会预判意图，并生成相同的执行计划；exists 是目的是快速返回一个布尔值，避免遍历，只要找到一条满足条件的纪录即可；当集合为空时，exists 会返回 false；

重复元组存在性测试

unique 也是一个布尔函数，用来判断某个查询结果，是否存在重复的元组；

-- 找出所有在 2009 年最多开设一次的课程
select T.course_id
from course as T
where unique (
	select R.course_id
    from section as R
    where T.course_id = R.course_id and R.year = 2009
);

如果 unique 的参数是一个空的集合，那么它会返回 false；

from 子句中的子查询

由于 select…from…where… 结构的返回结果是一个新的集合，那么这意味着任何接受以集合作为参数的表达式中，都可以放入一个 select…from…where… 子结构；

-- 找出系平均工资超过 42000 美元的那个系中教师的平均工资

-- 写法一
select dept_name, avg (salary) as avg_salary
from instructorl
group by dept_name
having avg_salary > 42000;

-- 写法二
select dept_name, avg_salary
from (
	select dept_name, avg(salary) as avg_salary
    from instructor
    group by dept_name
)
where avg_salary > 42000;

-- 写法三：对子查询结果进行重命名
select dept_name, avg_salary
from (
	select dept_name, avg(salary)
    from instructor
    group by dept_name
) as dept_avg (dept_name, avg_salary) -- 重命名
where avg_salary > 42000;

-- 找出所有系中工资总额最大的系
select max (total_salary)
from (
	select dept_name, sum (salary)
    from instructor
    group by dept_name
) as dept_total (dept_name, total_salary);

with 子句

with 有点像是定义一个局部变量，该局部变量指向一个临时的集合；理论上也可以直接使用子查询的结果，但用 with 能够让 SQL 更容易阅读和理解；就跟精心设计的变量名称一样；

-- 找出具有最大预算的系
with max_budget (value) as (
	select max (budget) from department
)
select budget
from department, max_budget
where department.budget = max_budget.value;

-- 找出所有工资总额大于所有系平均工资总额的系
with dept_total (dept_name, value) as (
	select dept_name, sum (salary)
    from instructor
    group by dept_name
), dept_total_avg (value) as (
    select avg (value)
    from dept_total
)
select dept_name
from dept_total, dept_total_avg
where dept_total.value >= dept_total_avg.value;

标量子查询

定义：如果子查询只返回一个值，那么该子查询称为标量子查询；对于返回只单个值的标题子查询，它可以出现在 select, where, having 中的任意位置，毕竟它只是一个值；

理论上标量子查询返回的也是一个集合，只是该集合只包含一个元组，该元组只包含一个属性；当将该集合放在只允许单个值的参数的位置时，SQL 引擎会自动从该集合的第一个元组中取出唯一的一个属性值；

-- 列出所有的系以及它们拥有的教师数量
select dept_name, (
	select count (*)
    from instructor
    where department.dept_name = instructor.dept_name
    as num_instructors
)
from department;

数据库的修改

删除

delete 关键字可用来删除一个或多个元组，但不能用来删除元组中的某个属性值；其语法结构如下：

delete from…where…

如果没有写 where 条件，则将删除表中的所有元组；

-- 删除 Finance 系的所有教师
delete from instructor
where dept_name = 'Finance';

-- 删除工资在 13000 到 15000 之间的教师
delete from instructor 
where salary between 13000 and 15000;

-- 删除在 Watson 办公的各系所有教师
delete from instructor
where dept_name in (
	select dept_name
    from department
    where building = 'Watson'
);

插入

问：什么是分量数？

-- 课程表新插入一条记录，代号 CS-437，名称 Database Systems，系名 Comp.Sci， 4 个学分
insert into course
values ('CS-437', 'Database Systems', 'Comp.Sci', 4);

-- 也可指定属性名称，这样可以不用保证顺序相同
insert into course (course_id, title, dept_name, credits)
values ('CS-437', 'Database Systems', 'Comp.Sci', 4);

insert into course (title, course_id, dept_name, credits)
values ('Database Systems', 'CS-437', 'Comp.Sci', 4);

也可以基于 select 的查询结果（元组集合），做为要插入的数据；

注：select 出来的记录需要有唯一识别的属性，做为不同记录之间的区分，例如主键；否则将可能导致重复插入的无限循环；最好的方法是确保 select 先执行完毕，之后再逐条执行插入；而边插入边 select；

-- 将 Music 系修满 144 学分的学生变成教师，工资为 18000 元
insert into instructor
select ID, name, dept_name, 18000
from student
where dept_name = 'Music' and tot_cred > 144;

考虑 insert 是逐条插入，因此当应对插入大量数据的场景时，耗时可能很久；通常数据库软件会提供一个批量插入的函数；

更新

-- 所有教师的工资上涨 5%
update instructor
set salary = salary * 1.05;

-- 给工资低于 70000 元的教师工资上涨 10%
update instructor
set salary = salary * 1.1
where salary < 70000;

-- 给工资低于平均工资的教师上涨 5%
update instructor
set salary = salary * 1.05;
where salary < (
	select avg (salary)
    from instructor
);

当需要根据条件进行不同的更新操作时，可使用关键字 case，结构为 case…when…then…else…end（有点像编程语言中的 switch…case…）；

注：如果不使用 case，而是根据条件，拆分成多条 SQL 语句，那么有可能存在顺序冲突，某些记录被重复更新，最终导致更新结果和预期不一致；

-- 目标：工资超 10 万元的教师涨 3%，其余教师涨 5%
update instructor
set salary = case
	when salary <= 100000 then salary * 1.05
	else salary * 1.03
end;

case 语句的完整结构如下：

标量子查询的结果，也可用于 update 语句中，做为 set 的目标值，示例如下：

-- 将每个 student 的总学分 tot_cred 属性设为该学生已成功学完的课程的学分的总和
-- 如果该学生暂未学完任何课程，则总学分设置为 0
update student S
set tot_cred = (
	select case
    	when sum (credits) is not null then sum (credits)
    	else 0
    end
    from takes natural join course
    where S.ID = takes.ID and
    	takes.grade <> 'F' and
    	takes.grade is not null
);

第4章中级 SQL

连接表达式

连接条件

on 同 where 一样可用于条件筛选，差别在于它和 join 固定搭配；

-- 好奇以下的 using 和 on 是否是相同的意思
select * from student natural join takes using ID;
select * from student join takes on student.ID = takes.ID;

-- 另外也可以使用 where
select * from student, takes where student.ID = takes.ID;

-- 如果 select * 和 join 同时使用，那么最终结果会包含两列 ID，它们分别来自两个表
-- 可以显式的指定想要返回的列，来避免 ID 的重复
select student.ID as ID, name, dept_name
from student join takes on student.ID = takes.ID;

另外 on 和 where 也可以组合使用，让表达能力更丰富；

外连接

有三种外连接的形式，分别是：

外连接，left outer join，只保留连接运算前的元组；
右连接，right outer join，只保留连接运算后的元组；
全连接，full outer join，保留出现在两个关系中的所有元组；

注：左连接和右连接是对称的，这意味着 A left join B 与 B right join A 的结果是等价的，唯一的区别是两者的列顺序有些不同，一个是 A 在前，一个是 B 在前；

-- 显示 CompSci 系所有学生以及他们在 2009 年春季选修的所有课程列表；2009 年春季开设的所有课程都必须显示
select * from
(select * from student where student.dept_name = 'CompSci')
full outer join
(select * from takes where semester = 'Spring' and year = 2009);

连接类型和条件

连接类型和连接条件之间可以任意组合；

视图

视图是一种虚表，在逻辑上存在，但是在物理上不存在；

感觉视图很像数据的某种形式的动态呈现；这种动态呈现可以控制显示的内容范围、显示的格式等；

视图定义

1 2	`-- 创建视图 create view <name> as <expression>`

使用视图

视图可以像真正的表那种被引用；可以实现一层一层嵌套的效果；

物化视图

当视图被频繁的引用时，对物理进行物理存储有助于提升性能；但这是有代价的，一个是更新的代价，一个是过期的代价；如果实时更新，那么会产生性能开销，不管是马上更新，还是访问时更新；如果不实时更新，则会产生过期风险；

不同数据库对物化视图有不同的实现方式，通常允许数据管理员根据实际的业务场景，选择最佳方案；

视图更新

在查询场景中，视图提供了便利，但用于插入、更新或删除场景时，存在一些缺陷；例如视图只包含部分属性，插入时，可能会遗漏基表中一些必填的属性；因此，通常应避免将视图用于查询之外的场景，除非视图满足特定的条件，这些条件包括：

from 只包含一个表
select 只包含属性名，不包含表达式、聚集、Distinct 等；
未在 select 中出现的属性允许取空值；
不包含 group by 或者 having；

虽然特定条件下，可以通过视图插入，但是插入后的结果，如果不满足视图的 where 条件的话，不一定会出现在视图中；为避免出现该情况， SQL 支持通过添加 with check option 标记来排队不满足条件的更新或插入；

事务

事务由多条查询和（或）更新的语句组成；当一条语句被执行时，就隐式的开始了一个事务；有两个关键字用于标记事务的结束，分别是：

commit work，提交事务，实现数据的持久化保存；
rollback work，回滚事务，恢复的执行 SQL 语句前的状态；

注：work 可省略；

在 SQL 语句未实现 commit 前，如果出现异常，例如断电、断网、报错等，数据库系统都会将事务回滚；

注：断电的回滚需要在重启后执行；

大部分 SQL 实现会默认为单条 SQL 语句开启一个事务；如果需要将多条 SQL 语句打包成一个事务，就需要通过关键字关闭该默认功能；不同的 SQL 实现有不同的语法，常用的如 begin atomic…end；

完整性约束

完整性约束用于确保数据库中的数据始终处于一致性的状态，避免被错误的操作破坏；常见的约束示例：

某个属性的值不允许为空；
某个属性的值需要大于0；
某个属性的值不允许重复，需要唯一；
某个属性的值必须在另外一张表中存在；

理论上可添加任意条件的约束，但条件越复杂，检测的成本就越高，因此需要折中平衡；

完整性约束可以在定义表结构时声明，也可以后补

1 2	`-- 后补完整性约束 alter table tableName add contraint...`

单个关系上的约束

在使用 create table 定义表结构时，可添加相应的完整性的约束，例如主键约束、not null、unique、check 等；

not null 约束

1 2	`name varchar(20) not null budget numeric(12, 2) not null`

unique 约束

1 2	`-- 声明 A/B/C/D 四个属性的组合需要唯一 unique (A, B, C, D)`

check 子句

check 关键字用于添加限定条件，属性的取值需要满足该条件；

-- 模拟枚举
create table section (
	semester varchar(6),
    check (semester in ('Spring', 'Summer', 'Fall', 'Winter'))
);

参照完整性

-- 确保某个属性的取值必然出现在另外一个表中
-- 关键字：foreign key (<column_name>) references <table_name>
create table instructor (
	ID varchar(5),
    name varchar(20), not null
    dept_name varchar(20),
    salary numeric(8, 2), check (salary > 20000),
    primary key (ID),
    foreign key (dept_name) references department -- 显式声明外键，实现参照完整性
)

参照完整性可用来实现级联操作

create table course (
	...
    foreign key (dept_name) references department
    on delete cascade -- 级联删除
    on update cascade, -- 级联更新
    ...
)

除了 cascade 级联的删除和更新，还可以实现 set null 或者 set default；

事务中对完整性约束的违反

事务通常包括多个操作，执行到中间阶段时，完整性约束可能暂时无法满足，而是在完成所有操作后，完整性约束才会得到满足。针对这种情况，可以添加 initially deferred 关键字，显示声明完整性约束在需要的时候，可以延迟检查；

完整性约束默认是立即检查，而且并不是每种数据库实现都支持延迟检查；

复杂 check 条件与断言

复杂的 check 条件，例如在 check 中包含子查询，对实现完整性约束帮助很大，但有可能代价也很大，因为一个操作可能会触发一系列正向或逆向的检查操作；

断言也是一种条件判断，格式如下：

1	`create assertion <assertion_name> check <predicate>;`

-- 每个 student 的 tot_cred 属性的取值，必须等于其所完成的所有课程的学分总和
create assertion credits_earned_constraint check (
	not exists (
    	select ID
        from student
        where tot_cred <> (
        	select sum(credits)
           	from takes natural join course
           	where student.ID = takes.ID
            and grade is not null
            and grad <> 'F'
        )
    )
);

目前市场上大部分的数据库软件还不支持在 check 中使用子查询，或者使用 create assertion 结构，但很多可以通过触发器来实现类似的效果；

SQL 的数据类型与模式

SQL 中的日期和时间类型

与日期时间相关的几种类型：

date，‘2001-04-25’
time，’09:30:00.45’，秒部分可能包含小数；
timestamp，’2001-04-25 09:30:30.45’，如果声明 with timezone，则时区信息也会存储

SQL 有自带一些返回当前日期或时间的函数：

current_data
current_time
local_time
current_timestamp
local_timestamp

以上几个类型都支持比较运算；同时也支持算术运算，即计算两个时间点之间的差，例如：dateX - dateY

默认值

SQL 允许为属性指定默认值

create table student (
	ID varchar(5),
    name varchar(20) not null,
    dept_name varchar(20),
    tot_cred numeric(3, 0) default 0, -- 指定默认值0
    primary key (ID)
);

创建索引

1 2	`-- 不同数据库创建索引的语法格式可能不同 create index studentID_index on student(ID);`

大对象类型

SQL 提供两种数据类型，用于存储非常大的数据值：

clob，字符类型的大对象
blob，二进制类型的大对象

lob 是 large object 的缩写

1
2
3

book_review clob (10KB)
image blob (10MB)
movie blob (2GB)

当对象很大时，全部加载到内存中，资源开销很大；更好的做法是返回一个地址引用即可，之后在代码中使用该引用，对对象进行操作，这样效率更高；跟操作系统使用 read 函数返回文件描述符类似；

用户定义的类型

SQL 支持两种自定义类型：

distinct type，独特类型（感觉有点像为某种类型定义起个变量名，这样方便复用和维护）；
structured data type，结构化数据类型，支持嵌套、数组、多重集等，类似 JSON；

-- 创建自定义类型
create type Dollars as numeric (12, 2); 

create table department (
	dept_name varchar(20),
    building varchar(15),
    budget Dollars -- 引用自定义类型
);

1
2
3

-- 删除或更新自定义类型
drop type ...
alter type ...

由于强类型检查, 定义为 numeric （12， 2）类型的 budget 属性，如果用于以下场景： budget + 20 将会报错；SQL 还支持一种 domain 的语法

1	`create domain Dollars as numeric(12, 2) not null;`

create domain 和 create type 有如下一些区别：

domain 支持声明约束，例如 not null；type 不支持
domain 支持设置默认值；type 不支持；
domain 不会做强类型检查，因此只要基本类型兼容，表达式 budget + 20 就不会报错；

-- domain 支持添加 constraint 约束
create domain YearSalary numeric(8, 2)
	constraint salary_value_test check (value >= 29000);
	
create domain DegreeLevel varchar(10)
	constraint salary degree_level_test check (value in ('Bachelors', 'Master', 'Doctor'));

注：不同的数据库软件对 domain 和 type 的支持不尽相同，语法和解释也可能不同，实际使用时，需要查阅官方文档为准；

create table 的扩展

1 2	`-- 使用 like 关键字，可创建与现有表的结构相同的新表 create table temp_instructor like instructor;`

在编写复杂的查询语句时，为了提高语句的易读性，可考虑将某个查询结果起个临时的名字，以便阅读或后续引用

create table t1 as (
	select * 
    from instructor
    where dept_name = 'Music'
) with data;

-- with data 用于显式的声明老百姓加载数据到 t1，但多数数据库软件支持省略该关键字，会自动默认加载数据；

此处表 t1 没有单独定义属性的名称和数据类型，它会从查询结果中自动推导出来；当然，也可以显式的指定列名；

模式、目录与环境

当前的数据库软件基本采用三层结构来组织数据，包括

目录：catalog，也称为数据库
模式：schema
表：table

每个登录到数据库的用户都会分配一个默认的目录和模式，通过三层结构，可以唯一标识一个表：catalog1.schema2.course3；

如果访问默认目录和模式下的表，那么前两层结构可以省略；如果访问其他目录和模式，则需要显式的指定目录和模式名称；

当建立一个数据库连接时，数据库应用将会为该连接创建一个 SQL 环境，该环境包含默认的目录和模式；通常情况下，当创建用户账户时，将会自动创建一个模式，此时用户的账号名称，将被作为模式名；

create schema 和 drop schema 可用来创建和删除模式；

授权

可授权的动作：增删改查；

可授权的范围：表、视图、模式等；

授权的授予与收回

关键字 grant 用来授权权限

-- SQL 新增授权
grant <权限列表>
on <表名或视图名称>
to <用户或角色>

-- 示例：授予查询权限
grant select on department to Amit, Satashi;

-- 只授予某个字段的修改权限
grant update (budget) on department to Amit;

内置用户名 public 代表所有用户的角色，当对 public 进行授权时，意味着所有用户都会获得相关的权限；

SQL 可以指定授权哪些字段，但无法指定授权哪些元组；

关键字 revoke 用来撤销授权；

-- SQL 撤销授权
revoke <权限列表>
on <表名或视图名称>
from <用户或角色>

-- 示例：撤销查询权限
revoke select on department from Amit;
revoke update (budget) on department from Amit;

角色

授权角色和授权用户所使用的语句都是一样的；

-- 创建角色
create role instructor;
-- 给角色授权
grant select on takes to instructor;
-- 给用户添加角色
grant instructor to Amit;

-- 除了给用户添加角色，还可以给其他角色添加角色
create role dean;
grant instructor to dean;
grant dean to Satoshi;

视图的授权

当只允许查看部分数组时，可考虑使用视图来实现；创建一个只包含该部分数据的视图，然后授予用户该视图相关的权限；

-- 注意，创建以下视图的人，需要具备instructor 表的 select 权限
create view geo_instructor as (
	select *
    from instructor
    where dept_name = 'Geology'
);
grant select on geo_instructor to Tom;

模式的授权

只有 schema 的拥有者，才能执行与 schema 相关的操作，例如新增或删除表、增加或删除表中的属性、增加或删除索引等；

外键 referenece 由于存在联动更新效应，因此它的权限需要单独设置

1 2	`-- 授予外键权限 grant references (dept_name) on department to Mariano;`

权限的转移

普通用户默认无法转授权自己当前获得的权限；但管理员在授权时，可通过添加 with grant option 以便用户可以转授权；

1	`grant select on department to Amit with grant option;`

权限的收回

拥有权限的充分必要条件：在权限图中，存在从根节点出来，到达当前节点的路径；此特性将导致权限的撤销存在级联效应，即头部用户的授权撤销后，其之前给其他用户的转授权也随之失效；

1 2	`-- 可通过 restrict 关键字来取消授权的级联撤销 revoke select on department from Amit restrict;`

1 2	`-- 撤销转授权 revoke grant option for select on department from Amit;`

使用 granted by currect_role，可实现使用角色来授权；因为权限是挂属在角色下面，这样当某名父用户被收回权限时，也不会导致子用户的权限也被撤销；

第5章高级 SQL

使用程序设计语言访问数据库

通用语言有两种方法与数据库进行交互：

动态 SQL：由通用语言动态生成 SQL 语句，然后交由相应的数据库接口，例如 JDBC 或者 ODBC，传输给数据库执行；
嵌入式 SQL：有点像是静态 SQL，即先将写好的 SQL 交给数据库预编译成相应的代码和函数，然后嵌入在通用语言中进行调用；

JDBC

全称：Java Database Connectivity，Java 与数据库进行连接的接口（或者称为库），方便不同的应用程序复用，避免重复造轮子；

注：JDBC 只包含了接口，没有限制使用哪种通信协议；

public static void JDBCexample(String userId, String passwd) {
    try {
        Class.forName("oracle.jdbc.driver.OracleDriver");
        Connection conn = DriverManager.getConnection(
        	"jdbc:oracle:thin:@db.yale.edu:1521:univdb", userId, passwd
        );
        Statement stmt = conn.createStatement();
        try {
            stmt.executeUpdate(
            	"insert into instructor values ('77987', 'Kim', 'Physics', 98000)"
            );
        } catch (SQLException sqle) {
            System.out.println("Cound not insert tuple: ", tuple);
        }
        ResultSet rset = stmt.executeQuery(
        	"select dept.name, avg(salary) " +
            "from instructor " +
            "group by dept_name"
        );
        while (rset.next()) {
            System.out.println(
                rset.getString("dept_name") + " " + rset.getFloat(2)
            );
        }
    } catch (Exception sqle) {
        System.out.println("Exception: " + sqle);
    }
}

JDBC 工作步骤：

与数据库建立连接；
向数据库发送 SQL 语句；
获取查询结果；

预备语句

相当于预编译，语句中的动态部分使用参数填充；

// 预备语句：使用 ? 做为点位符
PrepareStatement pStmt = conn.prepareStatement("insert into instructor valeus(?, ?, ?, ?)");
pStmt.setString(1, '88877'); // 参数索引的起始值竟然是 1，而不是常规的 0，有点奇怪
pStmt.setString(2, "Perry");
pStmt.setString(3, "Finance");
pStmt.setInt(4, 125000);
pStmt.executeUpdate();
pStmt.setString(1, '88878');
pStmt.executeUpdate();

可调用语句

使用 JDBC 提供的 CallableStatement 接口，可调用 SQL 的存储过程和函数；

CallableStatement cStmt1 = conn.prepareCall(" { ? = call some_function(?) }");
CallableStatement cStmt2 = conn.prepareCall(" { call some_procedure(?, ?) }");

// 函数的返回值，以及过程的参数类型，即 ? 点位符指代的部分，需要先使用方法 registerOutParameter 进行定义

此处 prepareCall 的原理和 prepareStatement 类似，差别仅在于调用不同的东西；

元数据特性

数据类型通常使用 SQL DDL 进行定义，因此默认情况下，应用程序的代码并不包含这部分信息，因此需要通过 JDBC 的接口从数据库中获取该信息，以便知道如何正确的处理数据；在 JDBC 返回的结果 ResultSet 对象中，有一个 getMetaData 的方法，可以通过 ResultSetMetaData 对象，获取表结构的元信息，例如列数量、列名、列的数据类型等；

ResultSetMetaData rsmd = rs.getMetaData();
for (int i = 1; i <rsmd.getColumnCount(); i++) { // JDBC 的起始索引是 1，与众不同
    System.out.println(rsmd.getColumnName(i));
    System.out.println(rsmd.getColumnTypeName(i));
}

获取元数据信息的接口，可以让应用程序的代码和数据库软件之间解耦；代码无需关心具体的数据库类型，而是交由 JDBC 进行适配；

其他特性

可更新的结果集：对结果集的更新，会引起数据库中相应元组的更新：

大对象处理接口：

读取：不用将整个大对象读入内存，而是通过地址 + 偏移来实现对大对象的操作，有点像文件流的机制；
定入：将大对象与输入流绑定，数据不用全部加载内存再写入，而是分批定入；

ODBC

open database connectivity，数据库连接标准，让不同数据库和不同的开发语言之间实现解耦，这样只需遵守该标准，即可实现互连；通常每个数据库软件都会提供一个实现 ODBC 接口的 SDK ，方便开发人员调用；

对于用 C 语言编写的 ODBC API 来说，它会根据表中各字段的数据类型和长度，为每个字段预先分配内存；在建立连接发送 SQL 语句后，将返回结果存放在预先分配的内存中；返回的状态有可能是失败的，也有可能是成功的；如果成功，就将返回值存放在之前预分配的内存中；如果某个字段的返回值的长度为 -1，则说明返回值为空；

ODBC 包含很多不同的函数，处理不同类型的 SQL 语句；默认情况下，每个 SQL 语句视为一个独立的事务；如果想手工控制事务的提交和结束，可在 Option 选项中进行设置；

嵌入式 SQL

SQL 可以嵌入在不同的程序语言中，例如 C, C++, Java 等；此时 SQL 语句将由该程序语句进行预处理，然后替换成程序语言的某个内置函数，最后统一交由程序语句的编译器进行编译；而在 JDBC 中，SQL 语句是在运行的时候，才进行编译的；

注：对于嵌入式 SQL，不同的程序语言有不同的语法

EXEC SQL
    declare c cursor for  // 使用 declare 关键字定义 SQL 语句
    select ID, name
    from student
    where tot_cred > :credit_amount; // 此处使用冒号来标识 credit_amount 是宿主语言中的变量
        
EXEC SQL open c; // 使用 open 关键字执行 SQL 语句
EXEC SQL fetch c into :si, :sn; // 使用 fetch 取出 SQL 语句的执行结果，si、sn 分别对应 ID、name
EXEC SQL close c; // 使用 close 关键字通知数据库那边删除查询结果的临时表；

update、insert、delete 等语句不返回结果

可使用 EXEC SQL COMMIT 或 ROLLBACK 来提交或者回滚；

函数和过程

函数和过程可将“业务逻辑”存放在数据库中，以便在数据库软件进行执行；它的一个好处是数据库从硬盘取出数据后，无需网络传输给代码，而是就地计算，之后只返回计算结果即可；当数据集较大时，这种方法能够有效的降低网络开销；另外一个好处是同样的“业务逻辑”可以被多个应用程序之间共享；

函数和过程可使用 SQL 进行定义，也可使用程序语言进行定义；不同的数据库软件，其定义函数的 SQL 语法略有不同；

声明和调用 SQL 函数和过程

-- 声明函数，计算某个系的教员数量
create function dept_count(dept_name varchar(20))
	returns integer
	begin
	declare d_count integer
		select count(*) into d_count
		from instructor
		where instructor.dept_name = dept_name
	return d_count
	end
	
-- 使用该函数
select dept_name, budget
from department
where dept_count(dept_name) > 12;

SQL 定义的函数除了返回单个值外，也支持返回表，这类函数称为表函数；声明返回类型的时候，需要定义表的相关字段；

create function instructor_of (dept_name varchar(20))
	returns table (
        ID varchar(5),
        name varchar(20),
        dept_name varchar(20),
        salary numeric(8, 2)
    )
    return table (
    	select ID, name, dept_name, salary
        from instructor
        where instructor.dept_name = dept_name
    )

-- 调用该函数，语法跟返回单个值的函数有些区别，多了一个 table 关键字
select * from table (instructor_of('Finance'));

SQL 也支持定义存储过程，从名称来看，包含了“存储”二字，这意义着存储过程不仅可以返回查询结果，还可以更新或删除数据，不返回结果。更加灵活一些，用途更加广泛；函数更适用于完成一些单一的小任务，然后通过组合去完成一个大的查询任务；

-- 声明过程
create procedure dept_count_proc(in dept_name varchar(20), out d_count integer)
	begin
		select count(*) in d_count
		from instructor
		where instructor.dept_name = dept_count_proc.dept_name
	end
	
-- 使用过程，使用 call 关键字进行调用
declare d_count integer
call dept_count_proc('Physics', d_count);

过程和函数都支持同名重载，即允许参数个数或类型不同，但过程或函数的名称相同；

支持过程和函数的语言构造

SQL 有一套自己的编程语法，通过该语法，SQL 可以实现与其他编程的几乎所有功能；例如：

使用 declare 声明变量（JS 使用 var / let / const 等）
使用 set 给变量赋值（其他编程语言一般使用等号 =）
复合语句使用 begin…end 包裹（其他编程语言一般使用 {…}）
- begin atomic … end 可用来声明事务
使用 while、repeat、for 来实现循环
退出循环用 leave（其他编程语言用 break）
跳过当前循环用 iterate（其他编程语言用 continue）
使用 if-then-else、case 实现条件分支
使用 signal 来抛出异常（其他编程语言用 throw）

尽管 SQL 接近图灵完备，但问题是它缺少库，而且它为了让非开发人员容易上手，牺牲了语法的灵活结构，导致它在有序集合、对象引用方面存在先天的缺陷，复杂查询的 SQL 语句难以阅读和维护；为解决该问题，后来推出了 SPL 语言；

while 条件判断 do
	一条或多条执行语句;
end while


repeat
	一条或多条执行语句;
until 条件判断
end repeat


declare n integer default 0;
for r as -- 这里的 as 有点像 in 的意思，r 代表结果中的每一行，类似 python 里面的 for i in list;
	select budget
	from instructor
	where dept_name = 'Music'
do
	set n = n - r.budget
end for;


if 条件判断
	then 一条或多条执行语句
elseif 条件判断
	then 一条或多条执行语句
else
	一条或多条执行语句
end if

declare out_of_classroom_seats condition
declare exit handler for out_of_classroom_seats
create function registerStudent(
	in s_id varchar(5),
    in s_courseid varchar(8),
    in s_secid varchar(8),
    in s_semester varchar(6),
    in s_year numeric(4, 0),
    out errorMsg varchar(100)
    
    returns integer
    
    begin
    	declare currEnrol int;
    	select count(*) into currEnrol
    	from takes
    	where course_id = s_courseid and sec_id = s_secid
    		and semester = s_semester and year = s_year;
    
    	declare tot_limit int;
    	select capacity into tot_limit
    	from classroom natural join section
    	where course_id = s_courseid and sec_id = s_secid
    		and semester = s_semester_id and year = s_year;
    
    	if (currEnrol < tot_limit)
    		begin
    			insert into takes values
    				(s_id, s_courseid, s_secid, s_semester, s_year, null);
    			return(0);
    		end
    	else
    		set errorMsg = 'Enrollment limit reached for course ' || s_courseid
    			|| ' section ' || s_secid;
    		return(-1);
    end;
)

虽然 SQL 标准有规定函数和过程的语法，但实际上各个数据库软件并不完全遵照该语法，而是有各自的一套ygif；主要原因在于标准出现的比较晚，而数据库软件的实现更好，为了保持兼容，就一直按旧的自身标准了；

外部语言过程

函数和过程可以在 SQL 中定义，也可以使用编程语言进行定义，作成外部库或插件，供数据库软件进行调用，这样扩展性更好，也能够进行更加复杂的计算。这些定义好的函数，可直接在 SQL 中进行调用；

-- 注：不同的数据库软件在调用外部语言编写的库时，可能使用不同的语法
create procedure dept_count_proc(in dept_name varchar(20), out count integer)
language C
external name '/usr/avi/bin/dept_count_proc'

create function dept_count(dept_name varchar(20))
returns integer
language C
external name '/user/avi/bin/dept_count'

外部函数除了需要处理入参和出参，还需要传递操作状态，即成功或者失败，以便调用者可以处理异常；

为了避免外部语言随意访问和操作数据库管理的数据，一般数据库软件会创建某个沙盒，来运行外部程序，以便实现隔离；不同的数据库软件，能够支持的外部编程语言有所不同；

触发器

触发器是在某种条件下可以被自动执行的语句，它由三部分组成：

待触发的事件；
待满足的条件判断；
待执行的动作；

对触发器的需求

触发器的使用场景：

用来实现某些完整性约束；
用来发送警报；
用来自动执行某个任务；例如库存低于最小量时，自动生成一条订货记录；

SQL 中的触发器

-- 使用触发器检查 section 表中属性 time_slot_id 的参照完整性
create trigger timeslot_check1 after insert on section -- 插入后检查
	referencing new row as nrow
	for each row
	when (nrow.time_slot_id not in ( -- 检查是否满足参照完整性
        select time_slot_id
        from time_slot
    ))
    begin
    	rollback -- 不满足的话，就回滚
    end;
    
create trigger timeslot_check2 after delete on time_slot -- 删除时检查
	referencing old row as orow
	for each row
	when (orow.time_slot_id not in (
        select time_slot_id
        from time_slot
    ) and orow.time_slot_id in (
        select time_slot_id
        from section
    ));
    begin
    	rollback
    end;

更新操作也可以设置触发器

create trigger credit_earned after udpate of takes on (grade)
	referencing new row as nrow
	referencing old row as orow
	for each row
	when nrow.grade <> 'F' and nrow.grade is not null
		and (orow.grade = 'F' or orow.grade is null)
	begin atomic
		update student
		set tot_cred = tot_cred + (
            select credits
            from course
            where course.course_id = nrow.course_id
        )
        where student.id = nrow.id;
    end;

除了增删改查，许多数据库软件还支持其他各种事件，例如登录数据库、改变设置、数据库停止等；

-- 在事件发生前的触发器
create trigger setnull before update of takes
	referencing new row as nrow
	for each row
	when (nrow.grade = "")
	begin atomic
		set nrow.grade = null;
    end;

触发器除了可以监控行的事件（行触发器），也可以监控 SQL 的语句（即语句触发器）；

触发器创建后，默认开启。但也可以手工暂时禁用或者删除；

何时不用触发器

如果某些事情能够由数据库自带的功能进行解决，那么则应避免使用触发器，例如级联操作、物化视图、复制备份数据库等；

触发器潜在问题：

导入备份数据时，如果未关闭触发器，会引起预期外的操作；
闭环的事件，可能造成死循环；

原则：如果有其他办法，则优先不考虑使用触发器；

递归查询

用迭代来计算传递闭包

-- 根据课程id查找该课程的所有前置课程
create function findAllPrereqs(cid varchar(8))
	returns table (course_id varchar(8))
	begin
		create temporary table c_prereq (course_id varchar(8)) -- 所有前置课程
		create temporary table new_c_prereq (course_id varchar(8)) -- 当前前置课程
		create temporary table temp (course_id varchar(8)) -- 中间变量
		insert into new_c_prereq
			select prereq_id
			from prereq
			where course_id = cid;
		repeat
        	insert into c_prereq
                select course_id
                from new_c_prereq;
            insert into temp (
                select prereq.course_id
                from new_c_prereq, prereq
                where new_c_prereq.course_id = prereq.prereq_id
            ) except (
                select course_id
                from c_prereq
            );
            delete from new_c_prereq;
            insert into new_c_prereq
            	select *
            	from temp;
            delete from temp;
            
            until not exitst (select * from new_c_prereq)
        end repeat;
        return table c_prereq;
    end;

SQL 中的递归

SQL 支持使用 with recursive 来表达递归（有限形式）；

with recursive rec_prereq(course_id, prereq_id) as (
    -- 找出当前课程对（基查询）
	select course_id, prereq_id
    from prereq
    union
    -- 找出当前课程对的前置课程对（递归查询）
    select rec_prereq.course_id, prereq.prereq_id
    from prereq, rec_prereq
    where prereq.course_id = rec_prereq.prereq_id
)
select *
from rec_prereq;

常规编程语言中的递归本身就有些小抽象，结果发现 SQL 写出来的递归，更是抽象中的抽象；毕竟日常的递归还使用了函数进行封装，降低了理解的难度；结果发现 SQL 这里，连封装都没有；

高级聚集特性

排名

排名：查找某个值在一个有序集合中的位置；

SQL 使用 rank() over (order by 属性顺序) 关键字来计算某个值的排名；

-- 排名使用 rank 实现，性能更好（猜测数据库针对该关键字，有单独的实现）
select ID, rank() over (order by (GPA) desc) as s_rank
from student_grades
order by s_rank;

-- 排名实现 count 实现，当表太大时，计算起来较为费时
select ID, (1 + (
    select count(*)
    from student_grades B
    where B.GPA > A.GPA
)) as s_rank
from student_grades A
order by s_rank;

考虑到不同行存在相同的值，例如有两个分数一样的第2名，因此 rank() 排名值有可能是不连续的整数；

rank 还支持按分区进行单独排名，例如学生在其所在系里面的排名，这样每个系的排名是单独计算的；

1
2
3

select ID, dept_name, rank() over (partition by dept_name order GPA desc) as dept_rank
from dept_grades
order by dept_name, dept_rank;

ntile 函数可按照一定的规则将结果进行分组，例如按分数所在的区间段，分成 A, B, C, D 等多个等级；

select ID, ntile(4) over (order by GPA desc) as quartile
from student_grades

-- 如果存在空值，则需要相应的处理，指示空值优先 nulls first，还是放在最后 nulls last
select ID, ntile(4) over (order by GPA desc nulls last) as quartile
from student_grades

分窗

窗口与分组最大的区别在于，窗口允许同一个元组出现在多个窗口中出现，这样可以很方便的计算移动平均值；

-- 假设存在视图 tot_credits(year, num_credits)，记录每年学生的总学分

-- 求最近三年的平均学分（注：每个年份的最近三年有所不同，例如对 2009 年，其他最近三年是 2007，2008 和 2009）
-- 关键字 rows 表示按行数计算范围
-- 关键字 preceding 是指前面的意思，例如 3 preceding 指前面三个元组
select year, avg(num_credits) over (order by year rows 3 preceding) as avg_total_credits
from tot_credits;

-- 求截止当年的历史总平均学分
-- 关键字 unbounded 表示数量不限，即涵盖前面所有的元组
select year, avg(num_credits) over (order by year rows unbounded preceding) as avg_total_credits
from tot_credits;

-- 指定窗口的范围，前 3 后 2
select year, avg(num_credits) over (order by year rows between 3 preceding and 2 following) as avg_total_credits
from tot_credits;

-- 用关键字 range 代替 rows 来指定取值范围
select year, avg(num_credits) over (order by year between year - 4 and year) as avg_total_credits
from tot_credits;

窗口函数也支持分区计算

-- 假设存在视图 tot_credits_dept(dept_name, year, num_credits)，记录每年学生的总学分
select dept_name, year, avg(num_credits) 
	over (partition by dept_name order by year rows between 3 preceding and current row)
	as avg_total_credits
from tot_credits_dept;

OLAP

全称：online analytical processing，联机分析处理，主要用于数据统计分析的场景；

联机分析处理

元组通常由多个属性构成，其中有些属性属于“度量属性”，例如商品销量；某些属性属于“维属性”，例如商品颜色、尺寸等；如果某个数据集合能够模式化“维属性”+“度量属性”，那么称之为多维数据；

二维交叉表（也叫转轴表，很像 Excel 里面的数据透视表）：

三维交叉表：

立方体角上有一个 all 字样，表示汇总的值；

当使用不同的维度对数据进行统计时，称为 pivoting（书中翻译为“转轴”）；如果只查到某个维度下某个具体值的其他维度统计，称为“切片（slicing）”，相当于查看立方体的剖面；

之所以叫“转轴表”，貌似是因为其英文是 pivot，感觉有点机械翻译的感觉，在中文的语境中，或许翻译为多维统计表更好一些；

相同的属性，可以细分成多个不同的颗粒度，然后在不同的颗粒度上面进行统计；例如同样是时间维度，颗粒度可以是小时、天、周、月、年等；

交叉表与关系表

交叉表跟关系表存在明显的区别，但可看做关系表的按某种维度的聚合；对于聚合的属性，可使用 all（null）表代指聚合的所有可能取值；

加快统计查询的一种办法是预计算；但是对于 n 个维度的表，存在 2^n 种的组合可能。因此只能预计算部分常用的组合，不然预计算结果将要比原始基表占用多得多的存储空间；另外一种方法是预计算部分细颗粒度的组合；之后精颗粒度的组合可以基于细颗粒度计算得出，从而避免全表扫描，即 rollup；

SQL 中的 OLAP

部分数据库软件支持实现 pivot 关键字创建交叉表，例如 SQL Server 和 Oracle；

select *
from sales
pivot (
	sum(quantity)
    for color in ('dark', 'pastel', 'white')
)
order by item_name;

查询结果如下：

如果使用简单的 group by 关键字进行多维度的聚合时，也是可行的，但是每个维度都需要单独计算一遍，性能并不理想；SQL 引入了 cube 关键字，来避免这个问题；

1
2
3

select item_name, color, clothes_size, sum(quantity)
from sales
group by cube(item_name, color, clothes_size);

以上 SQL 语句产生的查询模式如下：

（item_name, color, clothes_size, sum(quantity)

如果修改一下语句

1
2
3

select item_name, color, sum(quantity)
from sales
group by cube(item_name, color)

产生结果如下：

关键 rollup 也可用于生成交叉表，而且由于它是基于上一个聚合结果去生成下一个聚合，因此它的性能比 cube 会更好一些；尤其是在基于层次结构的查询中特别有用；

第6章形式化关系查询语言

关系代数

关系代数：一种过程化查询语言，它由一系列运算组成，常见的运算如选择、投影、并、差、积等；这些运算通常以1~2个关系（即表）做为输入，产生一个新的关系做为结果；其他运算还包括集合交、自然连接、赋值等；

基本运算

基本运算类型：

一元运算：对一个关系进行运算，例如选择、投影、更名等；
二元运算：对两个关系进行运算；

选择运算

此处使用希腊字母 σ （念做 sigma）表示选择，即 select；将选择条件（即谓词）写在下标中；

多个条件（谓词）可使用 and（∧）, or（∨）, not 进行连接

投影运算

一元运算，返回指定的列；用大写希腊字母 pi（π）表示：

关系运算的组合

关系运算的结果也是一个关系，因此，不同的运算可以进行组合，构成关系代数表达式，类似使用加减乘除符号组合而成的表达式；

示例：找出物理系教师的名字

并运算

将两个关系运算表达式的计算结果，合并起来，即计算并集 r U s；

注：由于关系是一种集合，因此并集会自动去重；

合并需满足以下两个条件：

两个关系的属性数目需要相同；
每个属性的域（取值范围）需要相同；

关系代数的形式化定义

附加的关系代数运算

扩展的关系代数运算

元组关系演算

域关系演算

第7章数据库设计和 E-R 模型

设计过程概览

实体-联系模型

约束

从实体集中删除冗余属性

实体-联系图

转换为关系模式

实体-联系设计问题

扩展的E-R特性

数据建模的其他表示法

数据库设计的其他方面

第8章关系数据库设计

第9章应用设计和开发

第10章存储和文件结构

物理存储介质概述

磁盘和快闪存储器

RAID

第三级存储

文件组织

一个数据库通常由多个不同的文件组成，每个文件代表一张表；这些文件存储在磁盘上面，由操作系统来管理和维护；一个文件在逻辑上是由多个记录组成的一个序列；

块是数据存储和分配的基本单元，一个文件由多个块组成；块的长度通常是固定的，例如4~8KB；当然，也可以在创建数据库时，手动设置块的大小；

一个块通常包含多条记录；块至少要大于单条记录的长度，以免将单条记录存储在多个块中。因为数据读取是以块为单位的，如果跨块的话，将导致额外的性能损耗，一条记录要读取至少两个块；

当然，一个块的空间不可能百分百复用起来，刚刚全部用于存储数据，不可避免存在一些小小的浪费；

定长记录

当某条记录被删除时，它所占据的空间将会空闲出来；如果让后续新插入的记录利用该空间是一个有趣的问题；在块的头部，会记录该块中第一条可用空闲记录的指针（地址）。这样在插入新记录时，能够快速定位，找到可存储记录的位置；同时更新空闲指针到下一个可用记录的位置上；

每个可用记录的地址，存储在上一个可用记录的空间中；直至第一个记录存储在文件头部；这些地址构成了一个链表（空闲列表）；

变长记录

有几种不同形式的变长记录

某个字段的类型是数组；
一个文件包含多种记录类型；
某个字段是变长的，例如 varchar；

变长记录需要解决两个问题：

如何存储和描述一条记录，以便能够快速读取记录中的某个属性的值（注：由于数据读取是以块为单位，因此当读取属性时，记录实际上已经在内存中了）；
如何在块中存储记录，以便能够快速提取块中的记录；

变长记录通常会划分成两部分，初始部分存储定长的属性；之后的部分存储变长的属性；同时，在初始部分会存储变长属性的偏移量和长度，这样就能够基于快速定位该属性的起始点和结束点；

块中存储变长记录的一种方式：分槽的页结构；这种结构很特别，它拥有一个头部，然后记录在从尾部向头部方向存储的；

块的头部包含如下信息：

当前块中存储的记录数量；
块中空闲空间的地址（由于空闲空间位于头部和尾部中间，因此该地址实际是空闲空间的最右端地址，因为记录是从右往左存的）；
包含每条记录起始位置和长度的数组；

为了保证空闲空间居中，当有记录被删除时，其左侧的记录将向右移动，以确保将空闲空间腾挪到中间位置；然后还需要空间空间的指针，让其指向新的起始位置；另外因为发生移动，还需要更新头部记录条目位置和长度的数组；

由于块的大小只有 4~~8 KB，因此移动是在内存中完成的，最后只需将 4~~8 KB 的结果写入磁盘即可，因此其代价是可以接受的；

对于超过一个块的大属性，通常是将其单独存储，然后使用指针指向它即可，这样可以简化块的管理；

文件中记录的组织

几种在文件中组织记录的方法：

堆文件组织：记录没有顺序，可存放在文件中的任意位置；
顺序文件组织：按“搜索码”的值的顺序进行存放；
散列文件组织：基于记录某个属性的值，计算散列值，按散列值存放；

通常每个关系使用一个文件单独进行存储，但还存在一种特殊情况，将多个关系存储在同一个文件中，称为多表聚簇文件组织，multitable clustering file organization；使用场景：当需要频繁进行多表连接时，在一个块中即可提取到多个关系中的记录，有助于提升性能，避免读取多个块；

顺序文件组织

顺序文件：表中的记录，按搜索码的顺序进行存储；搜索码可以是表中任意一个属性或者多个属性，无须是主码或超码；

除非搜索码是自增的，否则如果能够任意取值的话，那么很可能记录的物理存储顺序，不完全是按顺序的。因为某个块和下个块可能已经存满，新插入的记录，只能存放到最后的溢出块中。此时物理上已经不连续了，只能通过修改指针链表，来指向新的位置；此时指针链表在逻辑上仍然是连续的，但物理位置已不连续；

随着时间推移，这种逻辑顺序与物理顺序的不一致，有可能会变得越来越多。当到达某个临界点时，原本预期的高效率顺序读取，将变得不再高效，变成了接近随机读取了，此时需要进行文件重组。但重组的代价是很大的，因此需要选择负载代的时候进行；

一种常见的应对方法是搜索码使用自增主键，同时配合逻辑删除，这样在插入时是按顺序的，同时也不会出现空闲空间；

多表聚簇文件组织

单表单文件的好处是可以利用操作系统的文件管理机制，简化数据库在管理文件方面的工作量。在嵌入式或便携式设备中，可以最大化利用资源；但在资源不紧张的场景中，一些大型数据库可考虑自己管理文件，自定义文件管理策略，以满足特定场景下的性能要求；

多表聚簇是有代价的，它在某种特定的连接查询下会效率很高，但在非特定查询的场景中，效率反而降低了。因此，选择这种结构时，需要小心谨慎的进行权衡；

数据字典存储

关系中存储着记录，因此还需要在另外的位置，存储与关系本身有关的一些信息，例如关系的模式等，这些信息即“元数据”；元数组一般存储在“数据字典”或“系统目录”的结构中。

这些元数据信息本身构成了一个小型的数据库，可使用单独的文件结构进行存储，但为简便起见，通常直接使用当前数据库的数据存储结构进行存储，实现复用，简化代码和复杂度；

元数据包括：

表的相关信息
- 表的名字；
- 每个表中属性的名字
- 属性的域和长度；
- 视图的名字和定义；
- 完整性约束；
授权相关信息
- 授权用户的名字
- 授权内容
- 认证密码等；
统计相关信息
- 表中的元组数量
- 表的存储方法（聚簇或非聚簇等）；
表的存储信息
- 顺序、堆、散列；
- 存储位置
- 表对应的文件名；
索引相关信息
- 索引的名称
- 索引的表的名称；
- 索引的属性
- 索引的类型

数据字典通常存储为非规范化的形式，以便实现快速读取；每次对表进行查询时，都需要先读取数据字典，因此它的读取是非常频繁且必须的；

数据库缓冲区

内存的访问速度比硬盘快很多，因此，出于性能考虑，将数据提前从硬盘加载到内存中，可以有效的提高访问速度；但内存容量是有限，而且成本也更高。如何利用有限的容量，达成性能与成本之间的平衡，是缓冲区管理策略要解决的问题；

缓冲区管理器

缓冲区管理器使用的一些技术：

替换策略：Least Recently Used，最近最少使用策略；
将块钉住：当块正在更新时，标记为钉住状态，以限制其写回硬盘；这样如果系统崩溃，那么硬盘上的数据虽然是未更新前的状态，但确保是可用的；
强制写出块：将块中的数据强制写回硬盘，即使缓冲区并没有资源紧张；

缓冲区替换策略

除了 LRU（最近最少使用策略）外，还有一种相反的策略，称为 MRU（最近最常使用）。该策略在 join 请求中，如果使用双层嵌套循环来实现数据访问，那么此时使用 MRU 策略来决定哪些块优先被替换将更加合理；

外层循环的块，用得最频繁，用完后，应该优先被替换，因为后续不再用得上了。而内层循环的块，反而需要先钉住，因为后续每一次外层循环，都将会用到；

优先常驻缓冲区的内容：

数据字典（表的元数据）；
索引

数据库收到并发请求是不可避免的，为了保证数据的一致性，有些请求需要进行排队；此时缓冲区管理器可以基于排队中的请求信息，适当的调整替换策略，以提高性能；

缓冲区管理需要配合崩溃恢复模块进行工作，而不是任意的将数据写回硬盘，以便崩溃恢复功能能够实现预期的目标；

第11章索引与散列

基本概念

两种常见的索引类型：

顺序索引：按照值的顺序进行排序；
散列索引：将值平均分布到多个散列桶中；

两种索引各有其使用场景，没有哪一种更好；取决于实际的数据类型；

索引的评价指标包括：

访问类型：例如是否支持查找某个范围的记录，常见的范围如时间段；
访问用时
插入用时：包括更新索引的时间；
删除用时，包括更新索引的时间；
空间开销，索引所占用的存储空间；

顺序索引

数据记录本身也可以按照某种顺序存储；如果包含记录的文件按照某个搜索码指定的顺序进行排序，则该索引码对应的索引称为聚集索引（主索引）；如果索引指定的记录顺序与文件存储的物理顺序不同，则称为非聚集索引（辅助索引）；

稠密索引和稀疏索引

索引项（索引记录）：由搜索码值 + 指向1个或者多个记录的指针构成；指向记录的指针包括硬盘块中的标识，以及记录在块中的偏移量；

两类顺序索引：

稠密索引：每个搜索码值都有一个索引项；一个索引项可能对应多条记录，此时记录将顺序存储在一起；以便到时可一起读出；
稀疏索引：只为部分搜索码值建立索引项；仅在记录按照搜索码指定的顺序进行存储时，才能够使用稀疏索引；

稀疏索引的好处是可以减少索引的空间开销，但如今主存越来越大的情况下，除非表中记录的数量非常多，例如10亿条纪录，不然貌似大多数情况下，没有必要使用稀疏索引；不过倒是可用于二级索引；

多级索引

由于索引本身是有序的，因此如果索引过大，无法一次性加载到内存中时，我们可以为该索引创建一个二级的稀疏索引。先搜索稀疏索引，得到稠密索引的块位置，然后将该块加载到内存中，再次进行搜索即可。

索引的更新

插入记录

稠密索引

如果搜索码值不在当前索引中，则在索引中合适的位置，插入该搜索码值对应的索引项；
如果搜索码值已经在索引中
- 如果索引项存储的是指向多条记录的指针，则在末尾添加一个指向新记录的指针；
- 如果索引项存储的是指向第一条记录的指针，则索引项不更新，仅仅将记录存储到其他记录之后即可；

稀疏索引

假设一条索引对应一个块：

如果创建了一个新的块，则将新块中的最小的那条搜索码值（貌似只有一条？）插入到索引中；
如果没有创建新的块
- 如果新插入的记录，含有块中的最小搜索码值，则更新该块的索引项
- 否则，不做变更

删除记录

稠密索引

如果被删除的记录，是搜索码关联的唯一的一条记录，则删除该索引项；
否则
- 如果索引项中存储指向多条记录的指针，则从索引项中删除指向被删除记录的指针；
- 如果索引项指向被删除记录的指针，则更新索引项，让其指向下一条记录；

稀疏索引

如果索引不包含被删除记录的搜索码，则索引不必更新；
否则
- 如果被删除的记录，是搜索码关联的唯一记录
  - 则用下一个搜索码的索引记录，替换当前的索引记录；但是如果下一个搜索码值已经有一个索引项，则直接删除当前的索引项；
- 否则被删除的记录，不是搜索码值的唯一的记录
  - 如果该搜索码值的索引记录，指向被删除的记录，则更新索引项，让其指向具有相同搜索码值的下一条记录；
  - 否则不用更新索引项；

辅助索引

对于聚集索引来说，数据记录的存储顺序，跟索引项的顺序是一致的，因此主索引来说，可以使用稀疏索引。但对于辅助索引来说，由于数据记录的存储顺序跟索引项的顺序不同，因此只能使用稠密索引；

通过在辅助索引和原始记录之间，添加一个指针层，可让辅助索引实现指向内容的连续化；这种连续化是通过额外的指针层来实现的；

辅助索引可以提高非主码的搜索性能，但代价是增加了更新索引的开销；

多码上的索引

搜索码可以支持多个属性，即复合搜索码；

B⁺ 树索引文件

随着数据记录不断的插入和删除，顺序索引的查找性能和顺序扫描性能会下降；当然，这种下降可以通过不断重组文件的弥补，但频繁的重组文件也是一项性能开销；为了应对这个问题，引入了 B+ 树索引结构；

B+ 树使用平衡结构，即根节点到叶子节点的路径长度相同，每个非叶子节点，可拥有 n/2 ~ n 个子节点（n 是一个固定的值，可根据场景进行初始设定）；

B+ 树的优缺点：

优点：减少文件重组的发生概率，保持查找性能稳定；
缺点：插件和删除时，会增加性能开销；会增加空间开销（节点的子节点数量不饱和）；

B⁺ 树的结构

B⁺ 树是一种多级索引，但跟顺序索引中的多级索引结构很不同；每个节点由搜索码值 K + 指针 P 构成；单个节点可以包含多个搜索码值，其典型结构如下：

此外假设单个结点包含 n - 1 个搜索码值，其中 P 代表指针，K 代表搜索码值；

在叶结点上面，指针的数量比搜索码的数量多一个；这多出来的一个指针，指向下一个叶节点的地址；因为叶节点内部的搜索码是顺序存放的，结合指向下一个叶节点的指针，就能顺序读取所有搜索码值的效果；

此处的叶结点示例，n 为 4，即单个叶结点包含 3 个搜索码值；搜索码是 name

注意：非叶结点的指针指向的是树中的结点，而叶结点的指针则是指向文件中的记录；从某种角度来说，非叶结点有点像是叶结点的多级（稀疏）索引；

节点的指针数量叫做节点的“扇出”；非叶子节点称为“内部节点”；对于内部节点中的每个搜索码值 K_i：

其左侧的指针，指向一棵子树，该子树中的所有搜索码值，都 <= K_i；
其右侧的指针，也指向一棵子树，该子树中的所有搜索码值，都 >= K_i，且 <= K_i+1 ；

B⁺ 树的查询

查找目标值 V 的过程：

步骤1：以根节点作为当前节点
步骤2：顺序遍历节点中的所有 K 值，找到最小的 K，满足 K >= V；
步骤3：如果 V >= K，那么将 K 右侧指针指向的节点设置为当前节点，回到步骤2；
步骤4：如果 V < K，那么将 K 左侧指针指向的节点设置为当前节点，回到步骤2；
步骤5：如果没有找到满足条件的 K，说明 V 大于所有 K 值；那么将 K 右侧指针指向的节点设置为当前节点，回到步骤2；
步骤6：重复步骤 2~5，直至到达叶节点；
步骤7：如果在叶节点中，没找到 K = V，说明 V 不存在，返回空值；
步骤8：如果找到 K = V，且存在其他 K > V，那么返回该叶结点；
步骤9：如果找到 K = V，且不存在其他 K > V，那么需要再搜索下一个相邻的叶节点，因为上面也可能存在 K = V；

节点的大小一般等于磁盘块的大小，即 4KB；如果搜索码的长度为 12 字节，指针的长度为 8 字节，总共 20 个字节；那么一个节点可以存放 4 * 1024 / 20 大约 200 个搜索码；假设某个文件有 100 万条记录，每个节点平均访问一半的搜索码，即 200 / 2 = 100，那么总共需要访问的节点数量（块数量）为 log₁₀₀ 1000000，等于 3，即只需访问 3 个节点（磁盘块），即可找到目标值，效率非常高；（由于根节点由于经常被访问，大概率在缓冲区中，因此实际只需访问 2 个节点即要）；

由于 B⁺ 树的节点可以存储多个指针，因此它的层级更少，显得更加矮胖，而不是像二叉树那样瘦高；

B⁺ 树的更新

由于节点的大小是有上下限的，因此当出现更新时，有可能因为插入导致节点中的搜索码数量过多，因此需要分裂；也可能因为删除，导致搜索码数量过少，从而需要合并；同时，在分裂或合并时，还需要兼顾 B+ 树的平衡；

如果删除的搜索码刚好在节点的中间，如果不涉及合并，那么此时余下的搜索码需要左移，占据多出来的空挡，保持存储的连续性；

插入

插入的过程：

查找到需要插入的叶子节点；
发现插入后空间不足，因此分裂成两个叶子结点，两个叶子节点各有一半的搜索码；
将两个叶结点中的最小搜索码，插入父结点（非叶节点）；
如果父结点空间充足，可直接插入；如果父结点空间不足，则父结点也需要分裂；
重复第3~4步（最坏的情况下，有可能追溯至根节点，最后导致整棵树的高度增加）；

由于非叶节点存储的是子节点的最小搜索码，因此分裂导致需要更新非叶节点时，有些不同。

插入后的样子如下，内部父结点也分裂了（当内部节点分裂时，它还会影响到该内部结点的父结点）；

对于内部节点（非叶子节点），搜索码的右则指针指向的子结点，以该内部节点的搜索码值为最小搜索码值；左侧的指针指向的子，以该内部节点的搜索码值为最大搜索码值；

非页结点的分裂，涉及两部分内容；一部分是指针的分裂，一部分是搜索码的分裂；指针分裂的处理跟叶子节点差不多，毕竟它是有顺序要求的；但搜索码分裂有所不同，因为它是用来判断方向的；因此需要在上一级节点中，添加一个新的搜索码和指针，以指向因分裂而新增的内部节点；此时会将分裂后左侧节点的最大搜索码，上提到祖父节点中；

以上貌似即是树的重新平衡

删除

涉及的过程：

删除后，原叶节点的搜索码数量低于最小值，因此需要和左侧的兄弟节点进行合并；
合并后，需要更新原父节点的指针；由于此时父节点仅包含被删除的搜索码，因此父节点也被清空了；
清空后的父节点，也需要跟其左侧的兄弟节点合并。但是兄弟节点已经满了，所以合并后只能选择重新分配指针，以便树保持平衡；
分配后，左侧内部节点包含三个指针，右侧内部节点，包含两个指针；二者通过中间值的搜索码，在祖父节点关联起来；

对于叶子节点，当指针数量少于 (n - 1) / 2 时，需要进行合并；对于内部节点，当指针数量少于 n / 2 时，需要进行合并；

从以上结果中，再删除 Singh 和 Wu：

从以上结果中，再删除 Gold：

某个搜索码在叶子节点被删除后，有可能该搜索码仍然会存在于父节点中；例如本例中的 Gold 搜索码；

不唯一的搜索码

定义：多条记录，包含相同的搜索码；或者说，一个搜索码，对应着多条记录；

当搜索码不唯一时，删除记录时，有可能涉及遍历多个叶节点；

由于叶节点是连续的，除非相同的值太多，按理说也还好;

解决办法之一，是创建复合索引，让搜索码变得唯一；另外一种方法是使用桶来存储重复的记录，这样在 B+ 树上的搜索码值仍然是唯一的；

不过桶也会带来额外的问题，即桶存放在哪里；有两种办法：

存在叶结点上；
- 优点：无额外的 I/O 操作；
- 缺点：B+ 结构变得复杂，需要处理桶的变长，以及其尺寸大于叶结点空间的场景；
存在单独的块中；
- 优点：B+ 结构不变；
- 缺点：需要额外的 I/O 操作读入块；

B+ 树更新的复杂性

B+ 在插入和删除时，其操作是相对复杂的。但是优点是在内存中操作即可，I/O 成本低；

在最坏的情况下，最大成本为 log_n/2 (N) 次操作，n 为节点的尺寸，N 为表中的记录数量；

当 B+ 树的节点尺寸设置得较大时，例如 n = 100，那么 B+ 树的扇出很高，树的高度很小；大部分非叶节点因频繁被使用，大概率位于缓冲区中。因此 I/O 操作通常只涉及叶子节点的块；同时因插入或删除发生分裂的几率也很低，大概只比 1 / n 大一点点；

因为 B+ 树的性能非常不错，所以它被很多数据库实现广泛使用；

B⁺ 树的扩展和变种

B+ 树文件组织

B+ 结构树除了可用于存储索引，也可用于组织表文件中的记录，此时 B+ 树的叶子节点存储的不再是指向记录的指针和搜索码，而是真正的原始记录；

由于记录的长度通常比指针的长度大得多，因此同样大小的块（叶节点），能够存储记录数量，要远少于指针数量；尽管如此，叶节点仍然需要满足半满的条件，否则需要进行合并；

由于记录的尺寸较大，节点能够存储的记录数量较少。因此在插入或删除而触发合并或分裂后，可能造成节点的空间使用率较低。处理该问题的一种办法是优先从相邻的兄弟节点借入（删除时）或借出（插入时）记录，以便让每个节点中的存储空间存储尽可能多的记录，大约 2 / 3 满，而不是 1 / 2 满；

辅助索引和记录重定位

当表文件使用 B+ 树组织时，节点的分裂或合并，将会导致记录物理存储位置的变化，同时辅助索引也将随之更新指针所指向的记录地址；考虑到一个节点（块）中的记录可能有几十或几百条，其涉及的辅助索引项可能非常多，有可能需要几十或几百次 I/O 操作来更新辅助索引；应对以上问题的一种办法是辅助索引中，不存储指向记录的指针，而是存储记录主搜引的搜索码，这样就不需要变动了；当然，代价就是查找记录时，需要查询两个索引文件；

字符串上的索引

字符串字段通常是变长的，因此给字段创建的索引，其搜索码也面临变长的问题。如果搜索码过长，将会导致节点的搜索码数量并不多，但却已经满了，导致必须分裂，从而增加了 B+ 树的高度；

应对以上问题的一种办法是“前缀压缩”，即搜索码只存储能够区分两个相邻子节点的前缀即可，例如 Silberschatz，为了区分 Silas 和 Silver 两个搜索码，只需存储前缀 Silb 就够了；

B*树索引的批量加载

发现对于大表，如假设有一亿条记录，其首次创建索引的开销还挺大的。因为创建索引需要扫描全表，假设磁盘的读取速度是 50MB/秒，那么可能需要 200 秒来读取整个关系表；

考虑到对大表创建索引的速度较慢，有一种办法是使用批量加载；即先创建一个由索引项（搜索码+指针）组成的临时文件，然后排序文件，最后将该文件插入到索引中即可；

此处的排序很重要，因为它让后续的叶节点写入和磁盘写入变得很高效，因为都是顺序写入；

如果 B+ 树索引一开始是空的，那么可以从底向上构建它，这样效率更高；如果开始是非空的，则只能自上而下构建了（如果已存在的索引内容不多，那么可以考虑先将旧索引删除，之后自底向上全新构建新索引更快）

B树索引文件

B 树和 B+ 的最大区别在于，搜索码在 B 树的所有节点上是唯一的，而 B+ 则可能存储多份；

好处：因为搜索码无冗余，那么单个节点能够存储更多的搜索码，空间利用更好；但对于大索引该优点不明显；
缺点：
- 非叶节点上，需要有额外的指针，来存储非叶节点上的搜索码指向的记录或者桶；即非叶节点的每个搜索码，对应着两个指针，一个指针子节点，一个指针自己所映射的记录；
- 删除的场景更复杂一些，因此搜索码唯一，因此需要从子节点中挑选合适的搜索码，来代替被删除项；

总体来说，B 树的优点并不明显，因此大部分数据库实现的索引都使用 B+ 树为主；只是由于某些原因，都通俗的说是使用 B 树，但实际使用的是 B+ 树；

闪存

对于随机访问，磁盘的平均速度是毫秒级的，而闪存则可以做到微秒级；闪存的缺点是不允许就地更新单条记录所在的存储块，而是需要清除整个闪存块，即删除块中的全部旧数据，然后重新写入新数据，大概需要 1 毫秒；

多码访问

使用多个单码索引

如果某个查询包含两个条件，例如

1
2
3

select ID
from instructor
where dept_name = 'Finance' and salary = 80000;

此时如果 dept_name 和 salary 都已经建立索引的话，那么理论上两个索引都可以用上。既先利用 dept_name 的索引，找到符合条件的指针，然后再利用 salary 的索引，找到金额为 80000 的指针，然后计算二者的交集；

据说位图索引结构，在某些情况下，有助于提升以上查询的性能；

多码索引

可使用复合搜索码（dept_name，salary）提升以上查询的效率，此时搜索码由 dept_name 和 salary 连接而成；

-- 以下两个查询，复合搜索码的顺序索引和 B+ 索引，都能很好的工作
select ID
from instructor
where dept_name = 'Finance' and salary = 80000;

select ID
from instructor
where dept_name = 'Finance' and salary < 80000;

-- 以下查询，复合搜索码的顺序索引也能很好的工作
select ID
from instructor
where dept_name = 'Finance';

-- 以下查询，由于两个条件都是计算范围，使用复合搜索码的顺序索引，仍然可能涉及大量的 I/O 操作
-- 因为记录可能存储在多个块中
select ID
from instructor
where dept_name < 'Finance' and salary < 80000;

覆盖索引

覆盖索引（covering index，或者叫 index covering 更合理）：在索引中额外存储一些属性的值，对于想要得到某个索引对应的属性值时，将非常高效，因为它无须访问表，直接从索引中就查到结果了；

假设有一张 instructor 表，包含 ID，name，salary 三个属性；有个查询需求，是查找 name = ‘’张三’’ 的工资金额；通常情况下，需要基于 name 的索引，找到记录指针；然后从磁盘中提取块，读出记录，返回 salary 金额；但是如果在索引中，已经额外存了 salary 金额，那么可以直接返回金额，而无须读取记录，非常省事；

静态散列

散列（也叫哈希）本质上是建立一种映射关系，建立 A 到 B 的映射关系；对于二分搜索，查找成本是 logN，对于散列，则可以实现 O(1)；虽然时间省了，但散列需要付出空间上的代价，因为部分桶可能比较空；理想的散列是尽量实现均匀的分布，不然查找代价将急剧上升，因为所有值都集中在一个桶里面了，查任意一个记录，相当于在查询所有记录，并没有让查询变快；

散列函数

散列函数的目标：

分布是均匀的；
分布是随机的；

一种常见的字符串散列函数实现是对加总各字符的整数值（可先乘个质数，如31），然后对桶的数量进行取模；以便让每个字符串平均分配到各个桶中；

桶溢出处理

假设记录总数为 n，单桶可存放 f 条记录，则初始桶的数量为：

1
2
3

(n / f) * (1 + d)

(* 其中 d 为冗余系数（也叫避让因子），一般设置为 0.2 ，即桶中大约有 20% 的冗余空间； *)

当桶出现溢出时，一种解决办法是将溢出的记录存放在溢出桶中：

使用溢出桶的方案也称为闭地址；还一种开地址的方案，它的桶数量是固定的，如果某个桶溢出了，就将记录存储在下一个有空闲空间的桶中；

开地址方案的好处是节省空间，缺点是删除的时候比较麻烦，可能涉及数据的迁移，因此适用于删除不频繁的场景，例如编译器构建符号表；对于删除频繁的场景，例如数据库，一般使用闭地址方案；

散列索引

散列索引：将搜索码及指针组织成散列结构；

如果一个表文件本身是按散列结构组织存放内容的话，就没必要再建立一个散列索引了；

动态散列

当文件会随着时间推移不断变大时，使用静态函数就不合适了，因为单个桶包含的记录越来越多，查询性能会不断下降，此时需要引入动态散列方案，以应对表文件的变化；一种常见的方案是使用可扩充散列；

数据结构

可扩充散列通过对桶进行分裂或者合并，来实现对表大小变化的动态适应；每次分裂或合并只涉及一个桶，因此重组的成本可控；

假设散列函数为 h，K 为搜索码，计算 h（K）可得到一个 32 位的哈希值；理论上，32 位的哈希值可映射 2^32 约 40 亿个桶，能够应对很大的数据库表；但一开始不用马上创建这么多，而是根据表文件大小，逐步扩充，不然太浪费空间了；

初期先以哈希值的前缀来做为桶数，例如 2 位前缀可映射 4 个桶；4 位前缀可映射 16 个桶，以此类推；

此处还需要一张桶地址表，用来记录每个桶对应的地址；随着桶数量变多，这张地址表会不断扩张，变得越来越大；假设散列前缀为 i 位，那么可按前缀值（ 2^i ），作为桶地址表上的偏移量来快速定位，例如前缀为 2 位，那么 10 表第2 个桶，11 表示第 3 个桶，以此类推；

问：为什么前缀 00，会指向同一个桶？然后没有第 0 个桶？

答：原来，为了最大化利用桶中的存储空间，当一个桶未存满时，可以将不同的表项（例如 00 和 01）指向同一个桶，此时 00 和 01 虽然有 2 位，可以指向两个桶，但是在桶未存满的情况，先只取前 1 位，即 0，让两个表项指向同一个桶；一直到桶中的记录存满了，再开始分裂；分裂后，将创新一个新桶。此时 00 指向老桶，01 指向新桶；然后桶的左上角的位数，由原来的 1 位，改成 2 位；然后原桶中的所有记录，重新按哈希值的前 2 位前缀，进行分配，部分存到旧桶中，部分存到新桶中；

查询和更新

插入新记录时，先计算该记录搜索码的哈希值，然后取哈希值的前缀，按该前缀查找桶地址表；根据表项的指针，找到相应的桶；

如果桶中有剩余空间，则将该记录放入桶中，结束；
如果桶满了，则需要分裂该桶；

分裂也存在两种情况。

如果桶的已使用位数 i = 前缀位数，那么意味着位数全部用完了，需要增加新位数，扩大桶地址表；
如果桶的已使用位置 i < 前缀位数，那么意味着位数未用完，存在多个桶地址表项批向同一个桶的情况；此时可创建新桶，让原指向同一个桶的表项，指向不一样的桶；例如原来 00 和 01 两个表项指桶 0，此时创建新的桶1，让 00 指向桶 0， 01 指向桶 1；然后按桶中各记录的哈希值前期，重新分配到这两个桶中；

如果有很多记录的搜索码值相同，那么无论分裂多少次，它们的前缀都相同，都会指向同一个桶，因此靠分裂是无法解决问题的，桶都是放不下。此时只能放多余的记录存放到单独的溢出桶中解决；

删除记录时，如果桶空了，那么桶也需要删除；原桶的地址表项 01，将指向剩下的桶 00，即两个表项 00 和 01 都指向一个旧桶；然后旧桶的左上角的 i 由原本的 2 位，修改为 1 位；

如果删除的记录非常多，有可能会涉及需要缩减前缀位数，让桶的总数目减半。这是一个开销非常大的操作，因为相当于所有桶中的记录都要重新分配一遍，很可怕。因此需要谨慎操作，除非记录真的删除非常多，可能才值得这么做；

静态散列与动态散列比较

可扩展散列的方案优点是空间利用率非常高，即非常节省空间；缺点是额外引入了一层桶地址表，带来了一些性能开销。但这个开销非常小，微乎其微，利大于弊；

除了可扩展散列，还有另外一种方案是使用线性散列。它没有桶地址表，而是使用了溢出桶；

顺序索引和散列比较

按顺序索引或 B+ 索引组织文件，文件最后的存储顺序是连续的；散列索引则是桶内连续；还有一种组织方式是堆文件，记录没有特定的顺序；

如果是查找单个值，那么散列的性能更好；但如果涉及查找范围，那么顺序索引的性能更好；

总体来说，一般优先选择使用顺序索引，除非在做表结构设计时，明确知道只会按值查询，不会按范围进行查询；

位图索引

位图即 bitmap，一个由二进制位构成的数组；位图结构也可以用来做为表的索引；

位图索引结构

位图索引是一种很巧妙的结构；当某个属性（例如性别 gender）的取值有限时，那么可以用一个二进制数组来代表各条记录的取值情况；在该二进制数组中，第 i 位的值，用来代表第 i 条记录的属性取值情况；

由于二进制位只有 0 和 1 两种情况，因此该位只能用来表示是否取某个映射的值，而无法代表所有值；此时需要为每个可能的取值都建立一个同等长度的二进制位数组；

多个条件的组合查询，在位图索引中，相当于求多个二进制位值的交集；如果该查询是为了统计个数，那么只需计算交集后的 1 的个数即可得出结义，甚至都不需要访问关系表；

使用场景示例：

查询有哪些女性的收入在 $10000 ~ $19999 之间；此时可取 gender 为 female 的位图，和收入为 L1、L2 两个位图的交集；
统计满足某个查询条件的记录个数：可直接从索引中得出结果，无需读取记录；
存在位图：用二进制位来表示某条记录是否存在，还是被删除了；常用于文件块的头部，表示当前块中有哪些位置是空闲的；

位图操作的高效实现

位的交集操作的一种高效实现是利用 CPU 的 and 指令，它以两个位图做为参数，返回一个新位置做为结果；

位图的几种操作：

and，取交集
or，取并集
not，补码，相当于翻转；

单纯的补码操作无法应对记录被删除的情况，此时需要跟存在位置再做一次 and 计算，确保记录存在；另外对于空值的场景，也需要和空值 null 的补码位图（存在位图）进行 and 操作；

统计位图中值为 1 的数目，传统方法是遍历每一位，挨个加一遍；还有一种方法是分段加。例如假设位图总共有 256 位，计算机是 64 位的，那么可以每 64 位作为一个单位，不断累加即可；这样一来，256 位只需加 4 次就完成了；

位图和 B+ 树

B+ 的叶子结点通常是存储记录的标识符，但某些情况下（某个值出现的很频繁）也可以使用位图，来减少空间的使用；

当某个属性值出现很频繁时，意味着有些搜索码中的记录数量特别多，此时两种方案的对比：

假设表中总共有 N 条记录，每个记录在叶子节点中的标识符为 64位；具有某个特定搜索码的记录数量为 10%；

使用列表：占用的位数 = N * 10% * 64 = 6.4 N 位
使用位图：总共只有 N 位，其中有 10% 的位值为 1，其他 90% 的位值为 0；

此处有个困惑的点，B+ 树的叶节点中，正常是要存放着记录的指针；当使用位置时，这个指针存到哪里去了？如果没有指针，只有记录的在顺序索引中的位置，要如何找到记录？

SQL中的索引定义

索引是有空间和时间代价的，建立合适的索引取决于表的查询和更新情况，没有统一的标准，因此索引的创建通常由程序员来决定和控制；

CREATE INDEX <index_name> ON <relation-name> (<attribute-list>)

# 示例
CREATE INDEX dept_name ON instructor (dept_name)

第12章查询处理

概述

查询的步骤：

语法解析
优化
执行

示例：

1
2
3

select salary
from instructor
where salary < 75000;

以上 SQL 查询语句可翻译成以下两种关系表达式之一：

因此，完成查询涉及几个动作：

确定要使用哪种关系表式；
给有关系表达式添加操作注释，例如使用哪个索引（称为“计算原语”）；
多条原语组成查询计划；
查询引擎执行查询计划；

事实上，转成关系代数表达式的步骤有些多余，很多数据库实现并没有这个步骤；而是将 SQL 转成语法树后，直接添加操作注释，进入查询优化阶段；

同一个查询，有多种实现方式；查询优化器基于过往经验和数据统计，大致计算不同查询计划的代价，然后选择最优的方案；

查询代价的度量

查询代价一般包括：

从磁盘上读取数据的时间（最主要的代价，读取操作分为搜索定位和传输两部分）；
调用 CPU 进行计算的时间；
分布式计算涉及的通信时间；

消耗的磁盘资源包括：

搜索磁盘的次数；
读取磁盘的块数；

优化器的目标是尽量降低查询带来的总资源消耗，而不是尽量缩短响应时间；

考虑到资源消耗的时间大致恒定，因此减少资源消耗，相当于缩短了响应时间；

选择运算

使用文件扫描和索引的选择

选择运算的几种方案：

A1 线性搜索：相当于全表扫描，效率最低，但通用性最好，可应用于任意场景；
A2 索引扫描（主索引，unique 搜索码等值比较）：查找满足等值条件的唯一记录；
A3 索引扫描（主索引，非 unique 搜索码等值比较）：查找满足条件的多条记录；
A4 索引扫描（辅助索引，等值比较）：对于辅助索引，满足条件的记录很可能分布于很多个存储块上，这将导致随机读取；如果满足条件的记录非常多的话，最终的性能有可能还不如全文件扫描；

不同搜索方式的代价比较：

对于 A4 和 A6 两种辅助索引来说，如果其叶节点存储的是主索引的搜索码，那么其代价还要进一步增加；

涉及比较的选择

A5 （主索引，比较），对于特定值 v

查找 A >= v 时，只需先定位到 >= v 的第一条记录，之后顺序扫描完整个文件即可；
查找 A <= v 时，无需使用索引，直接从头开始扫描文件，直到遇到 > v 的记录时即停止；

A6 （辅助索引，比较），情形同 A5 差不多，但是：

如果叶节点存的是记录的指针，则利用指针随机读取数据块；
如果叶节点存的是主搜索码，则还需要通过主搜索码得到指针，之后才是随机读取数据块；

对于 A6，如果条件命中的记录很多，那么其性能可能还不如全文顺序扫描；

复杂选择的实现

几种复杂的选择：

合取：多个简单条件的 and 组合；
析取：多个简单条件的 or 组合；
取反：不满足简单条件的集合；

A7（合取），只用一个索引查找所有满足单个查询条件的记录，然后遍历这些记录，筛选出满足余下条件的记录；

A8（合取），使用复合索引，根据索引类型，情形同 A2、A3 或者 A4；

A9（合取），每个索引查找出各自的记录集合，然后计算这些集合的交集；得到指针的集合后，可对其进行排序，这样多个指针可能只需读取一次磁盘块；

A10（析取），每个索引查找出各自的记录集合，然后计算这些集合的并集（同样可对结果进行排序）；但如果某个谓词未创建索引，那么只能进行线性扫描了；

排序运算

通过对某个属性创建索引，可以得到排序后的记录的指针；但是如果这个索引不是主索引，那么这些指针指向的记录随机分布在很多个磁盘块上面。当记录数量很多时，其读取的代价是很大的；

当内存足够大，能够容纳整个表时，那么一种方案是将整个表加载到内存中，然后对其进行快速排序；

外部排序归并算法

外排序：当表文件过大，无法全部加载到内存中时，需要使用外排序技术；外排序的原理是化整为零，即将整个文件分段，每次只排序其中一个段，最后合并所有段的结果；

假设内存缓冲区能够容纳 M 个硬盘块，文件总共分成 N 段，外排序步骤如下：

每次从磁盘读 M 个块到内存中，对其进行排序；将排序结果写入文件 R_i 中；
对归并段进行合并；取每个块的最小值，进行排序，得到所有块的最小值，写入到最终结果的内存块中（积累足够数量后，就写入磁盘中）；

如果表非常大，即使已经分成 N 段，N 也超过了内存能够容纳的最大磁盘块数量 M，那么需要分成多趟处理；相当于拆分成多级进行处理；

外部排序归并的代价分析

假设某个表有 b 个磁盘块，内存最大可容纳 M 个磁盘块；

排序的磁盘传输代价 T 计算如下：
$$
T = b * (2 * \log_m (b/m) + 1)
$$
磁盘的搜索代价如下：
$$
S = 2 * (b / M) + (b_r / b_b) * T
$$

连接运算

计算等值连接，student join takes

假设：

student 表有 5000 条记录；n_student = 5000；
student 表有 100 个磁盘块；b_student = 100；
takes 表有 10000 条记录；n_takes = 10000；
takes 表有 400 个磁盘块；b_takes = 400；

嵌套循环连接

嵌套循环连接（nested loop join）由两个嵌套的 for 循环组成；

如果内存足够大，能够同时容纳两张表，那么：

磁盘搜索次数 = 2，每个表各一次，搜索到了后，将所有的块加载到内存中；
磁盘传输次数 = b_student + b_takes，即将两个表的所有磁盘块都传输到内存中即可；

如果内层关系的磁盘块能够先全部加载到内存中的话，那就跟内存足够大的场景相同了，传输次数 = b_student + b_takes；磁盘的搜索次数也是 2 次；

如果内存非常有限，无法同时加载任意一张表的全部记录，那么在最坏的情况下，即每个表只能各分配一个块，磁盘传输次数 = 外层块数 + 外层记录数 * 内层块数；假设传输时间为 0.1 毫秒，搜索时间为 4 毫秒

student 外，takes 内：
- 传输次数 = 100 + 5000 * 400 = 2 百万；约 80 万毫秒
- 搜索次数 = 100 + 5000 = 5100；约 2 万毫秒
- 总计：82 万毫秒
takes 外，student 内：
- 传输次数：400 + 10000 * 100 = 1 百万；约 10 万毫秒
- 搜索次数：400 + 10000 = 10400；约 4 万毫秒；
- 总计：14 万毫秒

经过比较，发现在最坏的情况下，将大表做为外层，小表做为内层的性能更好；因为内层要重复查询多次，所以越小越好；

块嵌套循环连接

以记录为单位进行循环，意味着外层的每个记录，都要遍历一次内层的所有块。因此，如果能够以块为单位，那么将可以大大减少内层块的遍历次数；

假设 student 外，takes 内，传输时间为 0.1 毫秒，搜索时间为 4 毫秒

传输次数：100 * 400 + 100 = 40100 次，约 4 千毫秒
搜索次数：100 + 100 = 200 次，约 800 毫秒；
合计：4800 毫秒；

其他改进：

如果连接属性在内层关系上是唯一的，那么找到记录后，即可略过余下的记录，跳过本轮遍历；
如果内存缓冲区不止可以放两个块，那么多出来的块，应尽量多放外层关系的块，这样可显著减少内层的遍历次数；
若内层循环在连接属性上已创建索引，那么可利用索引代替全表扫描；

索引嵌套循环连接

考虑到内层关系将会被遍历多次，那么在做全表扫描前，先给内层关系创建一个临时索引也未尝不可，这样可以遍历外层关系的过程中，就可以不断复用该索引了；

如果两个表的连接属性都有建立索引，那么将小表放在外层，大表放在内层效果更好。因为内层的查找代价是 logN，外层是 N，因此将大表放在内层性能更佳；

归并连接

归并连接算法（merge join）：排序-归并-连接，用于计算自然连接和等值连接，据说原理跟排序算法中的归并阶段很类似；

归并算法

先将两个关系在连接属性上排序，然后比对排序后的两个关系，值相同，就加入结果集中；值不同，则依次向后遍历；

代价分析

如果关系的连接属性刚好已经排序，那么将很省事；如果没有排序，则需要增加考虑排序的代价；如果缓冲区较大，能够容纳较多的磁盘块，那么排序的代价并不高；

混合归并连接

当连接属性在其中一个关系上是主索引，另外一个关系是辅助索引时，如果直接按索引的顺序读取磁盘块，其代价较大，因为对应的磁盘块是分散的，而不是连接的；

此时可将已排序的关系，先与辅助索引进行归并；然后读磁盘前，先对其进行排序，这样最后读磁盘时就是有序的了；

散列连接

基本思想

先将关系中的每个元组按散列函数分配到各个桶里，然后对比两个关系相同编号的桶中的元组，检查其连接属性的值是否相同；

在对关系 S 桶中的元组进行比较前，可先为其创建临时索引，这样关系 R 中的元组在进行比较时，可利用索引的优势，提升速度；

递归划分

当内存不足时，没办法一次划分关系中的所有元组时，可拆分成多趟进行划分，即递归划分；大致可以这么理解，例如先分成 10 组；然后每组内部，再分成 10 组，这样总共就 10 * 10 = 100 组了；随着递归的进行，每组的元组数量会分得越来越小，直到该数量能够加载到内存中为止；

溢出处理

当很多的记录拥有相同的连接属性值时，某些划分后的桶中，其记录的数量会高于平均值；同时也有一些桶中的记录数量少于平均值；导致整个划分结果不均匀，出现偏斜（skewed）；如果偏斜的过于厉害，将会导致某些桶中的记录数量太少，产生溢出；

溢出有两种处理办法：

溢出分解：对发生溢出的桶，使用新的散列函数，进行二次分解（划分）；另外一个表相同编号的桶都需要二次分解，以便对应得上；
溢出避免：尽量选择一个不会造成溢出的散列函数；

如果有大量的记录其连接属性值相同，那么溢出分解或溢出避免两种方法都无法产生效果。如果是这种情况，则不应再使用散列连接方法，而是应使用其他连接方法，如块嵌套循环；

散列连接的代价

假设 b 表示每个表的总磁盘块数量，有 r 和 s 两个表；

传输次数：

生成散列桶阶段：需要全表读取并写回，两个表需要 2 * （b_r + b_s）次传输；
构造和探查阶段：每个桶需要读入一次，两个表需要（b_r + b_s）次传输；
合计：3 * （b_r + b_s）次传输

搜索次数，假设内存中可容纳 b_b 个块；

生成散列桶阶段：需要 2 * （b_r + b_s）/ b_b 次搜索；
构建和探查阶段：每个桶搜索一次，需 2 * n_h 搜索；
合计：2 * （b_r + b_s）/ b_b + 2 * n_h 次搜索

如果发生递归划分，假设内容只能容纳 M 个块；

传输次数：两个表需要 2 * （b_r + b_s）* log_M（b_s）+ （b_r + b_s）次传输；
搜索次数：2 * （b_r + b_s）/ b_b * log_M（b_s）次搜索；

示例：student join takes

student 表有 100 个磁盘块；b_student = 100；
takes 表有 400 个磁盘块；b_takes = 400；
内存可容纳 20 个块
- student 表划分成 5 个桶，每个桶 20 个块；
- takes 表划分成 5 个桶，每个桶 80 个块；

计算结果：假设传输时间为 0.1 毫秒，搜索时间为 4 毫秒

传输次数：3 * （100 + 400）= 1500 次，约 150 毫秒；
搜索次数：2 *（100 + 400）/ 3 = 333 次，约 1300 毫秒；

貌似在没有溢出的情况下，散列连接的速度好像比嵌套循环要快一些；

如果内存足够大，那么散列连接的代价是 b_r + b_s 传输和 2 次搜索，跟嵌套连接一样；

混合散列连接

如果内存相对宽松，但不足以加载整个表时，可考虑使用混合散列连接（hybrid hash join）；这是一种很有趣的做法，实现思路如下：

将多余的内存块做为散列构造表的第一个桶 s₀ 的缓冲区，用来存放记录并建立索引。这样做的好处是该桶在使用时不用从磁盘再次读入；
散列输入表 r 中的记录划分到第一个 r₀ 桶后，无须写入磁盘，而是直接利用 s₀ 的索引进行匹配查找，得到连接后的元组；

混合散列索引在内存较充足的情况，成本大约降低 20%；

复杂连接

嵌套循环和块嵌套循环可用于任意的复杂连接形式，合并连接和散列连接只能处理简单的连接，例如自然连接或者等值连接。但是可以通过计算多个简单连接结果的并集或交集，来实现复杂形式的连接；

其他运算

去除重复

有两种去除重复的方法：

排序
散列

不管哪种方法，去除重复都需读取每一条记录，所以代价还是不小的；

投影

如果投影属性包含主码，则结果不会存在重复；如果不包含主码，则还需要多一个去重的动作；

集合运算

集合运算包括计算并集、交集、差集，在计算前，需要先对集合进行排序，之后只需遍历每个元组并进行比较即可；

除了排序算法外，也可以使用散列算法进行集合运算；

外连接

外连接有几种形式：

左外连接和右外连接（二者互为镜像）：适用嵌套循环、归并、散列；
全外连接：只适用归并和散列，普通嵌套循环搞不定；

聚集

聚集前，需要先按聚集的属性进行排序，其计算代价跟去重差不多；聚集的动作可在循环或构造的过程中同步进行，不必等到构造结束后才开始，这样可以减少磁盘传输的代价，直接将结果放在内存中，无需写回磁盘；

表达式计算

关系运算的输入，除了是一个已经存在的表之外，也有可能是另外一个表达式的计算结果。一种简单的办法是将每个表达式的计算结果进行“物化”，即保存到一个临时表中，最后对这些临时表进行计算；还有一种方法是使用流水线，将每个表达式的计算结果传入下一个表达式，而不是等全部算完再传入；

物化

物化：为计算的中间结果创建临时表（有可能只是保存在内存中，不写回磁盘）；

物化的代价在于如果内存不够大时，将结果写入磁盘需要消耗资源。此时可设置两个缓冲区（双缓冲技术），一个用于 CPU 提取记录进行计算，一个用于将结果写入磁盘。这样两个动作可以并行，提高性能；

流水线

使用流水线有两个好处：

减少临时表的创建；
可提前返回部分计算结果，减少等待；

流水线的实现

流水线有两种驱动方式：

需求驱动：向流水线上游环节，发送需要元组的请求；该环节收到请求后，开始计算结果并返回；
生产驱动：直接生产，不等待需求；每个操作有点类似一个单独的线程（这种方式貌似不错，但可能需一个中间队列来缓存结果，平衡不同操作之间的速度差异）；

需求驱动的一种实现方式是使用迭代器，由诸如 open(), next(), close() 等方法组成；同时还要维护一个中间状态，以记录当前已经迭代到哪条记录了；

生产驱动在不同的操作之间使用缓冲区来保存中间结果；当缓冲区满了后，就等待；直到缓冲区被消费后，出现空闲空间再进行生产。如果有多核 CPU，那么可以由不同的处理器更好的实现并行；

需求驱动算法更容易实现，但生产驱动算法可以利用多核优势，提高性能；

流水线的执行算法

流水线不一定能够完全的实现，因为某些计算步骤是阻塞的，需要等待该步骤处理完所有记录的结果，才能进入下一步，例如排序运算；

当两个表都已经在连接属性上存在排序时，那么流水线是很容易实现的。但如果没有排序，则可以考虑使用双流水线散列连接技术；它的核心思想是先通过散列，将一个大表拆分成很多个小表（放在桶里面），然后不同的桶，可以实现并行运算，互不干扰，实现性能提升；当然需要多一个合并结果的动作；

使用场景：双流水线散列连接常用于数仓等数据分析的场景；

第13章查询优化

优化有两个切入点：

寻找更高效的表达式进行替代；
相同表达式，寻找合适的查询策略（运算所用算法）；

概述

查询示例：找出音乐系所有教师的名字，以及他们所教授的课程名称；

执行计划示例：

生成执行计划的三个步骤：

根据给定表达式，寻找更好的等价表达式；
给表达式添加注释，生成多个不同的执行计划；
计算各个执行计划的性能代价，从中选择最优的一个；

关系表达式的转换

等价规则

等价规则：如果两个表达式产生的结果集一样（顺序可以不同），则称它们是相互等价的；

示例：

以下是一些等价转换的例子：

两个选择条件可替换为级联；

选择运算的条件顺序可交换：

多个投影只取最后一个即可：

按条件连接满足交换律

有选择条件的笛卡尔积，等同于条件连接

有二次选择的条件连接，等同于两个条件叠加的连接

转换的例子

背景：

目标：查找音乐系在 2009 年教授课程的教师名称，以及课程名称

初始表达式与最终表达式之间的对比：

连接的次序

连接的次序很重要，因为不同的次序，产生的中间结果集的大小不同，这也意味着付出的性能代价不同；

等价表达式的枚举

根据等价规则，枚举所有与给定表达式等价的其他表达式形式；但由于规则较多，这个枚举会有比较大的性能开销。一般使用两种改进方法：

允许子表达式被引用，避免重复生成；
根据成本高低，直接排除成本高的替换，减少可能性；

表达式结果集大小估计

目录信息

运算代价的大小，跟输入的表大小有直接关系。因为在评估计算代价前，可利用表的一些目录统计信息，提前进行代价估计。虽然这些估计不一定完全准确，但通常都是八九不离十。

数据库中表的目录信息一般包括：

N，元组数组
B，占用的磁盘块数量
L，单个元组的字节数量
F，每个块可存储的元组数量；
V（A，r）：关系 r 中 A 属性的不重复个数；注：A 除了可以是单个属性，也可以是复合属性；

另外目录通常也包括索引相关的一些信息，例如 B+ 树的高度，叶子节点的页数等；

为了减少实时更新目录信息的开销，目录中的信息不定时才更新一次（例如等系统负载比较低时，进行随机抽样调查）。虽然这会造成一些统计误差，但通常可以忽略不计。

事实上目录里面存放的不止以上提到的那些信息，它还会存一些有助于性能优化的信息。例如某个属性的取值分布，取值可按区域进行划分，也可按等高的直方图进行划分。

选择运算结果集大小估计

假设 n 为表中的元组个数，V(A, r) 为关系 r 中 A 属性的不重复值的个数；判断某个值 a 在表中的出现次数，平均大约为 n / V；但考虑到每个值出现的概率不同，按以上公式直接计算，误差有时候会很大。

这个时候目录中的直方图统计信息就可以派上用场了。可利用 a 值所在区间的元组数量代替 n，同时用该区域中的不同属性值的个数代替 V，之后计算出来的结果要准确多了；

按范围进行计算的场景

可利用目录中的 min(A, r) 和 max(A, r) 进行估计。

如果目录中的统计信息跟实际信息出入比较大的话，很可能会导致优化器生成性能不佳的执行计划；

合取场景

合取：多个 and 条件的组合；假设每个条件的概率是 S_i，各条件相互独立，那么最终概率为：

析取场景

析取：多个 or 条件的组合；它有点像是 and 条件的取反

取反场景

取反的概率为总数 n 减去未取反前的出现概率；

连接运算结果集大小估计

笛卡尔积比较好计算，结果集为两个关系的乘积，磁盘块数量为二者之和；

对于条件连接，可换算成在笛卡尔积的状态下，做选择运算；

其他运算的结果集大小估计

投影：由于需要去重，因此等同于 V(A, r)；
聚集：貌似等同于 V(A, r)；
集合运算
- 并集：r + s
- 交集：r - s
- 差集：r
外连接：
- 左连接或右连接：普通连接 + 左/右
- 全连接：r + s

不同取值个数的估计

目标：运算结果集中，某个属性 A 满足指定条件的元组个数：

对于选择操作：

如果条件 θ 为 A 等于某个特定值的场景，则元组数量直接取 1 即可；

如果条件 θ 为 A 等于指定值的集合，则元组数量为该指定集合的成员个数；

如果条件 θ 为比较运算，则元组数量为比较运算的命中率乘以 V(A, r)；

如果是其他选择情况，假设 A 的取值分布跟选择条件无关的话，那么可粗略的取最小概率：

对于连接操作：

如果 A 中的所有属性都来自于 r

如果 A 中的所有属性都来自于 s

如果部分来自于 r，部分来自于 s

执行计划选择

同一个表达式有多种不同的实现算法，优化器的主要任务，是从中找出最优算法。此时需要基于统计信息，进行代价计算；

基于代价的优化器

对于多表连接的场景：

不同的选择顺序组合非常多，约为：

但是可以通过分而治之的方法来缩小搜索空间，即先寻找局部最佳，然后递归（动态规划）；

采用等价规则并基于代价的优化器

通过引入等价规则，能够生成更多的执行计划组合，然后计算每种计划的代价，找到最佳方案。

当组合过多时，计算量很大，因此需要一些方法，来减少潜在的计算量，这些方法包括：

使用引用，让多个子表达式副本实现复用，避免重复创建；
使用缓存，存储某个子表达式的最优计划，避免重复计算；
使用剪枝，删除那些高代价的计划，减少计算量；

启发式优化

由于计算所有潜在执行计划的代价很大，因此基于经验，引入了一些启发式规则（感觉更像是经验法则），来减少计划代价；

例如：

尽早执行选择运算；

尽量执行选择运算，通常都会降低运算代价，但也并不总是如此。例如连接运算时，其他某个关系的元组数量很少，另一个关系的元组数量很多，而选择条件是针对大关系的。并且用于连接的公共属性具有索引。在这种情况下，很可能先执行连接运算的代价更低。

尽早执行投影运算；
使用缓存：将已找到的最佳计划缓存起来，让后续的查询复用；
使用预算阈值：仅当计划的执行时间超过预算时，再考虑进一步优化；

嵌套子查询的优化

SQL 在概念上，将位于 where 子句中的子查询视为一个函数，该函数接受一个从外部查询提供的参数，然后返回一个值，或者一个集合；

select name
from instructor
where exists (
	select *
    from teaches
)

由于每个外层的元组，都需要调用函数检查是否满足条件，因此会产生很多磁盘随机 I/O，查询效率不是很高；因此，优化器会尽量将嵌套查询转化成连接的形式；

但是很多时候一些复杂的嵌套子查询，无法直接转化成连接的形式。此时只能先优化子查询本身，然后将其查询结果创建一个临时表，之后使用临时表与主查询进行连接。

考虑到优化器无法很好的应用嵌套子查询，因此出于性能考虑，应该尽量避免使用复杂的嵌套子查询；

物化视图

物化视图的好坏是可以让查询变快，因为它提前将需要查询的数据计算并存储了起来。但它也是有代价的，该代价即更新维护成本；

视图维护

视图有几种维护方法：

在代码中更新：缺点是容易遗漏；
使用触发器更新：每次都全量重新计算，代价也很大；
使用数据库内置的增量更新：维护代价最小；

大多数数据库软件默认使用实时增量更新，但有部分软件也支持延迟增量更新，即可以设置在低负载的时间段，例如晚上再进行更新；

增量的视图维护

有三种操作会触发视图的更新，分别是更新、删除、插入；其中更新可视为由删除+插入组成，因此只更新考虑插入和删除操作带来的差异变化即可。

连接操作

假设物化视图由连接进行定义，即 v = r ⨝ s，此时向 r 插入一个新元组 i；

当向 r 表插入一个新元组集 i 时，相当于 r^new = r^old ∪ i

v^new = r^new ⨝ s

v^new =（r^old ∪ i ）⨝ s

v^new =（r^old ⨝ s）∪ ( i ⨝ s)

v^new = v^old ∪ ( i ⨝ s)

即只需计算新元组 i 和 s 的连接，然后将结果添加到视图中即可；

当从 r 中删除一个元组集 d 时， v^new = v^old - ( d ⨝ s)

选择和投影操作

选择场景

假设视图为 v = σ_θ (r)

插入元组集 i， v^new = v^old ∪ σ_θ (i)

删除元组集 d， v^new = v^old - σ_θ (d)

投影场景

假设视图为 v = π_A(r)

考虑多个不同的元组，在投影视图中，有可能出现重复，因此不能直接简单的进行添加或删除。而是需要为相同的属性值维护一个计数器。

当插入时，如果计数已存在，则加1；如果不存在，则插入并初始化计数器为1；

当删除时，如果计数已存在，则减1；如果计数器减1后为零，则从视图中删除元组；

聚集操作

SQL 中的聚集操作主要有：count、sum、avg、max、min；

假设视图 v 在 r 关系上，以属性 A 进行分组，然后以属性 B 进行聚集；聚集操作与投影操作有些类似，也是维护一个属性计数器，插入时加1，删除时减1，然后根据结果进行视图更新；

其中的 avg 比较特殊，因为 avg = sum / count，因此它可以复用 sum 和 count 进行更新；

其他操作

交集

假设 v = r ∩ s

向 r 插入 i 时，检查 i 是否在 s 中，如果在，则播入 v；

从 r 删除 d 时，检查 d 是否在 v 中，如果在，则直接从 v 中删除；

外连接

外连接的操作与连接类似

向 r 插入 i 时，应检查 s 中与 i 相匹配的元组；

从 r 删除 d 时，也应检查 s 中与 d 相匹配的元组；

子表达式的处理

思路类似，可利用等价原则进行换算；

查询优化和物化视图

当存在物化视图时，查询优化器有可能可利用物化视图的便利，实现更好的优化效果；例如 v = r ⨝ s，那么优化器可考虑将 r ⨝ s ⨝ t 转化成计算 v ⨝ t；

另外还可以反向操作，例如对于计算 σ_A=10 (v)，v = r ⨝ s

因为有可能 A 在 v 上面没有索引，但在 r 上面有索引，那么可将表达式转换成 σ_A=10 (r) ⨝ s，利用 r 的索引，提升查询性能；

物化视图和索引选择

物化视图的更新维护，以及建立索引，是有代价的。至于付出的代价是否值得，与系统的实际工作荷载直接相关，因此应具体情况具体分析。一般来说，很多数据库软件都有提供历史记录的分析工具，方便数据库管理员基于过往数据，做出合理的决策。

高级话题

除了上述的一些优化方法外，还有一些其他高级的查询优化方法；

top-K 优化

有种常见的业务场景是对某些属性进行条件查询和排序，最后只返回前 K 的结果；如果这些属性有创建索引则还好，如果没有索引，则有两种优化方法：

方法一：使用能够产生有序结果的流水线计划；
方法二：预估满足 K 条件的 max 值，将其作为谓词进行查询，以缩小范围；如果查询结果不满足要求，再微调 max 值，进行二次查询；

连接极小化

当查询基于视图时，如果视图由连接构成，但是待查询的属性仅在其中一张表上面，并不在连接的另外一张表上面。此时可以绕过视图，直接取基表进行查询，即连接最小化，避免多余的连接操作，因为这些多余的连接操作并不会对最终结果造成任何影响。

更新的优化

按条件更新有可能会引发重复更新的问题（即万圣节问题），因为更新的过程中，会实时更新索引。在某些情况下，更新后的索引会影响后续的查询结果，导致再次更新，一不小心还会陷入无限循环。

因此优化器在进行此类操作时，需要先进行判断，确保该问题不会出现时，再进行更新操作。如果问题会存在，则需要拆分执行计划，先查询出待更新的所有元组，之后再进行批量更新，而不是单条更新。

当然，进行批量更新时，可以先对数据进行排序，这样可以提升更新性能，减少磁盘的随机 I/O 操作次数。

多查询优化和共享式扫描

多查询优化：在批量处理多个查询，或者处理某个复杂的查询时，其中可能会出现多个相同的子表达式。此时将缓存该子表达式的查询结果，实现结果复用，避免重复查询。

共享式扫描：扫描到某个可复用的结果时，将其传递给多个执行计划，实现扫描结果的复用。

参数化查询优化

执行计划的生成，本身也是需要消耗时间的。因此，如果某类查询如果频繁出现，彼此间的区别仅仅是某个属性的取值不同，即查询参数不同。那么可以提前为该类查询生成执行计划。后续根据不同的属性，直接选用其中提前计划好的最优计划即可。这些可以省去筛选最优计划的时间。

第14章事务

事务概念

定义：由多个操作组成，构成一个单一的逻辑执行单元。

事务的几个特性：

原子性：事务中包含的多个动作，要么全部执行完成，要么全部没有执行；
持久性：事务执行成功后，其结果应该保存到数据库中；
隔离性：多个事务的并发执行，不会相互影响；

事务机制的好处：让开发人员可专注单个事务内部的逻辑处理，而无须关心并发和容错问题；

问：保证“一致性”是程序员的职责？

答：一致性是指事务做为原子，在执行之前，如果数据库处于一致性的状态，那么在事务执行后，数据库也应仍然处于一致性的状态；举个例子，假设存在 A 和 B 两个账户，当从 A 转账 50 元到 B 账户后，两个账户的合计金额，在转账前和转账后，应该保持一致性。

一个简单的事务模型

从账户 A 转 50 元到账户 B；

如果执行操作的过程中出现异常，可通过日志中记录的旧值，将数据库恢复到原始状态。

保持持久性的两种办法：

实时将更新数据写入磁盘；
将更新信息写入磁盘，以便于后续构造更新数据；

存储结构

此处在传统的易失性和非易失性存储器之外，引入了一个新的概念，叫“稳定性存储器“。它可以保证存储其上的信息，永远不会丢失（非极端条件）

很神奇，好奇它是如何实现的。

事务原子性和持久性

“已中止”的事务特指事务提交失败并实现了回滚。当事务处于“已提交”或者“已中止”的状态，此时事务“已经结束”。

当事务进入中止状态，系统有两种处理方案：

重启事务：常用于由事务外部引起的异常，例如死机、停电等
杀死事务；常用于由事务内部逻辑错误引发的异常；例如输入有误、所需数据无法在数据库中找到等；

事务隔离性

并发执行有两个好处：

提高吞吐量；
减少等待时间；

操作系统默认支持并发执行，但是这种并发无法保证数据的一致性。因此，数据库软件不能依赖于操作系统的并发机机制，而是需要自己实现并发控制和调度，通过一定的串行化，来保证一致性。

可串行化

数据库操作主要由读和写两种操作构成。两个并发事务下，两种操作有四种组合：

I = read(Q)，J = read(Q)
I = read(Q)，J = write(Q)
I = write(Q)，J = read(Q)
I = write(Q)，J = write(Q)

对于相同的数据项 Q，仅第一种情况，I 和 J 的顺序是不重要的，其他三种情况下，结果都是顺序有关的，即相互冲突的。

如果调度方案 S，在经过一系列的非冲突指令交换，转换成新调度方案 S^` 时，这两个调度方案称为冲突等价（conflict equivalent）；

如果某个调度方案 S，与某个串行调度是冲突等价的，那么称调度方案 S 为冲突可串行化的调度。

判断某个调度是否是冲突可串行化，有一种方法是绘制有向图（也称为优先图）

图的顶点表示一个事务，图的边由以下三种读写顺序构成：

T_j 执行 read(Q) 前， T_i 执行 write(Q)；
T_j 执行 write(Q) 前， T_i 执行 read(Q)；
T_j 执行 write(Q) 前， T_i 执行 write(Q)；

如果有向图存在环，则说明该调度是非冲突串行化；如果没有环，则是冲突可串行化。但即使两个调度不是冲突等价的，它们也有可能产生相同的结果。只是要辨别它们，计算的代价比较大，没有太大的必要。

除了优先图，还有其他检查事务是否可串行化的更好方法。

事务隔离性和原子性

当多个事务并发执行时，它们之间可能存在依赖关系。当被依赖的事务失败中止时，存在依赖的其他事务也需要中止回退。为了降低复杂性，有必要对调度策略进行一定的限制。

可恢复调度

如果事务 T_j 读取了前置事务 T_i 定入的数据，那么 T_j 不能早于 T_i 进行提交；不然一旦 T_i 出现故障， T_j 将不无法恢复。

无级联调度

当存在较长的依赖链条，会导致产生级联回退，让事务变得复杂棘手。因此，为避免出现这种情况，采取无级联的调度策略，即如果事务 T_j 需要读取前置事务 T_i 定入的数据，则 T_i 应该在 T_j 读之前进行提交。

事务隔离性级别

为了实现读写性能和保证数据一致性之间的平衡，有以下四种事务隔离性策略：

可串行化：保证可串行化的调度（强一致性，隔离级别最高）；
可重复读：只允许读已提交的数据；如果多次读同一数据，期间其他事务不得更新该数据（即重复读期间不可串行）；
已提交读：只允许读已提交的数据；如果多次读同一数据，期间其他事务可更新该数据（即重复读期间可串行）；此时如果重复读，会读到与上一次不一样的数据；
未提交读：允许读未提交的数据（弱一致性，隔离级别最低）；

以上四个隔离级别都不允许“脏写”，即如果某个数据项已经执行写入操作，但尚未提交，或者出现中止，那么该数据项不可以再次执行写入操作。

大多数数据库软件默认的事务隔离级别是“已提交读”；但用户可通过 SQL 指令显式指定当前事务要使用的隔离级别，例如 set transaction isolation level serializable；修改隔离级别的 SQL 指令需要做为事务的第一条指令，同时还需要关闭单条 SQL 语句的自动提交功能。

隔离性级别的实现

锁

两阶段封锁协议：

阶段一：只获得锁，不释放锁；
阶段二：只释放锁，不获得锁；

两种类型的锁：

共享锁：用于读取数据，多个事务可以获得相同数据项的共享锁；
排他锁：用于写入数据，仅限单个事务同时获得共享锁和排外锁时，才允许写入数据；

时间截

首先在创建事务时，为事务先分配一个时间截。然后在数据项中额外记录两个时间截：

读时间截：最近一次读取数据的事务时间截；
写时间截：最近一次定入数据的事务时间截；

事务按时间截顺序访问数据：

如果事务的时间截大于数据项上的时间截，允许访问
如果事务的时间截小于数据项上的时间截，不允许访问，并重新给事务分配新的时间截；

多版本和快照隔离

维护多个版本的数据项，其中一种常用的技术为“快照隔离”；每个事务获得一份自己私有的数据版本，然后在自己的版本中进行数据操作。在提交时，检查是否有其他事务更新了数据，如果没有则允许提交；如果有，则中止提交。

快照隔离的优点是性能最好，因为一个事务无须等待另外一个事务。但缺点是一个事务无法查看另外一个事务的更新，可能在某些极端情况下，会造成数据状态的不一致性。

事务的 SQL 语句表示

在前面章节的简单模型中，有一个具体的数据项，用于判断事务间的冲突是否存在。但在实际的 SQL 语句中，数据项常常不是具体的，而是由谓词条件进行筛选决定的，因此并不容易非常直观的看出哪些数据项会被影响，并可能存在冲突。有一种解决办法是使用“谓词锁”，即判断谓词是否存在冲突。但这种方案较为复杂，计算代价比较大，很少使用。

第15章并发控制

每种并发管理机制都有其优缺点，没有完美的方案，在实际使用中，最常用的两种机制是两阶段锁和快照隔离。

基于锁的协议

锁

锁的两种类型：

共享锁：可读不可写；
排他锁：可读可写；

事务在对数据项进行操作之前，不管是读还是写，需要先向并发控制器申请锁。在并发控制器给事务授予锁之后，事务才能进行相关的操作。

并发控制器在收到申请后，会检查目标数据项是否存在排他锁，如果没有，则通过申请；如果有，则不通过申请，让事务先等待。

如果一个事务涉及更新两个数据项 A 和 B，例如从 A 转 50 元给 B，那么在更新 A 数据后，不能马上释放 A 锁，因为 B 还没有完成更新。如果此时有另外一个事务访问 A 和 B，那么将看到合计值不一致的状态。

当一个事务跨多个数据项进行更新时，由于获取每个数据项的锁之间存在空挡。在这个空挡中，有可能其他并行事务也获得了某个数据项的锁，此时有可能会进入死锁状态，即事务 1 持有数据 A 的锁，然后准备申请数据 B 的锁，事务 2 持有数据 B 的锁，准备申请数据 A 的锁，导致进入相互等待的死锁状态。

锁的授予

饿死：在某些极端情况下，某个事务申请某个数据项的锁，但一直处于等待状态，长时间没有进展。

为避免饿死，需要引入先来后到的规则，即如果有多个事务对同一个数据项申请锁，则优先分配给最早申请的那个事务，以避免其他事务加塞。

两阶段封锁协议

该协议要求事务在不同的阶段做不同的事情，不能混在一起：

增长阶段（growing phrase）：该阶段只允许申请锁，但不允许释放锁；
缩减阶段（shringking phrase）：该阶段只允许释放锁，但不允许申请锁；

简单来说，就是事务一开始默认处于增长阶段，此时控制器接收事务提交的锁申请。一旦事务释放了锁，那么控制器认为事务已经进入了缩减阶段，接下来不再接收该事务的锁申请。因此，如果事务要申请多个数据项的锁，必须在前期一次性发起，而不能在释放某个锁后再发起。

两阶段协议可用来保证可串行化，但无法用来保证避免出现死锁和级联回滚。

两种变体：

严格两阶段封锁协议：事务在提交前，不能释放排他锁，可避免级联回滚；
强两阶段封锁协议：事务在提交前，不能释放任何锁；

虽然强两阶段协议可以保证串行，但增加了事务间的等待，损失了一定的性能。通过引进锁转换的机制，可一定程度减少等待，提升性能。

锁转换：在增长阶段，允许共享锁升级为排他锁；在缩减阶段，允许将排他锁降级为共享锁

封锁的实现

锁管理器使用一个锁表来管理各数据项的状态（授予或等待）。锁管理器使用链表作为数据结构，每一个锁请求，对应链表中的一个表项，按请求到达的顺序进行排列。表项使用溢出链来存储数据项的锁状态。

其中 I7, I23, I912, I4, I44 等是指数据项的编号；T23, T1, T8 等是事务的编号；另外锁管理器还需要维护一个索引，用来查询某个事务项下涉及的锁的集合。这样当该事务中止时，能够删除或释放其项下的锁。

这里的锁表是一个三级结构，分别为：请求->数据项->事务；当一个事务发起多次请求时，该事务将分布在不同的表项中。

锁管理器的工作流程：

收到某个数据项的加锁请求时，检查数据项是否已存在；
- 若存在，将请求添加到溢出链末尾；检查先前的请求是否已授予锁
  - 已授予，等待；
  - 未授予，授予；
- 若不存在，新建一个溢出链；
收到某个数据项的解锁请求时，将对应数据项溢出链中的事务记录删除。检查是否存在其他记录
- 如有，检查是否可以授权
  - 若可以，进行授权；
  - 若不行，等待；
如果某个事务中止，则根据索引，找到所有相关的锁集合，删除所有等待加锁的请求，并释放持有的所有锁；

基于图的协议

假如数据项满足偏序，即数据的访问存在固定顺序 A -> B（可以是索引形成的逻辑顺序，也可以是物理存储的顺序），那么说明数据的访问过程类似一个有向无环图（数据库图），类似下面这个样子：

对于偏序数据，可使用树形协议来实现调度。树形协议只使用排他锁，有以下一些规则：

每个事务，最多只能对一个数据项加一次锁；
首次加锁的对象，可以是任意一个数据项；
之后加锁的对象，要求事务持有其该对象的父节点的锁；
可以随时解锁；
一个数据项被解锁后，不可以再次加锁；

基于树形协议的调度，可实现冲突可串行化，而且也不会产生死锁。但无法保证可恢复性和无级联回滚。

如果想保证可恢复性和无级联，那么在事务结束前，不允许释放排他锁，但这样会降低并发性。

如果只想保证可恢复性，那么在发生写操作时，需要记录相应的事务ID；之后如果有其他事务读取该数据，则添加提交依赖的标记，以便确保被依赖的事务先被提交。如果出现中止，相关依赖的事务也会被中止。

树形协议的优点是不会死锁，无须回滚，较少的等待时间（因为会较早解锁）；缺点则是会访问原本无需访问的数据项，并给他们加锁，降低了并发性。

死锁处理

两种处理死锁的办法：

死锁预防：阻断源头，确保永远不会发生死锁（以牺牲部分性能为代价）；
死锁检测和恢复：出现死锁后回滚；

出现死锁进行回滚时，有时可以不用全部回滚，而是部分，即回滚释放某个被等待的锁后，就可以正常了；

当出现死锁的概率较高时，优先用死锁预防的办法；当死锁概率较低时，优先使用死锁检测与恢复的办法；

死锁预防

以下是预防死锁的几种办法：

方法一：要求获得所有数据项的锁，以确保不会出现相互等待；

缺点：事务开始前，不知道有哪些数据项需要加锁；事务开始后，很多数据项在封锁期间实际可能用不到，降低了并发；

方法二：对所有加锁请求进行排序

事务只能按照数据项的顺序，申请加锁请求，以确保不会出现相互等待；

方法三：每当等待有可能会造成死锁时，就直接回滚事务，而不是进入等待状态；

该要求需要给事务加个时间截，当事务 A 申请的数据项的锁，被事务 B 持有时：

wait-die（等待或死亡）：如果事务 A 的时间截小于 B，则等待，否则回滚；
wound-wait（等待或伤害）：如果事务 A 的时间截大于 B，则等待，否则 B 回滚（B 会被伤害）；

方法四：锁超时

给事务的等待时间设置上限，超过后，就回滚事务。

缺点：不知道事务实际需要等待多久，有可能造成误伤（死锁未发生），或者无谓等待（死锁已发生）；

死锁检测与恢复

思路：有点像是一个定时器，定期检查是否存在死锁，如有，就尝试解决；检查的时间间隔取决于死锁的发生概率；如果较频繁发生，则需要检测的更加频繁一些。

死锁检测

可使用有向图（等待图）是否存在环来判断是否存在死锁。

死锁恢复

死锁恢复通常会涉及以下一些动作：

选择牺牲者：即选择要回滚的事务，理论上是选择能够让回滚代价最小的事务，但有时候“最小代价”不是很好判断，因为它有可能不只是涉及有多少个数据项会受到影响，还涉及计算了多久；
回滚：有两种回滚方案，一种是彻底回滚，一种是部分回滚。通常部分回滚更好一些，一是因为减少影响面，二来不容易造成二次死锁；但部分回滚需要额外记录事务的一些状态信息才有办法实现；
饿死：在特定的牺牲策略下，有可能会造成某个事务总是被选为牺牲者，最终造成饿死。为避免出现这种情况，可在牺牲策略中记录已回滚的次数；

多粒度

前述的加锁都是针对单个数据项，如果当某个特殊场景需要对整张表加锁时，以数据项为单位进行加锁显然效率低下。因此，需要给加锁操作引入不同的颗粒度级别，例如表级别、数据库级别等。

事务可以为树中的每个节点申请加锁，当锁授予成功后，该节点的后代节点也隐式的获得了相同类型的锁。为了避免出现加锁冲突，每次进行锁检测时，都需要从根节点往下遍历，确保某个节点的父节点未处于封锁状态。

当给某个节点加锁时，还需要给其所有父节点添加意向锁（intention lock mode），以便用于记录某个父节项下的子节点，是否处于封锁状态。意向锁也分于共享和排他两种类型。

给节点添加锁需要遵循一套特定的规则，称为多粒度封锁协议（multiple granularity lock protocol），以便保证锁的可串行性。协议要求加锁操作需要自顶向下操作，释放锁的操作则是自底向上。

多粒度封锁协议的好处是可以提高并发性，减少加锁开销，尤其适用以下两个场景：

给少数数据项加锁的短事务；
访问整个文件或多个文件生成报表的长事务；

基于时间戳的协议

时间戳

有两种办法是可以实现时间戳：

使用系统时钟；
使用计数器；

另外每个数据项还需要额外记录两个状态值，以便用于调度决策：

最后一次成功执行写操作的时间戳 R-timestamp；
最后一次成功执行读操作的时间戳 W-timestamp；

时间戳排序协议

基本规则：

事务发起读操作 read(Q)
- 如果 read(Q) 的时间戳 < W-timestamp，说明要读的值已经被改写，拒绝 read 操作，回滚事务；
- 如果 read(Q) 的时间戳 >= W-timestamp，则执行 read 操作，并更新 R-timestamp 为当前事务的时间戳；
事务发起写操作 write(Q)
- 如果 write(Q) 的时间戳 < R-timestamp，说明要写入的值是之前需要的，拒绝 write 操作，回滚事务；
- 如果 write(Q) 的时间戳 < W-timestamp，说明要写入的值可能已经过时，拒绝 write 操作，回滚事务；
- 其他情况，执行 write 操作，并更新 W-timestamp 为当前事务的时间戳；

以上规则可以保证不产生死锁，因为没有事务处于等待状态，但有可能产生饿死，因为某些长事务可能被一系列存在冲突的短事务导致反复重启；当出现这种情况时，需要设置重启次数的上限；若超过了，则暂时阻塞有冲突的短事务，确保长事务能够完成。

另外以上规则可能产生不可恢复的调度，因此需要引入新的规则，选择以下任意一种规则均可：

将写操作放在事务的最后执行；在执行过程中，任何事务都暂时不允许访问已写完的数据；
在更新数据项的事务提交之前，暂时不允许其他事务访问数据项；
如果事务 A 读取了事务 B 所写的数据，那么在事务 B 提交之前，事务 A 暂时不允许提交；

Thomas 写规则

如果严格按照前述时间戳协议的基本规则，可能会出现一些不必要的回滚，导致并发性降低。为应对这种情况，引入了 Thomas 写规则，它对写规则的第二点进行了微调：

如果 write(Q) 的时间戳 < W-timestamp，说明要写入的值可能已经过时，忽略 write 操作，不回滚事务（区别：原本是要回滚的）；

Thomas 写规则的一个好处是引入了非冲突可串行化，这是目前为止其他两个协议（两阶段协议、树形协议）无法实现的。

基本有效性检查的协议

加锁协议或按时间戳排序等并发控制机制不可避免会带来一定的性能开销以及事务的延迟，属于悲观的并发控制。为提升性能，使用乐观的并发控制也是一种可行的方案。

乐观的并发控制对事务进行有效性检查，它将事务分成三个阶段执行，它们分别是：

读阶段：将数据读取到临时变量中；
有效性检查阶段：对事务进行有效性检查，确保执行 write 操作不会违反可串行性；如果违反，则终止事务；
写阶段：将变量中写操作的临时结果提交保存到数据库中（注：只读操作可忽略这个阶段）；

同一个事务需要按顺序执行以上三个阶段，不同事务之间的三个阶段可以交叉执行；

为实现有效性检测，需要记录事务三个阶段各自的时间：

事务开始时间，Start
有效性检查的时间，Validation
完成写阶段的时间，finish

有效性检查协议有点类似于基于有效性检查（Valication）的时间戳排序协议。

对于 TS(T_A) < TS(T_B)，要通过有效性测试，需要至少满足两个条件中的一个：

Finish(T_A) < Finish(T_B)，因为 A 事务的完成时间在前，所以不会影响到 B 事务；
事务 A 准备写入的数据集，和事务 B 准备读取的数据集之间，不存在重合；并且事务 A 的写阶段，在事务 B 开始有效性检查之间完成；

有效性检查协议可以避免出现级联回滚，因为写操作需要先完成。但是存在饿死的可能，即涌入很多短事务，导致某个长事务一直处于重启和等待的状态。为避免饿死，一种方法是引入重启上限，如果超过上限，让先阻塞短事务，让长事务有机会执行完成。

有效性检查是一种乐观的并发机制，锁协议和时间戳排序协议则是悲观的并发控制机制；二者的区别在于，对于悲观机制，如果发现冲突，则进入等待或回滚；对于乐观机制，它优先检查是否可并发，如果不可以，才进入等待或者回滚。

多版本机制

前述的几个协议，每个数据项只有一份拷贝，因此出现冲突时，要么等待，要么回滚。如果保存数据项的多个版本，那么可以进一步提高并发性。当然，这个机制也会引入一个新的问题，即如何判断应该读取哪个版本，才能保证结果的正确性（也即实现冲突可串行化的调度）

多版本时间戳协议

每个数据项需要保存一系列不同版本的信息，包括：

Content，数据项的值；
W-timestamp，创建该版本的事务的时间戳；
R-timestamp，成功读取该版本的事务的最大时间戳（该值是动态的，会随着读取事务进行更新）；

假设 Q 表示数据项的一个最新版本：

当事务 T 发出 Read(Q) 请求时，直接返回 Q 版本的内容；
当事务 T 发出 Write 请求时：
- 如果 T 的时间戳小于 R-timestam(Q)，则说明 T 要写入的数据已经过时了，因此回滚事务 T；
- 如果 T 的时间戳等于 W-timestam(Q)，则说明 T 要写入的数据，正好是当前事务之前写入的，因此可覆盖 Q 的内容；
- 如果 T 的时间戳大于 W-timestam(Q)，则说明 T 要写入新版本的数据，因此创建一个新的版本；

过时的数据版本的删除规则：假设最新版本为 Q3，同时还存在两个过时的版本 Q1 和 Q2，那么 Q1、Q2 中较老的版本可以删除，因为不会再用到了。

本协议的优缺点：

优点：读请求不用等待；因为多数业务场景是读远大于写，所以这个优点的好处很大；
缺点：不保证可恢复性和无级联，需要引入新的规则；

多版本两阶段封锁

两阶段锁也可与多阶段协议结合，以提高并发性；结合后的协议用于对只读事务和更新事务进行版本上的区分；只读事务在新协议下无须等待；

对于强两阶段协议，更新事务获得锁之后，会一直持有，直至事务结束后才会释放，因此更新事务是可串行化的。

需要设置一个全局的计数器 ts-counter；创建一个新事务时，会以 ts-counter 的值作为事务的时间戳，创建完成后，ts-counter 递增1；

只读事务将遵守多版本的时间戳排序协议，数据库系统根据只读事务的时间戳 TS，返回小于 TS 的数据项版本中的内容；

更新事务读取数据项，需要先获得共享锁，数据库系统返回最新版本中的值；更新后，需要先获得排他锁，然后创建一个新版本的数据，该版本的时间戳为 ts-counter + 1，同时全局的 ts-counter 也需要递增 1；同一时间内，仅能允许一个更新事务进行提交；

多版本的两阶段协议的好处是让只读事务需要等待加锁，同时也能够保证可恢复性和无级联。

快照隔离

概念：每个事务拥有一份数据库的快照，然后读和写都发生该份快照上，这样就无须考虑与其他事务的并发冲突问题，同时每个事务也不会看到其他事务对相同数据项的更新。但最终数据还是要写回数据库的物理设备的，此时数据库软件需要处理多份快照之间数据不一致的问题。

事务在提交时，单个事务内的更新操作需要做为一个原子操作执行；

更新事务的有效性检验步骤

当两个更新操作出现并发时，如果不加以控制，让后面的写入覆盖前面的写入时，将会出现更新丢失。为了预防这种情况，需要有一个检查机制，判断哪个更新操作允许写入，而另外一个则需要回滚。

检查机制有两种策略：

先更新者获胜

假设事务 T 进入了部分提交的状态，那么：

检查是否有其他事务与 T 并发，对于 T 计划写入的数据项，是否存在其他事务是否已经提交写入；
若存在，则 T 中止；
若不存在，则 T 提交；

先提交者获胜；

事务 A 在更新某个数据项之前，需要先申请获得一个写锁；

拿到锁：
- 如果数据项已经被其他并发事务更新，则 A 中止；
- 如果没有被其他并发事务更新，则 A 可提交；
没拿到锁，则 A 进入等待状态，直到另外一个持有锁的事务 B 中止或提交：
- 如果 B 出现中止，则 A 获得锁，进入第一步；
- 如果 B 提交，则 A 中止；

串行化问题

快照机制咋看上去很美好，但它存在一个问题，即无法保证可串行化。例如：

可能存在两个事务，各自读取对方要写入的数据；
两个事务插入相同的主键；
事务 A 创建外键，事务 B 删除了该外键指向的主键；

为了避免出现以上的情况，数据库不能仅在快照上做约束检查，还需要在快照之外，也即事务提交时，进行约束检查；

插入操作、删除操作与谓词读

删除

在数据项被删除之后进行读取或写入都会产生逻辑错误，因为事务中的删除操作也可能与其他事务发生冲突。

在两阶段协议中，一个数据项在删除之前，需要先获得排他锁；

在时间戳协议中，假设事务 T 要执行 delete(Q) 指令：

如果 T 的时间戳小于 R-timestamp(Q)，则说明要删除的值已经被读取使用，因此 T 需要回滚；
如果 T 的时间戳小于 W-timestamp(Q)，则说明要删除的值，已经被定入了新的版本，因此 T 需要回滚；
若不存在以上两种情况，则 T 执行；

插入

在数据项插入之前进行读取，显然也是一种逻辑错误；

在两阶段协议中，如果事务 T 执行 insert(Q) 操作，则需要先获得该数据项的排他锁；

在时间戳协议中，如果事务 T 在执行 insert(Q) 操作后，将数据项的 R-timestamp 和 W-timestamp 设置为事务 T 时间戳的值；

谓词读和幻象现象

幻象元组：事务 A 在执行过程中，并发事务 B 插入了一个新的元组；这会导致事务 A 进行第二次相同条件查询（谓词读）的时候，将会产生不一致的结果，即不可重复读；

还有一种幻象场景，即原本某个数据项不满足 A 的查询条件，但并发事务 B 对数据项的属性进行了更新，更新后的元组满足事务 A 的查询条件。这种情况也会导致事务 A 再做第二次查询的时候，结果将与第一次不同，也是一种不可重复读；

显然，仅仅在元组上进行封锁，没有办法杜绝谓词读场景中可能产生的幻象，还需要增加其他封锁条件，例如对索引进行封锁，控制谓词读的并发。

封锁整个索引会严重降低并发性能，通常是封锁索引上的某个叶子结点，该叶子节点满足谓词条件，同时将封锁的影响面降到最低。这种处理方案称为索引封锁协议。

除了索引封锁协议，还有一种方法是使用谓词锁，即对查询条件（谓词）添加共享锁。其他并发事务在执行前，需要检查自己是否满足谓词。若不满足，可继续执行。若满足，则等待。这种方案的性能代价很大，一般在实践中很少采用。

大部分数据库软件都没有实现谓词锁和索引封锁；

实践中的弱一致性级别

隔离级别从高到低分别是：可串行化、可重复读、已提交读、未提交读；有些业务场景对一致性要求不高，此时可考虑降低隔离级别来提升性能。

二级一致性

二级一致性也是一种封锁协议，同样有共享锁和排他锁，但它没有将事务分成两阶段；共享锁可在任意时候释放，也可以在任意时间获得；排他锁则在事务提交或中止之后释放；

二级一致性协议不保证可串行性，也不保证可重复读，但它可以防止级联中止。从本质上来说，它相当于“可提交读”的隔离级别；

游标稳定性

游标稳定性是二级一致性的一种实现方案。有些程序利用游标对关系中的元组进行迭代，此场景可使用游标稳定性方案，它保证：

如果元组被遍历处理，则加上共享锁；
如果元组被修改，则加上排除锁，直到事务提交后才释放；

此方案主要适用场景为高频访问的表；且一致性要求不高。

跨越用户交互的并发控制

前面讨论的并发控制机制，并未考虑事务是否涉及用户的交互，而只是研究多个并发控制之间如何控制顺序。但在实际的业务场景中，用户的交互也会影响并发控制。

例如一个常见的场景是先从数据库读取数据，呈现给用户；用户基于看到数据，进行相关的操作，之后提交保存到数据库；读取和提交之间，是存在一定时间差的。在这个时间差中，数据有可能被其他用户做了修改。

此场景的一种常见应对方案是使用乐观并发控制，即不对读操作做任何限制，但是会在数据元组中添加一个版本号的字段。应用程序在第一次读取数据后，将版本号信息先缓存在会话中，之后用户提交写入操作时，先检验一下版本号是否发生变化。如果已经改变，说明数据被其他用户动过了，事务中止；如果没有变，则允许写入，并将版本号加1；这种机制需要对象关系映射（ORM）组件提供支持，例如创建一个与用户交互的对话 conversation，以便和使用版本号的常规事务进行区分。

索引结构中的并发

索引本身也是一种数据，因为对它的访问也存在并发问题。由于索引的访问非常频繁，因此对它进行加锁的代价有可能是很大的。不过还好，索引的访问并不需要保证可串行化。

索引通常使用 B+ 树结构，该结构的并发控制也可以使用锁，但与常规的两阶段锁协议有些不同，它使用蟹行协议。之所以叫这个名字，据说是因为加锁的过程有点像是螃蟹走路，先动一只脚，落地后，再移动另外一只脚。过程如下：

当查找一个值时，同样从根节点开始查找，先获得根节点的共享锁，然后遍历根节点的子节点。找到对应的子节点后，获得子节点的共享锁，然后释放父节点的共享锁。重复这个过程，一直到达叶节点。此时将只持有叶子节点的共享锁，所以父级节点的共享锁都已经释放了；
当插入或删除一个码值时：
- 首先需要先找到叶子节点，因此过程同上；
- 获得叶子节点的排他锁，插入或删除码值；
- 如果插入或删除涉及分裂节点或者合并节点，那么需要申请获得父节点的排他锁。由于分裂或合并有可能是级联传播的，因此有可能需要获得一连串的父结点的排他锁。

索引的加锁过程涉及两个部分，分别是向下和向上的传播。这个过程有可能会造成死锁，如果真的发生，可先释放搜索操作的共享锁，然后重新从根节点再次搜索。

除了蟹行协议，为了获得更大的并发性，还有一种并发控制机制是使用改良版的 B+ 树，称为 B-link 树；它与 B+ 树的区分在于，B+ 树仅在叶子节点保存指向右边兄弟节点的指针，B-link 则要求所有中间节点都这么做。B-link 封锁协议的操作过程如下：

查找一个值时，先获得子节点的共享锁，然后释放父节点的共享锁。如果查找过程中发生了分裂，则根据指针查找右兄弟节点（这点是蟹行协议做不到，因此蟹行协议需要重新获取父节点的写锁）；对于叶子节点，则需要遵循两阶段封锁协议，以避免出现幻读现象；
插入或删除一个值时，查找叶子节点的过程同上。找到叶子节点后，将共享锁升级为排他锁，然后遵循两阶段协议对叶子节点进行更新。
分裂：如果事务导致节点分裂，那么需要给新建的节点添加右兄弟指针，并且还需要给父节点加写锁，以便能够将新节点的指针更新到父节点中。
合并：如果事务导致节点合并，那么需要给待合并节点加写锁，然后更新右兄弟指针；之后父节点加锁，删除被合并节点的指针。

问：据说通过右兄弟指针可以减少锁的持有时间，提高并发性，为什么？

答：主要是相对于蟹行协议而言，当发生分裂时，蟹行协议要求重新获得父节点的排除锁，然后再查找对应的子节点。而 B-link 树因为已知右兄弟节点的指针，因为可以跳过这一步，直接申请右兄弟节点的锁即可。由于没有向上传播，B-link 封锁机制减少了死锁的概率；

问：当发生分裂时，由于需要将新节点的指针存放到父节点中，因此貌似获取父节点的排他锁是不可避免的？

答：确实不可避免。假设此时有另外一个查找操作处于等待，那么当父结点的锁被释放后，查找将继续，但是此时该操作获得的指针仍然指向旧结点，因此不可能找到。好了，此时重点来了。对于蟹行协议，此时需要重新申请回到父结点，但 B-link 树则不用，因此当前节点拥有右兄弟节点的指针，可以直接向右查找，无需回到父节点。

对于删除操作，如果目标节点因为合并被删除了，那么处于等待的查找操作持有的指针将指向一个不存在的节点。当出现这种情况时，该操作将进入死胡同，因此需要从根节点重头开始查找。考虑到日常业务中，删除操作的发生频率，因此代价可能是可以接受的。

除了 B-link 协议，还有一种提高并发性的技术是码值封锁，即不封锁整个节点，而是只封锁两个码值，一个是目标码值，另外一个是比目标码值大的下一个码值。

第16章恢复系统

第17章数据库系统体系结构

第18章并行数据库

第19章分布式数据库

第20章数据仓库与数据挖掘

决策支持系统

数据库应用可分为两大类，分别为：

事务处理：用来记录与事务相关的信息；
决策支持：从事务处理系统中提取高层次的信息辅助决策；

传统数据库应用在决策支持场景遇到的一些问题：

在传统的事务处理系统广泛使用 SQL 查询语言，并不适合执行详细的数据统计分析任务；要么写不出来，要么写出来很复杂，不容易被理解，或者查询性能低下；
数据可能跨多种不同的数据库应用进行存储，有多种来源；
数据挖掘技术对数据库有要求；

数据仓库

数据仓库：将数据从多个来源以统一的格式汇总存储到一个统一的数据库中。

数据仓库成分

有两种数据归集方式：

主动型：由源数据库实时和定期将数据发送到目标数据库；
被动型：由目标数据库定期向源数据库发送查询请求；

由于决策支持系统通常并不需要实时的数据，因此通常没有必要实时同步，这样也可以提高性能；

数据仓库的职责之一是对不同的数据源进行数据的整合，因此它看起来有点类似数据源的一个物化视图，而不仅仅是源数据的一份拷贝。

源数据通常存在一些细微的错误、重复或不一致，此时一般会增加一个数据清洗的环节，例如去重、格式转换等；

源数据的数据量可能很大，但做为决策支持的数据，通常是一些汇总数据，因此它可以很小，这样可以减少维护整个关系的性能代价；

将数据存入数据仓库主要涉及抽取 extract，转换 transform，装载 load 等几个步骤，简称 ETL；

数据仓库模式

数据仓库主要面向数据分析的场景，因此其模式也有所不同，通常使用 OLAP 工具。数据采用多维模式，通常由维属性和度量属性组成；

维属性一般指某种标识，用于 group by，度量属性一般指数值类的属性，例如价格、数量等，用于做数学运算，例如 sum，average 等；

星型模式由一个事实表 + 多个维表组成；对于复杂的业务场景，维表还可以有自己的维表，此时星型模式看起来像是雪花模式。

面向列的存储

传统的数据库使用面向行的模式，数据仓库有时会使用面向列的模式，将某个属性单独存储为一个表文件，通过减少无关数据的访问，来提高访问性能。

列存储的优点：

减少了无关数据的内存加载；
同类型数据有助于提高压缩率；

列存储的缺点：

写入时，或者读取单个元组时，将涉及多次 I/O 操作；

虽然列存储在事务处理系统中用得很少，但在统计分析的场景中用得很多。

数据挖掘

数据挖掘的目标是从数据集中发现规则和模式。例如发现一个模式：年收入超过 5 万美元的年轻妇女，最有可能购买小型跑车。

发现的规则或模式有很多应用场景，其中最广泛的一种应用场景是用来做预测，例如某个人申请信用卡时，预测其会不会违约，风险有多大。

另外一种预测场景是关联。例如当某个人购买了 A 物品时，预测其可能也需要 B 物品。

关联规则

其他类型的关联

聚类

其他类型的数据挖掘

第21章信息检索

文本信息通常是非结构化的，因此需要有专门的技术，实现对文本类型数据的高效查询。它的侧重点包括：

基于关键字的查询；
文档与查询的相关性；
文档的分析、分类和索引；

概述

信息检索领域与数据库领域的一个不同在于，信息通常以非结构化的形式存储，没有特定的模式，例如存储为文档类型，并且是数量庞大的文档，每个文档长度不一。之后基于用户的输入（包括关键字或者示例文档）来定位目标文档。

信息检索技术在 Web 资源搜索领域，发挥到了关键作用。在 Web 环境中，每个 HTML 文件即是一份文档。用户通常使用关键字来描述其预期想要检索的一份或一系列特定的文档。

由于文档以非结构化的形式存储，因此如何计算关键字与文档之间的相关性变得很重要。在全文（full text）检索场景中，文档中的每个词都会当作关键字，一般使用术语（term）来表示这些关键字。会提前计算文档中每个术语的索引，例如术语在文档中的位置、出现次数等；如果再将这些信息映射到多维空间中，就能够实现对文档的理解（这是 NLP 自然语言处理领域的基础做法）；

目前主流的搜索引擎不仅只是按相关性返回文档列表，还会基于关键字，结合时事热点，判断用户可能所处的场景，并基于场景返回信息。例如当用户输入 NBA 时，不仅会返回 NBA 的相关文档，还会返回最近的赛事、赛程等。

使用术语的相关性排名

由于用户输入的关键字数量有限，但数据库中的文档数量庞大，因此按相关性高低返回结果是非常有必要的。虽然相关性查询无法非常精确，但目前已经有一些相关成熟的做法。

使用 TF-IDF 的排名方法

假设文档用 d（document）表示，术语（term）用 t 表示，TF 术语频率（Term Frequency）表示相关性，一种计算相关性的公式为：

其中：

n(d, t) 表示术语 t 在文档 d 中出现的次数；
n(d) 表示文档 d 中的术语总数；

简单来说，就是关键字在文档中出现的越频繁，相关性就越高。但不是线性关系，而是对数关系。

如果文档存在某些结构，例如分成了标题、摘要、作者列表等部分，那么还可以通过计算这些部分的 TF，并给予不同的权重，来进一步提高检索的准确性。

当查询中包含多个术语时，不同术语显然不能等同对待，因为有些单词是连接词，例如 and，the 等；此时需要对这些语言中特殊的高频词汇单独处理。一种处理方法是通过计算逆文档频率（Inverse Document Frequency）给予不同的权重；还有一种方法是做一个停用词列表（英语中大约有 100 个左右），将这类单词剔除掉，不纳入相关性的计算。

逆文档频率的计算公式如下：

其中：n(t) 表示包含术语 t 的文档数量，这个值越大，说明这个单词越是频繁的出现在各式文档中，显然它大概率是一个通用单词，跟业务场景无关。

因此，计算查询中多个术语的相关性总和的公式如下：

其中：r(d, Q) 表示文档 d 与查询 Q 的相关度；如果允许用户指定某个术语的权重，那么公式中还可以再乘上一个权重系数 w(t)；

另外还一个可以纳入计算的维度是术语的接近度（proximity）；如果术语在一份文档中越接近，那么相对另一份术语比较疏远的文档，显然前者的相关性大概率更高。

基于相似性的检索

使用场景：给定一份文档 A，从数据库寻找相似的文档 B；思路一是先从 A 文档中找出 TF(d, t) * IDF(t) 最大的 k 个术语，然后拿着这 k 个术语作为关键字，从数据库中查找相关度最高的文档。

还有另外一种方法是使用余弦相关性，它其实是将一个拥有 n 个术语的文档 A，映射到 n 维空间中得到一个向量 V。然后计算各个文档在这个 n 维空间中的向量与向量 V 的夹角。夹角越小，说明相似度越高。

其中：r(d, t) = TF(d, t) * IDF(t)；

如果按上述方法匹配后结果集很大，那么还可以引入“相关反馈”（relevance feedback）的方法，来进一步改善匹配结果。它的原理是从基于余弦相似性的匹配结果中，让用户挑选几份最相关的文档。然后基于这几份文档的相似性，再做一轮搜索。

还有一种替代相关反馈的方法是让用户增加关键字。二者的本质是一样的，即增加输入（筛选条件）来缩小输出范围。从易用性来说，相关反馈可能会更好一些。因为它没有让用户思考，而是让用户选择。

搜索引擎可以使用余弦相似性对文档提前进行聚类，之后当用户进行查询时，可以在搜索结果中展示不同的分类。

对于 Web 文档，由于引用的大量存在，因此对搜索结果进行去重是必须的，否则排名靠前的文档，都是一些重复文档。

使用超链接的相关性

Web 文档包含一个普通文本文档不具备的特性，即它可以内嵌超链接。这些超链接可用于对搜索结果的相关性进行排名。

流行度排名

包含同样关键字的页面有很多，但它们的流行度可能存在很大的不同。将流行度高的页面，排在搜索结果的前面，有可能更契合用户的需求。毕竟流行程度从某种意义来说，也算是对页面内容质量的一种背书。

计算流行度的一种方法是看这个页面的链接，在多少个其他页面中出现（即被引用）；为了实现这个统计，搜索引擎需要抓取并分析页面内容，即统计里面有多少个链接，这些链接是指向哪些网站，之后将结果存入数据库，用来计算流行度。

一种计算方案是按页面的外链数量来计算；一个站点的页面有很多，但外部链接通常只指向该站点的根页面；由于子页面仅被根页面引用，这种算法会导致子页面计算出来的流行度很低，导致好的页面没有被发现。

另一种计算方案是按站点的外链数量来计算；一个站点可能分成很多个版块，不同版块的流行度可能存在很大的不同。这种方案会导致准确性下降，即混入了一些不相关的页面。

针对以上问题的一种解决方案是传递威望。它的原理是当一个页面被其他威望值高的页面引用时，它可能分享该页面的威望值。相当于即使一个人并不知名，但如果很多知名人物都认识他，那么应该给其设置高威望值。

PageRank

PageRank 使用随机游走模型来统计页面的流行度。随机游走是指用户打开一个页面后，假设有 δ 概率会随机打开另外一个完全不相关的页面，但是也有 1 - δ 的概率会打开当前页面中显示的链接。

计算过程：它抓取一个页面后，先统计其中的超链接。然后赋予每个超链接 1 - δ 的打开概率。之后将该打开概率累加到超链接页面的 PageRank 值中。

原理：如果一个页面的链接被其他很多页面引用，那么该页面最终累加的 PageRank 会很高。而被高 PageRank 页面指向的页面，其 PageRank 也会跟着比较高。

其中：

δ 是 0 ~ 1 之间的一个常数；
P[i] 是指 i 页面的 PageRank；
T[i, j] 是指随机游走者从 i 页面跳转到 j 页面的概率；T[i, j] = 1 / N
N 是 i 页面引用的链接数量；

以上方程可使用迭代进行求解，P[i] 的初始值设置为 1/N，每一次迭代更新 P[i] 的值；当某一次更新的幅度小于临界值时，停止迭代；

其他的流行度度量

搜索引擎一开始并不知道每个网站的被访问量，这个数据掌握在网站的所有者中，无法直接获取。但有一种间接的办法，即搜索引擎在返回搜索结果时，将结果的链接替代为自己的服务器链接；当用户点击时，记录该链接的被点击次数。然后返回一个重定向的链接，让浏览器打开真正的目标页面。

PageRank 可以很好的计算流行度，但页面内容与查询的关键字并没有相关性。解决该问题的一种方法是利用超链接的标题来判断页面内容。有时候网页开发者只将一句话中的少数单词做为链接标题，此时可以将超链接所在的整句话都纳入计算。

HITS 算法中的链接中心与权威页（详情页）的概念；链接中心页是一个包含指向很多权威页（详情页）链接的页面，但它本身可能并不包含关键字信息；权威页则是一个包含关键字的页面，但没有包含指向其他权威页的链接；二者都可以计算威望值。如果一个链接中心指向很多高权威页，则它的链接中心威望值也跟着升高；同理，如果一个权威页链接被很多高权威的链接中心页所包含，那么它的威望值也升高。

搜索引擎作弊

提高页面的搜索排名是有利可图的，因此必然有人想要钻排名算法的空子，这是一场旷日持久的斗争，道高一尺，魔高一丈。例如故意建一个链接中心站点，包含大量链接指向高流行高的网站。这样根据算法可以获得高威望值，然后在其中混入一些不流行的小网站，以便通过威望值传递，让这些小网站获得高排名。

将 TF-IDF 和流行度排名度量方法结合

为了获得高质量的搜索结果，搜索引擎需要综合多种算法。早期搜索引擎的开发者通过人工的方式整合这些算法，现在则更倾向于使用机器学习的方法，让模型通过数据集习得算法，提高灵活度和准确性。

同义词、多义词和本体

在大多数语言中，存在不止一个词汇可以用来表达一个相近的概念。不同的用户在使用关键字进行搜索时，可能会使用不同的同义词。因此搜索算法的开发者，需要考虑这个情况，以便能够最大化的呈现用户想要的结果。

解决以上问题的一种方法是提炼通用概念，即从一组同义词中提取出一个通用的概念。之后不管是输入的关键字，还是输出的结果，都以该概念作为匹配条件。

由于用户输入的关键字有限，直接从中猜测用户想要的概念，有时候不一定准确，此时可提供多个概念选项，让用户进行选择，之后再进行搜索。

使用概念进行搜索还有一个好处是可以跨语言查询。因为虽然不同的语言形式不同，但概念却是相通的。由于现实世界中的物体，通常包含种属的层次关系。因此在概念系统加入层次关系，有助于进一步提升准确性。概念之间的层次结构可用本体（ontoloty）来表达。这些层次关系包括：is-a，part-of 等；

本体是哲学研究中的一个概念，主要研究存在的本质，存在的类别，以及与其他存在的关系；

除了日常生活中的语言外，在特定的领域存在一些专业术语，因此也可以定义不同的本体，以专门处理该领域的专业问题。例如法律、医学、物流等诸多领域。

文档的索引

检索的有效性度量

Web 的抓取和索引

信息检索：网页排名之外

目录与分类

第22章基于对象的数据库

第23章 XML

第24章高级应用开发

第25章时空数据和移动性

第26章高级事务处理

第27章 PostgresSQL

其他

视图

视图有如下一些好处：

当为用户开通数据库的账号，允许其访问数据库时，视图可用来隔离用户直接访问原始表；有限制的开放表中的某些列，让用户查看；也可以限制只能访问某些行；
当查询数据库的 SQL 编写比较复杂时，可将该 SQL 存为视图，方便复用，避免每次查询时手工编写；

以上两个好处都是建立在开放数据库的账号给用户，但在 web 应用的场景中，用户是不能直接访问数据库的，所以这些好处都派不上用场；

存储过程

优点：

预编译 SQL，可一定程度提高性能；
查询数据后，可直接计算出结果，减少数据的传输；

缺点：

有可能使用了某些数据库的特性，导致后续不方便移植；
不方便调试，毕竟不是代码；
当表变大后需要拆分时，可能会造成极大的重新编写和测试的工作量；

事务隔离

事务不可避免存在并发,这些并发的事务会相互影响, 因此会出现以下几种可能:

脏读: 事务 A 能够看到事务 B 即将对某行数据做出修改,于是读取修改后的值；但后来事务 B 发生了回滚, 并没有将做出修改；导致当事务 A 读到的值, 是一个不存在的值；
不可重复读: 事务 A 读取某行数据后, 事务 B 修改了该行数据, 导致事务 A 再次读取时, 发现数据变了；
幻读: 事务 A 读取数据后, 事务 B 又新增或删除了一些新数据, 导致事务 A 在写入时,数据变多或变少了；

为解决以上问题, 数据库引入了几种事务隔离机制:

可读取未提交数据: 这种隔离等同没有, 它会导致脏读；
只读取提交的数据: 这种隔离可避免脏读；但无法避免另外两种问题；
重复读: 引入读锁, 每次只允许一个事务读, 这样就可避免”不可重复读” 的问题了；
串行化: 引入读锁 + 写锁, 相当于所有事务排队按顺序执行, 这样可避免以上全部三个问题, 但代价是性能下降；

或许可以用空间换时间, 如果内在不是问题,那么或许可以为每个待修改的行建立一个队列, 序列化执行；

计算机

#数据库

数据库系统概念

https://ccw1078.github.io/2014/05/09/数据库系统概念/

作者

ccw

发布于

2014年5月9日

许可协议

用户体验要素-概要上一篇

SQL 下一篇

数据库系统概念

第1章 引言

数据库语言

关系数据库

存储管理部件

查询处理器

事务管理

第2章 关系模型介绍

关系数据库的结构

数据库模式

码

模式图

关系查询语言

关系运算

第3章 SQL

SQL 查询语言概览

SQL 数据定义

常用基本类型

基本模式定义

SQL 查询的基本结构

单关系查询

多关系查询

自然连接

附加的基本运算

更名运算

字符串运算

select 子句中的属性说明

排列元组的显示次序

where 子句谓词

集合运算

并运算

交运算

差运算

空值

聚集函数

基本聚集

分组聚集

having 子句

对空值和布尔值的聚集

嵌套子查询

集合成员资格

集合的比较

空关系测试

重复元组存在性测试

from 子句中的子查询

with 子句

标量子查询

数据库的修改

删除

插入

更新

第4章 中级 SQL

连接表达式

连接条件

外连接

连接类型和条件

视图

视图定义

使用视图

物化视图

视图更新

事务

完整性约束

单个关系上的约束

not null 约束

unique 约束

check 子句

参照完整性

事务中对完整性约束的违反

复杂 check 条件与断言

SQL 的数据类型与模式

SQL 中的日期和时间类型

默认值

创建索引

大对象类型

用户定义的类型

create table 的扩展

模式、目录与环境

授权

授权的授予与收回

第1章引言

第2章关系模型介绍

第4章中级 SQL

第5章高级 SQL

第6章形式化关系查询语言

第7章数据库设计和 E-R 模型

第8章关系数据库设计

第9章应用设计和开发

第10章存储和文件结构