高级数据库课堂笔记

简介：Advanced Database Technologies是中科大软件学院金培权教授的课，主要讲解了数据库基本原理和设计方法。让人收获很大。本文整理了课堂笔记，以备复习之用。文中引用了很多授课课件的截图，若有侵权，请联系我删除。

总览

第二章 关系数据库回顾

数据库系统体系结构

二级映像和数据独立性

数据的逻辑独立性：当概念模式发生改变时，只要修改外模式/模式映象，可保持外模式不变，从而保持用户应用程序不变，保证了数据与用户程序的逻辑独立性。

数据的物理独立性：当数据库的内部存储结构发生改变时，只要修改模式/内模式映象，可保持概念模式不变，从而保持外模式以及用户程序的不变，保证了数据与程序的物理独立性。

关系数据模型

几个术语：

• 超码（Super Key）
  • 在关系中能唯一标识一个元组的属性集称为关系模式的超码
• 候选码（Candidate Key）
  • 不含多余属性的超码
  • 包含在候选码中的属性称为主属性（Primary Attribute）
  • 不包含在任何一个候选码中的属性称为非主属性（NonprimeAttribute）
• 主码（Primary Key）
  • 用户选作元组标识的一个候选码称为主码，其余的候选码称为替换码（Alternate Key）

函数依赖

Armstrong公理：

关系代数

数学符号表示：

举例：

供应商关系模式： S (S#, SNAME, STATUS, CITY)，求住在同一个城市里的供应商号码对：

SQL

数据库语言包括三类子语言：

• 数据定义语言（Data Definition Language, DDL），存取数据库模式
• 数据操纵语言（Data Manipulation Language， DML），存取数据库数据
• 数据库控制语言（Data Control Language， DCL），存取访问控制信息

SQL的组成：

第三章 数据库设计の模式设计

关系模式的设计问题

设计不规范带来的问题：数据冗余，更新异常，插入异常，删除异常

解决问题的方法：模式分解

关系模式的分解

标准

1. 具有无损连接
2. 要保持函数依赖
3. 既具有无损连接，又要保持函数依赖

无损连接

判断方法：

关系模式的范式

范式的概念

范式：满足特定要求的模式

• 不同级别的范式要求各不相同
• 范式可以作为衡量一个关系模式好坏的标准
• 若关系模式R满足范式xNF，记R∈xNF
• 5NF ⊂ 4NF ⊂ BCNF ⊂ 3NF ⊂ 2NF ⊂ 1NF

函数依赖图

举例：

1NF

对于关系模式R的任一实例，其元组的每一个属性值都只含有一个值，则R∈1NF。

反例：

姓名	年龄	早餐	数量
张三	12	鸡蛋，包子	1，1
李四	32	NULL	NULL
王五	41	豆浆，鸡蛋，油条	1，2，1

2NF

当且仅当R属于1NF，且R的每一个非主属性都完全函数依赖于主码时， R∈2NF。

• 完全函数依赖：对于函数依赖W→A，若不存在X⊂W，并且X→A成立，则称W→A为完全函数依 赖，否则为局部函数依赖。
• 主属性：包含在候选码中的属性。
• 非主属性：不包含在任何候选码中的属性。

反例：

3NF

当且仅当R属于2NF，且R的每一个非主属性都不传递依赖于主码时， R∈3NF 。

• 传递依赖：若Y→X， X→A，并且X→Y， A不是X的子集，则称A传递依赖于Y 。

反例：

BCNF

BCNF模式的函数依赖图的箭头左边都是候选码。

举例：

反例：

模式分解的算法

保持函数依赖地分解到3NF的算法

例子：

无损并且保持函数依赖分解为3NF的算法

方法：

例子一：

例子二：

无损分解为BCNF的算法

例子：

第三章 数据库设计の设计过程

数据库设计概念

我们以新奥尔良方法为基础，基于ER模型和关系模式，采用计算机辅助进行数据库设计

• 概念设计：基于ER模型
• 逻辑设计：基于关系模式设计
• 计算机辅助设计工具
  • PowerDesigner（SYBASE）

数据库设计方法

• 自顶向下进行需求分析

• 自底向上进行ER设计

ER模型

ER模型(EntityRelationship Model) ：实体-关系模型

举例：

设计原则：实体要尽可能得少。现实世界中的事物若能作为属性就尽量作为属性对待。

范式

范式级别的确定：根据实际应用的需要（处理需求）确定要达到的范式级别。 时间效率和模式设计问题之间的权衡。

范式越高，模式设计问题越少，但连接运算越多，查询效率越低。

• 如果应用对数据只是查询，没有更新操作，则非BCNF范式也不会带来实际影响
• 如果应用对数据更新操作较频繁，则要考虑高一级范式以避免数据不一致
• 实际应用中一般以3NF为最高范式

数据库设计步骤

第四章 数据存储

存储器结构

几个术语：

盘片platter，盘面 surface，磁头 R/W head，磁道 track，柱面cylinder，扇区 sector ，块block

块（Block）

• OS或DBMS进行磁盘数据存取的最小逻辑单元，由若干连续扇区构成
• 块是DBMS中数据存取的最小单元
• 扇区是磁盘中数据存储的最小单元

磁盘块存取时间

$$ 磁盘块读取时间 ＝ 寻道时间S + 旋转延迟R + 传输时间T $$

块地址：物理设备号 -> 柱面号 -> 盘面号 -> 扇区号

磁盘例子

磁盘存取优化

按柱面组织数据

• 减少平均寻道时间

磁盘调度算法

• 如电梯算法 (Elevator Algorithm)

磁盘阵列(Disk Arrays) 磁盘镜像(Disk Mirrors) Random IO to Sequential IO 预取(Pre-fetch)和缓冲(Buffering)

• 双缓冲处理时间＝R＋nP（P>=R）或者 ＝nR＋P（R>=P）
• 单缓冲处理时间＝n(R + P)

第五章 数据表示

数据项的表示（ Data Items）

记录的表示（ Records）

记录在块中的组织（ Block）

记录的修改

块在文件中的组织

第六章 缓冲区管理

缓冲区置换算法

OPT，LRU，LRU-K，2Q，Second-Chance FIFO ，CLOCK ，

缓冲区管理的实现

Buffer Manager的基本功能

FixPage(int page_id) 将对应page_id的page读入到buffer中。如果buffer已满，则需要选择换出的frame。

FixNewPage() 在插入数据时申请一个新page并将其放在buffer中

SelectVictim() 选择换出的frame_id

FindFrame(int page_id) 查找给定的page是否已经在某个frame中了

SetDirty(int frame_id)

第七章 索引结构

索引的动机： 提高按查找键（Search Key）查找的性能，将记录请求快速定位到页地址

顺序文件上的索引

密集索引

优点：要查找键值为K的记录是否存在，不需要访问磁盘数据块

缺点：索引占用太多空间

稀疏索引

优点：节省了索引空间

缺点：要查找键值为K的记录是否存在，需要访问磁盘数据块

多级索引

二级索引必须使用稀疏索引！！

优点：

• 二级索引更小，可以常驻内存
• 减少磁盘I/O次数

辅助索引

• 数据文件不需要按查找键有序
• 根据索引值不能确定记录在文件中的顺序

辅助索引必须是密集索引！！

倒排索引

应用于文档检索，与辅助索引思想类似

常用索引结构

树形索引： B+树

• 一种树型的多级索引结构
• 树的层数与数据大小相关，通常为3层
• 所有结点格式相同： n个值， n＋ 1个指针
• 所有叶结点位于同一层

节点个数：

• 至少 ⌊(n+1)/2⌋ 个指针指向子树
• 根结点至少 2 个指针

插入的例子：

删除的例子：

散列型索引： Hash Index

散列函数(Hash Functions)

• h：查找键(散列键) → [0…B – 1]
• 桶(Buckets), numbered 0,1,…, B-1

散列索引方法

• 给定一个查找键K，对应的记录必定位于桶h(K)中
• 若一个桶中仅一块，则 I/O次数＝ 1
• 否则由参数B决定，平均＝总块数/B

动态散列表

• 可扩展散列表（ Extensible Hash Tables）：成倍增加桶数目
• 线性散列表（ Linear Hash Tables）：线性增加

第八章 查询优化

语法分析

构造语法分析树

逻辑查询计划生成

查询重写

运用转换规则，将一个代数表达式转换为另一个等价的代数表达式 。

转换的直接目的

• 减少查询执行时的中间关系大小
• 减少元组的大小

查询计划代价估计

中间关系大小估计

一些统计量(statistics)

• T(R) : R的元组数
• S(R) : R中每个元组的大小(bytes)
• V(R, A) : R的属性A上的不同值数
• B(R)：容纳R所有元组所需的块数

1. W = R1 × R2 的大小估计

   T(W) = T(R1) * T(R2) S(W) = S(R1) + S(R2)

2. 

3. W = R1 ⋈ R2 的大小估计

   

   S(W)＝ S(R1) + S(R2) － S(A)

例子：

I/O代价估计

执行查询计划所必须读（写）的磁盘块数目

第九章 查询执行

物理查询计划操作符

逻辑操作符的特定实现。

连接操作的实现算法

嵌套循环连接

归并连接

索引连接

散列连接

连接算法的I/O代价估计

• 当关系较小时，嵌套循环连接更优。
• 当关系较大时，归并连接更优。
• 关系有序时，使用归并连接。

第十章 事务处理の日志和恢复

事务的状态及原语操作

事务(transaction) ：一个不可分割的操作序列，其中的操作要么都做，要么都不做 。

事务的状态：

• <Start> ：事务已开始
• <Commit T> ：事务已完成
• <Abort T> ：事务已废除

事务的原语操作：

• Input (x)：将 x 读入内存
• Output (x)：将 x 写回磁盘
• Read (x,t)：t 的值赋给 x
• Write (x,t)：x 的值赋给 t

数据库的一致性和正确性

正确性：如果数据库在事务开始执行时是一致的，并且事务执行结束后数据库仍处于一致状态。

Correctness of DB ≠ Correctness of reality

数据库系统故障分析

Consistency of DB 可能由于故障而被破坏

1. 事务故障：发生在单个事务内部的故障
   • 可预期的事务故障：应用程序可以发现的故障，如转帐时余额不足。由应用程序处理。
   • 非预期的事务故障：如运算溢出等，导致事务被异常中止。应用程序无法处理此类故障，由系统进行处理 。
2. 介质故障：硬故障，一般指磁盘损坏 。
   • 导致磁盘数据丢失，破坏整个数据库 。
3. 系统故障 ：软故障，由于OS、 DBMS软件问题或断电等问题导致内存数据丢失，但磁盘数据仍在 。
   • 影响所有正在运行的事务，破坏事务状态，但不破坏整个数据库。

数据库系统故障恢复策略

• 基本原则：冗余（ Redundancy）

• 实现方法：

  1. 定期备份整个数据库
  2. 建立事务日志 (log)
  3. 通过备份和日志进行恢复

Undo日志

记录方法：

• 记录旧数据

  • 事务的每一个修改操作前都生成一个日志记录 <T,x, old-value>

• 先写日志

恢复方法：

1. 从头扫描日志，找出所有没有<Commit,T>或<Abort,T>的所有事务，放入一个事务列表L中
2. 从尾部开始扫描日志记录<T,x,v>,如果T∈L，则write (X, v) and output (X)
3. For each T∈ L do write <Abort,T > to log

Redo日志

记录方法：

• 记录新数据

  • 事务的每一个修改操作前都生成一个日志记录 <T,x, new-value>

• 先写日志

恢复方法：

1. 从头扫描日志，找出所有有<Commit,T>的事务，放入一个事务列表L中
2. 从首部开始扫描日志记录<T,x,v>,如果T∈L，则 write (X, v) output (X)
3. For each T∈ L do write <Abort,T > to log

undo和redo对比：

	undo	redo
更新策略	立即更新（乐观）	延迟更新（悲观）
内存代价	小	大
恢复代价	大	小

Undo/Redo日志

记录方法：

• 记录新旧数据

  • 事务的每一个修改操作前都生成一个日志记录 <T, x, old-value, new-value>

• 先写日志

恢复过程：（先undo后redo！！）

1. 正向扫描日志，将<commit>的事务放入Redo列表中，将没有结束的事务放入Undo列表。
2. 反向扫描日志，对于<T,x,v,w>，若T在Undo列表中，则Write(x,v); Output(x)。
3. 正向扫描日志，对于<T,x,v,w>，若T在Redo列表中，则Write(x,w); Output(x)。
4. 对于Undo列表中的T，写入<abort,T> 。

例子：

Checkpoint

检查点技术保证检查点之前的所有commit操作的结果已写回数据库，在恢复时不需REDO。

日志轮转

为节省存储空间，防止日志文件过大。

第十章 事务处理の并发控制

并发事务调度与可串性

可串调度：一个调度的结果与某一串行调度执行的结果等价

优先图

优先图用于冲突可串性的判断 。

• 结点 (Node)：事务

• 有向边 (Arc): Ti → Tj ，满足 Ti <s Tj 存在Ti中的操作A1和Tj中的操作A2，满足A1在A2前，并且A1和A2是冲突操作

例子：

锁与可串性实现

两阶段锁(2PL)

• 事务在对任何数据进行读写之前，首先要获得该数据上的锁

• 在释放一个锁之后，事务不再获得任何锁

X Lock

• Exclusive Locks（ X锁，也称写锁）

• 只有获得R上的X锁的事务，才能对所封锁的数据进行修改。

S Lock

• Share Locks（ S锁，也称读锁）
• 如果事务T对数据R加了S锁，则其它事务对R的X锁请求不能成功， 但对R的S锁请求可以成功。
• 这就保证了其它事务可以读取R但不能修改R，直到事务T释放S锁。
• 当事务获得S锁后，如果要对数据R进行修改，则必须在修改前执行Upgrade(R)操作，将S锁升级为X锁。

Update Lock

• 如果事务取得了数据R上的更新锁，则可以读R，并且可以在以后升级为X锁
• 如果事务持有了R上的Update Lock，则其它事务不能得到R上的S锁、 X锁以及Update锁
• 如果事务持有了R上的S Lock，则其它事务可以获取R上的Update Lock
• 如果其它事务已经持有了S锁，则当前事务可以请求U锁，以获得较好的并发性

Multi-Granularity Lock

锁的粒度：指加锁的数据对象的大小可以是整个关系、块、元组、整个索引、索引项。

锁粒度越细，并发度越高；锁粒度越粗，并发度越低。

多粒度锁：同时支持多种不同的锁粒度 。

多粒度锁上的两种不同加锁方式：

• 显式加锁：应事务的请求直接加到数据对象上的锁
• 隐式加锁：本身没有被显式加锁，但因为其上层结点加了锁而使数据对象被加锁

Intension Lock

• IS锁（ Intent Share Lock，意向读锁） IX锁（ Intent Exlusive Lock，意向写锁）

• 如果对某个结点加IS(IX)锁，则说明事务要对该结点的某个下层结点加S (X)锁； 对任一结点P加S(X)锁，必须先对从根结点到P的路径上的所有结点加IS(IX)锁。

锁的相容性：