database system notes

数据库概述

数据库的基本概念

数据
- 结构化数据：关系数据（表）
  - 关系模型：二维表格来表示数据。每一行代表一个记录，每一列代表一个属性
- 半结构化数据：KV，XML，JSON
- 非结构化数据：文本，图像
数据库
数据库管理系统（DBMS）
数据库系统（DBS）

数据库模型

层次数据库：除根节点外，其他节点有且只有一个父节点
网状数据库：允许一个以上的结点无父亲，一个节点可以有多个父亲
关系数据库

关系模型

关系数据库的基本概念

关系数据库是表的集合：

每个表有唯一的名字
每个表可以有多个列
每个列有唯一的名字

超键：某一个属性或者属性集合可以唯一标识不同的元组，这样的属性为超键

候选键：不含有多余属性的超键：去除一个属性就不是超键了

候选键的各个属性为主属性，反之为非主属性

复选键：需要使用两个或者两个以上的属性才能唯一标识不同的元组

主键：选择多个候选键中最合适的一个作为主键

外键：R1中的属性是另一个关系模型R2的主键，这样的属性在R1上称作参照R2的外键

术语

Domain（域）：在数据库中，域表示某个属性（列）可能的所有取值范围。例如，一个“年龄”属性的域可能是所有正整数。
Attribute（属性）：表示表中的列，如“姓名”或“年龄”。
Degree（度）：指一个关系表中的属性（列）的数量。
Tuple（元组）：表示关系表中的一行数据。

关系操作

### 关系数据语言

关系运算
- 关系代数：关系代数是一种过程化查询语言。它包括一个运算的集合，这些运算以一个或者两个关系为输入，产生一个新的关系作为结果。是SQL语言的基础
  - 基本关系代数运算：
    - 选择：
    - 投影（SELECT）
    - 并
    - 差
    - 笛卡尔积
    - 重命名
  - 附加关系代数运算：
    - 交
    - 连接
      - 自然连接
      - 外连接
    - 赋值
    - 除
      
      \(A\div B\)
    表示我们要找的是那些在 B 的所有元组中都有对应记录的A。
  - 扩展关系代数
    - 去重
    - 广义投影
    - 聚集
    - 分组
    - 排序
- 关系演算
  - 元组关系演算：元组关系演算是非过程化的，它只描述所需的信息，而不给出获得该信息的具体方式。（关系代数是过程化的查询语言，提供了产生查询结果的过程序列）。表达式如下
  - 域关系演算：
SQL（结构化查询语言）

关系完整性约束

实体完整性约束：每个元组都是唯一且可区分的
- 实体完整性约束规则：
  - 主键不能取空值
  - 如果主键是复合键，则构成复合键的多个属性均不能为空值
  - 主键在关系模型中不能重复
参照完整性约束：参照关系元组在某个特定属性上的值必然等于被参照关系中某个元组在特定属性上的值。
- 区别外码约束：若属性F是基本关系R的外码，它与基本关系S的主码相对应时，则R中每个元组在F上的值必然为S中某个元组的主码值
- 参照完整性约束不要求F是S的主码
用户定义完整性约束

关系数据库语言

关系运算：
- 关系代数：过程化查询语言
- 关系演算：非过程化查询语言
  - 元组关系演算
  - 域关系演算
- 结构化查询语言SQL

SQL

SQL数据定义语言

创建表

1	create table temp_instructor like instructor

上述语句创建了一个与instructor具有相同模式的新表temp_instructor

表的数据类型

完整性约束

断言

一个断言就是一个谓词。域约束和参照完整性约束是断言的特殊形式。

修改表

删除表

创建索引

索引是一种数据结构，它允许数据库系统高效地找到关系中，那些在索引属性上取定值的元组，而不用扫描所有的元组

修改删除索引

### 视图 #### 创建视图

视图是数据库中一个查询的查询结果构成的“虚关系”,可以较少重复的查询工作。视图并不预先计算并存储，而是在使用的时候才通过查询计算出来

具体例子：

视图的属性名可以通过以下方式显式指定：

修改视图

一般来说，如果定义视图的查询满足以下条件，则称视图是可更新的：

在视图末尾包含with check option子句来定义视图，那么如果向该视图插入一条不满足where条件元组就会被j

删除视图

物化视图

物化视图（Materialized Views） 确保在数据库中存储了视图的结果集，以便可以在后续查询中直接访问这些预计算的结果

SQL操作语言

数据查询

ORDER BY 关键字默认按照升序对记录进行排序。

聚集操作

当指定了DISTINCT选项时，会消除重复取值

分窗

窗口查询用来对一定范围内的元组计算聚集函数

具体例子：

### 连接操作

join = inner join = natural join

嵌套查询

集合操作

### 数据更新

需要检查是否破坏完整性约束，如果破坏完整性约束可能会执行失败

插入操作

修改数据

实际例子：

删除数据

语法：

事务

事务由查询或更新语句的序列组成。SQL标准规定当一条SQL语句被执行就隐式的开始了一个事务。

下面的SQL语句会结束事务：

Commit Work：提交当前事务，也就是该事务的更新会在数据库中持续保持。
Rollback Work：回滚当前事务，即撤销该事务所以SQL对数据库的更新。

一旦某事务执行了commit back，它的影响就不能用rollback work来撤销了。

数据库提供了对事务的原子性，要么把事务的所有影响反映到数据库，要么不会产生任何影响

关系代数和SQL的转换

关系代数是关系数据库理论的一部分，是SQL的基础。SQL在执行时需要先转换成等价的关系代数表达式

SQL数据控制语言

存储过程和函数

函数使用的实际例子：

对于返回关系的函数，称为表函数

过程的使用例子：

可以使用call来调用过程：

支持过程和函数的语言构造

变量通过declare进行声明，使用set语句进行赋值

复合语句使用begin...end的方式构造，begin atomic... end确保复合语句以单一事务的方式运行

while和repeat语句：

for循环：

if-then-else语句：

SQL支持发信号通知异常情况，并且能够创建handler处理异常

触发器

触发器是一条语句，当数据库作修改时，它被自动的执行。执行触发器机制，必须满足两个要求：

指明什么条件下执行触发器
指明触发器执行时的动作

如下图所示：

触发器可以有效也可以设置为无效或者删除

递归查询

任何递归视图都被定义为两个查询的并：一个非递归的基查询，一个递归查询

数据库设计

数据模型

数据模型表示数据库设计的“描述”

数据模型：

逻辑数据模型
- 基于对象的模型
- 基于记录的模型
物理数据模型

概念结构设计：E-R模型

E-R模型基本元素

实体和实体集
- 实体就是对现实事物概念的某种抽象。是现实世界中可区别于其他所有对象的一个“事物”、“对象”。如一个学生，一个课程。
- 实体集是相同类型（即具有相同性质的）的实体的集合。
属性
- 用来描述实体集的数据特征
- 标识符：用来唯一标识不同实体集的某一属性
联系
- 实体与实体之间的联系
- 也可以具有描述性属性
参与：实体集之间的关联称为参与，也就是说实体集E1，E2,E3参与联系集R。
联系实例：
角色：实体在联系中扮演的功能称为实体的角色
度：参与联系集的实体集的数目称为度，二元联系集的度为2
属性：
- 域/值集：属性的可取值
- 简单和复合属性：
  - 简单：不可再划分
  - 复合：可以再划分，如name可以再划分为first name 和last name...
    - 复合属性可以有层次，如图：
- 单值和多值属性：
  - 单值：属性只有一个值
  - 多值：可以有多个值，如phone number可以有多个
- 派生属性：从别的相关属性或实体中派生出来

约束

映射基数

映射基数表示一个实体能够通过联系集能关联的实体的个数

具有以下的情况：

一对一
一对多
多对一
多对多

参与约束

基本结构

弱实体集

没有足够的属性以形成主键的实体集称为弱实体集，有主键的实体称为强实体集

转换为关系模式

具有简单属性的强实体集的表示

关系模式的每个元组同实体集E的实体相对应

强实体集的主键就是生成的模式的主键

例子：

具有复合属性的强实体集的表示

为每个子属性创建一个单独的属性来处理，而不为复合属性创建属性

多值属性：

弱实体集的表示：

联系集的表示

主键：

外码约束：对于每个与联系集R相关的实体集Ei，我们建立一个关系模式R上的外码约束，R中来自Ei主键属性的那些属性参照表示关系模式Ei的主键

关系数据库理论

规范化

范式

范式是符合某一级别的关系模式的集合。

范式之间的联系：

2NF

定义：若关系模式R属于1NF，并且每一个非主属性都完全函数依赖于任何一个候选码，则R属于2NF。

3NF

不存在非主属性对候选码的传递函数依赖

3NF属于2NF

至少一项成立

BCNF

在第一范式的基础上，不存在任何属性对候选码的传递函数依赖

这里的码是候选码

BCNF的性质：

所有非主属性都完全函数依赖于每个候选码
每个主属性都完全函数依赖于不包含它的候选码
没有任何属性完全函数依赖于非码的任何一组属性

如果一个关系数据库的所有关系模式都达到了BCNF，那么在函数依赖的范畴内，它已实现了模式的彻底分解，已经消除了插入和删除的异常

一定满足以下其中之一：

多值依赖

多值依赖的性质：

对称性：
传递性：
函数依赖是多值依赖的特殊情况

平凡多值依赖

4NF

关系模式是4NF，则一定是BCNF

小结

公理系统

Armstrong公理系统：是一套推理的规则，是模式分解算法的理论基础。

根据上述三条规则又可以得到以下规则：

根据合并规则和分解规则，可以得到：

闭包定义如下：

Armstrong公理系统具有有效性和完备性：
- 有效性：公理系统推出每个函数依赖一定在闭包中
- 完备性：闭包中的每一个函数依赖都可以由公理系统推出

可以得到以下引理：

求属性闭包的算法：

求解候选码的方法：

正则覆盖

判断无关属性：

判断正则覆盖：

计算正则覆盖：

模式分解

模式分解的定义：

F在属性\(U_i\)上的投影的定义：

模式分解的三个定义

分解后的模式应该与原模式等价。对于等价的三种定义：

分解具有无损连接性
分解要保持函数依赖
分解既要保持无损连接性，又要保持函数依赖

说明：这三个定义是实行分解的三条不同的准则

无损连接性和保持函数依赖性

定义：

说明：

如果两个关系有相同的属性列，则使用等值连接

否则用笛卡尔乘积

验证无损分解：

保持函数依赖定义：

模式分解算法

关于模式分解的几个重要事实：

若要求分解保持函数依赖，那么模式分解可以达到3NF，但不一定能达到BCNF
若要求分解具有无损连接性，则可以达到4NF

3NF分解

BCNF分解

分解法：转换为BCNF的无损连接分解

引理5：无损连接可以由更小的无损连接替换

引理6：连接满足结合律

定理6：多值依赖的充分必要条件

算法6：达到4NF的无损连接的分解：

包含函数依赖和多值依赖的有效且完备的公理系统：

得到如下的4条推理规则：

数据库存储引擎

事务管理

事务概览及其概念

事务：事务是多个数据库操作组合成的一个不可分割的、同时成功或失败的工作单元（原子）

包括四大特性：ACID：

原子性：不可分割，事务单元全部成功或全部失败（事务中的包括的所有操作要么都做，要么都不做）
一致性：正确一致，一个正确的状态转移到另一个正确的状态（事务必须使数据库从一个一致性状态转移到另一个一致性状态）
隔离性：互补干扰，多个事务并发执行和串行执行的结果应该是一致的（一个事务内部的数据和操作对并发的其他事务是隔离的）
持久性：永久保持。执行结果不会丢失（事务一旦提交，对数据库的改变是永久的）

隔离性

并发控制是实现事务隔离性的手段：

总结

可串行化调度

给定一个并发调度S，存在一个串行调度S'，如果在任何数据库状态下，S和S‘的执行结果相同，则S为可串行调度

验证一个并发调度的代价很大，一般找一个容易验证的可串行化调度方案：

冲突可串行化调度

冲突：当两个不同的事务在同一项数据上进行操作，并且两条指令中至少有一条是write时，我们说这两个操作是冲突的

冲突等价：如果调度S可以交换一系列非冲突操作变成另一个调度S’时，我们称S和S‘冲突等价

冲突可串行化调度：当调度S与一个串行调度是冲突等价的，则称S为冲突可串行化调度

优先图：

如果优先图有环则调度S是非冲突可串行化的

通过拓扑排序就可以得到一个可能的调度。

视图可串行化调度

冲突可串行化调度一定是视图可串行化调度

视图可串行化调度验证：

调度的包含关系

可恢复调度

不可恢复调度：读写了未提交事务修改的数据

可恢复调度：对于每对事务\(T_i\)和\(T_j\)，如果\(T_j\)使用了之前\(T_i\)写的数据项，那么\(T_i\)应该限于\(T_j\)提交

为什么需要恢复调度：由于失败事务会导致系统处于不一致的状态，因此必须回滚失败事务。但是，如果一个调度不具有可恢复性，就不能正确地回滚失败事务。

提交回滚：

无级联回滚调度：

数据库隔离级别

SQL标准规定的隔离级别如下：

可串行化：通常保证可串行化调度
可重复读：只允许读取已经提交的数据，并且一个事务读取同一数据项期间不允许其他事务更新该数据
已提交读：只允许读取已经提交的数据，但不保证可重复读
未提交读：允许读取未提交的数据

以上隔离级别都不允许脏写：即如果一个数据项已经被尚未提交的事务写入或中止的事务写入，则不允许对该数据执行写操作

无级联调度

对于每对事务\(T_i\)和\(T_j\)，如果\(T_j\)读取了之前\(T_i\)写入的数据，那么\(T_j\)必须在这一读操作之前提交。

数据库恢复

正向扫描日志文件

单机系统崩溃恢复

崩溃恢复的策略设计：

优缺点和解决方法：

数据页面写回磁盘时机

### 数据库日志

分为回滚日志（原子性）和重做日志（持久性）。

Undo回滚日志：

redo重做日志：

物理/逻辑日志比较：

因此redo日志不能用逻辑日志，必须用物理日志，undo必须用逻辑日志，不能用物理日志

恢复算法

影子拷贝

基于undo的日志恢复

基于redo的日志恢复

基于undo/redo的日志恢复

检查点机制：检查点之前的日志记录对应的缓冲区页面修改已经刷新到磁盘

ARIES优化策略

并发控制

悲观

锁

共享锁：读锁，S锁

互斥锁：写锁，X锁

锁表：

两阶段锁

两个阶段：

在增长阶段申请完所有的锁，申请完之后只能释放锁不能再

严格两阶段封锁协议：除了要求封锁是两阶段之外，还要求排他锁只能在事务提交之后才能释放

强两阶段封锁协议：事务在提交之前不得释放任何锁

死锁

死锁预防

wait-die：基于非抢占的机制，允许旧事物（时间戳更小）等待新事务，新事物则直接回滚
wound-wait：基于抢占机制，允许新事务等待旧事务

死锁的检测与恢复：

等待图，有环代表存在死锁：

有环则代表死锁

发现死锁后还需要从死锁中恢复：

死锁超时重启

基于图的锁协议

树形协议：必须要先拿到父节点的锁（X锁），满足冲突可串行化而且不会死锁

需要先得到数据项的偏序集，这个偏序集可以视为有向无环图，称为数据库图：

树形协议需要满足的规则：

锁的粒度

多粒度锁：

当事务给一个节点加锁，那么它的后代都被隐式的加上了锁，从根节点到这个节点上的路径上的所有节点都被加上意向锁，它本身被加上显示锁

意向锁具有三种类型：

乐观

时间戳排序协议

时间戳：

Thomas写规则：

乐观并发控制

数据库索引

索引概述

索引：通过存储（查找键，数据位置）来快速定位记录，一般以页面为单位组织（内存索引除外），插入记录时，先插入页面，再记录索引

索引的目的：用于从数据库中高效地获取满足条件的记录

索引分类

按物理存储分为：聚集索引 vs 非聚集索引

聚集索引（主索引）：

搜索码指定的顺序与文件中记录的物理顺序相同
数据按照查找键排序连续存储，范围查询更快
增删时需要维护记录，开销较大
一张表只能有一个

非聚集索引（辅助索引）：

一张表可以有多个

按索引粒度分类：稠密索引 vs 稀疏索引

稠密索引：索引到数据记录

稀疏索引：索引到文件页面

按层数分类

一层索引：哈希

多级索引：B+ tree

按索引字段分类

主键索引：建立主键上

唯一索引

索引类型

B+树索引

结构：平衡多叉查找树

根到所有叶子节点的路径长度相同

非叶子节点：

至少包含\(\lceil n/2 \rceil\)个指针
最好包含n个指针

叶子节点：

至少包含\(\lceil (n-1)/2 \rceil\)个值
最多包含n-1个值

查找算法

叶节点包含所有的索引

点查询：

区间查询：

插入算法

父节点不用产生新的节点

删除算法

哈希索引

静态哈希表

桶数固定，发生溢出时重新哈希

动态/可扩展哈希表

位图索引

只适合列上的不同值比较少

举例：

查询处理

查询处理概览

查询数量是指针对一条查询，从数据库中提取目标数据时对该查询进行处理的过程，包括：

查询解析
查询优化
查询执行：物理的实际查询

如下图：

查询解析

输入SQL语句，输出查询树

包括：

词法分析
语法分析
语义分析：检查语法分析树的语义正确性

如下图：

查询优化

输入查询树，输出物理的执行计划

包括：

逻辑优化
代价估计
物理优化

查询执行

输入为查询的执行计算，输出为查询结果

包括：

计划编译
计划执行

SQL解析

查询优化开始前，需要把SQL转为等效的关系代数

词法分析

按照查询语句的词法规则将查询语句拆解为token序列，提取关键词，标识和常量。

对不同类别的单词进行类别标记，形成字符标记流

语法分析

根据词法分析输出的原子节点构建一个语法分析树

语法分析树：

语义分析

在语法分析树上进行语义上的正确性检查，还会做等价转化为关系代数

查询算子

查询算子指关系代数运算，每种查询算子可能存在不同的物理实现方式，不同方式有不同的适用场景

如下图：

磁盘I/O代价度量

在大型数据库系统中，磁盘I/O的代价最主要，用磁盘I/O的块数作为代价度量的指标

用B(R)表示R占用的磁盘块数，T(R)表示R的元组条数，M表示内存缓冲块数

排序算子

主要的实现方式是外部归并排序（内存不够）

外部归并排序：

排序：划分归并段
归并：已排序的归并段归并

代价：

排序和归并阶段都需要从磁盘拿出所有元组，然后再放回，因此访问次数为B(R)。这是课本上的磁盘块传输总数，最后一次不考虑放回

选择算子

分为两大类：

线性扫描
索引扫描

线性扫描

代价：B(R)

索引扫描

聚簇索引，非聚簇索引，等值选择，范围选择

课本上的代价估计：

连接算子

嵌套循环连接

最好的情况是内存空间足够，只要内存能够装下内存循环即可：

即一个两层循环

代价：B(R)+T(S)B(S)

块嵌套循环连接

可以优化为：

索引嵌套循环连接

待学习

排序归并连接

如图，是一个例子：

代价分析：

哈希连接

课本上为构造阶段

实现方式：

如图所示：

代价分析：

构造阶段：

约束条件：

如果不满足上述约束条件，可以进行递归划分，直到每个划分最多占M块为止。代价如下：

总结：

其他算子

去重，集合，分组聚合基本用排序和哈希实现：

外部归并排序
哈希连接的划分阶段

去重：

集合：

聚集：

不需要等到聚合完成才进行聚合函数的计算，可以在聚合过程中就维护着

查询优化

查询优化流程：

查询重写（逻辑优化）

查询重写：按照关系代数的等价规则，对查询的关系代数表达式进行等价转换，提高查询效率

等价规则：

基于规则
基于代价

基于规则

规则：

重写顺序

不一定最优：

规则的枚举顺序一般为：

其他查询策略

子查询转为连接：

常数传播：

代价估计

为什么需要代价估计：

基数估计

基数：查询结果的元组数，表示为card(p)

选择度：符合p的元组占所有元组的比例，表示为sel(p)

选择运算的基数估计：

假设服从均匀分布
假设每个属性独立

使用直方图

连接运算的基数估计

优化器做了以下简化假设：

单个属性上做连接

还可以得到：

多个属性上连接：

多个关系多个属性连接：

其他算子的基数估计

简答题

简述系统故障时的数据库恢复策略

正向扫描日志文件，找出故障时已经提交的事务，并将事务标识加入Redo队列。同时找出故障时尚未提交的事务，并将事务标识加入Undo队列。对Undo队列的事务进行撤销处理，对Redo队列的事务进行重做处理。

说明视图与基本的区别和联系

视图是从一个或几个表中导出的表，它与基本表不同，它是一个虚表。视图并不存储数据，数据存储在定义视图所引用的表中。视图在概念上与基本表等同，用户可以如同基本表那样使用视图，也可以在视图的基础上建立视图。

简述事务的特性

原子性：一个事务里的所有操作要么都完成要么都不完成
一致性：事务必须保证数据从一个一致性状态到另一个一致性状态
隔离性：一个事务的内部操作和使用的数据对并发的其他事务是隔离的
持久性：事务一旦提交，对数据库的改变是永久的

试述关系模型的外码约束和普通参照完整性约束的规则

外码约束：若属性F是关系模型R上的外码，它与基本关系S上的主码K相对应。R中每个元组F上的每一个值都必须为S中某个元组的主码值

参照完整性约束：参照完整性约束不要求K为主码，取值方面要求与外码约束一致