2022FALL《数据库系统原理》期末复习笔记

由
内容纲要

第一章 关系型数据库

数据库系统由一个互相关联的数据集和一组用以访问这些数据的程序组成。

文件处理系统存储、组织信息弊端有下：

  • 数据的冗余和不一致
  • 数据访问困难，对于每个新任务需要编写新的应用程序处理
  • 数据孤立，多个文件具有不同的格式
  • 完整性问题，完整性约束“固化”（buried）在程序代码中，很难通过修改程序来体现新的约束
  • 原子性问题，故障会导致部分更新，使数据库处于不一致状态
  • 并发访问异常
  • 安全性问题

关系模型：表（行列）用于表示数据和数据间的联系
实体-联系（E-R）模型：实体、联系；数据库设计
基于对象的数据模型：E-R模型增加了封装、对象等
半结构化数据模型：用XML来表示半结构化数据

数据抽象的三个层次：屏蔽数据结构的复杂性

视图层：视图可以隐藏信息，使用户仅访问数据库的一部分，提高安全性。
逻辑层：描述存储在数据库中的数据，以及数据之间的关系，降低耦合。
物理层：描述数据实际上是怎样存储的。

模式：数据库的总体设计。
实例：特定时刻存储在数据库中的信息的集合。

SQL: 广泛使用的非过程化（声明式）语言

第二章 关系模型介绍

关系数据库由表的集合构成。

关系模式的表示

元组：表中的一行，顺序无所谓。
属性：必须是原子的，具有属性域。

关系模式可以表示为R(A_1, A_2,..., A_n)，如：

  • instructor(ID, name, dept\_name, salary)
  • department (dept\_name, building, budget)

在关系模式中，使用相同属性可以将不同关系的元组联系起来。

元组中的码

超码：若K能唯一标识关系r(R)中的一个元组，则K是关系r(R)的超码。
超码作为元组，可以是一个或者多个属性的集合。

候选码：任何真子集都不能成为超码的最小超码称为候选码。

选择值很少或者从不变化的候选码作为主码。

外码：一个关系模式r1在其属性上包含另一个关系模式r2的主码，这个属性在r1上称为参照r2的外码。r1称为外码依赖的参照关系，r2称为外码的被参照关系。

参照完整性约束：参照关系中的任意元组在特定属性（如外码）上的取值，必须等于被参照关系中的某个元组在该特定属性上的取值。

模式图：

  • 每一个关系模式用一个矩形来表示
  • 主码属性用下划线标注
  • 外码约束（依赖）用从参照关系的外码到被参照关系的主码之间的箭头表示

关系代数

六个基本关系运算：

  • 选择 \sigma
  • 投影 \Pi
  • 集合并 \cup
  • 集合差 -
  • 笛卡尔积 ×
  • 更名 \rho

此外，集合交、自然连接和赋值运算可以用以上基本运算来定义。

选择运算

选择满足给定谓词条件的元组。
\sigma_{dept\_name='Physics'}(instructor)

投影运算

过滤掉特定属性。
\Pi_{ID,name,salary}(instructor)，只选择instructor表的指定三列。

笛卡尔积运算

结合来自任意两个关系的信息。
两个关系的所有元组一对n行配对。相同的属性名可能同时出现在两个表中。如果重名，需要加入表的名字作为属性前缀。

运算的组合

可以使用多种运算构建表达式。
\sigma_{A=C}(r×s)，将r和s表连接。

连接运算

r\bowtie_{\theta}s=\sigma_{\theta}(r×s)

集合并运算

r\cup s
要求r和s必须同元，属性数量和属性域必须相同。

集合差运算

r-s
要求r和s必须同元，属性数量和属性域必须相同。

查询举例

利用大学模式，找出最高工资。
\Pi_{salary}(instructor)-\Pi_{instructor.salary}(\sigma_{instructor.salary < d.salary}(instructor × \rho_{d}(instructor)))

第三章 SQL基础

数据定义语言DDL

SQL的DDL能够定义每个关系的信息，包括：

  • 关系的模式
  • 属性的取值类型，取值范围
  • 完整性约束
  • 关系的安全性和权限信息
  • 每个关系维护的索引集合
  • 每个关系在磁盘上的物理存储结构

SQL的基本类型

SQL的常用基本类型包括：

  • char(n): 固定长度的字符串，用户指定长度n
  • varchar(n): 可变长度字符串，用户指定最大长度n
  • int: 整数类型 (4字节)
  • smallint: 小整数类型 (2字节)
  • numeric(p,d): 定点数，精度由用户指定。这个数有p位数字，其中，d位数字在小数点右边
  • real, double precision: 浮点数与双精度浮点数，精度与机器相关
  • float(n): 精度至少为n位的浮点数

基本关系模式的定义

create table instructor(
    ID char(5),
    name varchar(20),
    dept_namt varchar(20),
    salary numeric(8,2),
    primary key(ID),
    foreign key(dept_name) references department
);

SQL禁止破坏完整性约束的数据库更新，例如：

  • 新插入元组的主码为空值或重复
  • 新插入instructor元组的dept_name未出现在department关系中，破坏外码约束

删除和修改表

drop table：删除表和其中内容。
delete from：删除表内容，但是保留关系模式。
alter table R add/drop A：增加或删除属性。
许多数据库都不支持删除属性，但支持drop整个表。

select语句

select A,B,C
from r,m
where P1 and/or/not... P2;

ABC代表属性，rm代表关系，P是谓词（限定条件）。

例如大学模式中，查找所有教师的名字。

select name
from instructor;

SQL语句是不区分大小写的。

all/distinct

SQL在查询结果和关系中默认允许重复。为了强制消除重复，在select后加上关键字distinct。

属性的运算

selec子句可以包含算术表达式，例如：

select ID, name, salary/12
from instructor;

where子句

where子句表示结果满足的必须限定条件。
例如找出Comp.Sci系中工资大于80000教师的姓名。

select name from instructor
where dept_name = 'Come.Sci' and salary > 80000;

from分句

from中可以用逗号隔开多个关系，表示多个关系间的笛卡尔积。

select * from instuctor, teaches;

连接

接上一小节，如果要去除无效属性，则需要用where子句选择出属性名和属性均相同的元组。

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

如果省略where子句，则谓词P为true。

自然连接

在连接的基础上，去除重复属性列。

select name, course_id
from instructor natural join teaches;

更名运算

SQL允许对关系和属性进行更名操作。

使用as子句更改属性名：

select ID, name, salary/12 as monthly_salary
from instructor;

使用as子句更改关系名（as可以省略）：

select distinct T.name
from instructor as T, instructor as S
where T.salary > S.salary and S.dept_name = 'Comp.Sci';

字符串运算

SQL的like运算符可以实现模式匹配：

  • 百分号匹配任意字符串
  • 下划线匹配任意一个字符

SQL字符串使用单引号，关系代数的字符串使用双引号。
SQL的匹配模式是大小写敏感的。

'intro%'匹配以intro开头的字符串。
'%Comp%'匹配包含Comp子串的字符串。
'___'匹配只含三个字符的字符串。
'___%'匹配至少包含三个字符的字符串。

例如，找出姓名中包含dar的教师的姓名。

select name
from instructor
where name like '%dar%';

元组的排序

使用order by A，令查询结果按照属性A排序。
可以用desc表示降序，asc表示升序，省略则按照asc排序。

select distinct name
from instructor
order by name desc;

排序可以在多个属性上进行。

order by dept_name desc, name asc;

where子句谓词

SQL提供between运算。
例如找出工资在90000和100000之间的教师姓名。

select name
from instructor
where salary between 90000 and 100000;

元组比较符可以比较属性组成的元组，但是不建议使用。

集合运算

union表示并，intersect表示交，except表示差。
集合操作自动消除冗余，如果要保留冗余，需要在运算关键字后面加上all。

空值

属性为空可以以null表示它的值。

使用null的谓词可以测试空值：

  • is null
  • is not null

任何与null的算术表达式结果为null。
任何空值的比较运算表达式结果为unknown。

unknown逻辑表达式

四个特例：

  • unknown or false = unknown
  • unknown and false = false
  • not unknown = unknown
  • unknown is unknown = true

如果where子句的谓词结果为unknown，可以当作false处理。

如果元组在除了null值外的所有属性上取值相等，那么它们可以视为相同元组。
但是这样的元组用逻辑等于运算后，结果为unknown。

聚集函数

聚集函数包括：

  • avg
  • min
  • max
  • sum
  • count

其中，sum和avg的输入必须是数字集。

例如：
找出Comp.Sci教师的平均工资。

select avg(salary)
from instructor
where dept_name = 'Comp.Sci';

分组聚集

查询每个学院的平均工资。

select dept_name, avg(salary)
from instructor
group by dept_name;

在select子句中出现，但是不在group by子句中出现的属性，只能出现在聚集函数内部。

子查询

在查询中调用另一个有特定限制的关系时，可以使用嵌套子查询。

空关系测试

用于测试一个子查询结果是否存在元组，关键字exists。

例如查询在2009年秋季学期和2010年春季学期同时开课的所有课程：

select course_id
from section as S
where semester = 'Fall' and year = 2009 and
    exists(select *
           from section as T
           where semester = 'Spring' and year = 2010 and S.course_id = T.course_id);

可以使用not exists（B except A)表示关系A中元组集合包含关系B的元组集合。

例如：找出选修了Biology系开设的所有课程的学生

select distinct S.ID, S.name
from student as S
where not exists((select course_id
                  from course
                  where dept_name = 'Biology')
                 except
                 (select T.course_id
                 from takes as T
                 where S.ID = T.ID));

from子查询

注意，如果子查询需要使用having子句的条件，一般写在父查询的where子句中。

lateral关键字：使得from子句中的子查询使用来自其他关系的相关变量。

标量子查询

该子查询返回包含单个属性的单个元组。

不带from子句的标量

例如，查询平均每位教师所讲授的课程段数。

(select count(*) from teaches)/(select count(*) from instructor)

数据库的修改

删除

删除所有在位于Watson大楼的系工作的教师。

delete from instructor
where dept_name in (select dept_name from department
                    where building = 'Watson');

当删除操作对查询过程的表达式产生影响时，SQL采用一种解决方案：

  • 先计算
  • 再删除（无需重新计算或者测试）

插入

在插入表格的内容来源于本表格时，应当先执行select语句，再执行插入。

更新

给工资超过100000的教师涨3%的工资,其余教师涨5%。

update instructor
    set salary = case
        when salary <= 100000 then salary * 1.05
        else salary * 1.03
    end

第四章 中级SQL

连接表达式

连接操作以两个关系为输入，将另一个关系作为结果返回。

加入course和prereq中均有course_ids属性，则以下查询等价：

select * from course natural join prereq;
select * from course join prereq using(course_id);

要求保留重复的属性，以下查询等价：

select *
from course join prereq on course.course_id = prereq.course_id;

select *
from course, prereq
where course.course_id = prereq.course_id;

外连接

外连接是连接的扩展，可以避免因为连接导致的操作结果信息的丢失。

外连接的过程：先执行连接操作，然后将两个关系中不匹配的元组都加入到最后的结果关系中，并使用null作为属性值补全。

连接操作默认为内连接。

左外连接保留第一个关系模式的所有元组，右外连接保留第二个关系模式的所有元组。全外连接则全部保留。

视图

在某些情况下，用户对关系的访问需要加以控制。视图提供了向用户隐藏特定数据的机制。

一旦定义了视图，就可以用视图名指代该视图生成的虚关系。
视图定义会导致一个表达式被存储，当使用这个视图时，查询过程中这个表达式将会被代入使用。、

例如：
创建视图

create view faculty as
    select ID, name, dept_name
    from instructor;

select name
from faculty
where dept_name = 'Biology';

create view departments_total_salary(dept_name, total_salary) as
    select dept_name, sum(salary)
    from instructor
    group by dept_name;

一个视图可能被用到定义另一个视图的表达式中，如果视图v2用于v1的定义中，我们称v1直接依赖v2。
如果v1直接依赖v2或者从v1到v2有一条依赖路径，我们称v1依赖v2。
如果一个视图v依赖其自身，我们称该视图v是递归的。

视图展开：递归地将语句中所有的视图替换为它所存储的表达式。只要涉及到的所有视图的定义不是递归的，视图就可以被展开。

物化视图

特定数据库系统允许师徒关系被存储，当实际关系改变时，视图也随之更改，这样的视图称为物化视图。
维护一个物化视图需要将实际关系的改变应用到视图中。

视图更新

考虑faculty关系：

create view faculty as
    select ID, name, dept_name
    from instructor;

如果要插入元组，那么插入操作必须被描述为对关系instructor的操作。
考虑下述插入语句：

insert into faculty
values ('30765', 'Green', 'Music');

对于此语句，数据库有两种处理方法：

  • 拒绝插入
  • 插入('30765', 'Green', 'Music', null)，因为instructor还有一项salary属性

更为复杂的情况，考虑下述视图：

create view instructor_info as
select ID, name, building
from instructor, department
where instructor.dept_name= department.dept_name;

insert into instructor_info values('69987','White','Taylor');

由于插入的属性分别位于两个关系模式中，只能在instructor表中插入('69987','White',null,null)，在department中插入('null','Taylor',null)。但是由这两张表构建出来的视图还是不存在元组（'69987','White','Taylor')。

一般情况下，不允许对视图关系进行更新。
如果定义视图的查询语句对下列条件都能满足，我们称SQL视图是可（插入）更新的：

  • from子句只有一个关系
  • select子句只包含关系的属性名，不包含任何表达式，聚集函数或distinct生命
  • 任何没有出现在select子句中的属性内容可以取空值
  • 查询不包含group by，having
更新带条件的视图

考虑下述视图：

create view history_instructors as
select *
from instructor
where dept_name = 'History';

数据库允许向history_instructor插入('25566','Brown','Biology',100000)，即使创建视图时的条件是dept_name = 'History'。

视图定义的时候，可以加入with check option子句，可以拒绝不满足视图where子句条件的元组更新和插入。

create view history_instructors as
select *
from instructor
where dept_name= 'History'
with check option;

事务

事务（Transaction）由查询和（或）更新语句的序列组成。
事务的开始是隐式的，以commit或rollback结束一个事务。其中commit指令提交事务，并持久保存事务所做的更新。rollback回滚当前事务，撤销事务的更新。

事务具有ACID特性：

  • 原子性：要么事务的所有影响被反映到数据库中，要么在回滚之后不产生任何影响；
  • 一致性：事务的执行不能破坏数据库数据的完整性和一致性，一个事务在执行之前和执行之后，数据库都必须处于一致性状态。如果数据库系统在运行过程中发生故障，有些事务尚未完成就被迫中断，这些未完成的事务对数据库所作的修改有一部分已写入物理数据库，这是数据库就处于一种不正确的状态，也就是不一致的状态；
  • 隔离性：事务的隔离性是指在并发环境中，并发的事务时相互隔离的，一个事务的执行不能不被其他事务干扰。不同的事务并发操作相同的数据时，每个事务都有各自完成的数据空间，即一个事务内部的操作及使用的数据对其他并发事务时隔离的，并发执行的各个事务之间不能相互干扰；
  • 持久性：一旦事务提交，那么它对数据库中的对应数据的状态的变更就会永久保存到数据库中。即使发生系统崩溃或机器宕机等故障，只要数据库能够重新启动，那么一定能够将其恢复到事务成功结束的状态。

在大多数数据库中：每个SQL语句默认为一个事务，自动提交。也可以通过begin atomic end将多条语句视为一个事务。

完整性约束

完整性约束防止的是对数据的意外破坏，它保证授权用户对数据库所做的修改不会破坏数据的一致性。

实体完整性约束

实体完整性约束保证关系中的每个元组都是可识别的和唯一的：

  • not null：声明属性不可为空
  • unique：指出属性（组）形成一个超码，但是允许为null
  • check：是的关系中的每个元组都必须满足谓词P

参照完整性约束

参照完整性约束一般是指多个实体或关系之间的关联关系，用于描述实体之间的联系。

用户自定义完整性约束（域完整性或语义完整性约束）：关系中属性的取值范围，避免属性的值与应用语义的矛盾。它保证在一个关系中给定属性集上的取值也在另一关系的特定属性集的取值中出现。

外键：若r1.k1参照的属性集r2.k2为所属关系r2的主键，则称k1为参照关系r2.k2的外键。

参照完整性中的级联操作
create table course(
    dept_name varchar(20),
    foreign key(dept_name) references department
        on delete cascade
        on update cascade
);

表示在department中删除某个元组后，在course中也删除参照被参照的已删除元组。

将cascade替换为set null, set default，表示在department中删除某个元组，即将course中参照被删除系置空或置为默认值。

外码可以为null，值为null的外码自动被认为满足约束。

如何在不违反完整性约束的情况下插入一个元组:

  • 先将配偶信息设为null，在插入配偶元组后再更新该配偶信息（当配偶信息设为not null 时，该操作不可行）
  • 推迟完整性约束检查到事务结束时进行

复杂Check条件与断言

断言就是一个谓词，它表达了我们希望数据库总能满足的一个条件；属性域约束和参照完整性约束是断言的特殊形式。

create assertion <assertion-name> check <predicate>;

SQL的数据类型和模式

类型转换

使用后表达式：cast(e as t)将表达式e转换为类型t。
例如：

select cast(ID as numeric(5)) as inst_id
from instructor
order by inst_id;

coalesce()函数可以解决输出空值的情况，该函数接收任意相同数量的参数，并返回第一个非空参数。

在DDL定义关系时，default关键字可以定义属性的默认值。

创建索引

create index studentID_index on student(ID);

大对象类型

blob：二进制大对象。
clob：字符大对象。

用户自定义类型

create type Dollars as numeric(12,2) final;
create table department(
    budget Dollars
);

drop type删除类型，alter type更改类型。

域

域类型是可以有约束和默认值的用户自定义类型。
基本类型相容的一个域类型的值可以被赋给另一个域类型。

模式、目录与环境

数据库系统提供三层结构的关系命名机制：目录/模式/关系、视图。

授权

数据库在数据上的权限：

  • select 允许读取
  • insert 允许插入
  • update 允许修改
  • delete 允许删除

数据库在模式上的权限：

  • index 允许创建、删除索引
  • resources 允许创建新的关系
  • alteration 允许添加或删除关系中的属性
  • drop 允许删除关系

授权规范

对视图的授权并不代表对视图相关的实际关系的授权；权限授予人必须已经具有对指定项目的权限（或者是数据库管理员）。

grant select on instructor to U1,U2,U3;
grant update(salary) on instructor to U1, U2, U3;

with grant option字段允许被授权的用户将此权限授予其他用户。

收回权限

revoke update(budget) on department from U1,U2,U3;

默认级联收回权限（cascade），如果使用restrict关键字，可以避免一些不合适的权限级联收回。

如果某些权限被不同的授权者授予同一个用户两次，那么在一次权限回收后该用户可能仍保有这个权限；一个权限被回收后，基于这一权限的其他权限（如视图）也将被回收。

角色Role

权限可以被授予给角色：

grant select on takes to instructor;

角色可以被授予给用户，同时也能被授予给其他角色：

grant instructor to Amit;
create role TA;
grant TA to instructor;

模式授权

SQL标准为数据库模式指定了一种基本的授权机制：只有模式的拥有者才能够执行对模式的任何修改。

SQL提供了references权限，允许用户在创建关系时声明外码。这个权限能够避免没有ref权限的用户创建参照联系，从而引发限制其他用户操作的行为。

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

设计过程

概念设计阶段：构建E-R图
逻辑设计阶段：将E-R图映射到关系模式
物理设计阶段：指明数据库文件组织格式和索引结构

E-R模型

E-R模型是一种语义模型，在将现实世界事物的含义和相互关联映射到概念模式方面非常有用。

E-R模型采用三个基本概念：

  • 实体集
  • 联系集
  • 属性

一个数据库可以被建模为：

  • 实体的集合
  • 实体间的联系

实体集

实体是现实世界可区别于所有其他对象的一个“事物”或“对象”，实体集则是实体的集合。

实体有属性，它是实体集中每个成员所拥有的描述性性质。
每个实体的每个属性都有一个值。

联系集

联系指多个实体之间的相互关联。

实体在联系中扮演的功能称为实体的角色。
当同样的实体集参与一个联系集多于一次，这类联系集称作是递归联系集。

联系集的度

参与联系集的实体集数目称为联系集的度。

约束

映射基数约束

映射基数，又叫基数比率，表示一个实体通过一个联系集能关联的实体个数。

参与约束

如果实体集E中的每个实体都参与到联系集R的至少一个联系中，实体集E在联系集R中的参与称为全部的。

如果实体集E中只有部分实体参与，则称E部分参与R。

联系集的超码

由相关实体集的主码构成的集合。

冗余属性

假如有实体集instructor，department和联系集inst_dept，instructor中有dept_name属性，那么这个属性就是冗余的，因为有一个明确的联系关系。

E-R图

矩阵代表实体集，属性在实体矩阵中列出，构成主码的属性用下划线表明，菱形代表联系集。

参与联系集中的实体集

全部参与用两条线表示。

具有属性的联系集

基数约束联系集表示

我们在联系集和实体集之间画一个箭头(→)代表“一”或者一条线段(—)代表“多”来表示基数约束。

有三元联系的E-R图

我们只允许在一个三元（或三元以上）联系集外有一个箭头来表示基数约束。如果多于一个箭头，会有多种解释导致歧义。

弱实体集

没有足够属性形成主码的实体集叫做弱实体集。
弱实体集必须与标识或属主实体集关联才有意义。
将弱实体集与其标识实体集相连的联系称为标识性联系。

弱实体集通过一个全部参与的、（多对一或一对一）的联系集与标识实体集联系。

弱实体集的主码由标识实体集的主码和该弱实体集的分辨符（部分码）共同组成。

弱实体集的分辨符用虚下划线表示。

强实体集的主码并不存储于弱实体集，如果存入弱实体集，会导致属性的重复存储。

E-R模型转化为关系模式

实体集和联系集都可以用表示数据库内容的统一的关系模式来表示；
每个实体集和联系集都有一个特有的关系模式与其对应，并分配相应的名字；
每个关系模式都有一些列（通常对应属性），每个列都有唯一的名字；

模式的冗余

多对一和一对多的联系集的模式，如果“多”方参与是全部的，那么可以将“多”方实体集和联系集的模式合并成单个包含两个模式所有属性并集的关系模式。

比如模式instructor,department，教师和学院的基数约束是多对一的，并且全部教师参与与学院的联系。因此可以将department的主码dept_name加入instructor，并添加外码约束。这样就可而已少建立一个联系集。

如果“多”方参与是部分的，也可以通过使用空值来进行模式合并。转换为关系模式时，联系集中“一”方的相关属性应注意不能设为not null。

在一对一联系的情况下，联系集的关系模式可以跟参与联系的任何一个实体集的模式进行合并。

扩展的E-R特性

特化

在实体集内部进行分组的过程称为特化。

子集中的实体在某些方面区别于实体集中的其他实体，这些子集成为了较低层的实体集，可能具有高层实体集不具有的属性、或者参与到高层实体集不参与的联系集中。

特化通过从特化实体指向另一个实体的空心箭头来表示 (e.g., instructor “is a” person)

概化

概化是高层实体集与一个或多个低层实体集间的包含关系。

不相交：一个实体至多属于一个低层实体集。
重叠：同一个实体可同时属于同一概化的多个低层实体集。

完全性约束：定义高层实体集中的一个实体是否必须属于该概化的至少一个低层实体集。
全部：必须属于一个；
部分：不加限制；

默认情况是部分概化。

聚集

为不引入冗余，用聚集来表示E-R模型。

第八章 关系数据库设计

好的关系设计的特点

函数依赖

考虑department(dept_name, building, budget)关系，主键是dept_name，即dept_name可以确定(building, budget)，即保持函数依赖：dept_name -> building, budget。

有损分解

无法通过自然连接重建原始关系元组的分解为有损分解。

考虑这种情况，将employee(ID, name, street, city, salary)分解为employee_attr1(ID, name)，employee_attr2(name, street, city, salary)。
其中name无法作为第二个关系的主码，因为可能有重名。这时候将attr1，attr2自然连接，无法得出原始的关系。

函数依赖

假设r(R)是一个关系模式，a,b是R上的属性。
则R上的函数依赖a\rightarrow b成立的条件是，如果对于任意关系实例r中的两个任意元组t_1,t_2，如果两者的属性a相同，则它们的属性b相同。
函数依赖a\rightarrow b称为a函数确定b，或者b函数依赖于a。

函数依赖允许我们表达超码不能表达的约束。

如果关系实例r在函数依赖集F上合法，则称r满足F。如果模式R上的所有合法关系实例都满足函数依赖集F，我们说F在关系模式R上成立。

有些函数依赖被称为平凡的，因为它们在所有关系中都是满足的。
例如：

  • name -> name
  • ID, name -> ID

通常，如果属性集b\subseteq a，那么a->b就是平凡的函数依赖。

a->b，则这里的a是决定因素。

函数依赖a->b称为部分依赖的条件是：存在a的真子集c，使得c->b。

函数依赖集F能够推导出的所有函数依赖的集合，我们称之为F集合的闭包，记作F+。

逻辑蕴含

给定关系模式r(R)，如果r(R)的每个满足F的实例也满足某个函数依赖f，则R上的函数依赖f逻辑蕴含（logically imply）于r上的函数依赖集F。

计算函数依赖集闭包算法

F+ = F
repeat
    for each F+中的函数依赖f
        在f上应用自反律和增补律
        将结果加入到F+中
    for each F+中的一对函数依赖f1和f2
        if f1和f2 可以使用传递律结合
            将结果加入F+中
until F+不变

属性闭包

属性集a在函数依赖集F下，由属性a函数确定的所有属性集合叫做F下a的闭包，记为a+。

属性闭包可以判断属性是否是超码，验证函数依赖，计算F的闭包。

规范化

规范化的目标

令每个关系模式都是好的模式：无数据冗余。
分解是无损分解，保持依赖。

范式

1NF

如果一个关系模式R的所有属性域都是原子的，那么R是1NF。

非原子的值会造成复杂存储及数据冗余。

2NF

在1NF基础上，F+中每一个非主属性完全函数依赖于候选码，则R是2NF。

BCNF

在2NF基础上，对所有F+中的函数依赖a\rightarrow b，如果b不是a的子集，那么a一定是R的一个超码。

排除了任何属性（包括主属性和非主属性）对候选码的部分依赖和传递依赖，也排除了主属性之间的传递依赖。

如果F上的每一个函数依赖都在其分解后的一个关系上成立，那么这个分解是保持依赖的，但是BCNF分解通常不保持依赖，因此增加检查约束的开销。所以考虑3NF。

将模式分解为BCNF：假设有模式R，及其一个非平凡依赖a\rightarrow b不属于BCNF，那么可以将R分解成：(a\cup b),(R-(b-a))，如果分解后的模式仍然不符合BCNF，那么继续按照上述方法分解，直到每个模式都属于BCNF为止。

BCNF的问题：检查约束的开销很大，但是如果只涉及到单个关系，检查约束的开销就相对较低。但是BCNF的分解会导致原模式的某些函数依赖的检查开销变大。
比如对于模式(sid, iid, dept)，函数iid\rightarrow dept; sid, dept \rightarrow iid成立。观察到函数iid \rightarrow dept不符合BCNF，因为根据上述函数依赖，唯一超码为(sid,dept)。所以根据BCNF分解规则，将模式分解为a\cup b:(iid, dept); R-(b-a):(sid, iid)。
然而，函数依赖sid, dept \rightarrow iid在新的两个模式中间的验证，需要在两个模式的连接运算后检查。因此这种分解是不保持依赖的。所以需要设计一种保持依赖的，较BCNF更加宽松的范式。

3NF

3NF比起BCNF，对所有F+中的函数依赖多了一个可选成立条件：b-a中的每个属性A都包含在R的候选码中。

第三个条件是BCNF的一个最小放宽：即允许存在主属性对候选码的传递依赖和部分依赖，在函数依赖集F中用来满足保持某些函数依赖。

也就是说，具有函数依赖集F的关系模式R属于3NF，则R的任何非主属性既不部分依赖于码，也不传递依赖于码。

例：对于关系模式R(S,C,P)，S表示学生，C表示课程，P表示成绩，判断R属于哪一种范式。

  1. 易得R属于1NF；
  2. 对于关系模式R，写出R的函数依赖集F\{(S,C)\rightarrow P, (C,P)\rightarrow S\}，F+=F。因此R的候选码为：(S,C),(C,P)，主属性为：S,C,P。由于不存在非主属性，所以R属于2NF；
  3. 对于F+中任意非平凡的X→Y，所有的X都是R的一个候选码（超码），所以R属于BCNF；

例：对于关系模式R(S,T,C)，S表示学生，T表示教师，C表示课程，规定每个教师只教一门课，判断R属于哪一种范式。

  1. 易得R属于1NF；
  2. 对于关系模式R，写出R的函数依赖集F\{T\rightarrow C, (S,C)\rightarrow T, (S,T)\rightarrow C\}，并且F+=F。因此R的候选码为(S,C),(S,T)，主属性为：S,T,C。由于不存在非主属性，所以R属于2NF；
  3. 对于F+中非平凡的X→Y，其中T→C中的T不是候选码，所以R不属于BCNF；
  4. 对于函数依赖T→C，C包含于R的候选码，所以R属于3NF。
BCNF的缺陷

BCNF不是一个足够好的关系模式，考虑关系inst_info(ID, ChildName, tel)，其中一个inst可以有很多个孩子和电话。
对于这个关系模式，不存在任何非平凡的函数依赖，所以它是BCNF。但是当要对某个ID新建一个电话号码的时候，需要插入他孩子数量的元组。因此存在由多值依赖造成的信息冗余。这里需要4NF来规范关系模式。

函数依赖理论

正则覆盖

F的正则覆盖F_c不存在任何的冗余依赖或冗余的部分依赖。并且和F具有相同的依赖集闭包F+。

无关属性

无关属性的形式化定义：对于函数依赖集F和其中的函数依赖a→b，如果

  • 对于属性A\in a，F逻辑蕴涵(F-(a\rightarrow b))\cup ((a-A)\rightarrow b)
  • 对于属性B\in b，F逻辑蕴涵(F-(a\rightarrow b))\cup (a\rightarrow (b-B))
    那么其中的A是a中的无关属性，B是b中的无关属性。

无关属性的验证：考虑函数依赖集F和F中的函数依赖a→b

  • 为了验证属性A\in a是否多余，使用F中的函数依赖计算属性集闭包(a-A)+，验证其是否包含b，如果包含，那么A是无关属性
  • 为了验证属性B\in b是否多余，使用函数依赖集(F-a\rightarrow b)\cup a\rightarrow(b-B)计算a+，验证其是否包含B，如果包含则无关
计算F的正则覆盖算法
Fc=F;
repeat
    使用合并律将Fc中的依赖合并；
    再Fc中将包含无关属性的函数依赖中的无关属性从依赖中删除
until Fc不变

在删除了某些无关属性后可能需要使用合并律，因此合并律会重复应用。

F的正则覆盖Fc是一个函数依赖集，具有如下特性：

  • F逻辑蕴涵Fc中的所有函数依赖
  • Fc逻辑蕴涵F中的所有函数依赖
  • Fc中的任何函数依赖都不含无关属性
  • Fc中的函数依赖左部都是不同的

无损分解

将模式R分解成R1，R2。如果R1和R2的交集属性是R1或R2的超码，那么称这个分解是无损的。

保持依赖

如果分解的模式的函数依赖集的并集的闭包，和原来函数依赖集F的闭包相同，那么说这种分解是保持依赖的。

保持依赖的检验

对F中的每一个函数依赖，检测其是否被分解后的模式保持。

result = a;
while (result变化) do
    for each 分解后的Ri
        t = (result \cap Ri)+ \cap Ri
        result = result \cup t

如果最后result包含b中的所有属性，那么函数依赖a→b被保持。
这个方法的好处在于，没有计算F在Ri上的限定，直接使用F上的属性闭包。

分解算法

BCNF简化判定

要检查关系模式R是否属于BCNF，仅需检查给定集合F中的函数依赖是否违反BCNF即可，不许检查F+。因为如果F中没有违反BCNF的函数依赖，F+也不会有。

但是，在检测由关系R分解后的关系Ri是否满足BCNF范式时，只使用F是不正确的。

3NF分解

3NF的分解有以下结论：

  • 允许冗余
  • 函数依赖可以不连接，在单个关系上检验
  • 总是能够在无损分解和保持依赖的情况下分解成3NF
冗余

两个问题，信息重复和空值。
考虑模式d_a(sid, iid, d_n)，表示学生，导师和专业的关系。存在F=\{sid d\_n\rightarrow iid, iid \rightarrow d\_n\}，那么对于一个导师，可能有很多他的学生，这就导致导师和专业的信息重复；对于没有学生的导师，需要对sid设置为空值。

3NF的验证

用属性闭包验证每个依赖a→b，判断a是否是超码；如果a不是超码，验证b-a中的每个属性被R的一个候选码包含。

因为要找到候选码，所以验证花销很大。是个NP难问题。但是3NF的分解可以在多项式时间内完成。

第十章 存储管理

文件组织

数据库是以一系列文件的形式存储的。每个文件在逻辑上组织成为记录的一个序列。
每个文件分为定长的存储单元，称为块（block），块是存储分配和数据传输的基本单元，块大小一般为4-8KB。
记录在文件中可以是定长的或是变长的。

定长记录

记录i从n(i-1)个字节开始存储，n是每个记录的大小。
假定每个记录都被完全包含在单个块中，不允许记录跨越块的边界。

删除第i个记录的可选方案：

  • 后面的记录前移
  • 将最后的记录放到位置i
  • 不移动记录，在空闲列表中列出空闲记录位
空闲链表

对于每个文件，分配特定数量的字节来增添一个文件头，将第一个删除的记录的地址存储在文件头。
如果删除第二个记录，那么就将第二个记录的地址存放在第一个被删除的记录里，后续的删除操作以此类推。
于是被删除的记录形成了一个链表，被称为自由链表。

如果需要插入一条新记录，就将内容存放在文件头指向的记录中，并改变文件头的指针，使其指向下一个空闲记录位。如果没有空闲记录位，则将新纪录添加在文件末尾。

变长记录

变长记录以下面几种方式出现在数据库系统中：

  • 多种记录类型存储在一个文件中
  • 允许一个或多个字段是变长的记录类型
  • 允许可重复字段的记录类型

具有变长属性的记录通常包含两个部分：

  • 带有定长信息的初始部分
  • 变长属性的内容

变长属性在初始部分中被表示为一个（偏移量，长度）对，其中偏移量表示在记录中该属性的数据开始的位置，二长度表示变长属性字节长度。

在记录初始定长的部分之后，变长属性的值是连续存储的。
记录末尾加上记录终止符。

分槽的页结构

分槽页的块头包含：

  • 块中记录的条目的个数
  • 块中空闲空间的末尾处
  • 一个由包含记录位置和大小的记录条目组成的数组

记录从块的末尾开始连续地分配空间，自由空间位于块头和记录中间。插入新记录时，在空闲空间的尾部分配空间，并将这条记录的大小和位置作为一项加入块头数组中。

如果记录被删除，它所占用的空间被释放，项被置为deleted，块中位于被删除记录前的记录将被向后移动，使空闲空间连续。

文件中记录的组织

堆文件组织：只要空间足够，一个记录可以放在文件的任何地方。
顺序文件组织：记录根据搜索码的值顺序存储。
散列文件组织：在每条记录上的某些属性上计算一个散列函数，根据函数值确定记录应该放入哪个块。

通常，每个关系的记录用一个单独的文件存储。

但是多表聚簇文件组织中，几个不同关系的记录存储在同一个
文件中，目的在于在同一块中存储相关记录，以将I/O代价减到最小。

顺序文件组织

适用于需要对整个文件进行顺序处理的应用，每个记录包含搜索码，按照搜索码排列。

所有的记录以链表的方式存储，对于删除操作，使用指针链即可。对于插入操作，如果在插入位置的所在块有空闲空间，那么插入到空闲处；如果没有空闲空间，那么将新记录插入溢出块。两种方式均需要重新调整指针，使链表按照搜索码排列。

多表聚簇文件组织

在一个文件中存储多个关系。

能够很好地处理多个关系的连接查询。对于下图，在CompSci下方的，Physics上方的教师都是CompSci系的。由于每个系是不连续存储的，所以要添加指针链，对只涉及系的查询效果不好。

数据字典存储

数据字典：也叫系统目录存储元数据（关于数据的数据）

它存储：

  • 关系的信息
    • 关系的名字
    • 每个关系属性的名字、类型和长度
    • 视图定义
    • 完整性约束
  • 用户的账户信息
  • 统计和描述性数据
    • 每个关系中的元组数目
  • 物理文件组织信息
    • 关系如何存储
    • 关系的物理位置
  • 索引的信息

系统元数据是为在内存中进行高效访问而设计的特殊数据结构。

数据缓冲区

存储访问

每个文件分成定长的存储单元，称为块。块是存储分配和数据传输的基本单位。

数据库系统的一个主要目标就是减少磁盘和存储器之间传输的块数。减少磁盘访问次数的一种方法是在主存储器中保留尽可能多的块。

缓冲区：主存储器中用于存储磁盘块的副本的那一部分。
缓冲区管理器：负责缓冲区空间分配的子系统。

缓冲区管理器

程序需要磁盘上的块时，可以向缓冲区管理器发出请求

  1. 如果这个块已经在缓冲区中，缓冲区管理器将这个块在主存储器中的地址传给请求者
  2. 如果这个块不在缓冲区中，缓冲区管理器
    a. 在缓冲区中为这个块分配空间
    ① 如果需要的话，会把其他块移出主存储器，为这个新块腾出空间
    ② 移出的块仅当它自从最近一次写回磁盘后被修改过，才被写回磁盘
    b. 把这个块从磁盘读入缓冲区，并将这个块在主存储器中的地址传给请求者

大多数操作系统使用最近最少使用策略 (least recently used ，LRU)
当涉及对数据重复扫描的访问模式时，LRU是一个糟糕的策略。
由查询优化器提供的带有提示的混合替换策略是较好的选择：

  • 被钉住的块：不允许写回磁盘的块
  • 立即丢弃：一旦块中的最后一个元组被处理完毕，立刻命令缓冲区管理器释放这个块所占用的空间
  • 最近最常使用：系统替换最近一直使用的块，当块的最后一个元组处理完毕后，块被解除钉住，最近最常使用的块被移除

缓冲区管理器可以使用请求访问某个特定关系的统计信息
例如：数据字典被经常访问
因此：将数据字典的块保留在主存储器的缓存中

为保证数据可恢复性，缓冲区管理器也支持块的强制写出到磁
盘。

第十一章 索引

索引机制用于加速对所需数据的访问，类比于图书馆的作者目录。

搜索码：用于在文件中查找记录的属性或属性集。

一个索引文件包含索引项（搜索码值，记录指针）。
索引文件一般比原文件小很多。

两个基本类型索引：

  • 顺序索引：按搜索码顺序存储索引
  • 散列索引：使用散列函数将搜索码平均分布到若干散列桶中（一般作为辅助索引）

索引技术评价指标：

  • 能支持的访问类型
  • 访问时间
  • 插入时间
  • 删除时间
  • 空间开销

顺序索引

顺序索引：按顺序存储搜索码的值，并将每个搜索码与包含该搜索码的记录关联起来。

主索引: 顺序文件组织中，索引的搜索码指定了文件中记录的顺序（一个关系只有一个），也叫聚集索引。主索引的搜索码一般是主码，但不是必须的。

辅助索引: 搜索码指定的顺序与文件中记录的物理顺序不同的索引（一个关系可以有多个），也叫非聚集索引。

索引顺序文件: 在搜索码上有聚集索引的文件（若记录按搜索码顺序排列）。

稠密索引：文件中的每个搜索码值都有一个索引记录。

稠密聚集索引：文件中不同的元组可能有重复的搜索码，对于重复的搜索码的索引，一个索引可能对应多个元组。元组按照聚集的属性，相同的排列在一起。

稀疏索引：只为搜索码的某些值建立索引记录。在记录按照搜索码顺序排列时适用。

稠密索引与稀疏索引对比：

  • 稀疏索引插入和删除时所需的空间及维护开销较小
  • 稀疏索引定位一条记录的速度比较慢

好的折中方案：为每个块建一个索引项（块起始搜索码）的稀疏索引。

多级索引：将主索引以顺序文件的形式放于磁盘，并为之建立一个稀疏索引。防止主索引太大无法放入主存。

如果外层索引还是太大，那么就可以再建另外一级索引，以此类推；对文件进行插入或删除操作后，所有级别的索引都需要更新。

通常，我们希望找到某一特定字段（非主索引的搜索码）符合某些条件的所有记录。
例1：关系instructor按照ID顺序存储，我们希望找到某一特殊领域内的所有教师
例2：和上面相同的情况，但是我们希望找出符合给定薪水值或薪水范围的所有教师

我们可以使用一个辅助索引，每个搜索码值都有一个索引记录（稠密索引）

索引记录指向包含所有指向具有特定搜索键值的实际记录的指针，辅助索引必须是稠密的，即不可能存在辅助稀疏索引。

索引的更新会给数据库的修改带来额外的开销，每当文件被修改时，这个文件上的每个索引都要更新。

使用主索引进行顺序扫描是很高效的，但是使用辅助索引却花费很大。因为：

  • 每次对记录的访问都可能从磁盘获得一个新块
  • 获取新块需要5到10毫秒，而存储器访问只需要100纳秒

多码索引

复合搜索码是指包含不止一个属性的搜索码。

B+树索引

使用顺序索引的缺点：

  • 性能随着文件的增长而下降，因为创建了许多溢出块
  • 需要定期重组整个文件

B+树索引文件的优势：

  • 在面对插入和删除时，使用小的局部更改自动重组
  • 不需要重组整个文件来保持查询性能

B+树索引缺点：

  • 额外的插入和删除开销，空间开销

B+树结构

B+树是一种平衡树，也就是说它所有从根到叶的路径长度都相同。
对于一棵B+树，有一个特定的值n，对于n：

  • 每个非叶节点（除根节点外）都有\lceil n/2 \rceil到n个子节点
  • 一个叶节点内可包含搜索码的数量在\lceil (n-1)/2 \rceil到n-1之间

如果根节点是一个非叶节点，则它至少有两个子节点；
如果根节点是一个叶子节点，则它可以有0到（n-1）个值（即搜索码）。

在B+树的节点中，搜索码是按顺序排序的。指针域位于搜索码的左侧。

B+树的叶子节点具有如下属性：

  • 指针Pi指向具有搜索值为Ki的记录
  • 叶子节点的搜索码值从左到右升序排列
  • Pn按搜索键的顺序指向下一个叶子节点

B+树的非叶子节点形成了对叶子节点的一个多级（稀疏）索引。对于带有m个指针（m称为扇出）的非叶节点：

  • P1所在的子树中的所有搜索码都小于K1
  • Pn所在的子树中的所有搜索键的值大于或等于Kn–1
  • 对于其他指针，Pi所在子树的所有搜索码的值大于或等于Ki–1、且小于Ki

B+树特性

B+树形成了一个稀疏索引的层次结构；
B+树可以用相对较少的层次来表示大量的搜索码

因此，如果索引文件中有K个搜索键值，则树的高度（即搜索路径长度）不超过\lceil log_{\lceil n/2 \rceil}(K)\rceil

可以有效地处理对主文件的插入和删除。因为B+树索引可以在有限时间内（与树的高度成正比关系）进行有效重构。

B+树查询

典型B+树的节点规模通常与磁盘块的大小相同，通常取值为4KB，因此n取值为100左右。
对于有100万个搜索码的索引文件、且n=100，则最多查询log50(1,000,000) = 4 个节点（4个块），即可完成从根到叶子节点的遍历。

B树索引

B树只允许搜索码出现一次，消除了搜索键的冗余存储。

非叶节点中的搜索码在B树中没有其他位置可出现，因此，必须为非叶节点中的每个搜索键包含一个额外的指针字段（需指向文件记录）。

B树的优点：

  • 可能比相应的B+树使用更少的节点
  • 有时可以在到达叶节点之前找到搜索码

B树的缺点：（数据库的范围查找效率低）

  • 在所有搜索码中，只有一小部分被早期找到
  • 非叶节点需存储搜索码的记录指针，所以扇出相应地（fanout）变小了。因此，B树通常比B+树具有更大的深度
  • 插入和删除比B+树更复杂
  • 实现比B+树更难

散列索引

桶是能存储一条或多条记录的一个存储单元(一个桶就是一个磁盘块)，在散列文件组织中，通过使用散列函数直接从搜索码中获得包含该记录的桶。

散列函数h是一个从K到B的函数。K表示所有搜索码值的集合，B表示所有桶地址的集合。

散列函数用来为获取、插入和删除操作定位记录。
具有不同搜索码值的记录可能映射到同一个桶，因此整个桶都要被顺序搜索来定位记录。

散列索引无法支持范围查询。

桶溢出可以减少，但是不能消除。

闭散列

所有溢出桶用一个链表链接在一起。

开散列

没有溢出链，一个桶满后将记录插入到其他桶中。

SQL创建索引

create index <index_name> on <table_name>(<element_list>);

使用create unique index直接声明该搜索码是一个候选码。

SQL撤销索引

drop index <index_name>;

大多数数据库允许指定索引类型，并声明聚集索引。

第十三章 事务管理

事务

事务是构成单一逻辑工作单元的操作集合。
事务是访问并可能更新各种数据项的一个程序执行单元。
事务由事务开始（begin transaction）与事务结束（end transaction）之间执行的全体操作组成。

事务管理主要处理的两个问题：

  • 各类故障恢复，如硬件故障，系统崩溃
  • 多个事务的并发执行

ACID特性

为了保证数据的完整性，数据库系统必须保证：

  • 原子性：事务的所有操作在数据库中要么全部反应，要么完全不反应；
  • 一致性：事务隔离执行时保持数据库的一致性；
  • 隔离性：多个事务可能并发执行，但是单个事务的执行过程中感受不到其他事务在并发执行；例如两个事务Ti和Tj，对于Ti，Tj要么在Ti开始之前完成了执行，要么在Ti结束后开始执行；
  • 持久性：一个事务成功完成后，它对数据库的更改是永久的，即使系统出现故障。

事务原子性和持久性

事务状态：

  • 活动的：初始状态，事务执行时处于这个状态
  • 部分提交的：最后一条语句执行后
  • 失败的：发现正常的执行不能继续后
  • 中止的：事务回滚并且数据库已恢复到事务开始执行前的状态后。中止后可以重新开始事务或者杀死事务
  • 已提交的：成功完成执行的事务，如果想撤销影响需要新建执行一个补偿事务

事务隔离性

事务处理系统通常允许多个事务并发地执行。优点是:

  • 提高吞吐量和资源利用率
  • 减少等待时间

通过并发控制机制来实现事务隔离性，它控制并发执行的事务之间的相互作用，来避免他们破坏数据库的一致性。

调度

调度即指令执行顺序，指定并发执行事务的指令执行的时间顺序。
一组事务的一个调度必须包含这一组事务的全部指令；必须保持指令在各个事务中出现的顺序。

一个事务成功执行后，会有一条指令作为最后的声明，事务默认提交指令commit为其最后一条指令。

一个事务没有成功完成时，会用一条中止指令abort来作为最后的声明。

SQL的事务定义

SQL标准规定事务的开始是隐式的。
事务的结束用下列SQL语句之一来表示：

  • Commit [work]：提交当前事务并开始一个新的事务
  • Rollback [work]：回滚当前事务

在几乎所有的数据库系统中，缺省每个SQL语句如果成功执行的话，也立即隐式提交事务。
这种隐式提交也可以通过数据库指令关闭。

可串行化

基本假设：每个事务都能保持数据库的一致性
事务的串行执行是可以保持一致性的
如果一个调度等价于一个串行调度，那么这个调度就是可串行化的

按调度的不同形式可分为:

  1. 冲突可串行化（重点关注）
  2. 视图可串行化

简化视图：只考虑read和write指令。假设事务在read和write指令之间可以对本地缓冲区的数据进行任意的操作。

两条属于不同事务的连续指令，当数据项被两条指令同时访问，并且至少有一个指令执行write操作时产生冲突。

两条冲突的指令之间必须有一个逻辑时间顺序。如果两条指令在时间上连续且不发生冲突，那么可以交换这两条指令的顺序。

如果调度S可以通过一系列非冲突指令交换转化成S'，则这两个调度是冲突等价的。

若一个调度S与一个可串行调度冲突等价，则称调度S是冲突可串行化的。

可恢复性

可恢复调度：如果Ti读取了之前由Tj所写的数据项，则Tj须先于Ti提交。

下图是一个不可恢复的调度。

级联回滚：因单个事务故障导致一系列事务回滚。

无级联调度：对于每对事务Ti和Tj，如果Ti读取了之前由Tj所写的数据项，则Tj须先于Ti的这一读取操作提交。这种调度不会发生级联回滚。

并发控制

调度的目标是：

  • 冲突可串行化
  • 可恢复性，最好是无级联

并发控制则是建立一个能够保证串行化的并发控制协议。

SQL-92中的并发级别

可串行化：通常保证可串行化的执行。
可重复读：只允许毒已提交的数据，一个事务对相同数据的重复读取要返回相同的值。
已提交读：（默认）只允许读取已提交的数据，但不要求可重复读。
未提交读：允许读取未提交数据。

以上所有隔离级别都不允许脏写：即一个数据项被一个尚未提交或中止的事务写入，它不允许被任何其他事务执行写操作。

set transaction isolation level serializable

基于锁的协议

锁是用来控制对数据项的并发访问的一种机制。

给数据加锁有两种方式：

  • 排他锁，对数据项可写可读 lock-X
  • 共享锁，对数据项只能读 lock-S

unlock释放锁

申请锁请求发送给并发控制管理器，只有在管理器授予锁后，事务才能继续其操作。

锁相容矩阵：

  • 如果被请求锁与数据项上已有的锁相容，那么事务可以被授予该锁
  • 一个数据项可以同时有多个共享锁
  • 如果一个事务在某个数据项上拥有排他锁，那么其他事务不能再在这个数据项上加任何锁
  • 如果一个锁不能被授予，那么请求该锁的事务必须等待，直到该数据项上的其他不相容锁全部释放，然后再被授予锁

封锁协议：一组规定事务何时对数据项进行加锁、解锁的规则。封锁协议限制了可能的调度数目。

考虑这个调度：

排他锁lock-S(B)导致T4等待T3释放其在B上的X锁，共享锁lock-X(A)导致T3等待T4释放其在A上的S锁。
这种情况称为死锁，必须回滚并释放锁，否则调度无法进行。

大多数封锁协议都会产生死锁。

饿死：T2对一个数据项施加共享锁，此时T1事务想要在同一数据项上加上排他锁，那么就需要等候T2事务释放共享锁。然而一个事务序列{T3...Tn}对这一数据项申请共享锁的操作是不需要阻塞的，如果申请共享锁的事务过多，则T1会迟迟得不到调度。这种现象称为饿死。

避免事务饿死的授权加锁方式：当事务Ti申请对数据项Q加M型锁时，并发控制管理器授权加锁的条件须满足：

  1. 不存在在数据项Q上持有与M型锁冲突的锁的其他事务
  2. 不存在等待对数据项Q加锁且先于Ti申请加锁的事务

封锁协议：令T0-Tn是参与调度S的一个事务集，如果对于数据项Q，Ti在Q上持有A型锁，而后Tj在Q上持有B型锁，且Comp(A,B)=false，那么Ti先于Tj，记为Ti→Tj。这意味着任何等价的串行调度中，Ti必须出现在Tj前。

如果调度S是遵从封锁协议规则的可能调度置一，则它是合法的。

一个封锁协议当且仅当其所有合法的调度为冲突可串行化时，我们称它保证冲突可串行性；换句话说，对于任何合法的调度，其关联的事务优先关系是无循环的。

两阶段封锁协议

阶段1：增长阶段，即事务只能获得锁，不能释放锁。
阶段2：缩减阶段，即事务只能释放锁，不能获得锁。

封锁点：在调度中该事务获得其最后加锁的位置。（增长阶段结束点）

两阶段封锁协议保证可串行化：可以证明事务可以按照封锁点排序。

两阶段封锁不能保证不发生死锁，可能出现级联回滚。

严格两阶段封锁协议要求未提交事务所写的任何数据在该事务提交之前均以排他方式加锁，防止其他事务读取这些数据。

强两阶段封锁协议更加严格：要求事务提交之前不得释放任何锁，在这个协议下，事务可以按其提交（commit）的顺序串行化。

多粒度

将多个数据项聚成一组，作为同步单元。这样对一组数据加锁。

多粒度：允许各种大小的数据项，并定义数据粒度的层次结构，可以图形化表示为树。

如果一个事务对树的某个结点加了所，那么它也给统一模式下该结点的子结点隐式加锁。

锁的粒度:
细粒度 (树的低层): 高并发性，锁开销多
粗粒度 (树的高层): 低并发性，锁开销少

意向锁类型

除了排他锁和共享锁，多粒度下还有其他三种类型的锁：

  • 共享型意向锁（IS）：将树的较低层显式封锁，但只能施加共享锁
  • 排他型意向锁（IX）：将树的较低层进行显式封锁，能施加S和X锁
  • 共享排他型意向锁（SIX）：以该节点为根的子树显式加了共享锁，并且在树的更低层显式加了排他锁

意向锁允许较高层的节点被加上共享锁或排他锁，而无需从树根遍历到子孙节点来检验锁的相容性，提升锁相容检验的效率。

事务Ti 按如下规则对数据项Q加锁：

  1. 必须遵从锁类型相容函数
  2. 必须首先封锁树的根结点，并且可以加任意类型的锁
  3. 仅当事务Ti当前对Q的父结点具有IX或IS锁时，对结点Q可加S或IS锁
  4. 仅当事务Ti当前对Q的父结点具有IX时，对结点Q可加X、SIX或IX锁
  5. 仅当Ti未曾对任何结点解锁时，Ti可对结点加锁（满足两阶段封锁）
  6. 仅当Ti当前不持有Q的子结点的锁时，Ti可对结点Q解锁

加锁按自顶向下的顺序，锁的释放按自底向上的顺序。

基于时间戳的协议

对于系统中每个事务Ti，我们把一个唯一的固定时间戳和它联系起来，此时间戳记为TS(Ti)；该时间戳是在事务Ti开始执行前由数据库系统赋予的。

事务的时间戳决定了串行化顺序。

W-timestamp(Q)表示成功执行write(Q)的所有事务的最大时间戳。
R-timestamp(Q)表示成功执行read(Q)的所有事务的最大时间戳。

时间戳排序协议保证任何有冲突的rw操作按时间戳顺序执行。

对于指令read(Q)：

  • 若TS(Ti) < W-timestamp(Q)，则Ti需要读入的Q值已被覆盖，read操作被拒绝，Ti回滚
  • 若TS(Ti) >= W-timestamp(Q)，则执行read操作，R-timestamp(Q)更新为max(R-timestamp(Q), TS(Ti))

对于指令write(Q)：

  • 若TS(Ti) < R-timestamp(Q)，Q已经被读过了，Ti想要更新的值过时，write操作被拒绝，Ti回滚
  • 若TS(Ti) < W-timestamp(Q)，Q已经被写过了，write操作被拒绝，Ti回滚

其他情况write操作正常执行。

时间戳排序协议保证冲突可串行化

  • 冲突操作按时间戳的顺序来处理

保证无死锁

  • 不存在等待
  • 可能有事务饿死

可能产生不可恢复的调度

基于有效性检查的协议

有效性检查协议（适用于大部分只读事务的情况）要求每个事务Ti在其生命周期中按两个或三个阶段执行：

  • 读阶段：事务Ti的所有write操作都是对局部临时变量进行的
  • 有效性检查阶段：事务Ti进行有效性测试，判断是否可以在不违反可串行性的基础上执行write操作
  • 写阶段：如果Ti已通过有效性检查，则保存任何写操作结果的临时局部变量值被复制到数据库中。只读事务不进入此阶段。

每个事务必须按照上述顺序经历这些阶段，然而，并发执行的事务的三个阶段可以是交叉执行的。

每个事务Ti都有三个不同的时间戳：

  • Start(Ti)：事务Ti开始的时间
  • Validation(Ti)：事务Ti完成读阶段并开始其有效性检查的时间
  • Finish(Ti)：事务Ti完成写阶段的时间

利用时间戳Validation(Ti)的值，通过时间戳排序技术决定可串行性顺序，以增加并发性。

对于任何满足TS (Tk) < TS (Ti)的事务Tk必须满足下面两条件之一：

  • Finish(Tk) < Start(Ti)
  • Start(Ti) < Finish(Tk) < Validation(Ti) ，并且需保证Tk所写的数据项集与Ti所读数据项集不相交；即Tk的写操作不会影响到Ti的读操作。

有效性检查协议能够自动预防级联回滚，保证无死锁。

恢复系统

故障分类

事务故障：

  • 逻辑错误：由于某些内部条件而无法继续正常执行
  • 系统错误：系统进入一种不良状态，导致事务无法正常继续执行

系统崩溃：硬件故障，或者数据库软件、操作系统存在漏洞导致易失性存储器内容丢失，使得事务处理停止。

磁盘故障：由于磁头损坏或故障造成磁盘块上的内容丢失。毁坏是可探测的：磁盘驱动器用校验和来检测故障。

恢复机制

保证数据库一致性以及事务的原子性的算法称为恢复算法：

  • 在正常事务处理时采取措施，保证有足够的信息可用于故障恢复
  • 故障发生后采取措施，将数据库内容恢复到某个保证数据库一致性、事务原子性及持久性的状态

存储器类型：

  • 易失性存储器（volatile storage）：易失性存储器中信息在系统崩溃时通常无法保存下来。例子有主存和高速缓冲存储器
  • 非易失性存储器（nonvolatile storage）：非易失性存储器中的信息在系统崩溃时可以保存下来。这类存储器的例子有磁盘和磁带（但仍有可能丢失数据）
  • 稳定存储器（stable storage）：稳定存储器中的信息永不丢失

事务

  • 必须在第一次访问X之前执行read(X)
  • write(X)可以在事务被提交前的任意时刻执行

为保证原子性，我们必须在修改数据库本身之前，首先向稳定
存储器输出信息，描述要做的修改
目的：确保由中止事务所做的修改不会持久保存于数据库中，即回滚该中止事务

基于日志的恢复机制

日志保存于稳定存储器中，日志是日志记录的序列。它记录数据库中的所有更新活动。

立即修改模式允许在事务提交前，将未提交的事务更新至缓冲
区或磁盘

延迟修改模式直到事务提交时都没有更新到缓冲区/磁盘

  • 简化了恢复
  • 但是多了存储本地副本的开销

日志记录的更新必须在数据项被write（数据库修改）之前完
成。假设日志记录直接被写入稳定存储器

当事务将其关于提交的日志记录输出到稳定存储器时，该事务
被认为已提交。之前的所有日志记录必须都已经输出

事务提交时，由该事务执行的write操作结果可能仍在缓冲区，随后被输出

在并发事务中，所有事务共享一个磁盘缓冲区和日志

从故障中恢复时:
当日志是以下状态时，事务Ti需要进行undo操作
• 有日志 Ti, start
• 没有日志Ti, commit和Ti, abort
当日志是以下状态时，事务Ti需要进行redo操作
• 有日志 Ti, start
• 有日志Ti, commit或Ti, abort

囧：如果事务Ti 之前执行了undo操作，Ti abort被写入到日志，接着故障发生。为了从故障中恢复，Ti 要执行redo操作

这样的redo操作重新执行了原先的所有操作，包括重新存储旧值
• 称为重复历史
• 看起来很浪费，但是最大程度地简化了恢复

检查点

流线型恢复过程周期性地执行检查点

  1. 将当前位于主存的所有日志记录输出到稳定存储器上
  2. 将所有修改了的缓冲块输出到磁盘上
  3. 将一个日志记录< checkpoint L>输出到稳定存储器

执行检查点时，所有数据更新都停止

只有在L未提交/中止的事务或者在检查点后开始的事务需要redo或undo

第十五章 大数据与分布式数据库系统

大数据

大数据是大容量（Volume）、高流速（Velocity）、多样化（Variety）、高价值、真实的信息资产，它需要新的数据处理形式来增强决策、提升洞察力、优化处理过程。
5V特性：

  • Variety
  • Velocity
  • Volume
  • Value（高价值）
  • Veracity (真实性)

并行数据库架构

共享内存

处理器（或处理器内核）和磁盘可以访问公共内存。
优点是进程间高效通信，缺点是无法扩展到超过64-128个处理器内核。

共享内存系统可以有多个处理器，每个处理器都有自己的缓存级别。

共享磁盘

所有处理器都可以通过互连网络直接访问所有磁盘，但处理器具有私有内存存储器。
缺点：瓶颈现在出现在与磁盘子系统的互连网络。

无共享架构

节点由处理器、内存和一个或多个磁盘组成；通过互连网络进行所有通信，可以无干扰地扩展到数千个处理器。
缺点：通信成本和非本地磁盘访问；发送数据涉及两端的软件交互。

分层架构

结合共享内存、共享磁盘和无共享架构的特征

顶层是无共享架构
• 系统的每个节点都是共享内存系统
或者，顶层可以是共享磁盘系统
• 系统的每个节点都是共享内存系统

共享内存在内部看起来像无共享！

  • 每个处理器都可以直接访问自己的内存，间接（硬件级别）访问其余内存
  • 也称为非统一内存架构 (NUMA)

无共享——可以看起来像共享内存

  • 通过分布式虚拟内存抽象来降低此类系统编程的复杂性
  • 远程直接内存访问 (RDMA) 在无共享系统上提供非常低延迟的共享内存抽象。由于其非常低的延迟，通常在无限带宽（infiniband） 之上实施。但是粗心的编程会导致性能问题

分布式系统

数据分布在多台机器上。

分布式数据库：

  • 同构分布式数据库：所有站点上的相同软件/架构、数据可能分布于站点之间，提供单个数据库的视图（全局模式），隐藏分布细节
  • 异构分布式数据库：不同站点上的不同软件/架构，整合现有数据库以提供有用的功能

区分本地事务和全局事务

  • 本地事务访问启动事务的单个站点中的数据
  • 全局事务要么访问与启动事务的站点不同的站点中的数据，要么访问多个不同站点中的数据

数据集成的好处：

  • 共享数据——一个站点的用户能够访问其他站点的数据
  • 自治——每个站点都能够对本地存储的数据保持一定程度的控制

留下评论