数据库系统工程师知识点-上午

2019

CPU由四大部件构成：

1、运算器：完成算术运算和逻辑执行，完成对数据的加工和处理。

2、控制器：控制指令执行。控制器的组成包括：程序计数器（PC）、状态条件寄存器（PSW）、时序产生器、指定寄存器（IR）、指令译码器（ID）、数据寄存器（DR）、地址寄存器（AR）、控制总线（CB）

控制器	作用
程序计数器PC（Program Counter）	存放下一条即将执行的指令地址
指令寄存器IR（Instruction Register）	存放当前正在执行的指令
指令译码器ID（Instruction Decoder）	将指令进行译码，确定操作类型和操作数地址
地址寄存器AR（Address Register）	临时存储访问内存时所使用的地址
数据寄存器DR（Data Register）	暂存从内存中读取或写入的数据
状态条件寄存器PSW（Program Status Word）	记录运算结果的状态（如溢出、进位、零等），用于条件跳转
时序产生器	生成控制各部分工作的节拍信号
控制总线CB（Controller Bus）	负责将控制信号传送到内外部设备

3、寄存器组：用来存放CPU运行中临时使用的数据和结果，速度远快于内存。

寄存器	作用
通用寄存器	供程序自由使用，如AX、BX等
专用寄存器	如栈指针SP、基址寄存器BP、段寄存器等
状态寄存器	如PSW，保存标志信息
高速缓存寄存器	作为CPU与内存交互时的临时缓冲

4、内部总线：连接CPU内部各个部件（ALU、寄存器、控制器）之间的数据传输通道。

总线	作用
数据总线	传输指令或数据
地址总线	传送地址信息
控制总线	传送控制和状态信号

• DMA控制方式是在主存与外设之间直接建立数据通路进行数据的交换处理。

• 令序列X、Y、Z的每个元素都按顺序进栈，且每个元素进栈和出栈仅一次，则不可能得到的出栈序列是ZXY。

此序列的含义为如果Z先出栈，则入栈顺序为XYZ，此时Z出栈，下一个出栈的元素应为Y

• 单链表存储结构特征

1、表中节点所占用存储空间的地址不必是连续的。

2、在表中任意位置进行插入和删除都不需要移动元素。

3、所需空间与结点个数成正比。

4、可随机访问表中的任一结点。（该选项是错误的，单链表的每个元素由数据和向后指针构成，可以仅有头节点，查询方向只能从前向后。）

• B-树称为二叉查找树，具有以下性质

1、左子树上所有结点的值均小于等于它的根结点的值。

2、右子树上所有结点的值均大于它的根结点的值。

3、根结点的左、右子树也分别为二叉查找树。

4、从根结点到每个叶结点的路径长度相同。

• 对于给定的关键字序列（47，34，13，12，52，38，33，27，5），若用链地址法（拉链法：将具有同一哈希地址的记录存储在一条线性链表中）解决冲突构造哈希表，且哈希函数为H（key）=key%11，则34和12在同一个链表中。

• 已知有序数组a的前10000个元素是随机整数，现需查找某个整数是否在数组中，使用二分查找法的效率最高。（有序数组：按小到大或者大到小进行排序。哈希查找适用于无序数据）

• 《中华人民共和国著作权法》和《计算机软件保护条例》是构成我国保护计算机软件著作权的两个基本法律文件。单个自然人的软件著作权保护期为自然人终生及死亡后50年。

• 某文件系统采用位示图(bitmap)记录磁盘的使用情况。若计算机系统的字长为64位（64位等=8字节），磁盘的容量为1024GB,物理块的大小为4MB,那么位示图的大小需要4096个字。（1024GB*1024/4MB=262144）（262144/64=4096）

• 设备驱动程序是直接与硬件打交道的软件模块。

函数调用和返回控制是用栈实现的。

编译是将高级语言源代码转换成目标代码的过程（把源程序翻译为机器语言/目标代码）。在编译方式下，用户程序运行的速度更快。

通用的高级程序设计语言一般都会提供描述数据、运算、控制和数据传输的语言成分，其中，控制包括顺序、选择和循环结构。

常见软件设计模型包括：瀑布模型、原型法、增量模型、演化模型、螺旋模型、喷泉模型。

模型	作用
瀑布模型	结构严谨、阶段分明，适合需求稳定项目，但不灵活，变更代价高
原型法	快速构建原型便于确认需求，适合需求不明确项目，但易陷入反复修改
增量模型	逐步开发逐步交付，适合可拆分功能的项目，但架构需稳固、易集成
演化模型	需求边做边调整、持续演进，适合迭代式开发，但成本与进度难控制
螺旋模型	注重风险控制、循环推进，适合大型高风险项目，但成本高、实施复杂
喷泉模型	支持面向对象和并行开发，适合现代OO系统，但管理难度大、流程复杂

模块间的耦合度是指模块之间的依赖关系，划分模块的一个准则就是高内聚低耦合。常见的耦合类型如下表所示。

耦合类型	含义
非直接耦合	如果两个模块之间没有直接关系，之间的联系完全是通过主模块的控制和调用来实现的
数据耦合	模块彼此之间是通过数据参数（不是控制参数、公共数据结构或外部变量）来交换信息
标记耦合	一组模块通过参数表传递记录信息，这个记录是某一数据结构的子结构，而不是简单变量
控制耦合	通过传送开关、标志、名字等控制信息，明显地控制选择另一模块的功能
外部耦合	一组模块都访问同一全局简单变量而不是同一全局数据结构
公共耦合	一组模块都访问同一个公共数据结构
内容耦合	一个模块直接访问另一个模块的内部数据；或者一个模块不通过正常入口转到另一模块内部

• 软件测试的目的是通过合理的测试用例，以最少的人力和时间发现潜在的各种错误和缺陷。软件测试用于检查错误，但不能证明程序中没有错误。通过有效性测试保证系统质量（满足需求规则）和可靠性。软件测试通常由开发人员、用户一起完成。软件测试分四个步骤：单元测试、集成测试、确认测试（验收测试）和系统测试。
• 数据流图建模应遵循自顶向下、从抽象到具体的原则。

数据模型三要素

要素	含义
数据结构	所研究的对象类型的集合，是对系统静态特性的描述
数据操作	对数据库中各种对象（型）的实例（值）允许执行的操作的集合，包括操作及操作规则。是对系统动态特性的描述
数据约束	是一组完整性规则的集合。对于具体的应用数据必须遵循特定的语义约束条件，以保证数据的正常、有效和相容

给定关系模式如下，学生(学号，姓名， 专业)，课程(课程号，课程名称)，选课(学号，课程号，成绩)。查询所有学生的选课情况的操作是学生LEFT JOIN选课;查询所有课程的选修情况的操作是选课RIGHT JOIN课程。

参数	含义
完全外连接	把舍弃的元组（悬浮元组）也保存在结果关系中，而在其他属性上填空值（NULL）
左外连接	只把左边关系R中要舍弃的元组保留
右外连接	只把右边关系S中要舍弃的元组保留

关系数据库查询优化的经典策略，查询优化的一个主要宗旨就是：中间结果越小越好，减少磁盘调度；因此先做筛选、然后连接、最后投影。

1、选择运算（如 WHERE age > 30）尽可能先做。在优化策略中这是最重要、最基本的一条。

2、把投影运算（如 SELECT name, age）选择运算同时进行。避免重复扫描关系。

3、把投影同其前或其后的双目运算（双目运算 = 两个表的运算，比如并、差、连接）起来。

4、把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算（直接做等值连接，不要做“无条件全连接”）

5、找出公共子表达式。

• 给定关系R（A.B.C.D）与S（C.D.E.P），则R x S（笛卡尔积，不合并相同的列）与R∞S（自然连接，合并相同的列）操作结果的属性个数分别为8，6。与表达式pai2，3，4（欧米茄2<5（R∞S））等价的SQL语句为select R.B,R.C,R.D from R,S where R.C=S.C and R.D=S.D and R.B<S.E

• 某企业人事管理系统中有如下关系模式，员工表Emp(num,ename, age, sal,dname)属性分别表示员工号，员工姓名、年龄、工资和部门名称，部门表Dept(dname,phone),属性分别表示部门名称和联系电话。需要查询其它部门比销售部门(Sales) 所有员工年龄都要小的员工姓名及年龄，对应的SQL语句如下: select ename,age from Emp where age<ALL(select age from Emp where dname='Sales') and name <>'Sales'

• 对分组查询结果进行筛选的是HAVING子句，其条件表达式中可以使用聚集函数。

• 授权语句GRANT中，WITH GRANT OPTION子句用于指明获得权限的用户还可以将该权限赋给其他用户。

• 触发器（trigger）是SQL Server提供给程序员和数据分析员来保证数据完整性的一种方法，它是与表事件相关的特殊存储过程，它的执行不是由程序调用，也不是手工启动，而是由事件来触发。触发器可以实现比CHECK更为复杂的约束。与CHECK约束不同，触发器可以引用其他表中的列。触发器不能使用参数，不能使用事务控制语句；触发器中调用的过程、函数也不能包含事务控制语句。

• 最小函数依赖集的定义为：每个函数依赖右部为单属性，左部不含冗余属性；不含多余的函数依赖。传递依赖为多余的函数依赖，部份依赖的左部含有冗余属性。

Armstrong 公理三条基本规则和推导

规则	含义
自反性（Reflexivity）	如果 Y ⊆ X，则 X → Y
增广性（Augmentation）	如果 X → Y，则 XZ → YZ
传递性（Transitivity）	如果 X → Y 且 Y → Z，则 X → Z
合并（Union）	X → Y 且 X → Z 推出 X → YZ
分解（Decomposition）	X → YZ 推出 X → Y 和 X → Z
伪传递（Pseudo Transitivity）	X → Y 且 WY → Z 推出 WX → Z

• 关系模式R<{A, B, C}，{AC→B, B→C}>的候选码之一 是AB ;由于该模式存在主属性对码的部分函数依赖，其规范化程度最高属于3NF。（该题目候选码若为AC，则只属于1NF）

关系数据库关键术语对比表

名称	含义	举例说明	是否唯一标识元组	是否是码的一部分
候选码	能唯一标识一条记录的最小属性集合，可能不止一个	例：表中（身份证号）、（手机号）都可以唯一标识用户	✅ 是	✅ 是
主码	候选码中选出来作为主要标识的一个	通常选用身份证号作为主码	✅ 是	✅ 是
外码	表中的一个属性，它引用另一个表的主码，用于建立关联关系	学生表中 DeptNo 是外码，引用 Dept 表的 DeptNo 主码	❌ 否	❌ 否
主属性	属于候选码中的属性	例：若候选码是（Sno, Cno），那 Sno 和 Cno 都是主属性	✅ 是	✅ 是
非主属性	不属于任何候选码的属性	成绩（Grade）不是候选码的一部分，就是非主属性	❌ 否	❌ 否

• 将一个关系r分解为两个关系r1和r2，再将分解之后的两个关系r1和r2进行自然连接，得到的结果如果比原关系r记录多，则称这种分解为有损连接的分解。

• 用于提交和回滚事务的语句为commit transaction和rollback transaction。

事务的ACID特性：原子性、一致性、隔离性、持久性。由于并发操作打破了隔离性，则带来了数据的不一致。

影响	含义
丢失修改	一个事务对数据的修改被另一个事务所覆盖
读脏数据	读到了另一个事务未提交的修改数据，稍后该数据因事务的回滚而无效
不可重复读	一个事务两次读同一数据期间，该数据被另一事务所修改，造成两次读的值不同
幻影现象	两次读中间被插入或删除了记录，造成两次读到的记录数不同

• 并发事务如果对数据读写时不加以控制，会破坏事务的隔离性和一致性。控制手段就是加锁，在事务执行时限制其他事务对数据的读取。在并发控制中引入两种锁：排他锁（独占写）和共享锁（共享读）。

• 存储过程（Procedure）是一组为了完成特定功能的SQL语句集合，经编译后存储在数据库中，用户通过指定存储过程的名称并给出参数来执行。存储过程中可以包含逻辑控制语句和数据操纵语句，它可以接受参数、输出参数、返回单个或多个集合集以及返回值，存储过程中可以调用其他存储过程。

以下是关于1NF到4NF以及BCNF的对比表格，包含定义、解决的问题和示例：

范式	名称	定义	解决的问题	示例	分解方法
1NF	第一范式	所有属性都是原子的（不可再分），每一列的值都是单一值，无重复组。	消除重复组和保证数据原子性	表格中的“地址”列存储“省-市-区”，需拆分为三列。	拆分非原子列为多个字段。
2NF	第二范式	满足1NF，且所有非主属性完全依赖于候选键（消除部分依赖）。	消除部分依赖	订单表（订单号, 产品号, 产品名称, 数量）中，“产品名称”仅依赖产品号。	拆分为订单表（订单号, 产品号, 数量）和产品表（产品号, 产品名称）。
3NF	第三范式	满足2NF，且非主属性不传递依赖于候选键（消除传递依赖）。	消除传递依赖	员工表（员工ID, 部门, 部门经理）中，“部门经理”通过“部门”依赖员工ID。	拆分为员工表（员工ID, 部门）和部门表（部门, 部门经理）。
BCNF	巴斯-科德范式	满足3NF，且所有决定因素（左侧属性）必须是候选键。	消除主属性对候选键的依赖	课程表（课程, 教授, 系别）中，假设“教授 → 系别”，但教授不是候选键。	拆分为（教授, 系别）和（课程, 教授）。
4NF	第四范式	满足BCNF，且消除非平凡的多值依赖。	消除多值依赖	员工表（员工, 技能, 项目）中，技能和项目独立多值，导致冗余。	拆分为员工技能表（员工, 技能）和员工项目表（员工, 项目）。

• 数据库系统应该定期备份，如果备份过程中仍有更新事务在运行，则备份结果是不一致的，这种备份称为动态备份，静态备份在转存期间不允许对数据库进行更新。

• 数据库系统的故障分为三类：事务故障、系统故障和介质故障。事务故障是单独一个事务出现问题而不能执行下去，并不影响其他事务的执行；系统故障是故障导致系统重启，当前运行中的事务及刚刚提交的事务会导致数据库不一致；介质故障则是数据库文件的存储介质如硬盘发生故障导致数据丢失。DBMS对不同类别的故障使用不同的恢复方法。其中事务故障和系统故障由DBMS来完成事务级别的恢复，即根据日志文件对未完成的事务进行UNDO操作，对已完成的事务进行REDO操作，使数据库恢复到故障前的一致性状态；介质故障需要DBA介入，装载备份文件后交由DBMS进行恢复。（redo 是“重做提交操作”，undo 是“撤销未提交”）

• 两段锁协议：对任何数据进行读写之前必须对该数据加锁，在释放了一个封锁之后，事务不再申请和获得任何其他封锁。这就缩短了持锁时间，提高了并发性，同时解决了数据的不一致性。两段锁协议可以保证可串行化，它把每个事务分解为加锁和解锁两段，但是两段锁协议不能保证不产生死锁。

反规范化（denormalization）是加速数据检索的方法，这种方法有效地在数据标准化后增加特定的冗余数据实例。常用的反规范化计算有增加冗余列、增加派生列、重新组表和分割表。

技术	含义
增加冗余列	在多个表中具有相同的列，用于查询时避免连接操作
增加派生列	增加的列来自于其他表中的数据，由他们计算生成。用于在查询时减少连接操作
重新组表	许多用户需要查看两个表连接出来的数据结果，则把这两个表重新组成一个表来减少连接而提高性能
分割表	对表做水平分割或垂直分割以提升性能

• 在索引改进中，一般的调整原则是:当查询是性能瓶颈时，则在关系上建立索引;当更新操作（如插入、删除、修改）是性能瓶颈时，则考虑删除某些索引;管理人员经常会将有利于大多数据查询的索引设为聚簇索引。

SQL语句性能优化知识：

1、尽可能减少多表查询。

2、在更新频繁、实时性要求高的场景下，慎用物化视图；但在查询密集、更新较少的场景下，物化视图是非常有效的优化手段。

3、在采用嵌套查询时，尽可能以不相关子查询替代相关子查询。

4、只检索需要的列。

5、在WHERE子句中尽可能使用IN运算代替OR运算。

6、查询时避免使用LIKE'%string'，避免全表数据扫描；而采用LIKE'string%'则可使用对应字段的索引。

7、尽可能使用UNION ALL而不使用UNION，因为后者操作时要排序并移走重复记录，而前者不执行该操作。

8、经常使用COMMIT语句，以尽早释放封锁。

• 审计日志（Audit Log）是指记录用户对数据库的所有操作。DBA利用审计日志能找出非法存取数据的人、时间和内容。

• NoSQL为非关系型数据库，不使用SQL作为查询语言，数据存储不需要固定的表结构，通常也不存在连接操作。NoSQL在大数据存取上具备关系型数据库无法比拟的性能优势，满足了数据存储在横向伸缩性上能够满足需求（尤其是WEB应用）。同时，NoSQL不需要满足ACID，只需要满足Base（弱一致性理论，只要求最终一致性）即可。

2022

计算机系统基础知识

时间单位	含义
指令周期	取出一条指令并执行这条指令的时间。一般由若干个机器周期组成，是从取指令、分析指令到执行完所需的全部时间，每一阶段完成一个基本操作
时钟周期	也称为振荡周期，定义为时钟频率的倒数。时钟周期是计算机中最基本的、最小的时间单位。在一个时钟周期内，CPU仅完成一个最基本的动作。更小的时钟周期就意味着更高的工作频率
总线周期	CPU完成一次访问MEN（内存访问）或I/O端口操作所需要的时间
CPU周期	完成一次基本操作所需要的时间，也称为机器周期，一般情况下，一个机器周期由若干个时钟周期组成
存储周期	主存储器两次启动操作之间需要的最小的时间间隔，即主存储器周期时间

• 设指令由取指、分析、执行 3 个子部件完成，并且每个子部件的时间均为△t。若采用常规标量单流水线处理机，连续执行20条指令，共需22△t。（采用流水方式时，执行时间=单条指令时间+（n-1）MAX△t）

• 计算机系统中，I/O接口的功能有数据传输及缓存、设备状态检测和反馈、I/O操作的控制与定时。

I/O接口是主机与被控对象进行信息交换的纽带，CPU与外设之间的数据交换必须通过接口来完成，通常接口有以下功能。

1、设置数据的寄存、缓冲逻辑，以适应CPU与外设之间的速度差异。

2、信息格式的转换，例如串行和并行的转换。

3、协调CPU和外设两者在信息的类型和电平的差异，如电平转换驱动器、数/模或模/数转换器等。

4、协调时序差异。

5、地址译码和设备选择功能。

6、设置终端和DMA控制逻辑。

计算机中使用系统总线结构的目的是便于增减外设，同时减少信息传输线的数量。

总线（BUS）是计算机各种功能部件之间传输信息的公共通信干线，它是由导线组成的传输线束。根据总线连接设备范围的不同，可分为以下几种。

1、片内总线：芯片内部的总线。

2、系统总线：计算机各部件之间的总线。系统总线根据功能可以划分为数据总线、地址总线和控制总线，分别用来传输数据、数据地址和控制信号。

3、通信总线： 用于计算机系统之间或计算机系统与其他系统之间的通信。

• 计算机在处理算数表达式 78+21*（36-34）时，先将其转换成"78 21 36 34-*+"的后缀形式表示，然后利用栈进行计算。（算数表达式 78+21（36-34）转化为后缀从左向右扫描，从优先级最低的运算符开始分解：1、78 21（36-34）+2、78 21（36-34）*+）

• 队列：限定只能在表的一端（队尾rear，如左端）进行插入，在表的另一端进行删除（队头front，如右端）的线性表。此种结构称为先进先出（FIFO）线性表。

• 串是由 n 个字符（字符的取值范围是有限的）组成的一个整体，串的逻辑结构和线性表相似，故看作一种受限线性表。串的存储方式包括：定长顺序存储、堆分配存储、块链存储（链表）。

• 折半查找（二分法查找）的前提是：必须在顺序存储结构的有序表中进行。

排序算法相关知识

算法	含义
冒泡排序	交换类排序法，借助元素之间的互相交换进行排序。思想是：小的浮起，大的沉底。排序n个数据，最多需要n-1趟冒泡排序
快速排序	分治法。选一个“基准值”（pivot），小的放左边，大的放右边，然后递归处理两边
堆排序	将数组构造成一个最大堆（父节点比孩子大），然后不断把堆顶最大值取出，重新调整堆
希尔排序	改进的插入排序。把整个序列分组，组内插入排序，逐步缩小 gap，最后 gap=1 做一次插入排序

• SSH专门为远程登录会话和其他网络服务提供安全性的协议，工作在应用层。

• IPSec：利用IPSec可以提供VPN中传送经过加密的信息，IPSec并不是一个单一协议，而是能够在IP层提供互联网通信安全的协议簇。工作在网络层

• Socks：防火墙安全会话转换协议，为在TCP和UDP域中的客户机/服务器应用程序能更方便安全地使用网络防火墙所提供的服务器。工作在会话层。

I/O中断相关知识

输入输出控制方式	含义
无条件传送	在此情况下，外设总是准备好的，它可以无条件地随时接收CPU发来的输出数据，也能够无条件地随时向CPU提供需要的输入的数据，实际上这只是理想方式
程序查询方式	在这种方式下，利用查询方式进行输入输出，就是通过CPU执行程序查询外设的状态，判断外设是否准备好接收数据或准备好了向CPU输入的数据
中断方式	由程序控制I/O的方法，其主要缺点在于CPU必须等待I/O系统完成数据传输任务，在此期间CPU需要定期地查询I/O系统的状态，以确定传输是否完成。因此整个系统的性能严重下降。
直接主存存取（DMA）	指数据在主存与I/O设备间的直接成块传送，即主存与I/O设备间传送数据块的过程中，不需要CPU作任何干涉，只需要在过程开始启动（即向设备发出传送一块数据的命令）与过程结束（CPU通过轮询或中断得知过程是否结束和下次操作是否准备就绪）时由CPU进行处理，实际操作由DMA硬件直接完成，CPU在传送过程中可做别的事情。
TLB转译后备缓冲器	CPU的一种缓存，可介于CPU和CPU缓存之间，或在CPU缓存和主存之间。地址转换加速缓存，保存页表的热点映射项，加快虚拟地址到物理地址的转译过程

操作系统的处理机调度相关知识

调度算法	含义
先来先服务FCFS	有利于长作业（进程）；有利于CPU繁忙性作业（进程），不利与I/O繁忙型
优先级调度	有利于优先级较高的作业，有可能造成低优先级作业饿死
短作业进程优先调度算法	提高了平均周转时间和平均带权周转时间，从而提高了系统吞吐量；对长作业不利，有可能得不到服务（饿死）
时间片轮转算法	系统将CPU服务时间进行划分，每个划分称为一个时间片，进程轮流获得指定时间片的CPU服务，适合交互式系统

• 能够不访问页表（将虚拟地址映射到物理地址），实现快速将虚拟地址映射到物理地址的硬件机制是转换检测缓冲区。

线程相关知识

线程共享资源	线程独享资源
地址空间	程序计数器
全局变量	寄存器
打开的文件	栈
子进程	状态字
闹铃
信号及信号服务程序
记账信息

• 系统为全局变量分配的存储空间在程序运行的过程中一般是不改变的，而为局部变量分配的存储单元是动态改变的。结构体中可以嵌套对象类型数据，这些数据会随着上下文动态变化；同理，数组概念也是可以拓展到对象数组，即使对基本数据数组，也会根据需要拓展数据存储空间。

• 函数是C语言的基本构成单元，包括标准库函数和用户定义函数。C语言函数是一段具有独立功能的程序单元；需要先声明后引用；函数的定义包括函数首部（函数名及参数）和函数体。C语言中的函数是不允许嵌套定义的。

• V模型又称快速应用开发模型，测试为驱动的开发模型，该模型强调开发过程中测试贯穿始终，是瀑布模型的一个变体。

软件需求分析是确定系统的各方面需求，包括：确定系统界面要求、系统的功能要求、系统的性能要求、系统的安全和保密性要求、系统的可靠性要求、异常处理要求和将来可能提出的要求。

数据流图以图形的方式描绘数据在系统中流动和处理的过程，它反映了系统必须完成的逻辑功能，是结构化分析方法中用于表示系统逻辑模型的一种工具。

概念	含义
数据流（data flow）	沿箭头方向传送数据的通道，一般在旁边标注数据流名
加工（process）	输入数据经加工、变换产生输出
存储文件（file）	数据源，表示处理过程中存放各种数据的文件
源/谭（source/sink）	表示系统和环境的接口，属于系统之外的实体

UML图相关知识

概念	含义
类图	展现了一组对象、接口、协作和它们之间的关系。类图用于对系统的静态设计视图建模
对象图	展现了一组对象以及它们之间的关系。描述了在类图中所建立的事物的实例的静态快照（某一时刻）
序列图	强调以时间顺序组织的对象之间的交互活动。有对象生命线、控制焦点
状态图	展现了一个状态机，对一个对象按事件排序的行为建模，它由状态、转换、时间和活动组成

• 模式是数据库中全体数据的逻辑结构和特征的描述。模式可以看作数据库的型，是静态的固定的；而实例是模式的一个具体值，反映数据库某一时刻的状态，同一个模式可以有很多实例，实例随数据库中的数据更新而变动。

• 为了有效地组织、管理数据，数据库采用三级模式结构：内模式、模式和外模式组成，即由物理级、概念级和视图级组成。模式也称为逻辑模式，一个数据库只有一个模式；是数据库中全体数据的逻辑结构和特征的描述，所有用户的公共数据视图，综合了所有用户的需求。外模式也称为子模式或用户模式，是数据库用户（包括应用程序员和最终用户）使用的局部数据的逻辑结构和特征的描述，一个模式可以有若干外模式。内模式也称存储模式，是数据物理结构和存储方式的描述，是数据在数据库内部的表示方式。一个数据库只有一个内模式。由于存在模式/外模式映射和模式/内模式映射，因此模式和内模式变化不会导致外模式改变；反之，外模式的变化也不会导致模式和内模式变化。

数据库中完整性约束

概念	定义
实体完整性	规定基本关系R的主属性A不能取空
用户自定义完整性	针对某一具体关系数据库的约束条件，反映某一具体应用所涉及的数据必须满足语意要求，由应用的环境决定。如：年轻必须大于0小于150的整数
参照完整性/引用完整性	规定，若F是基本关系R的外码，它与基本关系S的主码K相对应（基本关系R和S不一定是不同的关系），则R中每个元组在F上的值必须存在（等于S中某个元组的主码值）或者取空值

一个二维表能称之为关系，具有如下性质

1、属性的原子性，即属性是不可再分，表中不再包含表。

2、同一关系中属性唯一性。

3、关系中元组的唯一性。

4、关系中元组的有限性。

5、关系中元组次序无关紧要。

6、关系中属性次序无关紧要。

ACID性质

性质	概念
原子性（atomicity）	事务上原子的，要么都做，要么都不做
一致性（consistency）	事务执行的结果必须保证数据库从一个一致性变化到另一个一致性状态
隔离性（isolation）	事务相互隔离。当多个事务并发执行时，任一事务的更新操作直到其提成功提交的整个过程，对其他事务都是不可见的
持久性（durability）	一旦事务成功提交，即使数据库崩溃，其对数据库的更新操作也将永久生效

• NOT NULL表示字段取值不能为空；UNIQUE表示在字段上建立唯一索引，该字段取值不能重复，但可以为空；DEFAULT表示指定字段的默认值。

• 行级触发器（For Each Row）：每条记录上执行了触发动作，触发器就执行一次。语句级触发器（For Each Statement）：一条SQL如果涉及到多条记录，触发器仅执行一次。

在关系模式"学生（学号，姓名，性别，年龄，系号，系名）"中，一个学生只能属于一个系"系名"对于码"学号"的数据依赖是传递函数依赖，该关系模式最高属于2NF，将"学生"分解为两个关系模式：S（学号，姓名，性别，年龄，系号）和D（系号，系名），则此分解具有无损连接性，保持函数依赖。

类型	定义描述	举例说明	所在范式相关性
平凡函数依赖	若属性集 Y 属于 X（即 Y ⊆ X），则 X → Y 是平凡函数依赖	例如：{学号, 姓名} → 学号	所有范式都允许
部分函数依赖	若 X → Y，且 Y 依赖于 X 的 一部分，则称为部分依赖。只发生在候选码是复合属性的情况下	例如：{学号, 课程号} → 成绩，但 成绩 仅依赖于 课程号	存在于 1NF，排除于 2NF
传递函数依赖	若 X → Y，Y → Z，且 Z 不属于 X，称 Z 对 X 存在传递依赖	例如：学号 → 系号，系号 → 系名 ⇒ 学号 → 系名 为传递依赖	存在于 2NF，排除于 3NF
多值依赖	若给定 X 的值时，Y 有多个独立于 Z 的值（即 X →→ Y，且 Y 与 Z 无关），称 Y 对 X 有多值依赖	例如：教师 T 教多个课程、负责多个项目 ⇒ T →→ 课程名，T →→ 项目名	3NF无法消除，排除于 4NF

• 存储过程（Procedure）是一组为了完成特定功能的SQL语句集合，经编译后存储在数据库中，用户通过指定存储过程的名称并给出参数来执行。存储过程正是在服务器端所提供的功能调用，适用于编写更新数据库的事务程序。存储过程中可以包含逻辑控制语句和数据操纵语句，它可以接受参数、输出参数、返回单个或多个结果集以及返回值，存储过程可以调用其他存储过程。

• 如果事务T获得了数据项R上的X（排他锁）锁，则T对R既可读又可写。

封锁协议是策略，是规定“在什么时候、如何使用锁”的一系列规则。

级别	内容	优点	缺点
一级封锁协议	事务在修改数据之前，必须先对该数据加 X锁，直到事务结束时才释放	防止“丢失修改”	不加锁的事务，可能“读脏数据”，也可能“不可重复读”
二级封锁协议	但其他事务在读取数据之前必须先加 S锁	防止“丢失修改” 防止“读脏数据”	对加 S锁 的事务，可能“不可重复读”
三级封锁协议	事务在读取数据时必须加 S锁，直到事务结束时才释放	防止“丢失修改” 防止“读脏数据” 防止“不可重复读”	无显著缺点（但并发性会相对降低）

数据库设计的6个阶段依次如下所示

1、需求分析：对数据库应用系统所要涉及的内容（数据）与功能（行为）的整理和描述，是以用户的角度来认识系统。

2、概念结构设计：E-R图，在需求分析的基础上，依照需求分析中的信息要求，对用户信息加以分类、聚集和概括，建立信息模型，反映了用户观点。

3、逻辑结构设计：逻辑结构设计阶段的主要工作步骤包括确定数据模型、将E-R图转换成指定的数据模型、确定完整性约束和确定用户视图。

4、物理结构设计：确定数据库在计算机的具体存储。

5、数据库实施：根据逻辑和物理设计的结果，在计算机上建立起实际的数据库结构并装入数据，进行试运行和评价的过程。

6、数据库运行和维护：对数据库性能的检测和改善，数据库的备份及故障恢复，数据库重组和重构。

• 数据字典是值对数据的数据项、数据结构、数据流、数据存储、处理逻辑等进行定义和描述，其目的是对数据流图中的各个元素做出详细的说明。在数据库中，数据字典是对系统中的各类数据描述的集合。

• E-R是概念模型用于信息世界的建模，是数据库设计的有力工具，也是数据库设计人员和用户之间进行交流的语言。其中，矩形表示实体、椭圆表示属性，菱形表示联系。现实世界中事物内部以及事物之间的联系，在信息世界中反映为实体内部的联系和实体之间的联系。实体之间的联系根据其关联的实体个数，又分为一元联系、二元联系、三元联系等。

• 数据仓库（DataWarehouse）是决策支持系统建立的重要技术手段，是建立决策支持系统的基础。数据仓库的数据具有四个基本特征：面向主题的、集成的、不可更新的（相对稳定）、随时间不断变化。

2023

• 计算机的存储体系中，三级存储指的是：高速缓冲存储器、主存储器、辅助存储器。三级存储的用途是：高速缓冲存储器用来改善主存储器与中央处理器的速度匹配问题；辅助存储器用于扩大存储空间。CPU执行指令时需要读取数据，发出的数据地址是内存的物理地址。

• 设有效信息位的位数为M，校验位数为K，则能检测1位出错并自动纠正1位错误的海明校验码应满足下面的关系

$$ 2^K-1>=M+K $$

• 在中断方式下，I/O设备工作时CPU不再等待，而是进行其他的操作（此时应保存正在执行程序的现场）；当I/O设备完成后，通过一个硬件中断信号通知CPU，CPU再来处理接下来的工作（中断服务程序的入口地址）。中断向量表用来保存各个中断源的中断服务程序的入口地址。当外设发出中断请求信号（INTR）以后，由中断控制器（INTC）确定其中断号，并根据中断号查找中断向量表来取得其中中断服务程序的入口地址，同时INTC把中断请求信号提交给CPU。

• 二叉树的结点总数n=n0+n1+n2，且n0=n2+1。

软件测试方法的相关知识

测试方法	含义
源代码测试	属于静态测试源代码，安全测试覆盖所有代码路径和查找大部份的安全漏洞类型
二进制代码测试	属于动态测试，对源代码编译后的二进制代码进行测试，一般采用黑盒测试的方法
动态渗透测试	渗透测试服务的目的在于充分挖掘和暴露系统的弱点，从而让管理人员了解其系统所面临的威胁。渗透测试不同于脆弱性评估，渗透测试往往是黑盒测试，测试者模拟黑客，主要评估安全性问题
模糊测试	通过向目标系统提供非预期的输入，并监视异常结果来发现软件漏洞的方法

密码安全相关知识

生日攻击是一种密码学攻击手段，所利用的是概率论中生日问题的数学原理，攻击者可在中找到hash散列函数碰撞，伪造报文，攻击报文身份验证。

攻击方法	含义
流密码	序列密码也称为流密码（Stream Cipher），是对称密码算法，利用密钥产生一个密钥流Z=Z1Z2Z3…，然后利用此密钥流依次对明文X=X0X1X2...进行加密
分组密码	将明文消息编码表示后的数字（简称明文数字）序列，划分成长度为n的组，每组分别在密钥的控制下变换成等长的输出数字（简称密文数字）序列
替换密码	通过对明文中的字母根据某种方式替换为其它字母转变为密文
Hash碰撞	哈希碰撞是指，两个不同的输入得到了相同的输出

• 著作权的保护中，署名权、修改权、保护作品完整权不受时间限制。

• 我国计算机软件的保护方式主要有著作权、商业秘密、专利3种方式。通常，计算机软件的保护应以著作权保护为主，商业秘密保护为辅，专利保护为补充。

设备管理相关知识

磁盘上数据读取和写入所花费的时间分为：寻道时间、旋转延迟、传输时间三个部份，寻道时间（查找时间）占主导地位。

操作	含义
寻道时间（查找时间）	磁臂移动到指定磁道所需要的时间
旋转延迟	扇区移动到磁头下方的时间，只与磁盘驱动器的转速有关，如7200转/秒，平均旋转延迟=1/（2*转速每秒）
传输时间	从磁盘读出或将数据写入磁盘的时间。传输时间=读写的字节数/每秒转速*每扇区字节数

进程间通信（Inter-Process Communication，IPC）即进程间传输数据（交换信息），实现方法有：管道、消息队列、共享内存、信号量、信号、Socket。

方法	含义
锁变量	为避免两个进程间同时要求访问同一共享资源而引起访问和操作的混乱，在进程对共享资源进行访问前必须对其进行锁定，该进程访问完后再释放。这是UNIX为共享资源提供的互斥性保障，会出现等待
Petersion算法	实现互斥锁的并发程序设计算法，可以控制两个线程访问一个共享的单用户资源而不发生访问冲突
TSL指定	用硬件实现，执行的过程不允许被中断，把"上锁"和"检查"操作用硬件的方式变成原子操作。缺点是不满足"让权等待"原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致"忙等"
信号量	不是用于交换大量数据，而用于多进程之间的同步（协调对共享存储段的存取），不需要忙等

页面替换算法相关知识

算法	含义
先进先出（FIFO）	总是淘汰最先进入内存的页面
最近最久未用	选择最近（在一段时间内）最久未被使用的页面换出。为页面设置访问字段，记录上一次被访问的时间t，选择t最大的页面换出
第二次机会算法	FIFO算法可能会把经常使用的页面置换出去，为避免该问题，修改为：检查最老页面的R位。如果R位为0，代表这么页面既老又没有被使用，可以立即置换，如果是1，就将R位清0，并把该页面放到链表的尾端
时钟算法	第二次机会算法经常要在链表中移动页面，降低了效率；将所有页面都保存在环形链表中，一个表针指向最老的页面，当发生缺页中断时，检查表针指向的页面，如果R位数0就淘汰该页面，并把新的页面插入这个位置，然后把表针前移一个位置，如果R位是1就清除R位并把表针前移一个位置
最近未使用算法	系统为每一页面设置了两个状态位。当页面被访问（读）时 设置R位，当页面被写入（修改）时设置M位

数据库类型相关知识

类型	含义
基本类型	整型（int）、实型（float、double）、字符型（char）、布尔型（bool）
特殊类型	空类型（void）
用户定义类型	枚举类型（enum）
构造类型	数组（Array）、结构体（Struct）、联合（Union）
指针类型	type*
抽象类型	类类型class

• 在两个关系R和S中，如果R和S属性个数不同，即关系的结构不同，不能进行并、交、差运算，只能进行笛卡尔积运算。

• 视图是从一个或者多个表或视图中导出的虚表，其结构和数据是建立在对表的查询基础上的。视图创建完毕后，数据字典中存放的是视图定义。更新视图是指通过视图来插入、删除、修改数据。对视图的更新，最终转换为对基本表的更新。并不少所有的视图都可以更新，比如：从多个基本表通过连接操作导出的视图不允许更新，对使用了分组、集函数操作的视图不允许更新操作。

• NULL值在数据库中是一个非常特殊的值，表示无意义或者不知道（即unknown，属性没有值或者属性值未知）。NULL值不能用比较运算符进行比较，只能使用IS NULL或IS NOT NULL进行比较。

• 在SELECT中，聚集函数（sum、avg、count、max、min）等可以出现在任何使用表达式的地方，如select、having等，但不能出现在where子句中。

• 触发器可以实现比CHECK更为复杂的约束。与 CHECK 约束不同，触发器可以引用其它表中的列。触发器经常用于加强数据的完整性约束和业务规则等。触发器不能使用参数，不能使用事务控制语句；触发器中调用的过程、函数也不能包含事务控制语句，内部不能使用数据定义语言（DDL）。

比较项	触发器（Trigger）	CHECK 约束
功能复杂性	✅ 可实现复杂逻辑，包括调用函数、条件判断、多表操作等	❌ 只能针对当前表的单一列或列组合做简单布尔判断
是否能引用其他表	✅ 可以引用其他表中的字段	❌ 不可以引用其他表
适用范围	行级或语句级，在 INSERT、UPDATE、DELETE 时触发	仅在插入或更新字段时生效
参数使用	❌ 不支持传参	❌ 不支持传参
事务控制语句	❌ 不允许使用（如 COMMIT、ROLLBACK）	❌ 不涉及事务
支持的 SQL 类型	支持 DML（INSERT、UPDATE、DELETE）	不涉及 DML，只能检查条件是否为真
与函数/过程关系	可以调用存储过程或函数，但其中也不能含事务控制语句	无法调用外部函数或过程
常用用途	实现跨表约束、自动维护日志、复杂业务规则等	强制基本的数据字段合法性检查

表设计优化策略

1、如果频繁访问两个表中的关联数据，则考虑采用表合并的方法，减少连接操作。

2、如果元组数量很大、导致操作效率降低时，可以对表进行水平分解，从而减少检索元组数量。

3、物理分区,就是将一个表分成多个区块进行操作和保存，从而降低每次操作的数据，提高性能。

4、如果进程对关系中某些属性进行检索或操作，可以考虑采用垂直分解将相关属性分离出来，提高效率。

优化策略	原理/做法	适用场景
表合并	将频繁联合查询的两个表合并为一个新表，减少 JOIN 操作开销	两表存在强关联关系，且总是同时访问，例如订单表和订单详情表
水平分解	按条件将表中的行（元组）划分为多个子表，例如按时间/地区划分	表中记录太多，查询中常带有过滤条件（如查询最近一月记录）
垂直分解	将表中不同功能的列（属性）划分到多个表中，常配合主键关联	频繁访问表中部分列，如频繁查询用户信息表中的登录字段，而很少访问头像、地址等字段
物理分区（分区表）	在物理存储层面将大表划分为多个分区，数据库自动管理这些分区，用户逻辑上仍访问一个表	数据量极大，需提高读写效率或提升并行处理能力，如按月分区日志数据

• 索引的主要作用是提高数据的检索效率，数据库系统中主要采用B树索引和散列索引。

• 延迟修改机制先在日志中记录一个事务的所有write操作，而该事务的所有write操作拖延到事务最后一条语句被执行后才执行，来保证事务的原子性。延迟修改减少I/O操作，有助于提高数据库的运行效率。

• 磁盘是计算机主要的存储介质，可以存储大量的二进制数据，并且断电后也能保持数据不丢失。根据计算机组成原理中对存储器的分类，易失性存储器的特点是当电源关闭后不能保留数据，而且无法恢复；非易失性存储器是把电流关掉后，所存储的数据不会消失的数据存储器。虚拟存储器：虚拟内存别称虚拟存储器，即利用一部分硬盘空间来充当内存使用；当内存耗尽时，计算机就会自动调用硬盘来充当内存，以缓解内存的紧张。

• 分布式数据库的设计主要考虑数据分布的设计，数据分布主要目的是提高访问的局部性，即通过数据的合理分布，尽可能地使更多的数据能够就地存放，以减少远距离的数据访问。