数据结构复习

发表于 分类于 本文字数： 8.7k 阅读时长 ≈ 32 分钟


第一章 绪论

1.1数据库系统概论

  1. 数据是数据库中存储的基本对象。
  2. 数据的定义：描述事物的符号记录
  3. 数据库定义：长期存储在计算机内、有组织、可共享的大量数据的集合。
  4. 数据库的数据按一定的数据模型组织、描述和存储，具有较小的冗余度、较高的数据独立性和易扩展性，并可为各种用户共享。
  5. 数据库管理系统作用：在数据库建立、运用和维护时对数据库进行统一控制，以保证数据的完整性和安全性，并在多用户同时使用时进行并发控制，在发生故障时对数据库进行恢复。
  6. 数据库管理系统用途：科学地组织和存储数据、高效地获取和维护数据。
  7. 数据库主要功能：
    • 数据定义功能
    • 数据组织、存储和管理
    • 数据操纵功能：实现数据库的基本操作：查询、插入、删除和修改等。
    • 数据库的事务管理和运行管理
    • 数据库的建立和维护功能
    • 其他功能：数据库管理系统与其他软件系统的通信，与另一个数据库关系系统或文件系统的数据转换功能
  8. 数据库系统：由数据库、数据库管理系统、应用程序和数据库管理员组成的存储、管理、处理和维护数据的系统。
  9. 数据库管理技术经历了：人工管理、文件系统、数据库系统三个阶段。
    • 人工管理阶段
      • 数据不保存：用于科学计算，不需要长期存储
      • 应用程序管理数据：应用规定数据的逻辑结构和设计物理结构，程序员负担很重
      • 数据无共享，冗余度极大：一组数据智能对应一个程序，多个程序涉及相同的数据必须各自定义，产生大量冗余
      • 数据不独立，完全依赖于程序：数据的逻辑结构或物理结构发生变化后，必须对程序做相应更改
    • 文件系统
      • 数据可以长期保存
      • 由文件系统管理数据：利用“按文件名访问，按记录进行存取”的管理技术，实现了记录内的结构性。
      • 数据共享性差，冗余度大：文件仍然面向应用，不能共享相同的数据，造成冗余；相同的数据重复存储容易造成数据的不一致性。
      • 数据独立性差：文件系统的文件是为某一特定应用服务的，文件的逻辑结构是针对具体的应用来设计和优化的，因此想对文件内的数据增加一些新的应用会很困难。
    • 数据库系统阶段
      • 参照二维表的设计结构，组织结构相同。
      • 共享性高，冗余度小
      • 具有高度的物理独立性和一定的逻辑独立性
      • 整体结构化，用数据模型描述（二维表）
      • 由数据库管理系统提供数据安全性、完整性、并发控制和恢复能力
  10. 数据库系统的特点：
    • 数据结构化：实现整体数据的结构化，数据库系统与文件系统的本质区别
      • 不再针对某一应用，而是面向整个组织；数据的内部和整体均为结构化，数据之间具有联系。
    • 数据的共享性高，冗余地且易扩充
      • 数据共享可以大大减少数据冗余，节约存储空间，避免数据之间的不相容性和不一致性。
      • 有结构的数据可以被多个应用共享使用，使得数据库弹性大，异于扩充。
    • 数据独立性高
      • 物理独立性：用户的应用程序与数据库中的数据的物理存储是相互独立的。（使得数据的物理存储改变时应用不用改变）
      • 逻辑独立性：用户的应用程序和数据库的逻辑结构是相互独立的。（数据的逻辑结构改变时程序也不用改变）
    • 数据由数据库管理系统统一管理和控制
      • 数据的安全性保护
      • 数据的完整性检查
      • 并发控制
      • 数据库恢复

1.2数据模型

  1. 两类数据模型
    • 第一类：概念模型
    • 第二类：逻辑模型和物理模型（DBMS）
  2. 实体之间的联系：一对一、一对多、多对多
  3. 数据模型三要素：由数据结构、数据操作和数据的完整性约束组成
  4. 数据库领域中主要的逻辑数据模型：层次、网状、关系模型
  5. 数据的操作：增、删、改、查
  6. 数据的完整性约束条件：实体、参照、用户自定义完整性
  7. 什么是关系型数据模型？从用户观点看，关系模型由一组关系组成，每个关系的数据结构是一张规范化的二维表。
  8. 关系模型的由缺点：
    • 优点
      • 关系模型与格式化模型不同，他是建立在严格的数学概念的基础上的
      • 关系模型的概念单一，无论实体还是实体间的联系都可以用关系表示。数据结构简单、清晰，用户易懂易用
      • 关系模式的存取路径对用户透明，从而具有更高的数据独立性，更好的安全保密性，简化了程序员的工作和数据库开发建立的工作
    • 缺点
      • 查询效率不如格式化数据模型，数据库管理系统必须对用户的查询请求进行优化，增加了开发数据库管理系统的难度

1.3数据库系统的结构

  1. 数据库系统模式的概念：数据模型中有“型（type）”和“值（value）”的概念
  2. 数据库系统的三级模式结构：外模式、模式、内模式
  3. 如何理解模式？模式也称逻辑模式，是数据库中全体数据的逻辑结构和特征的描述，是所有用户数据的公共数据视图。是基本的逻辑表结构
  4. 如何理解外模式？外模式也称子模式或用户模式，它是数据库用户能够看见和使用的局部数据的逻辑结构和特征的描述，是数据库用户的数据视图，是与某一应用有关的数据的逻辑表示。
  5. 如何理解内模式？内模式也称存储模式，一个数据库只能有一个内模式，它是数据物理结构和存储方式的描述，是数据在数据库内部的组织方式。表结构的实现（物理存储的数据库）
  6. 数据库的二级映像功能与数据独立性
    • 外模式/模式映像：当模式改变时，数据库管理员对映像做相应更改，使得外模式保持不变，保证了数据与程序的逻辑独立性
    • 模式/内模式映像：当数据库的存储模式结构改变时，数据库管理员对映像做相应改变，使得模式保持不变，保证了数据与程序的物理独立性

第二章 关系数据库

2.1 关系数据结构及形式化定义

  1. 域：一组具有相同数据类型的值的集合
  2. 笛卡尔积：所有可能的集合组合，是一个固定关系的有序集合，元组次序不能任意交换。
  3. 关系：关系是笛卡尔积的子集合
    • 关系是一张二维表，表的每一行表示一个元组（记录）
    • 每一列对应一个域，域可以相同，必须对每列起一个名字，称为属性
    • n目关系必有n个属性
  4. 候选码：关系中某一属性组的值能唯一地标识一个元组，而其子集不能的属性组
    • 一个关系有多个候选码，则选其中一个为主码
    • 候选码的诸属性称为主属性，其他的为非主属性/非码属性
    • 关系模式中所有的属性都是这个关系模式的候选码，称为全码
  5. 关系可以有三种类型：基本关系（基本表或基表）、查询表和视图表。
    • 基本表是实际存在的表，是实际存储数据的逻辑表示
    • 查询表是查询结果对应的表
    • 视图表是虚表，不对应实际存在的数据
  6. 基本关系具有6条性质
    1. 无限关系在数据库系统中是无意义的
    2. 通过为关系的每一列附加一个属性名取消关系属性的有序性
    3. 列的顺序无所谓，可任意交换
    4. 任意两个元组的候选码不能取相同的值（主键，相同则不能为候选码）
    5. 分量必须取原子值，每一个分量都是不可分的数据项（第一范式原则）
    6. 行的顺序无所谓，可任意交换
  7. 关系表中不允许表中有表
  8. 表是关系数据的逻辑模型

2.2 关系操作

  1. 基本的关系操作：选择、投影、并、差、笛卡尔积
  2. 关系操作的特点：集合操作方式，即一次一集合的方式。非关系数据模型的数据操作方法为一次一记录

2.3 关系的完整性（结合第五章）

  1. 关系模型有三类完整性约束：实体完整性、参照完整性、用户定义的完整性
    • 实体完整性和参照完整性是关系模型必须满足的完整性约束，被称作关系的两个不变性。
    • 用户定义的完整性是应用领域需要遵循的约束条件，体现了具体领域中的语义约束。
  2. 实体完整性规则：若属性A是基本关系R的主属性，则A不能取空值
  3. 外码：F是基本关系R的一个/组属性，但不是R的码，K是S的主码，若F与K相对应，则F是R的外码。R为参照关系，S为被参照关系。
  4. 参照完整性规则：属性F是基本关系R的外码，与基本关系S的主码K相对应，则R中每个元组在F上的值必须为：
    • 空值（F的每个属性值均为空）
    • 等于S中某个元组的主码值

2.4 关系代数

  1. （网络找题）传统集合运算：二目运算，并、差、交、笛卡尔积
  2. （网络找题）专门的关系运算：选择、投影、连接、除运算（不考）

第三章 关系数据库标准语言SQL

3.1 SQL概述

  1. SQl特点
    • 综合统一
    • 高度非过程化
    • 面向集合的操作方式，采用集合操作方式，一次一集合
    • 以同一种语法结构提供多种使用方式
    • 语言简洁，易学易用

3.3 数据定义 （SQL语句）

SQL语句进行创建、修改、删除

3.4 数据查询（SQL语句）

单表查询

3.5 数据更新（SQL语句）

UPDATE、INSERT、DELETE

3.6 空值的处理 （SQL语句）

NULL的使用

3.7 视图 （SQL语句）

视图的作用：

  1. 视图能够简化用户的操作
  2. 视图使用户能够以多种角度看待同一数据
  3. 视图对重构数据库提供了一定程度的逻辑独立性
  4. 视图能够对机密数据提供安全保护：对不同用户定义不同的视图，设置查询和修改视图的权限
  5. 适当利用视图可以更清晰的表达查询

第四章 数据库安全性

4.1 数据库安全性概述

  1. 数据库的安全性是指保护数据库以防不合法使用所造成的数据泄露、更改或破坏
  2. 数据库的不安全因素
    • 非授权用户对数据库的恶意存取和破坏
    • 数据库中重要或敏感的数据被泄露
    • 安全环境的脆弱性
  3. TCSEC/TDI(紫皮书 定义了数据库管理系统的设计与实现中需要满足和用以进行安全性级别评估的标准
    • 从四个方面描述安全性级别划分的指标：安全策略、责任、保证和文档
  4. TCSEC/TDI的7级安全级别划分
    • 常用的商用安全软件级别：B1/C2

4.2 数据库安全性控制

  1. C2级别的数据库管理系统支持自主存取控制，B1级别的数据库管理系统支持强制存取控制。
  2. 自主存取控制：用户对于不同的数据库对象有不同的存取权限，不同的用户对同一对象也有不同的权限，而且用户还可以将拥有的存取权限转授给其他用户，因此自主存取控制比较灵活
    • GRANT和REVOKE语句
    • 权限授予为级联形式，同时不可循环授权
    • 缺陷：可能存在数据的“无意识”泄露
      • 甲对乙授权，乙就可以将数据备份，获得自身权限（主人）的副本，在不征得甲同意的情况下进行传播。
      • 仅仅通过对数据的存取权限来进行安全控制，而数据本身无安全性标记
  3. 强制存取控制：每个数据库的对象被标以一定的密级，每一个用户也被授予某一个级别的许可证。对于任意一个对象，只有具有合法许可证的用户才可以存取，因此强制存取控制比较严格
    • 数据库管理系统的所有实体被分为主体和客体
      • 主体是系统的活动实体，即包括数据库关系系统所管理的实际用户，也包括代表用户的各个进程
      • 客体是系统中的被动实体，是受主体操作的，包括文件、基本表、索引、视图等
    • 对于主体和客体，数据库管理系统为他们的每个实例指派一个敏感度标记
      • 绝密（TS）、机密（S）、可信（C）、公开（P）。密级的次序为：TS>=S>=C>=P
      • 主体的敏感度标记为许可证级别，客体的敏感度标记为密级
    • 强制存取控制机制就是通过对比主体的敏感度和客体的敏感度标记，确定主体能否存取客体
    • 是对数据本身的密级标记，无论数据如何复制，也只有符合对应密级要求的主体才能存取，提高了更高级别的安全性
  4. 强制存取控制中，主体对任何客体的存取必须遵循以下规则
    1. 仅当主体的许可证级别大于等于客体密级时，主体能够读取相应客体
    2. 仅当主体的许可证级别小于等于客体级别时，主体才能写相应客体
      • 违反会造成数据从高流向低，造成数据泄漏（TS主体把TS的客体修改为P，导致泄漏）

4.3 视图机制（SQL语句）

视图的定义和查询

第五章 数据库完整性

为实现数据库的完整性，数据库必须能够实现如下功能：

  1. 提供定义完整性约束条件的机制
  2. 提供完整性检查的方法
  3. 进行违约处理

5.1 实体完整性

  1. 实体完整性检查：
    • 检查主码值是否唯一，如果不唯一拒绝插入或修改
    • 检查主码的各个属性是否为空，若为空拒绝插入或修改
      • 检查方法：全表扫描（唯一方法）
        • 方式：建立索引，排序后折半查找

5.2 参照完整性

  1. 可能破坏参照完整性的操作以及违约处理
被参照表（Student） 参照表（SC） 违约处理
可能破坏参照完整性 插入元组 拒绝
可能破坏参照完整性 修改外码值 拒绝
删除元组 可能破坏参照完整性 拒绝（默认）/级联删除/设为空值
修改主码值 可能破坏参照完整性 拒绝（默认）/级联删除/设为空值
  1. 参照关系属性的定义有不同的要求
    • 如果外码的属性为非主码，可以设置默认为Null
    • 如果外码的属性为主码，必须有取值

5.3 用户定义的完整性 （SQL语句）

  1. 属性上的约束条件
    1. 列值非空 NOT NULL
    2. 列值唯一 UNIQUE
    3. 检查列值是否满足某一个条件（CHECK语句）

5.4 完整性约束命名子句 （SQL语句）

CONSTRAINT

第六章 关系数据理论

6.1 问题的提出

  1. 数据依赖：一个关系内部属性与属性之间的一种约束关系，通过属性间值的相等与否体现出的数据间的相关联系
    1. 多值依赖
    2. 函数依赖

      建立一个描述学校教务的数据库，该数据库涉区的对象包括学生的学号(Sno)、所在系（Sdept)、系主任姓名（Mname)、課程号（Cno）和成绩（Grade）。假设用一个单一的关系模式 Student 来表示，则该关系模式的属性集合为
      U= {Sno, Sdept, Mname, Cno, Grade}
      现实世界的已知事实（语义）告诉我们：

    3. 一个系有若干学生，但一个学生只属于一个系。
    4. 一个系只有一名（正职）负责人。
    5. 一个学生可以选修多门课程，每门课程有若干学生选修。
    6. 每个学生学习每一门课程有一个成绩。
      于是得到属性组U上的一组函数依赖F={Sno->Sdept,Sdept->Sname,(Sno,Cno)->Grade}

      合成一张大表后存在的问题：

    7. 数据冗余（大量的重复数据）
    8. 更新异常（更新系主任后必须更新所有学生信息）
    9. 插入异常（新建立的系若没有学生则无法插入）
    10. 删除异常（学生毕业后系的信息也无法保留）
      一个好的模式应当不会发生更新、插入、删除异常，并尽可能减少数据冗余

6.2 规范化

  1. 函数依赖：R（U）是属性集U上的关系模式，X，Y为U的子集，对于R（U）可能的关系r，r不存在两个可能的元组在X上属性值相等，在Y上不等的，则X函数确定Y或Y函数依赖于X。

  2. 评价数据库设计




  1. 规范化小结
    1. 1NF->2NF：消除非主属性对码的部分函数依赖
    2. 2NF->3NF：消除非主属性对码的传递函数依赖
    3. 3NF->BCNF：消除主属性对码的部分和传递函数依赖

第七章 数据库设计

7.1 数据库设计概述

  1. 数据库设计的6个阶段
    • 需求分析
    • 概念结构设计（E—R图）
    • 逻辑结构设计（规则）
    • 物理结构设计（SQL？）
    • 数据库实施（SQL？）
    • 数据库运行和维护

7.3 概念结构设计

  1. E-R图的画法

7.4 逻辑结构设计

  1. E-R图向关系模型的转换
    • 一个1:1联系可以转换为一个独立的关系模式，也可以与任意一端对应的关系模式合并
    • 一个1:n联系可以转换为一个独立的关系模式，也可以与n端对应的关系模式合并
    • 一个n:m联系转换为一个关系模式
    • 三个或三个以上实体间的一个多元联系可以转换为一个关系模式
    • 具有相同码的关系模式可以合并
      实例

第九章 关系查询处理和查询优化

9.3 代数优化

  1. 查询树的启发式优化
    1. 选择运算应尽可能先做（结合代数运算，需先计算选择）
    2. 把投影运算和选择运算同时进行
    3. 把投影同起前或后的双目运算结合起来
    4. 把某些选择同在它前面要执行的笛卡尔积结合起来成为一个选择运算

第十章 数据库恢复技术

10.1 事务的基本概念

  1. 事务是用户定义的一个数据库操作序列，这些操作要么全做，要不全不做，是一个不可分割的工作单位
  2. 事务和程序是两个概念，一般一个程序包含多个事务
  3. 事务的ACID特性：原子性（A）、一致性（C）、隔离性（I）、持续性（D）。ACD为数据库恢复的要求。
    • 原子性：事务是数据库的逻辑工作单位，事务中的操作要么全做要么都不做
    • 一致性：数据库必须由一个一致性状态变为另一个一致性状态（事务的执行完成或回滚完成等状态）
    • 隔离性：一个事务的执行不能被其他事务干扰
    • 持续性/永久性：一个事务一旦提交，他对数据库中的数据的改变应该是永久性的。

COMMIT表示提交事务的所有操作，将事务对数据库的更新写回到磁盘上的物理数据库中；ROLLBACK表示回滚，将事务对数据库的所有已完成操作全部撤销，回滚到事务刚开始的状态。

10.2 数据库恢复概述

  1. 数据库系统所采用的恢复技术是否行之有效，不仅对系统的可靠程度起决定性作用，而且对系统的运行效率也有很大影响，是衡量系统性能优劣的重要指标。（所以要定期备份）
  2. 数据库管理系统必须具有把数据库从错误状态恢复到某一已知的正确状态的功能，就是数据库的恢复

10.3 故障的种类

  1. 事务内部的故障
    • 事务内部的故障不影响其他事务的执行，更多的是非预期的，不能由应用程序处理。

BEGIN TRANSACTION
读账户甲的余额为x；
x=x-a; //a转账金额
IF(x<0) THEN
{打印‘金额不足，不能转账’；
ROLLBACK；}
ELSE
{写回x；读账户乙的余额y；
y=y+a；
写回y；
COMMIT；}
这段程序中若账户甲余额不足，程序可以发现并让事务滚回，撤销已做的修改，是数据恢复到正确状态。
事务故障意味着事务没有达到预期的终点（COMMIT或者显示ROLLBACK），因此数据库可能处于不正确状态。恢复程序要在不影响其他事务的运行情况下，强行滚回该事务，即撤销该事务已经做出的任何对数据库的修改，这类恢复操作称为事务撤销（UNDO）。 此操作为自主操作。

事务撤销的恢复步骤：
1. 反向扫描文件日志（从后往前扫描），查找该事务的更新操作
2、对该事务的更新操作执行逆操作，即将日志记录中“更新前的值”写入数据库
3、继续反向扫描日志文件，查找该事务的其他更新操作，并做同样处理。
4、如此处理下去，直至读到此事务的开始标记，事务故障恢复就完成了。

  1. 系统故障：造成系统停止运转的任何时间，使得系统要重新启动

    • 影响并发执行的所有操作，所有事务都非正常中止
    • 恢复子系统必须在系统重启时让所有非正常终止的事务回滚（UNDO），已完成但仍未写入磁盘的事务全部重做（REDO）
    • 检查点处恢复
      1. 正向扫描日志文件（将在故障发生前已经提交的事务加入重做（REDO）队列，这些事务既有begin transaction记录，也有commit记录；将在故障发生时未完成的事务加入撤销（Undo）队列，这些事务中只有begin transaction记录，无相应的commit记录）
      2. 对撤销（Undo）队列事务进行撤销（Undo）处理（1.反向扫描日志文件，对每个undo事务的更新操作进行逆操作；2.将日志记录中“更新前的值”写入数据库）
      3. 对重做（Redo）队列事务进行重做（Redo）处理（正向扫描日志文件，对每个REDO事务重新执行登记的操作；将日志记录中“更新后的值”写入数据库）

  2. 介质故障：系统故障通常称为软故障，此类为硬故障，如磁盘损坏等。

    • 不考虑检查点，采取备份+日志文件恢复，同时日志文件中修改的新值要重新覆写一遍

      (1） 装入最新的数据库后备副本（离故障发生时刻最近的转储副本），使数据库恢复到最近一次转储时的一致性状态。
      (2） 转入相应的日志文件副本，重做已完成的事务。即首先扫描日志文件，找出故障发生时已提交的事物的标识，将其记入重做队列；然后正向扫描日志文件，对重做队列中的所有事务进行重做处理。即将日志记录中“更新后的值”写入数据库。

  3. 计算机病毒，参考介质故障

  4. 各类故障对数据库的影响：数据库本身被损坏、数据库没有被破坏但数据可能不正确

  5. 恢复的基本原理：冗余（备份+日志文件）

10.4 恢复的实现技术

  1. 建立冗余数据最常用的技术是数据转储和登记日志文件。

  2. 转储可分为静态转储和动态转储

    • 静态转储是在系统无运行事务时进行转储，转储期间不允许对数据库进行任何存取、修改活动
      • 降低数据库的可用性
    • 动态转储是转储期间允许对数据库进行存取或修改。
      • 必须把转储期间各事务对数据库的修改记录，建立日志文件，便于备份完成后进行恢复

  3. 转储也可分为增量转储和海量转储

    • 海量转储是每次转储所有数据库
    • 增量转储是只转储上一次转储后更新的数据

      动态海量转储、动态增量转储、静态海量转储、静态增量转储

  4. 每个日志记录的内容

    • 操作的类型
    • 操作对象
    • 更新前的旧值
    • 更新后的新值

      日志重写覆盖的意义：回写数据库存在更新延迟（写入磁盘的速度原小于内存），提交后可能存在尚未写入磁盘的情况。

10.6 具有检查点的恢复技术

  1. 建立检查点的意义：改善恢复效率，系统强制对该点之前的事务进行提交，避免在恢复时对已执行完毕的事务重复提交。只针对系统故障
  2. 检查点记录的内容：
    • 建立检查点时所有正在执行的事务
    • 这些事务最近一个日志记录的地址
  3. 系统使用检查点方法进行恢复的步骤是：
    1. 从重新开始文件中找到最后一个检查点记录在日志文件中的地址，由该地址在日志文件中找到最后一个检查点记录。
    2. 由该检查点记录得到检查点建立时刻所有正在执行的事务清单 ACTIVE-LIST。
      这里建立两个事务队列：
      •UNDO-LIST：需要执行 UNDO 操作的事务集合；
      •REDO-LIST：需要执行 REDO 操作的事务集合。
      把ACTIVE-LIST 暂时放入 UNDO-LIST 队列，REDO队列暂为空。
    3. 从检查点开始正向扫描日志文件。
      1. 如有新开始的事务T,把T暂时放入UNDO-LIST 队列;
      2. 如有提交的事务J,把J从UNDO-LIST队列移到 REDO-LIST队列；直到日志文件结束。
    4. 对 UNDO-LIST 中的每个事务执行 UNDO 操作，对 REDO-LIST 中的每个事务执行REDO 操作。

第十一章 并发控制

并发是指在一个时间段内有多个进程在执行。
并行指的是在同一时刻有多个进程在同时执行。

  1. 什么是并发？ 是指一个时间段中有几个事务都处于已启动运行到运行完毕之间，且这几个事务都是在同一个处理机上运行，但任一个时刻点上只有一个事务在处理机上运行。**
  2. 并发的要求：一致性、隔离性

11.1 并发控制概述

  1. 事务是并发控制的基本单位
  2. 并发操作带来的问题
    1. 丢失修改：两个事务T1和T2读入同一数据并修改，先后提交了结果，前提交的数据会丢失
    2. 不可重复读：
      1. 事务T1读取某一数据后，T2对其进行修改，当T1再次读取时得到了与第一次不同的结果
      2. 事务T1按一定条件读取某些数据记录，T2删除了其中一部分，当T1再次按相同条件读取数据时会发现某些记录神秘消失了
      3. 事务T1按一定条件读取某些数据记录，T2插入了一些记录，当T1再次按相同条件读取数据时发现多了一些记录
    3. 读“脏”数据：事务T1修改某一数据并将其写回磁盘，T2读取同一数据后，T1因为某种原因被撤销，T2读取的数据就与数据库中的不一致。

11.2 封锁

  1. 基本的封锁类型：排他锁（X）、共享锁（S）
    1. 排他锁（写锁）：若事务T对数据对象A加上X锁，则只允许T读取和修改A，其他任何事务都不能再对A加任何类型的锁，直到T释放A
    2. 共享锁（读锁）：T对A加S锁，则T可以读A但不能修改A，其他事务只能在对A加S锁，而不能加X锁，直到T释放A为止

11.3 封锁协议

  1. 封锁协议：在运用X和S锁时需要遵守的规则，用于解决并发操作的3个问题
    1. 一级封锁协议：事务T在修改数据R之前必须对其加X锁，直到事务结束才释放。可防止丢失修改，只针对读数据。
    2. 二级封锁协议：在一级封锁协议的基础上增加事务T在读取数据R之前必须先对其加S锁，读完后释放。除防止丢失修改外，还可进一步防止读“脏”数据，由于读完数据后立即释放S，不能保证可重复读。
    3. 三级封锁协议：在一级封锁协议的基础上增加事务T在读取数据R之前必须先对事务加S锁，直到事务结束释放，解决了并发操作的3个问题。

11.4 活锁和死锁

  1. 死锁：事务T1封锁了数据R1，T2封锁了R2，T1又申请封锁R2，造成T1和T2两个事务永远不能结束
  2. 活锁：T1封锁了R1，T2申请R1，T3也申请R1后得到系统批准，T2继续等待，可能造成永远等待。
  3. 预防死锁的方法
    1. 一次封锁法：每个事务必须一次将所有要使用的数据全部加锁。扩大了封锁的范围，降低了系统的并发度
    2. 顺序封锁法：预先对数据对象规定一个封锁顺序，所有事务按照这个顺序实施封锁。要求动态处理，实现困难，成本很高，同时事务的随机性高，难以按预先规定实施
  4. 数据库解决死锁的方法：选择一个处理死锁代价最小的事务，将其撤销，释放此事务所有的锁，使得其他事务可以继续运行下去。

11.6 两段锁协议

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

    1. 对任何数据进行读、写操作之前，首先要申请并获得该数据的封锁
    2. 在释放一个封锁后，事务不再申请和获得任何其他封锁

    即事务分两个阶段，第一阶段是获得封锁，也称扩展过程，这个阶段事务可以申请任何数据的任何类型的锁，但不能释放锁；第二阶段锁释放封锁，也称收缩过程，在这个阶段，事务可以释放任何数据项上任何类型的锁，但是不能再申请封锁。
    若事务遵守两段锁协议，则对这些事务的任何并发调度策略都是可串行化的，可以进行可串行化调度。

  2. 事务遵循两段锁协议是可串行化调度的充分条件，而非必要条件。

  3. 两段锁协议和一次封锁法的区别：一次封锁法要求事务必须一次将要使用的数据全部加锁，否则不能继续执行。因此一次封锁法遵循两段锁协议。但是两段锁协议并不要求事务必须一次将所有要使用的数据加锁，因此遵守两段锁协议的事务可能发生死锁。目的是保证了并发调度的正确性。