数据库笔记

---

第一章

DBMS（数据库管理系统）

DBMS是一个存储数据的系统，同时为软件提供数据访问。

目标：

• 海量数据 (massive)

  • 异构（图片，声音，鼠标点击）
  • 数据存放在外存

• 持续存储（persistent）

• 安全（safe）

  • 避免丢失，被覆盖

• 多用户（multable user）

  • 多用户可以访问数据的不同部分
  • 数据一致性
    • 并发控制
    • 一致性和性能之间的权衡

• 方便（convenient）

  • 便于处理大量数据
  • 物理数据独立性：数据的存储、布局方式与程序逻辑（程序访问数据）无关
  • SQL查询语言

• 高效（efficient）

• 可靠（reliable）

  • 随时可用
  • 备份

数据模型

描述数据结构，数据上的操作，数据的约束的集合

• 关系型数据模型（结构化）
• 半结构数据模型（例：xml）
• 图数据模型

模式（schema）

定义数据库的结构，数据的类型
模式不经常更改，而数据更改很快
模式也是一种数据（数据的数据，元数据）

DDL,DML

• DDL
• DML

---

第二章

关系数据模型

关系

关系是两个或两个以上集合的笛卡尔积的子集

• 一种集合
• 笛卡尔积
  • 设 A = {a1,a2,…}, B = {b1,b2,…}
  • A 和 B 的笛卡尔积 A x B = { <a,b> | a属于A, b属于B}
• 关系是各个属性集的笛卡尔积的子集

关系数据模型的组件

• 数据库是有名字的关系（表）的集合
• 每张表（关系）拥有若干属性（列）
• 每个元组（行）在每个属性（列）上都有一个值
• 每个属性（列）都有类型

一些概念

• schema（模式，属性集） 描述数据库中的关系，不经常变化
• instance（实例） 给定时间点的实际内容，随时间变化
• NULL 未知或未定义
• key（键） 所有元组拥有唯一取值的属性的或独一五二的属性的集合

创建和使用关系数据库

• 使用 DDL 设计模式（schema）
• 使用 ETL 工具对数据操作
  • 提取
  • 变换
  • 加载
• 重复执行查询和修改

查询的结果

关系数据库中任何查询的结果是关系

解释：

• 在上一次的查询结果上可以进行组合查询
• 封闭的 （查询的对象是关系，结果也是关系）

查询语言

• 关系代数 （人来查询）
• SQL （机器来查询）

这两种查询语言在功能上等价

---

第三章

关系运算

最简单的查询：一张表的所有元组

代数的核心：表达式

一个单独的关系是一个表达式，嵌套了关系运算符的表达式仍是表达式

关系代数表达式有值，最基本的表达式就是关系名

基本运算符

• 选择（select）运算符：σ

  • σ Cond (Relation) Cond:条件，Relation: 关系
  • 作用：选择某些行

• 投影（project）运算符： π

  • π A1,…,An (Relation) A:列名
  • 作用：选择某些列，结果没有重复的行（这里与SQL不同）

• 连结（join）运算符：×

  • tableA × tableB
  • 作用：两个关系的组合 结果的行数等于tableA的行数与tableB的乘积

• 自然连接：⋈

  • 对具有相同名称的属性取值要相等
  • 消去重复属性

• θ 连接：默认的连接

集合运算符

• 并集：∪
  • 垂直方向上对元组进行组合，使元组个数增加
• 差集：A - B
  • A 中有但 B 中没有
• 交集：∩
  • 可以由差集构造出来 A ∩ B 等价于 A - ( A - B )

schema(A) = schema(B) 时，A ∩ B 相当于 A ⋈ B

---

第四章

数据库设计

单表设计异常

• 数据冗余（Redundancy）：
  • 坏处：相同信息被存储多次，不利于修改，造成数据不一致
  • 好处：提高安全性（备份)，加速查询（缓存）
• 更新异常
• 删除异常

范式

第一范式（1NF）

原子性：保证每一列不可再分

第二范式（2NF）

前提：满足第一范式
每行都是独一无二的，要有主键
每张表只描述一个事情

第三范式（3NF）

前提：满足第一范式和第二范式
要确保表的每一列都与主键直接相关，不能间接相关

Boyce-Codd范式（BCNF）

位于第三范式和第四范式之间
定义：对R上的任意的函数依赖，如果属性集A都函数地决定B，那么A应该是键
用于解决函数依赖造成数据冗余的问题

第四范式（4NF）

定义：在关系R上，如果对于每个多值依赖A->->B，那么A是键。
用于解决多值依赖造成数据冗余问题

函数依赖

如果A函数地决定B(或B函数地依赖A)，记为A -> B

如果A函数地决定了所有属性等价于A是一个键

关系中不能有重复的元组

• 分解规则
• 组合规则

属性的闭包（closure）

属性集A的闭包是所有依赖于A的属性的集合

如果属性集A的闭包是全部属性组成的集合，那么属性集A是键

如果属性集A是键，那么A的超集也是键

无损分解

如果关系A可以分解成B和C，并且满足

• schema(B)与schema(C)的并集等于schema(A)
• B与C的自然连接是A的超集

那么该分解为无损分解

多值依赖

记为：A->->B
定义：在关系R上，如果存在属性A相等的两个元组t,u，那么必然存在另一个元组v在属性B上和其中一个元组相等但在rest上不等。

• A到B是一到多的映射。
• 函数依赖都是多值依赖。

BCNF和4NF的缺点

• 造成过度分解

主属性

包含在键中的属性就是主属性

3NF分解

满足3NF的关系R，对每个平凡函数依赖A->B，要么A是键要么A是主属性。

第五章

实体关系模型

• 实体：事物或对象
• 实体集：相似的实体组成的集合
• 属性：实体集的属性，一般为单一的值，不能为结构体或集合
• 关系：指的是多个实体之间的联系，该联系允许拥有隶属于这段联系的独立的属性
• 关系集：某个特定关系类型联系的所有实体的集合

E-R图（entity-relationship diagram）

• 实体集：矩形
• 属性：椭圆
• 关系：菱形
• 多对多：直线或曲线
• 多对一：单向箭头
• 一对一：双向箭头
• 子类：三角形箭头
• 弱实体集：自身没有键要依赖其他强实体集才能有键，用双实线矩形
• 多值属性：双实线椭圆
• 主键：下滑线

实体之间的联系

• 多对多
• 多对一
• 一对一

设计原则

• 尽量少用弱实体集，每个实体集都要有自己的键
• 多对一的多的那一方要建模为实体集，如果是一的那一方必须要有除键外的其他属性才能建模为实体集
• 如果E-R图中的关系有一些属性，那么要将关系建模为数据库中的一张表
• 合并关系，多对一的关系可以合并到多的那一方的表的属性中
• 对于弱实体集，可以建立一张包含弱实体集全部主属性的表
• 对于子类
  • 所有子类都建模一张表
  • 只建立父类的表，空的子类用nulls

第六章

存储管理

文件 file

• 文件是pages的集合
• pages是记录的集合

文件类型

• 未排序的堆文件
• 分类簇的未排序堆文件
• 排序文件
• 索引文件：一定是有序的

页面 page

record id = (page, location in page) = (page, slotId)

页面组成

• page header/footer
• record

槽化页面 slotted page ：现代数据库基本都使用这种

记录 record

• header
• 字段

索引

稠密索引：每个数据都有索引
稀疏索引：不是每个数据都有索引

哈希表

• 链式哈希（哈希桶）：每个表项链接多个桶，桶里存若干条记录
• 开放地址哈希：哈希值相同的记录需要链接起来
• Cuckoo Hash 布谷鸟哈希：使用2个hash函数（对应两个表）来处理碰撞，从而每个key都对应到2个位置
• 动态哈希：引入一个仅存储桶指针的目录数组，用翻倍的目录项数来取代翻倍的桶的数目，且每次只分裂有溢出的桶，从而减小翻倍的代价。

B+树

B+树的特点：

• 动态树索引、平衡树
• 高效插入、删除
• d<=m<=2d,d是结点的度，m为阶(order)，m为结点中最大键值个数
• 每个内部结点的最大子结点数：扇出系数=2d+1
• 数据记录只存放在叶子结点，页面内部的记录要排序，页面之间用指针链接

• 聚簇索引：索引的叶子结点就是数据page
  • 要对数据排序，数据是索引的一部分
  • 一个表只能建立一个
• 非聚簇索引：
  • 不用按数据排序
  • 一个表能建立多个

第七章

• 并发控制

事务 transaction

事务（Transaction）是一种机制、一个操作序列，包含了一组数据库操作命令。事务把所有的命令作为一个整体一起向系统提交或撤销操作请求，即这一组数据库命令要么都执行，要么都不执行，因此事务是一个不可分割的工作逻辑单元。

事务的基本原则 ACID

原子性 （Atomicity）

要么都成功，要么都失败

一致性 （Consistency）

事务提交后的数据要保持一致

隔离性 （Isolation）

隔离性是当多个用户并发访问数据库时，比如操作同一张表时，数据库为每一个用户开启的事务，不能被其他事务的操作所干扰，多个并发事务之间要相互隔离。

持久性 （Durability）

事务提交后的数据持久化保存在数据库中，提交后不可逆

事务的隔离级别

四个级别：

• 读未提交：可以脏读，可以不可重复读，可以幻读
• 读已提交：不可以脏读，可以不可重复读，可以幻读
• 可重复读：不可以脏读，不可以不可重复读，可以幻读
• 可串行化：不可以脏读，不可以不可重复读，不可以幻读

脏读

一个事务读取了另一个事务未提交的数据

不可重复读

一个事务内读取到了另一个事务更新的数据，多次读取的结果不同

虚读或幻读

在一个事务内读取到了另一个事务插入的数据，导致前后数据读取不一致

调度

多个事务的读写操作按时间排序的执行序列

串行调度

各个事务之间没有任何操作交错执行，事务一个一个执行。

可串行调度 Serializable

如果一个调度的结果与某一串行调度执行的结果等价，则称该调度是可串行化调度，否则是不可串调度。

冲突可串行调度 Conflict-serializable

冲突(Conflicts)操作：

• 这两个操作属于不同的事务
• 这两个操作涉及相同的对象，且至少一个操作是写

冲突可串行：

• 能够通过交换非冲突操作，将调度改变为可串行的调度

第1步: 将调度S表示为有向图(precedence graph)

• 每个顶点代表S中的一个事务
• T从事务Ti到事务j有一条有向边(arc)，如果Ti的某个操作oi和Tj的某个操作oj冲突，并且oi在S中先于oj

第2步: S是冲突可串行化调度，当且仅当其优先图没有环(acyclic)

• 优先图顶点的任意拓扑序(topologicalorder)表示了一个与S冲突等价的串行调度

视图可串行化

两个调度S1和S2视图等价，如果

• 如果S1中事务T1读了对象A的初始值，则S2中T1也读了A的初始值
• 如果S1中事务T1读了事务T2修改过的A值，则S1中T1也读了T2修改过的A值
• 如果S1中事务T1写了A的最终值，则S2中T1也写了A的最终值

如果一个调度视图等价于某个串行调度，则该调度是视图可串行化调度(view serializable schedule)。

锁 Lock

• 乐观锁：操作数据时不会对操作的数据进行加锁（这使得多个任务可以并行的对数据进行操作），只有到数据提交的时候才通过一种机制来验证数据是否存在冲突(一般实现方式是通过加版本号然后进行版本号的对比方式实现);
• 悲观锁：每次请求都会先对数据进行加锁， 然后进行数据操作，最后再解锁

两段锁(Two-Phase Locking，简称2PL)协议

运用封锁方法，避免冲突操作。

2PL协议规定所有事务必须分两个阶段对数据项加锁和解锁：

• 阶段1：
  • 在读任何数据之前，都要获得数据的共享锁 S
  • 在写任何数据之前，都要获得数据的排他锁 X
• 阶段2：
  • 一个事务释放锁之后，就不能再获取新的锁了

并发执行的所有事务均遵守两段锁协议，则对这些事务的任何并发调度策略都是可串行化的。所有遵守两段锁协议的事务，其并发执行的结果一定是正确的。

但2PL协议不能避免级联撤销问题（一个事务回滚，受它影响的事务也要回滚）。

严格的2PL协议可以避免级联撤销问题。
严格的2PL协议：在释放锁的时候要一起释放所有锁。

锁的粒度

• Database
• Table
• Page
• Record

意向锁 Intention Lock

多粒度封锁协议中，避免对子孙结点的检测

• 意图共享锁 IS
• 意图排他锁 IX
• 共享意图排他锁 SIX

在对资源结点加锁时，必须给该结点的所有祖先结点都加上意图锁。
好处：对新的结点加锁时就不需要检测其子孙结点了

• 事务在获取行级 S 锁之前，必须获取其对应表的 IS 或 IX 锁
• 事务在获取行级 X 锁之前，必须获取其对应表的 IX 锁

恢复管理

保证原子性和持久性

• STEAL：未提交事务的数据可以写回磁盘
• NO STEAL：未提交事务的数据不可以写回磁盘
• FORCE：已提交事务的数据立即写回磁盘
• NO FORCE：已提交事务的数据不一定立即写回磁盘（延迟写）

并发度最高的组合：STEAL + NO FORCE

保证未提交事务的原子性，已提交事务的持久性

引入日志

日志

存放按时间顺序的记录，保证REDO和UNDO

• Undo一般用于事务的取消与回滚，记录的是数据被修改前的值
• Redo一般用于恢复已确认但未写入数据库的数据，记录的是数据修改后的值

log record: <XID,pageId,old data,new data>

写优先日志协议

• 在数据页写回数据磁盘之前，必须确保日志写回日志磁盘
• 事务提交之前，确保所有操作记录到日志里

STEAL + NO FORCE + log 可以确保原子性和持久性

LSN 日志序列号

pageLSN: 每个page在磁盘里的最后一条日志
flushedLSN: 在内存里面，指向日志磁盘的最后一条日志

保证 pageLSN<=flushedLSN

日志写回日志磁盘的时候是不能中断的（一直占用CPU）

Tx Table: 用来记录所有正在进行的Tx信息的table
Dirty_Page Table：用来记录脏页的Redo Log的“可能的”开始位置

检查点 checkpoint

系统崩溃恢复时，从最后一个checkpoint开始向后搜索日志，来减少日志搜索范围

checkpointing记录包含事务表和脏页表，可以得到哪些事务已经提交，哪些事务还未提交

第八章

查询处理及优化

查询处理

SQL语言 –> 解析和翻译 –> 关系代数表达式 –> 优化器 –> 查询执行计划 –> 执行引擎 –> 查询输出

• 原语操作：带有标注信息的关系代数运算

• 查询执行计划：一系列原语操作序列

• 优化：

选择、投影运算要尽量早做
连接运算尽量后做