第一章 绪论

数据库系统概述

数据库4个基本概念

  • 数据data：数据库中存储的基本对象

    • 结构化、半结构化、非结构化

    • 数据是符号化的信息；信息是语义化的数据

  • 数据库database：长期储存在计算机内、有组织、可共享的大量数据的集合

  • 数据库管理系统DBMS：用户和OS之间的一层数据管理软件

    • 功能：数据定义、组织、存储、管理操纵、事务管理和运行管理、建立和维护，其他

  • 数据库系统DBS：数据库+数据库管理系统+应用程序、数据库管理员(DBA)

  • 管理信息系统(MIS)架构：C/S、B/S

数据模型：对现实世界数据特征的抽象

分类：两个层次

  • 概念模型：用户观点

  • 逻辑模型(计算机系统观点)和物理模型(数据最底层抽象)

概念模型：

  • 信息世界中的基本概念：

    • 实体：客观存在可相互区别的事物
    • 属性：尸体所具有的某一特性
    • 码/键：唯一标识实体的属性集
    • 实体型：用实体名及其属性名集合来抽象和刻画同类实体
    • 实体集：同一类型实体的集合
    • 联系：现实世界中事物内部、事物之间的联系没在信息世界中反映为实体(型)内部/之间的联系
      • 内部：各属性之间的联系
      • 之间：不同实体集之间的联系
      • 一对一、一对多、多对多

  • 实体-联系方法：

    • E-R图(ERD)描述现实世界的概念模型

数据模型的组成要素：

  • 数据结构：

    • 描述数据库的组成对象、以及对象之间的联系
    • 对系统静态特性的描述

  • 数据操作

    • 操作的集合，包括操作及有关操作规则
    • 查询、更新(插入删除修改)

  • 数据的完整性约束条件

    • 一组完整性规则的集合

常用的数据模型：

  • 层次模型、网状模型、关系模型、面向对象数据模型、对象关系数据模型、半结构化数据模型、图数据模型

层次模型

  • DBS中最早的数据模型
  • 树形结构：表示各类实体及实体间的联系
  • 双亲唯一：只能处理一对多的实体联系

网状模型：

  • 网状数据库系统的数据模型
  • 层次模型是网状模型的特例

关系模型：

关系模型的数据结构

  • 关系数据库的数据模型
  • 用户观点下，关系模型数据的逻辑结构是一张二维表
  • 关系：一张表(包括数据)
  • 元组：表中一行
  • 属性：表中一列
  • 主码/主键：码或键，表中的某个可唯一确定一个元组的属性组
  • 域：一组具有相同数据类型的值的集合；属性的取值范围来自某个域
  • 分量：元组中的一个属性值
  • 关系模式：对关系的结构描述
  • 关系规范化：不允许表中还有表

关系模型的数据操作

  • 集合操作，操作对象和操作结果都是关系

关系的完整性约束条件

  • 实体完整性
  • 参照完整性
  • 用户自定义的完整性

数据库系统的结构

数据库系统模式的概念

  • 型：某一类数据的结构和属性的说明

  • 值：型的一个具体赋值

  • 模式：

    • 数据库逻辑结构和特征的描述
    • 型的描述
    • 反映数据的结构及其联系
    • 模式相对稳定

  • 实例：

    • 模式的一个具体值
    • 反映数据库某一时刻的状态

三级模式结构：

  • 数据库应用开发人员角度

  • 数据库系统内部的系统结构

  • 模式、外模式、内模式

  • 对数据的三个抽象级别

模式：逻辑模式

  • 数据库中全体数据的逻辑结构和特征的描述
  • 所有用户的公共数据视图
  • 一个数据库只有一个模式

外模式：子模式/用户模式

  • 数据库用户使用的局部数据的逻辑结构和特征的描述
  • 数据库用户的数据视图
  • 技术上：视图View的定义和描述
  • 地位：介于模式和应用之间
    • 模式与外模式的关系：一对多；
      • 外模式通常是模式的子集
    • 外模式与应用的关系：一对多；一个应用只能使用一个外模式
  • 作用：保证数据库安全性(用户只能看/访问外模式的数据)

内模式：存储模式

  • 数据物理结构和存储方式的描述
  • 一个数据库只有一个内模式
  • 对用户半透明

二级映像功能：

  • DBMS内部实现三级模式这三个抽象层次的联系和转换

  • 外模式/模式映像、模式/内模式映像

  • 保证了数据库外模式的稳定性

  • 从底层保证了应用程序的稳定性

外模式/模式映像

  • 每个外模式对应一个外模式/模式映像，定义外模式和模式之间的对应关系

  • 保证数据的逻辑独立性：模式改变时，DBA改变外模式/模式映像即可保证外模式不变；应用程序依据外模式编写，因此不必修改应用程序

  • 映像定义通常包含在各自外模式的描述中

模式/内模式映像

  • 定义了数据全局逻辑结构与存储结构之间的对应关系

  • 模式/内模式映像是唯一的

  • 映像定义通常包含在模式的描述中

  • 保证了数据的物理独立性：DB的存储结构改变，DBA修改模式/内模式映像，使模式保持不变

  • 应用程序也不受影响

数据库系统组成

数据库、数据库管理系统、应用程序、数据库管理员、硬件平台及数据库、软件、人员

第二章 关系数据库

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

关系：实体及实体间的各种联系

  • 关系的组成：同一类实体型的实例集合

  • 关系之间的联系

  • 逻辑结构：二维表表头(关系模式)——描述表的组成关系

  • 建立在集合论和关系代数的基础上

  • 关系的表示：R(D1,D2,...,Dn)R(D_1,D_2,...,D_n)

关系与表的术语对照

一般表格的术语 关系术语
表名 关系名
表头(表格结构的描述) 关系模式
二维表(数据) 关系
记录/行 元组
列 属性
列名 属性名
列值 属性值
一条记录中的一个列值 分量
表中有表 非规范关系

码/键：

  • 候选码/键：关系中某一属性组的值能唯一地标识一个元组；找不出真子集仍满足前一条件
  • 全码/键：关系模式的所有属性组都是候选码
  • 超键：只满足唯一标识的条件，候选键是最小超键
  • 主码/键：多个候选码选定一个，其诸属性称为主属性
  • 外键：一个实体的主键被另外一个实体使用，以表达不同实体元组之间的关系

实体(表)间的关系：依赖主键-外键关系实现

三类关系：基本关系、查询表、视图表

关系模式：

  • 关系模式是型，是结构；关系是值(二维表)

  • 关系模式是关系的结构；关系是关系模式某一时刻的数据

形式化表示：R(U,D,DOM,F)R(U,D,DOM,F)

  • R：关系名

  • U：组成该关系的属性名集合

  • D：U中属性所来自的域

  • DOM：属性向域的映像集合

  • F：属性间数据的依赖关系的集合

关系数据库：所有关系的集合构成一个关系数据库

  • 型：关系数据库模式

  • 值：关系模式在某一时刻对应的关系的集合(关系数据库RDB)

关系模型的存储结构：关系数据库的物理组织

关系操作

查询：

  • 8种：选择、投影、连接、除、并、差、交、笛卡尔积

  • 5种基本：选择、投影、并、差、笛卡尔积

更新：插入、删除、修改

特点：操作对象和结果都是集合，一次一集合

关系数据库语言的分类：关系代数语言、关系演算语言、具有关系代数和关系演算双重特点的语言(SQL等)

关系的完整性

实体完整性

  • 实体完整性规则：主属性不能取空值

参照完整性：

外码：

  • 设F是基本关系R的一个或一组属性，但不是关系R的码。如果F与基本关系S的主码KsK_s相对应，则F是R的外码
  • R：参照关系
  • S：被参照关系/目标关系
  • R和S不一定不同；主码KsK_s和FF必须定义在同一域上；外码不一定要与对应主码同名

参照完整性规则：

  • R中每个元组在F上的值必须等于S中某个元组主码值KsK_s/NULL

数据冗余：

  • 关系数据库不支持m:n联系，因为水导致数据冗余
  • 1:1、1:m的联系不会存在实体数据冗余

用户自定义的完整性

针对某一具体关系数据库的约束条件

  • 具体应用所设计的数据必须满足的语义要求

关系模型应提供定义和检验这类完整性的机制

关系代数

  • 是一种抽象的查询语言，用关系运算表达查询

  • 运算对象、结果都是关系

  • 关系代数的运算符：集合运算符和专门的关系运算符

运算符 含义
集合运算符 ∪\cup 并
−- 差
∩\cap 交
×\times 笛卡尔积
专门的关系运算符 σ\sigma 选择
π\pi 投影
⋈\Join 连接
÷\div 除

并：

  • R、S同目n同域

  • R∪S={ t∣t∈R∨t∈S }R\cup S=\set{t|t\in R \vee t\in S}

  • 不允许重复

差：

  • R−S={ t∣t∈R∧t∉S }R-S=\set{t|t\in R \wedge t\notin S}

  • “是…但不含”

交：

  • R∩S={ t∣t∈R∧t∈S }R\cap S=\set{t|t\in R\wedge t\in S}

笛卡尔积：

  • R×S={ trts∣tr∈R∧ts∈S }R\times S=\set{t_rt_s|t_r\in R\wedge t_s\in S}

  • 行：k1×k2k_1\times k_2

  • 列：m+nm+n

选择：

  • σF(R)={ t∣t∈R∧F(t)=True }\sigma_F(R)=\set{t|t\in R\wedge F(t)=True}

  • F是一个逻辑表达式

投影：

  • πA(R)={ t[A]∣t∈R }\pi_A(R)=\set{t[A]|t\in R}，A为R中属性列

  • 投影后重复元组要去除

连接：

  • 从两个关系的笛卡尔积中选取属性间满足一定条件的元组

  • R⋈SAθB={ trts∣tr∈R∧ts∈S∧tr[A]θtsB }R\Join S_{A\theta B}=\set{t_rt_s|t_r\in R \wedge t_s\in S \wedge t_r[A]\theta t_sB}

  • A/B：R和S上度数相等且可比的属性组

  • θ\theta：比较运算符

  • R⋈SAθB=σtr[A]θts[B](R×S)R\Join S_{A\theta B}=\sigma_{t_r[A]\theta t_s[B]}(R\times S)

等值连接：θ\theta为“=”

  • R⋈SA=B=σtr[A]=ts[B](R×S)R\Join S_{A=B}=\sigma_{t_r[A]= t_s[B]}(R\times S)

自然连接：特殊的等值连接

  • 比较分量必须为相同的属性组
  • 结果中把重复的属性列去掉

  • R⋈S=σtr[B]=ts[B](R×S)R\Join S=\sigma_{t_r[B]= t_s[B]}(R\times S)

悬浮元组：

  • 自然连接时，R中某些元组可能在S中 不存在公共属性上值相等的元组，从而造成R中这些元组在操作时被舍弃了

外连接：保存悬浮元组，填写空值

左外连接：只保留R中悬浮元组，右边S不匹配的元组为NULL

右外连接：只保留S中悬浮元组，左边R不匹配的元组为NULL

全外连接：保留所有悬浮元组

除运算：关系R(X,Y),S(Y,Z)R(X,Y),S(Y,Z)

  • R.Y/S.YR.Y/S.Y应出自相同域，且一般πy(S)⊆πy(R)\pi_y(S)\subseteq\pi_y(R)

  • R÷S={ tr[X]∣tr∈R∧_y(S)⊆Yx }R\div S=\set{t_r[X]|t_r\in R\wedge \_y(S)\subseteq Y_x}

  • 理解：求X=x的象集被S.Y所包含的一些元组

  • “查询…至少/全部/所有…”

  • Eg：查询选修了全部课程的学生的学号

    • πSno,Cno(SC)÷πCno(Course)\pi_{Sno,Cno}(SC)\div\pi_{Cno}(Course)

  • SQL：R(X,Y)÷S(Y,Z)R(X,Y)\div S(Y,Z)

1
2
3
4
5
6
7
8
9
10
select distinct R.X from R as R1
where not exists
(
  select S.Y from S
   where not exists
   (
     select* from R as R2
     where R2.X = R1.X and R2.Y = S.Y
   )
);

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

SQL概述

SQL：结构化查询语言，关系数据库的标准语言

SQL特点：

  • 综合统一：

    • 集数据定义语言(DDL)、数据操纵语言(DML)、数据控制语言(DCL)于一体。还有事物控制语言(TCL)
    • DDL：数据库结构schema定义：create、alter、drop
    • DML：数据查询与修改：insert、select、update、delete
    • DCL：权限控制：grant、revoke
    • TCL：保障数据修改的原子性：begin transaction、commit、rollback

  • 高度非过程化

  • 面向集合的操作方式

  • 以同一种语法结构提供多种使用方式

  • 语言简洁，易学易用

学生-课程数据库

数据定义：create/alter/drop

  • 模式定义(mysql中与database等价)：定义了一个命名空间

  • 表定义

    • 创建

      1
      2
      3
      4
      5
      create table <tableName>(
          <colname><datatype>[<col constraint>]
          ...
          [<table constraint>]
      );

    • 数据类型：域

    • 字符串常量：单引号

    • 两个连续单引号转义为一个

    • 双引号标识关键字、对象名、字段名

    • 修改

      1
      2
      3
      4
      5
      6
      7
      alter table <tableName>(
          [ADD <colname><datatype>[<col constraint>]]
          ...
          [ADD[<table constraint>]]
          [DROP constraint...]
          [alter column <name><type>]
      );

    • 删除

      1
      drop table <name> [restrict|cascade]

  • 视图和索引定义

    • 索引目的：加快查询速度

    • 顺序索引、B+树索引、散列索引、位图索引

数据查询

1
2
3
4
5
select [all|distinct] <colname>[,...]
from <tablename>[,...]|(select) [as [othername]]
[where <>]
[group by <colname> [having <>]
[order by <colname> [asc|dec]]

  • 等值连接：

    1
    where A=B

  • 自然连接：

    1
    table1 natural join table2

  • 自身连接：需要给表起别名以区别

  • 外连接：

    1
    2
    3
    4
    SELECT Student.Sno, Sname, Ssex, Sage, Sdept, Cno, Grade 
    FROM Student LEFT[RIGHT|FULL] OUTER JOIN SC ON (Student.Sno=SC.Sno)

    SELECT * FROM Student NATURAL LEFT OUTER JOIN SC;

  • 嵌套查询：

    • 将一个查询块嵌套在另一个查询块的WHERE子句或HAVING短语的条件中

    • 子查询不能使用order by

    • 不相关子查询：子查询的查询条件不依赖于父查询

    • 相关子查询：子查询的查询条件依赖于父查询

数据更新

插入：

  • 将新元组插入指定表中

    1
    2
    INSERT INTO <表名> [(<属性列1>[,<属性列2 >…)] 
    VALUES (<常量1> [,<常量2>]… );

  • 插入子查询结果

    1
    2
    INSERT INTO <表名> [(<属性列1> [,<属性列2>… )] 
    子查询;

修改：

1
2
UPDATE <表名> SET <列名>=<表达式>[,<列名>=<表达式>]… 
[WHERE <条件>];

删除：

1
2
3
DELETE
FROM <表名> 
[WHERE <条件>];

空值处理

  • 主码、unique、not null不能取空值

  • 判断：is null/is not null

视图

  • 虚表

    1
    CREATE VIEW <视图名> [(<列名> [,<列名>]…)] AS <子查询> [WITH CHECK OPTION];

第四章 数据库安全性

概述

定义：保护数据库以防止不合法使用所造成的数据泄露、更改或破坏

主要评价指标：系用安全保护措施是否有效

安全目标：保密性、完整性、可用性

安全标准：TCSEC标准(可信计算机系统评估准则)、TDI(可信数据库系统解释)

安全级别划分：四组七级

  • D：最小保护
  • C(C1,C2C_1,C_2)：自主保护
  • B(B1,B2,B3B_1,B_2,B_3)：强制保护
  • A(A1A_1)：认证保护

安全性控制

数据库备份与恢复(后续)

存取控制：

  • 自主存取控制(DAC)：C2

    • grant
      1
      2
      3
      4
      GRANT <权限> [,<权限>]...
      ON <对象类型> <对象名>[,<对象类型> <对象名>]… 
      TO <用户>[,<用户>]...
      [WITH GRANT OPTION]; //针对数据对象
    • revoke
      1
      2
      3
      REVOKE <权限>[,<权限>]...
      ON <对象类型> <对象名>[,<对象类型><对象名>]… 
      FROM <用户>[,<用户>]...[CASCADE | RESTRICT];

  • 强制存取控制(MAC)：B1

第五章 数据库完整性

数据库完整性概念：防止数据库中存在不符合语义的数据

  • 数据的正确性：符合现实世界语义

  • 数据的相容性：符合逻辑

实体完整性：

定义

  • 关系模型的实体完整性：create table 中用primary key定义

  • 单属性构成的主键有两种说明方法:

    • 定义为列级约束条件
    • 定义为表级约束条件

  • 对多个属性构成的主键只有一种说明方法：

    • 定义为表级约束条件

检查和违约处理

  • 主码值是否唯一

  • 主码各属性是否为空

参照完整性

定义

  • create table中用froeign key定义外码

  • references指明外码参照哪些表的主码

检查和违约处理

  • 两个表将相应的元组联系起来，检查是否会破坏参照完整性

  • 处理：拒绝执行、级联操作、设置空值

用户定义的完整性

定义：针对某一具体应用的数据必须满足的语义的要去

属性上的约束条件：

  • 列值非空

  • 列值唯一

  • 检查列值是否满足一个条件表达式

属性上的约束条件检查和违约处理

  • 检查是否被满足，不满足则拒绝执行

元组上的约束条件

  • check定义元组级的限制

  • 可设置不同属性之间的取值的相互约束条件

元组上的约束条件检查和违约处理

  • 检查是否被满足，不满足则拒绝执行

完整性约束命名子句

1
CONSTRAINT <完整性约束条件名> <完整性约束条件>

触发器

定义：

  • 用户定义在关系表上的一类由事件驱动的特殊过程

  • 保存在数据库服务器中

类型：

  • 行级触发器

  • 语句级触发器

第六章 关系数据理论

问题的提出

规范化

函数依赖

  • 定义：X函数确定Y(Y函数依赖于X)，记作：X→YX\rightarrow Y，称X是函数依赖的决定因素

    • 相互依赖：X→Y∧Y→X⇒X↔YX\rightarrow Y \wedge Y\rightarrow X\Rightarrow X\leftrightarrow Y
    • 不函数依赖：X↛YX \nrightarrow Y

  • 语义范畴：根据数据语义确定一个函数依赖

  • 非平凡函数依赖：Y⊈XY\nsubseteq X

  • 平凡函数依赖：Y⊆XY\subseteq X

  • 完全函数依赖：X→FYX \overset{F}{\rightarrow}Y,不存在X的真子集函数决定Y

  • 部分函数依赖：X→PYX \overset{P}{\rightarrow}Y，存在X的真子集函数决定Y

  • 传递函数依赖：X→Y,Y→Z⇒X→传递ZX\rightarrow Y,Y\rightarrow Z\Rightarrow X \overset{\mathrm{传递}}{\rightarrow}Z，其中X和Y不是相互依赖，都不是平凡函数依赖

    • 存在非受控冗余

码/键

  • 候选码：K→FUK\overset{F}{\rightarrow}U

  • 超码：K→PUK\overset{P}{\rightarrow}U

函数依赖的公理：对于满足一组函数依赖F的关系模式R <U,F>，其任何一个关系r，若函数依赖X→Y都成立(即r中任意两元组t、s，若t[X]=s[X]，则 t[Y]=s[Y])，则称F逻辑蕴涵X →Y。

范式(NF)：符合某一种级别的关系模式的集合

  • 5NF⊂4NF⊂BCNF⊂3NF⊂2NF⊂1NF5NF\sub 4NF\sub BCNF\sub 3NF\sub 2NF\sub1NF

  • 规范化：一个低一级范式的关系模式，通过模式分解，可转换为若干个高一级范式的关系模式的集合

1NF

  • 二维表的每个分量不可再分

  • 关系数据库中对关系模式的基本要求

2NF

  • R∈1NFR\in 1NF，且每个非主属性都完全函数依赖于任何一个候选码，则R∈2NFR\in2NF

  • 问题：插入异常、删除异常、修改复杂

  • 原因：存在对候选码(复合主键)的部分函数依赖

  • 如果单一候选码，自然是2NF

3NF

  • R∈1NFR\in 1NF，不存在传递依赖，则R∈3NFR\in 3NF

  • 消除非主属性对候选码的传递依赖

BCNF(修正的第三范式)

  • R∈1NFR\in 1NF，X→YX\rightarrow Y时(非平凡)，X必含有码，则R∈BCNFR\in BCNF

  • 每一个决定属性集都包含候选码(即每个属性集都是超码)

  • 除了所有属性(组)对候选码的依赖关系之外，没有任何其他依赖关系

  • 函数依赖范畴内，实现模式的彻底分解，达到了最高规范化程度

  • 消除了插入一场和删除异常

多值依赖

  • X→→YX\rightarrow\rightarrow Y等价于∀(x,z),∃y\forall(x,z),\exist y仅与x有关而与z无关

  • X+Y+Z=UX+Y+Z=U

  • 平凡的多值依赖：Z=ΦZ=\Phi

  • 函数依赖(FD)是多值依赖(MVD)的特殊情况：X→Y⇒X→→YX\rightarrow Y\Rightarrow X\rightarrow\rightarrow Y

  • Y和Z是独立的，地位等价，具有对称性

4NF

  • R∈1NFR\in 1NF，每个非平凡的多值依赖X→→YX\rightarrow\rightarrow Y，X都含有码，则R∈4NFR\in 4NF

  • 不允许有非平凡且非函数依赖的多值依赖

关系模式规范化的基本步骤

1NF

↓\downarrow 消除非主属性对码的部分函数依赖

2NF

↓\downarrow 消除非主属性对码的传递函数依赖

3NF

↓\downarrow 消除==主属性==对码的部分函数依赖和传递函数依赖

BCNF(1→BC\rightarrow BC：消除决定因素非码的非平凡函数依赖)

↓\downarrow 消除非平凡且非函数依赖的多值依赖

4NF

数据依赖的公理系统

Armstrong公理系统：

  • 自反律

  • 增广律

  • 传递律

推理规则：

  • 合并规则：X→Y,X→Z⇒X→YZX\rightarrow Y,X\rightarrow Z\Rightarrow X\rightarrow YZ

  • 伪传递规则：X→Y,WY→Z⇒XW→ZX\rightarrow Y,WY\rightarrow Z\Rightarrow XW\rightarrow Z

  • 分解规则：X→Y,Z⊆Y⇒X→ZX\rightarrow Y,Z\subseteq Y \Rightarrow X\rightarrow Z

第七章 数据库设计

数据库设计概述

  • 6个阶段

需求分析

概念结构设计

  • 将需求分析得到的用户需求抽象为信息结构(概念模型)

概念模型

  • 反映现实世界，是现实世界的一个真实模型

E-R模型

  • 实体之间的联系：1:1、1：n、m：n

逻辑结构设计

  • 用Crow’s Foot ERD建模

  • 根据关系数据库==范式分解理论==，消除属性依赖与冗余，明确主键、外键参照关系，消除实体间==多对多==的关系

  • 按照规范化理论分解到3NF

物理结构设计

  • 数据库在物理设备上的存储结构与存取方法称为数据库的物理结构，它依赖于选定的数据库管理系统。

  • 确定数据库物理结构主要指确定数据的存放位置和存储结 构

数据库的实施和维护

第八章 数据库编程

过程化SQL

  • 业务逻辑在数据库上实现

过程化SQL的块结构

  • SQL的扩展

  • 增加了过程化语句功能

  • 基本结构是块

    • 块之间可以嵌套
    • 每个块完成一个逻辑操作

  • 块的基本结构

    • 定义部分
    • 执行部分

变量和常量的定义

  • 变量定义

  • 常量定义

  • 赋值语句

流程控制

  • 条件控制语句

  • 循环控制语句

  • 错误处理

JDBC编程

JDBC API

提供了一套访问任何RDBMS的标准接口

  • JDBC Driver

  • Connection

  • Statement

  • ResultSet

SQL注入

  • 高级代码注入技术，发生在应用程序和数据库交互层的安全漏洞

  • 攻击者专门构造传递给数据库的SQL字符串，来修改SQL自身的语法和功能

SQL注入产生的技术根源

  • 典型的B/S应用程序三层架构

方式：

  • 整数

  • 字符串

  • SQL注释

预防：

  • 检查用户输入、转义特殊字符

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

关系数据库系统的查询处理

查询处理阶段

  • 查询分析：对查询语句进行扫描、词法分析、语法分析

  • 查询检查：合法性检查、视图转换、安全性检查(DAC、MAC)、完整性初步检查

    • 检查通过后转为等价的关系代数表达式
    • 使用查询树/语法分析树

  • 查询优化：选择一个高效执行的查询处理策略

    • 选择依据：基于规则、代价、语义

  • 查询执行：依据优化器得到的执行策略生成查询执行计划

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

关系数据库系统的查询优化

选择操作：

  • 全表扫描方法：适合小表
  • 索引扫描方法：B+树索引、Hash索引

连接操作：查询处理中最耗时之一

  • 嵌套循环方法：遍历

    • 可快速获取前几条查询记录
    • 理想场景：外表小，内表连接字段有唯一索引

  • 排序-合并算法

    • 先排序再扫描
    • 只需各表扫描一遍

  • 索引连接算法(嵌套循环的变种)

    • 通过内表索引查找

  • Hash Join算法

    • 把连接属性作为hash码
    • 划分阶段+试探(连接)阶段
    • 大数据集连接常用，只能等值连接
    • 适用于较小的表完全可以放于内存中的情况

代数优化

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

  • 关系表达式等价，记作E1≡E2E_1\equiv E_2

常用的等价变换规则

  • 连接、笛卡尔积的交换律和结合律

  • 投影的串接定律：子集关系下，最外层投影有效

  • 选择的串接定律：选择条件可合并

  • 选择与投影操作的交换律：与F涉及的属性有关

  • 选择和笛卡尔积的交换律：与F涉及的属性有关

  • 选择与并的分配律

  • 选择与差的分配律

  • 选择对自然连接的分配律：F只涉及公共属性

  • 投影对笛卡尔积的分配律：属性也需要分配

  • 投影与并的分配律

典型的启发式规则

  • 选择运算尽可能先做

  • 投影和选择同时进行

  • … …

物理优化

  • 存取路径和底层操作算法的选择

方法

  • 基于规则的启发式优化

  • 基于代价估算的优化

第十章 数据库恢复技术

事务的基本概念

事务：

  • 用户定义的一个数据库操作序列，不可分割的工作单位

定义事务的语句：

  • BEGIN TRANSACTION：开始

  • COMMIT：提交事务的所有操作

  • ROLLBACK：回滚，系统将事务中对数据库所有已完成的操作全部撤销

事务的ACID特性：

  • 原子性：事务是数据库的逻辑工作单位

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

  • 隔离性：一个事物的执行不能被其他事务干扰

  • 持续性：永久性，一个事物一旦提交，他对数据库中的数据的改变就应该是永久性的

  • 事务是恢复和并发控制的基本单位

数据库恢复概述

故障种类

事务内部的故障

  • 一般是非预期的，不能由应用程序处理

  • 恢复：事务撤销

系统故障

  • 指造成系统停止运转的任何事件，使得系统要重新启动

  • 恢复：撤销+重做

  • 软故障

介质故障

  • 硬故障，数据库物理破环

计算机病毒

故障对数据库的影响

  • 数据库本身被破坏

  • 数据库未被破坏，但是数据可能不正确

恢复的基本原理：冗余

恢复的实现技术

建立冗余数据的最常用技术

  • 数据转储和登记日志文件

数据转储

  • DBA定期将整个数据库恢复到转储时的状态

  • 备用数据称为后备副本

  • 重装后备副本后只能将数据库恢复到转储时的状态

  • 分类：

    • 静态转储：系统中无运行事务时进行的转储操作
      • 静态海量转储
      • 静态增量转储
    • 动态转储：转储期间允许对数据库进行存取或修改。即转储和用户事务可并发执行
      • 动态海量转储
      • 动态增量转储

登记日志文件

  • 日志文件格式和内容

    • 日志文件：用来记录事务对数据库的更新操作的文件
      • 以记录为单位
      • 以数据块为单位

  • 日志文件的作用

  • 登记日志文件原则

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

恢复策略

具有检查点的恢复技术

第十一章 并发控制

并发控制概述

  • 事务是并发控制的基本单位

  • 为保证事务的隔离性和一致性，需要对并发操作进行正确调度

封锁

  • 事务T在对某个数据对象操作之前，先向系统发出请求，对其加锁

封锁类型

  • 排他锁(X锁)：写锁，其他事务不允许读取和修改，不允许叠加任何锁

  • 共享锁(S锁)：读锁，限制只读，其他事务只能叠加S锁

封锁协议

  • 封锁协议：运用基本封锁时，需要约定一些规则

一级封锁协议

  • 事务T在修改数据R之前必须先对其加X锁，直到事务结束

  • 防止丢失修改

二级封锁协议

  • 在一级封锁协议基础上增加事务T在读取数据R之前必须先对其加S锁，读完即可释放S锁

  • 防止丢失修改+防止读“脏”数据

三级封锁协议

  • 一级封锁协议的基础上增加事务T在读取数据R之前必须先对其增加S锁，知道事务结束才释放

  • 防止丢失修改+防止读“脏”数据+防止不可重复读

活锁和死锁

避免活锁：先来先服务

死锁预防：一次封锁、顺序封锁

死锁的诊断与解除：超时法、事务等待图

并发调度的可串行性

可串行化调度

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

  • 可串行性时并发事务正确调度的准则

两段锁协议(2PL)

  • 第一阶段：获得封锁，称扩展阶段

  • 第二阶段：释放封锁，称收缩阶段

  • 并发执行的所有事物均遵守两段锁协议，则这些事务的任何并发调度策略都是可串行化的(充分不必要)

封锁的粒度

封锁粒度：

  • 封锁对象的大小

  • 类型：逻辑单元、物理单元

  • 与系统的并发度和并发控制的开销密切相关

  • 多粒度封锁：支持多种封锁粒度

多粒度封锁

  • 多粒度树

  • 每个节点可独立加锁，其子节点也被加锁

  • 显示封锁：直接加到数据对象上的锁

  • 隐式封锁：未被独立加锁，但是由于上级节点被加锁而加上了锁

意向锁

  • 如果对一个节点加意向锁，则说明该节点的下层节点正在被加锁

  • IS锁(意向共享锁)：

  • IX锁(意向排他锁)：

  • SIX(共享意向排他锁)：

强度：X>SIX>S=IX>ISX>SIX>S=IX>IS