数据库期末复习知识点整理。

第一章 基本概念

1. 概念

• 数据：描述现实世界各种事物的可以识别的符号
• 数据永久存储和处理的一般性基本操作，包括数据组织、存储和更新、检索等称为数据管理，并形成数据管理专门的技术——数据管理技术
• 数据库技术是一种数据管理技术，按照某种数据结构对数据进行组织后，存储在计算机的二级存储中，并可以提供数据共享操作
• 数据库技术的软件实现就是数据库管理系统DBMS
• 数据库系统是基于数据库管理系统建立的具有特定数据处理功能的系统

1. 发展过程

• 人工管理阶段
  • 数据不在计算机上保存
  • 没有软件系统对数据进行管理，程序规定数据的逻辑结构和物理结构，数据与程序不具有独立性
  • 基本没有文件概念，数据组织方式必须由程序员自行设计
  • 一组数据对应一个程序，数据是面向应用的，程序间不能共享数据
• 文件系统阶段
  • 数据以文件形式保留在外存上
  • 文件多样化
  • 数据的存取基本上以记录为单位
  • 程序和数据有一定的独立性
  • 文件与应用程序基本上是一一对应，数据共享性差，冗余度大
  • 文件分散，相互独立，数据冗余度大，数据和程序缺乏独立性
  • 存储空间浪费
  • 容易造成数据的不一致性
  • 数据维护难度大
  • 程序维护工程量大
• 数据库系统阶段
  • 突破文件系统分散管理的弱点，实现对数据的集中控制，统一管理，数据是“集成的”和“共享的”
    • “集成的”是指把特定应用环境中各种应用相关的数据及数据之间的联系，全部地、集中地并按照一定结构形式进行存储
    • “共享的”是指数据可为多个不同的用户所操作
  • 数据库技术要解决的基本问题和技术
    • 集成数据的表示：数据模型
    • 统一管理下的数据共享：数据独立性
  • 数据库系统中的核心软件——数据库管理系统DBMS

1. 数据库数据管理特点

• 面向全组织的复杂数据结构
  • 在描述数据时，不仅描述数据本身，还要描述数据之间的联系，使整个组织的数据结构化
  • 数据结构化是数据库主要特征之一，是数据库与文件系统的根本区别
• 数据冗余度小，易于扩充
• 具有较高的数据和程序的独立性
  • 数据的物理独立性：数据的存储结构（物理结构）改变时，数据的逻辑结构可以不变，从而应用程序也不必发生改变
  • 数据的逻辑独立性：数据的逻辑结构改变时，应用程序可以不变
  • 数据库系统提供了两方面的映像（转换）功能，支持数据独立性实现：
    • 数据的存储结构与逻辑结构之间的映像——模式/内模式映像，实现数据的物理独立性
    • 数据的全局逻辑结构与某类应用所涉及的局部逻辑结构之间的映像——外模式/模式映像，实现数据的逻辑独立性
• 统一的数据控制功能
  • 数据的安全性控制：保护数据以防止不合法的使用所造成的数据的泄密和破坏
  • 数据的完整性控制：指数据的正确性和相容性
  • 并发控制：对多用户的并发操作进行控制、协调，保护数据的完整性
  • 数据库恢复：将数据库从错误状态恢复到某一已知的正确状态
• 数据的最小存取单位是数据项

1. 数据模型的层次

• 概念模型
  • 用于信息世界建模，是现实世界到信息世界的抽象，是用户和数据库设计人员进行交流的语言
  • 也称信息模型，基于信息世界的主要概念，表达应用中的各种语义（信息）
  • 具有较强的语义表达能力，能够方便、直接表达应用中的各种语义
  • 概念模型应该简单、清晰、易于理解
  • 概念模型最常用的表示方法：实体—联系方法（E-R法）
  • 基本概念：实体、属性、码、域、实体型、联系（具有名称、类型、属性）
• 数据模型
  • 用于机器世界，按计算机系统的观点对数据建模，包括如下两个子层次
    • 逻辑模型：按应用系统的观点对数据建模，是DBMS的核心
    • 物理模型：描述数据在存储介质上的存储结构和存取方法，由DBMS实现
  • 机器世界的数据模型常指逻辑模型
  • 数据模型是严格定义的概念集合，这些概念精确地描述系统汇总数据的静态特性、动态特性和完整性约束

1. 数据模型三要素

• 数据结构
  • 由描述数据对象以及对象之间联系的一组概念组成
  • 包括描述对象的类型、内容、性质的概念，描述对象之间联系的概念
  • 是数据静态特性的描述
  • 数据结构是刻画数据模型最重要的方面，通常按照数据结构的类型来命名数据模型
• 数据操作
  • 对数据库中各种数据对象的实例允许执行的操作集合，包括操作及操作规则
  • 定义操作的确切含义、操作符号、操作规则及操作语言
  • 是数据动态特性的描述
  • 数据库主要有检索和更新（增删改）两大类操作
• 完整性约束
  • 是完整性规则的集合，是给定的数据模型中数据及其联系所有的制约和依存规则，用以保证数据的正确、相容

1. 数据模型的分类

• 数据模型用来抽象和表示现实世界中的数据和信息
• 经典的数据模型主要有：层次模型、网状模型、关系模型
• 各种数据模型之间的根本区别在于数据之间联系的表示方式不同
  • 层次模型：树结构
    • 数据库系统中最早出现的数据模型
    • 结构简单，易于实现
    • 支持的联系种类太少没只能直接表示二元一对多联系
    • 数据操纵不方便，子结点的存取只能通过父结点来进行
  • 网状模型：图结构
    • 表达的联系种类丰富，结构复杂
  • 关系模型：二维表
    • 用关系描述实体及实体间的联系，这种描述一致性使数据结构大大简化，概念简单
    • 可直接表示多对多联系
    • 关系必须是规范化关系，即每个分类是不可分的数据项，不许表中套表
    • 关系模型是建立在数学概念基础上，有较强的理论基础

1. 数据独立性

• 数据独立性是指应用程序与数据结构之间互相独立的关系
• 实现方法：数据库结构多层次抽象，建立层次间映射/对应关系，具有三级模式、两级映像的结构特征
• 模式
  • 也称为逻辑模式、概念模式，是数据库中全体数据的逻辑结构和特性的描述，是所有用户的公共数据视图
  • 是三级模式的核心，不涉及数据物理存储细节，与具体的应用程序与编程语言无关
  • 具体定义数据的数据结构、数据安全性、完整性要求
  • 数据库系统提供模式描述语言进行模式定义，用模式DDL写出的一个数据库逻辑定义的全部语句，称为某个数据库的模式
• 外模式
  • 也称为子模式或用户模式，是个别用户的数据视图，即与某一应用有关的数据的逻辑表示
  • 通常是模式的子集，不同应用的外模式可以相互覆盖，一个应用只能启用一个外模式
  • 数据库系统提供外模式描述语言定义外模式，外模式DDL和用户选用的程序设计语言具有相容的语法
• 内模式
  • 也称为存储模式，是数据在数据库系统内部的表示，即对数据的物理结构和存储方式的描述
  • 内模式通常用内模式数据描述语言来描述和定义
• 两级映像
  • 外模式/模式映像定义某个外模式与模式之间的对应关系，当模式改变时，外模式/模式映像做相应改变，可以保证外模式不变，对应数据的逻辑独立性
  • 模式/内模式映像定义数据逻辑结构与存储结构之间的对应关系，当内模式改变时，模式/内模式映像做相应修改，使得模式保持不变，对应数据的物理独立性

1. 三级模式结构优点

• 保证数据的独立性
• 有利于数据共享：从模式产生不同的外模式，外模式间可相互覆盖
• 简化用户接口，方便用户使用，用户只按照外模式操作，无需了解数据库的总体逻辑结构与物理存储结构
• 有利于数据的安全保密：应用程序只能操作其对应的外模式

1. DBMS 的主要功能

• DBMS 是数据库系统的核心软件，在操作系统支持下工作
• 数据库定义功能
  • 提供DDL语言描述外模式、模式、内模式
  • 模式翻译程序把源模式翻译成目标模式，存入数据字典中
• 数据存取功能：提供DML语言对数据库进行增删改查
• 数据库运行管理：并发控制、存取控制、完整性约束条件检查和执行，日志组织和管理，事务管理和自动恢复
• 数据组织、存储和管理：用户数据、索引、数据字典的组织、存储和管理，包括文件结构、存取方式、数据之间联系的实现等
• 数据库的建立和维护功能：数据的装入、转换，数据库的转储、恢复、性能监视和分析等

1. DBMS 的组成

• 语言编译处理程序
• 系统运行控制程序：包括系统总控、存取控制、并发控制、完整性控制、保密性控制、数据存取和更新、通信控制等程序
• 系统建立和维护程序：数据装入、数据库系统恢复、性能监督、工作日志等程序
• 数据字典：也称为数据目录或系统目录，由一系列表组成，存储着数据库中有关信息的当前描述，包括数据库的三级模式、用户名表、用户权限等信息

1. 数据库管理员职责（DBA）

• 建库方面：确定模式、外模式、存储结构、存取策略、负责数据的整理和装入
• 用库方面：定义完整性约束条件，规定数据的保密级别、用户权限，监督和控制数据库的运行情况，制定后院和恢复策略，负责故障恢复
• 改进方面
  • 监督分析系统的性能（空间利用率、处理效率）
  • 数据库重组织，物理上重组织，以提高性能
  • 数据库重构造，设计上较大改动，模式和内模式修改

第二章 关系数据库

1. 关系模型

• 域：一组具有相同数据类型值的集合
• 关系数据模型中的关系必须是有限集合
• 每一分量必须是不可再分的数据，满足这一条件的关系称作满足第一范式（1NF）的
• 实体及实体之间的联系均用单一的数据结构——关系来表示
• 关系是关系模式在某一时刻的状态或内容，关系模式是相对稳定的，关系是动态的，是随时间不断变化的
• 关系模式的集合构成关系数据库模式——关系数据库的型
• 关系的集合则构成具体的关系数据库——关系数据库的值
• 语义约束
  • 实体完整性：要有属性或属性组合作为主码，主码值不可为空或部分为空
  • 参照完整性：如果关系R的外部码Fk与关系S的主码Pk相对应，则R中的每一个元组的Fk值或者等于S中某个元组的Pk值，或者为空值
  • 用户定义完整性：用户针对具体的应用环境定义的完整性的约束条件
  • 实体完整性和参照完整性是关系模型必须支持的约束条件
• 关系数据操作方式的特点是集合操作，一次一集合方式，操作的对象和结果都是集合
• 关系数据操作的基础是关系运算，关系运算方式有两种：代数方式、逻辑方式
  • 关系代数（代数方式）
    • 常规结合运算：并、差、交、广义笛卡尔积
    • 特有关系运算：选择、投影、连接、自然连接、求商
    • 传统的集合运算是二目运算。除笛卡儿积外，要求参加运算的两个关系必须是同类关系，即两个关系具有相同的度，且相对应的属性值必须取自同一个域
  • 关系演算（逻辑方式）：把谓词演算应用到关系运算中就是关系演算
    • 元组关系演算：以元组为变量，基本结构是元组演算表达式
    • 域关系演算：以域为变量
• 三种关系运算相互等价，可转换

1. 安全性约束

• 关系运算中把不产生无限关系和无穷验证的运算称为安全运算，其运算表达式称为安全表达式，对其所采取的限制称为安全约束
• 关系代数是安全运算，关系演算则不一定是，所以对关系演算要进行安全约束
• 在关系演算中，通常采用的安全性约束方法是对关系演算定义一个有限的符号集，使关系演算的运算结果及中间结果所有产生的关系及其元组的各个分量都必须属于符号集
• 经过安全约束后的三类关系运算的表达能力是等价的，可以相互转换

1. 关系数据语言

• 从功能上分类
  • 数据定义语言（DDL）：包括模式DDL、外模式DDL、内模式DDL
  • 数据操纵语言（DML）：四种基本操作，检索、插入、修改、删除，有联机交互方式和宿主语言方式
    • 联机交互方式下的DML称为自舍式语言，可独立使用，适用于终端直接查询
    • 宿主语言方式下的DML称为嵌入式语言，依附于宿主语言，是嵌入高级语言的程序中，以实现数据操作
  • 数据控制语言（DCL）：完成数据库的安全性控制、完整性控制、并发控制等
• 特点
  • 一体化：将数据的定义、查询、更新、控制等功能融为一体，只给用户提供一种称之为查询语言的语言，便于用户学习和使用
  • 非过程化：用户只需提出干什么，而怎么干由DBMS解决，所以语言操作简单，易学，易用
  • 面向集合的存取方式：操作对象是一个或多个关系，操作的结果也是一个新关系
  • 既可独立使用又可与主语言嵌套使用
• 优越性根源
  • 关系模型采用了最简单、最规范的数据结构，这使DML大大简化
  • 关系数据语言是建立在关系运算的数学基础上，可实现关系的垂直方向和水平方向的任意分割和组装操作，使得关系语言可随机地构造出用户需要的各种各样的新关系
• 关系数据语言的核心是查询，所以又称为查询语言，而查询往往表示成一个关系运算表达式，因此关系运算是设计关系数据语言的基础，关系运算的分类也决定了关系语言的分类

1. 关系模型的优缺点

• 优点
  • 建立在严格数学概念基础上，有严格的设计理论
  • 概念单一，实体和联系都用关系描述，查询操作结果也是一个关系，保证了数据操作语言的一致性
  • 数据结构简单直观、易理解、语言表达简洁
  • 存取路径对用户透明，数据独立性更高，安全保密性更好，简化了程序员和数据库开发建立的工作
• 缺点
  • 由于存取路径对用户透明，查询效率不如层次、网状数据模型
  • 为了提高性能，需要查询优化，增加数据库管理系统的开发难度

第三章 标准语言SQL

1. 特点

• 综合统一
• 高度非过程化
• 面向集合的操作方式
• 以同一种语法结构提供两种使用方式
• 语言简捷，易学易用

1. 基本表与导出表

• 基本表：是实际存在的，每个表在存储中可用一个存储文件来表示
• 导出表：是从基本表导出的表，有视图和快照
  • 视图是一个虚表，即视图所对应的数据不实际存储在数据库中，只在数据库的数据字典中存储视图的定义
  • 视图一经定义就可以和基本表一样进行查询等操纵，也可以用来定义新的视图

1. SQL语句

• WHERE子句中可以包含另一个查询块，该查询块称为子查询或嵌套查询，包含子查询的语句称为外部查询
• 子查询按照与外部查询的联系不同，分为普通子查询和相关子查询
  • 普通子查询：与外部查询无关，可单独执行得一组值
  • 相关子查询：把外查询的列值作为检索条件的条件值
• 并、差、交检索的操作对象必须是相容的，是同类关系，即必须有相同数量的属性列，且相应属性列的域也必须相同
• 库函数只能在SELECT子句以及HAVING子句中出现
• LIKE查询的列名必须为字符型或变长字符型
• 字符串常量包含两个特殊符号
  • %代表任意序列的0个或多个字符
  • _代表任意单个字符

1. 视图

• 视图消解：
  • DBMS执行对视图的查询时，从数据字典中取出视图的定义，把定义中的子查询和用户的查询结合起来，转换成等价的对基本表的查询，然后再执行修正的查询，这一转换过程称为视图消解
• 视图作用
  • 是用户能够以多种角度看待同一数据
  • 提供了一定程度的逻辑独立性
  • 能够对数据提供安全保护

1. SQL数据控制功能

• 定义完整性约束条件
• 支持事务操作
• 提供安全控制功能：授权、收回权限

1. 空值

• 空值是不知道、不存在或无意义的值，用NULL表示
• 空值与另一个值的算术运算结果为NULL，与另一个值的比较运算结果为UNKNOWN
• 在检索操作中，只有使WHERE和HAVING子句中的条件为TRUE的元组才被输出

1. 嵌入式SQL

• 嵌入式SQL把SQL语句嵌入到高级语言中
• 嵌入式SQL把SQL的最佳特性与程序设计语言的最佳特性结合起来，使SQL功能更强，灵活性更强
• 对于嵌入式SQL，DBMS多采用预编译的方法进行处理
  • 把嵌入在程序中的SQL语句翻译为高级语言源码，然后按主语言的通常方式进行编译、连接形成可执行代码
• 动态SQL允许在程序运行过程中临时组装SQL语句

第四章 数据库保护

1. 数据库安全性

• 保护数据库以防止不合法的使用所造成的数据泄漏、更改和破坏，包含两个方面的含义
  • 向授权用户提供可靠的信息服务
  • 拒绝对数据的非授权存取访问请求，保证数据的可用性、完整性和一致性，进而保护数据库所有者和使用者的合法权益
• 控制方法
  • 用户标识与认证：系统提供的最外层安全保护措施，用户名和口令
  • 存取控制：确保合法用户按照指定的权限使用DBMS和访问数据，而非法用户或不具有相关权限的用户则不能
    • 包括用户权限定义和合法权限检查
    • 用户权限定义和合法权限检查机制一起组成了DBMS的安全子系统
  • 审计：把用户对数据库的所有操作都自动记录下来放入审计日志中
  • 数据加密：防止数据库中数据在存储和传输中失密
  • 视图机制：为不同的用户定义不同的视图，可以将用户对数据的访问限制在一定的范围内

1. 存取控制方法分类

• 自主存取控制
  • 用户对于不同的数据对象具有不同的存取权限，不同的用户对同一对象也有不同的权限，而且用户还可以将其拥有的权限转授给其他用户
  • 角色是一组相关权限的集合，使用角色控制用户对数据对象的权限，可以大大简化权限的管理
    • 用户级权限：是数据库管理员为每个用户授予的特定权限，是对用户使用整个数据库权限的限定，与整个数据库相关，与数据库中具体的关系无关
    • 关系级权限：是数据库管理员或数据库对象的拥有者为用户授予的与关系或视图有关的权限，这种权限是对用户使用关系和视图权限的限定
• 强制存取控制
  • 每一个数据对象被标以一定的密级，每一个用户也被授予某一个级别的许可证，对于任一个对象，只有具有合法许可证的用户才可以存取
  • 全部实体分为实体和客体两类，为每个实例指定一个敏感度标记
  • 主体的敏感度标记称为许可证级别，客体的敏感度标记称为密级
    • 主体的许可证级别大于等于客体的密级时，该主体才能读取相应的客体
    • 主体的许可证级别等于客体的密级时，该主体才能写相应的客体

1. 数据库完整性

• 指数据的正确性和相容性
  • 正确性：数据应具有合法的类型，并在有效的取值范围之内
  • 相容性：同一对象在不同关系中的数据是符合逻辑的
• 数据库能否保持完整性关系到数据库系统是否能够真实的反映现实世界
• 施加在数据库数据之上的语义约束条件称为数据库完整性的约束条件

1. 完整性约束分类

• 完整性约束条件作用的对象可以是列、元组、关系三种
  • 列约束：列的类型、取值范围、精度等约束条件
  • 元组约束：元组中各个字段间联系的约束
  • 关系约束：若干元组间、关系之间的联系的约束
• 关系模型中的三种完整性约束条件
  • 实体完整性：关系约束，一个关系元组之间的
  • 参照完整性：关系约束，关系之间联系的对象
  • 用户自定义完整性：列约束、元组约束
• 静态约束与动态约束
  • 静态约束是数据库在每一确定状态数据对象所应满足的约束条件，它是反映数据库状态合理性的约束
  • 动态约束是指从一种状态转变为另一种状态时，新旧值之间所应满足的约束条件，它是反映数据库状态变迁的约束

1. 完整性控制

• 定义功能
• 检查功能，按完整性检查的时机分类
  • 立即执行约束：在一条语句执行完后立即进行完整性约束的检查，否则系统将拒绝该操作
  • 延迟执行约束：在整个用户事务执行完毕后，再进行完整性约束的检查，否则系统将拒绝整个事务
• 违约响应

1. 触发器

• 触发器是用户定义在关系上的一类由事件驱动的特殊过程
• 对于用户对表的更新操作，系统自动激活相应触发器，执行完整性控制

第五章 关系数据理论

1. 数据依赖

• 一个关系内部属性值之间相互依赖又相互制约的关系
• 函数依赖：对于X的每个确定值，Y有唯一的值与之对应，则X函数确定Y，Y函数依赖于X，X称为决定因素
  • 一对一联系、一对多联系、多对多联系
  • Y包含于X，那么X依赖于Y是平凡的函数依赖
• 完全函数依赖
• 传递函数依赖

1. 关系键

• 设K是关系中的属性或属性组合，如果K函数确定关系，则K是关系的候选码
• 若候选码对于一个，则选定其中的一个作为主码
  • 唯一性：唯一地标识关系中的元组
  • 最小性：若抽去主码中的任意一属性，则主码将失去标识的唯一性
• 包含在任意一个候选码中的属性，叫主属性
• 不包含在任何码中的属性称为非主属性
• 外部码：关系模式R中属性或属性组X并非R的码，但X是另一个关系模式的码，则称X是R的外码

1. 公理系统

• 从F中的函数依赖能够推出X->Y，则称F逻辑蕴含X->Y
• 在关系模式中，为F所逻辑蕴含的函数依赖的全体称为F的闭包
• 自反律、增广律、传递律
• 合并规则、伪传递规则、分解规则
• Armstrong公理系统是有效的，完备的
• 有效性：指由F出发根据Armstrong公理推导出来的每个函数依赖一定在F所蕴含的函数依赖的全体中
• 完备性：F所蕴含的函数依赖的全体中的每一个函数依赖，必定可以由F根据Armstrong公理导出

1. 极小函数依赖集

• 函数依赖集F和G，如果F和G的闭包一致，则F和G等价，称F覆盖G，G也覆盖F
• 极小函数依赖集：右部单属性化、没有多余的函数依赖，每个函数依赖左部没有多余属性

1. 范式

• 如果一个关系满足某个特定的约束集，则称它属于某种特定的范式
• 满足最低要求约束的称为第一范式，简称1NF
• 当一个关系只包含原子值这一约束时，称为1NF
• 满足原子值这一约束条件的关系称为规范化关系，简称范式，在关系数据库中，都是规范化的关系
• 一个低一级范式的关系模式，通过模式分解可以转换为若干个高级范式的关系模式的结合，这一过程称为规范化（1NF、2NF、3NF、BCNF、4NF、5NF）
• 2NF
  • 1NF，每个非主属性完全依赖于码
  • 如果关系的全体属性都是主属性，那么一定是2NF
  • 从1NF中，消除非主属性对码的部分依赖，则可获得2NF关系
  • 在2NF中，允许主属性部分函数依赖于码
  • 插入异常有所改善，但还是存在
  • 删除异常仍然存在
  • 数据冗余得到一定改善
• 3NF
  • 2NF，每个非主属性都不传递依赖于任何码
  • 没有限制主属性对码的部分与传递函数依赖，如果发生这些依赖，仍可能存在异常
  • 插入异常、删除异常、更新异常、数据冗余
• BCNF
  • 1NF，对于每个非平凡的函数依赖，左边必有码
  • 所有非主属性都完全函数依赖于每个候选码
  • 所有主属性都完全依赖于每个不包含它的候选码
  • 没有任何属性完全函数依赖于非码的任何一组属性
• 4NF
  • 多值依赖：给定的一对(x,z)有一组Y的值，这组值仅决定于x值而与z值无关
  • 函数依赖与属性集无关，多值依赖在全集上成立，一定在子集上成立，反之不然
  • Y函数依赖X，Y的子集一定函数依赖于X，而多值依赖不具有这样的特性
  • 多值依赖有对称性，Y多值依赖X，则U-X-Y多值依赖于X
  • 函数依赖是多值依赖的特殊情况
  • U-X-Y为空，那么X多值依赖于Y是平凡的多值依赖
  • Y和Z多值依赖于X，那么YZ的交、并、差集多值依赖于X
  • 1NF，对于每个非平凡的多值依赖，左边都含有码
  • BCNF，不存在非平凡非函数依赖的多值依赖
• 规范化的目的：消除关系数据库中，关系的异常和冗余等弊病
• 规范化的基本思想是逐步消除数据依赖中不合适的部分，使数据库模式中各关系模式达到某种程度的分离，使一个关系只描述一个实体或实体间的一种联系，即一事一地的设计原则
• 规范化的实质是概念的单一化

1. 模式分解

• 无损分解：对于任何一个关系r，都有r在分解后各关系模式投影上的连接是r
• 无损分解的充要条件：R1和R2的共同属性至少构成R1、R2二者之一的候选码
• 保持函数依赖：分解后函数依赖并集的闭包与R的闭包相同
• 判定方法：R中的每个函数依赖都能从分解后的函数依赖的并集中逻辑导出
• 规范化通过投影分解来完成，投影分解不是唯一的，结果大不相同
• 投影分解应该遵循的原则：具有无损连接性，保持函数依赖
• 若要求分解保持函数依赖，那么模式分解总可以达到3NF，但不一定能达到BCNF
• 若要求分解具有无损连接性，那一定可以达到4NF或更高

第六章 数据库设计

1. 数据库设计

• 指对于一个给定的应用环境，设计优化的数据库逻辑结构和物理结构，建立数据库，使之能够有效地存储数据，为开发满足用户需求的应用系统奠定基础
• 数据库设计的特点
  • 要把数据设计和处理设计密切结合起来
  • 与硬件、软件和管理紧密相关
• 手工试凑法（直接设计法）：根据应用的数据要求与处理要求，直接设计数据库的结构
  • 数据间关系复杂，使用要求各式各样，很难仅凭经验进行设计
  • 把数据的逻辑结构，物理结构，处理要求等一起考虑，很难对模式进行评价和优化，用户需求一旦发生变化，数据结构很难随之发生变化
  • 数据库设计与具体的DBMS紧密结合，移植困难
  • 缺乏文档资料，难以与用户交流，对设计难于评审
  • 难以由多个人合作进行设计
• 规范设计法：运用软件工程的思想和方法，把整个设计过程划分为若干阶段，把复杂的大问题分为若干相对简单的小问题，每个阶段只解决整个设计中的部分问题
• 规范设计法是迭代和逐步求精的过程

1. 数据库设计阶段

• 需求分析：对应用环境进行详细调查，收集支持系统目标的基础数据及其处理
  • 目标是收集支持系统应用目标的基础数据及其处理，调查的重点是数据和处理
    • 处理要求：用户要完成什么处理功能，对处理的响应时间和处理方式的要求
    • 信息要求：指系统中所涉及的数据即数据之间的联系，确定数据之间联系的类型
    • 安全性与完整性的要求
  • 调查用户实际要求，与用户达成共识
  • 分析、表达用户的需求
    • 用数据流图表达数据和处理之间的关系
    • 用数据字典描述系统中各类数据
  • 数据流图：以图形方式来表达系统的功能，数据在系统内部的逻辑流向和逻辑变换过程
  • 数据字典：是对数据的集中的系列说明，包含每一个数据元素的名字、含义等各方面的描述
  • 需求分析阶段的数据字典，可看成是数据元素表，在数据库实施阶段建立起的数据字典，是数据库系统重要组成部分
• 概念结构设计：通过对用户需求进行综合、归纳与抽象，形成独立于数据库逻辑结构与具体DBMS的概念模型，可以用E-R图等表示
• 逻辑结构设计：将概念结构转换为某个DBMS所支持的数据模型，并进行优化，再将得到的逻辑结构转换成特定的DBMS能处理的模式、子模式
• 物理结构设计：设计数据库在物理设备上的存储结构和存取方法，一般分为两步：一是确定数据库的内模式，二是对物理结构进行时间和空间效率的评价
• 数据库实施：是建立数据库的过程，用DBMS的DDL描述三级模式，并调试产生目标模式，开发应用程序，组织数据入库并试运行
• 数据库运行和维护：在数据库正常运行后，由DBA执行对数据库经常性的维护工作

1. E-R法

• E-R法的思想是用E-R图描述现实世界的信息，这种信息结构称为概念结构（概念模型），然后根据具体系统的要求将概念结构转换成特定系统所能接受的逻辑结构（层次、网状、关系）
• 概念模型用于信息世界建模，是现实世界到信息世界的抽象，是用户和数据库设计人员进行交流的语言
• E-R法由两部分组成
  • 用E-R图描述现实世界
  • 将E-R图转换成相应的数据模型
• E-R图组成：实体、属性、联系（一对一、一对多、多对多）
• 联系语义扩充
  • 存在依赖：依赖于其它实体的实体称为弱实体
  • 标识依赖：如果实体不能由它自己的属性来唯一标识，而必须通过与它相联系的另一实体一起来标识，那么称该实体标识依赖于另一个实体
  • 实体的子类：子类可以继承父类的属性，也可附加某些属性，子类之间的交不一定为空
• 设计方法
  • 自顶向下：首先定义全局概念结构的框架，然后逐步细化
  • 自底向上：首先定义各局部应用的概念结构，然后将其集成起来
  • 逐步扩张：首先定义核心概念结构，然后向外扩充
  • 混合策略：自顶向下设计全局概念框架，自底向上设计各局部概念策略
  • 最常用的方法是自底向上方法
• 自底向上设计
  • 局部E-R图设计
    • 选择局部应用
    • 以需求分析中得到的数据元素表为基础，建立实体模型
    • 确定实体之间的联系模型
    • 用E-R图表示这些实体与实体之间的联系，形成分E-R图
  • 综合局部E-R图形成总E-R图
    • 多个分E-R图一次集成
    • 逐步集成，用累加的方式一次集成两个分E-R图
  • 合并：解决冲突，将各分E-R图合并起来生成初步E-R图
    • 属性冲突：属性的类型、取值范围或取值集合不同，或属性取值单位冲突
    • 命名冲突：包括属性名、实体名、联系名之间的同名异义、异名同义
    • 结构冲突：同一对象在不同应用中有不同抽象，如在一应用中为实体，在另一应用为属性
  • 修改和重构：消除不必要的冗余，生成基本E-R图
    • 冗余的数据是指可由基本数据导出的数据
    • 冗余的联系是指可由其它联系导出的联系
  • 消除冗余的方法：分析法、规范化方法

1. 逻辑结构设计

• 逻辑结构设计的任务就是把概念结构转换为选用的DBMS所支持的数据模型的过程
• 形成初始关系数据库模式
  • 一个实体型转换为一个关系模式，实体的属性就是关系的属性，实体的码就是关系的码
  • 一个联系转换为一个关系模式，与该联系相连的各实体的码以及联系的属性转换为关系的属性
    • 若联系为一对一，则每个关系的码均是该关系的候选码
    • 若联系是一对多，则该关系的码是n端实体的码
    • 若联系为多对多，则该关系的码是诸实体码的组合
  • 三个或三个以上实体间的多元联系，转换为一个关系模式，与该多元联系相连的各实体的码以及联系的属性转换为关系的属性，而关系的码为各实体码的组合
  • 具有相同码的关系可以合并
  • 弱实体类型的转换
    • 对于每个弱实体类型，创建一个新的关系，该关系中包含所有弱实体类型的属性
    • 把标识关系（被依赖关系）的主码添加到新关系中，并将其作为新关系的外码
    • 新关系的主码是标识关系的主码和弱实体类型的部分标识的组合
  • 超类/子类联系的转换
    • 为超类和每个子类创建单独的关系
    • 在超类所创建的关系中，包含所有子类成员都共有的属性，包括主码
    • 在超类中包含一个或多个属性作为子类判定符
    • 在为每个子类所创建的关系中，包含超类的主码以及子类特有的属性
• 关系模式规范化
  • 按照数据依赖的理论，逐一分析转换所得关系模式，判断是否存在部分函数依赖、传递函数依赖、多值依赖等，确定它们的范式等级
• 关系模式优化
  • 按应用系统的处理要求，确定是否进行模式合并或分解
  • 为了提高存取效率和存储空间的利用率，可以对关系模式进行必要的分解
  • 水平分解：把关系的元组分为若干子集合，定义每个子集合为一个子关系，以提高系统效率
    • 80/20原则：可以把经常使用的那一部分数据分解出来作为一个关系，其他数据作为另一个关系
    • 数据分片：如果关系R上具有n个事务，而且多数事务存取的数据不相交，则R可以分解为少于或等于n个关系
  • 垂直分解：把关系模式R的属性分解为若干个集合，形成若干子关系模式
    • 原则：经常在一起使用的属性从R中分解出来形成一个子关系模式
    • 必须确保无损连接性和保持函数依赖
• 子模式定义
  • 根据局部应用的需求，结合具体DBMS的特点，设计用户外模式（视图）
    • 使用更符合用户习惯的别名
    • 可以对不同级别的用户定义不同的视图，以保证系统的安全性
    • 通过定义视图降低复杂查询的难度，简化用户对系统的使用

1. 物理结构设计

• 数据库物理结构包括数据在物理设备上的存储结构和存取方法
• 确定数据库的存储结构
  • 确定存放位置
    • 经常存取部分与存取频率较低部分分开存放
    • 数据和日志备份放于不同的磁盘上
  • 确定系统配置
    • 确定系统环境变量、存储分配参数，进行物理优化
• 选择关系的存取方法：是使事务能够快速存取数据库中的数据的技术
  • 索引方法：为了加速所需数据的访问
  • 常用B+树索引
  • 选择索引域原则
    • 经常在查询条件中出现的属性
    • 经常作为最大值和最小值库函数的参数
    • 经常作为连接属性
  • 索引并非越多越好
  • 聚集方法：把关系中某个属性/组（聚集键）值相同的记录集中存放在连续的屋里快，称为聚集，能够提高该属性的查询速度
  • 一个关系只能参加一个聚集
  • 一般原则
    • 经常进行连接操作的关系可建立聚集
    • 单个关系的某族属性经常进行相等比较
    • 关系的某个属性值重复率高
  • 注意：建立与维护聚集系统开销很大，对于更新操作远远多于连接操作的关系不应该使用聚集方法
  • Hash方法：一种支持快速存取的文件存储方法
  • 通过Hash函数将记录关键字转换成地址
  • 如果关系的属性主要出现在等连接条件中，或出现在相等比较条件中，而且满足下列条件之一，可以选择该方法
    • 关系的大小可预知，而且不变
    • 如果关系大小动态改变，则须DBMS提供动态Hash存取方法

第七章 存储管理与索引

1. 物理存储管理器

• DBMS中负责磁盘上数据组织和存取操作的模块，称为物理存储管理器，也称为磁盘管理器，是DBMS结构的最底层
• 物理存储管理器以页/块为单位组织数据
• DBMS设定数据库的基本存储是在磁盘上，DBMS管理内存与外存数据的交换
• 负责数据存取以及数据在磁盘和主存之间的移动，主要操作包括页/块读、写、申请和释放
• 可利用操作系统的文件系统，也可DBMS自己实现

1. 数据库的物理结构

• 数据库：若干文件组成，这些文件采用专有的格式，操作系统不能获取这些文件内容的任何信息
• 文件：由若干个定长的存储块/页构成
• 块/页：存储分配和数据传输的单位，可以包含几个记录，每个记录有唯一的标识符ID
  • 页/块是固定大小的数据块，每个页有唯一标识符，DBMS将页ID映射为页的物理位置
  • 由头部Header和数据构成，Header包含页中数据的元数据，如页大小，DBMS版本
  • 最常用的结构是分槽页结构，槽数组保存每个元组的起始位置偏移量，用于存储变长记录
• 记录：页内存储多个记录
  • 记录是字节序列，DBMS负责将该序列解释为属性类型和值
  • 包含记录头部、记录数据、唯一标识符ID
  • 应用程序不能依赖ID进行唯一性标识
• 一个文件在逻辑上被组织为记录的序列，记录被映射到磁盘快上
• 文件中的记录有多种组织方式，支持记录在磁盘上的定位

1. 文件的磁盘块分配

• 连续分配：数据块被分配到连续的磁盘块上
• 链接分配：数据块中包含指向下个数据块的指针
• 按簇分配：簇是连续的几个磁盘块，簇之间指针连接
• 索引分配：索引块中存放指向数据块的指针

1. 文件的记录组织

• 堆：记录可以存放在文件空间中的任何位置
  • 链表方式：在文件开始维护一个Header页，存储空白页链表头指针和数据页链表头指针，每个页记录了当前包含的空槽数
  • 页目录方式：DBMS维护特殊页，保存文件中的数据页的位置，记录每个页中的空槽数
• 顺序：基于每个记录的搜索码值顺序排列
  • 搜索码：用于在文件中查找记录的任意属性或属性集合
  • 通过指针把记录链接起来，每个记录的指针指向按搜索码排列的下一条记录
  • 可以高效按某个搜索码处理记录
• 索引：按某种顺序有序存储
  • 索引是指记录的关键字与相应记录的存储地址的对照表
  • 索引文件由主文件和索引表构成
    • 索引表必须按关键字有序
    • 主文件本身可以按主关键字有序组织（索引顺序文件）或无序组织（索引非顺序文件）
• 散列：在搜索码上的Hash函数，计算出记录在文件中存放的块
  • 设计哈希函数以及处理冲突的方法，计算出记录在文件中存放的块
  • 哈希函数将搜索码作为参数，计算出一个[0,N-1]区间的整数，将具有键值k的记录存储在h(k)编号的桶中，一个文件由N个桶组成
  • 处理冲突方法：在散列值的个数多余一个桶时，形成一个主桶和多个溢出桶的列表
• 聚集：将有联系的记录存储在同一个块上，以最小化I/O次数
  • 聚集码是一种属性，定义了哪些记录被存储在一起
  • 多表聚集：将多个关系存储于一个文件中，在每个块中存储两个或更多关系的相关记录，可以加快特定的连接查询，但会使单个表的访问变慢

1. 缓冲区管理系统

• 缓冲区：是主存中可以存储磁盘块副本的区域
• 缓冲区管理器：负责缓存空间分配，内外存交换，块/页是存储分配和数据交换的单位
• 缓冲区组织为一个固定大小的页面数组，每个元素称为帧，存放磁盘上的一个页/块
• 缓冲区元数据是页表，跟踪当前内存中所有页的访问情况，并保存了每个页的元数据
• 缓冲区的共享锁和排它锁
  • 实现并发控制，读操作加共享锁，更新操作加排他锁
  • 加锁规则：一次只能由一个进程获得排它锁，共享锁与排它锁不能同时加，多个进程可以同时持有共享锁
• 替换策略：LRU策略及其改进算法

1. 索引

• 索引记录/索引项，是索引表文件的记录，包含两个域
  • 索引域（搜索码）：存储数据文件中一个或一组域（属性）
  • 指针：指向索引域值为K的记录所在磁盘块的地址
• 分类
  • 排序索引：索引项是排序的
  • 哈希索引：索引项使用索引域上的Hash函数确定位置
  • 基于哈希表实现，讲一个键值映射到表中一个位置来访问记录
  • 静态哈希：哈希表的大小是固定的
    • 文件增大时，太多的溢出桶将降低访问性能
    • 数据规模缩小时，会造成空间浪费
  • 动态哈希：允许哈希表的大小动态修改
    • 定期重哈希：创建新的大的哈希表，把原表上的key重新哈希到新表上
    • 线性哈希：以一种递增的方式重新哈希
    • 重组的开销大
  • 适用于检索哈希码等于特定值的记录检索，不适用于区间值的检索，以及部分匹配检索
  • 有很多重复值的列，不适合于做key
• 聚集索引与非聚集索引
  • 聚集索引：索引域/搜索码值的排列顺序与记录在文件中的排列顺序一致，也称为主索引
  • 非聚集索引：索引项排列的次序与文件中记录的排列顺序不同，也称为辅助索引
• 稠密索引与稀疏索引
  • 稠密索引：随遇文件中的每个搜索码值都有一个索引项
  • 稀疏索引：只有部分索引域/搜索码值有索引记录，当文件记录以索引域排序时，可以采用
  • 相比稠密索引，占空间小并且维护代价低，但定位速度慢，非聚集索引都是稠密索引
• 多级索引
  • 索引规模大，无法全部放入内存，导致性能下降
  • 对索引文件建立稀疏索引
    • 外层索引：基本索引的稀疏索引
    • 内层索引：基本索引文件
• 二叉树索引与多枝树索引：每个节点D个关键字，D+1个指针
• B+树索引

1. B树与B+树

• B树
  • B树是附加限制条件的索引数，限制了每个节点放置关键字与指针的最小和最大个数
  • 根节点有[2,n]个子节点，中间节点有[[n/2], n]个子节点，叶节点[[(n-1)/2], n-1]个记录指针
  • 从树根到叶节点每条路径的长度都相同，因此所有的叶节点都在同一层上
  • B树的关键字是散布在各层上
• B+树
  • B+树是B树的改进，把树中所有关键字都按递增次序从左到右安排在叶节点上，并且链接起来
  • B+树能同时进行随机查找和顺序查找
  • B+树根节点、中间节点、叶节点的关键字与指针的最小和最大个数与B树相同
  • 在B+树文件组织中，叶节点存储的是记录，而不是记录的指针
  • 用B+树索引解决索引顺序文件组织的性能下降问题
  • 由于记录通常比指针大，所以要求叶节点半满，而最大记录数要小于中间节点的指针数

第八章 查询处理与查询优化

1. 查询处理

• 四个阶段：查询分析、查询检查、查询优化、查询执行
• 对于主流在磁盘上的大型数据库，从磁盘访问数据的I/O代价通常是最重要的代价
• 总代价 = I/O代价 + CPU代价 + 内存代价
• 假设存取一个块就需要一次磁盘访问，使用访问磁盘的块数作为估计代价的因素

1. 实现查询操作的算法

• 选择
  • 全表扫描法：按照物理顺序读表到内存，检查每个元组，直到所有块都经过检查
  • 索引扫描法：如果在选择条件的属性上有索引，先通过索引找到目标索引项，再通过索引项找到元组
• 排序
  • 内存中完全容纳的关系可以用快速排序法等算法
  • 内存中无法容纳的关系，采用外排序-归并算法
    • 第一阶段，建立多个排好序的归并段，每个段仅包含关系的部分记录
    • 第二阶段，对归并段进行归并
• 连接
  • 嵌套循环法
    • 两个连接的表，第一个表为外循环，另一个为内循环
    • 不需要索引，并适用于任何连接条件
    • 需要检查两个关系中的每一对元组，代价高
    • 应选择较小表作为外表
    • 设缓冲区块数为k，访问块数 = br + br / (k-1) * bs
  • 索引链接法
    • 第二个表按照连接属性建索引，取第一个表元组的连接属性与第二个表元组的连接属性比较
    • 以元组较少的关系作为外层关系，代价最小
  • 排序合并法
    • 两个表都按照连接属性排序，取第一个表元组的连接属性与第二个表元组的比较
    • 只能用于等值连接或自然连接
    • 访问块数 = br + bs
  • Hash Join法
    • 连接属性作为Hash码，用同一个Hash函数把两个连接表的元组散列到同一个Hash文件
    • 只能用于等值连接或自然连接
• 去重
  • 使重复数据相邻，保留一个数据删除其他
  • 排序方法和哈希方法
• 投影
  • 在每个元组上执行投影，之后再去重
• 集合运算
  • 类似排序-合并逻辑，排序然后对每个已排序的关系扫描一次
  • 类似Hash Join将两个关系分区，在两个关系对应区中执行运算
• 库函数
  • 基于分组属性进行排序或散列以聚集同组的元组，再执行库函数

1. 表达式的执行

• 物化方法
  • 按次序每次只执行一个运算，运算结果被雾化到一个临时关系中，这些临时关系一般需要写到磁盘上
  • 方法适用性广泛，但临时表的写和读的代价大
• 流水线方法
  • 同时执行多个运算，将结果传递给下一个运算
  • 不需要在磁盘上存储临时关系，代价小，但对有些运算不适用，如排序等

1. 查询优化

• 目标：选择一个高效执行的查询处理策略，使得查询代价最小，即访问磁盘的块数最少
• 按照优化的层次分为代数优化和物理优化
• 代数优化：关系代数表达式的优化，即按照一定的规则，改变代数表达式中操作的次序和组合
  • 通过对关系代数表达式的等价变换来提高查询效率
  • 选择运算尽早执行，减小中间关系-减少元组数据
  • 投影运算尽早执行，减小中间关系-减少属性数目
  • 把投影运算和选择运算同时进行，把投影同其前或其后的双目运算结合起来，减少扫描关系的次数
  • 把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算
  • 找出公共子表达式，把公共子表达式的结果写入中间文件，重复使用
• 物理优化：存取路径和底层操作算法的选择，包括基于规则或基于代价等
  • 选择高效合理的操作算法或存取路径，得到优化的查询计划
  • 基于启发式规则的操作算法选择
  • 选择操作
    • 对于小关系，使用全表顺序扫描
    • 对于大关系，可以采用索引扫描法，全表顺序扫描
  • 连接操作
    • 如果两个表都已经按照连接属性排序——排序-合并法
    • 如果一个表在连接属性上有索引——索引连接法
    • 如果连接属性上未排序且未建索引，且其中一个表较小——Hash Join法
    • 最后可选用嵌套循环法，并选择较小的表为外循环表
  • 基于代价估算的优化
    • 利用数据库的统计信息计算各种操作算法的执行代价，选出具有最小代价的执行计划
• 两者结合的优化方法
• 查询计划：定义了每个操作的算法以及这些操作执行的顺序

第九章 事务处理技术

1. 事务

• 事务是用户定义的数据库操作序列，这些操作要么都做，要么都不做，是一个不可分割的工作单位
• 特性
  • 原子性：事务中包括的所有操作要么都做，要么都不做
  • 一致性：事务执行的结果必须是使数据库从一个一致性状态，变到另一个一致性的状态
  • 隔离性：一个事务的执行不能被其它事务干扰，即一个事务内部的操作及使用的数据对其他并发事务是隔离的，并发执行的各个事务之间不能互相干扰
  • 持久性：一个事务一旦提交之后，它对数据库的影响必须是永久的，其它操作或故障不应该对其执行结果有任何影响
• 事务的ACID特性对于数据的正确、有效具有重要意义，但事务的特性有可能遭破坏
  • 多个事务并发运行时，不同事务的操作交叉进行
  • 事务在运行过程中被强行停止
• 利用数据库并发控制机制以及数据库恢复机制保证事务的特性不被破坏，从而保证数据库数据的正确、有效
  • 原子性由恢复机制实现
  • 一致性是由事务的原子性保证的
  • 隔离性通过并发控制机制实现
  • 持久性通过恢复机制实现
• 事务是数据库恢复和并发控制的基本单位
• 事务的开始和结束可以由用户显式控制，如果用户没有显式定义事务，则由DBMS按缺省规定自动划分事务
• 事务和应用程序是两个概念，一般来说，一个应用程序可以包含多个事务
  • BEGIN TRANSACTION：事务开始
  • COMMIT：提交事务，正常结束
  • ROLLBACK：撤销全部更新，回滚到事务开始时状态，非正常结束

1. 数据库恢复技术

• 数据库管理系统具有把数据库从错误状态恢复到某一已知正确状态的功能
• 数据库恢复是通过数据库管理系统的恢复子系统完成的
• 恢复子系统意义
  • 保证事务的原子性：实现事务非正常终止时的回滚
  • 保证事务的持久性：当系统发生故障以后，数据库能够恢复到正确状态
• 故障的种类
  • 事务内部的故障
    • 可预期的：事务根据内部的测试条件，确定是否回滚
    • 不可预期的：指不能由应用程序处理的事务故障，如死锁，运算溢出，违反完整性规则等
  • 系统故障
    • 是指造成系统停止运行的任何事情，使得系统要重新启动，如硬件错误，操作系统故障，停电等
    • 这类故障打断所有正在运行的事务，使事务都异常中止，但不会破坏数据库
  • 介质故障
    • 介质故障指外存故障，如磁盘损坏，瞬时强磁场干扰等
    • 这类故障将破坏全部或部分数据库，并影响正在存取这部分数据的所有事务
  • 计算机病毒
    • 计算机病毒是一种认为的破坏或故障，已成为数据库系统的主要威胁之一
    • 多数病毒对数据进行非法修改
• 故障对数据库系统的影响
  • 数据库本身被破坏，如介质故障
  • 数据库没有破坏，但数据可能不正确，由于事务的非法终止、计算机病毒造成
• 数据库恢复的关键问题
  • 建立冗余：数据转储和登录日志文件
  • 利用冗余实施数据库恢复

1. 数据转储

• DBA定期地将整个数据库复制到磁带上或另一个磁盘上保存起来的过程，这些备用的数据文本称为后备副本或后援副本
• 静态转储：系统中无事务运行时进行的转储操作，并且转储过程中，不允许对数据库进行任何存取、修改
  • 优点：保证副本的数据一致性
  • 缺点：由于转储必须等待正在运行的事务结束才能开始，而新的事务必须等待转储结束才能执行，降低了数据库的可用性
• 动态存储：转储期间允许对数据库进行存取或修改
  • 优点：不影响数据库的可用性
  • 缺点：不能保证副本上的数据正确、有效，还必须把转储期间各事务对数据库的修改记录下来，建立日志文件，后援副本加上日志文件就能把数据库恢复到某一时刻的正确状态
• 海量转储：每次转储全部数据库
• 增量转储：每次只转储上一次转储后更新过的数据
• 数据库镜像：根据DBA的要求，自动把整个DB或其中的关键数据复制到另一个磁盘上，由DBMS自动保证镜像数据库与主数据库的一致性

1. 日志文件

• 日志是用来记录事务对数据库更新操作的文件
• 日志文件主要有两种格式
  • 以记录为单位：各个事务的开始标记、结束标记、所有更新操作
  • 以数据块为单位：事务标识、更新前和更新后的数据块
• 作用
  • 在事务故障和系统故障恢复必须使用日志文件
  • 在动态转储方式中必须建立日志文件，后备副本和日志文件综合起来才能有效地恢复数据库
  • 在静态转储方式中，用日志文件恢复转储结束时刻到故障点间的事务
• 写入规则
  • 登记的次序严格按并发事务执行的时间顺序
  • 必须先写日志文件，后写数据库

1. 故障恢复策略

• 事务故障的恢复：在不影响其它事务的情况下，强行回滚，撤销已做的修改
• 系统故障的恢复
  • 一是未完成的事务对数据库的更新可能已经写入数据库——撤销
  • 二是已提交事务对数据库的更新可能还留在缓冲区未写入数据库——重做
• 介质故障的恢复
  • 装入最新的数据库后备副本，使数据库恢复到最近一次转储时的一致状态
  • 对于动态转储的副本，还需要装入转储开始时刻的日志文件副本，将数据库恢复到一致状态
  • 装入转储以后的日志文件副本，重做已完成的事务

1. 检查点

• 利用日志技术进行恢复时，恢复子系统通常需要检查大量日志记录，存在的问题是
  • 搜索日志耗费大量时间
  • 不必要重做某些事务
• 检查点技术可以改善效率，使得在检查点之前提交的事务，数据库恢复处理时不必重做
• 在日志文件中增加检查点记录，包括
  • 建立检查点时刻所有正在执行的事务清单
  • 这些事务最近一个日志记录的地址
• 系统中增加一个重新开始文件，用来记录各个检查点记录在日志文件中的地址
• 恢复子系统动态维护日志文件
  • 利用重新开始文件定位最近检查点记录
  • 找到检查点时刻运行事务清单
  • 确定需要撤销和重做的事务
  • 执行撤销或重做动作

1. 事务并发

• 优点：提高系统的吞吐量，减少平均响应时间
• 问题：多个事务同时存取同一数据时，如不加控制就可能会读取或存储不正确的数据，破坏数据库的一致性
  • 丢失更新：事务的修改被丢失
  • 脏数据的读出：读到的数据与数据库中的不一致
  • 不能重复读：事务无法再现前一次读取的结果
• 并发控制就是要合理调度并发事务，避免并发事务之间的互相干扰造成数据的不一致性
• 并发控制的主要方法是采用封锁机制
  • 排它锁（X锁）：只允许该事务读取和修改R，其它事务对R的任何封锁请求都不能成功
  • 共享锁（S锁）：该事务可以读取但不能修改R，其它事务只能对R加S锁
• 封锁协议：建立不同的约定，形成不同级别的封锁协议
  • 一级封锁协议
    • 事务在修改数据之前必须对数据加X锁，直到事务结束才释放
    • 防止丢失修改
  • 二级封锁协议
    • 一级封锁协议加上事务在读取数据之前必须先对数据加S锁，读完后即可释放S锁
    • 防止丢失修改、读脏数据
  • 三级封锁协议
    • 一级封锁协议加上事务在读取数据之前必须先对数据加S锁，直到事务结束才释放
    • 防止丢失修改、读脏数据、不可重复读

1. 封锁粒度

• 封锁对象的大小称为封锁粒度
• 封锁粒度大，则并发度低，封锁机构简单，开销小
• 封锁粒度小，则并发度高，封锁机构复杂，开销大
• 多粒度封锁：在一个系统中同时支持多种封锁粒度供不同的事务选择，选择封锁粒度时应同时考虑封锁开销和并发度两个因素，适当选择封锁粒度达到最优效果
• 多粒度树：根节点是整个数据库，表示最大的粒度，叶节点表示最小的粒度
• 多粒度封锁协议：允许多粒度树中的每个节点被独立的加锁，对一个节点加锁意味着这个节点的所有后裔节点也被加以同样类型的锁，因此，在多粒度封锁中一个数据对象可能以两种方式封锁
  • 显式封锁：应事务的要求直接加到数据对象上的封锁
  • 隐式封锁：该数据对象没有独立加锁，是由于其上级节点加锁而使该数据对象加上了锁
• 在多粒度封锁方法中，显式封锁和隐式封锁的效果是一样的
• 对某个数据对象加锁，系统要做如下检查
  • 是否与该数据对象上的显式封锁冲突
  • 是否与该数据对象上的隐式封锁冲突
  • 是否与该数据对象下级的显式封锁冲突

1. 意向锁

• 意向锁：该节点的下层节点正在被加锁
• 意向锁好处：在对象加锁时，不再检查下级节点的封锁，只需检查对象和它的上级节点
  • 意向共享锁（IS锁）：其后裔节点意向加S锁
  • 意向排它锁（IX锁）：其后裔节点意向加X锁
  • 意向共享排它锁（SIX锁）：对它加S锁，再加IX锁
• 具有意向锁的多粒度封锁方法中，任意事务T要对一个数据对象加锁，要先对它的上级对象节点加意向锁，申请封锁按自上而下的次序进行，释放封锁时，应按自下而上的次序进行

1. 活锁和死锁

• 避免活锁的简单方法是先来先服务的策略
• 预防死锁
  • 一次封锁法
    • 要求每个事务必须一次将其所有要使用的数据全部加锁，否则就不能执行
    • 可以有效地防止死锁的发生，但由于需要扩大加锁的范围，因此降低了系统的并发度
  • 顺序封锁法
    • 预先对数据对象规定一个封锁顺序，所有的事务都要按照这个顺序实行封锁
    • 可以有效地防止死锁，但由于数据库中数据的不断变化，和事务封锁要求的动态提出而实现难度大
• 死锁检测和解除
  • 超时法：如果一个事务的等待时间超过了规定的期限，就认为发生了死锁
  • 等待图法：如果发现图中存在回路，则表示系统出现思索
  • 死锁恢复：选择一个处理死锁代价最小的事务，将其撤销，释放此事务持有的所有锁，使其它事务得以继续运行下去，对于所撤销的事务所作的操作必须加以恢复

1. 事务的调度

• 调度要保证事务执行的正确性
• 可串行化：多个事务的并发执行是正确的，当且仅当其结果与按某一次序串行执行它们时的结果相同，这种调度策略称为可串行化调度
• 可串行化是并行事务正确性的准则
• 一个调度在保证冲突操作次序不变的情况下，可以通过交换两个事务不冲突操作的次序，得到另一个串行调度，则原调度为冲突可串行化调度
• 冲突操作：不同事务对同一数据的读-写操作以及写-写操作
• 操作次序交换的约束条件：不同事务的冲突操作，以及同一个事务的两个操作不能交换
• 一个冲突可串行化调度，一定是可串行化调度
• 两段锁协议可保证并发事务的可串行性
  • 在对任何数据进行读、写操作之前，事务首先要获得对该数据的封锁
  • 在释放一个封锁之后，事务不再获得任何其他封锁
  • 事务分为两个阶段，第一个阶段是获得封锁，也称为扩展阶段，第二个阶段是释放封锁，也称为收缩阶段
• 若所有事务均遵从两段锁协议，则这些事务的所有并发调度都是可串行化的
• 事务遵守两段锁协议是可串行化调度的充分条件而不是必要条件
• 两段锁协议并不要求事务在执行任何数据库读、写操作之前就一次申请全部封锁，因此遵守两段锁的事务仍可能发生死锁

1. 并发控制方法

• 事务隔离级别
  • 读未提交：事务可以读取到其他事务尚未提交的数据
  • 读已提交：事务只能读取到其他事务已经提交的数据，解决脏读
  • 可重复读：同一个事务内的多个查询中读取到的数据是一致的，解决不可重复读
  • 串行化：事务按照顺序一次执行，解决幻读
    • 幻读：一个事务中按照某个条件先后两次读取数据库，两次读取结果的条数不同
• 悲观并发控制：假定会发生并发冲突，事前控制，避免冲突发生
  • 三段封锁协议、两段锁协议
  • 当事务冲突时，通过锁等待读写的资源，可以实现各种隔离级别
  • 该协议适合事务冲突较多的场景
• 乐观并发控制：假设不会发生并发冲突，时候控制，只在提交操作时检查，做冲突处理
  • 时间戳排序协议：给每个事务分配一个全局唯一的时间戳，使得所有事务有单调顺序
    • 事务只能访问该事务时间戳前面的数据，而不能访问后面的数据
    • 可以产生冲突可串行化调度
    • 如果两个事务冲突，通常终止其中一个，将其回滚并重新调度，赋予新的时间戳
    • 当事务冲突时，通过回滚事务解决冲突，可以实现各种隔离级别
  • 乐观并发控制协议
    • 读阶段：从数据库中读取需要的数据，存放于事务私有工作区，在工作区进行写操作
    • 验证操作：有效性检查测试是否满足所需的隔离级别，若检测失败，终止事务，然后重启，否则进入写阶段
    • 写阶段：将私有工作区中的更新数据刷新到数据库里
    • 当事务冲突时，通过重启事务解决冲突，可以实现各种隔离级别
    • 如果事务冲突较少，执行时间较短，可采用乐观并发控制
• 多版本机制：维持一个数据的多个物理版本，供不同事务使用
  • 事务对数据进行写操作时，产生该数据的一个新版本
  • 事务对数据进行读操作时，读取事务开始时该数据的最新版本
  • 用来解决读写冲突的无锁并发控制，实现了读已提交和可重复读，但不能解决丢失更新问题
    • 事务的读操作无需等待且一定成功
    • 写操作会新建一个数据版本，不阻塞其它事务读老版本，提升并发度
  • MVCC与悲观、乐观并发控制技术相结合，提高并发性能
    • MVCC解决读写冲突，悲观/乐观并发解决写写冲突
  • 通过空间复用的多版本信息缓解读写冲突，再结合多种协议可以提升事务并发处理效率

第十章 数据库技术新发展

1. 数据仓库

• 数据仓库是支持管理决策过程的、面向主题的、集成的、随时间而增长的持久数据集合
  • 数据仓库上的业务处理称为联机分析处理（OLAP）
  • 数据库上的业务处理称为联机事务处理（OLTP）

1. 云数据库

• 云计算是信息技术与服务模式的一次重要变革
• 云服务提供商基于虚拟化技术，提供了数据库服务
  • 一是在硬件资源池服务器中部署传统数据库实例，称为云数据库服务
    • 将传统数据库部署在云上，借助虚拟化技术实现云数据库服务，并且可以很好兼容现有应用
    • 为了保证高可用性，通常部署成一主多从的结构
    • 数据库实例运行在独立的虚拟主机或容器上，每个实例都拥有隔离的存储，存储可以是本地存储或云存储
    • 存在的问题：资源利用率低、拓展性差、可用性低
  • 二是针对云的环境设计数据库架构，提供具有更好弹性及高可用的数据库服务，被称为云原生数据库技术
    • 数据库从设计之初即考虑到云的环境，为云而设计，架构为云设计
    • 计算存储分离、计算节点无状态、存储集群灵巧化
    • 对于计算实例，可根据负载状态进行弹性扩缩容，并在故障时实现快速切换
    • 对于存储，可以提供持久的数据可用及数据的快速获取
    • 很好满足云计算场景数据库服务对计算与存储的不同需求
    • 解决了传统数据库在资源利用率、拓展性及可用性方面的问题
• 基于计算存储分离架构的云原生数据库产品几乎都可分为计算层和存储层
• 计算存储分离架构数据库产品都是一主多从架构

1. 分布式数据库

• 分布式数据库是由一组分布在计算机网络的不同结点上的数据组成，每个节点具有独立处理的能力，称为场地自治，可以执行局部应用，同时每个结点也能通过网络通信支持全局应用
• 分布式数据库以“数据分布”为前提，强调场地自治性（局部应用）以及自治场地之间的协作性（全局应用），两者缺一不可
• 连接查询的优化方法：半连接
• 分布事务管理：两段提交协议
• 三类解决方案
  • 分布式中间件+单机数据库：单机数据库提供存储和执行能力，在多个单机数据库上封装一层中间层
  • 云原生数据库：通过构建分布式共享存储实现拓展，采用非对称计算节点
  • 原生分布式数据库：数据的存储、查询、处理都天然具备分布式特性
    • 由多个同构型的数据库节点组成
    • 采用Share-Nothing结构，即各节点相互独立，各自处理自己的数据，提供对等的读写服务
    • 每个节点都具备分布式处理的能力
    • 相互连接组合形成面向用户的单个数据库
  • 优点：
    • 系统自动扩容、按需扩容，不受数量和规模的限制
    • 数据由系统自动打散并存储多个副本，通过一致性协议保证多个副本和事务日志的一致性，对分布式事务、全局MVCC等支持更为彻底
    • 部署灵活，不被特定硬件和服务绑定