数据库系统原理

第一篇 基础篇

第 1 章 绪论

1.1 数据库系统概述

1.1.1 数据库的四个基本概念

数据 (data)

数据

数据是描述现实世界各种事物的可以识别的符号。数据的含义称为数据的语义，数据与其语义是不可分的。

信息

信息是一种已经被加工为特定形式的数据，这些数据对现在与将来的决策有明显价值。

信息是各种数据所包括的意义；数据是信息的载体，是信息的具体表现形式。

数据处理

从大量原始数据中抽取和推导出有价值信息的加工过程称为数据处理，包括：数据收集、组织、存储、加工、分类、检索、输出、传输等操作。

数据管理

数据处理一般性的基本操作，如数据分类、组织、存储、检索、维护等成为数据管理，并研究专门的技术——数据管理技术。

数据库 (DataBase, DB)

数据库

数据库是长期存储在计算机内的，有组织的，可共享的大量数据的集合。

数据库按照一定的数据模型组织，描述和储存，具有较小的冗余度(redundancy)、较高的数据独立性(data independency) 和易扩展性(scalability)，并可为各种用户共享。

数据库技术

• 是一种数据管理技术
• 按照某种数据结构对数据进行组织后，存储在计算机的二级存储中，并可以提供数据共享工作。

数据库系统

数据库系统是基于数据库管理系统建立的具有特定数据处理功能的系统。

数据库管理系统 (DataBase Management System, DBMS)

数据库管理系统是位于用户和操作系统之间的一层数据库管理软件。

特点：

• 数据的最小存取单位是数据项

它的功能有：

• 数据定义功能
  • 提供数据定义语言 (Data Definition Language, DDL)、

• 数据组织、存储和管理

• 数据操纵功能
  • 提供数据操纵语言 (Data Manipulation Language, DML)

• 数据库的事务管理和运行管理

• 数据库的建立和维护

• 统一的数据控制功能

  • 数据的安全性控制

    • 保护数据以防止不合法的使用所造成的数据的泄密和破坏

  • 数据的完整性控制

    指数据的正确性与相容性

  • 数据的并发控制

    • 对多用户的并发操作进行控制，协调，保护数据的完整性

  • 数据库恢复

    • 将数据库从错误状态恢复到某一已知的正确状态
• 其他功能

数据库系统 (DataBase System, DBS)

数据库系统是由数据库、数据库管理系统（及其应用开发工具）、应用程序和数据库管理员（DataBase Administrator, DBA）组成的存储、管理、处理和维护数据的系统。

1.1.2 数据管理技术的产生和发展

阶段	数据管理者	数据保存	数据共享程度	数据独立性	数据结构化	数据控制能力
人工管理阶段	用户（程序员）	不保存	无共享，冗余度极大	不独立，完全依赖于程序	无结构	应用程序自己控制
文件系统阶段	文件系统	可以长期保存	共享性差，冗余度大	独立性差	记录内有结构，整体无结构
数据库系统阶段	数据库管理系统	可以长期大量保存	共享性高，冗余度小	具有高度的物理独立性和一定的逻辑独立性	整体结构化，由数据模型描述	由数据库管理系统提供数据安全性、完整性、并发控制和恢复能力

1.1.3 数据库系统的特点

1. 数据结构化

   数据库的结构化是数据库的主要特征之一，也是数据库和文件系统的本质区别。

   数据内部结构化，整体结构化，数据之间有联系

2. 数据共享性高，冗余度低且易扩充

   数据共享可以大大减少数据冗余，节约存储空间，能避免数据之间的不相容性与不一致性，使得数据库系统弹性大，易扩充。

3. 数据独立性高

   减少应用程序的维护和修改

   • 物理独立性是指用户的应用程序与数据库中数据的物理存储是相互独立的。（数据的存储结构（物理结构）改变时，数据的逻辑结构可以不变，从而应用程序也不必改变）
   • 逻辑独立性是指用户的应用程序与数据库的逻辑结构是相互独立的（数据的逻辑结构改版时，应用程序可以不变）

4. 数据由数据库管理系统统一管理和控制

   1. 数据的安全性 (security) 保护

      数据的安全性是指保护数据以放置不合法使用造成的数据泄密和破坏

   2. 数据的完整性 (integrity) 检查

      数据的完整性是指数据的正确性（和客观世界相一致）、有效性和相容性（同一个数据在不同位置内容一致）

   3. 并发 (concurrency) 控制

      对多个用户的并发操作进行控制，协调，保护数据的完整性

   4. 数据库恢复 (recovery)

      将数据库从错误状态恢复到某一已知的正确状态

   5. 数据的最小存取单位是数据项

      既可以存取一个或一组记录，也可以存取数据库中某个或某一组数据项

1.2 数据模型

数据模型 (data model) 是对现实世界数据特征的抽象，是数据库的核心和基础。

将现实世界抽象为信息世界（概念模型），再将信息世界转换为机器世界（数据模型）。

概念模型（信息模型）

用于信息世界建模，是现实世界到信息世界的抽象描述用户和数据库设计人员进行交流的语言。

1. 信息世界中的基本概念

   1. 实体 (entity)

      客观存在并可相互区别的事物称为实体。

   2. 属性 (attribute)

      实体所具有的某一特性。

   3. 码 (key)

      唯一标识实体的属性集。

   4. 实体型 (entity type)

      用实体名及其属性名集合来抽象刻画同类实体，称为实体型

   5. 实体集 (entity set)

      同一类型的实体的集合。

   6. 联系 (relationship)

      实体型之间的联系，是实体之间的相互关联

      • 名称
      • 类型
        • 一对一 (1 : 1)
        • 一对多 (1 : n)
        • 多对多 (m : n)
      • （属性）

2. 概念模型是一种表示方法，实体–联系方法 (E-R 法)

   E-R 法(Entity-Relation Approach)：用 E-R 图描述现实世界的信息，这种信息结构称为概念结构

   • 用 E-R 图描述现实世界
   • 将 E-R 图转换成相应的数据模型

3. E-R 图

   • 组成
     • 实体：用长方形表示实体型，再框内写上实体名
     • 属性：用椭圆形表示实体的属性，并用无向边吧实体与其属性连接起来
       • 在无向边上打 ‘=’ 表示属性为实体的码
       • 在连接多条无向边的弧线上打 ‘=’ 表示这些属性共同组成实体的码
     • 联系：用菱形表示实体间的联系，菱形框内写上联系名。用无向边把菱形分别与有关实体相连，在边上标明连接的类型
   • 实体之间联系的语义补充
     • 存在依赖
     • 标识依赖
     • 实体的子类

数据模型（层次、网状、关系模型）

用于机器世界，按计算机系统的观点对数据进行建模。

数据模型的三要素

1. 数据结构

   • 描述数据库的组成对象以及对象之间的联系
     • 描述对象的类型、内容、性质的概念，如关系模型中的域，属性等
     • 描述对象之间联系的概念，如关系模型中的关系
   • 是数据模型静态特性的描述
   • 是刻画数据模型最重要的方面

2. 数据操作

   • 对数据库中各种对象（型）的实例（值）允许执行的操作的集合，包括操作及有关的操作规则。 * 是数据模型动态特性的描述
   • 类型：检索、更新（插、删、改）

3. 数据的完整性约束条件

   数据的完整性约束条件是一组完整性规则

   完整性规则：给定的数据模型中数据及其联系所有的制约和依存规则，用以保证数据的正确、相容。 完整性约束条件包括：

   • 符合这种数据模型所必须遵守的基本的通用的完整性约束条件
   • 针对具体数据的特定语义约束条件

数据模型的分类

1. 层次模型

   用树结构表示数据之间的联系，节点代表实体型，连线表示两实体型间的一对多联系。

   • 优点
     • 结构简单
     • 易于实现
   • 缺点
     • 支持联系种类少（只能直接表示二元一对多练习）
     • 数据操纵不便，子结点存取只能通过父节点来进行

2. 网状模型

   用图结构表示数据之间的联系，节点代表实体型，连线表示两实体型间的一对多联系。

   • 特点
     • 表达联系种类丰富
     • 结构复杂

3. 关系模型

   用二维表表示数据之间的联系

   • 特点
     • 用关系描述实体及实体间的联系（这种描述一致性使数据结构大大简化，概念简单）
     • 可直接表示多对多联系
     • 关系必须是规范化关系，即每个分量是不可分的数据项。或不许再表中套表
     • 建立在数学概念基础上，理论基础强

   • 语义约束

     • 实体完整性 （Entity Integrity）

       • 要有属性或属性组合作为主码，主码值不可位空或部分为空。或定义为若属性 A 是关系 R 的主属性，则属性 A 不能取空值。

         空值的含义是：不知道或不存在的值

     • 参照完整性 （Referential Integrity）

       • 外部码
       • 参照完整性

     • 用户定义完整性

1.3 数据库系统的结构

三级模式、两级映像

数据库的两级映像

• 数据的存储结构与逻辑结构之间的映像——实现数据的物理独立性
• 数据的全局逻辑结构与某类应用所涉及的局部逻辑结构的映像——实现数据的逻辑独立性

数据库系统的三级模式结构

1. 模式 (schema)

   模式也称为逻辑模式，是数据库中全体数据的逻辑结构和特性的描述。是所有用户的公共数据视图。

   三级模式的核心。

   模式描述语言（Data Description Language, DDL）

2. 外模式 (external schema)

   也称为子模式或用户模式。是个别用户的数据视图，即与某一应用有关的数据的逻辑表示。

   外模式 DDL

3. 内模式 (internal schema)

   也称为存储模式，是数据在数据库系统内部的表示，即对数据的物理结构和存储方式的描述。

   内模式 DDL

• 优点
  • 保证数据的独立性:
    • 模式与内模式分开–数据物理独立性
    • 模式与外模式分开–数据逻辑独立性
  • 简化用户接口, 方便用户使用
  • 有利于数据共享
  • 有利于数据的安全保密
• 缺点

1.4 数据库系统的组成

DBMS 的主要功能

• 数据库定义功能
  • 利用 DDL 语言描述外模式, 模式, 内模式(源模式)
  • 模式翻译程序把内模式翻译哼目标模式
• 数据存取功能
  • 提供 DML(Data Manipulation Language) 语言对数据库进行检索, 插入, 修改, 删除
• 数据库运行管理
  • 并发控制, 存取控制, 完整性约束检查, 日志管理……
• 数据组织, 存储和管理
• 数据库的建立和维护

DBMS 的组成

• 语言编译处理程序
• 系统运行控制程序
• 系统建立和维护程序
• 数据字典

DBA

• 建库
• 用库
• 改进

第二章 关系数据库

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

2.1.1 关系

1. 域(domain)

   域是一组具有相同数据类型的值的集合.

2. 笛卡尔积(cartesian product)

   $D_1\times D_2\times … \times D_n={(d_1, d_2, …, d_n)

   d_i\in D_i, i = 1,2,..,n}$

   1. 元组(n-tuple) $(d_1, d_2, …, d_n)$ n 元组
   2. 分量(component) 元组的每一个值 $d_i$

   3. 基数(cardinal number) 一个域允许的不同取值个数称为这个域的基数

      笛卡尔积的基数 = $\prod_{i=1}^{n}m_i$

3. 关系(relation)

   • 关系 $D_1\times D_2\times … \times D_n$ 的子集叫做在域 $D_1, D_2, …, D_n$ 上的关系, 用 $R(D_1, D_2,…, D_n)$ 表示, n 是关系的目(度, degree)
     • 单元关系(unary relation)
     • 二元关系(binary relation)
     • 属性(attribute): 关系二维表每个列附加的名称
     • 候选码(candidate key): 能唯一标识一个元组的属性组
     • 主码(primary key): 在候选码中选择一个为主码
     • 主属性(prime attribute): 候选码的各个属性
     • 非主属性(non-prime attribute) * 基本关系的性质
   • 列的同质(Homogeneous)的，即每一列中的分量来自同一域，是同一类型的数据。
   • 不同列可出自同一域, 每列必须有不同的属性名
   • 列的顺序无所谓, 即列的次序可以呼唤
   • 任意两个元组不能完全相同
   • 行的顺序无所谓, 即行的次序可以呼唤
   • 每一分量必须是不可再分的数据, 满足这一条件的关系称作满足第一范式 (1NF, Normal Form) 的

关系模式

关系的描述称为关系模式(relation schema), 它可以形式化表示为: $R(U, D, DOM, F, I)$

• R–关系名
• U–组成该关系的属性名集合
• D–U 中属性来自的域
• DOM–属性向域的映像集合
• F–属性间数据的依赖关系集合
• I–完整性约束集合

2.2 关系操作

2.3 关系的完整性

2.3.1 实体完整性

• 要有属性或属性组合作为主码, 主码值不可为空或部分为空。或定义为若属性A是关系R的主属性，则属性 A 不能取空值。
• 空值的含义是：不知道或不存在的值。

2.3.2 参照完整性

• 外部码
  • 设 F 是基本关系 R 的一个或一组属性，但不是 R 的码。如果 F 与基本关系 S 的主码 Ks 相对应，则称 F 是关系 R 的外部码（Foreign Key），并称 R 为参照关系（Referencing Relation），S 为被参照关系（Referenced Relation）或目标关系（Target Relation）。R 和 S 不一定是不同的关系。
  • 目标关系 S 的主码 Ks 和参照关系的外部码 F 必须定义在一个域上。
• 参照完整性
  • 如果关系R的外部码 Fk 与关系 S 的主码 Pk 相对应，则R中的每一个元组的 Fk 值或者等于 S 中某个元组的 Pk 值，或者为空值。

2.3.3 用户定义完整性

用户定义完整性反映了某一具体应用所涉及的数据必须满足的语义要求。

2.4 关系代数

• 从数学角度，基本关系代数运算有 5 种：并、差、乘、选择、投影
• 从数据库角度，核心的关系代数运算为：选择、投影、连接（或自然连接）

关系模型的数据操作

关系数据操作的基础是”关系运算“。关系运算的方式有两种：代数方式，逻辑方式。

关系代数

关系代数是一种抽象的查询语言 ，它用对关系的运算来表达查询。

• 运算对象

  • 关系

• 运算结果

  • 关系

• 运算符

  • 集合运算符
    • $\cup$ 并
    • $\cap$ 交
    • - 差
    • $\times$ 笛卡尔积
  • 专门关系运算符
    • $\sigma$ 选择
    • $\prod$ 投影
    • $\Join$ 连接
    • $\div$ 除

  2.4.1 传统的集合运算

  传统的集合运算是二目运算

  1. 并 (union)

     $R\cup S={t

     t\in R\vee t\in S}$

  2. 差 (except)

     $R-S={t

     t\in R\wedge t\not\in S}$

  3. 交 (intersection)

     $R\cap S={t\in R\wedge t\in S}$

  4. 笛卡尔积 (cartesian product)

     $R\times S={t_r t_s

     t_r\in R\wedge t_s\in S}$

2.4.2 专门的关系运算

引入记号

1. 关系模式 $R(A_1, A_2, …,A_n)$，它的一个关系为 $R$，$t\in R$ 表示 $t$ 是 $R$ 的一个元组。$t[A_i]$ 则表示元组 $t$ 中相应于属性 $A_i$ 的一个分量。
2. 若 $A={A_{i1},A_{i2},…,A_{ik}}$，其中 $A_{i1},A_{i2},…,A_{ik}$ 是 $A_1, A_2, …,A_n$ 中的一部分，则称 $A$ 为属性列或属性组。$t[A]=(t[A_{i1}],t[A_{i2}],…,t[A_{ik}])$ 表示元组 $t$ 在属性列 $A$ 上诸分量的集合，$\overline{A}$ 则表示 ${A_{1},A_{2},…,A_{n}}$ 中去掉 ${A_{i1},A_{i2},…,A_{ik}}$ 后剩余的属性组。
3. $R$ 为 $n$ 目关系，$S$ 为 $m$ 目关系，$t_r\in R$，$t_s\in S$，$t_rt_s$ 称为元组的连接 (concatenation) 或元组的串接。它是一个 $n+m$ 列数组。

4. 给定一个关系 $R(X,Z)$，$X$ 和 $Z$ 为属性组，当 $t[X=x]$ 时，$x$ 在 $R$ 中的象集 (images set) 定义为：$Z_x={t[Z]

   t\in R,t[X]=x}$，它表示 $R$ 中属性组 $X$ 上值为 $x$ 的诸元组在 $Z$ 上分量的集合。

1. 选择 (selection)

   选择又称为限制 (restriction)。

   $\sigma_F(R)={t\in R\wedge F(t)=’真’}$

2. 投影 (projection)

   关系 $R$ 上的投影是从 $R$ 中选择出若干属性列组成新的关系

   $\prod_Z(R)={t[A]

   t\in R}$

3. 连接 (join)

   连接也称为 $\theta$ 连接。它是从两个关系的笛卡尔积中选取属性间满足一定条件的元组

   $R\underset{A\theta B}{\Join}S={t_rt_s

   t_r\in R\wedge t_s\in S\wedge t_r[A]\theta t_s[B]}$

   其中，$A$ 和 $B$ 分别为 $R$ 和 $S$ 上列数相等且可比的属性组，$\theta$ 是比较运算符。连接运算从 $R$ 和 $S$ 的笛卡尔积 $R\times S$ 中选取 $R$ 关系在 $A$ 属性组上与 $S$ 关系在 $B$ 属性组上的值满足比较关系 $\theta$ 的元组

   • 等值连接

     $\theta$ 为 “=” 的连接运算称为等值连接。

   • 自然连接

     自然连接要求两个关系中进行比较的分量必须是同名的属性组，并且在结果中把重复的属性列去掉

     在自然连接中被舍弃的元组称为悬浮元组 (dangling tuple)

   • 外连接 (outer join)

     把悬浮元组也保存在结果关系中，而在其它属性上填空值 (NULL)

     • 左外连接 (left outer join)

       只保留左边关系 $R$ 中的悬浮元组

     • 右外连接 (right outer join)

4. 除运算 (division)

   设关系 $R$ 除以关系 $S$ 的结果为关系 $T$，则 $T$ 包含所有在 $R$ 但不在 $S$ 中的属性及其值，且 $T$ 中的元组与 $S$ 中的元组的所有组合都在 $R$ 中

   $R\div S={t_r[X]

   t_r\in R\wedge \prod_Y(S)\subseteq Y_x}$，其中 $Y_x$ 是 $x$ 在 $R$ 中的象集

关系运算的安全性约束

• 关系运算种把不产生无限关系和无穷验证的运算称为安全运算；其运算表达式称为安全表达式，对其所采用的限制称为安全约束。
• 关系代数是安全运算，关系演算则不一定是，所以对关系演算要进行安全约束
  • 在关系演算中，通常采用的安全约束方法是对 $\Phi$ 定义一个有限的符号集 DOM($\Phi$)，使 $\Phi$ 的运算结果及中间结果所产生的关系及其元组的各个分量都必须属于 DOM($\Phi$)
  • 设 $\Phi$ 是一个元组关系演算公式，为 DOM($\Phi$) 是由如下两类符号构成的集合
    • $\Phi$ 中的所有常量
    • $\Phi$ 中出现的所有元组的所有分量值

2.5 关系演算

2.5.1 元组关系演算

元组关系演算的基本结构是元组演算表达式。

• 形式定义：${t

  \Phi(t)}$

  • $t$ 为元组变量，如果元组变量前有“全称” ($\forall$) 或“存在” ($\exists$) 量词，则称其为约束元组变量，否则称为自由元组变量
  • $\Phi(t)$ 是元组关系演算公式
• 递归定义
  • 原子命题函数是公式，称为原子公式。原子公式有三类：
    • $R(t)$。$t$ 是关系 $R$ 中的一个元组
    • $t[i]\theta u[j]$
    • $t[i]\theta c$ 或 $c\theta t[i]$，$c$ 为常量
  • 如果 $\Phi_1$，$\Phi_2$ 是公式，则 $\Phi_1\vee\Phi_2,\ \Phi_1\wedge\Phi_2,\ \neg\Phi$ 也是公式
  • 如果 $\Phi$ 是公式，则 $\exists t(\Phi)$ 和 $\forall t(\Phi)$ 也是公式
• 优先级
  • 括号 > 算术比较运算符 > 量词 ($\exists$ > $\forall$) > 逻辑运算符 ($\neg$ > $\wedge$ > $\vee$)

2.5.2 域关系演算

• 形式定义：${(x_1x_2…x_k)

  \Phi(x_1,x_2,…,x_k)}$

  • $x_i$ 表示域变量，如果域变量前有“全称” ($\forall$) 或“存在” ($\exists$) 量词，则称其为约束域变量，否则称为自由域变量
  • $\Phi$ 是域关系演算公式
• 递归定义
  • 原子命题函数是公式，称为原子公式。原子公式有三类：
    • $R(x_1,x_2,…,x_k)$。$(x_1,x_2,…,x_k)$ 是关系 $R$ 中的一个元组，$x_i$ 是域变量或常量
    • $x_i\theta y_j$
    • $x_i\theta c$ 或 $c\theta x_i$，$c$ 为常量

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

SQL 的特点

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

SQL 语言的基本概念

数据库数据语言

分类：数据定义（描述）语言(DDL, Data Definition or Description Language)、数据操纵语言(Data Manipulation Language, DML)、数据控制语言(Data Control Language, DCL)

数据定义语言

包括模式 DDL，外模式 DDL，内模式 DDL

数据操纵语言

检索、插入、修改、删除

数据控制语言

完成数据库的安全性控制、完整性控制、并发控制等

关系数据语言的特点

• 一体化

  将数据的定义、查询、更新、控制等功能融为一体，只给用户提供一种称之为”查询语言“的语言。便于用户学习与使用。

• 非过程化

  用户只需提出”干什么“，而”怎样干“由 DBMS 解决。所以语言操作简单、易学、易用

• 面向集合的存取方式

  操作对象是一个或多个关系，操作的结果也是一个新关系

• 既可独立使用又可与诸语言嵌套使用

关系数据库语言优越性的根源

• 关系模型采用了最简单、最规范化的数据结构，这使 DML 大大简化

• 关系数据语言是建立在关系运算的数学基础上，可实现关系的垂直方向和水平方向的任意分割和组装操作，使得关系语言可随机地构造出用户需要的各种各样的新关系。

• 关系语言的核心是查询，所以又称为查询语言。

• 关系运算是涉及关系数据语言的基础，关系运算的分类也决定了关系语言的分类。

  

基本表与导出表

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

SQL 数据查询功能

查询的基本结构

查询的基本结构是 SELECT-FROM-WHERE 组成的查询块

SELECT 目标列
FROM 基本块（或视图）
WHERE 检索条件
ORDER BY 列名 ASC 或 DESC

• 查询的结果仍是一个表
• 查询块执行的过程是在表的水平方向上按“检索条件”选取元组，又在垂直方向上按 SELECT 指定的列进行投影。
• 查询块可进行关系函数中投影、选取、连接等操作的组合

查询语句实现细节

SELECT 目标列

• 若在目标列前添加 DISTINCT，则表示要删除 SELECT 结果中的重复行

FROM 基本块（或视图）

• 连表检索
  • 各个数据表之间用逗号相连
  • 连表时后面的检索条件中需要有连表条件
  • 如果连接的表中有属性名相同，要用表名作前缀加以区分（S.A, R.A）。
  • 若需要对表自身进行连接，则可以通过定义别名，将一个表看作两个表进行连接(FROM S X, S Y)
  • 外连接：在连接谓词的某一边加（* 或 +），则逻辑上为 * 所在边的表增加了一个空行。它可以与另一个表中所有不满足连接条件的元组进行连接，使这些元组能够输出。

WHERE 检索条件

• 检索条件可以包含如下运算符：

  • 比较运算符（=, <, >, <=, >=, !=）
  • 布尔运算符（AND, OR, NOT）
  • 括号

• 子查询（嵌套查询）

  • WHERE 子句中可以包含另一个查询块，该查询块称为子查询或嵌套查询，包含子查询的语句称为外部查询。
  • 分类
    • 普通子查询：与外部查询无关，可单独执行得一组值
    • 相关子查询：把外查询的列值作为检索条件的条件值
  • 如果子查询返回单值，可以直接用比较运算符 =, <, >, <=, >= 等连接子查询
  • 如果子查询返回一组值，则必须在比较运算符和子查询之间插入 ANY, ALL 等操作符。
  • IN 可以代替 =ANY，NOT IN 可以代替 != ALL
  • EXIST 表示存在量词 $\exist$
  • NOT EXIST 表示不存在
  • 将全程谓词表示为等价的存在谓词 $(\forall x)P=\neg(\exist x(\neg P))$
  • 将蕴含关系表示为等价的存在谓词 $p\rightarrow q=\neg p\vee q$

• 并、差、交检索

  • 并 UNION
  • 差 MINUS
  • 交 INTERSECT

  并、差、交检索的操作对象必须是相容的，是同类关系。即必须拥有相同数量与域的属性列。

ORDER BY 列名 ASC 或 DESC

• 该语句可省略
• 可以将结果按照指定列排序
• ASC 为升序，DESC 为降序，缺省则默认为升序

库函数

• COUNT() 按列值计个数，COUNT(*) 对行记数
• SUM() 对数值列求总和
• AVG() 求数值列的平均值
• MAX() 在列中找出最大值
• MIN() 在列中找出最小值

只能在 SELECT 子句以及 HAVING 子句中出现。

分组检索

按属性列（列组）将关系的元组分组，每组在这些分组属性列（列祖）上具有相同值，对每一组执行 SELECT 操作。

分组子句

GROUP BY 列名
[HAVING 条件表达式] # 分组条件

算数表达式值的检索

SELECT 子句中，可包括由属性列、常数、库函数、算数运算符 + - * / 等组成的算数表达式

检索结果数据项名可用表达式表示或用“别名”表示

部分匹配查询

使用谓词 LIKE 或 NOT LIKE，一般形式：<列名> LIKE/NOT LIKE <字符串常量>

• <列名> 必须为字符型或变长字符型
• <字符串常量>可包含两个特殊符号 % 和 _
  • %：代表任意序列的 0 个或多个字符
  • _：代表任意单个字符

SQL 数据定义功能

操作对象	创建	删除	修改
基本表	Create Table	Drop Table	Alter Table
视图	Create View	Drop View
索引	Create Index	Drop Index

定义基本表

Create Table <表名>
(
    <列名> <数据类型> [<列级完整性约束>]
    [{,<列名> <数据类型> [<列级完整性约束>]}]
    [{, [<表级完整性约束>]}]
);

• 完整性约束
  • NULL / NOT NULL
  • UNIQUE
  • PRIMARY KEY
  • FOREIGN KEY
  • CHECK

修改基本表

Alter Table <表名>
[Add <新列名> <数据类型> [<完整性约束>]]
[Drop <完整性约束名>]
[Modify <列名> <数据类型>]

删除基本表

Drop Table <表名>

SQL 数据类型

数据类型	说明
char(n)	固定长度的字符串
varchar(n)	可变长字符串
int	整数
smallint	小整数类型
numeric(p, q)	定点数共 p 位，小数点右边 q 位
Real, double precision	浮点数域双精度浮点数，精度域机器有关
Float	n 位的精度浮点数
date	日期（年、月、日）
time	时间（小时、分、秒）
interval	两个 date 或 time 类型数据之间的差

索引操作

定义索引

Create [Unique] [Cluster] Index <索引名>
On <表名> (<列名> [次序] [, <列名> [次序]]);

删除索引

Drop Index <索引名>

视图操作

视图的作用

• 能够简化用户操作
• 使用户能够以多种角度看待同一数据
• 提供了一定程度的逻辑独立性
• 能够对数据图个安全保护

定义视图

Create View <视图名>
[(<列名> [, <列名>] ...)]
As <子查询>
[With Check Option]

删除视图

Drop View <视图名>

查询视图

视图消解 (View Resolution)

DBMS 执行对视图的查询时，从数据字典中取出视图的定义，把定义中的子查询和用户的查询结合起来，转换成等价的对基本表的查询，然后再执行修正的查询。这一转换的过程称为视图消解。

SQL 数据更新

插入数据——Insert 语句

• 插入单个元组

  Insert Into <表明> [(<属性列> [{, <属性列>}])]
  Values (<值> [{, <值>}])
  

• 插入子查询结果

  Insert Into <表名> [(<属性列> [{, <属性列>}])]
  <子查询>
  

修改数据——Update 语句

Update <表名>
Set <列名> = <表达式> [{, <列名> = <表达式>}]
[Where <条件>]

删除数据——Delete 语句

Delete From <表名> [Where <条件>]

空值

空值的运算

空值是“不知道”或“不存在”或“无意义”的值，用 NULL 表示

• 属性定义有 NOT NULL 或 UNIQUE 约束以及主属性，都不可取空值

• 空值与另一个值的算数运算结果为 NULL，与另一个值的比较运算结果为 UNKWOWN

• TRUE, FALSE, UNKNOWN 的三值逻辑

  逻辑表达式	值
  T AND U, U AND U	U
  F AND U	F
  F OR U, U OR U	U
  T OR U	T
  NOT U	U

空值的判断

判断属性是否为空值，用 IS NULL 或 IS NOT NULL 来表示

SQL 数据控制功能

• 定义完整性约束条件
• 支持事务操作
• 提供安全控制功能
  • 授权
    • GRANT <权限> [ON <对象类型> <对象名>] TO <用户>
  • 收回权限
    • REVOKE <权限> [ON <对象类型> <对象名>] FROM <用户>

嵌入式 SQL 的意义

• 嵌入式 SQL 把 SQL 语句嵌入到高级语言中
• 嵌入式 SQL 把 SQL 的最佳特性与程序设计语言的最佳特性（如过程处理能力）结合起来，使 SQL 功能最强，灵活性更强。

第六章 关系数据理论

6.1 问题的提出

本章中把关系模式看作一个三元组 $R<U, F>$，其中 ：

• $R$ 为关系名
• $U$ 为一组属性
• $F$ 为属性组 $U$ 上的一组数据依赖

概念

第一范式

每个分量必须是不可分的数据项，满足这个条件的关系模式就属于第一范式 (1NF)

存在的问题：

• 数据冗余
• 更新异常 (update anomalies)
• 插入异常 (insertion anomalies)
• 删除异常 (deletion anomalies)

一个好的关系模式应当不会发生插入异常、删除异常和更新异常，数据冗余应尽可能少。

数据依赖

数据依赖是一个关系内部属性与属性之间的一种约束关系，这种约束关系是通过属性间值的相等与否体现出来的数据间的相关联系。

函数依赖 (Functional Dependency, FD)

多值依赖 (Multi-Valued Dependency, MVD)

6.2 规范化

6.2.1 函数依赖

函数依赖

设 $R(U)$ 是属性集 $U$ 上的关系模式，$X$，$Y$ 是 $U$ 的子集，若对于 $R(U)$ 的任意一个可能的关系 $r$，$r$ 中不可能存在两个元组在 $X$ 上的属性值相等，而在 $Y$ 上的属性值不等，则称 $X$ 函数确定 $Y$ 或 $Y$ 函数依赖于 $X$，记作 $X\rightarrow Y$

函数依赖和别的数据依赖一样是一个语义范畴的概念，只能根据语义来确定一个函数依赖。

平凡 & 非平凡函数依赖

非平凡函数依赖

$X\rightarrow Y$，但 $Y\not\subseteq X$，则称 $X\rightarrow Y$ 是非平凡的函数依赖

平凡函数依赖

$X\rightarrow Y$，但 $Y\subseteq X$，则称 $X\rightarrow Y$ 是平凡的函数依赖

完全 & 部分函数依赖

完全函数依赖

在 $R(U)$ 中，如果 $X\rightarrow Y$，并且对于 $X$ 的任何一个真子集 $X’$，都有 $X’\not\rightarrow Y$，则称 $Y$ 对 $X$ 是完全函数依赖，记作 $X\overset{F}{\rightarrow}Y$

部分函数依赖 (partial functional dependency)

记作 $X\overset{P}{\rightarrow}Y$

传递函数依赖 (transitive functional dependency)

在 $R(U)$ 中，如果 $X\rightarrow Y (Y\not\subseteq X),Y\not\rightarrow X, Y\rightarrow Z, Z\not\subseteq Y$ 则称 $Z$ 对 $X$ 传递函数依赖，记为 $X\overset{t}{\rightarrow}Y$ 或 $X\overset{传递}{\rightarrow}Y$

6.2.2 码

候选码 (Candidate key)

关系中的某一属性组，若它的值为一标识了一个元组，并具有最小性，则称该属性组位候选码。

设 $K$ 为 $R<U,F>$ 中的属性或属性组合，若 $K\overset{F}{\rightarrow} U$，则 $K$ 为 $R$ 的候选码 (candidate key)

超码

如果 $U$ 函数依赖于 $K$，即 $K\rightarrow U$，则称 $K$ 为超码 (surpkey)

候选码是一类特殊的超码，即候选码的超集（如果存在）一定是超码，候选码的任何真子集一定不是超码

主码

若候选码多于一个，则选定其中的一个为主码 (primary key)

主属性

包含在任何一个候选码中的属性称为主属性 (prime attribute)

非主属性 (非码属性)

不包含在任何一个候选码中的属性称为主属性 (nonprime attribute) 或 (non-key attribute)

全码

整个属性组是码

外部码 (外码)

关系模式 $R$ 中属性或属性组 $X$ 并非 $R$ 的码，但 $X$ 是另一个关系模式的码，则称 $X$ 是 $R$ 的外部码 (foreign key)，简称外码。

6.2.3 范式

关系数据库中的关系是要满足一定要求的，满足不同程度要求的为不同范式。

低一级范式的关系模式可以通过模式分解 (schema decomposition) 转化为若干个高一级范式的关系模式的集合，这种过程就叫规范化 (normalization)。

6.2.4 2NF

若 $R\in$ 1NF，并且每一个非主属性完全函数依赖于任何一个候选码，则 $R\in$ 2NF

不属于 2NF 的问题

• 插入异常
• 删除异常
• 修改复杂

6.2.5 3NF

设关系模式 $R<U,F>\in$ 1NF，若 $R$ 中不存在这样的码 $X$，属性组 $Y$ 及非主属性 $Z (Z\not\subseteq Y)$ 使得 $X\rightarrow Y$，$Y\rightarrow Z$ 成立，$Y\not\rightarrow X$，则称 $R<U, F>\in$ 3NF

若 $R\in$ 3NF，则每一个非主属性既不转递依赖于码（任意一个候选码），也不部分依赖于码，也不部分依赖于码

6.2.6 BCNF

关系模式 $R<U, F>\in$ 1NF，若 $X\rightarrow Y$ 且 $Y\not\subseteq X$ 时 $X$ 必含有码，则 $R<U, F>\in$ BCNF

关系模式 $R<U, F>$ 中，若每一个决定因素都包含码，则 $R<U,F>\in BCNF$

6.2.7 多值依赖

多值依赖的定义

设 $R(U)$ 是属性集 $U$ 上的一个关系模式。$X$，$Y$，$Z$ 是 $U$ 的子集，并且 $Z=U-X-Y$。关系模式 $R(U)$ 中多值依赖 $X\rightarrow\rightarrow Y$ 成立，当且仅当对 $R(U)$ 的任一关系 $r$，给定的一对 $(x,z)$ 值，有一组 $Y$ 值，这组值仅仅决定于 $x$ 值而与 $z$ 值无关。

多值依赖的性质

1. 多值依赖具有对称性

若 $X\rightarrow\rightarrow Y$，则 $X\rightarrow\rightarrow Z$，其中 $Z=U-X-Y$

1. 多值依赖具有传递性

   若 $X\rightarrow\rightarrow Y$， $Y\rightarrow\rightarrow Z$，则 $X\rightarrow\rightarrow Z-Y$

2. 函数依赖可以看作是多值依赖的特殊情况

   若 $X\rightarrow Y$，则 $X\rightarrow\rightarrow Y$

3. 若 $X\rightarrow\rightarrow Y$，$X\rightarrow\rightarrow Z$，则 $X\rightarrow\rightarrow YZ$

4. 若 $X\rightarrow\rightarrow Y$，$X\rightarrow\rightarrow Z$，则 $X\rightarrow\rightarrow Y\cap Z$

5. 若 $X\rightarrow\rightarrow Y$，$X\rightarrow\rightarrow Z$，则 $X\rightarrow\rightarrow Y-Z$，$X\rightarrow\rightarrow Z-Y$

多值依赖与函数依赖的区别

1. 多值依赖的有效性与属性集的范围有关
2. 若函数依赖 $X\rightarrow Y$ 在 $R(U)$ 上成立，则对于任何 $Y’\subset Y$ 均有 $X\rightarrow Y’$ 成立。而多值依赖 $X\rightarrow\rightarrow Y$ 若在 $R(U)$ 上成立，却不能断言对于任何 $Y’\sub Y$ 有 $X\rightarrow\rightarrow Y’$ 成立。

6.2.8 4NF

关系模式 $R<U,F>\in 1NF$，如果对于 $R$ 的每个非平凡多值依赖 $X\rightarrow\rightarrow Y(Y\not\subseteq X)$，$X$ 都包含码，则称 $R<U,F>\in$ 4NF

4NF 就是限制关系模式的属性之间不允许有非平凡且非函数依赖的多值依赖。

6.2.9 规范化小结

规范化的基本思想就是逐步消除数据依赖中不合适的部分，即“一事一地”的模式设计原则。规范化实质上是概念的单一化。

关系模式的规范化过程是通过对关系模式的分解来实现的，即把低一级的关系模式分解为若干个高一级的关系模式。这种分解不是唯一的。

6.3 数据依赖的公理系统

逻辑蕴含

对于满足一组函数依赖 F 的关系模式 $R<U,F>$，其任何一个关系 $r$，若函数依赖 $X\rightarrow Y$ 都成立（即 $r$ 中任意两元组 $t$、$s$，若 $t[X]=s[X]$，则 $t[Y]=s[Y]$），则称 F 逻辑蕴含 $X\rightarrow Y$

Armstrong 公理系统 (Armstrong’s axiom)

设 $U$ 为属性集总体，$F$ 是 $U$ 上的一组函数依赖，于是又关系模式 $R<U,F>$，对 $R<U,F>$ 来说有以下的推理规则：

• 自反律 (reflexivity rule)

  若 $Y\subseteq X\subseteq U$，则 $X\rightarrow Y$ 为 $F$ 所蕴含。

• 增广律 (augmentation rule)

  若 $X\rightarrow Y$ 为 $F$ 所蕴含，且 $Z\subseteq U$，则 $XZ\rightarrow YZ$ 为 $F$ 所蕴含。

• 传递律 (transitivity rule)

  若 $X\rightarrow Y$ 及 $Y\rightarrow Z$ 为 $F$ 所蕴含，则 $X\rightarrow Z$ 为 $F$ 所蕴含。

Armstrong 公理系统是有效的，完备的。

• 有效性

  由 $F$ 出发根据 Armstrong 公理推导出来的每一个函数依赖一定在 $F^+$ 中

• 完备性

  $F^+$ 中的每一个函数依赖，必定可以由 $F$ 出发根据 Armstrong 公理推导出来

推理规则

• 合并规则 (union rule)

  由 $X\rightarrow Y$，$X\rightarrow Z$，有 $X\rightarrow YZ$

• 伪传递规则 (pseudo transitivity rule)

  由 $X\rightarrow Y$，$WY\rightarrow Z$，有 $XW\rightarrow Z$

• 分解规则 (decomposition rule)

  由 $X\rightarrow Y$ 及 $Z\subseteq Y$，有 $X\rightarrow Z$

引理

$X\rightarrow A_1A_2…A_k$ 成立的充分必要条件是 $X\rightarrow A_i(i=1,2,…,k)$ 成立

闭包 (closure)

在关系模式 $R<U,F>$ 中为 $F$ 所逻辑蕴含的函数依赖的全体叫做 $F$ 的闭包，记为 $F^+$

属性集关于函数依赖的闭包

定义

设 $F$ 为属性集 $U$ 上的一组函数依赖，$X$、$Y\subseteq U$，$X_F^+={A

X\rightarrow A 能由 F 根据 Armstrong 公理导出}$，$X_F^+$ 称为属性集 $X$ 关于函数依赖集 $F$ 的闭包。

算法

求属性集 $X(X\subseteq U)$ 关于 $U$ 上的函数依赖集 $F$ 的闭包 $X_F^+$

• 输入：$X$、$F$

• 输出：$S_F^+$

步骤：

1. 令 $X^{0} = X$, $i=0$

2. 求 $B$，这里 $B = {A

   (\exists V)(\exists W)(V\rightarrow W\in F\wedge X\subseteq X^{(i)}\wedge A\in W)}$

3. $X^{(i+1)}=B\cup X^{(i)}$

4. 判断 $X^{(i+1)} = X^{(i)}$

5. 若 $X^{(i+1)}$ 与 $X^{(i)}$ 相等或 $X^{(i)} = U$，则 $X^{(i)}$ 就是 $X_F^+$，算法终止

6. 若否，则 $i=i+1$，返回第二步

引理

设 $F$ 为属性集 $U$ 上的一组函数依赖，$X$、$Y\subseteq U$，$X\rightarrow Y$ 能由 $F$ 根据 Armstrong 公理导出的充分必要条件是 $Y\subseteq X_F^+$。

定理

Armstrong 公理系统的有效的、完备的

等价 / 覆盖

定义

如果 $G^+ = F^+$，就说函数依赖集 $F$ 覆盖 $G$ 或 $F$ 与 $G$ 等价。

定理

$G^+=F^+$ 的充分必要条件是 $G^+\subseteqF^+$ 和 $G^+ \subseteq F^+$

最小依赖集 (minimal cover)

定义

如果函数依赖集 $F$ 满足下列条件，则称 $F$ 为一个极小函数依赖集，亦称为最小依赖集或最小依赖

1. $F$ 中任一函数依赖的右部仅含有一个属性。
2. $F$ 中不存在这样的函数依赖 $X\rightarrow A$，使得 $F$ 与 $F-{X\rightarrow A}$ 等价
3. $F$ 中不存在这样的函数依赖 $X\rightarrow A$，$X$ 有真子集 $Z$ 使得 $F-{X\rightarrow A}\cup{Z\rightarrow A}$ 与 $F$ 等价

算法

1. 逐一检查 $F$ 中各函数依赖 $FD_i:X\rightarrow Y$，若 $Y=A_1A_2…A_k,k\ge 2$，则用 ${X\rightarrow A_j

   j=1,2,…,k$ 来取代 $X\rightarrow Y$

2. 逐一检查 $F$ 中各函数依赖 $FD_i:X\rightarrow A$，令 $G=F-{X\rightarrow A}$，若 $A\inX_G^+$，则从 $F$ 中去掉此函数依赖（因为 $F$ 与 $G$ 等价的充要条件是 $A\in X_G^+$）
3. 逐一去除 $F$ 中各函数依赖 $FD_i:X\rightarrow A$，设 $X=B_1B_2…B_m,m\ge 2$，逐一考查 $B_i(i=1,2,…,m)$，若 $A\in(X-B_i)_F^+$，则以 $X\rightarrow B_i$ 取代 $X$（因为 $F$ 与 $F-{X\rightarrow A}\cup {Z\rightarrow A}$ 等价的充要条件是 $A\in Z^+$，其中 $Z=X-B_i$）

6.4 模式分解

第七章 数据库设计

7.1 数据库设计概述

数据库设计是指对于一个给定的应用环境，构造（设计）优化数据库逻辑模式和物理结构，并据此建立数据库及其应用系统，使之能够有效地存储和管理数据，满足各种用户的应用需求，包括信息管理要求和数据操作要求。

• 数据库设计的方法
  • 手工试凑法（直接设计法）：根据应用的数据要求于处理要求，直接涉及数据库的结构。
  • 规范设计法：运用软件工程的思想和方法，把整个设计过程划分为若干阶段，把复杂的大问题分为若干相对简单的小问题，每个阶段只解决整个设计中的部分问题。

7.1.1 数据库设计的特点

1. 数据库建设的基本规律

   数据的收集、整理、组织和不断更新是数据库建设中的重要环节。

2. 结构（数据）设计和行为（处理）设计相结合

7.1.3 数据库设计的基本步骤

1. 需求分析

   数据库设计的基础。

   • 对应用环境进行详细调查。收集支持系统目标的基础数据及其处理。

2. 概念结构设计

   数据库设计的关键。

   • 通过对用户需求进行综合、归纳与抽象。形成独立于数据库逻辑结构于具体 DBMS 的概念模型，可以用 E-R 图等表示。

3. 逻辑结构设计

   • 将概念结构转换为某个 DBMS 所支持的数据模型，并进行优化。再将得到的逻辑结构转换成特定的 DBMS 能处理的模式、子模式。

4. 物理结构设计

   为逻辑数据模型选取一个最适合应用环境的物理结构（包括存取结构和存取方法）

   • 设计数据库在物理设备上的存储结构和存取方法。一般分为两步：一是确定数据库的内模式；二是对物理结构进行时间与空间效率的评价

5. 数据库实施

   运用数据库管理系统提供的数据库语言及其宿主语言，根据逻辑设计和物理设计的结果建立数据库，编写和调试应用程序，组织数据入库，并进行试运行。

   • 是建立数据库的过程。用 DBMS 的 DDL 描述三级模式，并调试产生目标模式。开发应用程序，组织数据入库并试运行

6. 数据库运行和维护

   数再运行过程中需要不断对其进行评估、调整与修改。

   • 在数据库正式运行后，由 DBA 执行对数据库经常性的维护工作，包括数据库转储与恢复、对数据库控制、数据库性能监控、数据库的重组与重构。

7.1.4 数据库设计过程中的各级模式

7.2 需求分析

7.2.1 需求分析的任务

调查的重点是“数据”和“处理”，通过调查、收集与分析，获得用户对数据库的如下要求：

1. 信息要求：指系统中所涉及的数据及数据之间的联系。具体收集数据的名称、类型、长度等，确定数据之间联系的类型。
2. 处理要求： 指用户要完成什么处理功能，对处理的响应时间和处理方式的要求。
3. 安全性与完整性要求

7.2.2 需求分析的方法

1. 首先调查用户的实际要求，与用户达成共识
2. 分析与表达这些需求。
   • 用数据流图表达数据和处理之间的关系
   • 用数据字典描述系统中的各类数据

数据流图 （Data Flow Diagram, DFD 图）

以图形方式来表达系统的功能、数据在系统内部的逻辑流向和逻辑变换过程。

数据字典

是对数据的集中的系列说明。包含每一个数据元素的名字、含义等各方面的描述。

• 从数据流图中提取出所有原子数据项
• 把有联系的数据项组合起来形成数据组
• 以数据组为单位，写出数据项的如下定义：
  • 语义定义：名字，实际含义等
  • 类型定义：数据类型，数据宽度，小位数等
  • 完整性约束定义：值约束、空值约束以及其他比较复杂的完整性约束。
• 根据用户和实际领域的信息模型需要补充其他数据项及其定义。

7.2.3 数据字典

数据字典是进行详细的数据收集和数据分析所获得的主要成果。它是关于数据库中数据的描述，即元数据，而不是数据本身。数据字典是再需求分析阶段建立，在数据库设计过程中不断修改、充实和完善的。它在数据库设计中占有很重要的地位。

数据字典包括：

1. 数据项
2. 数据结构
3. 数据流
4. 数据存储
5. 处理过程

7.3 概念结构设计

E-R 图

E-R 图的组成

• 实体

  用长方形表示实体型，在框内写上实体名

• 联系

  用菱形表示实体间的联系，菱形框内写上联系名。用无向边把菱形分别与有关实体相连，在无向边旁标上联系的类型。若联系也具有属性，则属性和菱形也能用无向边连接上。

• 属性

  用椭圆形表示实体的属性，并用无向边把实体于其属性连接起来。

原则

• 属性必须是不可分的数据项，不能是另一些属性的聚集
• 属性不能与其它实体具有联系，即 E-R 图中所表示的联系是实体之间的联系
• 实体和描述它的属性之间保持 1:1 或 n:1 的联系。对于 1:n 或 n:m 的联系，要进行调整，一般可将该属性上升为实体。

局部 E-R 图设计步骤

1. 选择局部应用
2. 以需求分析中得到的数据元素表为基础，利用数据抽象机制，建立实体模型
3. 确定实体之间的联系类型。用 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. 把 E-R 图中实体用符号表示
    2. 把每一对 n:1、1:1 或 n:m 联系表示为实体码之间的函数依赖表达式 X $\rightarrow$ Y
    3. 利用函数依赖集的最小覆盖算法进行极小化处理。
    4. 考察 D 中每一个函数依赖表达式，确定是否为冗余联系
    5. 去掉冗余联系后形成基本 E-R 图。

7.4 逻辑结构设计

逻辑结构设计的任务就是把概念结构转换为选用的 DBMS 所支持的数据模型的过程。

过程

1. 形成初始关系数据库模式
2. 关系模式规范化
3. 关系模式优化
4. 子模式定义

E-R 图向关系模型的转换规则

• 一个实体型转换为一个关系模式。实体的属性就是关系的属性，实体的码就是关系的码。
• 一个联系转换为一个关系模式。与该联系相连的各实体的码以及联系的属性转换为关系的属性：
  • 若联系为 1:1，则每个关系的码均是该关系的候选码
  • 若联系为 1:n，则该关系的码是 n 端实体的码
  • 若联系为 n:m，则该关系的码是诸实体码的组合
• 三个或三个以上实体间的多元联系，转换为一个关系模式，与该多元联系相连的各实体的码以及联系的属性转换为关系的属性，而关系的码为各实体码的组合
• 具有相同码的关系可以合并
• 弱实体类型的转换
  • 对于每个弱实体类型，创建一个新的关系，该关系中包含所有弱实体类型的属性。
  • 把标识关系（被依赖关系）的主码添加到新关系中，并将其作为新关系的外码
  • 新关系的主码是标识关系的主码和弱实体类型的部分标识（码）的组合
• 超类 / 子类联系的转换
  • 为超类和每个子类创建单独的关系
  • 在超类所创建的关系中，包含所有子类成员都共有的属性，包括主码
  • 在超类中包含一个（或多个）属性作为子类判定符
  • 在为每个子类所创建的关系中，包含超类的主码以及子类特有的属性

关系模型的规范化与优化

规范化

• 按照数据依赖的理论，逐一分析转换所得关系模式，判断是否存在部分函数依赖、传递函数依赖、多值依赖等，确定它们的范式等级

优化

• 按应用系统的处理要求，确定是否进行关系模式合并或分解

• 为了提高存取效率和存储空间的利用率，可以对关系模式进行必要的分解

  • 水平分解

    是把关系的元组分为若干子集合，定义每个子集合为一个子关系，以提高系统效率

    • 80/20 原则

      可以把经常使用的那一部分数据分解出来作为一个关系，其他数据作为另一个关系

    • 数据分片

      如果关系 R 上具有 n 个事务，而且大多数事务存取的数据不相交，则 R 可以分解为少于或等于 n 个子关系。

  • 垂直分解

    是把关系模式 R 的属性分解为若干子集合，形成若干子关系模式，

    • 垂直分解的原则是，经常在一起使用的属性从 R 中分解出来形成一个子关系模式
    • 垂直分解必须确保无损连接性和保持函数依赖。

7.5 物理结构设计

确定数据库的存储结构

• 确定存放位置
  • 经常存取部分和存取频率较低部分分开存放
  • 数据和日志备份放于不同的磁盘上
• 确定系统配置
  • 确定系统配置变量、存储分配参数，进行物理优化

选择关系的存取方法

存取方法是使事务能够快速存取数据库中数据的技术

索引方法

• 基本概念
  • 为了加速所需数据的访问
  • 索引记录 / 索引项，是索引文件的记录，包括两个域：
    • 索引域：存储数据文件中一个或一组域的一个值
    • 指针：指向索引域值为 K 的记录所在磁盘块的地址
• 常用 B+ 树索引
• 索引存取方法的选择
  • 选择索引域原则
    • 经常在查询条件中出现的属性
    • 经常作为最大值和最小值库函数的参数
    • 经常作为连接属性
  • 索引并非越多越好

聚集方法

• 基本概念
  • 把关系中某个属性 / 组（聚集键）值相同的记录集中存放在连续的物理块，称为聚集。能够提高该属性的查询速度。
• 一个关系只能参加一个聚集
• 一般原则
  • 经常进行连接操作的关系可以建立聚集
  • 单个关系的某组属性经常进行相等比较
  • 关系的某个属性组值重复率高
• 注意问题
  • 建立和维护聚集系统开销很大，对于更新操作远远多余连接操作的关系不应该使用聚集方法。

HASH 方法

• 一种支持快速存取的文件存储方法
• 基本概念
  • 通过 HASH 函数将记录关键字转换成地址
• 如果关系的属性主要出现在等连接条件中，或出现在相等比较条件中，而且满足以下条件之一，可以选择该方法：
  • 关系的大小可预知，而且不变
  • 如果关系大小动态改变，则徐 DBMS 提供动态 HASH 存取方法。

第六章 存储管理和索引

存储体系结构

• 数据只有被放入内存才能被处理
• DBMS 设定数据库的基本存储是在磁盘上，DBMS 的组件管理内存与外存数据的交换

• DBMS 存储管理的目标

  最小化磁盘和主存间传输存储块的数量，即最小化磁盘存取次数

磁盘

结构

磁盘块由若干个扇区组成，是存储分配和检索的逻辑单元，大小一般在 4k-16k 之间，数据以块为单位在磁盘和主存之间传输。页面 (page) 通常指块。

访问时间

• 寻道时间

  磁盘臂定位时间

• 旋转时间

  等待被访问的扇区出现在读写头下方的时间

• 传输时间

  从磁盘读取数据或向磁盘存储数据的时间

存储管理系统

• 数据库 - 文件 - 块 / 页

  • 数据库

    由若干文件组成，这些文件采用专有的格式。操作系统不能获取这些文件内容的任何信息

  • 文件

    由若干个定长的存储单元 / 存储块 / 页构成

  • 块 / 页

    存储分配和数据传输的单位

数据库的物理结构

• 数据库中的表被映射为底层存储中的文件

• 一个文件在逻辑上被组织为记录的序列，记录被映射到磁盘块上

• 文件在存储中由若干磁盘块构成，块是存储分配和数据传输的单位

• 一个块可以包含几个记录，每条记录被完全包含在单个块中

• 表所占磁盘块的分配方法

  • 连续分配

    数据被分配到连续的磁盘块上

  • 链接分配

    数据块中包含指向下个数据块的指针

  • 按簇分配

    簇是连续的几个磁盘块，簇之间用指针连接

  • 索引分配

    索引块中存放指向数据块的指针

数据库页 / 磁盘块

页是固定大小的数据块

• 每个页有唯一的标识符 (ID)，DBMS 将页 ID 映射为页的物理位置
• 每个页由头部 Header 和数据组成
  • Header 包含了页中的元数据，如页大小、Checksum、DBMS 版本等

分槽 (slot) 页结构

• Header 记录了已使用的槽数，以及最后一个被使用槽的起始位置偏移量，以及一个槽数组
• 槽数组保存了每个元组的起始位置偏移量
• 增加记录时，槽数组从开始到尾部的方向增长，而记录数据则从数据区的尾部到开始的方向增长。当槽数组与元组数据连接到一起时，认为页满
• 便于存储变长记录

数据库记录

记录是字节序列，DBMS 负责将该序列解释为属性类型和值

• 记录头部

  包含元组的元数据，例如加锁信息等

• 记录数据

  属性的实际数据。属性一般按表定义中的顺序存储。多数 DBMS 不允许一个记录大小超过一个页

• 唯一标识符 ID

  • 每个记录被分配了一个 ID
  • 最常见的形式：页 ID+ (offset 或槽)
  • 应用程序不能依赖该 ID 进行唯一性标识

文件中记录的组织方式

• 堆(Heap)：记录可以存放在文件空间中的任何位置

  • 链表方式

    在文件开始维护一个 header 页，该页存储了空白页链表头指针和数据页链表头指针，每个页记录了当前包含的空槽数

  • 页目录方式

    DBMS 维护特殊页保存文件中的数据页的位置，并记录每个页中空槽数

• 顺序(Sequential)：基于每个记录的搜索码值顺序排列

  • 文件中记录按搜索码排序。搜索码可以是任意属性或属性集合
  • 通过指针把记录链接起来，每个记录的指针指向按搜索码排列的下一条记录
  • 可以高效的按某个搜索码处理记录

• 索引(Indexing)：按某种顺序有序存储

• 散列 (Hashing)：在搜索码上的 hash 函数，计算出记录在文件中存放的块

• 聚集(Clustering)：将有联系的记录存储在同一个块上，以最小化 I/O 次数

  • 具有相同或相似属性值的记录存储于连续的磁盘块中
  • 聚集码是一种属性，它定义了哪些记录被存储在一起
  • 多表聚集：将多个关系存储于一个文件中，在每个块中存储两个或更多关系的相关记录，可以加快特定的连接查询，但会使单个表的访问变慢

缓存管理系统

• 块 / 页是存储分配和数据交换的单位
• 管理目标：最小化磁盘和主存间传输存储块的数量，即最小化磁盘存取次数；实现手段是在主存中保持尽量多的块
• 缓冲区：是主存中可以存储磁盘块副本的区域
• 缓存管理器：负责缓存空间分配，内外存交换

缓冲区组织与管理

• 缓冲区被组织为一个固定大小的页面数组，每个元素称为帧，存放磁盘上的一个页 / 块
• 缓冲区元数据——页表 (page table)，跟踪当前内存中的所有页，并保存了每个页的元数据，包括
  • Dirty Flag：由修改页的线程设置，通知存储管理器该页必须写回磁盘
  • Pin / Reference 计数器：在一页被进程读写操作前要钉住 (Pin)，方式该页被移出，操作结束后解除钉（计数器减 1），只有计数器 = 0 时，才能被移出或写回磁盘
• 缓冲区的共享锁与排它锁
  • 缓冲区管理器提供封锁系统，允许数据库进程以共享或排他模式封锁页，在完成操作后释放封锁
  • 实现并发控制，读操作加共享锁，更新操作加排他锁
  • 加锁规则：一次只能由一个进程获得排它锁，共享锁与排它锁不能同时加，多个进程可以同时持有共享锁
• 缓冲区替换策略
  • 最近最少使用 (LRU, Least Recently Used) 策略及其改进算法

索引

基本概念

• 索引文件构成
  • 索引记录 / 索引项，是索引文件的记录，包括两个域：
    • 索引域（搜索码）：存储数据文件中一个或一组域（属性）
    • 指针：指向索引域值为 K 的记录所在磁盘块的地址
  • 索引将表中的部分属性进行组织或排序，使得利用这些属性能够快速有效进行表的访问
  • DBMS 负责在执行查询时使用最恰当的索引

索引的分类

• 基本类型

  • 排序索引

    索引项是排序的

  • 哈希索引

    索引项使用索引域上的 hash 函数确定位置

• 聚集索引与非聚集索引

  • 聚集索引

    索引项值排列顺序与记录在文件中的排列顺序一致，也成为主索引

  • 非聚集索引

    索引项指定的次序与文件中记录的排列顺序不同，也称为辅助索引

• 稠密索引与稀疏索引

  • 稠密索引

    对文件中的每个搜索码值都有一个索引项

  • 稀疏索引

    只有部分索引域值有索引记录，当文件记录以索引域排序时，可以采用

  相比稠密索引，稀疏索引占空间小且维护代价低，但定位记录慢。非聚集索引都是稠密索引

多级索引

• 对索引文件建立稀疏索引
  • 外层索引：基本索引的稀疏索引
  • 内层索引：基本索引文件

• 二叉树索引

• 多枝树索引

• B 树（平衡树）索引

  • 是附加限制条件的索引树。限制了每个节点放置关键字与指针的最小和最大个数：根节点有 [2, n] 个子节点，中间节点有 [n/2, n] 个子结点，叶节点有 [n/2, n-1] 个记录指针，n 值对于特定树是固定的。
    • 从树根到叶节点每条路径的长度都相同，因此所有的叶结点都在同一层上
    • B 树的关键字是散布在各层上

• B+ 树

  • 是 B 树的改进，把树中所有关键字都按递增次序从左到右安排在节点上，并且链接起来。B+ 树能同时进行随机查找和顺序查找。
  • 节点结构
    • 每个节点最多包含 n-1 个搜索码 / 索引码值 $K_1, K_2, …, K_{n-1}$，以及 n 个指针 $P_1, P_2, …, P_n$

• Hash 索引

  • 基于哈希表 (Hash Table) 实现

  • 哈希表实现 key 到 value 的映射。通过键值映射到表中一个位置来访问记录，这个映射函数叫做 Hash 函数，存放记录的数组叫做哈希表。

  • 哈希表

    • 哈希函数

      将很大的 key 空间映射到比较小的域，用于计算桶 / 槽数组的元素符号；非用于加密算法的哈希函数，计算速度快且碰撞率低

    • 哈希方案 (scheme)

      解决一个哈希值对应多条记录。最长使用溢出链接 (Chaining) 法

  • 分类

    • 静态哈希：哈希表的大小是固定的
      • 文件增大时，太多的溢出桶将降低访问性能
      • 数据规模缩小时，会造成空间浪费
    • 动态哈希：允许哈希表的大小动态修改
      • 定期重哈希：创建新的大的哈希表，把原表上的 key 重新哈希到新表上
      • 线性哈希：以一种递增的方式重新哈希

第七章 关系查询处理与查询优化

关系查询处理步骤

1. 查询分析

• 词法分析
• SQL 语法检查和语法分析

2. 查询检查

• 语义检查
• 存取权限检查
• SQL 语句转换为关系代数表达式（查询树 / 语法分析树）

3. 查询优化

• 选择一个高效执行的查询处理策略
• 生成查询计划

4. 查询执行

• 生成查询计划的代码
• 代码执行

查询代价的度量

假设存取一个块就需要进行一次磁盘访问，使用访问磁盘的块数作为估计代价的因素

查询操作的实现

选择运算实现算法

• 全表扫描法

  按照物理顺序读表的 M 块到内存，检查内存的每个元组 t，如果满足条件则输出 t，直到表所有块都经过上述检查

• 索引扫描法

  如果在选择条件的属性上有索引，先通过索引找到目标索引项，再通过索引项找到元组

连接运算实现算法

嵌套—循环法

• 两个连接的表，第一个表为外循环，另一个为内循环。

• 连接运算 $r \bowtie _{\theta} s$ 的实现算法，$r$ 是外循环表，$s$ 是内循环表

  

• 不需要索引，并使用于任何连接条件

• 需要检查两个关系中的每一对元组，代价高

• 如果连接操作使用的缓冲区的块数为 k，分配 (k-1) 块给外表 r，1 块给内表 s，则存取块数为：$b_r+\frac{b_r}{k-1}\times b_s$，其中 $b_r$ 为表 r 的块数，$b_s$ 为表 s 的块数

• 应选择较小的表作为外表

索引连接法

第二个表按照连接属性建索引，取第一个表元组的连接属性与第二个表元组的连接属性比较。

• 如果内层关系 s 的连接属性上有索引，则对于外层关系 r 中的每一个元组 $t_r$，可以用索引查找 s 中与 $t_r$ 满足连接条件的元组
• 如果 r 和 s 在连接属性上都有索引，则以元组较少的关系作为外层关系，代价最小

排序—合并法

两个表都按照连接属性排序，取第一个表元组的连接属性与第二个表元组的连接属性比较。

1. 将两个关系在连接属性上排序
2. 为每个关系分配一个指针，分别为 $p_r$ 和 $p_s$，对于 $p_r$ 指向 r 的一个连接属性值，移动 $p_s$ 找到 s 中与该值相等的元组，与 $p_r$ 指向的元组做连接，如此移动两个指针分别遍历 r 和 s

• 两个关系的每个块都只需要读一次，访问块数 = $b_r$ + $b_s$
• 只能用于等值连接或自然连接

Hash Join 法

连接属性作为 hash 码，用同一个 hash 函数把两个连接表的元组散列到同一个 hash 文件。

1. 哈希函数 h 用于划分两个关系，h 将连接属性值映射到 {0, 1, …, n} 集合上。将 r 的元组划分为 $r_0, r_1, …, r_n$ 个部分，如果 h($t_r$[JoinAttrs])=i，则元组 $t_r$ 将被放入 $r_i$，同理将 s 页划分成 $s_0, s_1, …, s_n$ 个部分
2. 对于某个连接属性值，若被哈希为 i，则 s 中相应的元组必定在 $s_i$ 中，而 r 中的元组必定在 $r_i$ 中，因此只需要将 $s_i$ 和 $r_i$ 中的元组相比较

适用于等值连接或自然连接

排序

• 内存中完全容纳的关系，可采用快速排序 (quicksort) 法等算法
• 内存无法容纳的关系，可采用外排序-归并算法

外排序-归并

1. 建立多个排序好的归并段 (run)，每个段仅包含关系的部分记录
2. 对归并段进行归并

其他运算

• 去重

  使重复数据向相邻，保留一个数据删除其它

  • 排序方法
  • 哈希方法

• 投影

  在每个元组上执行投影，之后再去重

• 集合运算——并、交、差

  • 类似排序-合并连接，排序然后对每个已排序的关系扫描一次
  • 类似 hash-join 将两个关系分区，再两个关系对应区中执行运算

• 库函数

  基于分组属性进行排序或散列以聚集同组的元组，再执行库函数

表达式的执行

可选方法包括物化 (materialized) 方法和流水线 (pipeline) 方法

物化方法

• 按次序每次只执行一个运算，运算结构被物化到一个临时关系中，这些临时关系一般需要写到磁盘上
• 方法适用性广泛，但临时表的写和读代价大

流水线方法

• 同时执行多个运算，将结果传递给下一个运算
• 不需要在磁盘上存储临时关系，代价小，但对有些运算不适用，如排序等

查询优化

查询优化目标：选择一个高效执行的查询处理策略，使得查询代价最小，即发个文磁盘的块数最少

分类

代数优化

关系代数表达式的优化，即按照一定的规则，改变代数表达式中操作的次序和组合

物理优化

存取路径和底层操作算法的选择。包括基于规则或基于代价等

查询优化的结果

查询计划：定义了每个操作的算法以及这些操作执行的顺序

代数优化

通过对关系代数表达式的等价变化来提高查询效率

• 关系代数表达式的等价

  指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的

关系代数表达式等价变换规则

1. 连接、笛卡尔积交换律 \(E_1 \times E_2 = E_2 \times E_1 \\ E_1 \bowtie E_2 = E_2 \bowtie E_1 \\ E_1 \underset{F}{\bowtie} E_2 = E_2 \underset{F}{\bowtie} E_1\)

2. 连接、笛卡尔积的结合律 \((E_1\times E_2)\times E_3 = E_1\times (E_2\times E_3)\\ (E_1\bowtie E_2)\bowtie E_3=E_1 \bowtie (E_2\bowtie E_3) \\ (E_1\underset{F_1}{\bowtie} E_2)\underset{F_2}{\bowtie} E_3 = E_1\underset{F_1}{\bowtie}(E_2\underset{F_2}{\bowtie}E_3)\)

3. 投影的串联定理 \(\Pi_{A_1, A_2,...,A_n}(\Pi_{B_1,B_2,...,B_m}(E)) = \Pi_{A_1, A_2,...,A_n}(E)\)

4. 选择的串联定律 \(\sigma_{F_1}(\sigma_{F_2}(E)) = \sigma_{F_1\wedge F_2}(E)\)

5. 选择与投影的交换律 \(\sigma_{F_1}(\Pi_{A_1, A_2, ..., A_n}(E)) = \Pi_{A_1, A_2,...,A_n}(\sigma_F(E))\)

6. 选择与笛卡尔积交换律

   • $F$ 中只有 $E_1$ 的属性

   • $F=F_1\wedge F_2$，且 $F_1$ 只有 $E_1$ 的属性，$F_2$ 中只有 $E_2$ 的属性

     $\sigma_F{E_1\times E_2}=\sigma_{F_1}(E_1)\times \sigma_{F_2}(E_2)$

   • $F_1$ 只有 $E_1$ 的属性，$F_2$ 有 $E_1$ 和 $E_2$ 的属性

     $\sigma_F(E_1\times E_2)=\sigma_{F_2}(\sigma_{F_1}(E_1)\times E_2)$

7. 选择与并的分配律

   $\sigma_F(E_1\cup E_2)=\sigma_F(E_1)\cup \sigma_F(E_2)$

8. 选择与差的分配律

   $\sigma_F(E_1-E_2)=\sigma_F(E_1)-\sigma_F(E_2)$

9. 选择对自然连接的分配律

   $\sigma_F(E_1\bowtie E_2)=\sigma_F(E_1)\bowtie\sigma_F(E_2)$

10. 投影与笛卡尔积的分配律

    $\Pi_{A_1, A_2,…,A_n,B_1,B_2,…,B_m}(E_1\times E_2)=\Pi_{A_1,A_2,…,A_n}(E_1)\times \Pi_{B_1,B_2,..,B_m}(E_2)$

11. 投影与并的分配律

    $\Pi_{A_1,A_2,…,A_n}(E_1\cup E_2)=\Pi_{A_1,A_2,…,A_n}(E_1)\cup\Pi_{A_1, A_2,…,A_n}(E_2)$

查询树

查询树的关系代数表达式的树形表示

• 操作的关系位于叶结点
• 关系运算位于内部节点
• 执行方式：自底向上执行，当一个内部节点的操作分量可用时，该节点的操作启动执行，执行结束后用结果关系代替该节点

查询树的构造

• 将 SQL 语句转换为关系代数表达式
  • SELECT 子句对应投影操作
  • FROM 子句对应笛卡尔积
  • WHERE 子句对应选择操作
• 将关系代数表达式转换为查询树

查询树的启发式优化（优化的一般准则）

• 选择运算尽早执行。是优化策略中最重要，最基本的一条（减少中间关系-减少元组数据）
• 投影运算尽早执行（减小中间关系-减少属性数目）
• 把投影运算和选择运算同时进行；把投影同其前或其后的双目运算结合起来（减少扫描关系的次数）
• 把某些选择同在它前面要执行的笛卡尔积结合起来称为一个连接运算（把笛卡尔积与选择转换为连接）
• 找出公共子表达式，把公共子表达式的结果写入中间文件，重复使用。（中间结果复用）

物理优化

• 选择高效合理的操作算法或存取路径，得到优化的查询计划
• 查用方法
  • 基于规则的启发式优化算法
  • 基于代价估算的优化算法
  • 两者结合的优化算法

基于启发式规则的存取路径选择优化

选择操作的启发式规则

• 对于小关系，使用全表顺序扫描
• 对于大关系：可以采用索引扫描法（如结果的元组数目较小），全表顺序扫描

连接关系的启发式规则

• 如果两个表都已经按照连接属性排序——排序-合并法
• 如果一个表在连接属性上有索引——索引连接法
• 如果连接属性上未排序且未建索引，且其中一个表较小——Hash Join 法
• 最后可选用嵌套循环法，并选择较小的表作为外循环表

查询优化的一般步骤

1. 把查询转换成语法树，如关系代数语法树
2. 把语法树利用代数优化转换成优化后的标准形式
3. 利用基于启发式规则的物理优化，选择底层的存取路径。生成查询计划，利用基于代价的物理优化，选择代价最小的

第八章 事务处理技术

事务

定义

事务 (Transaction) 是用户定义的数据库操作序列，这些操作要么都做，要么都不做，是一个不可分割的工作单位。

特性

原子性 (Atomicity)

事务中包括的所有操作要么都做，要么都不做

一致性 (Consistency)

事务执行的结果必须是使数据库从一个一致性状态，变到另一个一致性状态

隔离性 (Isolation)

一个事务的执行不能被其它事务干扰。即一个事务内部的操作及使用的数据对其他并发事务是隔离的，并发执行的各个事务之间不能互相干扰

持久性 (Durability)

一个事务一旦提交之后，它对数据库的映像必须是永久的。其它操作或故障不应该对其执行结果有任何影响

• 事务的 ACID 特性对于数据库数据的正确、有效具有重要意义。但事务的特性有可能遭破坏，主要有两种情况：
  • 多个事务并行运行时，不同事物的操作交叉进行
  • 事物在运行过程中被强行停止
• 利用数据库并发控制机制以及数据库恢复机制保证事物的特性不被破坏，从而保证数据库数据的正确、有效
  • 原子性由恢复机制实现
  • 一致性是由事物的原子性保证的
  • 隔离性通过并发控制机制实现
  • 持久性通过恢复机制实现
• 事务是数据库恢复和并发控制的基本单位
• 事务的开始与结束可以由用户显式控制。如果用户没有显式定义事务，则由 DBMS 按缺省规定自动划分事务。
• 事务与应用程序是两个概念，一般来说，一个应用程序可以包含多个事务

SQL 中事务的定义

事务开始

BEGIN TRANSACTION

事务结束

正常结束

提交事务，正常结束

COMMIT

非正常结束

撤销全部更新，回滚到事务开始时状态。非正常结束

ROLLBACK

数据库恢复技术

定义

数据库管理系统必须具有把数据库从错误状态恢复到某一已知正确状态的功能，这就是数据库的恢复

方法

数据库恢复是通过数据库管理系统的恢复子系统完成的

数据库恢复的基本原理为冗余。即利用存储在系统别处的冗余数据来重建或恢复修正数据库

意义

• 保证事务的原子性。实现事务非正常终止时的回滚
• 当系统发生故障以后，数据库能够恢复到正确状态

故障

种类

事务内部的故障

• 可预期的：事务根据内部的测试条件，确定是否回滚
• 不可预期的：指不能由应用程序处理的事务故障，如死锁、运算溢出，违反完整性规则等

系统故障

• 是指造成系统停止运行的任何事情，使得系统要重新启动，如硬件错误，操作系统故障，停电等。
• 这类故障打断所有正在运行的事务，使事务都异常中止，但不会破坏数据库

介质故障

• 介质故障指外存故障，如磁盘损坏，瞬时强磁场干扰等
• 这类故障将破坏全部或部分数据库，并影响正在存取这部分数据的所有事务

计算机病毒

• 计算机病毒是一种人为的破坏或故障，已成为数据库系统的主要威胁之一
• 多数病毒对数据进行非法修改

数据转储

定义

是 DBA 定期的将整个数据库复制到磁带或另一个磁盘上保存起来的过程。这些备用的数据文本成为后备副本或后援副本

分类

静态转储

定义

系统中无事务进行时进行的转储操作。并在转储过程中，不允许对数据库进行任何读取，修改。

优点

保证副本的数据一致性

缺点

由于转储必须等待正在运行的事务结束才能开始，而新的事物必须等待转储结束才能进行，降低了数据库的可用性

动态转储

定义

转储期间允许对数据库进行存取或修改

优点

不影响数据的可用性

缺点

不能保证副本上的数据正确，有效。还必须把转储期间各事物对数据库的修改记录下来，建立日志文件。后援副本加上日志文件就能把数据库恢复到某一时刻的正确状态。

转储方式

海量转储

海量转储指每次转储全部数据库

增量转储

增量转储指每次只转储上一次转储后更新过的数据

日志文件的建立与使用

定义

日志是用来记录事务对数据库更新操作的文件。

格式

以记录为单位

• 记载的内容
  • 各个事务的开始标记
  • 各个事务的结束标记
  • 各个事务的所有更新操作
• 每个日志记录中包含的信息项
  • 事务标识（标明是哪个事务）
  • 操作的类型（输入、删除或修改）
  • 操作对象（记录的内部标识）
  • 更新前数据的旧值（对插入操作，此项为空）
  • 更新后数据的新值（对删除操作，此项为空）

以数据块为单位

日志记录的内容包括事务标识以及更新前和更新后的数据块

作用

• 事务故障和系统故障修复必须使用日志文件
• 在动态转储方式中必须建立日志文件，后备副本和日志文件综合起来才能有效地恢复数据库
• 在静态转储方式中，用日志文件恢复转储结束时刻到故障点间的事务

日志文件的写入规则

• 登记的次序严格按并发事务执行的时间顺序
• 必须先写日志文件，后写数据库

故障的恢复策略

事务故障的恢复

事务故障的恢复——UNDO，即撤销事务

在不影响其它事务的情况下，强行回滚，撤销已做的修改。具体步骤：

• 反向扫描日志文件，查找该事务的更新操作
• 对该事务的更新操作（插入、删除、修改）执行逆操作，即将日志记录中的“更新前的值”写入数据库
• 如此处理下去，直到读到该事务的开始标志

系统故障

系统故障——UNDO+REDO

• 系统故障造成数据库不一致状态的原因
  • 未完成的事务对数据库的更新可能已经写入数据库
  • 已提交事务对数据库的更新可能还留在缓冲区未写入数据库
• 恢复操作需要撤销 (UNDO) 故障发生时未完成的任务，重做 (REDO) 已完成的任务

步骤

系统故障

1. 正向扫描日志文件，找出故障发生前已经提交的事务，将其事务标识记入重做 (REDO) 队列，同时找出故障发生时尚未完成的事务，将其事务标识记入撤销 (UNDO) 队列
2. 对撤销队列中的各个事务进行 UNDO 处理
3. 对重做队列中的各个事务进行 REDO 处理

介质故障

1. 装入最新的数据库后备副本，使数据库恢复到最近一次转储时的一致状态。对于动态转储的副本，还需要装入转储开始时刻的日志文件副本，将数据库恢复到一致状态
2. 装入存储以后的日志文件副本，重做已经完成的事务

具有检查点的恢复技术

优势

• 利用日志技术进行恢复时，恢复子系统通常需要检查大量日志记录，存在的问题是：
  • 搜索日志耗费大量时间
  • 不必要重做某些事物
• 检查点技术可以改善效率，使得在检查点之前提交的事务，在数据库恢复处理时不必重做

检查点技术

• 在日志文件中增加检查点 (checkpoint) 记录
• 检查点记录的内容
  • 建立检查点时刻所有正在执行的事务清单
  • 这些事务最近一个日志记录的地址
• 系统中增加一个重新开始文件，用来记录各个检查点记录在日志文件中的地址
• 恢复子系统动态维护日志文件，即周期性地执行如下操作
  • 将当前日志缓存中的所有日志记录写入磁盘的日志文件上
  • 在日志文件上写入一个检查点记录
  • 将当前数据缓存的所有数据记录写入磁盘的数据库中
  • 把检查点记录在日志文件中的地址写入重新开始文件s

利用检查点技术进行恢复

• 利用重新开始文件定位最近检查点记录：在重新开始文件中找到最后一个检查点记录在日志文件中的地址
• 找到检查点时刻运行事务清单：由该检查点记录得到检查点建立时刻所有正在运行的事务清单 ACTIVE-LIST，把 ACTIVE-LIST 暂时放入 UNDO-LIST
• 确定需要撤销和重做的事务：从检查点开始正向扫描日志文件，做如下处理，直到文件结束
  • 如果有新开始的事务 $T_i$，把 $T_i$ 暂时放入 UNDO-LIST
  • 如果有提交的事务 $T_j$ ，把 $T_j$ 从 UNDO-LIST 队列移入到 REDO-LIST 队列
• 执行撤销或重做动作：对 UNDO-LIST 中的每一个事物执行 UNDO 操作，对 REDO-LIST 中的每个事务执行 REDO 操作

数据库镜像

根据 DBA 的要求，自动把整个 DB 或其中的关键数据复制到另一个磁盘上，由 DBMS 自动保证镜像数据库与主数据库的一致性。

并发控制

并发控制

• 事务并发执行的优点
  • 一个事务由不同的步骤组成，所设计的系统资源也不同。这些步骤可以并发执行，以提高系统的吞吐量
  • 系统中存在着周期不等的各种事务，串行会导致难以预测的时延。如果各个事务所涉及的是数据库的不同部分，采用并发会减少平均响应时间
• 事务并发执行带来的问题
  • 多个事务同时存取同一数据时，如不加控制就可能会读取或存储不正确的数据，破坏数据库的一致性。

并发操作导致的数据不一致性

丢失更新 (Lost Update)

两个事务 T1 和 T2 读入同一数据并修改，T2 提交的结果破坏了 T1 提交的结果，导致 T1 的修改被丢失

“脏”数据的读出 (Dirty Read)

事务 T1 修改某一数据，并将其写回磁盘，事务 T2 读取同一数据后，T1 由于某种原因被撤销，这时 T1 已修改过的数据恢复为原值，T2 读到的数据就与数据库中的不一致，则 T2 读到的数据就为“脏”数据。

不能重复读 (Non-Repeatable Read)

事务 T1 读取数据后，事务 T2 执行更新（修改、插入、删除操作），使 T1 无法再现前一次读取的结果。

并发控制基本思想

并发控制就是要合理调度并发事务，避免并发事务之间的互相干扰造成数据的不一致性

并发控制的基本手段——封锁

定义

封锁就是事务 T 在对某个数据对象等操作之前，先向系统发出请求，对其加锁，从而对该数据有了一定的控制权

分类

排他锁（X 锁，eXclusive lock）

事务 T 对数据对象 R 加上 X 锁，则只允许 T 读取和修改 R，其它事务对 R 的任何封锁请求都不能成功，直至 T 释放 R 上的 X 锁。

共享锁（S 锁，Share lock）

事务 T 对数据对象 R 加上 S 锁，则事务 T 可以读取但不能修改 R，其它事务只能对 R 加 S 锁，而不能对 R 加 X 锁，直到 T 释放 R 上的 S 锁。

基本锁的相容矩阵

T1 \ T2	X	S
X	N	N
S	N	Y

封锁协议

名称	内容	功能
一级封锁协议	事务 T 在修改数据 R 之前必须对其家 X 锁，直到事务结束（正常结束 & 非正常结束）才释放。	方式丢失修改，并保证事务 T 是可恢复的。不能保证可重复读和读“脏”数据。
二级封锁协议	一级封锁协议加上事务 T 在读取数据 R 之前必须先对其加 S 锁，读完后即可释放 S 锁。	可以防止丢失更新，还可以进一步防止读“脏”数据。但不能保证可重复读。
三级封锁协议	一级封锁协议加上事务 T 在读取 R 之前必须对其加 S 锁，直到事务结束才释放。	防止丢失修改，读“脏”数据和不可重复读。

封锁的粒度

定义

封锁对象

属性值、属性值集合、元组、关系、某索引项、整个索引、整个数据库、物理页、块等

封锁粒度

封锁对象的大小成为封锁粒度

性质

• 封锁粒度大，则并发度低，封锁机构简单，开销小
• 封锁粒度小，则并发度搞，封锁机构复杂，开销高

多粒度封锁

在一个系统中同时支持多种封锁粒度供不同的事务选择。选择封锁粒度时应考虑封锁开销和并发度两个因素，适当选择封锁粒度以达到最优效果。

多粒度封锁

多粒度树

多粒度树的根节点是整个数据库，表示最大的粒度。叶结点表示最小的粒度。

多粒度封锁协议

• 多粒度封锁协议允许多粒度树种的每个节点被独立的加锁。对一个结点加锁意味着这个结点的所有后裔结点也被加以同样类型的锁。因此，在多粒度封锁种一个数据对象可能以两种方式加锁，即：
  • 显式封锁：是应事务的要求直接加到数据对象上的封锁
  • 隐式封锁：是该数据对象没有独立加锁，是由于其上级结点加锁而使该数据对象加锁
• 在多粒度封锁方法中，显式封锁和隐式封锁的效果相同

存在的问题

在多粒度封锁方法中，一般对某个数据对象加锁，系统要做如下检查：

• 是否与该数据对象上的显式封锁冲突（检查对象本身）
• 是否与该数据对象上的隐式封锁冲突（检查对象的所有上级结点）
• 是否与该数据对象的下级的显示封锁冲突（检查其所有下级结点）

意向锁

定义

意向锁的含义是该结点的下层结点正在被加锁。

• 对任意结点加锁时，必须先对其上级结点加意向锁
• 意向锁的好处是：在对象加锁时，不再检查下级结点的封锁，只需检查对象和它的上级结点

分类

意向共享锁 (Intent Share Lock，简称 IS 锁)

如果要对一个数据对象加 IS 锁，表示它的后裔结点拟（意向）加 S 锁。

意向排它锁 (Intent Exclusive Lock，简称 IX 锁)

如果要对一个数据对象加 IX 锁，表示它的后裔结点拟（意向）加 X 锁。

意向共享排它锁 (Share Intent Exclusive Lock，简称 SIX 锁)

如果要对一个数据对象加 SIX 锁，表示对它加 S 锁，再加 IX 锁，即 SIX = S + IX

加锁方法

任意事务 T 要对一个数据对象加锁，先对它的上级对象加意向锁，申请封锁按自上而下的次序进行；释放封锁时，应按照自下而上的次序进行。

相容矩阵

T1 \ T2	S	X	IS	IX	SIX	-
S	Y	N	Y	N	N	Y
X	N	N	N	N	N	Y
IS	Y	N	Y	Y	Y	Y
IX	N	N	Y	Y	N	Y
SIX	N	N	Y	N	N	Y
-	Y	Y	Y	Y	Y	Y

活锁与死锁

活锁

定义

任务或执行者没有被阻塞，但由于某些条件没有满足，导致一直无法得到执行。

解决

采用先来先服务的策略

死锁

定义

当两个以上的运算单元，双方都在等待对方停止执行，以取得系统资源，但是没有一方提前退出时，发生死锁。

解决

• 预防死锁
• 死锁检测和解除

死锁预防

• 一次封锁法
  • 要求每个事务必须一次将所有要使用的数据全部加锁，否则不能执行。
  • 可以有效地防止死锁的发生，但由于需要扩大加锁范围，因此会降低系统的并发度
• 顺序封锁法
  • 预先对数据对象规定一个封锁顺序。所有的事务都要按照这个顺序执行封锁。
  • 可以有效的防止死锁，但由于数据库中数据的不断变化和事务封锁要求的动态提出而实现难度大

死锁检测

• 超时法

  如果一个事务的等待时间超过了规定的期限，就认为发生了死锁

• 等待图法

  事务等待图是一个有向图 G=(T, U)，其中 T 为结点集合，每个结点表示正在运行的事务，U 为边集，每条边表示事务的等待情况。并发控制子系统周期性的检测事务等待图，如果发现图中存在环路，则表示系统出现死锁

死锁恢复

• 通常采用的方法是选择一个处理死锁代价最小的事务，将其撤销，释放此事务持有的所有锁，使其他食物得以继续运行下去。对于所撤销的食物所作的操作必须加以恢复。

事务的调度

定义

N 个事务的一个调度 S 是 N 个事务所有操作的一个序列。表示这些操作的执行顺序。并且这个序列满足：对于每个事务 T，如果操作 i 在事务 T 中先于操作 k 执行，则在 S 中操作 i 也必须先于操作 k 执行。

并发调度的可串行性

定义

可串行化调度

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

冲突操作

冲突操作是不同事务对同一数据的读-写操作以及写-写操作。

性质

可串行性是并行事务正确性的准则

一个给定的并发调度，当且仅当它是可串行化的，才认为是正确调度。

判定

• 一个调度 Sc 在保证冲突操作次序不变的情况下，可以通过交换两个事务不冲突操作的顺序，得到另一个穿行调度 Sc’，则调度 Sc 为冲突可串行化调度。

  不同事务的冲突操作与同一个事物的两个操作不能交换。

• 一个冲突可串行化调度，一定是可串行化调度

两段锁协议 (Two-phase Locking)

内容

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

含义

事务分为两个阶段，第一个阶段是获得封锁，也称为扩展阶段，第二个阶段是释放封锁，也称为收缩阶段

作用

可保证并行事务的可串行性

并发调度的可串行性

定理

若所有事物均遵从两段锁协议，则这些食物的所有并发调度都是可串行化的。

注意的问题

• 事务遵守两段锁协议是可串行化调度的充分条件而不是必要条件
• 两段锁协议并不要求事务在执行任何数据库读、写操作之前就一次申请全部封锁，因此遵守两段锁的事务仍可能发生死锁。

第九章 数据库保护

数据安全性控制是保护数据库防止恶意的破坏和非法存取。

数据完整性控制是为了防止数据库中存在不符合语义的数据，防止错误信息的输入和输出。

安全性防范的是非法用户和非法操作，完整性措施防范的对象是不合语义的数据。

数据库安全性控制

定义

数据库的安全性是指保护数据库以防止不合法的使用所造成的数据泄露、更改和破坏，它包括：

• 向授权用户提供可靠的信息服务
• 拒绝对数据的非授权存取访问请求，保证给数据的可用性、完整性和一致性，进而保护数据库所有者和使用者的合法权益

数据库安全性控制

用户标识与鉴别

用户标识和认证是系统提供的最外层安全保护措施

• 标识是指系统采用一定的方式标识其用户或应用程序的名字或身份
• 认证是指系统在用户或应用程序登录时判断其是否为合法的授权用户
• 常用的方法是采用用户名和口令

存取控制

定义

存取控制确保合法用户按照指定的权限使用 DBMS 和访问数据，而非法用户或不具有相关权限的用户则不能。

• 用户权限定义：将用户权限记录到数据字典中，形成安全规则或授权规则
• 合法权限检查：每当用户发出数据库操作请求后，DBMS 根据数据字典中的安全规则进行合法权限检查，决定是否接受用户的操作请求。
• 用户权限定义和合法权限检查机制一起组成了 DBMS 的安全子系统。

自主存取控制 (discretionary access control, DAC)

用户对于不同的数据对象拥有不同的存取权限，不同的用户对同一对象也有不同的权限，而且用户还可以将其拥有的权限转授给其他用户。

根据预先定义的用户权限进行存取控制。用户权限是指用户对数据对象允许执行的操作类型，由数据对象和操作类型两个要素组成。

对于用户存取权限的定义称为授权。在授权中应指明：用户名、数据对象名、允许的操作类型

强制存取控制 (mandatory access control, MAC)

每一个数据对象被标以一定的密级，每一个用户也被授予某一个级别的许可证。对于任一个对象，只有具有合法许可证的用户才可以存取。

强制存取方法

在 MAC 中，DBMS 所管理的全部实体被分为主体和客体两类

• 主体是系统中的活动实体，既包括 DBMS 所管理的实际用户，也包括代表用户的各进程
• 客体是系统中的被动实体，是受主体操纵的，包括文件、基本表、索引、视图等

对于主体和客体，DBMS 为他们每个实例指定一个敏感度标记 (Label)。敏感度标记被分为若干级别，如绝密、机密、秘密、公开等。主体的敏感度标记称为许可证级别，客体的敏感度标记称为密级。

MAC 机制通过对比主体和客体的 Label来确定是否能够存取。

• 仅当主体的许可证级别大于或等于客体的密级时，该主体才能读取相应的客体。
• 当且仅当主体的许可证级别等于客体的密级时，该主体才能写相应的客体。

其它方法

视图控制

为不同的用户定义不同的视图，可以将用户对数据的访问限制在一定的范围内。

审计

把用户对数据库的所有曹祖都自动记录下来放入审计日志中。DBA 可以利用审计跟踪的信息，重现导致数据库现有状况的一系列事件，找出非法存取数据的人、时间和内容等。

数据加密

防止数据库中数据在存储和传输中失密。

SQL 的数据安全性控制

用户权限

用户级权限

是数据库管理员为每个用户授予的特定权限，是对用户使用整个数据库权限的限定。与整个数据库相关，与数据库中具体的关系无关。

关系级权限

是数据库管理员或数据库对象的拥有者为用户授予的与关系或视图有关的权限，这种权限是对用户使用关系和视图权限的限定。

角色与用户组

为了管理数据库特权的方便，数据库还支持角色与用户组的概念。

角色

角色是一组权限的集合，可以把它授予用户或其他角色。当把某个角色授予用户（或角色）或从用户（或角色）收回时，就同时授予或收回了该角色代表的全部权限。

用户组

用户组是一组具有相同特性用户的集合。在授权或收回权限时，可以以用户组为单位进行。

授予——Grant 语句

在 SQL 语言中，通过 Grant 语句授予用户用户级权限或角色

Grant <用户名权限>|<角色> [{, 用户级权限>|<角色>}]
	To <用户名>|<角色>|public [{, <用户名>|<角色>}] # public: 数据库中的全部用户
	[With Grant Option] # 允许被授权的用户将指定的用户级权限或角色授予其他用户

DBA 和数据库对象所有者将这些数据库对象上的部分或全部权限授予其他用户。

Grant ALL | <权限> [{, <权限>}]
	On <表名>|<视图名> [{, <表名>|<视图名>}]
	To {<用户> [{, <用户>}] | public}
	[With Grant Option]

收回——Revoke 语句

Revoke <用户级权限>|<角色> [{, <用户级权限>|<角色>}]
	From <用户名>|<角色>|public [{, <用户名>|<角色>}]

Revoke ALL | <表级权限> [{, <表级权限>}]
	On <表名>|<视图名> [{, <表名>|<视图名>}]
	To {<用户> [{, <用户>}] | public}
	[With Grant Option]

收回权限时，若该用户已将权限授予其他用户，则也一并收回

可信计算机系统评测标准

• TCSEC (Trusted Computer System Evaluation Criteria)
• TDI (Trusted Database Interpretation) / TCSEC
• TDI 与 TCSEC 从安全策略、责任、保证、文档四个方面描述了安全级别划分的指标

数据库完整性控制

数据完整性含义

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

• 正确性是指数据应具有合法的类型，并在有效的取值范围之内
• 相容性是指表示同一个事实的两个数据应该相同

数据库能否保持完整性关系到数据库系统是否能够反映现实世界，因此维护数据库完整性十分重要。

完整性约束条件

定义

施加在数据库数据之上的语义约束条件称为数据库完整性约束条件。数据库系统依据完整性约束条件进行完整性检查。

作用对象

• 列（主要是类型、取值范围、精度等）
• 元组（主要是各个字段间联系的约束）
• 关系（主要是若干元组间、关系间联系的约束）

分类

静态约束

静态约束是指数据库在每一确定状态数据对象所应满足的约束条件，它是反映数据库状态合理性的约束。

• 静态列级约束是对一个列的取值域的说明，包括对数据类型（类型、长度、单位、精度等）、数据格式、取值范围或取值集合、空值等的约束。
• 静态元组约束规定了组成一个元组的各个列之间的约束关系。
• 静态关系约束规定了一个关系的若干元组或者若干关系之间常常存在的各种联系或约束。包括：实体完整性约束、参照完整性约束、函数依赖、统计约束等。

动态约束

动态约束是指数据库从一种状态转变为另一种状态时，新、旧值之间所应满足的约束条件，它是反映数据库状态变迁的约束。

• 动态列级约束是修改列定义或列值时应满足的约束条件。
• 动态元组约束指修改元组指时元组中各个字段间需要满足的约束。
• 动态关系约束指加载关系变化前后状态上的限制条件。

完整性控制

包括

• 定义功能：提供定义完整性约束条件的机制
• 检查功能：检查用户发出的操作请求是否违背了完整性约束条件
• 违约响应：若违背了完整性约束条件，则采取一定措施来保证数据的完整性

分类

立即执行约束

在执行用户事务的过程中，在一条语句执行完后立即进行完整性约束的检查。若违背了完整性约束，系统将拒绝该操作。

延迟执行约束

在整个用户事务执行完毕后，再进行完整性约束检查，结果正确方能提交，否则系统将拒绝整个事务。

完整性规则的表示

用五元组 (D, O, A, C, P) 表示

• D (Data) 约束所作用的数据对象
• O (Operation) 除法完整性检查的数据库操作
• A (Assertion) 数据对象必须满足的断言或语义约束
• C (Condition) 选择 A 作用的数据对象值的谓词
• P (Procedure) 违反完整性规则时除法的过程

SQL 支持

CREATE TABLE

Create Table <表名>
	(<列名> <数据类型> [<列级完整性约束>]
    [{, <列名> <数据类型> [<列级完整性约束>]}]
    [{, <表级完整性约束>}]);

其中，完整性约束可以是：

NULL / NOTNULL
UNIQUE
PRIMARY KEY
FOREIGN KEY
CHECK

ASSERTION 断言

CREATE ASSERTION <断言名> <CHECK 子句>

TRIGGER 触发器

触发器 (Trigger) 是用户定义再关系上的一类由事件驱动的特殊过程

对于用户对表的更新操作，系统自动激活相应触发器，执行完整性控制

CREATE TRIGGER <触发其名称>
	{BEFORE | AFTER} <触发器事件> ON <表名>
	REFERENCING NEW | OLD ROW AS <变量>
	FOR EACH {ROW|STATEMENT}
	[WHEN <触发条件>]
	<触发动作体>

第四部分 数据库新技术

数据仓库 (Data Warehouse)

定义

数据仓库(Data Warehouse) 1990 年提出，是支持管理决策过程的、面向主题的、集成的、随时间而增长的持久数据集合。

业务

• 数据仓库上的业务处理称作 OLAP (On-line Analytical Processing)，即联机分析处理。
• 数据库上的业务处理称作 OLTP (On-line Transaction Processing)，即联机事务处理

新时代数据管理面临的挑战

• 数据量：互联网时代，数据量呈指数级飞速增长，从 TB 到 PB 或更多
• 用户数：从几千人到几亿人
• 非结构化数据占总数据量的 80% 以上

数据库管理技术的新发展

SQL

• 传统关系型数据库，支持 SQL 操作，事务 ACID 特性
• 几千用户，TB 级数据

NoSQL

• Not Only SQL，非关系型的数据库，水平可扩展、分布式
• 不使用 SQL，不支持事务的 ACID 操作
• HBase, MongoDB 等

NewSQL

• 新的可扩展 / 高性能数据库
• 不仅具有 NoSQL 的海量数据存储管理能力，还保持了传统数据库支持 ACID 和 SQL 等特性
• VoltDB, ScaleBase, 阿里 DRDS 等

第九章 分布式数据库系统

基本概念

定义

分布式数据库是由一组分布再计算机网络的不同结点上的数据组成，每个结点具有独立的处理能力（称为场地自治），可以执行局部应用，同时每个结点也能通过网络通信支持全局应用。

• 局部应用：只操作一个结点上数据库的应用
• 全局应用：操作两个或两个以上结点上的数据库的应用

特点

分布式数据库以“数据分布”为前提，强调场地自治性（局部应用）以及自治场地之间的协作性（全局应用）。

• 场地自治性：每个场地有自己的数据库、一组终端，运行局部 DBMS，是独立的 DBS，具有高度自治性。
• 自治场地之间的协作性：各结点组成整体。整体性的含义是，从用户角度看，分布式数据库系统逻辑上如同一个集中式数据库一样，用户可以再任何场地执行全局应用。

分布式数据库系统的特点有：

1. 数据独立性
   • 数据的逻辑独立性和物理独立性
   • 数据的分布独立性（也称分布透明性）：数据的逻辑分片、数据物理位置分布的细节、重复剧本（冗余数据）一致性问题、局部结点上的数据模型等域用户程序无关。
2. 集中与自治相结合的控制结构
   • 数据的共享有两个层次
     • 一是局部共享。即在局部数据库中存储局部结点各用户的共享数据
     • 二是全局共享。即在分布式数据库系统的各个结点也存储供其他结点的用户共享的数据，支持系统的全局应用。
   • 分布式数据库系统常常采用集中和自治相结合的控制结构
     • 各局部的 DBMS 可以独立的管理局部的数据库，具有自治功能。
     • 系统又设有集中控制结构，协调各局部 DBMS 的工作，执行全局应用。
3. 适当增加数据冗余
   • 在分布式数据库系统中适当的增加了冗余数据，在不同的结点存储同一数据的多个副本
     • 在提高系统的可靠性、可用性，当某一结点出现故障时，系统可以对另一结点的相同副本进行操作，不会因为一处故障而造成整个系统的瘫痪。
     • 提高系统性能，系统可以选择用户最近的数据副本来进行操作，减少通信代价，改善整个系统的性能。
   • 不利于更新，增加了系统维护的代价
4. 全局的一致性、可串行性和可恢复性
   • 分布式数据库除了各局部数据库应满足集中式数据库的一致性、可串行性和可恢复性以外，还应保证数据库的全局一致性、并行操作的可串行性和系统的全局可恢复性。

体系结构

模式结构

• 全局外模式及全局外模式 / 全局概念模式映像（映像 1）

  全局外模式全局应用的用户视图，是全局概念模式的子集；映像 1 定义全局外模式到全局概念模式的映像。

• 全局概念模式

  定义分布式数据库中数据的整体逻辑结构，使得数据如同没有分布一样

• 分片模式及全局概念模式 / 分片模式映像（映像2）

  每一个全局关系可以分为若干互不相交的部分，每一部分称为一个片段。分片模式及映像2定义片段以及全局关系到片段的映像。这种映像是一对多的。

• 分布模式及分片模式 / 分布模式映像（映像 3）

  定义片段的存放结点及片段到结点的映像。分布模式的映像类型确定了分布式数据库是冗余的还是非冗余的。

• 分布模式 / 局部数据库概念模式映像（映像 4）

  该映像把存储在局部场地的全局关系或全局关系的片段映像为各局部概念模式。

数据分片

水平分片

将关系依照一定条件按行分为不相交的若干子集，每个子集称为一个水平片段。

垂直分片

将关系按列分为若干属性子集，每个子集称为一个垂直片段。垂直分片的片段通过连接的方法恢复原关系。因此垂直分片的诸片段通常都包含关系的码。

导出分片

导出水平分片，分片的条件不是关系本身属性条件，而是其它关系的属性条件。

混合分片

指按上述三种分片方式得到的片段，继续按另一种方式分片

数据分片的约束

完全性

一个全局关系中的数据必须完全划分为若干片段，不允许某些数据属于全局关系但不属于任何片段。

不相交性

不允许一个全局关系的某些数据既属于该全局关系的某一个片段，又属于另一个片段（垂直分片的码属性除外）

可重构性

可以由片段重构全局关系

• 垂直分片可用连接操作重构
• 水平分片可用并操作重构

分布透明性

分片透明性

用户或应用程序只对全局关系进行操作而不必考虑关系的分片。它是分布透明性的最高层次

位置透明性

用户或应用程序不必了解片段的存储场地也不必关系各数据副本的一致性

局部数据模型透明性

用户或应用程序不必了解局部场地上是哟个的是哪一种数据模型。模型的转换以及查询语言等的转换均由分布式 / 局部概念模式（映像 4）完成

分布式数据库管理系统 DDBMS

组成

• LDBMS（局部场地上的数据库管理系统）
  • 功能：建立和管理局部数据库，提供场地自治能力，执行局部应用及全局查询的子查询。
• GDBMS（全局数据库管理系统）
  • 功能：提供分布透明性，协调全局事务的执行，协调各局部 DBMS 以完成全局应用，并保证数据库的全局一致性，执行并发控制，实现更新同步，提供全局恢复功能
• GDD（全局数据字典）
  • 存放全局概念模式、分片模式、分布模式的定义以及各模式之间映像的定义
  • 存放有关用户存取权限的定义，以保证全局用户的合法权限和数据库的安全性
  • 存放数据完整性约束条件的定义
• CM（通信管理）
  • 在分布式数据库各场地之间传递消息和数据，完成通信功能

分类

按全局控制方式分类

• 全局控制集中的 DDBMS

  • 特点：GDBMS 集中在某一结点上，GDD 只有一个，也放在该结点上
  • 优点：控制简单，容易设计实现
  • 缺点：易形成瓶颈，并且一旦该结点出现故障，整个系统将瘫痪

• 全局控制分散的 DDBMS

  • 特点：GDBMS 分散在每一个结点上，GDD 也在每个结点上有一份。这类结构称为完全分布的 DDBMS
  • 优点：结点独立、自治性强，单个结点出席那问题不会使系统瘫痪
  • 缺点：全局控制的协调机制和一致性维护都比较复杂

• 全局控制部分分散的 DDBMS

  根据应用的需要将全局数据库管理器和全局数据字典分散在某些结点上，介于上述两者之间

按局部 DBMS 的类型分类

• 同构型 DDBMS

  每个结点的局部数据库具有相同的 DBMS，即使硬件与操作系统互不相同

• 异构型 DDBMS

  各结点的局部数据库具有不同的 DBMS

主要技术

分布式查询处理和优化

分布式查询类型与处理过程

分为局部查询、远程查询和全局查询

• 局部查询和远程查询只涉及单个结点的数据（本地或远程），可以采用集中式数据库的处理技术
• 全局查询涉及到多个结点的数据，十分复杂

分布式查询处理过程

1. 查询分解

   把查询操作分解为若干子查询，每个子查询只涉及某一个结点的数据，可由局部 DBMS 处理。必须选择查询开销最省的哪些结点（物理片段）

2. 选择操作执行次序

   确定涉及不同结点上关系的连接和并操作的次序

3. 选择执行操作的算法

   包括选择存取路径、选择某种操作的算法以及连接的执行方法

查询优化的目标

首要目标是：使查询执行时通信代价最省

不同结点之间的连接操作和并操作是数据传输的主要原因，因此连接查询的优化是优化中需要研究的中重要问题

连接查询的优化

• 半连接：使用半连接来缩减关系（或片段）进而节省传输的开销
  • 定义
  • 性质

分布式事务管理

分布事务的原子性和可串行性

• 在分布式数据库系统中，一个全局事务被划分为许多结点上的子事务
• 分布事务的原子性是：组成该事务的所有子事务要么一致的全部提交，要么一致的全部回滚
• 在多用户系统中，还必须保证分布式数据的可串行性

事务的恢复

每个场地都有一个局部事务管理器，负责管理局部子事务的执行。同时，各局部事务管理器之间必须有相互协调，保证分布事务的原子性：各子事务要么都提交，要么都回滚

对局部事务管理进行协调，保证分布事务原子性最常用的技术——两段提交协议 (2-Phase-Commitment Protocol)

两段提交协议 (2-Phase-Commitment Protocol)

把分布事务的所有局部事务管理分为两类：协调者（一个），参与者

• 协调者：负责作出该事务是提交还是撤销的最后决定
• 参与者：负责管理相应于子事务的执行以及在各自局部数据库上执行写操作

内容：

• 第一阶段：协调者征求意见做决定
  • 协调者向所有参与者发出”准备提交“信息，并记入日志；参与者准备提交就回答”就绪“，否则回答”撤销“，并记入日志
  • 如果在规定时间内，协调者收到所有参与者的”就绪“信息，则做出”提交“决定，否则”撤销“
• 第二阶段：参与者执行决定
  • 协调者将有关决定写入日志，然后把这个决定发送给所有参与者
  • 所有参与者收到命令后，首先在日志中记入”收到提交 / 撤销决定“的信息，并向协调者发送应答信息，最后执行相应决定。
  • 协调者收到所有参与者的应答消息后，一个事务的执行到此结束。有关日志信息可以脱机保存。
• 采用两段提交协议后，当系统发生故障时，各场地利用各自有关的日志进行事务恢复

事务的并发控制

• 分布式数据库系统中的并发控制也可以采用封锁技术，但更加复杂
  • 分布式数据库系统支持多副本
  • 由于事务的分布执行，封锁的方法会引起全局死锁
• 策略：
  • 处理多副本封锁的几种可能方法
    • 对写操作，要申请所有副本的 X 锁；对读操作，只要申请某个副本的 S 锁。
    • 无论是写操作还是读操作都要对大多数副本申请 X 锁或 S 锁
    • 规定某个场地上的副本为主副本，所有的读、写操作均申请对主副本的封锁
  • 解决全局自锁（两个以上场地上发生死锁）
    • 死锁检测及解除方式
    • 死锁预防