数据库系统复习 知识点总结【数据库概念，关系数据库，数据库完整性定义，SQL简单操作概览，范式，数据依赖和公理系统，数据库设计概述，封锁并发，查询优化】

一、绪论

从保存游戏角色的信息到保存个人身份信息，从小型企业管理到电子商务、电子政务，甚至是高科技辅助制造等高科技行业，数据库都扮演者举足轻重的作用。

1.1 数据库系统概述

❗️ 4个基本概念

• 数据：描述事物的符号，其含义叫做数据的语义，数据必有其含义，否则只是一个符号，而不能描述事物
• 数据库：保存数据的仓库，有永久存储、有组织、可共享等特点（严格定义：数据库是长期存储在计算机上的有组织、可共享的大量数据集合，它的数据按照一定的数据结构组织、描述和管理，具有低冗余度、高独立性易扩展和供多用户共享的特点）
• 数据库管理系统：科学组织和存储数据，高效 获取维护数据的计算机基础软件（包含6点作用a数据定义；b数据组织、存储和管理c数据操纵；d数据库建立和维护；e数据库事物管理和运行管理；f其他扩展功能）
• 数据库系统：由数据库、数据库管理系统、数据库管理员、相应应用程序组成的存储、管理、维护和处理数据的系统（在通常情况下，一边简称为数据库）

❗️数据管理技术发展（数据库系统也是一种数据管理技术）：

• 人工管理阶段（特点：数据不保存、应用程序需要设计管理数据的部分、数据不共享、数据不独立）
• 文件系统阶段（特点：数据长期保存在计算机、统一由文件系统管理、数据共享性、独立性差）
• 数据库系统阶段（特点：见下）

❗️数据库系统特点：

• 整体数据结构化：数据的结构面向整个组织或企业，不仅仅像文件系统那样只对于一个应用；而且数据之间有联系，整体有结构（数据库系统与文件系统本质区别）
• 由数据库管理系统统一管理控制：数据库的高共享同时也带来了并发负担，由数据库管理系统解决（数据安全保护、数据完整性检测、并发控制、数据库恢复等），强大功能简化了使用者的负担
• 数据共享性高、冗余度低且易扩展：数据面向整体共享，不用保存重复的数据，而且其能够及时基于现有数据扩展功能，不用另外重新设计数据
• 数据独立性高：包括物理独立性，和应用程序可以保存在不同物理存储中；逻辑独立性，与应用程序的逻辑相互独立，可以自由更改，只需要保证对外接口不变

❗️综上所述：数据库是长期存储在计算机内部，有组织、大量、共享的数据集合，可供多个用户共享，有小冗余度和高数据独立性。数据库管理系统在数据库建立、运行使用和维护时对数据库进行统一控制，保证数据安全和完整性，以及提供并发控制和故障时恢复技术。

1.2 数据库数据模型

数据模型就是对现实世界的抽象，是数据库系统的核心和基础，可分为两类三种

• 概念模型：也叫信息模型，按照需要对现实事物进行概念化提取，用于设计数据库（比如学生模型（学号、姓名、年纪…）
• 逻辑模型和物理模型：
• • 逻辑模型：指数据库使用的数据结构设计的逻辑，用于数据库管理系统的实现——如层次模型，网状模型，关系模型等
  • 物理模型：数据最底层的抽象，表示数据在系统内部的表示方式和存取方法

现实世界——>抽象概念——>机器世界

再谈概念模型相关概念，在抽象过程中的一些术语：

• 实体：客观存在可分辨的事物，可以是具体的物体，也可以是概念和联系（如订货记录，选课关系）
• 实体型：同类实体的共同特征的提取（相当于Java的类）
• 实体集：就是同类实体的集合
• 属性：实体具有的某一特征（学生具有学号，姓名等特征）
• 码：唯一标识实体的属性集合
• 联系；一般指实体集合之间的联系（学生和课程产生选课联系）（有一对一、一对多、多对多）
• E-R图：概念模型的一种表示方法——实体-联系（Entity-Relationship）方法

逻辑模型：也叫数据模型，由数据结构（静态特征）、数据操作（动态特征）和完整性约束（约束条件）组成

• 数据结构：描述数据库的组成对象和联系
• 数据操作：指数据库中对象运行执行的操作（查询和更新）
• 数据完整性约束：数据的约束条件，后面再讲

常用数据模型：

• 层次模型：唯一无双亲节点（根节点），其余节点只有一个双亲节点的结构。
• • 优点（3）：结构简单清晰、查询效率高、良好的完整性支持
  • 缺点（4）：不适合表示多对多关系、有多个双亲的关系引入虚节点or冗余、查询子女节点需要通过双亲、结构严密命令过于程序化（就像写程序代码一样，不够灵活）
• 网状模型：允许多节点无双亲or多双亲节点的结构（就是网状结构…），还提供码约束、一对多保证、支持双亲和子女之间的约束条件
• • 优点（2）：更符合现实世界描述、性能良好存取效率高
  • 缺点（3）：结构复杂、需要嵌入高级语言中使用不易学、记录之间的联系与存取路径有关用户需要了解系统结构细节加重了开发负担
• 关系模型：二维表状的数据结构（关系为一张表、一行记录为一个元组、一列为一个属性、分量指一格数据）
• • 优点（3）：严谨的数学支持（关系数据理论）、结构单一易学易用、存取路径透明数据独立性高更安全且简化了开发工作
  • 缺点（2）：查询效率不够高、需要开发查询优化增大了数据库管理系统开发难度

1.3 数据库系统结构

• 型和值（相当于类和对象）——模式是数据库系统的型，描述了数据库全体数据的结构和特征，是相对稳定的；而实例则是模式的值，数据库的实际内容，是相对变动的——例子：定义数据库的模式为学生记录、课程记录和选课记录三种关系模式；该数据库的一个实例则可以是2019级所有学生和开设课程，以及他们的所有选课记录。

数据库三级结构、二级映射：

• 模式：对数据库中全体数据的逻辑结构和特征的描述
• 外模式：子模式or用户模式，模式数据对于用户的映射，是用户权限可见的局部数据逻辑结构和特征的描述
• 内模式：存储模式，表示数据在计算机上的物理存储结构和存储方式，是数据在计算机内部的组织方式
• 外模式/模式映射：每个外模式都是模式在其局部数据的映射，所以可以有多个映射，外模式不实际保存数据，程序的使用只与数据的外部映射相关联，实现了逻辑独立性
• 模式/内模式映射：唯一映射关系，实现了物理存储结构与数据记录的独立，实现了物理独立性

数据库模式结构需要确定全局的逻辑结构描述，即要先确定模式

内模式的选择决定数据物理存取的时间和空间效率

外模式的设计决定应用的使用性和可扩展性

三级模式和二级映射实现了数据与程序的独立性（逻辑和物理独立），使得数据的定义和应用程序分离，而是由数据库管理工具管理，简化了开发负担，和维护成本。

数据库系统组成：

• 硬件：大内存、大磁盘、高数据传输速率
• 软件：数据库管理软件、操纵系统、编译系统和开发工具
• 人员：数据库管理员、系统分析和数据库设计人员、程序开发者、用户（偶然用户、简单用户、复杂用户）

二、关系数据库

2.1关系数据结构和定义

关系的相关概念：

• 域：一组具有相同数据类型的值的集合
• 笛卡尔积：D₁ X D₂ X… X D_n={(d₁,d₂,…,d_n) | d_i 属于 D_i}
• n元组：含有n个属性的元素集合，(d₁,d₂,…,d_n)
• 分量：元素集合中的一个值，即d_i
• 多个属性做笛卡尔积所得的结果的子集可作为一个关系，实际上表示某个实体类有这些属性
• 关系的属性个数称为目或者度，为1叫一元关系，2叫二元关系
• 候选码：唯一标识一个元组（即一个实体）的最小属性集合
• 主码：从候选码中选取一个
• 主属性：注意是候选码中的属性，只要在一个候选码中就为主属性
• 非主属性：不在任何一个候选码中
• 全码：全部属性一起作为候选码

关系2条限定和6条性质：

• 关系为有限集合

• 关系每个列添加属性名来取消属性列的顺序

• 列同质（即同一列的分量来自同一域，同数据类型）

• 不同列可同质，但要给与不同属性名

• 列无序

• 行无序

• 行的候选码不能有重复的，否则不为候选码

• 分量取原子，不可再分（规范化条件基础，见后范式详解）

关系模式：关系的型，对关系的抽象描述

• 表示为R（U，D，DOM，F）
• R为关系名，U为属性集合，D为属性域，DOM为属性向域的映像集合，F为属性依赖关系
• 一般用R（U）或 R（U，F）表示即可

关系数据库：所有关系的集合，数据库内容

关系数据库模式：关系模式的集合，数据库内容格式的定义

2.2关系的完整性

关系模式有三大完整性约束：

• 实体完整性规则：主属性不能为空，由于主属性的相应集合（候选码）唯一标识实体，若为空则造成不能标识的情况，违背了实体能被区别的原则
• 参照完整性规则：在关系R中的非主属性组R_S对应关系S中的主码K_S，则R_S是R的外码，R是参照关系，S是被参照关系，参照完整性规定——外码要么取空，要么被参照关系存在该对照，该值存在
• 用户定义完整性：根据需求和实际情况定义的规则，比如学生成绩属性范围在0~100

2.3关系操作和关系代数

关系数据语言分类：关系代数和关系演算、具有二者优点的SQL（结构化查询语言）

关系代数运算符（操作不好解释，详情见书）：

• 并、差、笛卡尔、选择、投影、交、连接、除

连接：

• 等值连接：按照某属性相等做连接，使用“=”运算符
• 自然连接：特殊等值连接，有相同属性列，相同属性列分量相同自动连接
• 外连接：将舍弃的元组在对应位置添上NULL，左外连接，召回运算符左边的舍弃的元组，右外连接同理

除运算：

• 象集：x在R上的象集，结果为包含x的元组，不包含x属性列
• 除运算：R除以S结果为T，包含所有在R但不在S中的属性和属性的值，T和S的所有组合都在R中
• • 运算方法：R（X，Y），S（Y，Z）这样的形式
  • 结果为 x_i 属于X在R的象集，象集包含S在Y上的投影，保存 x_i 作为结果的一个元组

三、关系数据库标准语言SQL

3.1 SQL概述

SQL标准从1986年起经过多年增加，目前多达3777页，因此没有一个数据库系统能够支持SQL标准的所有概念和特性；而且软件商对SQL指令集还进行了不同程度的修改扩充

SQL的特点：

• 综合统一：（结合了模式数据定义语言、外模式数据定义语言、数据存储语言、数据操作语言）
• 高度非过程化：只要提出做什么，而无须指明怎么做，因此无须了解存储路径
• 面向集合的操作方式
• 同一种语法的多种使用：嵌入高级语言，单独使用
• 语言简洁，易学易用

SQL基本概念：

• 视图：相当于外模式，是基本表信息的部分展示
• 基本表：相当于模式，定义了数据的内容和数据之间的逻辑
• 存储文件：保存在计算机的实体文件，之间的逻辑构成内模式，对最终用户隐藏

3.2 数据定义

关键字：

• create（创建）、drop（删除）、alter（修改）
• schema（模式）、table（表）、view（视图）、index（索引）

相关SQL语句格式：

• 模式定义与删除

• 基本表定义与修改、删除

• 视图的定义与查询、删除

• 索引定义与删除

3.3 数据更新

• 插入数据
• 修改数据
• 删除数据

3.4 数据查询

• 单表查询
• 连接查询
• 嵌套查询
• 集合查询
• 派生表查询
• SELECT 语句格式

四、数据库完整性

数据库的完整性是指数据的正确性和相容性

• 正确性：符合现实世界语义、反应当前实际情况
• 相容性：同一对象在不同关系表中的数据符合逻辑

4.1 实体完整性

定义实体完整性：

#表级定义
PRIMARY KEY(C1,C2)
#或者，列级定义
NAME VARCHAR() PRIMARY KEY

完整性检测通过插入or修改时搜素表中是否有重复主码，若有——执行违约处理——拒绝执行

4.1 参照完整性

定义参照完整性：

#表级定义
FOREIGN KEY(NAME) REFERENCES TABLE_NAME(R_NAME)
#外码NAME，参照TABLE_NAME表中的R_NAME属性

操作导致违约：

• 参照表修改外码值、插入一个元组导致找不到对应的外码（在被参照表中没有对应的码）——拒绝执行
• 被参照表中修改被参照的码、删除元组导致参照表找不到外码——拒绝执行/级联修改、删除/设置为空

拒绝执行：当违约操作时，拒绝执行该操作（NO ACTION）

级联操作：当违约时，将参照表中使用该参照的元组删除/修改为相应值（CASCADE）

设置为空：违约时，将参照表中的使用该参照元素的元组的外码设置为NULL

#违约定义（不设置默认为拒绝执行）
FOREIGN KEY(NAME) REFERENCES TABLE_NAME(R_NAME)
		ON UPDATE CASCADE
		ON DELETE CASCADE，
#当删除违约时级联删除，修改违约时级联修改

FOREIGN KEY(NAME) REFERENCES TABLE_NAME(R_NAME)
		ON DELETE NO ACTION
		ON UPDATE CASCADE，
#当删除违约时拒绝执行，修改违约时级联修改

4.1 用户定义完整性

用户定义完整性：

#非空
NAME CHAR(10) NOT NULL,
#不重复，主码定义
ID INT(8) UNIQUE PRIMARY KEY,
#CHECK中自定义约束
SALARY INT(32) CHECK(SALARY >=1000),
#
SEX CHAR(2),
#定义表级约束，要么性别为女，要么姓名不能以‘Ms.’开头
CHECK(SEX='女' OR NAME NOT LIKE 'Ms.')

违约时拒绝执行

4.2 完整性约束命名子句

就是给上面提到的表级约束命名，不改变 其功能，只是更好方便修改删除

#定义表中有NAME为名的约束，CHECK()可替换为UNIQUE，PRIMARY KEY，FOREIGN等其他表集约束
CONSTRAINT NAME CHECK()

#删除表中NAME为名的约束
ALTER TABLE T_NAME
		DROP CONSTRAINT NAME;
		
#添加名字为NAME_2的新约束
ALTER TABLE T_NAME
		ADD CONSTRAINT NAME_2 CHECK(SEX IN ('男','女'));

五、关系数据理论

5.1 依赖的概念

将关系模式简单表示为一个三元组R<U,F>——关系模式名<属性集，数据依赖>

• F：数据依赖是表示关系内部属性与属性之间的一种约束关系
• 依赖中最重要的两种——函数依赖和多值依赖

函数依赖：X，Y作为U的子集，当X相等时，Y必相等，不存在一个X的值对应两个Y值的情况，称X–>Y，X函数决定Y，或者Y依赖X

• 平凡函数依赖：X无疑能够函数决定X的子集，这种依赖叫做平凡函数依赖
• 非平凡函数依赖：X–>Y，且X不包含Y（我们基本上只考虑这种依赖关系，平凡的函数依赖价值不大）
• 相互依赖：X–>Y且Y–>X的情况，即X <–> Y
• 完全函数依赖：X–>Y且X的任何一个真子集不能函数决定Y；可表示为 X-^F->Y
• 部分函数依赖：X–>Y，且X的一个真子集也能决定Y；X-^P->Y

使用依赖定义码：

• 候选码：K为R<U，F>的候选码当且仅当 K-^F->U，即通过K能够完全有效（最小集合）区别元组
• 超码：候选码的超集，S-^P->U包含候选码
• 主属性：在某一个候选码中的属性
• 非主属性，非码属性：不在任何一组候选码中
• 全码：特殊情况，整个属性组U作为候选码，称为全码
• 外码：在另一个关系中的码

关系模式码的标识：用下划线标识码，虚线标识外码

5.2 规范化

粗糙的设计关系，比如把整个关系模式不经拆分作为一个关系：比如如下关系

U={Sno,Sdept,Mname,Cno,Grade}

F={Sno->Sdept,Sdept->Mname,(Sno,Cno)->Grade}

只存在一张关系表，标识着学生选课记录，学生年纪和系相关信息如上，如此设计将会导致：

• 数据冗余：重复保存系主任名称，系名称
• 更新异常：修改系主任名称时数据库开销很大
• 插入异常：无法保存一个系的信息，如果没有学生选课，因为码为学号和课程号
• 删除异常：删除选课记录可能导致系相关信息丢失

在实际情况中，系信息和学生选课记录不应该放在一起，但数据库设计也不能仅仅依靠实际经验，这样的情况需要规范的定义和处理，这就是规范化的作用

规范化：通过根据关系属性间的依赖情况判断关系是否有一些不合适的性质，通过拆分变成更高要求的范式的过程叫做规范化（严格的说：将低级范式通过模式分解转化为若干高级范式的关系模式的集合的过程叫规范化）

5.3 范式

范式：关系模式满足的要求，简写为NF

• 1NF：最低要求，最小原子不可再分性（是一个关系就满足1NF）

• 2NF：在1NF基础上，消除了非主属性对码的部分依赖，即拆分后要实现所有非主属性完全依赖于码

• 

• 3NF：在2NF基础上，消除了非主属性对码的传递依赖，即现在非主属性不仅要完全依赖码还要直接依赖码，上面图中，Mame直接依赖于Sdept，而Sdept直接依赖于Sno(码)，而Mname传递依赖于Sno，可拆分如下：

• 

• BCNF：对3NF的补充，简单的表示为每一个决定因素都包含码（非主属性完全函数依赖于每一个码，主属性对于不包含它的码也是完全函数依赖，没有任何一个属性完全函数依赖于非码的任何一组属性）

5.4 数据依赖的公理系统

Armstrong公理系统：定义了依赖的相关推导基础

• 蕴含：在R<U，F>中对于关系模式R实例的任意一个关系r，如果满足X–>Y那么称F逻辑蕴含X–>Y
• 自反性：U包含X，X包含Y，必有X–>Y，且F逻辑蕴含X–>Y
• 增广性：X–>Y被F蕴含，U包含Z属性组，那么XZ–>YZ也被F蕴含
• 传递性：X–>Y，Y不能决定X，Y–>Z都被F蕴含，那么X–>Z也被F蕴含

推导得出的常用规则：

• 合并规则：X–>Y, X–>Z推导得X–>YZ
• 伪传递规则：X–>Y，WY–>Z，推导得XW–>Z
• 分解规则：X–>Y，Y包含Z，推导得X–>Z

由F逻辑蕴含的全体函数依赖称为F的闭包，F⁺，即全部U能够推导出来的函数依赖

• 有效性：从F推导出来的函数依赖都在F⁺中
• 完备性：F⁺中每一个函数依赖都可以由F中的函数依赖推导得出

X⁺_F称为U的属性子集X关于函数依赖集F的闭包，即是X根据F能够推导出来的所有依赖X的属性的集合

• 有X–>Y，即Y存在于X⁺_F中

等价概念：G⁺==F⁺，即两个函数依赖集能推导出的闭包相同，即G和F等价

F的极小函数依赖集满足以下条件：

• F中的函数依赖右部只有一个属性
• 不存在X–>A，但是F和F-{X–>A}等价（即能够被其他推导出来的函数依赖不需要，除去了传递函数依赖）
• 不存在X–>A，X有真子集Z使得F-{X–>A}U{{Z–>A}}与F等价（即不存在不完全函数依赖，应该用完全函数依赖取代）

六、数据库设计

6.1 数据库设计过程

• 六阶段
  1. 需求分析（基础）
     • 行为：需求收集和分析
     • 数据：数据字典：数据项、数据结构、数据流、数据存储
     • 处理：数据流图和判定树、数据字典：处理过程
  2. 概念结构设计（关键）****——形成概念模式
     • 行为：依据需求进行综合、归纳与抽象
     • 数据：概念模型：E-R图
     • 处理：系统说明书：方案、概图、数据流图
  3. 逻辑结构设计——形成逻辑模式（模式）
     • 行为：设计逻辑结构（转换规则）、数据模型优化（优化方法）
     • 数据：逻辑模式（某种数据模型）
     • 处理：系统结构图（模块结构）
  4. 物理结构设计——生成内模式
     • 行为：设计物理结构、评价设计性能预测（不满意→④或③）
     • 数据：存储安排、方法选择、存取路径建立
     • 处理：模块设计、IPO表
  5. 数据库实施
     • 行为：物理实现、试运行（不满意→④）
     • 数据：建立模式、装入数据、数据库试运行
     • 处理：编码、编译链接、测试
  6. 数据库运行和维护
     • 行为：用户方的使用和维护
     • 数据：性能监测、转储/恢复、数据库重组和重构
     • 处理：新旧系统转换、运行、维护

6.2 需求分析（略）

6.3 概念设计和逻辑结构设计

E-R图设计

• 实体：用框图表示
• 联系：用菱形表示
• 属性：用椭圆形表示
• 联系：直接用无方向箭头连接起来

E-R图向关系模型转化

每个实体可单独设置为一个关系模式

联系根据1对1、1对多、多对多可分别嵌入实体中或者单独实现为一个关系模式

七、查询优化

7.1查询树启发式优化

步骤：

• 选择运算尽可能先做（减少中间结果）
• 投影运算和选择运算同时进行（避免重复扫描）
• 投影同前后的双目运算符结合起来（避免重复扫描）
• 某些选择同前面要执行的笛卡尔积结合起来成为连接运算（减少中间结果）
• 找出公共子表达式（避免重复计算）

实例：

如下SQL语句：

SELECT sname,jname,pname FROM S,P,J,SPJ 
	WHERE S.sno=SPJ.sno AND P.pno=SPJ.pno AND J.jno=SPJ.jno 　　　
		AND qty>150 AND color='红' AND J.city='天津'; 

请画出其关系代数表达的初始查询语法树和优化后的语法树

八、事务处理技术（恢复和并发控制）

8.1事务和日志

事务：指用户定义的一个数据库操作序列，这些操作要么全做，要么全不做，是一个不可分割的工作单位

特性：

• 原子性
• 一致性
• 隔离性
• 持续性

特性可能被破坏的原因：

• 多个事务并行，不同事务交叉操作
• 事务在运行过程中被强制中断

日志：用来记录事务对数据库更新操作的文件（登记内容——事务的开始，事务的结束，事务所有的更新操作）

• 事务标识
• 操作类型（插入、修改或删除）
• 操作对象
• 更新前的旧值（插入操作此项为空）
• 更新后的新值（删除操作此项为空）

日志的作用：

• 事务故障和系统故障恢复使用
• 动态转储方式需要建立日志，以备日后有效恢复
• 静态转储也可以建立日志，数据库重新更新后利用日志复现相关操作

日志记录规则

• 登记的次序按并发事务执行的时间次序
• 必须先写日志后操作数据库

8.2故障和恢复策略

三种故障及其恢复策略：

事务故障：

• 指事物在运行至正常终止前被强制终止，这时候需要恢复子系统根据日志文件撤销该事务部分完成的操作（由于事务需要全做，要么不做）
• 恢复策略：撤销——通过日志文件反向查找该事务的更新操作，然后执行逆操作（即将更新前的值写入数据库），直到查找到该事务的开始标记

系统故障（软故障）：

• 指系统由于某些原因导致停止运转，使得系统需要重新启动——导致了某些事物未做完，某些事物提交了但是还没有完全写入数据库
• 恢复策略：撤销+重做——对于为完成的事物，反向查找日志文件，从后往前依次对该事物的更新操作执行逆操作，将其更新前的值写回数据库；对于提交的操作，正向查找，对于每个事务重新执行日志文件登记的操作，即将更新后的值写回数据库

介质故障（硬故障）：

• 指外存故障导致数据库信息丢失
• 恢复策略：重装+重做——装入最新保存的数据库后备副本，是数据库恢复到最近一次转储时的一致性状态；然后载入相应的日志副本，重做已完成的事务。扫描日志文件，找出故障发生前已提交的事务，记入重做队列，正向扫描，对标记的事务的更新操作进行重做

带有检查点的恢复策略

• 传统日志的问题
  • 搜索整个日志耗时太多
  • 重做存在大量重复（可能已经写入数据库的事务操作也被重做）
• 格式扩展
  • 日志中增加checkpoint记录
    • 建立检查点时正在执行的事务清单
    • 这些事务最近的一个日志记录的地址
  • 建立“重新开始”文件：检查点列表及其在日志文件中的位置
• 日志维护（此动作周期执行）
  • 缓冲区中所有日志内容写入磁盘
  • 日志文件中写入一检查点记录
  • 缓冲区中所有数据记录写入磁盘
  • 在重新开始文件中登记这个检查点
• 恢复方法
  1. 从重新开始文件中找到最后登记的一个检查点的日志文件中的位置
  2. 有日志文件中的该检查点记录得到该检查点时刻所有正在进行的事务清单：Active List
     • 建立UNDO LIST队列，初始化为Active list中的所有事务
     • 建立REDO LIST队列，初始化为空
  3. 从检查点开始正向扫描日志
     • 如有新开始的事务Ti，则放入UNDO LIST队列中
     • 如有提交的事务Tj，则从UNDO LIST中删除该事务，放入REDO LIST队列中
  4. 对UNDO LIST中的所有事务UNDO；对REDO LIST中的所有事务REDO

8.3 并发控制

单处理机系统：事务的并发实际上是并行事务的并行操作交通轮流运行

同时并发方式：在多处理机系统中，每个处理机运行一个事务，多个事务的并发操作同时进行

冲突操作：指不同事务对同一个数据的读写操作或写写操作，有可能导致数据不一致性的操作

并发操作带来的数据不一致性问题：

• 丢失修改：两个事务T1和T2同时读入同一数据并修改，后一个提交覆盖前一个提交造成修改丢失
• 不可重复读：当T1读取数据后，T2事务对数据进行修改导致T1再次读取的数据不一致（修改、删除、添加三种情况）
• 读脏数据：T1修改某一数据写回后，被T2读取，但是由于某些原因导致T1撤销操作，T2此时这个数据叫脏数据（与数据库不一致，应该被撤销的数据）

并发控制目的：使用正确的方式调度并发操作，使一个用户事务的执行不受其他事务的干扰，避免了数据的不一致性

主要技术有：封锁、时间戳、乐观控制法、多版本并发控制

可串行性：

• 可串行性调度：多个事务的并发执行是正确的，当且仅当其结果与按某一次序串行性的执行这些事务时的结果相同，即称这种调度策略为可串行化调度

8.4 封锁

封锁：事务T在对某个数据对象进行操作之前向系统发出请求对其加锁，加锁后事务T对该对象有了一定的控制，在释放锁之前，其他事务不能更新此数据对象

• 排他锁：又叫写锁，X锁，当事务T对数据对象加了X锁后，其他事务不能对其加锁，直到T释放，保证了除T之外的其他事务不能读取和修改加了X锁的数据对象
• 共享锁：又叫读锁，S锁，当事务T对数据对象加了S锁，则事务对象T可以读取但不能修改该对象，其他事务只能同时对该数据对象加S锁，直到数据对象上的S锁被释放。保证了该数据对象不会在读取期间被修改

两段锁协议：指所有事务必须分两个阶段对数据项加锁和解锁

• 在对任何数据进行读写之前，首先要申请和获取该对象的封锁
• 在释放一个封锁之后，事务不在申请和获得其他封锁

当所有并发执行的事务均遵守两段锁协议，那么这些事务的并发控制都是可串行化的，可通过交换两个不冲突的操作次序转化；注意两段锁协议是可串行化的充分条件，且两段锁协议的事务也可能发生死锁

多粒度封锁

• 封锁粒度：封锁对象的大小（比如封锁属性值，封锁属性组，封锁整个数据库）
• 封锁粒度大，并发程度小，系统开销小；反之，并发程度大，系统开销大

多粒度树：从数据库为根节点->多个关系->元组->…的树形结构

多粒度封锁协议允许对多粒度树中的节点单独加锁，同时意味着对该节点的子节点也加相同锁

• 显式封锁：该数据对象被直接加锁
• 隐式封锁：该数据对象的上级节点被加锁而使得该对象加锁
• 每次加锁时需要检测三种可能冲突——显式封锁冲突，上级隐式封锁冲突，下级显式封锁冲突（过于麻烦，引入了意向锁）

意向锁：当一个节点被加意向锁——该节点的下级节点正处于被加锁中，在给节点加锁时，需要给上级节点加意向锁

• IS锁：表示后裔节点需要被加S（共享锁）锁
• IX锁：表示后裔节点需要被加X（排他锁）锁
• SIX锁：表示对该节点加S锁，再对其加IX锁（其后裔节点需要被加X锁）；表示要读该对象，同时需要修改其下部分数据

锁的相容性表：