home archives github knives links
tags
categories 数据库
only title title and content
数据库
2019-11-15

1 数据库系统概述

1.1 基本概念

1.4 数据库内部结构体系

2 数据模型

2.1 数据模型的基本概念

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 关系模型与关系模型数据库系统

关系中的基本概念

3 关系数据库系统

3.3.0.1 关系数据结构

表结构

关系(Relation)

键(Key)

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

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

3.3.0.2 关系操纵

空值处理

3.3.0.3 关系中的数据约束

三类数据完整性约束

3.3.1 关系的表示

笛卡尔乘积

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

关系$R$

3.3.2 关系操纵的表示

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

相容表

投影运算

选择运算

关系的笛卡尔乘积

3.3.3 关系模型与关系代数

3.3.4 关系代数中的扩充运算

交运算

除运算

join运算

natural join运算

A 关系演算

A.1 一阶谓词演算

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

A.1.3 谓词

A.1.4 指派

A.2 关系的表示

关系演算系统

A.3 关系操纵的表示

关系演算表达式

关系演算的原子公式

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

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)$

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

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 ]

B.3.1.5 自连接

B.3.1.6 结果排序

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

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

where子句中的集合谓词

expr [ not ] in ( subquery )
expr 运算符 some|any|all ( subquery )
[ not ] exists ( subquery )

B.3.3 select语句间的运算

不加all只选取不同的值

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

B.3.4.1 统计功能

B.3.4.3 分类功能

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对数据库安全的支持

4.2 数据库的完整性

TODO

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

5.1 事务处理

5.1.1 事务

5.1.2 事务的性质

  1. 原子性(Atomicity)

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

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

5.1.4 有关事务的语句

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

  2. 持久性(Durability)

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 事务的并发执行

5.2.2 封锁

5.2.3 封锁协议

5.2.4 两阶段封锁协议

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

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

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

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

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

5.2.5 封锁粒度

封锁粒度 系统并发度 并发控制的开销
大 低 小
小 高 大
其他事务已持有的锁$\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 活锁与死锁

死锁

活锁

5.3 数据库恢复技术

5.3.2 数据库故障分类

5.3.3.1 转储

5.3.3.2 日志

undo日志

redo日志

undo/redo日志

5.3.4 恢复策略

5.3.5 数据库镜像

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

5.4 事务处理实现技术

6 数据库中的数据交换

7 数据库的物理组织

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

8.2.1 函数依赖

计算属性集$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$
    其中

$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$属性集合为$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. 合并那些具有相同关键字的子关系模式

8.2.3 多值依赖与第四范式

8.3.1 函数依赖理论

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

对于$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$是一个最小函数依赖集

寻找与函数依赖集$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 模式分解的研究

到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 概念设计

9.4 逻辑设计

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

9.5 物理设计