数据库_数据库设计

发表于 2020-06-04 更新于 2022-11-13 分类于学习笔记，数据库

数据库设计概述

特点

反复性：反复设计、逐步求精
多解性：设计结果不唯一，多种方案并存
分步进行：数据库设计分为多个阶段
结构设计与行为设计相结合
- 面向数据的设计方法（以信息需求为主）
- 面向过程的设计方法（以处理需求为主）

数据库设计方法

直观设计法（手工试凑法）
规范设计法
- 新奥尔良法：运用软件工程的思想和方法进行数据库设计
- 基于E-R模型的设计法：先用E-R图构造企业模式，然后转换为特的那个数据库模式
- 基于3NF的设计法：确定数据库模式中的全部属性和属性间的依赖关系，将它们组织在一个单一的关系模式中，然后再分解成若干个3NF关系模式的集合
- 基于视图的设计法：先为每个应用建立视图，再将这些视图合并为全局概念模式
计算机辅助设计法：
- 以人的知识或经验为主导，通过人机交互方式实现设计中的某些部分

E-R模型

概念模型

1、语义表达能力丰富

2、易于理解和交流

3、易于修改和扩充

4、易于向各种数据模型转换

可以使用E-R模型、UML、ODL

E-R模型的基本观点：现实世界是由实体和实体间的联系构成的。

实体：客观存在并且可以相互区分的物体。
实体集：具有相同类型、相同属性的实体集合。
属性：实体集中每个成员具有的描述性性质。
- 原子属性——不可再分的属性
- 复合属性——由多个原子属性构成，如：生日（年、月、日）
- 多值属性——多个同类原子/复合属性值，如：买家有多个收货地址
域：属性的取值范围。
码：能唯一标识实体集的属性或属性组，称为超码。而最小的超码（就是任意真子集都不能称为超码的超码）称为候选码。从候选码中选出一个来区别同一实体集中的不同实体称为主码（比如学生实体集中的学号）。主码在E-R图中用_____表示。
联系：实体之间相互的关联，如学生和老师的授课关系，同类联系的集合称为联系集。
元或度：参与联系的实体集的个数称为元。参与联系的实体集的主码的集合形成了联系集的超码。
参与：实体集之间的关联称为参与，实体参与联系。如学生选修课程，学生和课程参与了联系选修。

E中所有实体均参与R称为E全部参与R（用实体集合联系间的双线表示），否则称为E部分参与R。
映射基数：实体之间的联系数量，即一个实体通过一份联系集能与另一实体集相关联的实体数目。
- 一对一
  
  注意箭头：带箭头的表示1
- 一对多
  
  不带箭头的线段表示n
- 多对多

E-R模型的表示方法

总结来说，E-R图的四个组成的部分

1、矩形框:表示实体，在矩形框中写上实体的名字

2、椭圆形框:表示实体或联系的属性

3、菱形框:表示联系，在框中记入联系名

4、连线:实体与属性之间;实体与联系之间;联系与属性之间用直线相连，(对于一对一联系，要在两个实体连线方向各写1; 对于一对多联系，要在一的一方写1，多的一方写N;对于多对多关系，则要在两个实体连线方向各写N,M。)。

E-R模型的设计原则

避免冗余，避免浪费空间和操作异常。
一般情况下，凡是可以作为属性对待的，应该尽量作为属性
作为实体对待，应该满足如下条件中的一个：
- 该实体具有除码以为的其他属性
- 该实体是某个一对多或多对多联系的”多“端

概念结构设计

概念结构设计的方法与步骤

设计概念结构的E-R模型可采用四种方法
- 自顶向下
- 自底向上
- 逐步扩张
- 混合策略
最常用的方法是自底向上设计法，包含两个步骤：
- 设计局部E-R模型，即设计用户视图
- 集成各局部E-R模型，形成全局E-R模型

步骤一

设计局部E-R模型

步骤二

1、合并局部E-R图，消除冲突，生成初步E-R图

属性冲突

属性域冲突——属性值的类型、取值范围或是取值集合不同
属性取值单位冲突

属性冲突属于用户业务上的约定，必须与用户协商后解决

命名冲突

同名异义
异名同义

命名冲突的解决方式同属性冲突

结构冲突

同一对象在不同应用中有不同的抽象
同一实体在不同应用中属性组成不同
同一联系在不同应用中呈现不同的类型

2、消除不必要的冗余，生成基本的E-R图

冗余包括冗余的数据和冗余的联系
- 冗余的数据是指可由基本数据导出的数据
- 冗余的联系是指可由其他联系导出的联系
通常采用分析的方法消除冗余。依据为数据字典和数据流图。

逻辑结构设计

任务和步骤

数据库逻辑设计的任务是将概念结构转换成特定DBMS所支持的数据模型
步骤
- 初始化关系模式设计
- 关系模式优化
- 设计子模式

步骤一：初始关系模式设计

1、E-R图向关系模型转换

实体的转换
- 一个实体转换为一个关系
- 关系的属性就是该实体的属性
- 关系的码就是该实体的码
联系的转换
- 一个联系转换为一个关系
- 关系的属性：与该联系相连的各实体的码和该联系自身的属性
- 关系的码
  - 一对一的二元联系：两端实体的码都是候选码
  - 一对多的二元联系：”多“端实体的码
  - 多对多的二元联系：至少包含两端实体的码的并集
  - 存在”一“端的多元联系：除了一端以外的其他实体的码的并集
  - 不存在一端的多元联系：至少包含所有相关尸体的码的并集
- 关系的外码：对于每个与联系相连的实体，建立与该实体关系的外码约束

1对多或者多对1的联系可以被合并到1端实体对应的关系中

步骤二：关系模式优化

进行规范化，消除关系模式中存在的各种异常，改善完整性、一致性和存储效率
进行反规范化设计，是为了提高查询效率

垂直分解

把关系模式的属性分解为若干个子集

水平分解

把关系中的元组分解为若干个子集

步骤三：设计子模式

制导思想：注重局部用户的要求

具体方法：

使用更符合用户习惯的别名、计量单位等
从安全性出发，对不同级别的用户定义不同的视图
从易用性触发，将复杂查询语句定义为视图

物理结构设计

任务

对于给定的逻辑模型，设计一个最合适应用要求的物理结构

约束条件：

应用需求（响应时间、吞吐率、存储空间利用率、安全）
应用特征（数据量、事务频率、涉及的关系和属性）
具体DBMS产品的特点（存取方法，存储结构，参数）
存储设备特性

设计内容：

设计存取方法
设计存储方案
确定系统配置参数

设计存取方法

参考文章

索引
聚簇

聚簇索引的叶子节点就是数据节点，而非聚簇索引的叶子节点仍然是索引节点，只不过有指向对应数据块的指针。

索引

是与基表的属性组相关的数据对象，能够提供对基表数据的快速访问。

同一个基表上可键多个索引，执行查询语句，DBMS自动选择合适的索引访问数据

当表中的数据更新时，DBMS自动更新索引

数据越多，索引的优势越明显

索引可以提高查询效率，但是增加了空间开销以及维护的代价

B+树索引

B-Tree介绍

B-Tree是一种多路搜索树（并不是二叉的）：
1.定义任意非叶子结点最多只有M个儿子；且M>2；
2.根结点的儿子数为[2, M]；
3.除根结点以外的非叶子结点的儿子数为[M/2, M]；
4.每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
5.非叶子结点的关键字个数=指向儿子的指针个数-1；
6.非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
7.非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
8.所有叶子结点位于同一层；
如：（M=3）

B-树的特性：
1.关键字集合分布在整颗树中；
2.任何一个关键字出现且只出现在一个结点中；
3.搜索有可能在非叶子结点结束；
4.其搜索性能等价于在关键字全集内做一次二分查找；
5.自动层次控制；

B-树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点；

B+树是B-树的变体，也是一种多路搜索树：

1.其定义基本与B-树同，除了：

2.非叶子结点的子树指针与关键字个数相同；

3.非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）；

5.为所有叶子结点增加一个链指针；

6.所有关键字都在叶子结点出现；

如：（M=3）

B+的搜索与B-树也基本相同，区别是B+树只有达到叶子结点才命中（B-树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；

B+的特性：

1.所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；

2.不可能在非叶子结点命中；

3.非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；

4.更适合文件索引系统；

适用范围广：

等值查询
范围查询
聚集函数计算
排序
遍历

hash索引

适用于：

等值查询
等值连接

不适用于：

范围查询
排序
模糊

聚簇

为了提高查询速度，把在某个属性组上具有相同值的元组集中地存放在相邻的物理块中。该属性组称为聚簇码。

单表聚簇：将单个表的数据按聚簇码分组有序的存储
多表聚簇：把多个表的数据按聚簇码集中存储在一起

设计原则

一个表最多只能属于一个聚簇
聚簇维护的开销很大
频繁更新的属性不适合作为聚簇码
单表聚簇：最常用于等值比较的属性，且该属性上的重复取值较多
多表聚簇：经常进行连接操作的表可以建立聚簇

设计存储方案

确定数据的存放位置：
- 将表和索引分别存放在不同的磁盘上
- 将日志文件和数据库对象放在不同的磁盘上
- 将数据库的备份文件存放在磁盘上
对空间效率要求较高的应用，考虑压缩存储
对安全需求较高的应用，考虑加密存储

确定系统配置参数

根据应用特点和运行环境重新配置系统配置参数：

最大连接数
内存配置参数（查询缓存、日志缓存、数据缓存······）受总的物理内存大小的约束，参数之间相关制约
存储配置参数（数据文件的大小、日志文件的大小、物理块大小、物理块装填因子）
其他

数据库_关系数据理论概述

发表于 2020-06-04 更新于 2022-11-13 分类于学习笔记，数据库

关系数据理论概述

数据库逻辑结构设计的任务：为数据库应用构造良好的数据库模式

关系模式中的异常问题

数据冗余
更新异常
插入异常
删除异常

出现异常的原因：

关系模式中存在不合适的数据依赖

解决方式：

通过分解，消除不合适的数据依赖（规范化）

函数依赖

关系模式

一个关系模式可以表示为一个五元组R(U,D,DOM,F)；

R：关系名称
U：R中所有属性的集合
D：U中属性所来自的域的集合、
DOM：属性到域的映射
F：U中属性间的数据依赖的集合

模式涉及重点关注U和F

数据依赖

是一个关系中的属性之间的某种语义约束关系

知道A可以确切的找到B，这样的函数叫做函数依赖。其实就是单值函数

函数依赖

分类一：

平凡函数依赖：任何情况下都成立
例如：在一个职工关系中,职工号总能函数决定它本身,记作“职工号→职工号”,对于任一个给定的职工号,都有它本身的职工号值唯一对应,此为平凡函数依赖。又如:职工号和性别构成的属性子集总是能够函数决定其中的职工号或性别属性,可分别记作为“(职工号,性别)→职工号”和“(职工号,性别)→性别”,因为对于任何给定的一个元组中的职工号和性别的组合值,都唯一对应一个职工号值或性别值,不可能出现其他的职工号值或性别值,此种也为平凡函数依赖。
非平凡函数依赖
如在职工关系中,职工号函数决定其他每个属性都是非平凡函数依赖,另外“(职工号,姓名)→性别”也是非平凡函数依赖,虽然在这里由决定因素中所含的职工号单属性就能够函数决定性别,而带有的姓名属性有些多余。

分类二：

完全函数依赖：记作是f

设R（U）是属性集U上的关系，x、y是U的子集，x’是x的真子集。若对于R（U）的任何一个可能的关系，有x→y但x’→y，则称y完全函数依赖于x，记作X→^F^Y。
所谓完全依赖是说明在依赖关系的决定项（即依赖关系的左项）中没有多余属性，有多余属性就是部分依赖。
部分函数依赖：记作是p

设R（U）是属性集U上的关系，x、y是U的子集，x’是x的真子集，若x→y且x’→y，则称y部分依赖x，记作X→^P^Y。显然，当且仅当x为复合属性组时，才有可能出现部分函数依赖。

例如：职工号姓名性别年龄职务
1001 张三男 36 正处
1002 李四男 38 副处
1003 王五男 50 正科
1004 赵六女 38 副处
1005 孙七女 49 科员
职工号和其他的属性之间的函数依赖都是完全函数依赖。因为职工号是一个单属性决定因素，他不可能在包含其他任何属性，那么就不存在真子集函数决定其他每个属性的情况存在，如（职工号，性别）的值虽然能够决定相应职工的年龄，但其中的真子集“职工号”就能够函数决定其年龄，所以（职工号，性别）到年龄之间的函数为部分函数依赖（因为只通过“职工号”就可以决定）。（简单的说：真子集可以决定结果）

假设存在：“学号→系号”、“系号→系名”和“系号→系主任名”
那么存在：“学号→系名”和“学号→系主任名”这两个函数依赖是传递函数依赖。

分类三：

传递函数依赖

一个关系R（U），X,Y,Z为属性集U上的子集，其中存在X→Y和Y→Z，但Y不决定X，同时Y不包含Z，则存在X→Z，即X传递函数决定Z，Z传递函数依赖于X。

有关码的术语

码：一个关系的所有属性

码为单个属性，称为单属性码
码为多个属性，称为多属性码
码为全部属性，称为全码
包含一个码的属性组，称为超码。
包含在任何一个码中的属性，称为主属性
不包含在任何一个码中的属性，称为非主属性

候选码： 唯一标识一个关系的属性组
主码： 候选码多于一个，从候选码中选出的一个码作为主码。
主属性： 候选码的所有属性。
非主属性： 不包含在任何候选码中的属性
全码： 极端情况下，整个属性组都是码。
外码： X不是该关系模式的码，但是X是另一个关系模式的码。比如(Sno,Cno,Grade)中的Sno不是码，但Sno是(Sno,Sname,Sage)的码，则Sno是外码

1NF、2NF、3NF和BCNF

参考文章

规范化

是为了减少数据冗余和消除各种异常。

范式：满足规范化要求的关系模式

范式分类：

第一范式：满足最基本的规范化要求的关系模式
第二范式：在第一范式的基础上，进一步满足一些要求
依次类推：第三范式、BC范式、第四范式等

第一范式（1NF）：无重复列

1NF的定义为：符合1NF的关系中的每个属性都不可再分。

第一范式（1NF）是指数据库表的每一列都是不可分割的基本数据项，同一列中不能有多个值，即实体中的某个属性不能有多个值或者不能有重复的属性。如果出现重复的属性，就可能需要定义一个新的实体，新的实体由重复的属性构成，新实体与原实体之间为一对多关系。在第一范式（1NF）中表的每一行只包含一个实例的信息。简而言之，第一范式就是无重复的列。

　　说明：在任何一个关系数据库中，第一范式（1NF）是对关系模式的基本要求，不满足第一范式（1NF）的数据库就不是关系数据库。

问题：可能会出现：数据冗余、更新异常、插入异常、删除异常

第二范式（2NF）：属性完全依赖于主键【消除部分子函数依赖】

满足第二范式（2NF）必须先满足第一范式（1NF）。第二范式（2NF）要求数据库表中的每个实例或行必须可以被唯一地区分。为实现区分通常需要为表加上一个列，以存储各个实例的唯一标识。例如员工信息表中加上了员工编号（emp_id）列，因为每个员工的员工编号是唯一的，因此每个员工可以被唯一区分。这个唯一属性列被称为主关键字或主键、主码。

　　第二范式（2NF）要求实体的属性完全依赖于主关键字。所谓完全依赖是指不能存在仅依赖主关键字一部分的属性，如果存在，那么这个属性和主关键字的这一部分应该分离出来形成一个新的实体，新实体与原实体之间是一对多的关系。为实现区分通常需要为表加上一个列，以存储各个实例的唯一标识。简而言之，第二范式就是属性完全依赖于主键。

比如给出一个表：
$$
(Sno,Sdept,Sloc,Cno,Grade)
$$
其中Sno学号，Sdept是系，Sloc是寝室地址，Cno是课程号，Grade是该学生某个课程的成绩。
$$
(Sno,Cno)\stackrel{F}{\longrightarrow}Grade\Sno→Sdept, (Sno,Cno)\stackrel{P}{\longrightarrow}Sdept\
Sno→Sloc, (Sno,Cno)\stackrel{P}{\longrightarrow} Sloc
$$
那么上述存在了部分函数依赖，需要把部分函数依赖的进行消除：
$$
Sno→Sdept \
Sno→Sloc
$$
因此得出新的关系模式：
$$
(Sno,Sloc,Sdept)\
(Sno,Cno,Grade)
$$
判断的方法是：

第一步：找出数据表中所有的码。
第二步：根据第一步所得到的码，找出所有的主属性。
第三步：数据表中，除去所有的主属性，剩下的就都是非主属性了。
第四步：查看是否存在非主属性对码的部分函数依赖。

问题：可能会出现：数据冗余、更新异常、插入异常、删除异常

结论：对码的传递依赖不友好

第三范式（3NF）属性不依赖于其它非主属性[消除传递依赖]

https://blog.csdn.net/qq_43371004/article/details/88970261

第三范式（3NF） 3NF在2NF的基础之上，消除了非主属性对于码的传递函数依赖。

第三范式（3NF）要求一个数据库表中不包含已在其它表中已包含的非主关键字信息。

例如，存在一个部门信息表，其中每个部门有部门编号（dept_id）、部门名称、部门简介等信息。那么在的员工信息表中列出部门编号后就不能再将部门名称、部门简介等与部门有关的信息再加入员工信息表中。如果不存在部门信息表，则根据第三范式（3NF）也应该构建它，否则就会有大量的数据冗余。简而言之，第三范式就是属性不依赖于其它非主属性。

结论：主属性对码的不良函数依赖也会导致异常

BC范式（BCNF）消除主属性对于码的部分与传递函数依赖

所有非主属性对每一个码都是完全函数依赖；
所有的主属性对每一个不包含它的码，也是完全函数依赖；
没有任何属性完全函数依赖于非码的任何一组属性。

多值依赖和4NF

多值依赖

多值依赖：设R(U)是属性集U上的一个关系模式，X,Y,Z是U的子集，且Z=U−X−Y。当且仅当R(U)的任一关系r，给定的一对(x,y)值，有一组Y的值，这组值仅仅取决于X的值而与Z的值无关，则成R(U)中的多值依赖$X\rightarrow \rightarrow Y$成立。

判定方法：对于任意关系中，如果存在两个元组（就是行），记为A,B，如果他们的某一属性X的值相等，那么我们交换它们另外的属性Y的值后，得到的新的两个元组，在表中是可以在原来的表中找到与它们相匹配的元组的。

平凡多值依赖：若$X \rightarrow \rightarrow Y$，而$Z=\empty$，则称$X\rightarrow \rightarrow Y$为平凡多值依赖。

非平凡多值依赖：若$X \rightarrow \rightarrow Y$，而$Z\neq\empty$，则称$X\rightarrow \rightarrow Y$为非平凡多值依赖。

多值依赖的性质

（1）多值依赖具有对称性

若X→→Y，则X→→Z，其中Z＝U－X－Y

（2）多值依赖具有传递性

若X→→Y，Y→→Z，则X→→Z –Y

（3）函数依赖是多值依赖的特殊情况。

若X→Y，则X→→Y。

（4）若X→→Y，X→→Z，则X→→YU Z。

（5）若X→→Y，X→→Z，则X→→Y∩Z。

（6）若X→→Y，X→→Z，则X→→Y-Z，X→→Z -Y。

多值依赖和函数依赖的对比

1）若函数依赖X→Y在R（U）上成立，则对于任何Y’ 属于Y均有X→Y’ 成立

2）多值依赖X→→Y若在R(U)上成立，不能断言对于任何Y’ 属于Y有X→→Y’ 成立，因为多值依赖中，其实就是一对一组，一个老师可能交多门课，所以不同老师可能有教相同的课，所以不能推出X→→Y’ 成立。我们可以看出，如果把一组改为一个，实际上就是函数依赖，所以所函数依赖是多值依赖的特例，多值依赖不一定是函数依赖，但函数依赖一定是多值依赖。

4NF

关系模式$R<U,F>\in 1NF$，如果对于R的每个非平凡多值依赖$X\rightarrow \rightarrow Y(Y \nsubseteq X)$，X都含有码，则$R<U,F>\in 4NF$。

1）不允许有非平凡且非函数依赖的多值依赖

2）允许的非平凡多值依赖是函数依赖

3）平凡的多值依赖属于第四范式

关系规范化小结

ArmStrong公理系统

逻辑蕴涵和闭包

函数依赖:

属性集 α 决定属性集 β ,则称有函数依赖 α→β

逻辑蕴含:

F能推出原不直观存在于函数依赖集F 中的函数依赖 α → β,则成α→β被函数依赖集F逻辑蕴含

函数依赖的闭包 F^+^:

由关系模式R直观得到的函数依赖F所推出的所有隐含的或未隐含的(直观的)函数依赖的集合
举例:

F中有α–>β,β–>ω
则函数闭包F^+^中存在α–>ω

若F=F^+^，则称F是函数依赖的完备集

理论上，如果能求出F的闭包，就能求出R的所有码

Armstrong公理系统

设关系模式R<U,F>，其中U为属性集，F是U上的一组函数依赖，Y,X,Z⊆U那么有如下推理规则：

自反律(叫大推小更确切):
$若Y⊆X⊆U，则X→Y$
增广律(加了也不影响)
$若X->Y,则XZ–>YZ$
传递律(一传十十传百)
$X->Y,Y->Z,则X->Z$

Armstrong公理的推论

合并规则（合并右边）：
$X->Y,X->Y,则X->YZ$
分解规则（分解右边）：
$X->YZ,则X->Y,X->Z$
伪传递规则（左边加一点）：
$X->Y,YW->Z则XW->Z$

引理：$X→A_1A_2…A_k成立的充分必要条件是X→A_i成立(i=1,2,…,k)。$

Armstrong公理系统的证明

1、自反律：若Y,X⊆U，则X→Y为F所蕴含
证明:

设Y⊆X⊆U。
对R<U,F>的任一关系r中的任意两个元组t,s：
若t[X]=s[X]，由于Y X，则有t[Y]=s[Y]，所以X→Y成立，自反律得证。

2、增广律：若X→Y为F所蕴含，且Z U，则XZ→YZ为F所蕴含
证明:

设X→Y为F所蕴含，且Z⊆U。
对R<U,F>的任一关系r中的任意两个元组t,s：
若t[XZ]=s[XZ]，由于X ⊆XZ，Z⊆ XZ，根据自反律，则有t[X]=s[X]和t[Z]=s[Z]；
由于X→Y，于是t[Y]=s[Y]，所以t[YZ]=s[YZ]；所以XZ→YZ成立，增广律得证。

3、传递律：若X→Y，Y→Z为F所蕴含，则X→Z为F所蕴含
证明：

设X→Y及Y→Z为F所蕴含。
对R<U,F>的任一关系r中的任意两个元组t,s：
若t[X]=s[X]，由于X→Y，有t[Y]=s[Y]；
再由于Y→Z，有t[Z]=s[Z]，所以X→Z为F所蕴含，传递律得证。

4、合并规则：若X→Y，X→Z，则X→YZ为F所蕴含
证明：

因X→Y ，所以X→XY （增广律 XX→XY即X→XY）
因X→Z ，所以XY→YZ （增广律）
因X→XY，XY→YZ
故X→YZ （传递律）

5、伪传递规则：若X→Y，WY→Z，则XW→Z为F所蕴含

证明：

因X→Y ，所以WX→WY （增广律）
因WY→Z ，所以XW→Z （传递律）

6、分解规则：若X→Y，Z∈Y，则X→Z为F所蕴含

证明：

因Z∈Y 　所以Y→Z （自反律）
因X→Y 所以X→Z （传递律）

属性闭包

在关系模式R所对应的F^+^中,有α→β ,则所有β组成的集合αF^+^ 叫做属性集α关于F的属性闭包

属性闭包算法:

result=A //此处A是一个属性集,result就是要计算的属性闭包
for each α-->β in F:
    if α in result:   //α已经在属性闭包里了,即A-->α是成立的
    result=result+β   //增加属性闭包

正则覆盖 F^+^

将原函数依赖集F中的函数依赖α–>β中的部分(α或β属性中)冗余属性删除。F^+^ 和 F 的函数依赖的闭包是相同的

属性是否冗余判断条件,对于α–>β函数依赖(哪边冗余F在哪边)

1、α属性集中有属性A是冗余的,$(α−A)→β$成立:
F 逻辑蕴含 $(F−(α→β))∪((α−A)→β)$

2、β属性集中有属性b是冗余的,$α→(β−b)$成立
$(F−(α→β))∪(α→(β−b))$ 逻辑蕴含 F

无损分解

将关系模式R分解成关系模式R1和R2,则:

$R_1∩R_2→R_1或R_2$ ;即$R_1$和$R_2$的交集是R1或R2的super key

最小函数依赖集

函数依赖集的等价

定义：设F和G是关系模式R的两个函数依赖集，如果F^+^=G^+^,则称F和G等价。也称F是G的覆盖，或G是F的覆盖。

定理：设F和G是R的两个函数依赖集，则F和G等价的充要条件是F⊆G^+^且G⊆F^+^.

问题：给定两个函数依赖集G和F，判断F和G是否等价？

方法：

1、对于F中的每个函数依赖X->Y,求XG^+^，若都有Y⊆XG^+^，则说明F⊆XG^+^

2、对于G中的每个函数依赖X->Y,求XF^+^，若都有Y⊆XF^+^，则说明G⊆XF^+^

最小函数依赖集（最小覆盖）

1、定义：

如果函数依赖集F满足以下条件，则称F为一个极小函数依赖集。也称为最小依赖集或最小覆盖。

(1)F中任一函数依赖的右部仅含有一个属性（右部都是单属性）。

(2)F中不存在这样的函数依赖X→A，使得F与F-{X→A}等价（没有多余的依赖）。

(3)F中不存在这样的函数依赖X→A，X有真子集Z使得(F-{X→A})U{Z→A}与F等价（左部不存在多余属性）。

最小依赖集通用算法

① 用分解的法则，使F中的任何一个函数依赖的右部仅含有一个属性；

② 去掉多余的函数依赖：从第一个函数依赖X→Y开始将其从F中去掉，然后在剩下的函数依赖中求X的闭包X+，看X+是否包含Y，若是，则去掉X→Y；否则不能去掉，依次做下去。直到找不到冗余的函数依赖；

③ 去掉各依赖左部多余的属性。一个一个地检查函数依赖左部非单个属性的依赖。例如XY→A，若要判Y为多余的，则以X→A代替XY→A是否等价？若A属于(X)+，则Y是多余属性，可以去掉。（以上步骤中，求出关系依赖集F,此时，再F的基础上，求出X或者Y的闭包，是否包含A）

反复执行步骤2、3，直至F不再变化

注意：最小函数依赖集不是唯一的。

模式分解概述

参考文章

当模式不符合关系范式时，需要进行模式分解。

模式分解

函数依赖的投影

投影的计算方法

分解正确性检验

无损连接性

分解所得到的各个关系模式，经过自然连接可以还原成被分解的关系模式。

算法

参考文章

参考

对于一个分解，有k个子集，n个属性，建立一张k行n列的初始表，对于每一行也就是分解的每个子集，把该分解子集出现的属性对应的列写上aj，否则写上bij
对于每一个依赖，找到左部属性对应的列，根据行的值分组，对于行的值相同的这些行，查看对应右部属性的列，如果这些格子里有a值，那把所有这些格子改成a值，如果没有，改成行最小的b值。如果某个b值改成a值，那么其他行(不属于当前操作的行)的相同b值也要改成a值。
如果不变则停止，如果出现有一行为a1 a2 … an，那么说明该连接为无损连接。

依赖保持性

分解所得到的各个关系模式上的函数依赖集的并集，与被分解关系模式原有的函数依赖集等价。

模式分解算法

正确性

无损连接法：可保证分解达到BCNF
无损连接法+依赖保持法：可保证分解达到3NF
依赖保持性：可保证分解达到3NF

3NF和保持函数依赖的分解

算法

F=F的最小依赖集
U0={不在F出现的属性}
U=U-U0
若F中有函数依赖X->A，使得XA=U，那么分解就是R本身
如果没有，将剩下的F按左部分组，得到Ui，分解就是{R1<U1,F1>，…} ∪ R0<U0,F0>

3NF和保持函数依赖和具有无损连接性的分解

算法

求出3NF和保持函数依赖的分解。
X是R的码，让已有的分解∪上一个{R^∗^<X,FX>}。
如果分解中有某个Ui属于X，那么删掉该Ui，如果X属于某个Ui，那么删掉。

BCNF和具有无损连接性的分解

算法

类似递归的方法，首先判断自身是不是BC范式，如果是，无需分解。
否则，找到当前关系R的主码，找到一个左边不含主码的依赖X->A，设U1=A，分解出去，**剩下的U2=U-{A}**作为一个关系模式，继续重复上面的步骤。
根据X->A的选择的不同，得到的分解也是不同。

4NF和具有无损连接性的分解

算法

求出BCNF和具有无损连接性的分解。
对于一个关系R<U,F>，如果多值依赖X–>Y成立，则分解{R1<X,Y>,R2<X,Z>)}具有无损连接性，其中Z=U-X-Y。

数据库_数据库恢复技术

发表于 2020-06-03 更新于 2022-11-13 分类于学习笔记，数据库

事务的基本概念

参考文章

事务（trancaction）：用户定义的一个数据库操作序列，该序列构成一个独立的、不可分割的逻辑处理任务。要么全做，要么全不做。

一个数据库事务通常包含对数据库进行读或写的一个操作序列。它的存在包含有以下两个目的：

1、为数据库操作提供了一个从失败中恢复到正常状态的方法，同时提供了数据库即使在异常状态下仍能保持一致性的方法。
2、当多个应用程序在并发访问数据库时，可以在这些应用程序之间提供一个隔离方法，以防止彼此的操作互相干扰。

事务的组成

1、一条SQL语句

2、一组SQL语句序列

事务的描述方式

显式

BEGIN TRANSACTION
	update...
	insert...
COMMIT 或者ROLLBACK

其中：

COMMIT：提交。事务对数据库的所有修改操作写回到磁盘上的数据库文件中。

ROLLBACK：回滚。撤销所有已实施的对数据库的修改，数据库回滚到事务开始状态。

隐式

一条SQL语句，例如execDirect（）。

程序隐式定义，例如会话结束、程序对象关闭时其中隐藏的COMMIT/ROLLBACK。

事务的ACID性质

并非任意的对数据库的操作序列都是数据库事务。事务应该具有4个属性：原子性、一致性、隔离性、持久性。这四个属性通常称为ACID特性。

原子性（Atomicity）

定义：事务作为一个整体被执行，包含在其中的对数据库的操作要么全部被执行，要么都不执行。

目标：保证数据库中数据的正确性

技术：

日志+COMMIT/ROLLBACK（UNDO）；
并发控制（交叉执行）。

一致性（Consistency）

定义：事务应确保数据库（DB）的状态从一个一致（正确）状态转变为另一个一致状态。一致状态的含义是数据库中的数据应满足完整性约束。

目标：保证数据库中数据的正确性（有效、相容，防止对数据的更新结果被丢失、读到无效的数据、读到不一致的数据）。

技术：

并发控制（保护临界资源）

隔离性（Isolation）

定义：多个事务并发执行时，一个事务的执行不应影响其他事务的执行。

目标：防止事务之间由于相互干扰而出现并发错误、链式夭折。

技术

并发控制

原子性与隔离行

一致性与原子性是密切相关的,原子性的破坏可能导致数据库的不一致，数据的一致性问题并不都和原子性有关。
比如刚刚的例子，在第五步的时候，对B账户做加法时只加了50元。那么该过程可以符合原子性，但是数据的一致性就出现了问题。

因此，事务的原子性与一致性缺一不可。

持久性（Durability）

定义：一个事务一旦提交，他对数据库的修改应该永久保存在数据库中。

目标：保证数据库的可靠性

技术：

（事务终止前应完成commit）

提交的持久化（内存是挥发性存储装置，外存是非挥发性存储装置）。
备份+日志。（外存）

数据库系统故障分类

数据库系统故障种类

事务故障
系统故障
介质故障
计算机病毒

事务故障

1、表现形式：

应用处理异常
- 可能产生自程序预留的异常情况的应对方案。
- 可能来自于非预期的、不能由应用程序处理的故障
  - 断网
  - 应用程序进程僵死
  - 应用程序进行被意外杀死
  - 应用程序端电脑死机、断电
系统异常
- 事务超时、死锁、活锁等【为避免过久占用资源、DBMS系统按照事先设定的系统参数强行终止事务。】

2、特征：

特定的事务没有到达预期的终点（COMMIT），事务夭折；
夭折事务对数据库的部分修改可能已写入数据文件。
（数据库可能因此处于不正确、不一致状态）

系统故障

1、表现形式

某些类型的硬件故障
- CPU、内存、主板。。。
  【服务器上的硬件，其故障影响到DBMS系统的正常运行，但不涉及外存储设备】
系统软件故障
- DBMS：ORACLE、SQL SERVER、MYSQL、DB2。。。
- OS：UNIX、WINDOWS、LINUX。。。
- 死机、蓝屏、意外重启、某系统功能意外退出
- 服务器上的系统软件，其故障影响到DBMS系统的正常运行，但不涉及外存储设备。
系统操作失误
- 非正常关机\重启、强行终止系统进程、意外卸载相关系统运行环境。。。
系统异常断电
- 重启之后系统未发现数据库的存储文件错误或者磁盘错误。

2、特征

内存数据丢失或不再可靠
外存数据未受到破坏
一些尚未完成事务的更新结果可能已写入数据库存储介质
已完成事务的更新结果可能部分还未写入数据库（数据文件，也可能正处于提交过程中）
已完成事务的结果可能全部未写入数据库（例如正在等待检查点）
数据库的数据存储介质依旧可靠，但是数据处于不正确或不一致状态

介质故障

1、表现形式

磁盘故障
- 磁盘损坏（磁道、扇区、分区、文件分配信息）
- 磁盘读写装置损坏（磁头、电机）
外界干扰
- 强磁场干扰（磁性数据被清洗），灾害

2、特征

硬故障，外存中数据的部分或全部丢失，数据相关存储文件本身异常。
（目前比较成熟的DBMS软件一般能够在服务启动时校验存储介质上的数据文件是否异常）

计算机病毒

1、表现形式

消耗资源
- 内存、磁盘、网络端口，破坏系统的正常运行
泄露信息
- 系统信息、数据库信息
篡改数据
篡改程序
- 植入木马、埋下隐患

2、特征

计算机病毒是一种人为造成的技术故障或破坏，含有非法或者恶意企图，在执行某个功能时启动病毒代码，可能造成对数据库系统的危害

系统不再可靠、可信

各类故障对数据库的影响

数据本身被破坏

需要去寻找可用的数据，重建数据库状态
数据可能不正确（事务的运行被恶意干扰或非正常终止）
需要截至系统的容错机制，恢复数据的正确性

不同的故障影响的范围不同，采取的恢复策略也不同
自动、人工启动、借助外部资源

恢复的基本原理：冗余

数据库备份和日志

数据转储

一般由数据库管理员制定计划，定期的将数据库内容复制到磁带、磁盘或者其他存储介质上保存起来，成为后备副本或后援副本。

转储需要考虑的问题：耗费时间和资源，不宜频繁进行。

转储状态

静态转储

数据库系统中无事务运行时进行转储。

①特征：转储期间不对数据库进行任何联机事务操作。一定得到一个数据一致性付本。

②优点——简单

③ 缺点：停止一切事务运行；降低数据库的可用性

动态转储

转储与事务同时（并发）执行。

①特征：转储期间可对数据库进行读写操作。

②优点：不用等待正在运行的事务结束，也不影响新事务的运行。

③缺点：获得一致性副本比较麻烦。
解决思路：把转储期间各事务对数据库的修改活动登记下来——日志文件

转储方式

海量备份

① 方法：将数据库的全部数据转储。

② 优点：简单——备份简单，恢复简单

③ 缺点：重复执行全部数据的转储动作
转储量大；
停止运行（多为静态转储）。

增量备份

① 方法：每次转储上次转储后更新过的数据。

② 优点：备份量小。

③ 缺点：恢复过程相对复杂。

登记日志文件

在数据库系统中，数据文件也是一种设备，里面的数据是资源，也有类似的需求，相应的有日志文件及其维护机制。

日志——数据库恢复子系统“自己的数据”。

日志文件及其类型

日志文件的概念

记录事务对数据库的更新操作的文件称之为日志文件。

日志文件类型

①记录为单位的日志文件

②数据块为单位的日志文件

以记录为单位的日志文件内容

①事务开始标记（一个日志记录，Begin Transaction）；

②事务结束标记（一个日志记录，Commit，或者Rollback）；

③每个事务的所有更新操作（每个操作一个日志记录）。

每个日志记录内容：

1）事务标识（TRID）；
2）操作类型；
3）操作对象；
4）更新前数据旧值；
5）更新后数据新值。

以数据块为单位的日志文件内容

事务标识+数据块

①数据块（整块）更新前内容；

②数据块更新后内容。

日志文件的作用

1）事务恢复
2）数据库故障恢复
3）系统分析

日志文件的登记

为保证数据库的恢复能正确进行，日志文件的登记必须遵循两条原则：
1）按事务操作执行时间顺序登记日志（多个事务操作并发）
如实记录数据库的状态变化过程，从而保障恢复时能按照逻辑顺序定位到相应的状态。

2）须先写日志文件，后写数据库文件！！！！！
（先写日志协议——WAL）

日志包含了状态变化过程的与事务相关的完整信息，数据块则未必。因此，恢复的依据必须首先是日志。若先写数据文件之后日志文件因故障未能写出，则无法判断相关数据块在恢复时应该采取的动作。

故障恢复策略

事务故障恢复：UNDO

系统故障恢复：REDO+UNDO

介质故障恢复：装入后备副本+REDO

恢复的背景需求

1）文件管理系统和数据库管理系统都有备份与恢复技术

文件管理系统
Ghost、副本文件、操作系统补丁更新时的备份、平台提供的备份软件（例如：手机和电脑数据云备份）

数据库管理系统
转储备份+日志、镜像、逻辑备份（数据导出）

2）恢复的需求存在差异

文件管理系统
恢复到某个版本或某个时间点、恢复某个文件集合【数据的正确性一般由应用程序或人工判断】

数据库管理系统
以数据库为单位，恢复到某个时刻的数据库正确状态【数据的正确性由DBMS判断】

3）数据库恢复的任务

将因破坏或故障而导致的数据库数据的错误状态恢复到最近一个正确状态。

4）目标

①保持事务原子性（Atomicity）
②保持事务持久性（Durability）

5）恢复的数据基础

当前可用的数据文件——当前可看到的正确以及错误的数据
转储的数据文件——转储时可以看到的正确以及错误的数据
日志——用于分析可看到的数据的错误以及看不到的正确数据

事务故障的恢复【事务在运行至正常终点前被终止】

——因各种异常或错误导致事务未执行完而夭折时的恢复。

此时，数据库管理系统正常运行，数据文件和日志文件均未损坏；可能存在其他并发执行的事务，这些事务不受影响。

1）目标：维护原子性

2）动作特征：执行已有操作的“逆向”操作，称为撤销，或者undo。

3）恢复步骤

① 反向扫描日志文件（从日志文件尾向文件头）：
——查找事务执行过最后一条更新操作记录；

② 执行上述找到的最后一条日志记录的UNDO操作【插入→删除，删除→插入，修改前的值→修改后】；

③ 循环执行上述扫描及undo操作，直至事务开始标记。

4）执行方式DBMS自动完成

系统故障的恢复【系统终止造成数据库不一致状态】

——撤消故障发生时未完成事务和重做已完成事务的恢复。

此时，数据文件和日志文件均未损坏，但数据库管理系统出现异常，可能存在多个并发执行的事务，一些已提交事务的日志已写到日志文件，但最新数据却有可能遗留在数据缓冲区。

1）目标：原子性、持久性

2）动作特征：未完成事务已有操作需落实其逆向操作，称为撤销，或者undo；已完成事务需落实其全部操作动作，确保其原子性、持久性，称为“重做”，或者redo。

3）步骤

①正向扫描日志文件（从日志文件头向文件尾）：

找出故障发生前已提交事务，该事务标识记入REDO队列；
【有BEGIN TRANSANCTION和COMMIT的加入REDO队列】
找出故障发生时未完成事务，该事务标识记入UNDO队列；
【只有BEGIN TRANSANCTION没有COMMIT的加入UNDO队列】

②执行undo和redo操作

依照日志记录反向顺序对UNDO队列中事务进行UNDO操作（写入修改前的值）：
（反向扫描日志文件，执行队列中事务的undo操作）；
依照日志记录正向顺序对REDO队列中事务进行REDO操作（写入修改后的值）：
（正向扫描日志文件，执行队列中事务的redo操作）。

4）执行方式：一般是DBMS重启后自动完成。

介质故障的恢复【需要DBA介入】

——数据库文件和日志文件被破环时的恢复。

数据库管理系统发现数据文件或日志文件读写异常，系统无法正常运行，并且依靠重启也无法恢复到正确状态。

此时，需要以往转储的后备副本数据，以及相应的日志文件（包括归档日志文件和联机日志文件）。
如果联机日志文件损坏，则有可能丢失数据。

1）目标：原子性、持久性

2）动作特征：寻找、装载副本；未完成事务已有操作需落实其逆向操作，undo；已完成事务需落实其全部动作，确保其持久化，redo。

3）恢复步骤

①装入后备数据副本（一般选择最新的转储副本）

②运用与后备数据副本配套的归档日志
采用系统故障的恢复方法，通过归档日志中的事务的redo和undo操作，将数据恢复到和转储副本配套的数据库正确状态。

③运用后期的归档日志和联机日志副本
依次装入日志文件，正向扫描日志，直至日志文件尾，建立UNDO和REDO队列，按照系统故障的恢复动作，执行两个队列的redo和undo操作。

4）执行方式：人工介入、通过恢复子系统完成。

检查点技术

产生原因

利用日志恢复系统故障的过程需要扫描全部的日志记录，进行相关的恢复操作，因而较大的日志文件将带来大量的日志扫描和恢复操作。

Undo——为了确保夭折事务的更新影响不生效，逻辑上可看作一种撤销操作。

DBMS缓存中的数据会因为内外存交换机制写出到磁盘，不一致的数据必须物理上更新回正确状态，undo恢复是唯一能够执行此类撤销操作的系统机制。

Redo——为了确保已提交事务的更新的持久性。

事务提交时它所更新的数据可能仍在缓存中，缓存数据不具备持久化状态，此时，日志的redo功能可以看做其持久性的保障，所以需要先写日志协议。

如果数据存在不违背先写日志的前提下，及时的被写出到磁盘文件，结果会怎样？

许多需要redo的事务的数据更新结果（后像数据）已被写入磁盘文件中，对其redo只是重复的将数据再次设置为后像的值，没有必要。

可以将这一思想用于恢复的优化

优化机制——定期的在不违背先写日志的前提下，将缓存中的数据写出到磁盘文件——检查点（checkpoint）。【周期性、先写日志、缓存写出、记录优化完成】

优化了redo任务，undo的相关开销是否减少？

检查点机制

生成检查点的时机——周期性

①时间周期；

②日志记录周期（日志文件写满或者到达一定数量）。

两个“增加”：

（1）在日志中增加一类记录（检查点记录）

检查点记录内容：

① 建立检查点时刻所有正在执行的（active）事务清单；

②上述事务的最早一条日志记录的地址。

（2）增设重新开始文件。
用来记录各个检查点记录在日志文件中的地址。

检查点动作

——保存数据库状态，建立检查点。

1）将当前日志缓冲区中的所有日志记录写入磁盘的日志文件；

2）在日志文件中写入一个检查点记录；

3）把当前数据缓冲区的所有数据写入磁盘数据文件；

4）在重新开始文件中记录检查点记录的地址。

使用检查点的恢复技术

恢复子系统可以定期或不定期地建立检查点,保存数据库状态

定期：按照预定的一个时间间隔，如每隔一小时建立一个检查点
不定期：按照某种规则，如日志文件已写满一半建立一个检查点

T1：在检查点之前提交

T2：在检查点之前开始执行，在检查点之后故障点之前提交

T3：在检查点之前开始执行，在故障点时还未完成

T4：在检查点之后开始执行，在故障点之前提交

T5：在检查点之后开始执行，在故障点时还未完成

采用检查点的恢复步骤

1）从重新开始文件中找到最后一个检查点记录在日志文件中的地址，由该地址在日志文件中找到最后一个检查点记录；

2）由该检查点记录得到检查点建立时刻所有正在执行的事务清单ACTIVE-LIST

建立两个事务队列
- UNDO-LIST
- REDO-LIST
把ACTIVE-LIST暂时放入UNDO-LIST队列，REDO队列暂为空。

3）从检查点开始正向扫描日志文件，直到日志文件结束

如有新开始的事务Ti，把Ti暂时放入UNDO-LIST队列
如有提交的事务Tj，把Tj从UNDO-LIST队列移到REDO-LIST队列

4）以检查点记载的最早日志记录和日志文件末尾为界

对UNDO-LIST中的每个事务执行UNDO操作
对REDO-LIST中的每个事务执行REDO操作

问题回答

1、为什么需要检查点？

搜索整个日志文件需要耗费的时间很多
重做处理，重新执行，耗费了大量的时间

2、解决方案是什么？

在日志文件中增加检查点（check point）记录
增加重新开始文件
恢复子系统在登录日志文件期间动态的维护日志

3、检查点记录的内容有哪些？

建立检查点时刻，所有正在执行的事务清单
这些事务最近一个日志记录的地址

4、重新开始文件的内容有哪些？

记录各个检查点记录在日志文件中的地址

结论

事务是数据库的逻辑工作单位

DBMS保证系统中一切事务的原子性、一致性、隔离性和持续性

DBMS必须对事务故障、系统故障和介质故障进行恢复
恢复中最经常使用的技术：数据库转储和登记日志文件
恢复的基本原理：利用存储在后备副本、日志文件和数据库镜像中的冗余数据来重建数据库
常用恢复技术
事务故障的恢复（UNDO）
系统故障的恢复（UNDO + REDO）
介质故障的恢复（重装备份并恢复到一致性状态 + REDO）
提高恢复效率的技术
检查点技术（
Ø可以提高系统故障的恢复效率
Ø可以在一定程度上提高利用动态转储备份进行介质故障恢复的效率
）

编译原理-代码优化和目标代码生成

发表于 2020-04-30 更新于 2022-11-13 分类于学习笔记，编译原理

优化技术介绍

代码优化，是指对中间代码或目标代码进行等价变换，使得变换后的代码运行速度加快和存储空间减少。

代码优化按照优化的代码块尺度分为：局部优化、循环优化和全局优化。即

局部优化：只有一个控制流入口、一个控制流出口的基本程序块上进行的优化；
循环优化：对循环中的代码进行的优化；
全局优化：在整个程序范围内进行的优化。

常见的代码优化手段

常见的代码优化技术有：删除多余运算、合并已知量和复写传播，删除无用赋值等。

针对目标代码：

1
2
3

P := 0
for I := 1 to 20 do 
    P := P + A[I]*B[I]

假设其翻译所得的中间代码如下

删除多余运算
分析上图的中间代码，可以发现(3)和式(6)属于重复计算（因为I并没有发生变化），故而式(6)是多余的，完全可以采用T4∶=T1代替。
代码外提
减少循环中代码总数的一个重要办法是循环中不变的代码段外提。这种变换把循环不变运算，即结果独立于循环执行次数的表达式，提到循环的前面,使之只在循环外计算一次。针对改定的例子，显然数组A和 B的首地址在计算过程中并不改变，则作出的改动如下

强度削弱
强度削弱的本质是把强度大的运算换算成强度小的运算，例如将乘法换成加法运算。针对上面的循环过程，每循环一次，I的值增加1，T1的值与I保持线性关系，每次总是增加4。因此，可以把循环中计算T1值的乘法运算变换成在循环前进行一次乘法运算，而在循环中将其变换成加法运算。

变换循环控制条件
I和T1始终保持T1＝4*I的线性关系，因此可以把四元式（12）的循环控制条件I≤20变换成T1≤80，这样整个程序的运行结果不变。这种变换称为变换循环控制条件。经过这一变换后，循环中I的值在循环后不会被引用，四元式（11）成为多余运算，可以从循环中删除。变换循环控制条件可以达到代码优化的目的。
合并已知量和复写传播
四元式（3）计算4 * I时，I必为1。即4*I的两个运算对象都是编码时的已知量，可在编译时计算出它的值，即四元式（3）可变为T1＝4，这种变换称为合并已知量。

四元式(6)把T1的值复写到T4中，四元式（8）要引用T4的值，而从四元式（6）到四元式（8）之间未改变T4和T1的值，则将四元式（8）改为T6∶=T5[T1]，这种变换称为复写传播。

删除无用赋值
式（6）对T4赋值，但T4未被引用；另外，（2）和（11）对I赋值，但只有（11）引用I。所以，只要程序中其它地方不需要引用T4和I，则（6），（2）和（11）对程序的运行结果无任何作用。我们称之为无用赋值，无用赋值可以从程序中删除。至此，我们可以得到删减后简洁的代码

基本块内的局部优化

基本块的划分

入口语句的定义如下：
　　① 程序的第一个语句；或者，
　　② 条件转移语句或无条件转移语句的转移目标语句；
　　③ 紧跟在条件转移语句后面的语句。
有了入口语句的概念之后，就可以给出划分中间代码（四元式程序）为基本块的算法，
　　其步骤如下：
　　① 求出四元式程序中各个基本块的入口语句。
　　② 对每一入口语句，构造其所属的基本块。它是由该入口语句到下一入口语句（不包括下一入口语句），或到一转移语句（包括该转移语句），或到一停语句（包括该停语句）之间的语句序列组成的。
　 ③ 凡未被纳入某一基本块的语句、都是程序中控制流程无法到达的语句，因而也是不会被执行到的语句，可以把它们删除。

基本块的优化手段

由于基本块内的逻辑清晰，故而要做的优化手段都是较为直接浅层次的。目前基本块内的常见的块内优化手段有：

删除公共子表达式
删除无用代码
重新命名临时变量（一般是用来应对创建过多临时变量的，如t2 := t1 + 3如果后续并没有对t1的引用，则可以t1 := t1 + 3来节省一个临时变量的创建）
交换语句顺序
在结果不变的前提下，更换代数操作（如$x∶=y2$是需要根据 $$运算符重载指数函数的，这是挺耗时的操作，故而可以用强度更低的$x∶=y*y$来代替）

根据以上原则，对如下代码进行优化

t1 := 4 - 2
t2 := t1 / 2 
t3 := a * t2
t4 := t3 * t1
t5 := b + t4
 c := t5 * t5

给出优化的终版代码

1
2
3

t1 := a + a
t1 := b + t1
 c := t1 * t1

显然代码优化的工作不能像上面那样的人工一步步确认和遍历，显然必然要将这些优化工作公理化。而一般到涉及到数据流和控制流简化的这种阶段，都是到了图论一展身手的时候。

DAG（无环路有向图）应用于基本块的优化工作

利用DAG进行基本块优化的基本思想是：按照构造DAG结点的顺序，对每一个结点写出其相应的三地址代码表示

在DAG图中，通过节点间的连线和层次关系来表示表示式或运算的归属关系：
① 图的叶结点，即无后继的结点，以一标识符（变量名）或常数作为标记，表示这个结点代表该变量或常数的值。如果叶结点用来代表某变量A的地址，则用addr（A）作为这个结点的标记。
② 图的内部结点，即有后继的结点,以一运算符作为标记，表示这个结点代表应用该运算符对其后继结点所代表的值进行运算的结果。
（注：该部分内容转载自教材《编译原理》第11章DAG无环路有向图应用于代码优化）

DAG构建的流程如下

对基本块的每一四元式，依次执行：
　　1．

如果NODE（B）无定义，则构造一标记为B的叶结点并定义NODE（B）为这个结点；
　　如果当前四元式是0型，则记NODE（B）的值为n，转4。
　　如果当前四元式是1型，则转2.（1）。
　　如果当前四元式是2型，则：（Ⅰ）如果NODE（C）无定义，则构造一标记为C的叶结点并定义NODE（C）为这个结点，（Ⅱ）转2.（2）。
　　2．
　　（1）如果NODE（B）是标记为常数的叶结点，则转2.（3），否则转3.（1）。
　　（2）如果NODE（B）和NODE（C）都是标记为常数的叶结点，则转2.（4），否则转3.（2）。
　　（3）执行op　B（即合并已知量），令得到的新常数为P。如果NODE（B）是处理当前四元式时新构造出来的结点，则删除它。如果NODE（P）无定义，则构造一用P做标记的叶结点n。置NODE（P）＝n，转4.。
　　（4）执行B　op　C(即合并已知量)，令得到的新常数为P。如果NODE（B）或NODE（C）是处理当前四元式时新构造出来的结点，则删除它。如果NODE（P）无定义，则构造一用P做标记的叶结点n。置NODE（P）＝n，转4.。
　　3．
　　（1）检查DAG中是否已有一结点，其唯一后继为NODE（B），且标记为op（即找公共子表达式）。如果没有，则构造该结点n，否则就把已有的结点作为它的结点并设该结点为n，转4.。
　　（2）检查DAG中是否已有一结点，其左后继为NODE（B），右后继为NODE（C），且标记为op(即找公共子表达式)。如果没有，则构造该结点n，否则就把已有的结点作为它的结点并设该结点为n。转4.。
　　4．
　　如果NODE（A）无定义，则把A附加在结点n上并令NODE（A）＝n；否则先把A从NODE（A）结点上的附加标识符集中删除（注意，如果NODE（A）是叶结点，则其标记A不删除），把A附加到新结点n上并令NODE（A）＝n。转处理下一四元式。

说着很复杂，下面看一个案例

(1) T0∶=3.14
(2) T1∶=2 * T0
(3) T2∶=R + r
(4) A∶=T1 * T2
(5) B∶=A
(6) T3∶=2 * T0
(7) T4∶=R + r
(8) T5∶=T3 * T4
(9) T6∶=R - r
(10) B∶=T5 * T6

其DAG图的构建过程如下

通过DAG图可以发现诸多的优化信息，如重复定义、无用定义等，则根据上图的DAG图可以构建最后的优化代码序列

　　(1) S1∶=R+r
　　(2) A∶=6.28*S1
　　(3) S2∶=R-r
　　(4) B∶=A *S2

循环优化

循环优化的主要手段有：循环次数无关性代码外提、删除归纳变量和运算强度削弱。关于这三种手段的理解可以借助此前的描述进行类比，基本并无太多差异。

流图

结点是基本块的有向图G = ( N, E, root)

N是结点的集合，每个结点表示一个基本块
E是边的集合，如果结点ni和nj间存在前驱和后继的关系，则在存在一条从ni到nj的有向边（此时意味着，在ni执行后，可能会执行nj）
- ni的出口语句是goto(s)或if … goto(s)，且(s)是的nj入口语句
- nj在程序中的位置紧跟在ni后，且ni的出口语句不是无条件转移语句和停语句
root是流图的首结点（或称为根结点），是包含程序第一个语句的基本块

每个流图都可以等价变换为单入口，且每个结点最多有两个后继的图

根据上面基本块的定义，我们将诸多基本块组装在一起，构建成程序循环图，如针对下面这个例子

　　(1) read x
　　(2) read y
　　(3) r∶=x mod y
　　(4) if r=0 goto (8)
　　(5) x∶=y
　　(6) y∶=r
　　(7) goto (3)
　　(8) write y
　　(9) halt

则按照上面基本块的划分，可以分成四个部分，四个部分的控制流分析可知可以得到一个循环图（流图）

循环块最主要的特点是只有一个数据流和控制流入口，而出口可能有多个。

循环

编译原理-运行时存储组织

发表于 2020-04-30 更新于 2022-11-13 分类于学习笔记，编译原理

运行时存储组织概述

编译程序是将源程序的算法描述部分和数据说明部分，分别翻译成机器目标代码和数据存储单元，最终获得目标程序。

目标程序在目标机环境中运行时，都置身于自己的一个运行时存储空间。在基于操作系统之上运行的情况下，目标程序将在自己的逻辑地址空间内运行并存储数据。编译程序在生成代码时，负责明确各类对象在逻辑地址空间是如何存放的，以及目标代码运行时，如何使用逻辑地址空间。

在编译过程中，源程序的对象地址分配往往是相对于运行存储空间的偏移量，对象访问采用“基地址＋偏移量”寻址方式进行，使得可以选择内存的任意可用区域作为目标程序运行时的存储区。这样生成的目标代码称为浮动地址代码

注：“基地址”是指运行存储空间之首址。

重点：符号表的内容、组织，过程调用实现，

静态存储分配、动态存储分配的基本方法。

难点：参数传递，过程说明语句代码结构，

过程调用语句的代码结构，

过程调用语句的语法制导定义，

栈式存储分配。

运行时存储组织的任务和作用

编译程序生成的代码大小通常是固定的，一般存放在专用的区域，即代码区；
目标程序运行过程中，需要创建和访问的数据对象存放在数据区。

程序运行时存储空间的布局

存储分配策略

数据空间分配是将源程序数据对象名与给定的数据存储空间地址建立映射关系。数据对象名与数据存储地址可能是一对多的关系，因为在源程序中说明的一个数据对象，在运行时可能对应不同的存储地址，如递归程序中的局部变量。

静态存储分配

静态存储管理是一种最简单的存储管理。当在编译阶段能够确定源程序中各个数据实体的存储空间大小时，就可以采用静态存储管理。一般而言，适于静态管理的语言必须满足下面的条件：

( 1 )、数组的上下界必须是常数；

( 2 )、过程调用不允许递归；

( 3 )、不允许用户动态地建立数据实体。

对于静态存储分配，数据空间仅需要有静态数据区即可。在源程序翻译时，对于所有数据对象，其分配的存储地址都是相对于静态数据区的偏移量。这个偏移量就是登记在符号表中数据对象的地址( .place)属性值。在目标程序运行时，访问数据对象的绝对地址是：

绝对地址＝静态数据区首址+偏移量。

动态存储分配

如果源语言允许递归调用、可变数组和允许运行期间自由申请与释放空间，那么其需占用的存储空间在编译阶段无法确定，这样数据对象就需要采用动态存储分配的策略。

所谓动态存储分配是指在运行期间，动态进行存储地址分配。

•基于控制栈的原理，存储空间被组织成栈，活动记录的推入和弹出分别对应于活动的开始和结束。

•与静态分配不同，在每次活动中把局部名字和新的存储单元绑定，在活动结束时，活动记录从栈中弹出，因此局部名字的存储空间也随之消失。

栈式动态存储分配

由于过程允许递归，在某一时刻一个过程A 很可能已被自己调用了若干次，但只有最近一次正处于执行状态，而其余各次则处于等待返回被中断的那次调用的状态。这样，属于每次调用相应的数据区中的内容就必须保存起来，以便于调用返回时继续使用。对于这种语言来说，其存储分配策略必须采用栈式存储管理，即引入一个运行栈，让过程的每一次执行和过程的调用记录相对应，每调用一次过程，就把该过程的相应调用记录推入栈中，过程执行结束时再把栈顶的调用记录从找中弹出。

在运行期间以子程序数据区为基本单位，在数据空间栈中进行动态地址分配。

当调用子程序时，在数据空间栈顶，给子程序分配所需的子程序数据区；

当子程序返回时，从数据空间栈顶，收回分配给子程序所占用存储区。

当子程序被递归调用时，同一个子程序可能在数据空间中同时拥有多个子程序数据区，每个数据区对应于同一个子程序的一次执行过程。

堆式动态存储分配

某些程序设计语言(如C 和PASCAL等）允许程序在运行时，为其中的一些变量动态地申请和释放所需的存储空间，并且申请和释放这两类操作可以在任何时间、以任意的顺序来进行，这就需要一种更为灵活和更加有效的动态分配策略，即堆式存储分配来完成上述工作。

堆式分配的基本思想是：为正运行的程序划出一适当大的存储区域，称之为堆（Heap) ; 每当该程序提出申请时, 就按某种分配原则在堆的自由区（可占用区）中，找出一块能满足其需求的存储空间分配给它，对于释放操作，则是将程序不再占用的存储空间归还给堆的自由区。
可能遇到的各种情况与操作系统给进程分配存储空间时遇到的极其相似，如同样会出现“碎片”现象等，其根本差异就在于分配的层次和分配对象的粒度。

活动记录

1.活动记录本质是什么？

活动记录本质上是每次为函数调用时分配的一大块内存。一个函数的活动记录只由在函数被调用时才会创建，并且当函数返回时就会被销毁。

2.活动记录是如何存在的？

活动记录被组织在栈中，栈可以是物理上的实体也可以是逻辑上的概念。在数据结构中的栈是一个逻辑上的概念，而芯片中也可以根据这个概念来设计一部分电路，这部分能够模拟栈操作的电路就是物理意义上的栈了。
主函数的活动记录位于栈底，当一个函数调用另外一个函数时，被调用函数的活动记录就会被压入栈。或当记录所在的栈满足数据结构中的栈的特性：FILO(first in last out)。这个限制使得当主调函数和被调函数中出现了同名函数时，在执行被调函数时主调函数的变量对被调函数来说是不可见的。
特别提醒：大部分计算机为活动记录栈分配内存地址都是从高到低！

3.活动记录是如何进行入栈出栈的？

由于活动记录是位于一个栈中的，所以要近栈就需要知道栈结束处的位置，当出栈时就需要知道当前活动记录之前的一个活动记录的结束点。
所以编译器和硬件都会维护两个很重要的值：栈指针，帧指针。
栈指针：始终指向战结束处（注意不是栈底！）的地址，如果有新的活动记录入栈，那里就是新活动记录的起始地址所在。
帧指针：保存着先前那个活动记录的结束处的地址，在当前函数返回后，栈指针就会指向那里。
In short,栈指针和帧指针就是用来界定活动记录的，并操作活动记录。

过程调用

编译原理-语法制导的语义计算

发表于 2020-04-30 更新于 2022-11-13 分类于学习笔记，编译原理

语法制导的语义计算

编译原理的几个核心阶段：词法分析、语法分析和语义分析，其实编译的本质便是翻译，其各个阶段便是承担不同的翻译任务，词法分析阶段的任务是将程序输入的字符串流翻译成语言认可的字符流（剔除空格和注释等部分）；语法分析便是将程序按照语言文法的规则构建成语法树；语义分析便是在语法树构建的基础上完成语言规则的语义动作（类型检查、作用域和可视性检查、一致性检查等）。

属性文法（属性翻译文法）

对于语言而言，无论变量、函数、过程在程序中都是用一个标识符来代替，但如果给定了一个标识符，我们如何确定这个标识符的意义呢？其实这便引导出属性文法的概念（其实语义分析的公式化有多种方式，比如操作语义学、公理语义学、属性文法等，其中属性文法最为直观，也是当前绝大多数编译器采用的编译方式），比如变量有int\float\double之类的区别，那显然给定一个变量标识符，必须要指明该标识符的“数据类型属性”，所以必须给所有标识符配备一系列的属性。利用标识符的这些属性，便可以用来配合此前构建的语法树进行一系列的语义动作（类型检查、可见性是否合法等）。

语义分析一般是和语法分析组合在一起执行的，语法分析完成前一步语法树分析的构建（调用某个产生式完成一步规约，形成当前的树节点），然后语义分析便接着调用相应产生式配备的语义动作或子程序，完成属性文法所要求的语义动作（比如类型转换或生成中间代码）。所以对于属性文法而言，属性的加工和使用过程便是语义处理的意义。

形式上讲，一个属性文法是一个三元组，A＝（G，V，F），一个上下文无关文法G；一个属性的有穷集V和关于属性的谓词函数的有穷集F。每个断言与文法的某产生式相联。如果对G中的某一输入串而言（句子），A中的所有断言对该输入串的语法树结点的属性全为真，则该串也是A语言中的句子。

以上下文无关文法为基础：

它为每个文法符号（终结符或者非终结符）配备若干相关的“值”（称为属性），代表与文法符号相关信息，如类型、值、代码序列、符号表内容等
对于文法的每个产生式都配备了一组属性的语义规则，对属性进行计算和传递。【凡是能够用程序实现的信息处理都可以称为语义规则】

S-属性文法

只含有综合属性的属性文法

如果一个SDD是S属性的，可以按照语法分析树节点的任何自底向上顺序来计算它的各个属性值
S-属性定义可以在自底向上的语法分析过程中实现

L-属性文法

直观含义：在一个产生式所关联的各属性之间，依赖图的边可以从左到右，但不能从右到左。【产生式右边符号的继承属性不能依赖他右边的符号的属性】
正式定义：一个SDD是L-属性定义，当且仅当它的每个属性要么是一个综合属性，要么是满足如下条件的继承属性：假设存在一个产生式$A\rightarrow{X_1X_2…X_n}$其右部符号$X_i$的继承属性仅依赖于下列属性：

A的继承属性
产生式中$X_i$左边的符号$X_1,X_2,…,X_{i-1}$的属性
$X_i$本身的属性，但$X_i$的全部属性不能在依赖图中形成环路
注：每个S-属性定义都是L-属性定义

综合属性

自下而上传递信息

语法规则：根据右部候选式中的符号的属性计算左部被定义符号的综合属性

语法树：根据子结点的属性和父结点自身的属性计算父结点的综合属性

由此可知，综合属性是自下而上传递的。

继承属性

主要是用来自上而下传递信息。

语法规则：根据右部候选式中的符号的属性和左部被定义符号的属性计算右部候选式中的符号的继承属性

语法树：根据父结点的属性和兄弟结点自身的属性计算子结点的继承属性

属性依赖

对应每个产生式A -> α都有一套与之相关联的语义规则，每条规则的形式为：
b:f(c1,c2····ck)；f是一个函数，c1,c2····ck是某些属性，b是需要计算的属性。

我们称b依赖属性c1,c2····ck：

b是A的一个综合属性并且c1,c2····ck是产生式右边符号的属性
b是产生式右边某个文法符号的一个继承属性并且c1,c2····ck是A或产生式右边任何文法符号的属性

注意：
(1)终结符只有综合属性，它由词法分析器提供
(2)非终结符既可以有综合属性也可以有继承属性，文法开始符号的所有继承属性作为属性计算前的初始值。
(3) 产生式右边符号的继承属性和产生式左边符号的综合属性都必须提供一个计算规则
(4) 产生式左边符号的继承属性和产生式右边符号的综合属性不由所给的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算

所以在对属性计算的过程即是对语义处理的过程，对于文法的每一个产生式配备一组属性的计算规则，则称为语义规则。

语义规则

语义规则也是属性文法，对上下文无关文法做的一个扩充。每个产生式应该配备的语义规则，要说明该产生式中出现的语法符号的对应的属性的计算方法，以表达这个产生式所对应的语法结构的意义。

语义规则是描述该产生式中出现的语法符号的属性之间的相互关系，是以函数计算的方式体现。

注意：
(1)语义规则可能产生副作用（如产生代码），
(2)也可能是过程，不是严格的函数（即不一定有返回值）

带注释的语法树

在语法树中：

一个结点的综合属性的值由其子结点和它本身的属性值确定
一个结点的继承属性由其父结点、其兄弟结点和其本身的某些属性确定
用继承属性来表示程序涉及语言结构中的上下文依赖关系很方便

使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值

属性计算

语义规则的计算：

产生代码
在符号表中存放信息
给出错误信息
执行任何其它动作

对输出串的翻译就是根据语义规则进行计算

在属性文法的基础上进行处理

输入串语法树->依赖图->语义规则计算次序->计算结果
这种由源程序的语法结构所驱动的处理办法就是语法制导翻译法。

基于属性文法的处理方法

依赖图

在一颗语法树中的结点的继承属性和综合属性之间的相互依赖关系可以用称作依赖图的一个有向图来描述。依赖图可以确定属性计算的先后顺序。

依赖图中为每一个属性设置一个结点，如果属性b依赖于属性c，则从属性c的结点有一条有向边连到属性b的结点。

良定义的属性文法

如果一属性文法不存在属性之间的循环依赖关系，那么该文法为良定义的。为了设计编译程序，我们只处理良定义的属性文法。

一个依赖图的任何拓扑排序都给出一个语法树中结点的语义规则计算的有效顺序。

属性的计算次序

一个有向非循环图的拓扑序是图中结点的任何顺序m1,m2, …mk,使得边必须是从序列中前面的结点指向后面的结点。也就是说，如果mimj是mi到mj的一条边，那么在序列中mi必须出现在mj之前。
一个依赖图的任何拓扑排序都给出一个语法树中结点的语义规则计算的有效顺序。这就是说，在拓扑排序中，在一个结点上，语义规则b:=f（c1,c2,…ck)中的属性c1,c2…ck在计算b以前都是可用的。

树遍历的属性计算方法

通过树遍历的方法计算属性的值

假设语法树已经建立，且树中带有开始符号的继承属性和终结符的综合属性
以某种次序遍历语法树，直至计算出所有属性
深度优先，从左到右进行遍历
基于递归

输入串->语法树->遍历语法树计算属性

一遍扫描的处理方法

与语法分析方法相关，将属性计算穿插在语法分析的过程中进行。

产生语法结构的顺序决定了属性计算的顺序。【语法制导的思想】

所谓的语法制导翻译法，直观上说就是为文法中每个产生式配上一组语义规则，并且在语法分析的同时执行这些语义规则。

在自上而下分析，一个产生式匹配输入串成功时，就执行相应的语义规则
在自下而上分析，一个产生式被归约时，就执行相应的语义规则

抽象语法树

从语法树中去掉对翻译不必要的信息，而获得更有效的源程序中间表示。
这种经变换后的语法树称之为抽象语法树（Abstract Syntax Tree）。
在抽象语法树中，操作符和关键字都不作为叶结点出现，而是把它们作为内部结点，即这些叶结点的父结点。

S-属性文法的自下而上计算

s-属性文法：只含有综合属性

在自下而上的分析器分析输入符号串的同时计算综合属性

分析栈中保存语法符号和有关的综合属性值
每当进行归约时，新的语法符号的属性值由栈中正在归约的产生式右边符号的属性值进行计算

实现

原来自下而上分析栈一般只保存状态和语法符号。

现在，我们在分析栈中增加附加域存放综合属性值。

L-属性文法的自顶向下翻译

按照深度优先遍历语法树，计算所有属性值

与LL(1)自上而下分析方法结合

深度优先建立语法树
按照语义规则计算属性

翻译模式

语义规则：给出了属性计算的定义，没有属性计算的次序等实现细节。所以，我们得通过依赖图、树遍历等方法确定属性计算的顺序。

翻译模式：给出使用语义规则进行计算的次序，把实现细节表现出来

（1）在翻译模式中，和文法符号相关的属性和语义规则用花括号括起来，插入到产生式右部的合适位置上，可被插入到产生式右部的任何合适的位置上。

（2）这是一种语法分析和语义动作交错的表示法，他表达在按深度优先遍历分析树的过程中何时执行语义动作。

（3）翻译模式给出了使用语义规则进行计算的顺序。可看成是分析过程中翻译的注释。

设计翻译模式（根据语法制导定义）

条件：语法制导定义是L-属性定义
保证语义动作不会引用还没有计算的属性值。【必须保证当某个动作引用一个属性时它必须是有定义的】

只需要综合属性的情况

为每一个语义规则建立一个包含赋值的动作，并把这个动作放在相应的产生式右边的末尾。
例如：
产生式：T->T1*F
语义规则：T.val:=T1.valxF.val
翻译模式:T->T1*F {T.val:=T1.valxF.val}

因为父节点的综合属性的值只依赖于子节点，把综合属性的值计算放在最右边，它的子节点已经扩展完毕了。我们也就得到子节点的属性值

既有综合属性又有继承属性的情况

要求：

①产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来。
②一个动作不能引用这个动作右边符号的综合属性。
③产生式左边非终结符号的综合属性只有在它所引用的所有属性都计算出来以后才能计算。计算这种属性的动作通常可放在产生式右端的未尾。

此时Pt（A1.in）是不好的，这个翻译模式不对。因为A1.in还没有出来（在最右边）

改进翻译模式：

S->{A1.in:=1}A1{A2.in:=2}A2 A->a{print(A.in)}

语义动作执行时机统一

把所有的语义动作都放在产生式的末尾

语义动作的执行时机统一
转换方法
- 加入新产生式M->ε
- 把嵌入在产生式中的每个语义动作用不同的非终结符M代替，并把这个动作放在产生式M->ε的末尾

消除翻译模式的左递归

语义动作是在相同位置上的符号被展开（匹配成功）时执行的。为了构造不带回溯的自顶向下语法分析，必须消除文法中的左递归

当消除一个翻译模式的基本文法的左递归时同时考虑属性计算

适合带综合属性的翻译模式

计算机系统结构-多处理器

发表于 2020-04-15 更新于 2022-11-13

计算机系统结构-互连网络

发表于 2020-04-15 更新于 2022-11-13 分类于学习笔记，计算机系统结构

互连网络（ICN）

互连网络是计算机部件、计算机节点或计算机系统之间的连接。

例如：CPU和CPU之间、CPU内的多核之间、CPU和内存之间、内存和内存之间、计算机节点之间、网络和网络之间。

互连网络的直接设计目标是：在最少传输延迟约束内，传输尽可能多的数据，避免成为系统的瓶颈。

高速互连网络（<100s时钟周期）

片上/系统高速互连网络是一种由网络元件按照一定的拓扑结构和控制方式构成的网络，用来实现计算机系统中部件之间的高速连接。

三大要素：网络元件、互连结构、控制方式
结点：处理器、存储模块或其它设备
在拓扑上，互连网络为输入结点到输出结点之间的一组互连或映象。
- 互连结构是静态连接拓扑
- 控制方式是基于静态拓扑结构的动态传输机制

互连网络的主要操作：

置换（N-N）
广播（1-N）
选播（1-部分）

互连网络的结构参数和指标

结构参数

网络通常是用有向边或无向边连接有限个结点的图来表示。

互连网络的主要特性参数：

网络规模N：网络中接点的个数
结点度d：与结点相连接的边数，包括入度和出度
结点距离：对于网络中任意两个结点，从一个结点出发到另一个结点终止所需要跨越的边数的最小值
网络直径D：网络中任意两结点间距离的最大值
- 网络直径应尽可能小
等分宽度b：把由N个结点构成的网络切成结点数相同（N/2）的两半，在各种切法中，沿切口边数的最小值。
- 线等分宽度：B=b X w，w为通道宽度
- 该参数反映了网络最大流量
对称性：从任何结点看到的拓扑结构都相同的网络称为对称网络。

性能指标

时延和带宽

通信时延：指从源节点到目的结点传送一条消息所需的总时间
【=软件开销+通道时延+选路时延+竞争时延】
网络时延：通道时延与选路时延的和
- 由网络硬件特征决定，与程序行为和网络传输状态无关
端口带宽
- 对于互连网络中任意一个端口来说，其端口带宽是指单位时间内从该端口传送到其他端口的最大信息量。
聚集带宽
- 网络从一半结点向另一半结点传输时，单位时间内能够传送的最大信息量

互连函数

反映了网络输入数组和输出数组之间对应的置换关系或排列关系（置换函数或排列函数）

变量x：输入函数f(x)：输出

在互连函数f的作用下，输入端x连接到输出端f(x)

互连函数采用循环表示：（x0,x1,x2,x3,···x~~j-2~~,x~~j-1~~）表示f(x0)=x1,f(x1)=x2,f(x~~j-1~~)=x0

基本的互连函数

恒等函数：实现同号输入端和输出端之间的连接
$I(X_{n-1}X_{n-2}···X_{1}X_{0})=X_{n-1}X_{n-2}···X_{1}X_{0}$
交换函数：实现二进制地址编码中第K位互反的输入端和输出端之间的连接
$E(X_{n-1}X_{n-2}···X_{k+1}X_{k}X_{k-1}···X_{1}X_{0})=X_{n-1}X_{n-2}···X_{k+1}\bar{X_{k}}X_{k-1}···X_{1}X_{0}$
- 主要用于构造立方体互连网络和各种超立方体互连网络
- 供有n=log2N种互连函数（N为结点个数）
- $$
  Cube_0(x_2x_1x_0)=x_2x_1\overline{x_0}\
  Cube_1(x_2x_1x_0)=x_2\overline{x_1}x_0\
  Cube_2(x_2x_1x_0)=\overline{x_2}x_1x_0\
  $$
均匀洗牌函数（混洗函数、置换函数,shuffle函数）：将输入端分成数目相等的两半，前一半和后一半按类似均匀混洗扑克牌的方式交叉地连接到输出端（输出端相当于混洗的结果）
$\sigma(X_{n-1}X_{n-2}···X_{1}X_{0})=X_{n-2}X_{n-3}···X_{0}X_{n-1}$
- 即把输入端的二进制编号循环左移一位
- $shuffle^{n}(j)=j$
- $shuffle_n(j)=j$
子函数和超函数
- 互连函数(s)的第k个子函数sk：把s作用输入端的二进制编号的低k位
- 互连函数(s)的第k个超函数s^k^：把s作用输入端的二进制编号的高k位
逆函数
- 对于任意一种函数f(x),如果存在g(x)，使得$f(x)\times g(x)=I(x)$。则称g(x)是f(x)的逆函数，记作$f^{-1}(x)=g(x)$
逆均匀洗牌函数：将输入端的二进制编号循环右移一位而得到所连接的输出端编号
$\sigma^{-1}(X_{n-1}X_{n-2}···X_{1}X_{0})=X_{0}X_{n-1}···X_{2}X_{1}$
碟式函数（$\beta$）：把输入端的二进制编号的最高位与最低位互换位置得到输出端的编号。
- 第k个子函数：
  $\beta_{(k)}(X_{n-1}X_{n-2}···X_{k}X_{k-1}X_{k-2}···X_{1}X_{0})=X_{n-1}X_{n-2}···X_{k}X_{0}X_{k-2}···X_{1}X_{k-1}$
- 第k个超函数：
  $\beta^{(k)}(X_{n-1}X_{n-2}···X_{n-k+1}X_{n-k}X_{n-k-1}···X_{1}X_{0})=X_{n-k}X_{n-2}···X_{n-k+1}X_{n-1}X_{n-k-1}···X_{1}X_{0}$
- 碟式变换与交换变换的多级组合是构成多级立方体网络的基础
反位序函数：将输入端二进制编号的位序颠倒过来求得相应输出端的编号
$\rho(X_{n-1}X_{n-2}···X_{1}X_{0})=X_{0}X_{1}···X_{n-2}X_{n-1}$
- 第k个子函数
  $\rho_{(k)}(X_{n-1}X_{n-2}···X_{k}X_{k-1}X_{k-2}···X_{1}X_{0})=X_{n-1}X_{n-2}···X_{k}X_{0}X_{1}···X_{k-2}X_{k-1}$
- 第k个超函数
  $\rho^{(k)}(X_{n-1}X_{n-2}···X_{n-k+1}X_{n-k}X_{n-k-1}···X_{1}X_{0})=X_{n-k}X_{n-k+1}···X_{n-2}X_{n-1}X_{n-k-1}···X_{1}X_{0}$
移数函数：将各输入端都错开一定的位置（模N）后连到输出端
PM2I函数（加减2^i^函数）
- P和M分别表示加和减，2I表示2^i^
- 一种移数函数
  $PM2_{+i}(x)=x+2^i\quad mod(N)$
  $PM2_{-i}(x)=x-2^i\quad mod(N)$
  $0\leq x\leq N-1\quad o\leq i\leq n-1\quad n=log_2N,N表示结点数$
- PM2I互连网络共有2n个互连函数

静态互连网络

各结点之间有固定的连接通路、且在运行中不能改变的网络。

1、2维互连函数

线性阵列

一种一维的线性网络，其中N个结点由N-1个链路连成一行。

端结点的度：1
其余结点的度：2
直径：N-1
等分宽度b=1

环和带弦环

环：线性阵列的两个端点连接起来。可以单向工作也可以双向工作。

对称
结点的度：2
双向环的直径：N/2
单向环的直径：N-1
环的等分宽度b=2

带弦环

增加的链路越多，结点度越高，网络直径越小

全连接网络：两两结点之间都有链路
循环移数网络：通过在环上每个结点到所有与其距离为2的整数幂的结点之间都增加一条附加链
树形和星形：
树形是二叉树
- 最大结点度：3
- 直径：2(k-1)【k层完全平衡的二叉树】
- 等分宽度b=1
星形：
- 结点度：N-1
- 直径较小：2
- 等分宽度b=[N/2]【向下取整】
胖树形
网格形和环网形
- 网格形：一个由N=n^k^个结点构成的k维网格形网络（每维n个结点）的内部结点度d=2k，网络直径D=k(n-1)
- Illiac网络：把2维网格形网络的每一列的两个端结点连接起来，再把每一行的尾结点与下一行的头结点连接起来，并把最后一行的尾结点与第一行的头结点连接起来一个规模为nxn的Illiac网格： - 所有结点的度d=4 - 网络直径D=n-1 - 等分宽度：2n
- 环网形：把2维网格形网络的每一列的两个端结点连接起来，再把每一行的两个端结点连接起来。一个nxn的环网形网 - 结点度：4 - 网络直径：2x[n/2]【向下取整】 - 等分宽度b=2n

超立方体和寻径

超立方体

一种二元n-立方体结构，由N=2^n^个结点组成；分布在n维上，每维有两个结点。

为实现一个n-立方体，只要把两个（n-1）立方体中相对应的结点用链路连接起来即可。共需要2^n-1^条链路。

n-立方体中结点的度都是n，直径也是n，等分宽度为b=N/2。

带环立方体（3-CCC）

将k-立方体的每个结点用由k个结点的环来代替，组成带环k-立方体。

网络规模：$N=k\times2^k$
网络直径：$D=2k-1+\lfloor k/2\rfloor$
等分宽度：$b=\frac{N}{2k}$

k元n-立方体网络

环形、网格、环网形、二元n-立方体（超立方体）都是k元n-立方体网络系列的拓扑同构体
在k元n-立方体网络中，参数n是立方体的维数，k是基数，即每一维上的结点个数$N=N^n$
k元n-立方体的结点可以用基数为k的n位地址A=a1a2a3a4来表示【ai表示该结点在第i维上的位置】
通常把低维k元n-立方体称为环网，而把高维k元n-立方体称为超立方体

基于静态互连网络的寻径机制

确定性寻径：通信路径完全由源结点地址和目的地址来决定，寻径路径是预先唯一确定好了的，与网络状况无关
自适应寻径：通信的通路每一次都要根据资源或者网络的情况来选择【TCP/IP网络】

二维网格网络的X-Y寻径

先沿X维方向进行寻径，然后再沿Y维方向寻找路径

超立方体E-cube寻径

动态互连网络

由交换开关构成、可按运行程序的要求动态地改变连接状态的网络。

总线和交叉开关

总线网络

由一组导线和插座构成，经常被用来实现计算机系统中处理机模块、存储模块和外围设备等之间的互连。

计算机系统结构-I/O系统

发表于 2020-04-15 更新于 2022-11-13 分类于学习笔记，计算机系统结构

IO系统的基本概念

通常包含IO设备和IO设备与处理机的连接接口两个主要部分。

系统评价

参数指标：连接特性、IO系统的容量、响应时间和吞吐率

吞吐率反映单位时间内完成的I/O数量，响应时间则反映了完成一次I/O所花费的时间

计算机系统结构-存储系统

发表于 2020-04-15 更新于 2022-11-13 分类于学习笔记，计算机系统结构

存储系统性能量化分析

存储器越靠近CPU，则CPU对它的访问频度越高，但是容量也越低，单位存储容量价格越高。

存储容量S：一般来说，整个存储系统的容量即是第二级存储器M2 ，即S=S2

命中率H：CPU访问存储系统时，在M1 中找到所需信息的概率$H=\frac{N_1}{N_1+N_2}$

平均访问时间TA ：

当命中时，访问时间即是T1 （命中时间）
当没命中时，$T_2+T_1+T_B=T_1+T_M\T_m=T_2+T_B\传递一个信息块所需的时间为T_B\不命中开销T_M:从向M_2发出访问请求到整个数据块调入M_1中所需的时间$

Cache基本知识

Cache-利用局部性原理，加快经常性事件原理，将程序和数据放到与CPU速度匹配的高速存储器中。

cache关注的四个问题：

如何放
- 全相联映象
- 直接映象
- 组相联映象
如何找
如何写
- 写穿：写cache的同时也在写内存
- 写回：只写cache，只有被替换时才写回内存
如何换
- 轮换法
- LRU算法

具体见《组原原理》

映象规则及其变换

见《组成原理》

降低cache不命中率

三种类型的不命中

强制性不命中：当第一次访问一个块时，该块不在cache中，需从下一级存储器中调入cache。（冷启动不命中，首次访问不命中。）
容量不命中：如果程序执行时所需的块不能全部调入cache中，则当某些块被替换后，若重新被访问，就会发生不命中。
冲突不命中：在组相联或者直接映象cache中，如果太多的块映象到同一组（块）中，则该组中某个块被别的块替换（即使别的组或块有空闲位置），然后又被重新访问的情况。（碰撞不命中，干扰不命中）

特点

相联度越高，冲突不命中就越少；
强制性不命中和容量不命中不受相联度的影响
强制性不命中不受cache容量的影响，但是容量不命中却随着容量的增加而减少

减少三种不命中的方法

强制性不命中：增加块大小，预取
容量不命中：增加容量
冲突不命中：提高相关度

许多降低不命中率的方法会增加命中时间或不命中开销

增加cache块的大小

对于给定的cache容量，当块大小增加时，不命中率开始是下降的，但是后来就上升了。

一方面它减少了强制性不命中；
另一方面，由于增加块大小会减少Cache中块的数目，可能会增加冲突不命中

增加块的大小会增加不命中开销

增加cache的容量

缺点：

增加成本
增加命中时间

提高相联度

采取相联度超过8的方案实际意义不大

容量为N的直接映象cache的不命中率和容量为N/2的两路组相联cache的不命率差不多相同

提高相联度是以增加命中时间为代价的

伪相联cache和列相联cache

基本思想：在逻辑上把直接映象cache分为上下两个区。对于任何一次访问，伪相联cache先按直接映象cache的方式去处理：如果命中，则其访问过程和直接映象cache的情况一样；如果不命中，则再对另一区相应的位置去查找。如果找到了，则发生了伪命中，否则只好访问下一级存储器。

硬件预取

指令和数据都可以预取
预取内容即可放入cache中，也可放在外缓冲器中
指令预取通常由cache之外的硬件完成

预取应利用存储器的空闲带宽，不能影响对正常不命中的处理，否则会降低性能。

编译器控制的预取

在编译的时候加入预取指令，在数据被用到之前发出预取请求。

按照预取数据所放的位置，可把预取分为两种类型：
- 寄存器预取：把数据放在寄存器中
- cache预取：只将数据放在cache中
按照预取的处理方式不同，分为：
- 故障性预取：在预取时，如果出现虚地址故障或违反保护权限，就会发生异常
- 非故障性预取：不会发生异常，编译器会放弃预取，转为空操作
在预取数据的同时，处理器应能继续执行
编译器控制预取的目的：使得执行指令和读取数据能重叠执行
每次预取需要花费一条指令的开销
- 保证开销低于收益
- 编译器可以通过把重点放在那些可能会导致不命中的访问上，使得程序避免不必要的预取

编译器优化

通过对软件进行优化来降低不命中率

程序代码和数据重组
- 重新组织程序而不影响程序的正确性
  - 把一个程序的过程重新排序，减少冲突不命中，降低指令不命中率
  - 把基本块对齐，提高大cache块的效率
- 假设编译器知道分支指令会成功转移：
  - 将转移目标处的基本块和紧跟着该分支指令后的基本块进行对调
  - 把该分支指令转为操作语义相反的分支指令（？）

牺牲cache

在cache和它的下一级存储器之间设置一个全相联的小cache；用来存放被替换出去的块（牺牲者），以备重新使用

对于减小冲突不命中很有效，特别是对于小容量的直接映象数据cache，作用尤其明显。

采取两级cache

第一级cache小且快；第二级cache容量大。

全部不命中率和局部不命中率：$全局不命中率=不命中率_{L1} X 不命中率_{L2}$

评价第二级Cache需要使用全局不命中率；
第二级cache不会影响CPU的时钟频率；

$平均访存时间=命中时间L_1+不命中率L_1X()$

参数

容量：第二级cache的容量一般比第一级cache的大很多
相联度：第二级cache可以采用较高的相联度或伪相联方法
块大小：第二级cache可以采用较大的块

让读不命中优先于写

cache中的写缓冲器导致对存储器访问的复杂化：在读不命中时，所读单元的最新值可能还在写缓冲器中，还没有进入主存。
读不命中的处理：
- 推迟对读不命中的处理，直到写缓冲器清空
- 检查写缓冲器的内容
在写回法cache中，可采取写缓冲器

写缓冲合并

写直达cache：

依靠写缓冲来减少对下一级存储器写操作的时间。

如果写缓冲器为空，就把数据和相应地址写入该缓冲器【从CPU的角度来看，该写操作就算完成了】

如果写缓冲器中已经有了待写入数据，就要把这次写入地址与写缓冲器中已有的所有地址进行比较，看看是否有匹配的项。如果有地址匹配而对应的位置又空闲，就把这次要写入的数据与该项合并。【这就是写缓冲合并】

如果写缓冲器满并且没有能进行写合并的项，就等待。

请求字处理技术

请求字：从下一级存储器调入cache块中，只有一个字是立即需要的，该字就是请求字。

应尽早把请求字发送给CPU

尽早重启动：调块时，从块的起始位置开始读起。一旦请求字到达了，就立即发送给CPU，让CPU继续执行。【请求字优先】

非阻塞cache技术

cache不命中时依旧允许CPU进行其他的命中访问。

减少命中时间

命中时间直接影响处理器的时钟频率。

Cache的访问时间限制了处理器的时钟频率。

容量小、结构简单的Cache

硬件越简单，速度就越快。

虚拟cache

物理cache

使用物理地址进行访问的传统cache。

标识存储器中存放的是物理地址，进行地址检测越是用物理地址。

缺点就是：地址转换和访问cache串行进行，访问速度慢。

虚拟cache

直接使用虚拟地址进行访问的cache。标识存储器存放的是虚拟地址，进行地址检测用的也是虚拟地址

优点：在命中时不需要进行地址转换，省去了地址转换的时间。就算是不命中，地址转换和访问cache也是并行进行的，速度比物理cache快。

虚拟地址和进程相关。

虚拟地址=虚拟索引+物理标识
用虚地址中页内位移作为cache的索引，标识用物理地址；

Cache访问流水化

对第一级cache访问按流水线方式组织

访问cache需要多个时钟周期才能完成

不能够真正减少cache命中时间，但是可以提高时钟频率，提高cache的带宽。

踪迹Cache

存放CPU所执行的动态指令序列：包含了由分支预测展开的指令，该分支预测是否需要在取到该指令时进行确认。

地址映象机制复杂
相同的指令序列有可能被当作条件分支的不同选择而重复存放
能够提高指令cache的空间利用率

并行主存系统

主存的主要性能指标：延迟和带宽

定义：是在一个访存周期内能并行访问多个存储字的存储器

在单体单字宽的存储器中：存储器的访问周期为TM ,字长为W位，则
带宽为$B_M=\frac{W}{T_M}$

单体多字存储器

存储器能够每个存储周期读出m个CPU字

$B_M=\frac{mW}{T_M}$

单体多字存储器的实际带宽比最大带宽小

缺点：访存效率不高

如果一次去读的m个指令字中有分支指令，而且分支成功，则该分支指令之后的指令是无用的。
一次取出的m个数据不一定都是有用的。此外，当前执行指令所需要的多个操作数也不一定正好都存放在同一个长存储字中
写入可能变得复杂
当要读出的数据字和要写入的数据字处于同一个长存储字内时，读和写的操作就无法在同一个存储周期内完成

多体交叉存储器

由多个单字存储体构成，每个体都有自己的地址寄存器以及地址译码和读/写驱动等电路。

编址方式：

高位交叉编址
低位交叉编址

高位交叉编址

对存储单元矩阵按列优先的方式进行编址

低位交叉编址

对存储单元矩阵按行优先进行编址

虚拟存储器

进程保护：

界地址寄存器：基地址、上界地址；检测条件：（基地址+地址）<=上界地址

虚拟存储器：给每个页面增加访问权限标识

环形保护

加锁和解锁