LYNX

Links

Tags

Categories

数据库复习提纲

1 数据库系统概述

1.1 基本概念

  • 数据库,数据库管理系统,数据库系统,数据库管理员(相互之间的关系)

1.2 数据库系统的特点

  • 数据集成化,数据独立性,数据共享,数据冗余,数据安全性,完整性和一致性,并发控制和故障恢复

1.3 数据库内部结构体系

  • 数据模式
  • 三级模式,二级映射
  • 三级模式与数据独立性关系

2 数据模型

2.1 数据模型的基本概念

  • 数据模型及其组成成分:数据结构,数据操作,数据约束
  • 数据模型的核心,不同类型数据模型的区分依据
  • 三个抽象层次上的数据模型概念:概念数据模型,逻辑数据模型,物理数据模型

2.2 数据模型的四个世界

  • 现实世界,概念世界,信息世界,计算机世界

2.3 概念世界与概念模型

  • E-R模型与E-R图(包括扩充E-R模型)
    • 实体,属性,联系
    • 多值属性,组合属性
    • 联系上的函数对应关系,参与方式
    • IS-A联系,弱实体
  • 面向对象模型:对象,对象标识符,类,方法,超类和子类,聚合和分解,继承和合成

2.4 信息世界和逻辑模型

  • 关系模型:关系,属性,值域(域),元组,关系数据库,关键字

2.5 计算机世界与物理模型

  • 逻辑模型的物理存储:项,记录,文件,索引,集簇
  • 提高文件访问效率的常用方法:索引,集簇,hash

3 关系数据库系统

3.1 关系数据库系统概述

3.2 关系数据库系统的衡量准则

  • 完全关系型的十二条衡量准则
  • 空值(NULL)的定义

3.3 关系代数

3.3.0 关系模型(概念)

  • 关系数据结构
    • 表结构(表头):表框架,表的元数与基数
    • 关系:关系的性质
    • 关键字:候选关键字,主关键字,外关键字
    • 关系数据库:关系子模式-视图(view)
  • 关系操纵
    • 数据查询:两个关系的合并,单个关系内的元组选择,单个关系内的属性指定
    • 元组的删除,插入,修改
    • 空值的处理
  • 关系中的数据约束
    • 实体完整性约束,参照完整性约束,用户定义的完整性

3.3.1 关系的表示

  • 关系的表示,笛卡尔乘积

3.3.2 关系操纵的表示

  • 关系代数中的五种基本运算:选择,投影,笛卡尔积,并,差(注意执行条件)

3.3.3 关系模型与关系代数

3.3.4 关系代数中的扩充运算

  • 交,除法,联接,自然联接,$\theta$-联接
  • 扩充运算与基本运算之间的关系

3.3.5 关系代数的应用

3.3.6 关系演算

  • 原子公式,公式的定义
  • 基于关系演算的数据查询表示:单表查询,多表连接查询,复杂查询的表示

3.4 关系数据库语言SQL

3.4.1 SQL概貌

  • SQL的基本概念与使用方式:表,行,列

3.4.2 数据定义功能

3.4.3 数据操纵功能

  • SQL语言与关系代数的关系
  • 基本查询功能:distinct,like,is null,多表联接查询,表的自联接查询
  • 嵌套查询:in,some/any/all,exists等谓词,相关子查询与独立子查询
  • 子查询的合并:union/intersect/except [all]
  • 统计查询(group by,having):统计与分组统计查询,空值与空集在统计函数中的处理方法
  • 复杂数据查询
  • 查询结果输出
    • 结果元组去重:distinct
    • 结果元组排序:order by

3.4.4 更新功能

  • 元组删除
  • 元组插入:常量元组的插入,带子查询的元组插入
  • 元组修改

3.4.5 视图

  • 视图概念,视图与基表的区别
  • 视图的创建与删除
  • 视图的嵌套定义
  • 视图删除中的连锁反应
  • 可更新视图的判断准则
  • 视图的作用

4 数据库的安全性与完整性保护

4.1 数据库的安全性保护

  • 数据库安全的基本概念与内容:主体,客体,身份标识与鉴别,自主访问控制,审计
  • SQL对数据库安全的支持
    • SQL中的存储权限
    • SQL中的授权命令grant和权限回收命令revoke

4.2 数据库的完整性保护

  • 数据库完整性保护的功能:目的与常用实现措施
  • 实体完整性,参照完整性,用户定义完整性
  • 完整的create table命令
    • 基表的创建
    • 完整性约束的定义:主关键字,外关键字,check约束,unique,not null,default
  • 触发器及其创建命令

5 事务处理,并发控制与故障恢复技术

5.1 事务处理(概念)

  • 事务的定义与ACID性质
  • 事务活动及其状态转换图
  • 事务控制及相关的参数设置语句:事务的提交与回滚,事务的读/写类型与隔离级别
  • 事务的语句组成成分

5.2 并发控制技术(概念)

  • 事务
    • 事务的并发性,并发控制
    • 调度,串行调度,可串行化调度,冲突与冲突可串行化,视图可串行化
    • 冲突可串行化的判定方法
    • 不正确的事务所导致的数据不一致现象:丢失修改(lost-update),脏读(dirty-read),不可重复读(unrepeatable-read)
  • 封锁
    • 共享锁(S锁),排它锁(X锁),锁相容矩阵,锁申请/锁释放算法
    • 基于封锁技术的并发控制实现方法
      • 三级封锁协议,三级封锁协议与数据不一致现象之间的关系
      • 两阶段封锁协议
      • 两阶段封锁协议与冲突可串行化的关系
  • 多粒度封锁
    • 封锁粒度/并发度/并发控制实现开销之间的关系
    • 多粒度树,多粒度封锁
    • 基于意向锁的多粒度封锁协议
      • 意向锁:IS,IX,SIX
      • 意向锁锁相容矩阵
      • 意向锁锁申请/释放算法
  • 死锁的监测与预防
    • 死锁,活锁
    • 死锁的检测及其处理办法
      • 等待图法
      • 超时死锁检测法:锁申请等待超时,事务执行超时
      • 时间戳死锁检测法

5.3 数据库恢复技术

  • 数据库恢复的含义,方法和常用措施
  • 数据库故障的分类
  • 数据库故障恢复三大技术:数据转储,日志,数据库镜像
  • 数据转储:静态转储/动态转储,海量转储/增量转储
  • 日志
    • 日志的内容,组成,作用与记载原则
    • 在日志中设置检查点的作用
    • 事务的撤销(undo)与重做(redo)
    • undo日志
    • redo日志
    • undo/redo日志
    • 3种日志的优缺点
  • 恢复策略:小型/中型/大型故障的恢复策略

6 7

游标管理

  • 游标的作用
  • 游标的定义,打开,使用,关闭
  • 可滚动游标的定义及其在数据更新命令中的使用

索引

  • B+索引的数据结构,搜索算法

8 关系数据库规范化理论

8.1 概述

  • 模式设计质量的评级指标:数据冗余度,插入/删除等更新异常
  • 为什么要研究关系的规范化设计:规范化的目的与手段

8.2 规范化理论

8.2.1 函数依赖(FD)

  • 函数依赖的定义
  • 如何寻找函数依赖:函数依赖与数据完整性约束的关系
  • 完全/部分FD,平凡/非平凡FD,直接/传递FD
  • Armstrong公理系统:3条基本原则+3条扩充原则
  • 基于函数依赖的关键字定义
  • 属性集闭包的计算算法
  • 关键字的计算算法

8.2.2 与函数依赖有关的范式

  • 范式定义:1NF,2NF,3NF,BCNF
  • 理解各级范式与数据冗余度,插入/删除异常的关系

8.2.3 多值依赖与第四范式

  • 多值依赖,平凡多值依赖,非平凡多值依赖
  • 多值依赖与函数依赖的关系
  • 4NF

8.3 规范化所引起的一些问题

  • 函数依赖的逻辑蕴含,函数依赖集的等价
  • 最小函数依赖集及其判定方法
  • 最小函数依赖集的计算算法
  • 模式分解的无损联结性,依赖保持性及其判定方法
  • 直接到3NF且满足无损联结性和依赖保持性的模式分解算法
  • 从3NF到BCNF,4NF的分解方法

9 数据库设计

9.1 数据库设计概述

9.2 数据库设计的需求分析

9.3 数据库的概念设计

9.4 数据库的逻辑设计

9.5 数据库的物理设计

数据库

1 数据库系统概述

1.1 基本概念

  • 数据库系统(Database System, DBS)
    DBS的组成部分
    • 数据库
    • 数据库管理系统
    • 数据库管理员
    • 软件平台
    • 硬件平台

1.4 数据库内部结构体系

  • 数据库系统的三级模式
    • 概念模式(模式)
    • 外模式(子模式,用户模式)
    • 内模式(物理模式)

2 数据模型

2.1 数据模型的基本概念

  • 概念模型

    • 常用的概念模型:实体-联系(E-R)模型,面向对象模型等
  • 逻辑模型

    • 常用的逻辑模型:关系模型,对象关系模型
  • 物理模型:由DBMS负责实现

2.3.1 实体-联系(E-R)模型

关键字:关键字时可用于区分同一个实体集中不同实体的最小属性集合
函数对应:m

2.3.2 扩充E-R模型

扩充的实体-联系(EE-R)模型

  1. IS-A联系:如果实体集$B$时实体集$A$的一个子集,且具有比实体集$A$更多的属性,则我们称实体集$A$与实体集$B$之间存在着一种特殊的IS-A联系,其中:

    • 实体集$A$被称为超(实体)集
    • 实体集$B$被称为子(实体)集
      子集$B$可以通过IS-A联系继承超集$A$中的所有属性
  2. 弱实体(Weak Entity)

    • 如果一个实体$A$的存在需要依赖于其他某个实体的存在,那么实体$A$被称为弱实体
  3. 属性的划分

  4. 属性基数(Cardinality of Attributes)

  5. Cardinality of Entity Participation in a Relationship(实体在一个联系中的参与基数)
    参与方式:(0,m)

2.3.3 面向对象模型

2.3.4 谓词模型

2.4.1 关系模型与关系模型数据库系统

关系中的基本概念

  • 关系模式
  • 关系数据库模式
  • 元组
  • 关键字(键/key)
    • 主关键字
    • 外关键字

3 关系数据库系统

3.3.0.1 关系数据结构

表结构

  • 表框架(Frame)

  • 元组(Tuple)

    • 在表框架中可按行(row)存放数据,其中的每一行数据被称为一个元组
    • 在一$n$元表中,一个元组由$n$个元组分量组成,其中:第$j$个元组分量就对应着表框架中的第$j$个属性($j=1,2…n$)

关系(Relation)

  • 具有$n$个属性的关系称为$n$元关系
  • 关系名及其所有属性的属性名构成了关系框架.设关系的名为$R$,其属性名为$A_1,A_2…A_n$,则该关系的框架是$R(A_1,A_2…A_n)$

键(Key)

在二维表中凡能唯一最小标识元组的属性集称为该表的,或称关键字

  • 候选键(Candidate Key)
  • 主键(Primary key)

每一张二维表都至少存在一个键

  • 外键(Foreign Key)
    • 如果表$A$中的属性集$F$时表$B$的键,则称该属性集$F$为表$A$的外键(或称外关键字)
    • 其中
      • 表$A$被称为引用表,表$B$被称为被引用表
      • 表$A$和表$B$可以是同一张二维表

3.3.0.2 关系操纵

空值处理

  • 在算术表达式中出现空值,其运算结果也为空值
  • 在逻辑运算表达式中出现空值,其运算结果为逻辑假

3.3.0.3 关系中的数据约束

三类数据完整性约束

  • 实体完整性约束:主键中的属性不能有空值

  • 参照完整性约束:外键要么取空值,要么是被引用表中当前存在的某元组上的主键值

  • 用户定义的完整性:用户自己定义的属性取值约束

3.3.1 关系的表示

笛卡尔乘积

$D_1\times D_2\times…\times D_n$

  • $D_1,D_2,…,D_n$是$n$个集合
  • 设集合$D_i$的元素个数为$r_i(i=1,2,…,n)$,则他们的笛卡尔乘积的结果元素个数为$r_1\times r_2\times…\times r_n$

关系$R$

  • $n$元关系$R$是一个$n$元有序组的集合

  • 设$n$元关系$R$的属性域分别是$D_1,D_2,…,D_n$,那么这$n$个域的笛卡尔乘积也是一个$n$元有序组的集合,并且与关系$R$存在联系:$R\subseteq D_1\times D_2\times…\times D_n$

3.3.2 关系操纵的表示

关系上的基本操作 关系代数中的基本运算
元组选择 选择运算
属性指定 投影运算
关系的合并 笛卡尔乘积
元组的插入 并运算
元组的删除 差运算

相容表

投影运算

选择运算

关系的笛卡尔乘积

  • 笛卡尔乘积满足交换律和结合律

  • 如果关系$R$和$S$中存在相同的属性名,则必须在结果关系中对其中的一个进行换名

3.3.3 关系模型与关系代数

3.3.4 关系代数中的扩充运算

交运算

除运算

  • 除运算的推导过程
    若$Head(R)=\{A_1…A_nB_1…B_n\},Head(S)=\{B_1…B_m\}$
    $R\div S=\pi_{A_1…A_n}(R)-\pi_{A_1…A_n}((\pi_{A_1…A_n}(R)\times S)-R)$
    1. $T_{\max}=\pi_{A_1…A_n}(R)$
    2. $R_{\max}=T_{\max}\times S$
    3. $T_1=R_{\max}-R$
    4. $T_2=\pi_{A_1…A_n}(T_1)$
    5. $R\div S=T_{\max}-T_2$

join运算

  • 又称$\theta$-联接运算,可以将关系$R$和关系$S$根据join条件$F$合并为一个关系

  • 联接条件$F$的构造方式

  • join运算的推导公式
    $R\underset{F}{\bowtie}S=\sigma_F(R\times S)$

  • 联接运算与笛卡尔乘积运算的关系

natural join运算

  • 功能:根据两个关系中的同名属性进行等值联接

  • 运算结果

    • 结果关系中的元组
  • natural join运算的推导公式

A 关系演算

A.1 一阶谓词演算

一阶谓词演算中的基本概念

A.1.3 谓词

A.1.4 指派

A.2 关系的表示

关系演算系统

  • 元组关系演算

  • 域关系演算

A.3 关系操纵的表示

  • 设$R$和$S$时两个模式相同的关系表,他们对应的谓词分别为$R(t)$和$S(t)$,则

    1. $R\cup S=\{t|R(t)\vee S(t)\}$
    2. $R-S=\{t|R(t)\wedge\lnot S(t)\}$
    3. $\sigma_F(R)=\{t|R(t)\wedge F\}$
    4. $\pi_{A_{i_1},A_{i_2},…,A_{i_k}}(R)=$TODO
  • 设有$m$元的关系$R$和$n$元的关系$S$,他们对应的谓词分别为$R(u)$和$S(v)$,则
    $R\times S=$TODO

关系演算表达式

  • 关系演算表达式$\{t|\varphi(t)\}$表示由公式$\varphi(t)$的所有成真指派所构成的集合
  • 可将$\{t|\varphi(t)\}$简写为$\varphi(t)$

关系演算的原子公式

关系演算公式(简称为公式)

A.4 关系演算的例子

关系的联结

  1. 可以通过相关谓词的逻辑与运算实现两个关系的笛卡尔乘积
    $R(p)\wedge S(q)$
  2. 通过选择条件$F$实现两个关系的$\theta$-联结
    $R(p)\wedge S(q)\wedge F$
  3. 可以通过两个谓词中的公共变元(同名变元)实现两个关系的自然联结
    $R(x,y,z)\wedge S(y,u,v)$
  • 自联结:谓词名不变,对部分变元进行重命名,从而实现关系的自联结(同名变元取值相等)

元组插入,删除与修改操作

  • 删除:$S(sno, sn, sd, sa)\wedge\lnot S(‘S_1’, sn, sd, sa)$

  • 插入:$S(t)\vee R(t)$

  • 修改:
    $R(sno, sn, sd, sa)=\exists x(S(sno, sn, sd, x)\wedge sno=S_7\wedge sa=29)$
    $(S(sno, sn, sd, sa)\wedge sno\not=S_7)\vee R(sno, sn, sd, sa))$

A.5 关系演算的安全限制

无限关系

无穷验证

B 关系数据库语言SQL

B.2 SQL数据定义功能

基表创建

B.3 SQL数据操纵功能

B.3.1 SQL的基本查询功能

B.3.1.2 常用谓词

like谓词的使用方法
column [ NOT ] like val1 [ escape val2 ]
  • 模板(pattern):val1

    • _:可以匹配任意一个字符
    • %:可以匹配任意一个字符串(包括空字符串)
  • 转移指示字符:val2

    • 紧跟在val2之后的_%不再是通配符,而是其自身

B.3.1.5 自连接

B.3.1.6 结果排序

order by <列名> [ asc | desc ] {, ...}

  • 升序asc,降序desc,默认升序

B.3.2 分层结构查询与集合谓词使用

where子句中的集合谓词

  • in谓词:标量与集合量之间的属于比较
expr [ not ] in ( subquery )
  • 限定比较谓词:标量与集合中元素之间的量化比较
expr 运算符 some|any|all ( subquery )
  • exists谓词:是否为空集的判断谓词
[ not ] exists ( subquery )

B.3.3 select语句间的运算

  • union [all]
  • intersect [all]
  • except [all]

不加all只选取不同的值

B.3.4 SQL计算,统计,分类的功能

B.3.4.1 统计功能

  • count统计:

    • count(*):返回集合中的元组个数
    • count(colname):返回在colname属性上取值非空的元组个数
    • count(distinct colname):返回colname取值非空且互不相同的元组个数
  • sum,avg,max,min统计

  • null在统计函数中的处理:TODO

B.3.4.3 分类功能

  • 分类统计查询

    • 分组查询子句
      group by colname { ,
      colname ...}

    根据属性colname的取值的不同,将满足where条件的元组划分为不同的集合

  • 分组选择子句:having group_condition

B.3.5 select语句使用的一般规则

B.4 SQL的更新功能

  • 元组删除
delete from table_name
[ where search_condition ];
  • 元组插入
insert into table_name [ ( colname {, colname ... } ) ]
values ( expr | null {, expr | null ...} ) | subquery;
  • 元组修改
update table_name
set colname = expr | null | subquery, ...
[ where search_condition ];

B.5 视图

B.5.2 视图的删除

  • 在执行视图的删除操作时,将连带删除定义在该视图上的其他视图

B.5.3 视图上的操作

  • 对视图可以作查询操作

    • 视图上的查询操作将首先被改写为基表上的查询操作,然后才能得到执行
  • 一般不允许执行视图上的更新操作,只有在特殊情况下才可以进行

  • 可更新视图

4 数据库的安全性与完整性保护

4.1 数据库的安全性

4.1.2 数据库安全的基本概念与内容

  • 客体:数据库中的数据及其载体
  • 主体:数据库中数据的访问者

4.1.4 SQL对数据库安全的支持

  • 操作对象

    • 表,视图
    • 属性
    • 域(type),udt(用户定义数据类型)
    • 存储过程/函数,触发器
  • 授权语句
    grant <操作权限列表> on <操作对象> to <用户名列表> [ with grant option ]

  • 回收语句
    revoke <操作权限列表> on <操作对象> from <用户名列表> [ restrict | cascade ]

    • cascade:连锁回收
    • restrict:在不存在连锁回收问题时才能回收权限,否则拒绝回收

4.2 数据库的完整性

TODO

5 事务处理,并发控制与故障恢复技术

5.1 事务处理

5.1.1 事务

  • 事务
    一个事务是指由一条SQL语句或者一组SQL语句所构成的一个执行过程,并具有ACID四个特性
    由每个用户所执行的一个不能被打断的对数据库的操作序列被称为事务

5.1.2 事务的性质

  1. 原子性(Atomicity)

  2. 一致性(Consistency)
    数据库的一致的状态可以理解为数据库中所有数据的正确性,他要求数据库中的数据必须满足

    • 在数据库中显式定义的各种完整性约束
    • 用户心目中的隐式数据约束

5.1.4 有关事务的语句

  1. 隔离性(Isolation)
    一个事物的执行与并发执行的其他事务之间是相互独立的,互不干扰,这被称为事务执行的隔离性

  2. 持久性(Durability)

  • 设置事务的隔离级别
    • readuncommitted:未提交读
    • readcommitted:提交读
    • readrepeatable:可重复读
    • serializable:可序列化(可串行化)

5.1.5 事务的组成

  1. 事务控制操作

    • 事务的开始:start T
    • 提交事务:commit T
    • 回退(放弃)事务:abort T
  2. 数据访问操作

    • input(A):将数据对象A的值从磁盘中读入内存缓冲区
    • output(A):将内存缓冲区中数据对象A的至写入磁盘
    • read(A, t):将内存缓冲区中数据对象A的值读入内存变量t

      在一个read操作中,有可能隐含着一个input操作

    • write(A, t):将内存变量t的值写入内存缓冲区中数据对象A

5.2 并发控制技术

5.2.1 事务的并发执行

  • 多个事务的执行方式

    • 串行执行
      • 以事务为单位,多个事务依次顺序执行
    • 并发执行
    • 并发执行的可串行化
      • 如果一组事务并发执行的结果等价于他们之间的某种串行执行的结果,则称其为可串行化调度
  • 并发控制的目标:实现并发事务的可串行化调度

  • 调度:一个或多个事务中的数据库访问操作,按照这些操作在DBMS(database management system)被执行的时间先后,排序所形成的一个操作序列
    给定一组并发事务$T_1,T_2…T_k$,他们之间的调度$H$必须满足

    1. 必须包括所有事物的所有操作,包括每一个事务的结束命令(commit/abort)
    2. 单个事物内部的操作顺序必须保持不变
  • 串行调度

  • 可串行化调度

  • 事务及调度的表示方法

    • 事务用符号$T_1,T_2…$表示
    • $r_i(X)$表示事务$T_i$读数据库对象$X$
    • $w_i(X)$表示事务$T_i$写数据库对象$X$
  • 冲突可串行化

    • 冲突(conflict):指调度中的一对相邻操作(op1; op2),他们满足:如果交换它们两者的执行顺序,那么涉及的事务中至少有一个的行为会改变
    • 冲突的判断办法
      • 同一事务的任意两个相邻的操作都是冲突
      • 不同事物对统一数据对象的/读-写冲突
    • 冲突等价:如果通过一系列相邻操作的非冲突交换能够将一个调度转换为另一个调度,称这两个调度是冲突等价的
    • 冲突可串行化:如果一个调度$S$冲突等价于这一组事务之间的一个串行调度,称$S$时冲突可串行化的
      • 冲突可串行化调度必定是一个可串行化调度
      • 一个可串行化调度不一定是冲突可串行化的
  • 冲突可串行化的判断:优先图

  • 视图等价

    • 一个冲突可串行化调度一定是视图可串行化调度
  • 三种数据不一致现象

    • 丢失修改(lost updata)
      • 一个事务的修改结果破坏了另一个事务的修改结果
      • 对多个事务并发修改同一个数据对象的情况未加控制
    • 脏读(dirty read)
      • 读到了错误的数据
      • 一个事务读取了另一个事务未提交的修改结果
    • 不可重复读(unrepeatable read)
      • 在一个事务的执行过程中,前后两次读同一个数据对象所获得的值出现了不一致
      • 在两次操作之间插入了另一个事务的操作

5.2.2 封锁

  • 排它锁(X锁)

  • 共享锁(S锁)

  • 锁相容矩阵

  • 锁的申请与释放

5.2.3 封锁协议

  • 一级封锁协议
    事务$T$在数据对象$A$之前,必须先申请并获得$A$上的X锁,并维持到事务$T$的执行结束(包括commitrollback)才释放加在$A$上的锁
    防止丢失修改

  • 二级封锁协议
    事务$T$在数据对象$A$之前,必须先申请并获得$A$上的S锁,在操作完成后可以释放$A$上的S锁
    防止丢失修改,脏读

  • 三级封锁协议
    事务$T$在数据对象$A$之前,必须先申请并获得$A$上的S锁,并维持到事务$T$的执行结束才释放被加在$A$上的S锁
    防止丢失修改,脏读,不可重复读

5.2.4 两阶段封锁协议

以事务为单位来规定封锁的使用原则:对一个事务在执行过程中需要调用的所有锁申请和锁释放的动作顺序进行了约定

根据锁的申请与释放操作的调用时间,可以将一个事务的执行过程划分为两个阶段

  • 第一个阶段:申请并获得锁
  • 第二个阶段:释放持有的锁

在一个事务$T$中,如果所有的封锁请求都先于所有的解锁请求,则该事务被称为两阶段封锁事务,简称2PL事务(或者说采用两阶段封锁协议的事务)

假设系统采用X锁和S锁,有关封锁的申请与释放操作表示如下:

  • $sl_i(A)$:事务$T_i$申请数据对象$A$上的一个S锁

  • $xl_i(A)$:事务$T_i$申请数据对象$A$上的一个X锁

  • $u_i(A)$:事务$T_i$释放自己在数据对象$A$上所持有的锁

  • 封锁的使用规定:在每一个事务$T_i$中

    1. 采用如下的封锁协议
      • $r_i(A)$之前必须有$sl_i(A)$或$xl_i(A)$,而且在两者之间没有$u_i(A)$
      • $w_i(A)$之前必须有$xl_i(A)$,而且在两者之间没有$u_i(A)$
      • 每一个$sl_i(A)$或$xl_i(A)$之后必须有一个$u_i(A)$
    2. 必须遵循两阶段封锁协议
    3. 保证事务调度的合法性
      • 如果$xl_i(A)$出现在调度中,那么后面不能再有$sl_i(A)$或$xl_j(A)$,除非中间插入了$u_i(A)$
      • 如果$sl_i(A)$出现在调度中,那么后面不能再有$xl_j(A)$,除非中间插入了$u_i(A)$

定理:由2PL事务所构成的任意合法调度$S$都是冲突可串行化的(用归纳法证明)

5.2.5 封锁粒度

封锁粒度 系统并发度 并发控制的开销
  • 多粒度封锁

    • 如果在一个系统中同时支持多种封锁粒度供事务选择使用,这种封锁方法被称为多粒度封锁
    • 可以按照封锁粒度的大小构造出一颗多粒度树,以树中的每个节点作为封锁对象,可以构成一个多粒度封锁协议
  • 意向锁

    • 使用规定
      • 如果对一个节点加意向锁,则说明该节点的下层节点正在被加锁
      • 对任一节点加锁时,必须先对它的上层节点加意向锁
    • 三种常见的意向锁
      • 意向共享锁(IS锁):如果对节点$N$加IS锁,表示准备在节点$N$的某些后裔节点上加S锁
      • 意向排它锁(IX锁):如果对节点$N$加IX锁,表示准备在节点$N$的某些后裔节点上加X锁
      • 共享意向排它锁(SIX锁):如果对节点$N$加SIX锁,表示对节点$N$本身加S锁,并准备在$N$的某些后裔节点上加X锁
其他事务已持有的锁$\to$ S锁 X锁 IS锁 IX锁 SIX锁
S锁 y n y n n
X锁 n n n n n
IS锁 y n y y y
IX锁 n n y y n
SIX锁 n n y n n
  • 多粒度封锁协议
    • 申请封锁的顺序:上->下
    • 释放封锁的顺序:下->上

5.2.6 活锁与死锁

死锁

  • 例子:$r_1(B),r_2(B),w_1(B)$

  • 解除法

    • 超时死锁检测法
      • 事务的执行时间超时
      • 锁申请的等待时间超时
    • 等待图法
    • 时间戳死锁检测法
      • 每个事物都具有一个用于死锁检测的时间戳
      • 如果事务$T$必须等待另一个事务$U$所持有的锁
        • 等待-死亡方案:
          • 如果$T$比$U$老,那么允许$T$等待$U$持有的锁
          • 如果$U$比$T$老,那么事务$T$死亡(被回滚)
        • 伤害-等待方案:
          • 如果$T$比$U$老,他将伤害$U$,$U$必须被回滚
          • 如果$U$比$T$老,那么$T$等待$U$持有的锁

活锁

  • 例子:

    • $T_1$(卖票):$xl_1(A),r_1(A),w_1(A),u_1(A)$
    • $T_2$(剩余票额查询):$sl_2(A),r_2(A),u_2(A)$
    • 先启动一个$T_2$,再启动一个$T_1$:$T_1$处于等待状态,在已经运行的$T_2$结束之前,不断有新启动的$T_2$加进来
  • 解决方法:先来先服务

5.3 数据库恢复技术

5.3.2 数据库故障分类

  • 小型故障

    • 事物内部故障
  • 中性故障

    • 系统故障
    • 外部影响
  • 大型故障

    • 磁盘故障
    • 计算机病毒
    • 黑客入侵

5.3.3.1 转储

  • 静态转储:无事务运行时

  • 动态转储

  • 海量转储:每次转储全部数据库

  • 增量转储:更新过的

5.3.3.2 日志

undo日志

  • 记录格式

    • 开始一个事务:<Start T>
    • 提交事务$T$:<Commit T>
    • 放弃事务$T$:<Abort T>
    • 更新记录:<T, X, V>,事务$T$修改了数据库元素$X$的值,$X$的旧值是$V$
  • 记载规则

    1. 如果事务$T$修改了数据库元素$X$,则<T, X, V>必须在$X$的新值写到磁盘前写到磁盘
    2. 如果事务$T$提交,则<Commit T>必须在事务$T$改变的所有DB元素写到磁盘后再写到磁盘
  • 恢复过程

    1. 将所有事务划分为两种类型
      • 已提交事务:有<Start T><Commit T>
      • 未提交事务:有<Start T>没有<Commit T>
    2. 从undo日志的尾部向头部扫描整个日志,对每条更新记录<T, X, Y>:
      • 如果<Commit T>已被扫描到,则继续扫描下一条日志记录
      • 否则,由恢复管理器将数据库中的$X$的值改为$V$
    3. 在日志的尾部为每个未结束的事务$T$写入一条日志记录<Abort T>,并刷新日志(flush log)
  • 检查点
    在日志中插入检查点的处理过程

    1. 系统停止接受启动新事务的请求
    2. 等所有当前活跃的事务提交或中止,并且在日志中写入<Commit T><Abort T>
    3. 将日志记录刷新到磁盘
    4. 写入日志记录<CKPT>,并再次刷新日志
    5. 重新开始接受新的事务
  • 在故障恢复时,只要逆向扫描到第一条<CKPT>记录,就可以结束故障恢复工作

  • 非静止检查点
    设置非静止检查点的步骤

    1. 写入日志记录<Start CKPT(T1, ..., Tk)>
    2. 等待$T_1, …, T_k$所有事务的提交或终止,在这个过程中允许启动执行新的事务
    3. 当$T_1, …, T_k$都已经完成时,写入日志记录<End CKPT>并刷新日志
  • 带有非静止检查点undo日志的恢复

    1. 先遇到<End CKPT>记录
      • 继续向后(头部)扫描,直到出现与之相对应的<Start CKPT(...)>记录就可以结束故障恢复工作
    2. 先遇到<Start CKPT(T1, ..., Tk)>记录,故障恢复工作需要撤销两类事务的操作
      • <Start CKPT(T1, ..., Tk)>记录之后启动的事务
      • $T_1, …, T_k$中在系统崩溃前尚未完成的事务
  • undo日志的不足

    • 在将事务改变的所有数据写到磁盘前不能提交该事务
    • 在事务的提交过程中需要执行许多磁盘操作,增加了事务提交的时间开销

redo日志

  • 记录格式

    • redo日志的记录格式与undo一样,唯一区别:在更新记录<T, X, V>中记载的是更新后的值
  • 记载规则

    • 在修改磁盘上的任何数据库元素$X$之前,要保证所有与$X$这一修改有关的日志记录(包括提交记录<Commit T>)都必须出现在磁盘上
  • 恢复过程

    1. 先扫描一遍日志文件,确定所有已经提交的事务
    2. 再从日志头部开始扫描,对每条更新记录<T, X, V>
      • 如果$T$时未提交事务,则继续扫描日志
      • 如果$T$是已提交的事务,则为数据库元素$X$写入新值$V$(有可能是冗余的操作)
    3. 对每个未完成的事务(提交记录<Commit T>没有写入磁盘),在日志的尾部写入<Abort T>并刷新日志
  • 非静止检查点

    1. 写入日志记录<Start CKPT(T1, ..., Tk)>($T_1, …, T_k$时当前所有活跃事务的标识符),并刷新日志.同时获得当时所有已提交事务的标识符集合$S$
    2. 将集合$S$中的事务已经写到内存缓冲区但还没有写道数据库磁盘的数据库元素写入磁盘
    3. 写入日志记录<End CKPT>并刷新日志,不需等待事务$T_1, …, T_k$或新开始事务的结束
  • 带检查点redo日志的恢复

    • 找到最后一个被记入日志的<End CKPT>,假设与之对应的检查点记录时<Start CKPT(T1, ..., Tk)>,并找到最早出现的<Start Ti>
    • 重做$T_1, …, T_k$,以及在<Start CKPT()>后开始的已经被提交事务
  • redo日志的不足

    • 要求事务提交和日志就刷新之前将所有修改过的数据保留在内存缓冲区中,可能增加事务需要的平均缓冲区的数量
    • 如果被访问的数据对象$X$不是完整的磁盘块,那么在undo日志与redo日志之间可能产生相互矛盾的请求

undo/redo日志

  • 记录格式

    • 更新记录的格式<T, X, v, w>,不仅记录更新前的值$v$,同时也要记录更新后的值$w$
  • 记载规则

    1. 在由于某个事务$T$所做的改变而修改磁盘上的数据库元素$X$之前,更新记录<T, X, v, w>必须出现在磁盘上
    2. 在每一条<Commit T>后面必须紧跟一条Flush Log操作

      事务提交(Commit)和写数据库磁盘(Output)的操作顺序是随机的

  • 恢复过程

    1. 根据<Commit T>是否已经出现在磁盘中来确定事务$T$是否已经被提交
    2. 从后往前,撤销(undo)所有未提交的事务
    3. 从前往后,重做(redo)所有已提交的事务
  • 检查点

    1. 写入日志记录<Start CKPT(T1, ..., Tk)>($T_1, …, T_k$是当前所有活跃事务的标识符),并刷新日志
    2. 将所有被修改过的缓冲区写到数据库的磁盘中去
    3. 写入日志记录<End CKPT>并刷新日志
  • 带检查点日志的恢复

5.3.4 恢复策略

  • 小型故障的恢复

    • 利用未结束事务的undo操作进行恢复
  • 中型故障的恢复

    • 非正常中止的事务:undo
    • 已完成提交的事务:redo
  • 大型故障的恢复

    • 先利用后备副本进行数据库恢复,再利用日志进行数据库的恢复

5.3.5 数据库镜像

将整个数据库的数据(或主要数据)实时复制到另一个磁盘中

5.4 事务处理实现技术

6 数据库中的数据交换

7 数据库的物理组织

8 关系数据库的规范化理论

8.2.1 函数依赖

  • 平凡.非平凡函数依赖

  • 完全函数依赖
    在关系模式$R(U)$中,如有$X\subseteq U,Y\subseteq U$,满足$X\to Y$,且对任何$X$的真子集$X’$都有$X’\not\to Y$,则称$Y$完全函数依赖于$X$,记作$X\overset{f}{\to}Y$

  • 部分函数依赖

  • 传递函数依赖
    在关系模式$R(U)$中,如有$X\subseteq U,Y\subseteq U,X\subseteq U$且满足$X\to Y,Y\not\subset X,Y\not\to X,Y\to Z$,则称$Z$传递函数依赖于$X$.否则称为非传递函数依赖(直接函数依赖)

  • Armstrong公理系统

    • 基本规则
      • 自反规则:如果$Y$是$X$子集,则$X\to Y$
      • 增广规则:如果$X\to Y$,则$XZ\to YZ$
      • 传递规则:如果$X\to Y,Y\to Z$,则$X\to Z$
    • 扩充规则
      • 分解规则:如果$X\to YZ$,则$X\to Y$且$X\to Z$
      • 合并规则:如果$X\to Y$且$X\to Z$,则$X\to YZ$
      • 伪传递规则:如果$X\to Y$且$WY\to Z$,则$WX\to Z$
  • 关键字(码,键,key)
    在关系模式$R(U,F)$中,如有$K\subseteq U$且满足$K\overset{f}{\to}U$,则称$K$为关系$R$的关键字

  • 主属性集

    • 由关系模式$R$的所有关键字中的属性所构成的集合被称为关系模式$R$的主属性集
    • 主属性集中的属性被称为关系模式$R$的主属性
  • 非主属性集

计算属性集$X$在函数依赖集$F$上的闭包$X_F^+$(简写为$X^+$)

$X^+=X$
repeat
 $oldX^+=X^+$
 foreach 函数依赖 $Y\to Z\in F$ do
  if $Y\subseteq X^+$ then $X^+=X^+\cup Z$
until ($oldX^+ == X^+$)

寻找关系模式$R(U,F)$的关键字$K$

输入:关系模式$R(U,F)$
输出:关系$R$的一个关键字$K$

$K=U$
foreach 属性 $A\in K$ {
 计算 $(K-A)_F^+$
 if $(K-A)_F^+$ 包含了$R$的所有属性 then {
  $K=K-A$
 }
}
return $K$

优化算法:设$F$时关系上的最小函数依赖集.根据$F$中的函数依赖,可将$U$划分为

  1. 只在函数依赖的左边出现过的属性的集合$U_L$
  2. 只在函数依赖的右边出现过的属性的集合$U_R$
  3. 在两边都出现的属性的集合$U_A$
    其中
  • $U_L$中的属性时没一个关键字的组成部分
  • $U_R$中的属性不可能出现在任何一个关键字中
  • 在关键自己算算法中,只需针对$U_A$中的属性进行for循环计算

$K=U-U_R$
foreach 属性 $A\in U_A$ {
 计算 $(K-A)_F^+$
 if $(K-A)_F^+$ 包含了$R$的所有属性 then {
  $K=K-A$
 }
}
return $K$

8.2.2 与函数依赖有关的范式

  • 第一范式
    关系模式$R(U)$中的每个属性值都是一个不可分割的数据量
    如果不满足第一范式,那么也就不能被称为关系

  • 第二范式
    关系模式$R(U)\in1NF$,且每个非主属性都完全函数依赖于关键字
    判断一个关系$R$是否满足2NF:

    1. 找到关系$R$的所有非主属性和所有候选关键字
    2. 检查每一个非主属性$A$和每一个关键字$K$之间的函数依赖,判断是否存在非主属性对于关键字的部分函数依赖

模式分解的方法

设关系模式$R$属性集合为$Head(R),F$时其函数依赖集.将其分解到满足范式$M$的步骤如下

  1. 找出所有不满足范式$M$要求的函数依赖关系
  2. 选择一个不符合要求的函数依赖关系作如下的分解
    假设$X\overset{f}{\to}Y\in F^+$且不满足范式$M$的要求,则将关系模式$R$分解为如下的两个子关系
    • $R_1(X\cup Y,\{X\to Y\})$
    • $R_2(Head(R)-Y,F_2)$,其中$F_2=\{A\to B|A\to B\in F^+$且$(A\cup B)\subseteq Head(R_2)\}$
  3. 对于分解得到的子关系模式$R_2$重复上述的步骤1和2,直到所有的子关系模式都能满足范式$M$的要求
  4. 合并那些具有相同关键字的子关系模式

  • 第三范式
    设关系模式$R(U)\in$2NF,且每个非主属性都不传递函数依赖于关键字,则称关系模式$R(U)$满足第三范式
    如果关系$R\not\in$3NF,那么在关系$R$中必然存在以下形式的函数依赖$X\overset{f}{\to}Y$,其中$Y$是单个的非主属性,$X$不是关系$R$的关键字

  • BCNF
    设关系模式$R(U)$满足1NF,且若$X\to Y$是$X$必含有该关系模式的关键字,则称关系模式$R(U)$满足BCNF范式

  • 若$R(U)\in$BCNF,则$R(U)\in$3NF

8.2.3 多值依赖与第四范式

  • 多值依赖(MVD)

    • 设有关系模式$R(U),X,Y\subseteq U$
    • $R(U)$满足
      1. 多$X$的一个确定值,存在$Y$的一组值与之对应
      2. 且$Y$的这组值又与关系中的其他属性$(U-X-Y)$的取值不相关
    • 称$Y$多值依赖于$X$,记为$X\to\to Y$
  • 非平凡的多值依赖
    设在关系模式$R(U)$中,$X\to\to Y$且$U-X-Y\not=\emptyset$,则称$X\to\to Y$是非平凡的多值依赖,否则称其为平凡的多值依赖

  • 多值依赖的性质
    在一个关系模式$R(U)$中

    1. 如有$X\to\to Y$,则必有$X\to\to(U-X-Y)$
    2. 如有$X\to Y$,则必有$X\to\to Y$
  • 有关FD和MVD的推导规则

  • 第四范式
    在$R(U)$中,如果$X\to\to Y$是非平凡多值依赖,则$X$必含有关键字,此时称关系模式$R$满足第四范式
    特点

    1. 函数依赖:要满足BCNF
    2. 不是函数依赖的多值依赖:只允许出现平凡多值依赖

8.3.1 函数依赖理论

  • 函数依赖集的等价
    如果两个函数依赖集$F_1$和$F_2$的闭包是相等的,称函数依赖集$F_1$等价于函数依赖集$F_2$

  • 最小函数依赖集

    • 与函数依赖集$F$向等价的所有函数依赖集中的最小者被称为函数依赖集$F$的最小函数依赖集
    • 也被称为最小覆盖

最小函数依赖集的判定条件

对于$F$中的每一个FD关系$X\to A$均作如下判断

  1. 依赖因素$A$为单个属性
  2. 不存在冗余的函数依赖:令$F_1=F-\{X\to A\}$,则$F_1^+\not=F^+$
  3. 不存在部分函数依赖:对于决定因素$X$的每一个真子集$Y(Y\subset X)$均作如下判断:
    令$F_2=F-\{X\to A\}\cup\{Y\to A\}$,则$F_2^+\not=F^+$

如果$F$中的每一个函数依赖$X\to A$均符合上述要求,则$F$是一个最小函数依赖集

  • 条件1不是必需的,只是为了方便条件2和3的判断

寻找与函数依赖集$F$等价的最小函数依赖集$G$

输入:函数依赖集$F$
输出:与$F$等价的最小函数依赖集$G$
算法:

  1. 消除$F$中的部分函数依赖(化简为完全函数依赖)
  2. 消除冗余的函数依赖

具体计算过程

  1. $G=F$
    将$G$中每一个形如$X\to(A_1,A_2…A_n)$的函数依赖替换为$X\to A_1,X\to A_2…X\to A_n$
  2. 对$G$中的每个函数依赖$X\to A$作如下处理
    对$X$中的每一个属性$B$:
    1. 计算属性集的闭包$(X-B)_G^+$
    2. 如果$A\in(X-B)_G^+$,则用新的函数依赖$(X-B)\to A$替换原来的$X\to A$
  3. 对$G$中的每个函数依赖$X\to A$作如下处理
    1. 令$N=G-\{X\to A\}$
    2. 计算属性集的闭包$X_N^+$
    3. 如果$A\in X_N^+$,那么$G=G-\{X\to A\}$
  4. 将$G$中的每一组$X\to A_1,X\to A_2…X\to A_n$合并为一个函数依赖$X\to(A_1,A_2…A_n)$

8.3.2 模式分解的研究

  • 无损连接性:分解后,原关系中的信息不会被丢失
    设$R$是一个关系模式,$F$时$R$的函数依赖集,$\rho=\{R_1,R_2…R_k\}$是对$R$的一个分解,如果对$R$中满足$F$的每一个关系实例$r$都有$r=\pi_{R_1}(r)\bowtie\pi_{R_2}(r)\bowtie…\bowtie\pi_{R_k}(r)$,则称$\rho$相对于$F$是无损联结分解,或称分解$\rho$具有无损联结性

  • 依赖保持性:原有的函数依赖关系在分解后的关系模式上依然存在
    设$\rho=\{R_1,R_2…R_k\},F$是$R$的函数依赖集,如果$F^+=(\pi_{R_1}(F)\cup\pi_{R_2}\cup…\cup\pi_{R_k}(F))^+$,则称分解$\rho$具有依赖保持性

  • 无损联接性的充要条件:$\rho={R_1, R_2}:R_1\cap R_2\to(R_1-R_2)$或$R_1\cap R_2\to(R_2-R_1)$

到3NF的分解算法

假设$S$时分解所获得的子关系模式的集合

  1. $F=F$的最小函数依赖集
  2. $S=\emptyset$
  3. 对$F$中每一个函数依赖$X\to Y$
    如果在集合$S$中找不到满足下述条件的子关系模式$Z$
    $X\cup Y\subseteq Heading(Z)$
    则由$X$和$Y$构成一个新的子关系加入到$S$中($S=S\cup Heading(X\cup Y)$)
  4. 如果找不到一个关键字$K$和一个子关系模式$Z$满足$K\subseteq Z$
    那么从关系$R$中任选一个候选关键字$K$单独构成一个子关系模式($S=S\cup Heading(K)$)

9 数据库设计

9.2 需求分析

确定需要在数据库保存其信息的客观事物及其相互关系

9.3 概念设计

  • 目的:建立一个抽象的概念数据模型
  • 工具
    • E-R模型
    • EE-R模型
    • 面向对象模型

9.4 逻辑设计

将EE-R模型转换成相等价的关系数据库模式

9.5 物理设计

  • 存取方法的设计
  • 存储结构的设计

1 / 1