目录

第一章计算机系统基本知识

1.1 计算机系统

1.1.1 计算机硬件组成

1.1.2 中央处理单元

1.1.3 数据表示

1.1.4 校验码

1.2 计算机体系结构

1.2.1 体系结构分类

1.2.2指令系统存

1.2.3储系系统

1.2.4输入/输出技术

1.2.5总线结构

1.3 可靠性、性能、安全

1.3.1 计算机可靠性

1.3.2计算机系统的性能评价

1.3.3信息安全

第二章 程序语言基础知识

2.1 程序设计语言的基本概念

2.2 程序设计语言的基本成分

2.3 编译程序基本原理

第三章 数据结构与算法

3.1 数据结构

3.1.1 线性结构

3.1.2 数组

3.1.3 矩阵

3.1.4树与二叉树

3.1.5图

3.2 查找

3.2.1 顺序查找

3.2.2 折半查找

3.2.3 哈希表

3.3 排序

3.3.1 直接插入排序

3.3.2 希尔排序

3.3.3 简单选择排序

3.3.4 堆排序

3.3.5 冒泡排序

3.3.6 快速排序

3.3.7 归并排序

3.3.8 基数排序

3.3.9 内部排序算法总结

3.3.10 算法特性

第四章 操作系统知识

4.1 进程管理

4.1.1 操作系统概述

4.1.2 进程组成和状态

4.1.3 前趋图

4.1.4进程同步与互斥

4.1.5进程调度

4.1.6死锁

4.1.7线程

4.2 存储管理

4.2.1 分区存储管理

4.2.3分页存储管理

4.2.4分段存储管理

4.2.5段页式存储管理

4.3 设备管理

4.3.1 设备管理概述

4.3.2I/0软件

4.3.3设备管理技术

4.4 文件管理

4.4.1 文件管理概述

4.4.2索引文件结构

4.4.3文件目录

4.4.4文件存储空间管理

第五章 计算机网络

5.1 网络功能和分类

5.2OSI七层模型

5.3TCP/IP协议

5.4传输介质

5.5通信方式和交换方式

5.6IP地址

5.7IPv6

5.8网络规划和设计

5.9 其他考点补充

5.10 网络安全技术

5.11网络安全协议

第六章 数据库技术基础

6.1 基本概念

6.1.1 关于数据的基本概念

6.1.2 数据库管理系统的功能

6.1.3 数据各个发展阶段的特点

6.1.4 数据库系统的体系结构

6.2 数据模型

6.2.1 三级模式两级映像

6.2.2 数据模型_模型分类

6.2.3数据模型_组成要素

6.2.4概念模型中的基本概念

6.2.5 数据模型

6.3 数据存储与查询

6.4 数据仓库与数据挖掘基础知识

6.4.1 数据仓库

6.4.2 数据挖掘

6.4.3商业智能BI

第七章 关系数据库

7.1 关系数据库概述

7.2 关系代数

7.3 元组演算与域演算

7.4 查询优化

7.5 关系数据库设计

7.6 模式分解

第八章 数据库SQL语言

8.1 SQL语言概述

8.2 数据库定义

8.2.1 创建表(create table)

8.2.2 修改表 (alter table)

8.2.3 删除表 (drop table)

8.2.4 索引

8.2.5 视图

8.3 数据操作

8.3.1 查询语句格式

8.3.2 分组查询

8.3.3其他操作

8.3.4约束

8.4 数据授权

8.4.1 授权grant

8.4.2 收回权限revoke

8.5 触发器

8.6 嵌入式SQL

第九章 非关系型数据库NOSQL

9.1 概述

9.2 理论基础

9.3 分区方法

9.4 存储分布

9.5查询模型

9.6 存储模式

第十章 系统开发与运行

10.1 系统实施

10.1.1 信息系统生命周期

10.1.2 能力成熟度模型

10.1.3 软件过程开发模型

10.1.4 信息系统开发方法

10.1.5 系统分析与设计

10.1.6 结构化开发

10.2 系统测试

10.2.1 测试原则和方法

10.2.2 测试阶段

10.2.3 测试用例设计

10.2.4 调试

10.2.5 软件度量

10.3 系统维护

10.3.1 系统转换

10.3.2系统维护

10.3.3系统评价

10.4面向对象开发

第十一章 数据库设计

11.1 数据库设计概述

11.2 系统需求分析

11.3 概念结构设计

11.4 逻辑结构设计

11.5 物理结构设计

11.6 实施阶段

11.7 运行与维护

11.7.1 数据库系统的运行

11.7.2 数据库系统的维护

11.7.3 数据库系统的管理

11.7.4 性能调整

第十二章 事务管理

12.1 事务的基本概念

12.2 数据库的并发控制

12.3 数据库的故障与恢复

12.3.1 事务故障

12.3.2 系统故障

12.3.3介质故障

12.3.4数据库备份

12.4 数据库的安全性与完整性

第十三章 云计算与大数据处理

13.1 云计算

13.1.1 云计算的关键特征

13.1.2 云计算分类

13.1.3 云关键技术

13.1.4 云计算的安全

13.1.5 云安全实施的步骤

13.2 大数据

第十四章 数据库主流应用技术

14.1 分布式数据库

14.2 Web与数据库

14.3 XML与数据库

14.4 面向对象数据库

14.5 大数据与数据库

14.6 NewSQL

第十五章 知识产权和标准化

15.1 知识产权概述

15.2 保护期限

15.3 知识产权人的确定

15.4 侵权判断

15.5 标准划分

前言：

笔记来自《文老师软考数据库》教材精讲，精讲视频在b站，某宝都可以找到，个人感觉通俗易懂。

第一章计算机系统基本知识

1.1 计算机系统

1.1.1 计算机硬件组成

  • 计算机的基本硬件系统由运算器控制器、存储器、输入设备和输出设备5 大部件组成。
  • 运算器、控制器等部件被集成在一起统称为中央处理单元(Central Processing Unit，CPU)。CPU是硬件系统的核心，用于数据的加工处理，能完成各种算术逻辑运算及控制功能。
  • 存储器是计算机系统中的记忆设备，分为内部存储器和外部存储器。前者速容量小，一般用于临时存放程序、数据及中间结果。而后者容量大、速度高、度慢，可以长期保存程序和数据。
  • (简称外设)，输入设备用于输入原始输入设备和输出设备合称为外部设备数据及各种命令，而输出设备则用于输出计算机运行的结果。

1.1.2 中央处理单元

【CPU的功能】

  1. 程序控制。CPU通过执行指令来控制程序的执行顺序，这是PU的重要功能。
  2. 操作控制。一条指令功能的实现需要若干操作信号配合来完成，CPU产生每条指令的操作信号并将操作信号送往对应的部件，控制相应的部件按指令的功能要求进行操作。
  3. 时间控制。CPU对各种操作进行时间上的控制，即指令执行过程中操作信号的出现时间、持续时间及出现的时间顺序都需要进行严格控制。
  4. 数据处理。CPU通过对数据进行算术运算及逻辑运算等方进行加工处理，数据加工处理的结果被人们所利用。所以，对数据的加工处理也是CPU最根本的任务。

此外，CPU 还需要对系统内部和外部的中断(异常)做出响应，进行相应的处理。

【CPU的组成】
CPU 主要由运算器、控制器寄存器组和内部总线等部件组成。

  • 运算器：执行所有的算术运算，如加减乘除等，执行所有的逻辑运算并进行逻辑测试，如与、或、非、比较等。由以下组件组成：
    1.算术逻辑单元ALU ：实现对数据的算术和逻辑运算；
    2.累加寄存器AC ：运算结果或源操作数的存放区；
    3.数据缓冲寄存器DR：暂时存放内存的指令或数据；
    4.状态条件寄存器PSW：保存指令运行结果的条件码内容，如溢出标志等。
  • 控制器：控制整个CPU的工作，最为重要。由以下组件组成：
    1.指令寄存器IR：暂存CPU执行指令；
    2.程序计数器PC：存放指令执行地址；
    3.地址寄存器AR：保存当前CPU所访问的内存地址；
    4.指令译码器ID：分析指令操作码。
  • CPU依据指令周期的不同阶段来区分二进制的指令和数据，因为在指令周期的不同阶段，指令会命令CPU分别去取指令或者数据。

1.1.3 数据表示

  1. 进制的表示:二进制、十六进制，一般在题目中会给出中文说明，如果没给出，注意二进制符号为0b，一般表示为0b0011，十六进制符号为0x或H，可表示为0x18F或18FH。(十六进制可表示0-15，其中10-15用A-F来表示)
  2. R进制整数转十进制:位权展开法，用R进制数的每一位乘以R的n次方，n是变量，从R进制数的整数最低世并婚农次为0,1,2,3..累加。
  3. 例如有6进制数5043，此时R=6，用6进制数的每一位乘以6的n次方，n是变量从6进制数的整数最低位开始(5043从低位到高位排列:3,4,0,5)，n依次为0,1,2,3，那么最终5043=3*6^0+4*6A1+0*6A2+5*6A3=1107。
  4. 十进制转R进制:十进制整数 (除以R倒取余数)用十进制整数除以R，记录每次所得余数，若商不为0，则继续除以R，直至商为0，而后将所有余数从下至上记录，排列成从左至右顺序，即为转换后的R进制数:
  5. 例:有十进制数200，转换为5进制，此时R=6，将200/6,,得商为33s余数为2;因为商不等于0，因此再将商33/6，得商为5，余数为3;再将5/6，得商为0，余数为5;此时商为0，将所有余数从下到上记录，得532。
  6. m进制转n进制:先将m进制转化为十进制数，再将十进制数转化为n进制数中间需要通过十进制中转，但下面两种进制间可以直接转化:
    1. 二进制转八进制：每三位二进制数转换为一位八进制数，二进制数位个数不是三的倍数，则在前面补0(原则是数值不变)，如二进制数01101有五位，前面补一个0就有六位，为001101，每三位转换为一位八进制数，001=1101=1+4=5，也即01101=15
    2. 二进制转十六进制：每四位二进制数转换为一位十六进制数，二进制数位个数不是四的倍数，则在前面补0，如二进制数101101有六位，前面补两个0就有八位，为00101101，每四位转换为一位十六进制数，0010=2,1101=13=D，也即101101=2D。
  7. 机器数：各种数值在计算机中表示的形式，其特点是使用二进制计数制，数的符号用0和1表示，小数点则隐含，不占位置。机器数有无符号数和带符号数之分。无符号数表示正数，没有符号位。带符号数最高位为符号位，正数符号位为0，负数符号位为1。
  8. 定点表示法分为纯小数和纯整数两种，其中小数点不占存储位，而是按照以下约定:
    纯小数:约定小数点的位置在机器数的最高数值位之前。
    纯整数:约定小数点的位置在机器数的最低数值位之后。
    真值:机器数对应的实际数值。

【带符号数有下列编码方式，当真值为-45时】

  • 原码:一个数的正常二进制表示最高位表示符号，数值0的源码有两种形式+0(00000000)和-0(10000000)。-45对应原码为10101101
  • 反码:正数的反码即原码;负数的反码是在原码的基础上，各位按位取反。数值0的反码也有两种形式:+0 (00000000)，-0 (11111111)。-45对应反码为11010010
  • 补码:正数的补码即原码，负数的补码是在原码的基础上，除符号位外，其他各位按位取反，而后末位+1，若有进位则产生进位。因此数值0的补码只有一种形式+0=-0=00000000。-45对应补码为11010011
  • 移码:用作浮点运算的阶码，无论正数负数，都是将该原码的补码的首位 (符号位)取反得到移码。-45对应移码为01010011

【浮点数的表示】

  • 浮点数:表示方法为N=F*2E，其中E称为阶码，F称为尾数;类似于十进制的科学计数法，如85.125=085125*10^2，二进制如101.011=0.101011*2A3.
  • 在浮点数的表示中，阶码为带符号的纯整数，尾数为带符号的纯小数，要注意符号占最高位(正数0负数1)，其表示格式如下:
    阶符阶码数符尾数

    很明显，与科学计数法类似个浮点数的表示方法不是唯一的，浮点数所能表示的数值范围由阶码确定，所表示的数值精度由尾数确定

  • 尾数的表示采用规格化方法，也即带符号尾数的补码必须为1.0xxxx(或者0.1xxxx(正数)，其中x可为0或1。
    浮点数的运算:对阶(使两个数的阶码相同，小阶向大阶看齐，较小阶码增加几位，尾数就右移几位)。
    尾数计算(相加，若是减运算则加负数)结果规格化(即尾数表示规格化，带符号尾数转换为1.0xxxx或0.1xxxx)。

1.1.4 校验码

  • 码距:就单个编码A:00而言，其码距为1，因为其只需要改变一位就变成另一个编码。在两个编码中，从A码到B码转换所需要改变的位数称为码距，如A:00要转换为B:11，码距为2。一般来说，码距越大，越利于纠错和检错
  • 奇偶校验码:在编码中增加1位校验位来使编码中1的个数为奇数 (奇校验或者偶数 (偶校验)，从而使码距变为2。例如:
    ○ 发送给接收方，接收方收到后，会计算收到的奇校验:编码中，含有奇数个1，编码有多少个1，如果是奇数个，则无误，是偶数个，则有误。
    ○ 偶校验同理，只是编码中有偶数个1，由上述，奇偶校验只能检1位错，并且无法纠错。

【CRC校验码】

  • CRC只能检错，不能纠错。使用CRC 编码，需要先约定一个生成多项式G(x)生成多项式的最高位和最低位必须是1。假设原始信息有m位，则对应多项式M(x)。生成校验码思想就是在原始信息位后追加若干校验位，使得追加的信息能被G(x)整除。接收方接收到带校验位的信息，然后用G(x)整除。余数为0，则没有错误;反之则发生错误。
  • 例:假设原始信息串为10110，CRC的生成多项式为G(x)=x^4+x+1，求CRC校验码
    （1）在原始信息位后面添0，假设生成多项式的阶为r，则在原始信息位后添加r个0，本题中，G(x)阶为4，则在原始信息串后加4个0，得到的新串为101100000作为被除数。
    （2）由多项式得到除数，多项中x的幂指数存在的位置1，不存在的位置0。本题中，x的幂指数为0,1,4的变量都存在，而幂指数为2,3的不存在，因此得到串10011
    （3）生成CRC校验码，将前两步得出的被除数和除数进行模2除法运算 (即不进位也不借位的除法运算)。得到余数1111（注意:余数不足r，则余数左边用若千个0 补齐。如求得余数为11，r=4，则补两个0得到0011）。
    （4）生成最终发送信息串，将余数添加到原始信息后。上例中，原始信息为410110，添加余数1111后，结果为10110 1111。发送方将此数据发送给接收方
    （5）接收方进行校验。接收方的CRC 校验过程与生成过程类似，接收方接收了带校验和的帧后，用多项式G(x)来除。余数为0，则表示信息无错，否则要求发送方进行重传。注意:收发信息双方需使用相同的生成多项式

【海明码】

  • 海明码:本质也是利用奇偶性来错和纠错的检验方法，构成方法是在数据位之间的确定位置上插入k个校验位，通过扩大码距实现检错和纠错设数据位是n位，校验位是k位，则n和k必须满足以下关系: 。
  • 例:求信息1011的海明码
    （1）校验位的位数和具体的数据位的位数之间的关系所有位都编号，从最低位编号，从1开始递增，校验位处于2的n (n=0 1 2…..)次方中，即处于第1,2,4,8,16,32，…..位上，其余位才能填充真正的数据位，若信息数据为1011，则可知，第1,2,4位为校验位，第3,5,6,7位为数据位，用来从低位开始存放1011，得出信息位和校验位分布如下:

  • （2）计算校验码
    如下图所示
    将所有信息位的编号都拆分成二进制表示

上图中，7=4+2+1，表示7由第4位校验位(r2)和第2位校验位(r1)和第1位校验位(r0)共同校验同理，第6位数据位6=4+2，第5位数据位5=4+1，第3位数据位3=2+1前面知道，这些2的n次方都是校验位，可知，第4位校验位校验第765三位数据位，因此，第4位校验位r2等于这三位数据位的值异或，第2位和第1位校验位计算原理同上
计算出三个校验位后，可知最终要发送的海明校验码为1010101。
（3）检错和纠错原理
接收方收到海明码之后，会将每位校验位与某校验的位数分别异或，即做如下三组运算:

如果是偶校验，那么运算得到的结果应该全为0，如果是奇校验，应该全为1,才是正确，假设是偶校验，且接收到的数据为1011101 (第四位出错)，此时运算的结果为:

这里不全为0，表明传输过程有误，并且按照r2r1r0排列为二进制100，这里指出的就是错误的位数，表示第100，即第4位出错，找到了出错位，纠错方法就是将该位逆转。

1.2 计算机体系结构

1.2.1 体系结构分类

  • 按处理机的数量进行分类: 单处理系统(一个处理单元和其他设备集成)、并行处理系统(两个以上的处理机互联)分布式处理系统(物理上远距离且松合的多计算机系统)
  • Flynn分类法:分类有两个因素，即指令流和数据流，指令流由控制部分处理，每一个控制部分处理一条指令流，多指令流就有多个控制部分;数据流由处理器来处理，每一个处理器处理一条数据流，多数据流就有多个处理器;至于主存模块，是用来存储的，存储指令流或者数据流，因此，无论是多指令流还是多数据流，都需要多个主存模块来存储，对于主存模块，指令和数据都一样。
  • 依据计算机特性，是由指今来控制数据的传输，因此，一条指令可以控制一条或多条数据流，但一条数据流不能被多条指令控制，否则会出错，就如同上级命令太多还互相冲突不知道该执行哪个，因此多指今单数据MISD不可能

1.2.2指令系统存

  • 计算机指令的组成:一条指令由操作码和操作数两部分组成，操作码决定要完成的操作，操作数指参加运算的数据及其所在的单元地址在计算机中，操作要求和操作数地址都由二进制数码表示，分别称作操作码和地址码，整条指令以二进制编码的形式存放在存储器中。
  • 计算机指令执行过程:取指令–分析指令–执行指令三个步骤，首先将程序计数器PC中的指令地址取出，送入地址总线，CPU依据指令地址去内存中取出指令内容存入指令寄存器IR;而后由指令译码器进行分析，分析指令操作码;最后执行指令，取出指令执行所需的源操作数。

【指令寻址方式】
顺序寻址方式：当执行一段程序时，是一条指令接着一条指令地顺序执行；
跳跃寻址方式：指下一条指令的地址码不是由程序计数器给出，而是由本条指令直接给出，程序跳跌后，按新的指令地址开始顺序执行。因此，程序计数器的内容也必须相应改变，以便及时跟踪新的指令地址。

【指令操作数的寻址方式】

  1. 立即寻址方式：指令的地址码字段指出的不是地址，而是操作数本身；
  2. 直接寻址方式：在指令的地址字段中直接指出操作数在主存中的地址；
  3. 间接寻址方式：指令地址码字段所指向的存储单元中存储的是操作数的地址；
  4. 寄存器寻址方式：指令中的地址码是寄存器的编号；
  5. 基址寻址方式：将基址寄存器的内容加上指令中的形式地址而形成操作数的有效地址，其优点是可以扩大寻址能力；
  6. 变址寻址方式：变址寻址方式计算有效地址的方法与基址寻址方式很相似，它是将变址寄存器的内容加上指令中的形式地址而形成操作数的有效地址。

【复杂指令系统和精简指令系统】
CISC是复杂指令系统兼容性强，指令繁多、长度可变，由微程序实现；
RISC是精简指令系统，指令少，使用频率接近，主要依靠硬件实现(通用寄存器，硬布线逻辑控制)

【指令系统-流水线】

指令流水线原理: 将指令分成不同段，每段由不同的部分去处理，因此可以产生叠加的效果，所有的部件去处理指令的不同段。

RISC中的流水线技术
（1）超流水线 (Super Pipe Line) 技术。它通过细化流水、增加级数和提高主频，使得在每个机器周期内能完成一个甚至两个浮点操作。其实质是以时间换取空间
（2） 超标量 (Super Scalar) 技术。它通过内装多条流水线来同时执行多个处理，其时钟频率虽然与一股流水接dw更小的CPI。其实质是以空间换取时间
（3）超长指令字 (Very Long Instruction Word，VLIW) 技术VLIW和超标量都是20世纪8年代出现的概念，其共同点是要同时执行多条指令，其不同在于超标量依靠硬件来实现并行处理的调度，VLIW 则充分发挥软件的作用，而使硬件简化性能提高。

【流水线时间计算】
流水线周期：指令分成不同执行段，其中执行时间最长的段为流水线周期。
流水线执行时间：1条指令总执行时间+ (总指令条数-1)*流水线周期。
流水线吞吐率计算：吞吐率即单位时间内执行的指令条数公式：指令条数/流水线执行时间。
流水线的加速比计算：加速比即使用流水线后的效率提升度，即比不使用流水线快了多少倍，越高表明流水线效率越高，公式:不使用流水线执行时间/使用流水线执行时间

1.2.3储系系统

  • 计算机采用分级存储体系的主要目的是为了解决存储容量、成本和速度之间的矛盾问题。
  • 两级存储:Cache-主存、主存-辅存(虚拟存储体系)。
  • 局部性原理:总的来说，在CPU运行时，所访问的数据会趋向于一个较小的局部空间地址内，包括下面两个方面：
    （1）时间局部性原理:如果一个数据项正在被访问，那么在近期它很可能会被再次访问，即在相邻的时间里会访问同一个数据项。
    （2）空间局部性原理:在最近的将来会用到的数据的地址和现在正在访问的数据地址很可能是相近的，即相邻的空间地址会被连续访问。

  • 高速缓存Cache用来存储当前最活跃的程序和数据，直接与CPU交互，位于CPU由半导体材料构成。其内容是主存和主存之间，容量小，速度为内存的5-10倍内存的副本拷贝，对于程序员来说是透明的。
  • Cache由控制部分和存储器组成，存储器存储数据，控制部分判断CPU要访问的数据是否在cache中，在则命中，不在则依据一定的算法从主存中替换。
  • 地址映射: 在CPU工作时，送出的是主存单元的地址，而应从Cache存储器中读/写信息。这就需要将主存地址转换为Cache存储器地址，这种地址的转换称为地址映像，由硬件自动完成映射，分为下列三种方法:
    （1）直接映像：将Cache存储器等分成块，主存也等分成块并编号。主存中的块与Cache中的块的对应关系是固定的，也即二者块号相同才能命中。地址变换简单但不灵活，容易造成资源浪费。
    （2）全相联映像：同样都等分成块并编号。主存中任意一块都与Cache中任意一块对应。因此可以随意调入Cache任意位置，但地址变换复杂，速度较慢。因为主存可以随意调入Cache任意块，只有当Cache满了才会发生块冲突，是最不容易发生块冲突的映像方式。
    （3）组组相连映像：前面两种方式的结合，将Cache存储器先分块再分组，主存也同样先分块再分组，组间采用直接映像，即主存中组号与Cache中组号相同的组才能命中，但是组内全相联映像，也即组号相同的两个组内的所有块可以任意调换。

【磁盘结构和参数】

  • 磁盘有正反两个盘面，每个盘面有多个同心圆每个同心圆是一个磁道，每个同心圆又被划分为多个扇区，数据就被存放在一个个扇区中。
  • 磁头首先要寻找到对应的磁道，然后等待磁盘进行周期旋转，旋转到指定的扇区，才能读取到对应的数据，因此，会产生寻道时间和等待时间。公式为:存取时间=寻道时间+等待时间(平均定位时间+转动延迟)。
  • 注意:寻道时间是指磁头移动到磁道所需的时间，等待时间为等待读写的扇区转到磁头下方所用的时间。

1.2.4输入/输出技术

计算机系统中存在多种内存与接口地址的编址方法，常见的是下面两种：
（1）内存与接口地址独立编址方法内存地址和接口地址是完全独立的两个地址空间。访问数据时所使用的指令也完全不同，用于接口的指令只用于接口的读/写，其余的指令全都是用于内存的因此，在编程序或读程序时很易使用和辨认。这种编址方法的缺点是用于接口的指令太少、功能太弱。
（2）内存与接口地址统一编址方法内存地址和接口地址统一在一个公共的地址空间里，即内存单元和接口共用地址空间。优点是原则上用于内存的指令全都可以用于接口，这就大大地增强了对接口的操作功能，而且在指令上也不再区分内存或接口指令。该编址方法的缺点就在于整个地址空间被分成两部分，其中一部分分配给接口使用，剩余的为内存所用，这经常会导致内存地址不连续。

计算机和外设间的数据交互方式：
（1）程序控制(查询)方式：CPU主动查询外设是否完成数据传输，效率极低。
（2）程序中断方式：外设完成数据传输后，向CPU发送中断，等待CPU处理数据效率相对较高。中断响应时间指的是从发出中断请求到开始进入中断处理程序中断处理时间指的是从中断处理开始到中断处理结束。中断向量提供中断服务程序的入口地址。多级中断嵌套，使用堆栈来保护断点和现场。
（3）DMA方式(直接主存存取)：CPU只需完成必要的初始化等操作，数据传输的整个过程都由DMA控制器来完成，在主存和外设之间建立直接的数据通路效率很高。

  • 在一个总线周期结束后，CPU会响应DMA请求开始读取数据;CPU响应程序中断方式请求是在一条指令执行结束时。

1.2.5总线结构

  • 总线(Bus)是指计算机设备和设备之间传输信息的公共数据通道。总线是连接计算机硬件系统内多种设备的通信线路，它的一个重要特征是由总线上的所有设备共享，因此可以将计算机系统内的多种设备连接到总线上。
  • 从广义上讲，任何连接两个以上电子元器件的导线都可以称为总线，通常分为以下三类：
    （1）内部总线：内部芯片级别的总线，芯片与处理器之间通信的总线。
    （2）系统总线：是板级总线，用于计算机内各部分之间的连接，具体分为数据总线(并行数据传输位数)、地址总线 (系统可管理的内存空间的大小) 、控制总线(传送控制命令)。代表的有ISA总线、EISA总线、PCI总线。
    （3）外部总线：设备一级的总线，微机和外部设备的总线。代表的有RS232(串行总线)、SCSI(并行总线)、USB (通用串行总线，即插即用，支持热插拔)。

1.3 可靠性、性能、安全

1.3.1 计算机可靠性

【串并联系统可靠性】
无论什么系统，都是由多个设备组成的协同工作，而这多个设备的组合方式可以是串联、并联，也可以是混合模式，假设每个设备的可靠性为R1，R2……Rn则不同的系统的可靠性公式如下：
（1）串联系统，一个设备不可靠，整个系统崩溃，整个系统可靠性R=R1*R2*…* Rn。

（2）并联系统，所有设备都不可靠，整个系统才崩溃，整个系统可靠性R=1-(1-R1)
*(1-R2) * …*(1-Rn)。

1.3.2计算机系统的性能评价

  • 【性能评测的常用方法】
    （1）时钟频率。一般来讲，主频越高，速度越快。
    （2）指令执行速度。计量单位KIPS、MIPS。
    （3）等效指令速度法。统计各类指令在程序中所占比例，并进行折算，是一种固定比例法。
    （4）数据处理速率 (Processing Data Rate，PDR)法。采用计算PDR 值的方法来衡量机器性能，PDR值越大，机器性能越好。PDR与每条指令和每个操作数的平均位数以及每条指令的平均运算速度有关。
    （5）核心程序法。把应用程序中用得最频繁的那部分核心程序作为评价计算机性能的标准程序，在不同的机器上运行，测得其执行时间，作为各类机器性能评价的依据。
  • 【基准程序法】
    基准程序法是目前被用户一致承认的测试性能的较好方法，有(Benchmark)多种多样的基准程序，包括：
    （1）整数测试程序。同一厂家的机器，采用相同的体系结构，用相同的基准程序测试，得到的MIPS 值越大，一般说明机器速度越快。
    （2）浮点测试程序。指标MFLOPS(理论峰值浮点速度)。
    （3）SPEC基准程序(SPEC Benchmark)。重点面向处理器性能的基准程序集将被测计算机的执行时间标准化，即将被测计算机的执行时间除以一个参考处理器的执行时间。
    （4）TPC基准程序。用于评测计算机在事务处理、数据库处理、企业管理与决策支持系统等方面的性能。其中，TPC-C是在线事务处理(On-lineTransactionProcessing，OLTP)的基准程序，TPC-D是决策支持的基准程序。TPC-E作为大型企业信息服务的基准程序。

1.3.3信息安全

  • 信息安全含义及属性：保护信息的保密性、完整性、可用性，另外也包括其他属性，如：真实性、可核查性、不可抵赖性和可靠性。
  • 保密性:信息不被泄漏给未授权的个人、实体和过程或不被其使用的特性包括：
    （1）最小授权原则
    （2）防暴露
    （3）信息加密
    （4）物理保密
  • 完整性:信息未经授权不能改变的特性。影响完整性的主要因素有设备故障误码、人为攻击和计算机病毒等。保证完整性的方法包括：
    （1）协议：通过安全协议检测出被删除、失效、被修改的字段。
    （2）纠错编码方法：利用校验码完成检错和纠错功能。
    （3）密码校验和方法。
    （4）数字签名：能识别出发送方来源。
    （5）公证：请求系统管理或中介机构证明信息的真实性。
  • 可用性:需要时，授权实体可以访问和使用的特性。一般用系统正常使用时间和整个工作时间之比来度量。
  • 其他属性：
    • 真实性：指对信息的来源进行判断，能对伪造来源的信息予以鉴别。
    • 可核查性：系统实体的行为可以被独一无二的追溯到该实体的特性，这个特性就是要求该实体对其行为负责，为探测和调查安全违规事件提供了可能性。
    • 不可抵赖性：是指建立有效的责任机制，防止用户否认其行为，这一点在电子商务中是极其重要的。
    • 可靠性：系统在规定的时间和给定的条件下，无故障地完成规定功能的概率
  • 【安全需求】
    可划分为物理线路安全、网络安全、系统安全和应用安全；从各级安全需求字面上也可以理解：
    （1）物理线路就是物理设备如理环境；
    （2）网络安全指网络上的攻击、入侵；
    （3）系统安全指的是操作系统漏洞、补丁等；
    （4）应用安全就是上层的应用软件，包括数据库软件。

【对称加密技术】
数据的加密和解密的密钥 (密码) 是相同的，属于不公开密钥加密算法。其缺点是加密强度不高 (因为密钥位数少)且密钥分发困难 (因为密钥还需要传输给接收方，也要考虑保密性等问题)。优点是加密速度快，适合加密大数据。

  • 常见的对称密钥加密算法如下：
    （1）DES：替换+移位、56位密钥、64位数据块、速度快，密钥易产生；
    （2）3DES:三重DES，两个56位密钥K1、K2。加密：K1加密->K2解密->K1加密，解密:K1解密->K2加密->K1解密；
    （3）AES:是美国联邦政府采用的一种区块加密标准，这个标准用来替代原先的DES.对其的要求是“至少像3DES一样安全”；
    （4）RC-5：RSA数据安全公司的很多产品都使用了RC-5；
    （5）IDEA:128位密钥，64位数据块，比DES的加密性好，对计算机功能要求相对低。

【非对称加密技术】
数据的加密和解密的密钥是不同的，分为公钥和私钥是公开密钥加密算法其缺点是加密速度慢。优点是安全性高，不容易破解。
非对称技术的原理是:发送者发送数据时，使用接收者的公钥作加密密钥私钥作解密密钥，这样只有接收者才能解密密文得到明文。安全性更高，因为无需传输密钥。但无法保证完整性。如下：

  • 常见的非对称加密算法如下RSA：512位(或1024位)密钥，计算机量极大，难破解，Elgamal、ECC(圆曲线算法)、背包算法、Rabin、D-H等。

【对称密钥和非对称密钥的比较】
相比较可知，对称加密算法密钥一般只有56位，因此加密过程简单，适合加密大数据，也因此加密强度不高，而非对称加密算法密钥有1024位，相应的解密计算量庞大，难以破解，却不适合加密大数据，一般用来加密对称算法的密钥，这样，就将两个技术组合使用了，这也是数字信封的原理。

【数字信封原理】
信是对称加密的密钥，数字信封就是对此密钥进行非对称加密，具体过程：发送方将数据用对称密钥加密传输，而将对称密钥用接收方公钥加密发送给对方。接收方收到数字信封，用自己的私钥解密信封，取出对称密钥解密得原文。
数字信封运用了对称加密技术和非对称加密技术，本质是使用对称密钥加密数据，非对称密钥加密对称密钥，解决了对称密钥的传输问题。

【信息摘要】
所谓信息摘要，就是一段数据的特征信息，当数据发生了改变，信息摘要也会发生改变，发送方会将数据和信息摘要一起传给接收方，接收方会根据接收到的数据重新生成一个信息摘要，若此摘要和接收到的摘要相同，则说明数据正确。信息摘要是由哈希函数生成的。
信息摘要的特点：不算数据多长，都会产生固定长度的信息摘要，任何不同的输入数据，都会产生不同的信息摘要，单向性，即只能由数据生成信息摘要不能由信息摘要还原数据。
信息摘要算法：MD5(产生128位的输出)、SHA-1(安全散列算法，产生160位的输出，安全性更高)

【数字签名】
唯一标识一个发送方发送者发送数据时，使用发送者的私钥进行加密，接收者收到数据后，只能使用发送者的公钥进行解密这样就能唯一确定发送方，这也是数字签名的过程但无法保证机密性。如下：

【公钥基础设施PKI】
是以不对称密钥加密技术为基础，以数据机密性、完整性身份认证和行为不可抵赖性为安全目的，来实施和提供安全服务的具有普适性的安全基础设施。
（1）数字证书：一个数据结构，是一种由一个可信任的权威机构签署的信息集合。在不同的应用中有不同的证书。如X.509证书必须包含下列信息：（1）版本号息；（2）序列号；（3）签名算法标识符； （4）认证机构；（5）有效期限；（6）主题信；（7）认证机构的数字签名；（8）公钥信息。
公钥证书主要用于确保公钥及其与用户绑定关系的安全。这个公钥就是证书所标识的那个主体的合法的公钥。任何一个用户只要知道签证机构的公钥，就能检查对证书的签名的合法性。如果检查正确，那么用户就可以相信那个证书所携带的公钥是真实的，而且这个公钥就是证书所标识的那个主体的合法的公钥例如驾照
（2）签证机构CA：负责签发证书、管理和撤销证书。是所有注册用户所信赖的权威机构，CA在给用户签发证书时要加上自己的数字签名，以保证证书信息的真实性。任何机构可以用CA的公钥来验证该证书的合法性。

第二章 程序语言基础知识

2.1 程序设计语言的基本概念

  • 程序设计语言是为了书写计算机程序而人为设计的符号语言，用于对计算过程进行描述、组织和推导。
  • 低级语言：机器语言 (计算机硬件只能识别o和1的指令序列)，汇编语言
  • 高级语言：功能更强，抽象级别更高，与人们使用的自然语言比较接近。
  • 各程序设计语言特点：
    （1）Fortran语言:科学计算，执行效率高
    （2）Pascal语言:为教学开发，表达能力强
    （3）C语言：指针操作能力强，可以开发系统级软件，高效
    （4）C++语言:面向对象，高效。
    （5）Java语言:面向对象，中间代码，跨平台
    （6）C#语言:面向对象，中间代码，.Net框架
    （7）Python是一种面向对象、解释型计算机程序设计语言
    （8）Prolog是逻辑型程序设计语言。
  • 汇编：将汇编语言翻译成目标程序执行。
  • 解释和编译：将高级语言翻译成目标程序执行。不同之处在于：
    （1）编译程序生成独立的可执行文件，直接运行，运行时无法控制源程序，效率高。
    （2）而解释程序不生成可执行文件，可以逐条解释执行，用于调试模式，可以控制源程序，因为还需要控制程序，因此执行速度慢，效率低。
  • 程序设计语言定义三要素:：语法、语义、语用。
    （1）语法是指由程序设计语言的基本符号组成程序中的各个语法成分 (包括程序)的-组规则，其中由基本字符构成的符号 (单词)书写规则称为词法规则，由符号构成语法成分的规则称为语法规则。
    （2）语义是程序设计语言中按语法规则构成的各个语法成分的含义，可分为静态语义和动态语义。静态语义指编译时可以确定的语法成分的含义，而运行时刻才能确定的含义是动态语义。一个程序的执行效果说明了该程序的语义，它取决于构成程序的各个组成部分的语义。
    （3）语用表示了构成语言的各个记号和使用者的关系，涉及符号的来源、使用和影响。
  • 语言的实现则有个语境问题。语境是指理解和实现程序设计语言的环境，包括编译环境和运行环境。
  • 程序设计语言的分类：
    （1）命令式和结构化程序设计语言，包括Fortran、PASCAL和C语言
    （2）面向对象程序设计语言，包括c++、JAVA和Smalltalk语言
    （3）函数式程序设计语言，包括LISP、Haskell、Scala、Scheme、APL等
    （4）逻辑型程序设计语言，包括PROLOG。
  • 程序设计语言的基本成分：
    （1）数据成分：指一种程序设计语言的数据和数据类型。数据分为常量(程序运行全局量 (存储空间在静态数据时不可改变)、变量(程序运行时可以改变)区分配)、局部量 (存储空间在堆栈区分配)数据类型有整型、字符型、双精度、单精度浮点型、布尔型等。
    （2）运算成分：指明允许使用的运算符号及运算规则。包括算术运算、逻辑运算关系运算、位运算等。
    （3）控制成分：指明语言允许表述的控制结构。包括顺序结构、选择结构、构。
    （4）传输成分：指明语言允许的数据传输方式。如赋值处理、数据的输入输出等。

2.2 程序设计语言的基本成分

  • 函数：C程序由一个或多个函数组成，每个函数都有一个名字，其中有且仅有个名字为main的函数作为程序运行时的起点。函数的使用涉及3个概念:函娄定义、函数声明和函数调用。
    函数的定义包括两部分:函数首部和函数体。函数的定义描述了函数做什么和怎么做。
  • 函数首部说明了函数返回值的数据类型、函数的名字和函数运行时所需的参数及类型。函数所实现的功能在函数体部分进行描述。
  • 函数应该先声明后引用。如果程序中对一个函数的调用在该函数的定义之前进行，则应该在调用前对被调用函数进行声明。函数原型用于声明函数。函数声明的一般形式为：返回值类型函数名(参数类型表)。
  • 函数调用的一般形式为：函数名(实参表)
  • 函数调用时实参与形参间交换信息的方法有值调用和用调用两种
    （1）值调用 (Call by Value) ：若实现函数调用时将实参的值传递给相应的形参，则称为是传值调用。在这种方式下形参不能向实参传递信息。在C语言中，要实现被调用函数对实参的修改，必须用指针作为参数。即调用时需要先对实参进行取地址运算，然后将实参的地址传递给指针形参。其本质上仍属于值调用。这种方式实现了间接内存访问。
    （2）引用调用 (Call by Reference)：引用是C++中引入的概念，当形式参数为引用类型时，形参名实际上是实参的别名，函数中对形参的访问和修改实际上就是针对相应实参所做的访问和改变。

2.3 编译程序基本原理

  • 编译程序对高级语言源程序进行编译的过程中，要不断收集、记录和使用源程序中一些相关符号的类型和特征等信息，并将其存入符号表中，编译过程如下：
    （1）词法分析:是编译过程的第一个阶段。这个阶段的任务是从左到右一个字符一个字符地读入源程序，即对构成源程序的字符流进行扫描然后根据构词规则识别单词(也称单词符号或符号)。
    （2）语法分析:是编译过程的一个逻辑阶段。语法分析的任务是在词法分析的基础上将单词序列组合成各类语法短语，如“程序”，“语句”，“表达式”等等语法分析程序判断源程序在结构上是否正确。
    （3）语义分析:是编译过程的一个逻辑阶段语义分析的任务是对结构上正确的源程序进行上下文有关性质的审查,进行类型审查。如类型匹配、除法除数不为0等。又分为静态语义错误 (在编译阶段能够查找出来)和动态语义错误 (只能在运行时发现)。

  • 中间代码和目标代码:中间代码是根据语义分析产生的，需要经过优化链接最终生成可执行的自标代码。引入中间代码的目的是进行与机器无关的代码优化处理。常用的中间代码有后缀式(逆波兰式)三元式(三地址码)、四元式和树等形式。需要考虑三个问题(一是如何生成较短的目标代码;二是如何充分利用计算机中的寄存器，减少目标代码访问存储单元的次数;三是如何充分利用计算机指令系统的特点，以提高目标代码的质量)
  • 前缀表达式：+ab
  • 中缀表达式：a+b
  • 后缀表达式：ab+
  • 主要掌握上述三种表达式即可，其实就是树的三种遍历，一般正常的表达式是中席遍历，即中缀表达式，根据其构造出树，再按题目要求求出前缀或后缀式。
  • 简单求法：后缀表达式是从左到右开始，先把表达式加上括号，再依次把运算符加到本层次的括号后面。

第三章 数据结构与算法

3.1 数据结构

3.1.1 线性结构

  • 线性结构：每个元素最多只有一个出度和一个入度，表现为一条线状。线性表按存储方式分为顺序表和链表。
  • 存储结构：
    • 顺序存储：用一组地址连续的存储单元依次存储线性表中的数据元素，使得逻辑上相邻的元素物理上也相邻。
    • 链式存储：存储各数据元素的结点的地址并不要求是连续的，数据元素逻辑上相邻，物理上分开。

顺序存储和链式存储的对比如下图所示

（1）在空间方面：因为链表还需要存储指针，因此有空间浪费存在。
（2）在时间方面，当需要对元素进行破坏性操作 (插入、删除) 时，链表效率更高，因为其只需要修改指针指向即可，而顺序表因为地址是连续的，当删除或插入一个元素后，后面的其他节点位置都需要变动。
（3）而当需要对元素进行不改变结构操作时(读取、查找)，顺序表效率更高因为其物理地址是连续的，如同数组一般只需按索引号就可快速定位，而链表需要从头节点开始，一个个的查找下去。

  • 栈和队列队列、栈结构如下图，队列是先进先出，分队头和队尾栈是先进后出，只有栈顶能进出。
  • 循环队列
    设循环队列Q的容量为MAXSIZE，初始时队列为空，且Qrear和Qfront都等于0；元素入队时修改队尾指针，即令Qrear=(Q.rear+1)%MAXSIZE；元素出队时修改队头指针，即令Qfront==(Qfront+1)%MAXSIZE
  • 根据队列操作的定义，当出队操作导致队列变为空时，有Qrear==Qfront;若入队操作导致队列满，则Qrear==Qfront。
  • 在队列空和队列满的情况下，循环队列的队头、队尾指针指向的位置是相同的，此时仅仅根据Qrear和Qfront 之间的关系无法断定队列的状态。为了区别队空和队满的情况，可采用以下两种处理方式:其一是设置一个标志，以区别头、尾指针的值相同时队列是空还是满;其二是牺牲一个存储单元，约定以“队列的尾指针所指位置的下一个位置是队头指针时”表示队列满。
  • 字符串是一种特殊的线性表，其数据元素都为字符。
    • 空串：长度为0的字符串，没有任何字符。
    • 空格串：由一个或多个空格组成的串，空格是空白字符，占一个字符长度。
    • 子串:串中任意长度的连续字符构成的序列称为子串。含有子串的串称为主串，空串是任意串的子串。
    • 串的模式匹配:子串的定位操作，用于查找子串在主串中第一次出现的位置的算法。

【模式匹配算法】

  • 朴素的模式匹配算法：也称为布鲁特一福斯算法，其基本思想是从主串的第1个字符起与模式串的第1个字符比较，若相等，则继续逐个字符进行后续的比较否则从主串中的第2个字符起与模式串的第1个字符重新比较，直至模式串中每个字符依次和主串中的一个连续的字符序列相等时为止，此时称为匹配成功，否则称为匹配失败。

3.1.2 数组

  • 数组是定长线性表在维度上的扩展，即线性表中的元素又是一个线性表。N维数组是一种“同构”的数据结构，其每个数据元素类型相同、结构一致。
  • 其可以表示为行向量形式或者列向量形式线性表，单个关系最多只有一个前驱和一个后继，本质还是线性的。
  • 数组结构的特点：数据元素数目固定，数据元素类型相同;数据元素的下标关系具有上下界的约束且下标有序数
  • 组数据元素固定，一般不做插入和删除运算，适合于采用顺序结构
  • 数组存储地址的计算，特别是二维数组，要注意理解，假设每个数组元素占用存储长度为len，起始地址为a，存储地址计算如下(默认从0开始编号)

3.1.3 矩阵

  • 特殊矩阵:矩阵中的元素(或非0元素)的分布有定的规律。常见的特殊矩阵有对称矩阵、三角矩阵和对角矩阵
  • 稀疏矩阵:在一个矩阵中，若非零元素的个数远远少于零元素个数，且非零元素的分布没有规律。
  • 存储方式为三元组结构，即存储每个非零元素的(行列，值)。

3.1.4树与二叉树

  • 树是n个节点的有限集合(n>=0)当n=0时称为空树，在任一颗非空树中，有且仅有-个根节点。其余结点可分为m(m20)个互不相交的有限子集T1，T2，Tm，其中，每个Ti…又都是一棵树，并且称为根结点的子树。
  • 树的基本概念如下：
    （1）双亲、孩子和兄弟。结点的子树的根称为该结点的孩子，相应地，该结点称为其子结点的双亲。。具有相同双亲的结点互为兄弟。
    （2）结点的度。一个结点的子树的个数记为该结点的度。例如A的度为3，B的度为2，C的度为0，D的度为1。
    （3）叶子结点。叶子结点也称为终端结点，指度为0的结点。例如，E、F、c、G都是叶子结点
    （4）内部结点。度不为0的结点，也称为分支结点或非终端结点。除根结点以外，分支结点也称为内部结点。例如，B、D都是内部结点。
    （5）结点的层次。根为第一层，根的孩子为第二层，依此类推，若某结点在第i层，则其孩子结点在第i+1层。例如，A在第1层，B、C、D在第2层，E、F和G在第3 层。
    （6）树的高度。一棵树的最大层数记为树的高度(或深度)。例如，图中所示树的高度为3
    （7）有序(无序)树。若将树中结点的各子树看成是从左到右具有次序的，即不能交换则称该树为有序树，否则称为无序树。

  • 二叉树是n个节点的有限集合，它或者是空树或者是由一个根节点及两颗互不相交的且分别称为左有子村的一又村村所组成。

  • 二叉树有一些性质如下，要求掌握，在实际考试中可以用特殊值法验证。
    （1）二叉树第i层 (i>=1) 上至多有2^(i-1)个节点。
    （2）深度为k的二叉树至多有2^k – 1个节点(k>=1)
    （3）对任何一棵二叉树，若其终端节点数为n0，度为2 的节点数为n2，则n0=n2 + 1。
    此公式可以画一个简单的二叉树使用特殊值法快速验证，也可以证明如下设一棵二叉树上叶结点数为no，单分支结点数为n,，双分支结点数为n，则总结点数=n,+ni+n2。在一棵二叉树中，所有结点的分支数(即度数)应等于单分支结点数加上双分支结点数的2倍，即总的分支数=n,+2n。由于二叉树中除根结点以外每个结点都有唯一的一个分支指向它，因此二叉树中:总的分支数=总结点数-1。
    （4）具有n 个节点的完全二叉树的深度为|log2 nl+ 1
  • 二叉树的顺序存储结构：
    顺序存储，就是用一组连续的存储单元存储二叉树中的节点，按照从上到下从左到右的顺序依次存储每个节点。
  • 对于深度为k的完全二叉树，除第k层外，其余每层中节点数都是上一层的两倍，由此，从一个节点的编号可推知其双亲、左孩子、右孩子结点的编号。假设有编号为的节点，则有：
    （1）若i=1，则该节点为根节点，无双亲;
    （2）若i>1，则该节点的双亲节点为i/2。
    （3）若2i<=n，则该节点的左孩子编号为2i，否则无左孩子。
    （4）若2i + 1<=n，则该节点的右孩子编号为2i+1，否则无右孩子
  • 显然，顺序存储结构对完全二叉树而言既简单又节省空间，而对于一般二叉树则不适用。因为在顺序存储结构中，以节点在存储单元中的位置来表示节点之间的关系，那么对于一般的二叉树来说，也必须按照完全二叉树的形式存储也就是要添上一些实际并不存在的“虚节点”，这将造成空间的浪费。
  • 二叉树的链式存储结构：
    由于二叉树中节点包含有数据元素、左子树根、右子树根及双亲等信息，因此可以用三叉链表或二叉链表(即一个节点含有三个指针或两个指针)来存储二叉树，链表的头指针指向二叉树的根节点
  • 一颗非空的二叉树由根节点、左子树、右子树三部分组成，遍历这三部分也就遍历了整颗二叉树。这三部分遍历的基本顺序是先左子树后右子树，但根节点顺序可变，以根节点访问的顺序为准有下列三种遍历方式：
    先序 (前序) 遍历: 根左右
    中序遍历: 左根右
    后序遍历: 左右根
    示例:前序:12457836 中序: 42785136 后序:48752631

  • 层次遍历:按层次，从上到下，从左到右
  • 反向构造二叉树
    仅仅有前序和后序是无法构造二叉树的，必须要是和中序遍历的集合才能反向构造出二叉树。
    构造时，前序和后序遍历可以确定根节点，中序遍历用来确定根节点的左子树节点和右子树节点，而后按此方法进行递归，直至得出结果。
  • 引入线索二叉树是为了保存二叉树遍历时某节点的前驱节点和后继节点的信息，二叉树的链式存储只能获取到某节点的左孩子和右孩子结点，无法获取其遍历时的前驱和后继节点，因此可以在链式存储中再增加两个指针域，使其分别指向前驱和后继节点，但这样太浪费存储空间，考虑下述实现方法：
    （1）若n个节点的二叉树使用二叉链表存储，则必然有n+1个空指针域，利用这些空指针域来存放节点的前驱和后继节点信息，为此，需要增加两个标志，以区分指针域存放的到底是孩子结点还是遍历节点，如下：

    （2）若二又树的二叉链表采用上述结构，则称为线索链表，其中指向前驱、后继节点的指针称为线索，加上线索的二叉树称为线索二叉树。

  • 最优二叉树又称为哈夫曼树，是一类带权路径长度最短的树，相关概念如下路径：
    • 树中一个结点到另一个结点之间的通路
    • 结点的路径长度：路径上的分支数目。
    • 树的路径长度：根节点到达每一个叶子节点之间的路径长度之和。
    • 权：节点代表的值结点的。
    • 带权路径长度：该结点到根结点之间的路径长度乘以该节点的权值
    • 树的带权路径长度(树的代价)：树的所有叶子节点的带权路径长度之和
  • 哈夫曼树的求法: 给出一组权值，将其中两个最小的权值作为叶子节点，其和作为父节点，组成二叉树，而后删除这两个叶子节点权值，并将父节点的值添加到该组权值中。重复进行上述步骤，直至所有权值都被使用完。
  • 若需要构造哈夫曼编码 (要保证左节点值小于右节点的值，才是标准的哈夫曼树)，将标准哈夫曼树的左分支设为0，右分支设为1，写出每个叶节点的编会发现，哈夫曼编码前缀不同，因此不会混淆，同时也是最优编码。
  • 查找二叉树上的每个节点都存储一个值，且每个节点的所有左孩子结点值都小于交节点值，而所有右孩子结点值都大于父节点值，是一个有规律排列的二叉树，这种数据结构可以方便查找、插入等数据操作。
  • 二叉排序树的查找效率取决于二叉排序树的深度，对于结点个数相同的二叉排序树，平衡二叉树的深度最小，而单枝树的深度是最大的，故效率最差
  • 平衡二叉树又称为AVL 树，它或者是一棵空树，或者是具有下列性质的二又树它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度之差的绝对值不超过1。若将二叉树结点的平衡因子 (Balance Factor，BF) 定义为该结点左子树的高度减去其右子树的高度，则平衡二叉树上所有结点的平衡因子只可能是-10和1。只要树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。

3.1.5图

  • 无向图：图的结点之间连接线是没有箭头的，不分方向。
  • 有向图：图的结点之间连接线是箭头，区分A到B，和B到A是两条线。
  • 完全图：无向完全图中，节点两两之间都有连线，n个结点的连线数为(n-1)+(n-2)+…+1= n*(n-1)/2；有完全图5b节点两两之间都有互通的两个箭头，个节点的连线数为n*(n-1)。
  • 度、出度和入度：顶点的度是关联与该顶点的边的数目。在有向图中，顶点的度为出度和入度之和。
  • 路径：存在一条通路，可以从一个顶点到达另一个顶点。
  • 子图：有两个图G=(V, E)和G’=(V’,E)，如果 C VE’C E，则称G为G的子图。
  • 连通图和连通分量：针对无向图。若从顶点v到顶点u之间是有路径的，则说明v和u之间是连通的，若无向图中任意两个顶点之间都是连通的，则称为连通图。无向图G的极大连通子图称为其连通分量。强连通图和强连通分量:针对有向图。若有向图任意两个顶点间都互相存在路径，即存在v到u，也存在u到v的路径，则称为强连通图。有向图中的极大连通子图称为其强连通分量。
  • 网：边带权值的图称为网
  • 图的存储：
    邻接矩阵：假设一个图中有n个节点，!则使用n阶矩阵来存储这个图中各节点的关系，规则是若节点到节点有连线，!则矩阵Ri,j=1，否则为0，示例如下图所示

  • 邻接链表：用到了两个数据结构，先用维数组将图中所有顶点存储起来，而后，对此一维数组的每个顶点元素，使用链表挂上其出度到达的结点的编号和权值，示例如下图所示：

  • 存储特点:图中的顶点数决定了邻接矩阵的阶和邻接表中的单链表数目，边数的多少决定了单链表中的结点数，用邻接矩阵存储。而不影响邻接矩阵的规模，因此采用何种存储方式与有向图、无向图没有区别，要看图的边数和顶点数，完全图适合采用邻接矩阵存储。
  • 图的遍历是指从图的任意节点出发，沿着某条搜索路径对图中所有节点进行访问且只访问一次，分为以下两种方式：
    （1）深度优先遍历：从任一顶点出发，遍历到底，直至返回，再选取任一其他节点出发，重复这个过程直至遍历完整个图；
    （2）广度优先遍历: 先访问完一个顶点的所有邻接顶点，而后再依次访问其邻接顶点的所有邻接顶点，类似于层次遍历。

  • 图的最小生成树假设有n个节点，那么这个图的最小生成树有n-1条边 (不会形成环路，是树非图)，这n-1条边应该会将所有顶点都连接成一个树，并且这些边的权值之和最小，因此称为最小生成树。共有下列两种算法：
    （1）普里姆算法：从任意顶点出发，找出与其邻接的边权值最小的，此时此边的另外一个顶点自动加入树集合中，而后再从这这个树集合的所有顶点中找出与其邻接的边权值最小的，同样此边的另外一个顶点加入树集合中，依次递归，直至图中所有顶点都加入树集合中，此时此树就是该图的最小生成树。普里姆算法的时间复杂度为o(n^2)，与图中的边数无关，因此该算法适合于求边稠密的网的最小生成树。
    （2）克鲁斯卡尔算法：这个算法是从边出发的，因为本质是选取权值最(推荐)小的n-1条边，因此，就将边按权值大小排序，依次选取权值最小的边，直至囊括所有节点，要注意每次选边后要检查不能形成环路。克鲁斯卡尔算法的时间复杂度为o(eloge)，与图中的顶点数无关，因此该算法适合于求边稀疏的网的最小生成树。

  • 拓扑序列：若图中一个节点入度为0，则应该最先执行此活动，而后删除掉此节点和其关联的有向边，再去找图中其他没有入度的结点，执行活动，依次进行，示例如下(有点类似于进程的前趋图原理)
  • 工具与技术：
    关键路径法关键路径：是项目的最短工期，但却是从开始到结束时间最长的路径。进度网络图中可能有多条关键路径，因为活动会变化，因此关键路径也在不断变化中关键活动：关键路径上的活动，最早开始时间=最晚开始时间。通常，每个节点的活动会有如下几个时间：
    （1）最早开始时间 (ES)某项活动能够开始的最早时间
    （2）某项活动能够完成的最早时间。EF=ES+工期最早结束时间(EF)
    （3）最迟结束时间(LF)。为了使项目按时完成，某项活动必须完成的最迟时间。
    （4）最迟开始时间(LS)。为了使项目按时完成，某项活动必须开始的最迟时间。LS=LF-工期
  • 总浮动时间:在不延误项目完工时间且不违反进度制约因素的前提下，活动可以从最早开始时间推迟或拖延的时间量，就是该活动的进度灵活性。正常情况下，关键活动的总浮动时间为零。
  • 总浮动时间=最迟开始LS-最早开始ES 或最迟完成LF-最早完成EF 或关键路径非关键路径时长。
  • 自由浮动时间:是指在不延误任何紧后活动的最早开始时间且不违反进度制约因素的前提下，活动可以从最早开始时间推迟或拖延的时间量。
  • 自由浮动时间=紧后活动最早开始时间的最小值-本活动的最早完成时间。

3.2 查找

3.2.1 顺序查找

  • 顺序查找的思想：将待查找的关键字为key的元素从头到尾与表中元素进行比较，如果中间存在关键字为key的元素，则返回成功；否则，则查找失败。
  • 平均查找长度为
  • 时间复杂度为O(n)。

3.2.2 折半查找

  • 折半查找只适用于待查找序列中的元素是有序排列的情况。
  • 设查找表的元素存储在一维数组r[1..n]中，在表中元素已经按照关键字递增或递减)方式排序的情况下，进行折半查找的方法是：
    1、首先将待查元素的关键字 (key) 值与表r中间位置上 (下标为mid) 记录的关键字进行比较，若相等，则查找成功；
    2、若key>r[mid].key，则说明待查记录只可能在后半个子表r[mid+1..n]中，下一步应在后半个子表中查找；
    3、若key<r[mid].key，说明待查记录只可能在前半个子表rl1..mid-1]中，下一步应在r的前半个子表中查找；
    4、重复上述步骤，逐步缩小范围，直到查找成功或子表为空失败时为止。要注意两点:中间值位置求出若为小数，应该向下取整，即4.5=4，非四舍五入中间值已经比较过不相等，在划分下一次比较区间时，无需将中间值位置再纳入下一次比较区间。
  • 折半查找的时间复杂度为

3.2.3 哈希表

  • 哈希表通过一个以记录的关键字为自变量的函数 (称为哈希函数)得到该记录的存储地址，所以在哈希表中进行查找操作时，需要用同一哈希函数计算得到待查记录的存储地址，然后到相应的存储单元去获得有关信息再判定查找是否成功。

  • 哈希函数产生了冲突的解决方法如下
    1.开放定址法：Hi=(H(key)+di) % m i=1,2,…, k(km – 1)其中，H(key)为哈希函数;m 为哈希表表长；di为增量序列常见的增量序列有以下3 种。
    (1) d =1,2,3,··,m-1，称为线性探测再散列；
    (2) 二次探测再散列；
    (3) d=伪随机数序列，称为随机探测再散列。
    2.链地址法。它在查找表的每一个记录中增加一个链域，链域中存放下一个具有相同哈希函数值的记录的存储地址。利用链域，就把若千个发生冲突的记录链接在一个链表内。当链域的值为NULL时，表示已没有后继记录了。因此，对于发生冲突时的查找和插入操作就跟线性表一样了
    3.再哈希法: 在同义词发生地址冲突时计算另一个哈希函数地址，直到冲突不再发生。这种方法不易产生聚集现象，但增加了计算时间。
    4.建立一个公共溢出区。无论由哈希函数得到的哈希地址是什么，一旦发生冲突都填入到公共溢出区中

3.3 排序

3.3.1 直接插入排序

  • 要注意的是，前提条件是前i-1个元素是有序的第i个元素依次从第i-1个元素而后插入，插入位置及其后往前比较，直到找到一个比第i个元素值小的元素的元素依次向后移动。
  • 当给出一队无序的元素时，首先，应该将第1个元素看做是一个有序的队列，而后从第2个元素起，按插入排序规则，依次与前面的元素进行比较，直到找到一个小于他的值，才插入。示例如下图所示:下图中，59依次向前比较，先和68比较，再和57比较，发现57比他小，才插入：

3.3.2 希尔排序

  • 希尔排序又称“缩小增量排序“是对直接插入排序方法的改进。
  • 希尔排序的基本思想是：先将整个待排记录序列分割成若千子序列，然后分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入。
  • 排序具体做法是：先取一个小于n 的整数d1作为第一个增量把文件的全部记录分成d1个组，将所有距离为d1 倍数的记录放在同一个组中，在各组内进行直接插入排序;然后取第二个增量d2(d2<d1)，重复上述分组和排序工作，依此类推，直至所取的增量di=1(di < di-1< …< d2<d1)，即所有记录放在同一组进行直接插入排序为止。
  • 按上述，希尔排序实际是为了解决大数据的排序问题当待排序的数据很多时，使用直接插入排序效率很低，因此，采取分组的方法，使问题细化，可以提高效率，适用于多数据。

3.3.3 简单选择排序

  • n个记录进行简单选择排序的基本方法是: 通过n – i(1<=i<=n)次关键字之间的比较，从n – i +1个记录中选出关键字最小的记录，并和第i 个记录进行交换，当i等于n时所有记录有序排列。按上述，本质就是每次选择出最小的元素进行交换主要是选择比较过程交换过程只有一次。示例如下：

3.3.4 堆排序

  • 堆排序的基本思想是:对一组待排序记录的关键字，首先按堆的定义排成一个序列(即建立初始堆)，从而可以输出堆顶的最大关键字(对于大根堆而言)，然后将剩余的关键字再调整成新堆，便得到次大的关键字，如此反复，直到全部关键字排成有序序列为止。
  • 为序列(55,60,40,10,80,65,15,5,75) 建立初始大根堆的过程如图所示

  • 由上图可知，首先将给出的数组按完全二叉树规则建立，而后，找到此完全又树的最后一个非叶子节点 (也即最后一颗子树)，比较此非叶子节点和其两个孩子结点的大小，若小，则与其孩子结点中最大的结点进行交换;依据此规则再去找倒数第二个非叶子节点;这是只有一层的情况，当涉及到多层次时又打破了之前的堆，因此，又要进行变换。
  • 建立初始堆后，开始排序，每次取走堆顶元素 (必然是最大的)而后将堆中最后一个元素移入堆顶，而后按照初始建堆中的方法与其孩子结点比较大小依次向下判断交换成为一个新的堆，再取走堆顶元素，重复此过程。堆排序适用于在多个元素中找出前几名的方案设计，因为堆排序是选择排序而且选择出前几名的效率很高。

3.3.5 冒泡排序

  • n个记录进行冒泡排序的方法是:首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则交换这两个记录的值，然后比较第二个记录和第三个记录的关键字依此类推，直至第n- 1个记录和第n 个记录的关键字比较过为止。上述过程称为一趟冒泡排序，其结果是关键字最大的记录被交换到第n 个记录的位置上。然后进行第二趟冒泡排序，对前n – 1个记录进行同样的操作，其结果是关键字次大的记录被交换到第n – 1个记录的位置上。最多进行n – 1 趟所有记录有序排列。若在某趟冒泡排序过程没有进行相邻位置的元素交换处理，则可结束排序过程。
  • 示例给的是从后往前排序，也是可以的，需要从最后两个元素开始进行比较，将较小的元素交换到前面去，依次进行比较交换。比较是为了交换，交换次数很多。区分冒泡排序和简单选择排序。

3.3.6 快速排序

  • 快速排序是将n个记录分成两块，再递归，实际分成两块的方法如图所示:设定一个基准为57，设定两个指针high=1，low=n，从low指向的第n个元素开始，与基准值进行比较，若小于基准值，则与基准进行交换low–，此时，转而从high指向的第1个元素开始和基准值进行比较，若大于基准值，则和基准值进行交换此时，又转而从low一指向的值和基准进行比较，重复上述过程。
  • 要注意的是:每次都是和基准值进行比较，因此最终是以基准值为中间，将队列分成两块。只有当和基准值发生了交换，才变换high和low指针的计数，否则会一直low-下去
  • 上图中，最终以57为界，左边都是小于57的元素右边都是大于57的元素，完成一次快速排序，接着对两块再分别进行递归即可

3.3.7 归并排序

  • 所谓“归并”是将两个或两个以上的有序文件合并成为一个新的有序文件归并排序的一种实现方法是把一个有n 个记录的无序文件看成是由n 个长度为1的有序子文件组成的文件，然后进行两两归并，得到[n/21个长度为2或1的有序文件，再两两归并，如此重复，直至最后形成包含n个记录的有序文件为止。这种反复将两个有序文件归并成一个有序文件的排序方法称为两路归并排序。要仔细理解上述过程，一般归并排序都是用来合并多个线性表的，对单列数据，二路归并排序可以对元素进行两两合并，示例如下!对第三次归并，将52与28比较，28小，放入新表头，52再与33比较，33放入新表，52再与72比较，52放入新表，57再与72比较，57放入新表…..

3.3.8 基数排序

  • 基数排序是基于多个关键字来进行多轮排序的，本质也是将问题细分，如图例子，分别按个位、十位、百位的大小作为关键字进行了三轮排序，最终得出结果。
  • 基数排序是一种借助多关键字排序思想对单逻辑关键字进行排序的方法。基数排序不是基于关键字比较的排序方法，它适合于元素很多而关键字较少的序列。基数的选择和关键字的分解是根据关键字的类型来决定的，例如关键字是十进制数，则按个位、十位来分解。

3.3.9 内部排序算法总结

  1. 若待排序的记录数目n 较小，可采用直接插入排序和简单选择排序。由于直接插入排序所需的记录移动操作较简单选择排序多，因此当记录本身信息量较大时，用简单选择排序方法较好。
  2. 若待排序记录按关键字基本有序，则宜采用直接插入排序或冒泡排序
  3. 当n 很大且关键字的位数较少时，采用链式基数排序较好。
  4. 若n 较大，则应采用时间复杂度为o(nlogn)的排序方法，例如快速排序、堆排序或归并排序。

3.3.10 算法特性

  • 算法 (Algorithm)是对特定问题求解步骤的一种描述，它是指令的有限序列其中每一条指令表示一个或多个操作。此外，一个算法还具有下列5个重要特性:
    (1)有穷性一个算法必须总是(对任何合法的输入值)在执行有穷步之后结束且每一步都可在有穷时间内完成确定性。算法中的每一条指令必须有确切的含义，理解时不会产生二义性.
    (2)并且在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。
    (3)可行性。一个算法是可行的，即算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
    (4)输入。一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合.
    (5)输出。一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。

第四章 操作系统知识

4.1 进程管理

4.1.1 操作系统概述

  • 操作系统定义:能有效地组织和管理系统中的各种软/硬件资源，合理地组织计算机系统工作流程，控制程序的执行，并且向用户提供一个良好的工作环境和友好的接口。
  • 操作系统有两个重要的作用：
    第一，通过资源管理提高计算机系统的效率；
    第二，改善人机界面向用户提供友好的工作环境。
  • 操作系统的4个特征是并发性、共享性、虚拟性和不确定性。
  • 操作系统的功能
    （1）进程管理。实质上是对处理机的执行“时间”进行管理采用多道程序等技术将CPU的时间合理地分配给每个任务，主要包括进程控制.进程同步、进程通信和进程调度。
    （2）文件管理。主要包括文件存储空间管理、目录管理、文件的读/写管理和存取控制。
    （3）存储管理。存储管理是对主存器“空间”进行管理，主要包括存储分配与回收、存储保护、地址映射 (变换)和主存扩充。
    （4）设备管理。实质是对硬件设备的管理，包括对输入/输出设备的分配、启动、完成和回收。
    （5）作业管理。包括任务、界面管理、人机交互、图形界面、语音控制和虚拟现实等。
  • 操作系统的分类：
    （1）批处理操作系统：单道批处理和多道批处理(主机与外设可并行)。
    （2）分时操作系统：一个计算机系统与多个终端设备连接。将CPU的工作时间划分为许多很短的时间片，轮流为各个终端的用户服务。
    （3）实时操作系统：实时是指计算机对于外来信息能够以足够快的速度进行处理并在被控对象允许的时间范围内做出快速反应。实时系统对交互能力要求不高但要求可靠性有保障。
    （4）网络操作系统：是使联网计算机能方便而有效地共享网络资源，为网络用户提供各种服务的软件和有关协议的集合。三种模式:集中模式、客户端/服务器模式、对等模式。
    （5）分布式操作系统：分布式计算机系统是由多个分散的计算机经连接而成的计算机系统，系统中的计算机无主、次之分，任意两台计算机可以通过通信交换信息。
    （6）微型计算机操作系统:简称微机操作系统，常用的有Windows、Mac os、LinuX。
  • 嵌入式操作系统主要特点：
    （1）微型化。从性能和成本角度考虑，希望占用的资源和系统代码量少，如内存少、字长短、运行速度有限、能源少(用微小型电池)
    （2）可定制。从减少成本和缩短研发周期考虑，要求嵌入式操作系统能运行在不同的微处理器平台上，能针对硬件变化进行结构与功能上的配置，以满足不同应用需要。
    （3）实时性。嵌入式操作系统主要应用于过程控制、数据采集、传输通信、多媒体信息及关键要害领域需要迅速响应的场合，所以对实时性要求较高。
    （4）可靠性。系统构件、模块和体系结构必须达到应有的可靠性，对关键要害应用还要提供容错和防故障措施。
    （5）易移植性。为了提高系统的易移植性，通常采用硬件抽象层和板级支撑包的底层设计技术。
  • 嵌入式系统初始化过程按照自底向上、从硬件到软件的次序依次为:片级初始化>板级初始化>系统初始化。

4.1.2 进程组成和状态

  • 进程的组成：进程控制块PCB(唯一标志)、程序(描述进程要做什么)、数据(存放进程执行时所需数据）。
  • 进程基础的状态是下左图中的三态图。需要熟练掌握左下图中的进程三态之间的转换。

4.1.3 前趋图

  • 用来表示哪些任务可以并行执行，哪些任务之间有顺序关系，具体如下图可知，ABC可以并行执行，但是必须AB C都执行完后，才能执行D，这就确定了两点：任务间的并行、任务间的先后顺序。

4.1.4进程同步与互斥

  • 临界资源：各进程间需要以互斥方式对其进行访问的资源。
  • 临界区：指进程中对临界资源实施操作的那段程序。本质是一段程序代码。
  • 互斥：某资源(即临界资源)在同一时间内只能由一个任务单独使用，使用时需要加锁，使用完后解锁才能被其他任务使用;如打印机。
  • 同步：多个任务可以并发执行，只不过有速度上的差异，在一定情况下停下等待，不存在资源是否单独或共享的问题;如自行车和汽车
  • 互斥信号量：对临界资源采用互斥访问，使用互斥信号量后其他进程无法访问，初值为1。同步信号量:对共享资源的访问控制，初值一般是共享资源的数量

【PV操作】

  • P操作：申请资源，S=S-1，若S>=0，则执行P操作的进程继续执行；若S<0，则置该进程为阻塞状态(因为无可用资源)并将其插入阻塞队列。
  • V操作：释放资源，S=S+1，若S>0，则执行V操作的进程继续执行;若S<=0并将其插入就绪队列(此时因为缺少资源被P操作则从阻塞状态唤醒一个进程，阻塞的进程可以继续执行)，然后执行V操作的进程继续。

  • 经典问题：生产者和消费者的问题三个信号量:互斥信号量S0(仓库独立使用权)，同步信号量S1(仓库空闲个数)，同步信号量S2(仓库商品个数)

4.1.5进程调度

  • 进程调度方式是指当有更高优先级的进程到来时如何分配CPU。分为可剥夺和不可剥夺两种，可剥夺指当有更高优先级进程到来时，强行将正在运行进程的CPU分配给高优先级进程；不可剥夺是指高优先级进程必须等待当前进程自动释放CPU。
  • 在某些操作系统中，一个作业从提交到完成需要经历高、中、低三级调度
    (1)高级调度。高级调度又称“长调度”“作业调度”或“接纳调度”，它决定处于输入池中的哪个后备作业可以调入主系统做好运行的准备，成为一个或一组就绪进程。在系统中一个作业只需经过一次高级调度。
    (2)中级调度。中级调度又称“中程调度”或“对换调度”，它决定处于交换区中的哪个就绪进程可以调入内存，以便直接参与对CPU的竞争。
    (3)低级调度。低级调度又称“短程调度”或“进程调度”它决定处于内存中的哪个就绪进程可以占用CPU。低级调度是操作系统中最活跃、最重要的调度程序，对系统的影响很大。
  • 调度算法：
    (1)先来先服务FCFS：先到达的进程优先分配CPU。用于宏观调度。
    (2)时间片轮转：分配给每个进程CPU时间片，轮流使用CPU，每个进程时间片大小相同，很公平，用于微观调度优先级调度:每个进程都拥有一个优先级，优先级大的先分配CPU。
    (3)多级反馈调度:时间片轮转和优先级调度结合而成，设置多个就绪队列1,2,3…n，每个队列分别赋予不同的优先级，分配不同的时间片长度;新进程先进入队列1的末属，按FCFS原则，执行队列1的时间片:若未能执行完进程，则转入队列2的末尾，如此重复。

4.1.6死锁

  • 当一个进程在等待永远不可能发生的事件时，就会产生死锁，若系统中有多个进程处于死锁状态，就会造成系统死锁。
  • 死锁产生的四个必要条件: 资源互斥、每个进程占有资源并等待其他资源系统不能剥夺进程资源、进程资源图是一个环路。
  • 死锁产生后解决措施是打破四大条件，有下列方法：
    （1）死锁预防采用某种策略限制并发进程对于资源的请求，破坏死锁产生的四个条件之一使系统任何时刻都不满足死锁的条件。
    （2）死锁避免一般采用银行家算法来避免，银行家算法，就是提前计算出一条不会死锁的资源分配方法，才分配资源，否则不分配资源，相当于借贷，考虑对方还得起才借钱，提前考虑好以后，就可以避免死锁。
    （3）死锁检测：允许死锁产生，但系统定时运行一个检测死锁的程序，若检测到系统中发生死锁，则设法加以解除。
    （4）死锁解除:即死锁发生后的解除方法，如强制剥夺资源，撤销进程等。
  • 死锁资源计算：系统内有n个进程，每个进程都需要R个资源，那么其发生死锁的最大资源数为n*(R-1)。其不发生死锁的最小资源数为n*(R-1)+1。

4.1.7线程

  • 传统的进程有两个属性:可拥有资源的独立单位;可独立调度和分配的基本单位。
  • 引入线程的原因是进程在创建、撤销和切换中，系统必须为之付出较大的时空开销，故在系统中设置的进程数目不宜过多，进程切换的频率不宜太高，这就限制了并发程度的提高。引入线程后，将传统进程的两个基本属性分开，线程作为调度和分配的基本单位，进程作为独立分配资源的单位。。用户可以通过创建线程来完成任务，以减少程序并发执行时付出的时空开销。
  • 线程是进程中的一个实体，是被系统独立分配和调度的基本单位。线程基本上不拥有资源，只拥有一点运行中必不可少的资源(如程序计数器、一组寄存器和栈)，它可与同属一个进程的其他线程共享进程所拥有的全部资源，例如进程的公共数据、全局变量、代码、文件等资源，但不能共享线程独有的资源如线程的栈指针等标识数据。

4.2 存储管理

4.2.1 分区存储管理

  • 所谓分区存储组织，就是整存，将某进程运行所需的内存整体一起分配给它然后再执行。有三种分区方式:固定分区:静态分区方法，将主存分为若千个固定的分区，将要运行的作业装配进去，由于分区固定，大小和作业需要的大小不同，会产生内部碎片
  • 可变分区:动态分方法，主存空间的分区是在作业转入时划分，正好划分为作业需要的大小，这样就不存在内部碎片，但容易将整片主存空间切割成许多块，会产生外部碎片。可变分区的算法如下系统分配内存的算法有很多，如下图所示，根据分配前的内存情况，还需要分配9K空间，对不同算法的结果介绍如下:
  • 可重定位分区可以解决碎片问题，移动所有已经分配好的区域，使其成为个连续的区域，这样其他外部细小的分区碎片可以合并为大的分区，满足作业要求。只在外部作业请求空间得不到满足时进行。

4.2.3分页存储管理

  • 逻辑页分为页号和页内地址，页内地址就是物理偏移地址，而页号与物理块号并非按序对应的，需要查询页表，才能得知页号对应的物理块号，再用物理块号加上偏移地址才得出了真正运行时的物理地址。
    优点:利用率高，碎片小，分配及管理简单
    缺点:增加了系统开销，可能产生抖动现象。

  • 页面置换算法：
    （1）最优算法：OPT，理论上的算法无法实现，是在进程执行完后进行的最佳效率计算，用来让其他算法比较差距。原理是选择未来最长时间内不被访问的页面置换，这样可以保证未来执行的都是马上要访问的。
    （2）先进先出算法：FIFO，先调入内存的页先被置换淘汰，会产生抖动现象，即分配的页数越多，缺页率可能越多(即效率越低)
    （3）最近最少使用：LRU，在最近的过去，进程执行过程中，过去最少使用的页面被置换淘汰，，根据局部性原理，这种方式效率高，且不会产生抖动现象，使用大量计数器但是没有LFU多
    （4）淘汰原则：优先淘汰最近未访问的，而后淘汰最近未被修改的页面

【快表】

  • 是一块小容量的相联存储器，由快速存储器组成，按内容访问，速度快，并且可以从硬件上保证按内容并行查找，一般用来存放当前访问最频繁的少数活动页面的页号。
  • 快表是将页表存于cache中;慢表是将页表存于内存上。慢表需要访问两次内存才能取出页，而快表是访问一次cache和一次内存，因此更快。

4.2.4分段存储管理

  • 将进程空间分为一个个段，每段也有段号和段内地址，与页式存储不同的是每段物理大小不同，分段是根据逻辑整体分段的，因此，段表也与页表的内容不同，页表中直接是逻辑页号对应物理块号，而下图所示，段表有段长和基址两个属性，才能确定一个逻辑段在物理段中的位置。

4.2.5段页式存储管理

  • 对进程空间先分段，后分页，具体原理图和优缺点如下!优点:空间浪费小、存储共享容易、存储保护容易、能动态链接缺点:由于管理软件的增加，复杂性和开销也随之增加，需要的硬件以及占用的内容也有所增加，使得执行速度大大下降

4.3 设备管理

4.3.1 设备管理概述

  • 设备是计算机系统与外界交互的工具，具体负责计算机与外部的输入/输出工作所以常称为外部设备(简称外设)。在计算机系统中，将负责管理设备和输入/输出的机构称为I/0系统。因此，i/0 系统由设备、控制器、通道(具有通道的计算I0 设香机系统)、总线和I/0 软件组成。

  • 设备的分类:
    （1）按数据组织分类:块设备、字符设备；
    （2）按照设备功能分类:输入设备、输出设备、存储设备、网络联网设备、供电设备；
    （3）源分配角度分类:独占设备资共享设备和虚拟设备；
    （4）数据传输速率分类:低速设备、中速设备、高速设备。

  • 设备管理的任务是保证在多道程序环境下，当多个进程竞争使用设备时，按定的策略分配和管理各种设备，控制设备的各种操作，完成//0 设备与主存之间的数据交换。

  • 设备管理的主要功能是动态地掌握并记录设备的状态、设备分配和释放、缓冲区管理、实现物理1/0 设备的操作、提供设备使用的用户接口及设备的访问和控制

4.3.2I/0软件

  • I/O设备管理软件的所有层次及每一层功能如下图：
    实例:当用户程序试图读一个硬盘文件时，需要通过操作系统实现这一操作与设备无关软件检查高速缓存中有无要读的数据块，若没有，则调用设备驱动程序，向i/0 硬件发出一个请求。然后，用户进程阻塞并等待磁盘操作的完成当磁盘操作完成时，硬件产生一个中断，转入中断处理程序。中断处理程序检查中断的原因，认识到这时磁盘读取操作已经完成，于是唤醒用户进程取回从磁盘读取的信息，从而结束此次I/0 请求。用户进程在得到了所需的硬盘文件内容之，后继续运行。

4.3.3设备管理技术

  • 一台独占设备，在同一时间只能由一个进程使用，其他进程只能等待，且不知道什么时候打印机空闲，此时，极大的浪费了外设的工作效率。
  • 引入SPOOLING (外围设备联机操作)技术，就是在外设上建立两个数据缓冲区，分别称为输入井和输出井，这样，无论多少进程，都可以共用这一台打印机，只需要将打印命令发出，数据就会排队存储在缓冲区中，打印机会自动按顺序打印，实现了物理外设的共享，使得每个进程都感觉在使用一个打印机，这就是物理设备的虚拟化。如下图所示

4.4 文件管理

4.4.1 文件管理概述

  • 文件是具有符号名的、在逻辑上具有完整意义的一组相关信息项的集合。
  • 信息项是构成文件内容的基本单位，可以是一个字符，也可以是一个记录记录可以等长，也可以不等长。一个文件包括文件体和文件说明。文件体是文件真实的内容。文件说明是操作系统为了管理文件所用到的信息，包括文件名文件内部标识文件的类型、文件存储地址、文件的长度、访问权限、建立时间和访问时间等。
  • 文件管理系统，就是操作系统中实现文件统一管理的一组软件和相关数据的集合，专门负责管理和存取文件信息的软件机构，简称文件系统。文件系统的功能包括按名存取;统一的用户接口;并发访问和控制;安全性控制;优化性能;差错恢复。
  • 文件的类型：
    （1）按文件性质和用途可将文件分为系统文件、库文件和用户文件；
    （2）按信息保存期限分类可将文件分为临时文件、档案文件和永久文件；
    （3）按文件的保护方式分类可将文件分为只读文件、读/写文件、可执行文件和不保护文件；（4） UNIX 系统将文件分为普通文件、目录文件和设备文件 (特殊文件)。
  • 文件的逻辑结构可分为两大类:有结构的记录式文件;无结构的流式文件
  • 文件的物理结构是指文件在物理存储设备上的存放方法，包括：
    （1）连续结构。连续结构也称顺序结构，它将逻辑上连续的文件信息 (如记录)依次存放在连续编号的物理块上。
    （2）链接结构。链接结构也称串联结构，它是将逻辑上连续的文件信息 (如记录)存放在不连续的物理块上，每个物理块设有一个指针指向下一个物理块。
    （3）索引结构。将逻辑上连续的文件信息 (如记录)存放在不连续的物理块中系统为每个文件建立一张索引表。索引表记录了文件信息所在的逻辑块号对应的物理块号，并将索引表的起始地址放在与文件对应的文件目录项中。
    （4）多个物理块的索引表。索引表是在文件创建时由系统自动建立的，并与文件一起存放在同一文件卷上。根据一个文件大小的不同，其索引表占用物理块的个数不等，一般占一个或几个物理块。

4.4.2索引文件结构

  • 如图所示，系统中有13个索引节点，0-9为直接索引，即每个索引节点存放的是内容，假设每个物理盘大小为4KB，共可存4KB*10=40KB数据;
  • 10号索引节点为一级间接索引节点，大小为4KB，存放的并非直接数据，而是链接到直接物理盘块的地址，假设每个地址占4B，则共有1024个地址，对应1024个物理盘，可存1024*4KB=4096KB数据。
  • 二级索引节点类似，直接盘存放一级地址，一级地址再存放物理盘快地址，而后链接到存放数据的物理盘块，容量又扩大了一个数量级，为1024*1024*4KB数据。

4.4.3文件目录

  • 文件控制块中包含以下三类信息:基本信息类、存取控制信息类和使用信息类。
    (1)基本信息类。例如文件名、文件的物理地址、文件长度和文件块数等。
    (2)存取控制信息类。文件的存取权限，像UNIX 用户分成文件主、同组用户和一般用户三类，这三类用户的读/写执行RWX权限。
    (3)使用信息类。文件建立日期、最后一次修改日期、最后一次访问的日期、当前使用的信息(如打开文件的进程数在文件上的等待队列)等。
  • 文件控制块的有序集合称为文件目录
  • 相对路径：是从当前路径开始的路径
    绝对路径：是从根目录开始的路径。
    全文件名=绝对路径+文件名。要注意，绝对路径和相对路径是不加最后的文件名的，只是单纯的路径序列。

4.4.4文件存储空间管理

  • 文件的存取方法是指读/写文件存储器上的一个物理块的方法。通常有顺序存取和随机存取两种方法。顺序存取片法是指对文件中的信息按顺序依次进行读写;随机存取方法是指对文件中的信息可以按任意的次序随机地读/写
  • 文件存储空间的管理：
    （1）空闲区表。将外存空间上的一个连续的未分配区域称为“空闲区”。操作系统为磁盘外存上的所有空闲区建立一张空闲表，每个表项对应一个空闲区适用于连续文件结构。
    （2）位示这种方法是在外存上建立一张位示图(Bitmap)，记录文件存储每一位对应文件存储器上的一个物理块，取值0 和1 分别表示空闲和暂用。
    （3）空闲块链。每个空闲物理块中有指向下-个空闲物理块的指针，所有空闲物理块构成一个链表，链表的头指针放在文件存储器的特定位置上(如管理块中)，不需要磁盘分配表，节省空间。
    （4）成组链接法。例如，在实现时系统将空闲块分成若干组，每100个空闲块为一组，每组的第一个空闲块登记了下一组空闲块的物理盘块号和空闲块总数假如某个组的第一个空闲块号等于0，意味着该组是最后一组，无下一组空闲块。

第五章 计算机网络

5.1 网络功能和分类

  • 计算机网络是计算机技术与通信技术相结合的产物，它实现了远程通信、远程信息处理和资源共享。
  • 计算机网络的功能:数据通信、资源共享、负载均衡、高可靠性。

  • 总线型(利用率低、干扰大、价格低)、星型(交换机形成的局域网、中央单元负荷大)、环型(流动方向固定、效率低扩充难)、树型(总线型的扩充、分级结构)、分布式(任意节点连接管理难成本高)

5.2OSI七层模型

5.3TCP/IP协议

  • 网络协议三要素：语法、语义、时序。其中语法部分规定传输数据的格式，语义部分规定所要完成的功能，时序部分规定执行各种操作的条件、顺序关系等。

  • 网络层协议:
    • IP：网络层最重要的核心协议，在源地址和目的地址之间传送数据报，无连接、不可靠。
    • ICMP：因特网控制报文协议，用于在IP主机、路由器之间传递控制消息。控制消息是指网络通不通、主机是否可达、路由是否可用等网络本身的消息。
    • ARP和RARP：地址解析协议，ARP是将IP地址转换为物理地址，RARP是将物理地址转换为IP地址。
    • IGMP：网络组管理协议，允许因特网中的计算机参加多播，是计算机用做向相邻多目路由器报告多目组成员的协议，支持组播。
  • 传输层协议：
    • TCP：整个TCP/IP协议族中最重要的协议之一，在IP协议提供的不可靠数据数据基础上，采用了重发技术，为应用程序提供了一个可靠的、面向连接的、全双工的数据传输服务。一般用于传输数据量比较少，且对可靠性要求高的场合。
    • UDP：是一种不可靠、无连接的协议，有助于提高传输速率，一般用于传输数据量大，对可靠性要求不高，但要求速度快的场合。
  • 应用层协议：基于TCP的FTP、HTTP等都是可靠传输。基于UDP的DHCP、DNS等都是不可靠传输。
    • FTP：可靠的文件传输协议，用于因特网上的控制文件的双向传输。
    • HTTP：超文本传输协议，用于从WWW服务器传输超文本到本地浏览器的传输协议。使用SSL加密后的安全网页协议为HTTPS。
    • SMTP和POP3：简单邮件传输协议，是一组用于由源地址到目的地址传送邮件的规则，邮件报文采用ASCII格式表示。
    • Telnet：远程连接协议，是因特网远程登录服务的标准协议和主要方式。
    • TFTP：不可靠的、开销不大的小文件传输协议。
    • SNMP：简单网络管理协议，由一组网络管理的标准协议，包含一个应用层协议、数据库模型和一组资源对象。该协议能够支持网络管理系统，泳衣监测连接到网络上的设备是否有任何引起管理师行关注的情况。
    • DHCP:动态主机配置协议，基于UDP，基于C/S模型，为主机动态分配IP地址，有三种方式:固定分配、动态分配、自动分配。
    • DNS：域名解析协议，通过域名解析出IP地址

5.4传输介质

  • 双绞线:将多根铜线按规则缠绕在一起，能够减少扰:分为无屏蔽双绞线UTP和屏蔽双绞线STP，都是由一对铜线族组成。也即我们常说的网线: 双绞线的传输距离在100m以内。
  • 无屏蔽双绞线UTP:价格低，安装简单，但可靠性相对较低，分为CAT3(3类UTP，速率为10Mbps)、CAT4(4类UTP，与3类差不多，无应用)、CAT5(5类UTP，速率为100Mbps，用于快速以太网)、CAT5E(超5类UTP，速率为1000Mbps)、CAT6 (6类UTP，用来替代CAT5E，速率也是1000Mbps)
  • 屏蔽双绞线STP:比之UTP增加了一层屏蔽层，可以有效的提高可靠性，但对应的价格高，安装麻烦，一般用于对传输可靠性要求很高的场合。
  • 网线有如下两种安装标准:都是八根不同颜色的网线按照不同的顺序排序，插入水晶头中区分在第1236四根网线的位置不同。
  • 光纤：由纤芯和包层组成，传输的光信号在纤芯中传输，然而从PC端出来的信号都是电信号，要经过光纤传输的话，就必须将电信号转换为光信号。
  • 多模光纤MMF:纤芯半径较大，因此可以同时传输多种不同的信号，光信号在光纤中以全反射的形式传输，采用发光二极管LED为光源，成本低，但是传输的效率和可靠性都较低，适合于短距离传输其传输距离与传输速率相关，速率为100Mbps时为2KM，速率为1000Mbps时为550m。
  • 单模光纤SMF:纤芯半径很小，一般只能传输一种信号，采用激光二极管LD作为光源，并且只支持激光信号的传播，同样是以全反射形式传播，只不过反射角很大，看起来像一条直线，成本高，但是传输距离远，可靠性高。传输距离可达5KM。

5.5通信方式和交换方式

  • 通信方向：数据通信是指发送方发送数据到接收方，这个传输过程可以分类如下：
    单工：只能由设备A发给设备B，即数据流只能单向流动。
    半双工：设备A和设备B可以互相通信，但是同一时刻数据流只能单向流动。
    全双工：设备A和设备B在任意时刻都能互相通信。
  • 同步方式
    异步传输：发送方每发送一个字符，需要约定一个起始位和停止位插入到字符的起始和结尾处这样当接收方接收到该字符时能够识别，但是这样会造成资源浪费，传输效率降低。
    同步传输：以数据块为单位进行传输，当发送方要发送数据时，先发送一个同步帧，接收方收到后做好接收准备，开始接收数据块，结束后又会有结束帧确认，这样一次传输一个数据块，效率高。
  • 串行传输:只有一根数据线，数据只能1bit挨个排队传送，适合低速设备、远距离的传送，般用于广域网中。
  • 并行传输:有多根数据线，可以同时传输多个bit数据，适合高速设备的传送，常用语计算机内部各硬件模块之间。

5.6IP地址

  • 机器中存放的IP地址是32位的二进制代码，每隔8位插入一个空格，可提高可读性，为了便于理解和设置，一般会采用点分十进制方法来表示:将32位二进制代码每8位二进制转换成十进制，就变成了4个十进制数，而后在每个十进制数间隔中插入。
  • 因为每个十进制数都是由8个二进制数转换而来，因此每个十进制数的取值范围为0-255(掌握二进制转十进制的快速计算方法，牢记2的幂指数值，实现快速转换)
  • 分类IP地址:IP地址分四段，每段八位，共32位二进制数组成在逻辑上，这32位IP地址分为网络号和主机号，依据网络号位数的不同，可以将P地址分为以下几类：

  • 今无分类编址:即不按照A B C类规则，自动规定网络号，无分类编址格式为:IP地址/网络号，示例:128.168.0.11/20表示的1P地址为128.168.0.11，其网络号占20位，因此主机号占32-20=12位，也可以划分子网。
  • 公有地址:通过它直接访问因特网。是全网唯一的IP地址。
    私有地址:属于非注册地址，专门为组织机构内部使用，不能直接访问因特网，下表所示为私有地址范围。

  • 其他特殊地址如下表所示：

  • 子网划分一般公司在申请网络时，会直接获得一个范围很大的网络，如一个B类地址，因为主机数之间相差的太大了，不利于分配，我们一般采用子网划分的方法来划分网络，即自定义网络号位数，就能自定义主机号位数，就能根据主机个数来划分出最适合的方案，不会造成资源的浪费。
  • 因此就有子网的概念，一般的IP地址按标准划分为ABC类后，可以进行再一步的划分，将主机号拿出几位作为子网号，就可以划分出多个子网，此时IP地址组成为: 网络号+子网号+主机号。
  • 子网掩码网络号和子网号都为1，主机号都为0，这样的地址为子网掩码。
  • 要注意的是：子网号可以为全0和全1，主机号不能为全0或全1，因此，主机数需要-2，而子网数不用。
  • 还可以聚合网络为超网，就是划分子网的逆过程，将网络号取出几位作为主机号，此时，这个网络内的主机数量就变多了，成为一个更大的网络。

5.7IPv6

  • 主要是为了解决IPv4地址数不够用的情况而提出的设计方案，IPv6具有以下特性:：
    （1）Pv6地址长度为128位，地址空间增大了2^96倍；
    （2）灵活的IP报文头部格式，使用一系列固定格式的扩展头部取代了IPv4中可变长度的选项字段。IPv6中选项部分的出现方式也有所变化，使路由器可以简单撸过选项而不做任何处理，加快了报文处理速度；
    （3）IPv6简化了报文头部格式，加快报文转发；
    （4）提高了吞吐量;提高安全性，身份认证和隐私权是IPv6的关键特性；
    （5）支持更多的服务类型;
    （6）允许协议继续演变，增加新的功能，使之适应未来技术的发展。
  • IPv4和IPv6的过渡期间，主要采用三种基本技术:
    （1）双协议栈:主机同时运行IPv4和1Pv6两套协议栈，同时支持两套协议，一般来说IPv4和IPv6地址之间存在某种转换关系，如IPv6的低32位可以直接转换为IPv4地址，实现互相通信。（2）隧道技术:这种机制用来在Pv4网络之上建立一条能够传输PV6数据报的陈道，例如可以将IPv6数据报当做IPv4数据报的数据部分加以封装，只需要加一个IPv4的首部，就能在IPv4网络中传输IPV6报。
    （3）翻译技术:利用一台专门的翻译设备(如转换网关)，在纯IP4和纯IPV6网络之间转换IP报头的地址，同时根据协议不同对分组做相应的语义翻译，从而使纯IPv4和纯IPv6站点之间能够透明通信。

5.8网络规划和设计

  • 三层模型将网络划分为核心层、汇聚层和接入层，每一层都有着特定的作用。
  • 核心层提供不同区域之间的最佳路由和高速数据传送；
  • 汇聚层将网络业务连接到接入层，并且实施与安全、流量、负载和路由相关的策略
  • 接入层为用户提供了在本地网段访问应用系统的能力，还要解决相邻用户之间的互访需要，接入层要负责一些用户信息(例如用户IP地址、MAC地址和访问 日志等)的收集工作和用户管理功能(包括认证和计费等)

  • 建筑物综合布线系统PDS：
    (1)工作区子系统:实现工作区终端设备到水平子系统的信息插座之间的互联。
    (2)水平布线子系统然实现管息插和管理子系统之间的连接。
    (3)设备间子系统:实现中央主配线架与各种不同设备之间的连接。
    (4)垂直干线子系统:实现各楼层设备间子系统之间的互连。
    (5)管理子系统:连接各楼层水平布线子系统和垂直干缆线，负责连接控制其他子系统为连接其他子系统提供连接手段。
    (6)建筑群子系统:各个建筑物通信系统之间的互联

5.9 其他考点补充

  • 网络地址翻译NAT：公司内有很多电脑，在公司局域网内可以互联通信，但是要访问外部因特网时，只提供固定的少量IP地址能够访问因特网，将公司所有电脑这个大的地址集合映射到能够访问因特网的少量IP地址集合的过程就称为NAT。很明显，使用了NAT后，一个公司只有少量固定IP地址可以上网，大大减少了IP地址的使用量。
  • 默认网关:一台主机可以有多个网关。默认网关的意思是一台主机如果找不到可用的网关，就把数据包发给默认指定的网关，由这个网关来处理数据包。现在主机使用的网关，一般指的是默认网关。默认网关的IP地址必须与本机IP地址在同一个网段内，即同网络号。
  • 虚拟局域网VLAN:是一组逻辑上的设备和用户，这些设备和用户并不受物理位置的限制，可以根据功能、部门及应用等因素将它们组织起来，相互之间的通信就好像它们在同一个网段中一样。
  • VLAN工作在0SI参考模型的第2层和第3层，一个VLAN就是一个广播域，VLAN之间的通信是通过第3层的路由器来完成的。
  • 与传统的局域网技术相比较，VLAN技术更加灵活，它具有以下优点: 网络设备的移动、添加和修改的管理开销减少;可以控制广播活动;可提高网络的安全性。
  • 虚拟专用网VPN是在公用网络上建立专用网络的技术。其之所以称为虚拟网，主要是因为整个VPN网络的任意两个节点之间的连接并没有传统专网所需的端到端的物理链路，而是架构在公用网络服务商所提供的网络平台，如Internet、ATM(异步传输模式》、Frame Relay (中继)等之上的逻辑网络，用户数据在逻辑链路中传输。
  • PPP：安全认证介绍:PPP的NCP可以承载多种协议的三层数据包。PPP使用LCP控制多种链路的参数(建立、认证、压缩、回拨)。PPP的认证类型:pap认证是通过二次握手建立认证(明文不加密)，chap挑战握手认证协议通过三次握手建立认证(密文采用MD5加密)。PPP的双向验证，采用的是chap的主验证风格。PPP的加固验证，采用的是两种 (pap,chap)验证同时使用
  • 冲突域和广播域:路由器可以阻断广播域和冲突域，交换机只能阻断冲突域，因此一个路由器下可以划分多个广播域和多个冲突域:一个交换机下整体是一个广播域，但可以划分多个冲突域:而物理层设备集线器下整体作为一个冲突域和一个广播域。

5.10 网络安全技术

【防火墙】

  • 防火墙是在内部网络和外部因特网之间增加的一道安全防护措施，分为网络级防火墙和应用级防火墙。
  • 网络级防火墙层次低，但是效率高，因为其使用包过滤和状态监测手段，般只检验网络包外在(起始地址、状态)属性是否异常，若异常，则过滤掉不与内网通信，因此对应用和用户是透明的。
  • 但是这样的问题是，如果遇到伪装的危险数据包就没办法过滤，此时，就要依靠应用级防火墙，层次高，效率低，因为应用级防火墙会将网络包拆开，具体检查里面的数据是否有问题，会消耗大量时间，造成效率低下，但是安全强度高。

【入侵检测】

  • 入侵检测系统IDS防火墙技术主要是分隔来自外网的威胁，却对来自内网的直接攻击无能为力此时就要用到入侵检测IDS技术，位于防火墙之后的第二道屏障，作为防火墙技术的补充。
  • 原理:监控当前系统/用户行为，使用入侵检测分析引擎进行分析，这里包含个知识库系统，囊括了历史行为、特定行为模式等操作，将当前行为和知识库进行匹配，就能检测出当前行为是否是入侵行为，如果是入侵，则记录证据并上报给系统和防火墙，交由它们处理
  • 不同于防火墙，IDS入侵检测系统是一个监听设备，没有跨接在任何链路上无须网络流量流经它便可以工作。因此，对IDS的部署，唯一的要求是: DS应当挂接在所有所关注流量都必须流经的链路上。因此，IDS在交换式网络中的位置般选择在: (1)尽可能靠近攻击源 (2) 尽可能靠近受保护资源

【入侵防御】

  • 入侵防御系统IPSIDS和防火墙技术都是在入侵行为已经发生后所做的检测和分析，而iPS是能够提前发现入侵行为，在其还没有进入安全网络之前就防御。在安全网络之前的链路上挂载入侵防御系统IPS，可以实时检测入侵行为，并直接进行阻断，这是与IDS的区别，要注意。
  • 杀毒软件用于检测和解决计算机病毒，与防火墙和IDS要区分，计算机病毒要靠杀毒软件防火墙是处理网络上的非法攻击。
  • 蜜罐系统：伪造一个蜜罐网络引诱黑客攻击蜜罐网络被攻击不影响安全网络，，并且可以借此了解黑客攻击的手段和原理，从而对安全系统进行升级和优化
  • 网络攻击和威胁

【计算机病毒和木马】

  • 病毒：编制或者在计算机程序中插入的破坏计算机功能或者破坏数据，影响计算机使用并且能够自我复制的一组计算机指令或者程序代码。
  • 木马：是一种后门程序，常被黑客用作控制远程计算机的工具，隐藏在被控制电脑上的一个小程序监控电脑一切操作并盗取信息。
  • 代表性病毒实例：
    蠕虫病毒(感染EXE文件)：熊猫烧香，罗密欧与朱丽叶，恶鹰，尼姆达，冲击波，欢乐时光。
    木马:QQ消息尾巴木马，特洛伊木马，x卧底。
    宏病毒(感染word、excel等文件中的宏变量):美丽沙，台湾1号
    CIH病毒:史上唯一破坏硬件的病毒。
    红色代码:蠕虫病毒+木马。

5.11网络安全协议

物理层主要使用物理手段，隔离、屏蔽物理设备等，其它层都是靠协议来保证传输的安全，具体如下图所示：

  • SSL协议：安全套接字协议，被设计为加强Web安全传输(HTTP/HTTPS/)的协议安全性高，和HTTP结合之后，形成HTTPS安全协议，端口号为443。
  • SSH协议：安全外壳协议，被设计为加强Telnet/FTP安全的传输协议。
  • SET协议：安全电子交易协议主要应用于B2C模式(电子商务) 中保障支付信息的安全性。SET协议本身比较复杂，设计比较严格，安全性高，它能保证信息传输的机密性、真实性、完整性和不可否认性。SET协议是PKI架下的一个典型实现，同时也在不断升级和完善，如SET20将支持借记卡电子交易。
  • Kerberos协议：是一种网络身份认证协议该协议的基础是基于信任第三方它提供了在开放型网络中进行身份认证的方法，认证实体可以是用户也可以是用户服务。这种认证不依赖宿主机的操作系统或计算机的IP地址，不需要保证网络上所有计算机的物理安全性，并且假定数据包在传输中可被随机窃取和算改。
  • PGP协议：使用RSA公证书进行身份认证，使用IDEA (128位密)进行数据加密，使用MD5进行数据完整性验证。发送方A有三个密钥:A的私钥、B的公A成的一次性对称密接收方B有两个密钥：B的私钥、A的公钥。

第六章 数据库技术基础

6.1 基本概念

6.1.1 关于数据的基本概念

  • 数据：是数据库中存储的基本对象，是描述事物的符号记录数据的种类:文本、图形、图像、音频、视频、学生的档案记录、货物的运输情况等。
  • 数据库(DB)：是长期存储在计算机内、有组织的、可共享的大量数据的集合。
    数据库的基本特征：数据按一定的数据模型组织、描述和存储，可为各种用户共享，几余度较小;数据独立性较高；易扩展。
  • 数据库管理系统DBMS：是位于用户与操作系统之间的一层数据管理软件，用于科学地获取、组织、存储和维护数据，是一个大型复杂的软件系统。
  • 数据库系统(DBS)是计算机系统中引入数据库后的系统构成。
    数据库库系统的构成：数据库;硬件平台；软件 (应用程序) ；数据库管理员。

6.1.2 数据库管理系统的功能

DBMS的组成部分：
●数据定义语言DDL及编译处理程序
●数据操纵语言DML及其编译程序
●数据库运行控制程序
●实用程序

DBMS的主要功能：
●数据定义
●数据操纵
●数据库运行管理
●数据组织、存储和管理
●数据库的建立和维护
●数据通信接口
●数据控制功能

数据控制功能
(1)数据的安全性(Security) 保护保护数据，以防止不合法的使用造成的数据的泄密和破坏。
(2)数据的完整性(Integrity)检查将数据控制在有效的范围内，或保证数据之间满足一定的关系。
(3)并发(Concurrency)控制对多用户的并发操作加以控制和协调，防止相互干扰而得到错误的结果。
(4)数据库恢复(Recovery) 将数据库从错误状态恢复到某一已知的正确状态

6.1.3 数据各个发展阶段的特点

6.1.4 数据库系统的体系结构

  • 从数据库应用开发人员或数据库管理系统的角度看(内部体系结构): 数据库采用三级模式结构，是数据库系统的内部的系统结构，外模式、模式、内模式。
  • 从数据库最终用户角度看(外部体系结构)：
    （1）集中式：数据、数据管理、功能应用、用户接口到DBMS核心都集中在DBMS所在的计算机上。
    （2）分布式数据库系统是数据库系统和计算机网络相结合的产物。是针对面向地理上分散，而管理上又需要不同程度集中管理的需求而提出的一种数据管理信息系统。
    （3）客户-服务器结构:一个处理机(客户端)的请求被送到另一个处理机(服务器上执行。
    （4）并行式：使用相连接的多个CPU和多个磁盘进行并行操作，提高数据处理和I/O速度。
    （5）数据库技术是计算机处理与数据存储最有效、最成功的技术，而Web技术的特点是资源共享，因此数据与资源共享这两种技术的结合即形成了今天广泛应用的IWeh数据库(即网络数据库)

6.2 数据模型

6.2.1 三级模式两级映像

  • 模式(概念模式、逻辑模式)：就是我们通常使用的表这个级别;是数据库中全体数据的逻辑结构和特征的描述，是所有用户的公共数据视图，综合了所有用户的需求;一个数据库只有一个模式。如公司的所有员工管理信息系统。
  • 外模式(子模式、用户模式)：对应数据库中的视图这个级别;是数据库用户 (包括应用程序员和最终用户使用的局部数据的逻辑结构和特征的描述，数据库用户的数据视图，是与某一应用有关的数据的逻辑表示。员工管理员和薪酬管理员关注的不同方面。介于模式与应用之间，可以有多个外模式，通常是模式的子集;反映了不同的用户的应用需求外模式的用途:保证数据库安全性的一个有力措施每个用户只能看见和访问所对应的外模式中的数据。
  • 内模式《存储模式)：管理如何存储物理的数据，是数据物理结构和存储方式的描述，是数据在数据库内部的表示方法;一个数据库只有一个内模式。

【三个级别】
●用户级数据库：对应于外模式，是用户看到和使用的数据库，又称用户视图，一个数据库可有多个不同的用户视图；
●概念级数据库：对应于概念模式，是所有用户视图的最小并集，一个数据库应用系统只有一个DBA视图。
●物理级数据库：对应于内模式，是数据库的底层表示，它描述数据的实际存储组织，是最接近于物理存储的，又称为内部视图。

6.2.2 数据模型_模型分类

数据模型，现实世界的模拟，对现实世界中的概念进行抽象、表示和处理(对数据进行描述、组织和操作)的工具。数据模型是数据库系统的核心和基础。
●概念模型(信息模型)：按用户的观点来对数据和信息建模，通常用ER图进行描述，用于数据库设计。与计算机无关。
●逻辑模型：按计算机系统的观点对数据建模，用于DBMS实现。主要包括:网状模型、层次模型、关系模型、面向对象模型等。与计算机有关
●物理模型：是对数据最底层的抽象，描述数据在系统内部的表示方式和存取方法。与计算机有关。

6.2.3数据模型_组成要素

  • 实体完整性：实体完整性是指实体的主属性不能取空值。实体完整性规则规定实体的所有主属性都不能为空。
  • 参照完整性：在关系数据库中主要是外键参照的完整性。
  • 用户定义完整性:用户定义完整性是针对某一个具体关系的约束条件。

6.2.4概念模型中的基本概念

  • 实体型之间的联系：E-R图(实体-关系图)
    概念模型用于信息世界的建模是数据库设计的有力工具，也是数据库设计人员和用户之间进行交流的语言，主要通过E-R图进行描述。

（1）实体(Entity):客观存在并可相互区别的事物称为实体。可以是具体的人、事、物或抽象的概念客观实体：人、课桌、书本……
抽象实体：账户、贷款……
（2）属性(Attribute)：实体所具有的某一特性称为属性。一个实体可以由若干个属性来刻画如员工实体由员工编号、姓名、年龄、职务、部门……
（3）码(Key)：标识实体的属性集称为码。
（4）域(Domain)：属性的取值范围称为该属性的域
（5）实体型(Entity Type)：用实体名及其属性名集合来抽象和刻画同类实体称为实体型

  • 属性的分类：
    ●简单属性：原子的、不可再分的。
    ●复合属性：可细分为多个属性部分，如name有first name和last name。或者家庭地址:北京市朝阳区望京街道
    ●单值属性:定义的属性对于一个特定的实体都只有单独的一个值。
    ●多值属性:一个属性可能对应一组值。如员工的电话号码:每个员工就可能有0、1或多个与之相对应。
    ●NULL属性:当实体在某个属性上没有值或属性值未知时，使用NULL值。
    ●派生属性:这类属性的值可以从别的相关属性或实体中派生(计算出来)

【概念模型-E-R图-联系（2个实体）】

  • 一对一联系(1:1)定义：如果对于实体集A中的每一个实体，实体集B中至多有一个(也可以没有)实体与之联系，反之亦然，则称实体集A与实体集B具有一对一联系，记为1:1。
  • 一对多联系(1:n)定义：如果对于实体集A中的每一个实体，实体集B中有n个实体(n20)与之联系，反之，对于实体集B中的每一个实体，实体集A中至多只有一个实体与之联系，则称实体集A与实体集B有一对多联系，记为1:n。
  • 多对多联系(m:n)定义：如果对于实体集A中的每一个实体，实体集B中有n个实体(n20)与之联系，反之，对于实体集B中的每一个实体，实体集A中也有m个实体(m20)与之联系，则称实体集A与实体B具有多对多联系，记为m:n。

6.2.5 数据模型

  • 层次模型(Hierarchical Model)
  • 网状模型(Network Model)
  • 关系模型(Relational Model)
  • 面向对象模型(Object Oriented Model)
  • 对象关系模型(Object Relational Model)

层次模型用树形结构来表示各类实体以及实体间的联系层次模型只能表示1:n联系，不能表示mn联系。层次模型中的术语:根结点，双亲结点，兄弟结点，叶结点。层次模型两个基本条件：有且只有一个结点没有双亲结点，这个结点称为根结点；根以外的其它结点有且只有一个双亲结点。

关系数据库系统采用关系模型作为数据的组织方式，以关系代数为数据基础，数据用二维表表示。大多数数据库均为关系数据模型。优点:建立在严格的数学概念基础上;概念单一、结构简单、清晰，用户易懂易用，存取路径对用户透明从而数据独立性、安全性好，简化数据库开发工作。缺点:由于存取路径透明，查询效率往往不如非关系数据模型。
●关系：一个关系对应一张表(Relation)；
●元组(Tuple)：表中的一行即为一个元组；
●属性(Attribute)：表中的一列即为一个属性；
●主码(Key)：唯一确定一个元组属性集合；
●域(Domain)：属性的取值范围；
●分量：元组中的一个属性值；
●关系模式：对关系的描述基本形式，关系名 (属性1，属性2，…，属性n)示例：学生(学号，姓名，年龄，性别，系，年级)；
●关系的规范化理论-属性的原子性，即属性是不可再分，表中不再包含表同一关系中属性唯一性；
●关系中元组唯一性关系中元组的有限性；
●关系中元组次序无关紧要；
●关系中属性次序无关紧要

6.3 数据存储与查询

  • 存储管理器在数据库系统中负责在数据库中存储的低层数据与应用程序以及向系统提交的查询之间提供接口的部件，负责数据库中数据的存储、检索和更新。存储管理器部件包括以下四个：
    （1）权限及完整性管理器:检查访问数据库的用户权限，检测数据是否满足完整性约束；
    （2）事务管理器:保证一旦发生故障，数据库的一致性状态，以及并发事务执行时不发生冲突（3）文件管理器:管理磁盘存储空间的分配。
    （4）缓冲区管理器:负责将数据从硬盘放入内存，并决定哪些数据应被缓冲区放入内存
  • 查询处理器其组件包括：
    DDL解释器：解释DDL语句并将其放入数据字典中；
    DML编译器：将查询语言中的DML语句翻译为一个计算方案，包括一系列查询计算引擎能理解的命令。

6.4 数据仓库与数据挖掘基础知识

6.4.1 数据仓库

  • 数据仓库四大特点：
    （1）面向主题：按照一定的主题域进行组织的；
    （2）集成的：数据仓库中的数据是在对原有分散的数据库数据抽取、清理的基础上经过系统加工、汇总和整理得到的，必须消除源数据中的不一致性，以保证数据仓库内的信息是关于整个企业的一致的全局信息。
    （3）相对稳定的:数据仓库的数据主要供企业决策分析之用所涉及的数据操作主要是数据查询，一旦某个数据进入数据仓库以后，一般情况下将被长期保留，也就是数据仓库中一般有大量的查询操作，但修改和删除操作很少通常只需要定期的加载、刷新。
    （4）反映历史变化:数据仓库中的数据通常包含历史信息系统记录了企业从过去某一时点(如开始应用数据仓库的时点)到目前的各个阶段的信息，通过这些信息，可以对企业的发展历程和未来趋势做出定量分析和预测。

6.4.2 数据挖掘

  • 概念：是从大量数据中发现并提取隐藏在内的，人们事先不知道的但可能有用的信息和知识的一种新技术。
  • 目的：帮助决策者寻找数据间潜在的关联，发现经营者被忽略的要素。
  • 数据挖掘技术涉及数据库技术、人工智能技术、机器学习、统计分析等多种技术。
  • 数据挖掘和传统分析方法的区别：数据挖掘是在没有明确假设的前提下去挖掘信息，发现知识。其得到的信息应具有事先未知、有效和可实用3个特征。
  • 数据挖掘的应用过程：确定挖掘对象-准备数据-建立模型-数据挖掘-结果分析-知识应用。

数据挖掘分析方法：
（1）关联分析：关联分析主要用于发现不同事件之间的关联性，即一个事件发生的同时，另一个事件也经常发牛。
（2）序列分析：序列分析主要用于发现一定时间间隔内接连发生的事件，这些事件构成一个序列，发现的序列应该具有普遍意义。
（3）分类分析：分类分析通过分析具有类别的样本特点，得到决定样本属于各种类别的规则或方法。分类分析时首先为每个记录赋予一个标记(一组具有不同特征的类别)，即按标记分类记录，然后检查这些标定的记录，描述出这些记录的特征。
（4）聚类分析：聚类分析是根据“物以类聚”的原理，将本身没有类别的样本聚集成不同的组，并且对每个这样的组进行描述的过程。

数据挖掘算法(了解分类即可) ：
●EM：在概率模型中寻找参数最大似然估计的算法；
●Apriori：先验算法是关联规则学习的经典算法之一；
●K-means：是非监督学习中的聚类算法；
●SVM：中文名为支持向量机，是常见的一种判别方法。在机器学习领域，是一个有监督的学习模型，通常用来进行模式识别、分类以及回归分析；
●决策树：典型的分类算法。

6.4.3商业智能BI

BI系统主要包括数据预处理、数据分析和数据展现四个主要阶段建立数据仓库。

  • 数据预处理是整合企业原始数据的第一步，它包括数据的抽取(Extraction)、转换(Transformation)和加载(Load)三个过程(ETL过程)；
  • 建立数据仓库则是处理海量数据的基础；
  • 数据分析是体现系统智能的关键，一般采用联机分析处理(OLAP)和数据挖掘两大技术。联机分析理不仅进行数据汇总/聚集，同时还提供切片、切块、下钻、上卷和旋转等数据分析功能，用户可以便地对海量数据进行多维分析。数据挖掘的目标则是挖掘数据背后隐藏的知识，通过关联分析、聚和分类等方法建立分析模型，预测企业未来发展趋势和将要面临的问题；
  • 数据据展现：在海量数据和分析手段增多的情况下，数据展现则主要保障系统分析结果的可视化。

第七章 关系数据库

7.1 关系数据库概述

  • 关系模型采用单一的数据结构一关系，来表示现实世界的实体以及实体间的联系，对应的逻辑结构为二维表。
  • 候选码(Candidate Key)：若关系中的某一属性或属性组的值能唯一标识一个元组，则称该属性或属性组为候选码。
  • 主码(Primary Key)：或称主键，若一个关系有多个候选码，则选定其中一个为主码。
  • 主属性(Primeattribute)：包含在任何候选码中的属性称为主属性。不包含在任何候选码中的属性称为非主属性(NonPrime attribute)
  • 外码(Foreignkey)：如果关系模式R中的属性或属性组非该关系的码，但它是其他关系的码，那么该属性集对关系模式R而言是外码。
  • 全码(AIl-key)：关系模型的所有属性组是这个关系模式的候选码，称为全码。

7.2 关系代数

  • 并：结果是两张表中所有记录数合并，相同记录只显示一次；
  • 交：结果是对长表中相同的过录；
  • 差：S1- S2 结果是S1表中有，而S2表中没有的那些记录。

  • 笛卡尔积：S1*S2，产生的结果包括S1和S2的所有属性列，并且S1中每条记录依次和S2中所有记录组合成一条记录，最终属性列为S1+S2属性列，记录数为S1*S2记录数；
  • 投影：实际是按条件选择某关系模式中的某列，列也可以用数字表示；
  • 选择：实际是按条件选择某关系模式中的某条记录。

  • 自然连接的结果显示全部的属性列，但是相同属性列只显示一次，显示两个关系模式中属性相同且值相同的记录设有关系R、S如下左图所示，自然连接结果如下右图所示：

  • 一般连接(连接)和等值连接:先做笛卡尔积，在其基础上满足连接条件，如下图分别是选取RS笛卡尔积后条件第C行小于第E的数据，R的第B行等于S的第B行数据

  • 全外连接(FULLOUTERJOIN)：关系RS进行自然连接时，把舍弃的元组也保存在结果关系中，在其他表的属性上填NULL。
  • 左外连接(LEFTOUTERJOIN)：关系RS进行自然连接时，只把左边关系R中要舍弃的元组保留。
  • 右外连接：关系RS进行自然连接时，只把右边关系S中要舍弃的元组保留

7.3 元组演算与域演算

把数理逻辑的谓词演算引入到关系运算中，就可得到以关系演算为基础的运算关系演算又可分为：
●元组关系演算(元组演算)：以元组为变量
●域关系演算(域演算)：以属性(域)为变量

7.4 查询优化

【选择操作的实现】

  • 查询方法：
    简单的全表扫描方法:对查询的基本表顺序扫描，逐一检查每个元组是否满足选择条件，把满足条件的元组作为结果输出。
    对于小表，这种方法简单有效；对于大表，顺序扫描十分费时，效率低。
  • 优化方法：索引(或散列)扫描方法:如果选择条件中的属性上有索引(如hash索引)，用索引扫描法通过索引先找到满足条件的元组主键或元组指针，再通过元组指针直接在查询的基本表中找到元组。

【连接操作的实现】
连接操作是查询处理中最耗时的操作之一。

  • 查询方法：
    嵌套循环方法：对外层循环R的每一个元组，检索内层循环S中的每一个元组，并检查这两个元组在连接属性sno上是否相等，如果满足连接条件，则串接后作为结果输出，直到双重循环结束。
  • 优化方法：
    排序-合并方法：适合连接的各表已经有序的情况，步骤为：
    （1）先给各表排序；
    （2）取R表中第一个sno，依次扫描S表中具有相同sno的元组把它们连接起来；
    （3）当扫描到sno不相同的第一个元组时，返回到R表扫描其下一个元组，再用其下一个元组去S表中查找相同sno的元组，重复这个过程。
  • 查询优化的目标:选择有效策略，求得给定关系表达式的值，使得查询代价最小。
  • 优化准则：
    （1）提早执行选择运算，目的是减少中间结果
    （2）合并乘积与选择运算为连接运算，目的是避免扫描大的关系
    （3）将投影运算与其他运算同时进行，目的是避免重复扫描关系
    （4）将投影运算与二目运算结合起来，目的是减少扫描关系的次数
    （5）在执行连接前对关系适当的预处理，如索引连接法、排序合并法存储公共子表达式，目的是只需检索中间结果，不需重复计算。
  • 效率问题
    关系代数运算的效率，归根结底是看参与运算的两张表格的属性列数和记录数属性列和记录数越少，参与运算的次数自然越少，效率就越高。

7.5 关系数据库设计

  • 给定一个X，能唯一确定一个Y，就称X确定Y，或者说Y依赖于x，例如Y=X*X函数。
  • 函数依赖又可扩展以下两种规则：
    （1）部分函数依赖：A可确定C，(A,B)也可确定C，(A,B)中的一部分 (即A) 可以确定C，称为部分函数依赖。
    （2）传递函数依赖：当A和B不等价时，A可确定B，B可确定C，则A可确定C，是传递函数依赖;若A和B等价，则不存在传递，直接就可确定C。

  • 函数依赖的公理系统(Armstrong)设关系模式RU是关系模式R的属性全集，F是关系模式R的一个函数依赖集。对于R来说有以下的：

【几个比较重要的概念】

  • 超键：能唯一标识此表的属性的组合；
  • 侯选键：超键中去掉冗余的属性，剩余的属性就是候选键；
  • 主键：任选一个候选键，即可作为主键；
  • 外键：其他表中的主键；
  • 主属性：候选键内的属性为主属性，其他属性为非主属性；
  • 实体完整性约束：即主键约束，主键值不能为空，也不能重复；
  • 参照完整性约束：即外键约束，外键必须是其他表中已经存在的主键的值或者为空；
  • 用户自定义完整性约束：自定义表达式约束，如设定年龄属性的值必须在0到150之间。

【第一范式1NF】
●关系中的每一个分量必须是一个不可分的数据项。通俗地说，第一范式就是表中不允许有小表的存在。比如，对于如下的员工表，就不属于第一范式：

实例：用一个单一的关系模式学生来描述学校的教务系统学生(学号,学生姓名,系号,系主任姓名课程号,成绩)依赖关系(学号->学生姓名，学号->系号，系号->系主任姓名，学号->课程号，(学号，课程号) ->成绩)

【第二范式】
●如果关系R属于1NF，且每一个非主属性完全函数依赖于任何一个候选码，则R属于2NF。通俗地说，2NF就是在1NF的基础上，表中的每一个非主属性不会依赖复合主键中的某一个列。按照定义，上面的学生表就不满足2NF，因为学号不能完全确定课程号和成绩(每个学生可以选多门课)。

将学生表分解为：
●学生（学号，学生姓名，系编号，系名，系主任)
●选课(学号，课程号，成绩)
●每张表均属于2NF。

第二范式消除了非主属性对主属性的部分函数依赖

【第三范式】

●在满足1NF的基础上，表中不存在非主属性对码的传递依赖；
继续上面的实例，学生关系模式就不属于3NF，因为学生无法直接决定系主任和系名，是由学号->系编号，再由系编号->系主任，系编号->系名，因此存在非主属性对主属性的传递依赖

将学生表进一步分解为：
学生(学号，学生姓名，系编号)
系(系编号，系名，系主任)
选课(学号，课程号，成绩)
每张表都属于3NF。

【BC范式BCNF】
是指在第三范式的基础上进一步消除主属性对于码的部分函数依赖和传递依赖。通俗的来说，就是在每一种情况下，每一个依赖的左边决定因素都必然包含候选律，如下：

  • 上图中，候选键有两种情况：组合键(S,T)或者(S,J)，依赖集为(SJ-T，T一可知，STJ三个属性都是主属性，因此其达到了3NF(无非主属性)，然而，第二种情况，即(SJ)为候选键的时候，对于依赖T->J，T在这种情况不是候选键，即T-J的决定因素不包含任意候选码，因此上图不是BCNF。
  • 要使上图关系模式转换为BCNF也很简单，只需要将依赖T->J变为TS->J即可这样其左边决定因素就包含了候选键之一S

7.6 模式分解

  • 范式之间的转换一般都是通过拆分属性，即模式分解，将具有部分函数依赖和传递依赖的属性分离出来，来达到一步步优化，一般分为以下两种：
    （1）保持函数依赖分解对于关系模式R，有依赖集F，若对R进行分解，分解出来的多个关系模式，保持原来的依赖集不变，则为保持函数依赖的分解。另外，注意要消除掉冗余依赖(如传递依赖)
    ●实例：设原关系模式R(A,B,C)，依赖集F(A->B，B-C，A-C)，将其分解为两个关系模式R1(A,B)和R2(B,C)，此时R1中保持依赖A->B，R2保持依赖B->C，说明分解后的R1和R2是保持函数依赖的分解，因为A->C这个函数依赖实际是一个几余依赖，可以由前两个依赖传递得到，因此不需要管。

  • 无损分解：分解后的关系模式能够还原出原关系模式，就是无损分解，不能还原就是有损。

  • 当分解为两个关系模式，可以通过以下定理判断是否无损分解定理:如果R的分解为p=R1，R2)，F为R所满足的函数依赖集合，分解p具有无损连接性的充分必要条件是R1nR2->(R1-R2)或者R1nR2->(R2-R1)。

  • 当分解为三个及以上关系模式时，可以通过表格法求解，如下

第八章 数据库SQL语言

8.1 SQL语言概述

  • 数据定义语言DDL：数据结构定义与数据库对象定义的语言，由create、alter、drop三个语法组成。
  • 数据操纵语言DML: 实现对数据库的基本操作，包含select、update、insert、delete等语法。
  • 数据库语言的分类
    ●作为独立语言使用；
    ●嵌入到高级语言中使用：嵌入式SQL、宿主语言。
  • SQL由以下几个部分组成：
    （1）数据定义语言。SQL DDL提供定义关系模式和视图、删除关系和视图修改关系模式的命令。
    （2）交互式数据操纵语言。SQLDML 提供查询、插入、删除和修改的命令。
    （3）事务控制。SQL 提供定义事务开始和结束的命令。
    （4）嵌入式SQL和动态SQL。用于嵌入到某种通用的高级语言(C、C+ +、JavaPL/l、COBOL和VB等)中混合编程。其中，SQL负责操纵数据库，高级语言负责控制程序流程。
    （5）完整性。SQLDDL 包括定义数据库中的数据必须满足的完整性约束条件的命令，对于破坏完整性约束条件的更新将被禁止。
    （6）权限管理。SQLDDL 中包括说明对关系和视图的访问权限。

8.2 数据库定义

8.2.1 创建表(create table)

CREATE TABLE([列级完整性约束条件]
[，[列级完整性约束条件]]…
[，]) ;

●列级完整性约束条件有 NULL (空)和UNTQUE(取值唯一)。
●表级完整性约束条件有 primary key 和 foreign key 等。

create table stu(sno int not null unique, sex char(6), departnum int, sname char(10), primary key(sno), foreign key(departnum) references depart (departnum));

8.2.2 修改表 (alter table)

ALTER TABLE[ADD<新列名[完整性约束条件]]
[DROP]
[MODIFY];

alter table stu add telephone char(11);alter table stu modify sno char(6);

8.2.3 删除表 (drop table)

DROP TABLE 

drop table stu;

8.2.4 索引

【索引的作用】
（1）通过创建唯一索引，可以保证数据记录的唯一性。
（2）可以大大加快数据检索速度。
（3）可以加速表与表之间的连接，这一点在实现数据的参照完整性方面有特别的意义。
（4）在使用ORDERBY和GROUP BY子句中进行检索数据时，可以显著减少查中分组和排序的时间。
（5）使用索引可以在检索数据的过程中使用优化隐藏器，提高系统性能。

  • 索引分为聚集索引和非聚集索引。聚集索引是指索引表中索引项的顺序与表中记录的物理顺序一致的索引。

创建索引
CREATE [UNIQUE] [CLUSTER] INDEX ON([][，[次序>]]… ) ;

●次序：可选ASC (升序) 或DSC (降序) ，默认升序。
●UNIQUE：表明此索引的每一个索引值只对应唯一的数据记录。
●CLUSTER：表明要建立的索引是聚簇索引，索引项的顺序是与表中记录的物理顺序一致的索引组织。

删除索引
DROPINDEX

8.2.5 视图

视图不是真实存在的基本表，而是一个虚拟表，视图所对应的数据并不实际地以视图结构存储在数据库中，而是存储在视图所引用的表中。使用视图的优点和作用如下：
（1）可以使视图集中数据、简化和定制不同用户对数据库的不同数据要求。
（2）使用视图可以屏蔽数据的复杂性，用户不必了解数据库的结构，就可以方便地使用和管理数据简化数据权限管理和重新组织数据以便输出到其他应用程序中。
（3）视图可以使用户只关心他感兴趣的某些特定数据和所负责的特定任务，而那些不需要的或者无用的数据则不在视图中显示。
（4）视图大大地简化了用户对数据的操作
（5）视图可以让不同的用户以不同的方式看到不同或者相同的数据集。
（6）在某些情况下，由于表中数据量太大因此在表的设计时常将表进行水平或者垂直分割，但表的结构的变化对应用程序产生不良的影响。
（7）视图提供了一个简单而有效的安全机制。

创建视图

CREATE VIEW 视图名(列表名)
ASSELECT 查询子句[WITH CHECK OPTION];

  • 子查询可以是任意复杂的 select 语句，但通常不允许含有 order by 和distinct。ewith check option 表示执行 update、insert、delete 操作时保证更新、插入、删除的行满足视图定义中的条件。“
  • 组成视图的属性列名或者全部省略或者全部指定。如果省略属性列名，则隐含该视图由 select子查询目标列的主属性组成。
create view cs-stu as select * from stu where depart='cs' with check option;

删除视图

drop view 视图名

drop view cs-stu;

8.3 数据操作

8.3.1 查询语句格式

SELECT [ALL | DISTINCT] [目标列表达式>]..
FROM [，]
[WHERE]
[GROUPBY[HAVING]]
[ORDER BY[ASC|DESC]…]

  • SOL查询中的子句顺序为SELECT、FROM、WHERE、GROUP BY、HAVING 和ORDER BY其中，SELECT、FROM 是必须的，HAVING条件子只能与GROUP BY搭配起来使用。
    （1）SELECT子句对应的是关系代数中的投影运算，用来列出查询结果中的属性。其输出可以是列名表达式、集函数(AVG、COUNT、MAX、MIN、SUM)，DISTINCT选项可以保证查询的结果集中不存在重复元组。
    （2）FROM子句对应的是关系代数中的笛卡儿积，它列出的是表达式求值过程中需扫描的关系，即在FROM子句中出现多个基本表或视图时，系统首先执行笛卡儿积操作。
    （3）WHERE子句对应的是关系代数中的选择谓词。WHERE 子句的条件表达式中可以使用的运算符如表所示。
  • 简单查询：只涉及一张表。查询计算机系学生的学号和姓名。
    select sno,sname from stu where depart='CS‘;

  • 连接查询：查询涉及两个以上的表。查询选修了课程号为C1的学生号和学生姓名。

    select sno,sname from SSC where S.sno=SCsno and SCcno='C1';
  • 子查询：也称为嵌套查询，是指一个select-from-where查询块可以嵌入另一个查询块之中，SQL中允许多重嵌套。查询选修了课程号为C1的学生号和学生姓名。
    select sno,sname from S where sno in (select sno from SC where cno=’ C1');

  • 聚集函数：是以一个值的集合为输入，返回单个值的函数，SQL提供的聚集函数如下：

  • 使用ANY和ALL谓词必须同时使用比较运算符用聚集函数实现子查询通常比直接用ALL或ANY查询效率更高，二者等价转换如下：

8.3.2 分组查询

●group by[having ]；
●group by 按某一列分组，一般只能select分组的列以及使用聚集函数
●在group by子句后面加一个having子句，对分组设置过滤条件，可以使用聚集函数，注意：
●空值在任何聚集操作中都会被忽视，如求和、求平均值和计数都没有影响，如count(*)是某个关系中所有元组数组之和，但count(A)却是A属性非空的元组个数之和。
●NULL值可以看做分组属性中的一个一般的值，例如，在select A,avg(B) from R中，当A的属性值为空时，就会统计A=NULL的所有元组中B的均值。
●查找订单总金额小于2000的客户：

select customer, sum(orderPrice) from orders group by customer having sum(orderPrice) <2000；

8.3.3其他操作

  • 更名操作(as子句: ld name as new-name既可以出现在select子句中，也可以出现在from子句中select sname as 姓名, sage as 年 from S where SD=’ CS’;
  • 字符串操作作对于字符串进行的最通用的操作时使用操作符like的模式匹配，使用两个特殊的字符描述：
    %：匹配任意字符串
    _：匹配任意一个字符模式是大小写敏感的，例如zhang%,mary_ 等。
    select sname from S where saddress like ‘%张江%’;
  • 集合操作：在关系代数中用集合的并、交、差来组合关系，SQL提供了对应的操作，但是查询的结果必须具有相同的属性和类型列表。保留字union、intersect、 except分别对应并、交、差；
  • 查询选修了180101号或180102号课程或二者都选修了的学生学号、课程号和成绩。
    (SELECT学号课程号,成绩 FROM学习WHERE 课程号=180101)UNION
    (SELECT学号课程号成绩 FROM学习WHERE 课程号=180102)
    ●UNION运算自动去除重复。如果想保留所有的重复，则必须用UNION ALL代替UNION,目查询结果中出现的重复元组数等于两个集合中出现的重复元组数的和。
  • 查询同时选修了180101和180102号课程的学生学号、课程号和成绩。
    (SELECT学号,课程号,成绩 FROM学习 WHERE 课程号=180101) INTERSECT
    (SELECT学号课程号,成绩 FROM学习 WHERE 课程号=180102)
    ●INTERSECT运算自动去除重复，如果想保留所有的重复，必须用INTERSECT ALL代替●INTERSECT结果中出现的重复元组数等于两集合出现的重复元组数里较少的那个。
  • 查询选修了180101号课程的学生中没有选修180102号课程的学生学号、课程号和成绩(SELECT学号课程号,成绩FROM学习WHERE课程号=180101)EXCEPT
    (SELECT学号课程号,成绩 FROM学习WHERE 课程号=180102)
    ●EXCEPT运算自动去除重复，如果想保留所有的重复，必须用EXCEPT ALL代替EXCEPT，结果中出现的重复元组数等于两集合出现的重复元组数之差(前提是差是正值)

SQL对视图更新必须遵循以下规则：
（1）从多个基本表通过连结操作导出的视图不允许更新。
（2）对使用了分组、集函数操作的视图则不允许进行更新操作。
（3）如果视图是从单个基本表通过投影、选取操作导出的则允许进行更新操作，且语法同基本表。

  • 和过程定义不同的是Create view子句会在数据库中建立视图定义，该视图定义会一直保存，直到执行drop view 命令。但是，with子句提供了定义一个临时视图的方法，该定义只对with子句出现的那条查询有效。
  • 插入insert
    INSERTINTO 表名称 VALUES(值1值2,….)INSERTINTO table name(列1,列2…) VALUES (值1, 值2….)INSERT INTO Persons VALUES (GatesBill，Xuanwumen 10Beijing)INSERT INTO Persons (LastName, Address) VALUES (WilsonChamps-Elysees’)
  • 删除delete
    DELETE FROM 表名称WHERE 列名称=值DELETE FROM Person WHERE LastName=Wilson’
  • 更新update
    UPDATE 表名称SET 列名称=新值WHERE列名称=某值UPDATE Person SET FirstName =Fred’ WHERE LastName = Wilson’

8.3.4约束

  • 主键约束primary key
  • 完整性约束条件作用的对象有关系、元组和列

  • 完整性控制具有的功能:定义功能、检测功能和处理功能。
  • 检查是否违背完整性约束的时机有两种: 在一条语句执行完后立即检查称为立即执行约束;需要延到整个事务执行完后再检查称为延迟执行约束。
  • 实体完整性:关系中只能由一个主键，声明主键有两种方法；
  • 属性类型后加primary key 保留字；
  • 在属性列表的最后增加一行primary key(属性或属性组)

外键约束foreign key
参照完整性定义格式：
foreign key(属性名)references 表名(属性)[on delete cascade set nullj；
references指明外键对应于哪个表的主键；
on delete cascade指明删除被参照关系的元组时，同时删除参照关系中的元组:
set null表示空值。

属性值上的约束，属性值上的约束通过下面关键字进行
not null：不允许空值
unique：唯一值
check：属性值要满足指定条件

create table students (sno char(8)not null unique,sname char(10),sage int,sdept char(20),primary key(sno),foreign key(sdept) references D(dept),check(sage >=15 and sage <= 22))

8.4 数据授权

8.4.1 授权grant

GRANT[]… [ON)TO[，]…[WITH GRANT OPTION]

  • 若指定了WITH GRANT OPTION子句，那么获得了权限的用户还可以将权限赋给其他用户: 接受权限的用户可以是单个或多个具体的用户，PUBLIC参数可将权限赋给全体用户。不同类型的操作对象有不同的操作权限，常见的操作权限如表所示。

grant all privileges on table S,PJ to user1, user2;grant insert on table S to user1 with grant option;

8.4.2 收回权限revoke

REVOKE[，]… [ON]FROM[，]… ;

revoke all privileges on table S,PJ from user1,user2;revoke select on table S from user1;

8.5 触发器

  • 触发器和存储过程
    ●触发器trigger是与表事件相关的特殊的存储过程，它的执行不是由程序调用，也不是手工启动，而是由事件来触发。
    ●触发器经常用于加强数据的完整性约束和业务规则等;
    ●触发器与存储过程的唯一区别是触发器不能执行execute语句调用，而是在用户执行transact-SQl语句时自动触发执行。
    ●存储过程：是在大型数据库系统中，一组为了完成特定功能的SQL 语句集，存储在数据库中，经过第一次编译后再次调用不需要再次编译，用户通过指定存储过程的名字并给出参数(如果该存储过程带有参数)来执行它。
  • 触发器为数据库对象，当创建一个触发器时必须指定：
    （1）名称；
    （2）在其上定义触发器的表；
    （3）触发器将何时激发;
    （4）指明触发器执行时应做的动作。
  • 触发动作实际上是一系列SQL语句，可以有两种方式：
    （1）对被事件影响的每一行(FOR EACH ROW)-每一元组执行触发过程，称为行级触发器。（2）对整个事件只执行一次触发过程(FOREACHSTATEMENT)，称为语级触发器。该方式是触发器的默认方式。
  • 触发器的定义包括两个方面:指明触发器的触发事件，指明触发器的执行动作。

创建触发器：
（1）BEFORE:指示DBMS在执行触发语之前激发触发器
（2）AFTER:指示DBMS在执行触发语之后激发触发器。
（3）DELETE:每当一个DELETE语从表中删除一行时激发触发器。
（4）INSERT:每当一个时SERT 语句向表中插入一行时激发触发器
（5）UPDATE:每当UPDATE 语修改由OF子指定的列值时，激发触发器。如果忽略OF子，每当UDPATE 语修改表的任何列值时DBMS都将激发触发器
（6）REFERENCING:指定临时视图的别名。在触发器运行过程中，系统会生成两个临时视图，分别存放被更新值 (旧值)和更新后的值(新值》。对于行级触发器，默认临时视图名分别是OLD 和NEW (oracle，在MS中，为Deleted,Inserted) ;对于语句级触发器，默认临时视图名分别是OLD-TABLE和NEW-TABLE。一旦触发器运行结束，临时视图就不在。
（7）WHEN:指定触发器的触发条件。当满足触发条件时，DBMS才激发触发器。触发条件中必须包含临时视图名，不包含查询。

CREATE TRIGGERLBEFORE |AFTER)([DELETE |INSERT | UPDATEOF [列名清单]])ON表名
[REFERENCING][WHEN]
BEGIN

END[触发器名]

【修改触发器】
ALTER TRIGGER [(BEFORE | AFTER]([DELETE | INSERTIUPDATEOF[列名清单]])
ON表名 | 视图名
AS
BEGIN
要执行的SQL语句
END

【删除触发器】
drop trigger trigger name

8.6 嵌入式SQL

  • 将SQL语言嵌入到高级程序设计语言中使用
    1.区分主语言语句与SQL 语句：
    ●为了区分主语言语句与SQL 语句，需要在所有的SQl语句前加前缀EXEC SQL，而SQL的结束标志随主语言的不同而不同
    ●例如，PL/1和C语言的引用格式为: EXEC SQLSQL 语句>;
    ●又如，COBOL语言的引用格式为: EXEC SQLEND-EXEC。
    2.主语言工作单元与数据库工作单元通信：
    1)SQL 通信区SQL通信区向主语言传递SQL 语句执行的状态信息使主语言能够根据此信息控制程序流程。
    2)主变量
  • 主变量也称共享变量。主语言向SQL语句提供参数主要通过主变量，主变量由主语言的程序定义，并用SQL的DECLARE语句说明。例如在C语言中可用如下形式说明主变量
  • 【游标】
    一条SQL 语句可产生或处理多条记录。而主语言是面向记录的，一组主变SQL 语言是面向集合的量一次只能放一条记录，所以，引入游标，i通过移动游标指针来决定获取哪一条记录。与游标相关的SQL语句有四条：
    (1)定义游标，格式如下
    EXEC SOL DECLARE CURSOR FOR

    END EXEC
    这是一条说明性语句，定义中的 SELECT 语句并不立即执行。
    (2) 打开游标，格式如下:
    EXEC SQL OPEN END EXEC
    该语句执行游标定义中的 SELECT 语句，同时游标处于活动状况。游标是一个指针，此时指向查询结里的第一行之前。
    (3)推进游标，格式如下
    EXEC SQLFETCH FROMINTOENDEXEC该语句使用时，游标推进一行，并把游标指向的行(称为当前行)中的值取出，送到共享变量中。变量表由用逗号分开的共享变量组成。该语句常置于宿主语言程序的循环结构中。
    (4)关闭游标，格式如下:EXEC SQLCLOSEEND EXEC该语句关闭游标，使它不再和查询结果相联系。关闭了的游标，可以再次打开，与新的查询结果相联系。

第九章 非关系型数据库NOSQL

9.1 概述

  • 传统的关系数据库在应付Web 2.0网站，特别是超大规模和高并发的SNS类型的Web2.0纯动态网站方面已经显得力不从心，暴露了很多难以克服的问题，主要包括以下几个方面。
    1)对数据库高并发读写的需求；
    2)对海量数据的高效率存储和访问的需求；
    3)对数据库的高可扩展性和高可用性的需求。

9.2 理论基础

  • CAP原则又称CAP定理，指的是在一个分布式系统中，Consistency(一致性)、Availability (可用性)、Partition tolerance (分区容错性)，三者最多只能得其二。
  • 一致性(C): 在分布式系统中的所有数据备份，在同一时刻是否同样的值。 (等同于所有节点访问同一份最新的数据副本)
  • 可用性 (A): 在集群中一部分节点故障后，集群整体是否还能响应客户端的读写请求。(对数据更新具备高可用性)
  • 分区容忍性(P):以实际效果而言，分区相当于对通信的时限要求。系统如果不能在时限内达成数据一致性，就意味着发生了分区的情况，必须就当前操作在C和A之间做出选择。
  • 由于CAP 理论的存在，为了提高性能，出现了ACID 的一种变种BASE: Basically Available(基本可用)，Soft state (软状态) 和 Eventually consistent (最终一致性)。
  • Base理论核心思想是:既然无法做到强一致性，但每个应用都可以根据自身的业务特点，采用适当的方式来使系统达到最终一致性。
  • 基本可用：系统出现了不可预知的故障，但相比较于正常系统还是能用的。
  • 软状态:允许系统中的数据存在中间状态，并认为该状态不影响系统的整体可用性，即允许系统在多个不同节点的数据副本存在数据延时。
  • 最终一致性:系统能够保证在没有其他新的更新操作的情况下，数据最终一定能够达到一致的状态，因此所有客户端对系统的数据访问最终都能够获取到最新的值。
  • 具体地说，如果选择了CP (一致性和分区容忍性)，那么就要考虑ACID 理论如果选择了AP (可用性和分区容忍性)那么就要考虑BASE 系统。如果选择了CA(一致性和可用性)，那么在网络发生分区的时候，将不能进行完整的操作。

9.3 分区方法

（1）内存缓存:缓存技术可以看成一种分区。内存中的数据库系统将使用频率最高的数据复制到缓存中，加快了数据给用户传递的速度，同时也大大减轻了数据库服务器的负担。
（2）集群:数据库服务器集群在为用户提供服务时的透明性(用户感觉数据像是在同一个地2是另外一个对数据进行分区的方法。
（3）读写分离: 指定一台或多台主服务器，所有或部分的写操作被送至此，同时再设一定数量的副本服务器用以满足读请求。
（4）范围分割技术/分片(sharding): 指对数据按照如下方式进行分区操作，即对数据的请求和更新在同一个结点上，并且对于分布在不同服务器上的数据存储和下载的量大致相同。

9.4 存储分布

  1. 行存储和列存储：两者之间的主要区别在于，行存储将每条记录的所有字段的数据聚合存储而列存储将所有记录中相同字段的数据聚合存储。行存储主要适用于OLTP，或者更新操作，尤其是插入、删除操作频繁的场合: 而列存储主要适用于OLAP，数据仓库，数据挖掘等查询密集型应用。
  2. 带有局部性群组的列存储:是指根据需要将原来不存储在一起的数据，以列族为单位存储至单独的字表中。如用户对网站排名、语言等分析信息感兴趣，那么可以将这些列族放在单独的子表减少无用信息读取，改善存取效率。
  3. LSM-Tree：日志结构合并树，与前面介绍的存储结构有所不同，前面的存储结构在描述如何序列化逻辑数据结构，而LSM-Tree 描述的则是为了满足高效、高性能、安全地读写的要求，如何有效地利用内存和磁盘存储。主要用于解决日志记录索引的问题

9.5查询模型

  1. 结合SQL 数据库:一个最直接的方式是通过将NOSQL 数据库拷贝到关系数据库或者文本数据库来提供查询能方。
  2. 分散/集合本地搜索:一些NOSQL数据库提供本地数据库内的索引和查询处理机制。在这种情况下，我们可以让查询处理器将查询广播到DHT(分散哈希表)中的所有节点，在每个节点上将会执行查询，并将结果送回到查询处理器，然后查询处理器将结果聚集成一个单一响应。
  3. 分布式B十树:其基本思路是为了定位B+树的根节点哈希要搜索的属性。根节点的“值”包含其孩子节点的ID。
  4. 前缀哈希表/分布式Trie:前缀哈希表 (Prefix Hash Table, PHT，又名分布式Trie) 目的是一个树形数据结构。在这个树形结构中，从根节点到叶子的每一条路径上均包含了键值的前缀，并且每个Trie中的节点都包含了它是谁的前缀的所有数据。

9.6 存储模式

其他存储模式：
（1）多值数据库:是分布式数据库系统的重要分支。它速度快，体积小，比关系数据库便宜，很快得到了认可。它提供了一个通用的数据集成与访问平台，屏蔽了现有各数据库系统不同的访问方法和用户界面，给用户呈现出一个访问多种数据库的公共接口。多值数据库系统使用的多个异构的数据源之间可以共享它们相互依赖的数据，并具有相互操作的能力。常见的多值数据库有Rocket U2, Extensible Storage Engin (ESE/NT)、OpenInsight 和OpenQM等。
（2）时间序列与流数据库:时间序列数据库是指具有处理时间序列数据，能对时间数据数组建立索引的优化数据库系统。流数据库又被称为实时数据库，这是一种使用实时处理数据的方式来处理状态不断变化的数据库系统。对时间序列的数据库提出实时的处理要求，那么时间数据库就是流数据库。常见的时间序列数据库InfluxDB、OpenTSDBo。
（3）网格和云数据库:是基于网格计算或者云计算的数据库。

第十章 系统开发与运行

10.1 系统实施

10.1.1 信息系统生命周期

  • 软件工程基本原理：用分阶段的生命周期计划严格管理、坚持进行阶段评审、实现严格的产品控制采用现代程序设计技术、结果应能清楚的审查、开发小组的人员应少而精、承认不断改进软件工程实践的必要性。
  • 软件工程的基本要素：方法、工具、过程。
  • 软件生存周期：可行性分析与项目开发计划、需求分析、概要设计(选择系统解决方案，规划子系统)、详细设计(设计子系统内部具体实现)、编码、测试、维护。

  1. 系统规划阶段：任务是对组织的环境、目标及现行系统的状况进行初步调查，根据组织目标和发展战略确定信息系统的发展战略，对建设新系统的需求做出分析和预测，同时考虑建设新系统所受的各种约束，研究建设新系统的必要性和可能性。根据需要与可能，给出制建系统的备选方案输出：可行性研究报告、系统设计任务书。
  2. 系统分析阶段：任务是根据系统设计任务书所确定的范围，对现行系统进行详细调查，描述现行系统的业务流程，指出现行系统的局限性和不足之处，确定新系统的基本目标和逻辑功能要求，即提出新系统的逻辑模型。系统分析阶段又称为逻辑设计阶段。这个阶段是整个系统建设的关键阶段，也是信息系统建设与一般工程项目的重要区别所在。输出：系统说明书
  3. 系统设计阶段：系统分析阶段的任务是回答系统“做什么”的问题，而系统设计阶段要回答的问题是“怎么做”。该阶段的任务是根据系统说明书中规定的功能要求，具体设计实现逻辑模型的技术方案，也就是设计新系统的物理模型。这个阶段又称为物理设计阶段，可分为总体设计(概要设计)和详细设计两个子阶段。输出：系统设计说明书 (概要设计、详细设计说明书)
  4. 系统实施阶段：是将设计的系统付诸实施的阶段。这一阶段的任务包括计算机等设备的购置、安装和调试程序的编写和调试、人员培训、数据文件转换、系统调试与转换等。这个阶段的特点是几个互相联系、互相制约的任务同时展开，!必须精心安排、合理组织。系统实施是按实施计划分阶段完成的，每个阶段应写出实施进展报告。系统测试之后写出系统测试分析报告输出:实施进展报告、系统测试分析报告。
  5. 系统运行和维护阶段：系统投入运行后，需要经常进行维护和评价，记录系统运行的情况，根据一定的规则对系统进行必要的修改，评价系统的工作质量和经济效益。

10.1.2 能力成熟度模型

【能力成熟度模型集成CMMI】
是若干过程模型的综合和改进不仅仅软件，而是支持多个工程学科和领域的系统的、致的过程改进框架能适应现代工程的特点和需要，能提高过程的质量和工作效率。
CMMI两种表示方法：
（1）阶段式模型：类似于CMM，它关注组织的成熟度，五个成熟度模型如下：

10.1.3 软件过程开发模型

【瀑布模型】
瀑布模型(SDLC)：瀑布模型是一个经典的软件生命周期模型一般将软件开发分为:可行性分析 (计划)、需求分析、软件设计 (概要设计、详细设计)、编码 (含单元测试)、测试、运行维护等几个阶段。
瀑布模型特点：
（1）从上一项开发活动接受该项活动的工作对象作为输入；
（2）利用这一输入，实施该项活动应完成的工作内容；
（3）给出该项活动的工作成果，作为输出传给下一项开发活动。
（4）对该项活动的实施工作成果进行评审。若其工作成果得到确认，则继续进行下一项开发活动；否则返回前一项，甚至更前项的活动。尽量减少多个阶段间的反复。以相对来说较小的费用来开发软件。

【螺旋模型】

  • 螺旋模型是一个演化软件过程模型，将原型实现的迭代特征与线性顺序(瀑布)模型中控制的和系统化的方面结合起来。在螺旋模型中，软件开发是一系列的增量发布。
  • 开发过程具有周期性重复的螺旋线状。四个象限分别标志每个周期所划分的四阶段:制订计划、风险分析、实施工程和客户评估。螺旋模型强调了风险分析，特别适用于庞大而复杂的、高风险的系统。

【V模型】

  • V模型从整体上看起来，就是一个V字型的结构，由左右两边组成。左边的下画线分别代表了需求分析、概要设计、详编码。右边的上画线代表了单元测试、集成测试细设计、系统测试与验收测试。v模型的特点如下：
    （1）单元测试的主要目的是针对编码过程中可能存在的各种错误；
    （2）集成测试的主要目的是针对详细设计中可能存在的问题；
    （3）系统测试主要针对概要设计，检查系统作为一个整体是否有效地得到运行；
    （4）验收测试通常由业务专家或者用户进行，以确认产品能真正符合用户业务上的需要；
    （5）V模型用于需求明确和需求变更不频繁的情形。

【原型化模型】

  • 原型化模型第一步就是创建一个快速原型能够满足项目千系人与未来的用户可以与原型进行交互，再通过与相关干系人进行充分的讨论和分析，最终弄清楚当前系统的需求，进行了充分的了解之后，在原型的基础上开发出用户满意的产品。原型法认为在很难一下子全面准确地提出用户需求的情况下，原型应当具备的特点如下：
    （1）实际可行；
    （2）具有最终系统的基本特征；
    （3）构造方便、快速，造价低。原型法的特点在于原型法对用户的需求是动态响应、逐步纳入的。

【增量模型】

  • 增量模型：首先开发核心模块功能，而后与用户确认，之后再开发次核心模块的功能，即每次开发一部分功能并与用户需求确认，最终完成项目开发优先级最高的服务最先交付。
  • 特点：但由于并不是从系统整体角度规划各个模块，因此不利于模块划分难点在于如何将客户需求划分为多个增量。与原型不用的是增量模型的每一次增量版本都可作为独立可操作的作品，而原型的构造一般是为了演示。

【其他模型】

  • 喷泉模型：是一种以用户需求为动力，以对象作为驱动的模型，适合于面向对象的开发方法。使开发过程具有迭代性和无间隙性。
  • 基于构件的开发模型CBSD：利用预先包装的构件来构造应用系统。构件可以是组织内部开发的构件，也可以是商品化成品软件构件。特点是增强了复用性，在系统开发过程中，会构建一个构件库，供其他系统复用，因此可以提高可靠性，节省时间和成本
  • 形式化方法模型：建立在严格数学基础上的一种软件开发方法，主要活动是生成计算机软件形式化的数学规格说明。

10.1.4 信息系统开发方法

【结构化方法】

  • 结构是指系统内各个组成要素之间的相互联系、相互作用的框架。
  • 结构化方法也称为生命周期法，是一种传统的信息系统开发方法，由结构化分析 (Structured Analysis,SA) 、结构化设计 (Structured Design, SD) 和结构化程序设计 (Structured Programming，SP)三部分有机组合而成，其精髓是自顶向下、逐步求精和模块化设计。
  • 结构化方法的主要特点：
    （1）开发目标清晰化。结构化方法的系统开发遵循“用户第一”的原则；
    （2）开发工作阶段化。每个阶段工作完成后，要根据阶段工作目标和要求进行审查，这使各阶段工作有条不紊地进行，便于项目管理与控制；
    （3）开发文档规范化。结构化方法每个阶段工作完成后，要按照要求完成相应的文档，以保证各个工作阶段的衔接与系统维护工作的遍历；
    （4）设计方法结构化。在系统分析与设计时，从整体和全局考虑，自顶向下地分解，在系统实现时，根据设计的要求，先编写各个具体的功能模块，然后自底向上逐步实现整个系统。
  • 结构化方法的不足和局限：
    (1)开发周期长：按顺序经历各个阶段，直到实施阶段结束后，用户才能使用系统；
    (2) 难以适应需求变化：不适用于需求不明确或经常变更的项目；
    (3)很少考虑数据结构：结构化方法是一种面向过程，面向数据流的开发方法，很少考虑数据结构。
  • 结构化方法常用工具：结构化方法一般利用图形表达用户需求，常用工具有数据流图、数据字典、结构化语言、判定表以及判定树等.。

【面向对象方法】

  • 面向对象 (Object-Oriented，OO)方法认为，客观世界是由各种对象组成的，任何事物都是对象，每一个对象都有自己的运动规律和内部状态，都属于某个对象类，是该对象类的一个元素。复杂的对象可由相对简单的各种对象以某种方式而构成，不同对象的组合及相互作用就构成了系统。
  • 面向对象方法的特点：
    (1)使用OO方法构造的系统具有更好的复用性，其关键在于建立一个全面合理、统一的模型(用例模型和分析模型)。
    (2)OO方法也划分阶段，但其中的系统分析、系统设计和系统实现三个阶段之间已经没有“缝隙”。也就是说，这三个阶段的界限变得不明确，某项工作既可以在前一个阶段完成，也可以在后一个阶段完成;前一个阶段工作做得不够细，在后一个阶段可以补充。
    (3)面向对象方法可以普遍适用于各类信息系统的开发。
  • 面向对象方法的不足之处必须依靠一定的面向对象技术支持在大型项目的开发上具有一定的局限性不能涉足系统分析以前的开发环节。
  • 当前，一些大型信息系统的开发，通常是将结构化方法和OO方法结合起来首先，使用结构化方法进行自顶向下的整体划分;然后，自底向上地采用OO方法进行开发。因此，结构化方法和OO方法仍是两种在系统开发领域中相互依存的、不可替代的方法。

【原型化方法】

  • 原型化方法也称为快速原型法，或者简称为原型法。它是一种根据用户初步需求，利用系统开发工具，快速地建立一个系统模型展示给用户，在此基础上与用户交流，最终实现用户需求的信息系统快速开发的方法。
  • 按是否实现功能分类:分为水平原型(行为原型，功能的导航)、垂直原型(结构化原型，实现了部分功能)。
  • 按最终结果分类:分为抛弃式原型、演化式原型。

  • 原型法的特点：
    原型法可以使系统开发的周期缩短成本和风险降低、速度加快，获得较高的综合开发效益。
    原型法是以用户为中心来开发系统的，用户参与的程度大大提高，开发的系统符合用户的需求，因而增加了用户的满意度，提高了系统开发的成功率。由于用户参与了系统开发的全过程，对系统的功能和结构容易理解和接受，有利于系统的移交，有利于系统的运行与维护。
  • 原型法的不足之处：开发的环境要求高。管理水平要求高。
  • 由以上的分析可以看出，原型法的优点主要在于能更有效地确认用户需求。从直观上来看，原型法适用于那些需求不明确的系统开发。事实上，对于分析层面难度大、技术层面难度不大的系统，适合于原型法开发。
  • 从严格意义上来说，目前的原型法不是一种独立的系统开发方法，而只是一种开发思想，它只支持在系统开发早期阶段快速生成系统的原型，没有规定在原型构建过程中必须使用哪种方法。因此，它不是完整意义上的方法论体系。这就注定了原型法必须与其他信息系统开发方法结合使用。

【敏捷开发】

  • 敏捷开发是一种以人为核心、迭代、循序渐进的开发方法，相对于传统软件开发方法的“非敏捷”，更强调程序员团队与业务专家之间的紧密协作、面对面的沟通 (认为比书面的文档更有效)、频繁交付新的软件版本、紧凑而自我组织型的团队、能够很好地适应需求变化的代码编写和团队组织方法，也更注重软件开发中人的作用
  • 敏捷软件开发宣言：
    （1）个体和交互胜过过程和工具；
    （2）可以工作的软件胜过面面俱到的文档；
    （3）客户合作胜过合同谈判；
    （4）响应变化胜过遵循计划。

  • 结对编程：个程序员开发，另一个程序在一旁观察审查代码，能够有效的提高代码质量在开发同时对代码进行初步审查，共同对代码负责。
  • 自适应开发：强调开发方法的适应性 (Adaptive)。不象其他方法那样有很多具体的实践做法，它更侧重为软件的重要性提供最根本的基础，并从更高的组织和管理层次来阐述开发方法为什么要具备适应性。
  • 水晶方法：每一个不同的项目都需要一套不同的策略、约定和方法论。
  • 特性驱动开发：是一套针对中小型软件开发项目的开发模式。是一个模型驱动的快速迭代开发过程，它强调的是简化、实用、易于被开发团队接受，适用于需求经常变动的项目。
  • 极限编程XP：核心是沟通、简明、反馈和勇气。因为知道计划永远赶不上变化，XP无需开发人员在软件开始初期做出很多的文档。XP提倡测试先行，为了将以后出现bug的几率降到最低。
  • 并列争球法SCRUM：是一种迭代的增量化过程，把每段时间 (30天) 一次的，并按需求的优先级别来实现产品，多个自组织和自治迭代称为一个“冲刺”的小组并行地递增实现产品。
  • 统一过程(RUP)提供了在开发组织中分派任务和责任的纪律化方法。它的目标是在可预见的日程和预算前提下，确保满足最终用户需求的高质量产品。
    • 3个显著特点：用例驱动、以架构为中心、迭代和增量。
    • 4个流程:初始阶段、细化阶段、构建阶段和交付阶段。每个阶段结束时都要安排一次技术评审，以确定这个阶段的目标是否已经达到。
    • 适用：一个通用过程框架，可以用于种类广泛的软件系统、不同的应用领域不同的组织类型、不同性能水平和不同的项目规模。

10.1.5 系统分析与设计

  • 系统分析过程一般按如图所示的逻辑进行：
    （1）认识、理解当前的现实环境，获得当前系统的“物理模型”；
    （2）从当前系统的“物理模型”抽象出当前系统的“逻辑模型”；
    （3）对当前系统的“逻辑模型”进行分析和优化，建立目标系统的“逻辑模型”；
    （4）对目标系统的逻辑模型具体化(物理化)，建立目标系统的物理模型。
  • 系统开发的目的是把现有系统的物理模型转化为目标系统的物理模型，即图中所描述的路径，而系统分析阶段的结果是得到目标系统的逻辑模型。逻辑模型反映了系统的功能和性质，而物理模型反映的是系统的某一种具体实现方案。

  • 系统设计基本原理:抽象(模块化信息隐蔽、模块独立。衡量模块独立程度的标准有两个:耦合性和内聚性。内聚程度从低到高如下表：

  • 耦合程度从低到高如下表所示：

  • 系统总体结构设计是要根据系统分析的要求和组织的实际情况对新系统的总体结构形式和可利用的资源进行大致设计，这是一种宏观、总体上的设计和规划。
  • 系统结构设计原则
    （1）分解-协调原则。
    （2）自顶向下的原则。
    （3）信息隐蔽、抽象的原则。
    （4）一致性原则。
    （5）明确性原则。
    （6）模块之间的耦合尽可能小，模块的内聚度尽可能高。
    （7）模块的扇入系数和扇出系数要合理。
    （8）模块的规模适当
  • 子系统划分的原则：
    （1）子系统要具有相对独立性。
    （2）子系统之间数据的依赖性尽量小。
    （3）子系统划分的结果应使数据冗余较小。
    （4）子系统的设置应考虑今后管理发展的需要。
    （5）子系统的划分应便于系统分阶段实现。
    （6）子系统的划分应考虑到各类资源的充分利用。
  • 子系统结构设计的任务是确定划分后的子系统模块结构，并画出模块结构图王这个过程中必须考虑以下几个问题。
    （1）每个子系统如何划分成多个模块。
    （2）如何确定子系统之间、模块之间传送的数据及其调用关系。
    （3）如何评价并改进模块结构的质量。
    （4）如何从数据流图导出模块结构图。

【系统模块结构设计】

  • 模块是组成系统的基本单位，它的特点是可以组合、分解和更换。系统中的任何一个处理根据功能都可以看成是一个模块，具体化程度的不同，模块可以分为逻辑模块和物理功能。模块。个模块应具备以下4 个要素：
    （1）输入和输出。
    （2）处理功能。指模块把输入转换成输出所做的工作
    （3）内部数据。指仅供该模块本身引用的数据。
    （4）程序代码。指用来实现模块功能的程序。
    前两个要素是模块外部特性，反映了模块的外貌。后两个要素是模块的内部特性
  • 模块结构图为了保证系统设计工作的顺利进行，结构设计应遵循以下原则。
    （1）所划分的模块其内部的凝聚性要强，模块之间的联系要少，即模块具有较强的独立性。
    （2）模块之间的连接只能存在上下级之间的调用关系，不能有同级之间的横向联系。
    （3）整个系统呈树状结构，不允许网状结构或交叉调用关系出现。
    （4）所有模块(包括后继IPO图)都必须严格地分类编码并建立归档文件模块结构图主要关心的是模块的外部属性，即上下级模块、同级模块之间的数据传递和调并不关心模块的内部。

10.1.6 结构化开发

  • 结构化分析与设计方法是一种面向数据流的传统软件开发方法，它以数据流为中心构建软件的分析模型和设计模型。结构化分析(Structured Analysis，SA)结构化设计 (Structured Design，SD)和结构化程序设计 (StructuredProgramming Design，SPD)构成了完整的结构化方法。
    结构化方法的分析结果由以下几部分组成:一套分层的数据流图、一本数据词典、一组小说明 (也称加工逻辑说明) 、补充材料。

  1. 数据流：由一组固定成分的数据组成，表示数据的流向。在DFD 中，数据流的流向必须经过加工
  2. 加工：描述了输入数据流到输出数据流之间的变换，数据流图中常见的三种错误如图所示：
    加工3.1.2有输入但是没有输出，称之为“黑洞”；
    加工3.1.3有输出但没有输入。称之为“奇迹“；
    加工3.1.1中输入不足以产生输出，我们称之为“灰洞“。
  3. 数据存储：用来存储数据。
  4. 外部实体(外部主体)是指存在于软件系统之外的人员或组织，它指出系统所需数据的发源地(源)和系统所产生的数据的归宿地(宿)。

【分层数据流图】

【数据字典DD】
数据流图描述了系统的分解，但没有对图中各成分进行说明。数据字典就是为数据流图中的每个数据流、文件、加工，以及组成数据流或文件的数据项做出说明。
数据字典有以下4 类条目:数据流、数据项、数据存储和基本加工。

加工逻辑也称为“小说明”。常用的加工逻辑描述方法有结构化语言、判定表和判定树3 种。

  • 结构化设计(Structured Design，SD)方法是一种面向数据流的设计方法，它可以与SA方法衔接。结构化设计方法的基本思想是将系统设计成由相对独立功能单一的模块组成的结构。
  • 结构化设计方法中用结构图 (structure chart)来描述软件系统的体系结构指出一个软件系统由哪些模块组成，以及模块之间的调用关系。模块结构图是结构化设计的工具，由模块、调用、数据、控制和转接五种基本符号组成。
  • 结构化设计主要包括：
    （1）体系结构设计：定义软件的主要结构元素及其关系；
    （2）数据设计：基于实体联系图确定软件涉及的文件系统的结构及数据库的表结构描述用户界面，软件和其他硬件设备、其他软件系统及使用人员；
    （3）接口设计：的外部接口，以及各种构件之间的内部接口；
    （4）过程设计:确定软件各个组成部分内的算法及内部数据结构，并选定某种过程的表达形式来描述各种算法。

10.2 系统测试

10.2.1 测试原则和方法

  • 系统测试是为了发现错误而执行程序的过程，成功的测试是发现了至今尚未发现的错误的测试。
  • 测试原则：
    • 应尽早并不断的进行测试；
    • 测试工作应该避免由原:软件的人或小组承担；
    • 在设计测试方案时，不仅要确定输入数据，而且要根据系统功能确定预期的输出结果;
    • 既包含有效、合理的测试用例，也包含不合理、失效的用例;检验程序是否做了该做的事，且是否做了不该做的事;
    • 严格按照测试计划进行;
    • 妥善保存测试计划和测试用例:
    • 测试用例可以重复使用或追加测试。
  • 软件测试方法可分为静态测试和动态测试。
    • 静态测试:指被测试程序不在机器上运行，而采用人工检测和计算机辅助静态分析的手段对程序进行检测，包括对文档的静态测试和对代码的静态测试。对文档的静态测试主要以检查单的形式进行，而对代码的静态测试，包括桌前检查、代码审查、代码走查大方式。使用这种方法能够有效地发现30%-70%的逻辑设计和编码错误
    • 动态测试:指在计算机上实际运行程序进行软件测试，一般采用白盒测试和黑盒测试方法。
      黑盒测试法:功能性测试，不了解软件代码结构，根据功能设计用例，测试软件功能。
      白盒测试法:结构性测试，明确代码流程，根据代码逻辑设计用例，进行用例覆盖。

10.2.2 测试阶段

（1）单元测试：也称为模块测试，测试的对象是可独立编译或汇编的程序模块软件构件或OO软件中的类(统称为模块)，测试依据是软件详细设计说明书
（2）集成测试：目的是检查模块之间，以及模块和已集成的软件之间的接口关系，并验证已集成的软件是否符合设计要求。测试依据是软件概要设计文档。
（3）系统测试：测试对象是完整的、集成的计算机系统;测试的目的是在真实系统工作环境下验证完成的软件配置项能否和系统正确连接，并满足系统/子系统设计文档和软件开发合同规定的要求。测试依据是用户需求或开发合同。主要内容包括功能测试、健壮性测试、性能测试、用户界面测试、安全性测试安装与反安装测试等，其中，最重要的工作是进行功能测试与性能测试。功能测试主要采用黑盒测试方法;性能测试主要指标有响应时间、吞吐量、并发用户数和资源利用率等。
（4）确认测试：主要用于驰证软件的功能、性能和其他特性是否与用户需求-致。根据用户的参与程度，通常包括以下类型：
●内部确认测试：主要由软件开发组织内部按照SRS进行测试；
●Alpha测试：用户在开发环境下进行测试。用户在实际使用环境下进行测试，通过改测试后，产品才能交付用户；
●Beta测试：验收测试:针对SRS，在交付前以用户为主进行的测试。其测试对象为完整的、集成的计算机系统。验收测试的目的是，在真实的用户工作环境下，检验软件系统是否满足开发技术合同或SRS。
●验收测试的结论是用户确定是否接收该软件的主要依据。除应满足一般测试的准入条件外，在进行验收测试之前，应确认被测软件系统已通过系统测试。
（5）配置项测试:测试对象是软件配置项，测试目的是检验软件配置项与SRS的一致性。测试的依据是SRS。在此之间，应确认被测软件配置项已通过单元测试和集成测试。
（6）回归测试:测试目的是测试软件变更之后，变更部分的正确性和对变更需求的符合性，以及软件原有的、正确的功能、性能和其他规定的要求的不损害性。

  • 测试策略
    ●自底向上：从最底层模块开始测试需要编写驱动程序，而后开始逐一合并模块，最终完成整个系统的测试。优点是较早的验证了底层模块。
    ●自顶向下：先测试整个系统，需要编写桩程序，而后逐步向下直至最后测试最底层模块。优点是较早的验证了系统的主要控制和判断点
    ●三明治：既有自底向上也有自顶向下的测试方法，二者都包括。兼有二者的优点，缺点是测试工作量大。

10.2.3 测试用例设计

【黑盒测试用例】

  • 黑盒测试用例：将程序看做一个黑盒子，只知道输入输出，不知道内部代码由此设计出测试用例，分为下面几类:等价类划分:把所有的数据按照某种特性进行归类，而后在每类的数据里选取一个即可。
  • 等价类测试用例的设计原则:：设计一个新的测试用例，使其尽可能多地覆盖尚未被覆盖的有效等价类，重复这一步，直到所有的有效等价类都被覆盖为止;设计一个新的测试用例，使其仅覆盖一个尚未被覆盖的无效等价类，重复这一步，直到所有的无效等价类都被覆盖为止。
  • 边界值划分：将每类的边界值作为测试用例，边界值一般为范围的两端值以及在此范围之外的与此范围间隔最小的两个值，如年龄范围为0-150，边界值为0,150，-1,151四个。
  • 错误推测：没有固定的方法，凭经验而言，来推测有可能产生问题的地方作为测试用例进行测试。
  • 因果图：由一个结果来反推原因的方法，具体结果具体分析，没有固定方法

【白盒测试用例】

  • 白盒测试用例：知道程序的代码逻辑，按照程序的代码语句，来设计覆盖代码分支的测试用例，覆盖级别从低至高分为下面几种：
    (1)语句覆盖SC:逻辑代码中的所有语句都要被执行一遍，覆盖层级最低，因为执行了所有的语句，不代表执行了所有的条件判断。
    (2)判定覆盖DC: 逻辑代码中的所有判断语句的条件的真假分支都要覆盖一。

（3）条件覆盖CC：针对每一个判断条件内的每一个独立条件都要执行一遍真和假。
（4）条件判定组合覆盖CDC:：同时满足判定覆盖和条件覆盖。

（5）路径覆盖:逻辑代码中的所有可行路径都覆盖了，覆盖层级最高。

10.2.4 调试

  • 测试是发现错误，调试是找出错误的代码和原因。
  • 调试需要确定错误的准确位置;确定问题的原因并设法改正;改正后要进行回归测试。
  • 调试的方法有:蛮力法、回溯法 (从出错的地方开始，向回找)、原因排除法(找出所有可能的原因，逐一进行排除，具体包括演绎法、归纳法、二分法）。

10.2.5 软件度量

  • 软件的两种属性:外部属性指面向管理者和用户的属性，可直接测量一般为性能指标。内部属性指软件产品本身的的属性，如可靠性等，只能间接测量。
  • McCabe度量法:又称为环路复杂度，假设有向图中有向边数为m，节点数为n，则此有向图的环路复杂度为m-n+2。
  • 注意m和n代表的含义不能混淆，可以用一个最简单的环路来做特殊值记忆此公式，另外，针对一个程序流程图，每一个分支边(连线)就是一条有向边，每一条语句(语句框)就是一个顶点。

10.3 系统维护

10.3.1 系统转换

  • 遗留系统是指任何基本上不能进行修改和演化以满足新的变化了的业务需求的信息系统，它通常具有以下特点：
    （1）系统虽然完成企业中许多重要的业务管理工作，但仍然不能完全满足要求。一般实现业务处理电子化及部分企业管理功能，很少涉及经营决策。
    （2）系统在性能上已经落后，采用的技术已经过时。例如多采用主机/终端形式或小型机系统，软件使用汇编语言或第三代程序设计语言的早期版本开发，使用文件系统而不是数据库。
    （3）通常是大型的软件系统，已经融入企业的业务运作和决策管理机制之中，维护工作十分困难。
    （4）没有使用现代信息系统建设方法进行管理和开发，现在基本上已经没有文档，很难理解。

  • 系统转换是指新系统开发完毕，投入运行，取代现有系统的过程，，需要考虑多方面的问题，以实现与老系统的交接，有以下三种转换计划：
    （1）直接转换：现有系统被新系统直接取代了，风险很大，适用于新系统不复杂或者现有系统已经不能使用的情况。优点是节省成本。
    （2）并行转换：新系统和老系统并行工作一段时间，新系统经过试运行后再取代若新系统在试运行过程中有问题，也不影响现有系统的运行，风险极小，在试运行过程中还可以比较新老系统的性能，适用于大型系统。缺点是耗费人力和时间资源，难以控制两个系统间的数据转换。
    （3）分段转换：分期分批逐步转换，是直接和并行转换的集合，将大型系统分为多个子系统，依次试运行每个子系统，成熟一个子系统，就转换一个子系统。同样适用于大型项目，只是更耗时，而且现有系统和新系统间混合使用，需要协调好接口等问题。
  • 数据转换与迁移:将数据从旧数据库迁移到新数据库中。有三种方法:系统切换前通过工具迁移、系统切换前采用手工录入、系统切换后通过新系统生成。

10.3.2系统维护

  • 系统的可维护性可以定义为维护人员理解、改正、改动和改进这个软件的难易程度，其评价指标如下：
    (1)易分析性。软件产品诊断软件中的缺陷或失效原因或识别待修改部分的能力。
    (2)易改变性。软件产品使指定的修改可以被实现的能力，实现包括编码、设计和文档的更改。
    (3)稳定性。软件产品避免由于软件修改而造成意外结果的能力。
    (4)易测试性。软件产品使已修改软件能被确认的能力。
    (5)维护性的依从性。软件产品遵循与维护性相关的标准或约的能力。
  • 系统维护包括硬件维护、软件维护和数据维护，其中软件维护类型如下正确性维护：
    发现了bug而进行的修改；
    ●正确性维护：发现了bug而进行的修改。
    ●适应性维护：由于外部环境发生了改变，被动进行的对软件的修改和升级。
    ●完善性维护：基于用户主动对软件提出更多的需求，修改软件，增加更多的功能，使其比之前的软件功能、性能更高，更加完善。
    ●预防性维护：对未来可能发生的bug进行预防性的修改。

10.3.3系统评价

【系统评价分类】
立项评价：系统开发前的预评价，分析是否立项开发，做可行性评价。
中期评价：项目开发中期每个阶段的阶段评审。或者项目在开发中途遇到重大变故，评价是否还要继续。

  • 结项评价：系统投入正式运行后，了解系统是否达到预期的目的和要求而对系统进行的综合评价。系统评价的指标
    (1)从信息系统的组成部分出发，信息系统是一个由人机共同组成的系统，所以可以按照运行效果和用户需求(人)、系统质量和技术条件(机)这两条线索构造指标。
    (2)从信息系统的评价对象出发，对于开发方来说，他们所关心的是系统质量和技术水平:对于用户方而言，关心的是用户需求和运行质量:系统外部环境则主要通过社会效益指标来反映。
    (3)从经济学角度出发，分别按系统成本、系统效益和财务指标3 条线索建立指标。

10.4面向对象开发

  • (1)对象:由数据及其操作所构成的封装体，是系统中用来描述客观事务的-个实体，是构成系统的一个基本单位。一个对象通常可以由对象名、属性和方法3个部分组成。
  • (2)类:现实世界中实体的形式化描述类将该实体的属性(数据) 和操作(函数)封装在一起。对象是类的实例，类是对象的模板类可以分为三种:实体类、接口类《边界类) 和控制类实体类的对象表示现实世界中真实的实体，如人、物等。接口类(边界类) 的对象为用户提供一种与系统合作交互的方式，分为人和系统两大类，其中人的接口可以是显示屏窗口、Web 窗体、对话框、菜单、列表框、其他显示控制、条形码、二维码或者用户与系统交互的其他方法。系统接口涉及到把数据发送到其他系统，或者从其他系统接收数据。控制类的对象用来控制活动流，充当协调者。
  • (3) 抽象:通过特定的实例抽取共同特征以后形成概念的过程。它强调主要特征，忽略次要特征。一个对象是现实世界中一个实体的抽象，一个类是一组对象的抽象，抽象是一种单一化的描述，它强调给出与应用相关的特性，抛弃不相关的特性。
  • (4)封装:是一种信息隐蔽技术，将相关的概念组成一个单元模块，并通过-个名称来引用。面向对象封装是将数据和基于数据的操作封装成一个整体对象对数据的访问或修改只能通过对象对外提供的接口进行
  • (5)继承:表示类之间的层次关系 (父类与子类)这种关系使得某类对象可以继承另外一类对象的特征，又可分为单继承和多继承。
  • (6)多态:不同的对象收到同一个消息时产生完全不同的结果。包括参数多态(不同类型参数多种结构类型)包含多态 (父子类型关系) 、过载多态 (类强制多态(强制类型转换) 四种类型。多态以于重载，一个名字不同含义)由继承机制支持，将通用消息放在抽象层，具体不同的功能实现放在低层。
  • (7)接口: 描述对操作规范的说明，其只说明操作应该做什么，并没有定义操作如何做。
  • (8)消息:体现对象间的交互，通过它向目标对象发送操作请求
  • (9)覆盖:子类在原有父类接口的基础上，用适合于自己要求的实现去置换父类中的相应实现。即在子类中重定义一个与父类同名同参的方法
  • (10)函数重载:与覆盖要区分开，函数重载与子类父类无关，且函数是同名不同参数。
  • (11)绑定是一个把过程调用和响应调用所需要执行的代码加以结合的过程在一般的程序设计语言中，绑定是在编译时进行的，叫作静态绑定。动态绑定则是在运行时进行的，因此，一个给定的过程调用和代码的结合直到调用发生时才进行。

第十一章 数据库设计

11.1 数据库设计概述

数据库应用系统的生命周期：
（1）数据库规划：起点，数据库应用系统的任务陈述和任务目标制定阶段；
（2）需求描述与分析：从用户的角度，收集和整理用户需求；
（3）数据库设计与应用程序设计：针对用户数据的组织和存储设计，在此基础上对数据操作及业务实现的设计，包括事务设计和用户界面设计；
（4）实现：依据设计，使用DBMS支持的DDL实现数据库的建立，用高级语言编写应用程序；
（5）测试：对数据库系统进行测试；
（6）运行维护：不断的对DBS进行评价、调整与修改，直至系统消亡。

  • 数据库设计的一般策略：自顶向下，自底向上。
  • 数据库设计的步骤
    (1)用户需求分析·即分析数据存储的要求和边界，产出物有数据流图、数据字典、需求说明书。
    (2)概念结构设计，设计用户的数据模型，与具体DBMS无关的概念模型，一般般是设计E-R图，也即实体-属性图，与物理实现无关，就是说明有哪些实体，实体有哪些属性。
    (3)逻辑结构设计:(将抽象的概念模型转化为与选用的DBMS 产品所支持的数据模型相符合的逻辑模型，它是物理结构设计的基础。包括模式初始设计、子模式设计、应用程序设计、模式评价以及模式求精。
    (4)物理结构设计: 逻辑模型在计算机中的具体实现方案。
    (5)数据库实施阶段。数据库设计人员根据逻辑设计和物理设计阶段的结果建立数据库，编制与调试应用程序，组织数据入库，并进行试运行。
    (6)数据库运行和维护阶段。数据库应用系统经过试运行即可投入运行，但该阶段需要不断地对系统进行评价、调整与修改。
  • 数据库设计一般应包括数据库的结构设计和行为设计两部分内容。数据库的结构设计是指系统整体逻辑模式与子模式的设计，是对数据的分析设计:数据库的行为设计是指施加在数据库上的动态操作 (应用程序集)的设计，是对应用系统功能的分析设计。

11.2 系统需求分析

  • 在整个设计开发过程中是最困难、最耗时的一步。
  • 需求分析的任务：对现实世界中要处理的对象进行详细调查，确定新系统功能，收集支持系统目标的基础数据及处理方法。
  • 分析和表达用户需求的方法主要包括自顶向下和自底向上两类方法。
  • 需求分析的重点是调查组织机构情况、调查各部门的业务活动情况、协助用户明确对新系统的各种要求、确定新系统的边界，以此获得用户对系统的如下要求：
    (1)信息要求。用户需要在系统中保存哪些信息，由这些保存的信息要得到什么样的信息，这些信息以及信息间应当满足的完整性要求。
    (2)处理要求。用户在系统中要实现什么样的操作功能，对保存信息的处理过程和方式，各种操作处理的频度、响应时间要求、处理方式等以及处理过程中的安全性要求和完整性要求。
    (3)系统要求。包括安全性要求、使用方式要求和可扩充性要求。安全性要求:系统有几种用户使用，每一种用户的使用权限如何。使用方式要求:用户的使用环境是什么，平均有多少用户同时使用，最高峰时有多少用户同时使用，有无查询相应的时间要求等。可扩充性要求:对未来功能、性能和应用访问的可扩充性的要求。
  • 需求分析阶段的文档: 需求说明文档、数据流图DFD、数据字典DD

11.3 概念结构设计

  • 概念结构设计的目标是产生反映系统信息需求的数据库概念结构，即概念模式。概念结构是独立于支持数据库的DBMS 和使用的硬件环境的。此时，i设计人员从用户的角度看待数据以及数据处理的要求和约束，产生一个反映用户观点的概念模式，然后再把概念模式转换为逻辑模式。
  • 概念结构设计策略与方法: 自顶向上、自底向上、逐步扩张、混合策略。
  • 使用E-R 方法，无论是哪种策略，都要对现实事物加以抽象认识，以E-R 图的形式描述出来对现实事物抽象认识的三种方法分别是分类、聚集和概括。
    (1)分类:对现实世界的事物，按照其具有的共同特征和行为，定义一种类型。这在现实生活中很常见，如学校中的学生和教师就属于不同的类型。在某一类型中，个体是类型的一个成员或实例，即“is member of”，如李娜是学生类型中的一个成员。
    (2)聚集:定义某一类型所具有的属性。如学生类型具有学号、姓名、性别、班级等共同属性每一个学生都是这一类型中的个体，通过在这些属性上的不同取值来区分。各个属性是所属类型的一个成份，即“is part of”，如姓名是学生类型的一个成份。
    (3)概括:由一种己知类型定义新的类型。如由学生类型定义研究生类型，在学生类型的属性上增加导师等其他属性就构成研究生类型。通常把己知类型称为超类，新定义的类型称为子类。子类是超类的一个子集，即“is subset of”,如研究生是学生的一个子集。
  • 用E-R方法建立概念模型：
    (1)选择局部应用:依据数据流图，将庞大的数据划分成一个个局部应用场景。
    (2)逐一设计分E-R图:依据局部应用，设计分E-R图。现实生活中许多事物，作为实体还是属性没有明确的界定，这需要根据具体情况而定，一般遵循以下两条准则:属性不可再分，即属性不再具有需要描述的性质，不能有属性的属性属性不能与其他实体发生联系，联系是实体与实体间的联系。
    (3)E-R图合并: 多个分E-R图合并
    合并的目的是为了消除分E-R图之间存在的冲突和信息几余，会产生如下冲突:属性冲突:同一属性可能会存在不同的分E-R图，由于设计人员不同或是出发点不同，属性的类型、取值范围及数据单位可能会不一致。命名冲突:相同意义的属性，在不同分E-R图上有着不同的命名，或者是不同意义的属性有着相同的名称。同一实体在不同的分E-R图中有不同的属性，同一个对象在分E-R图中被抽象为实体结构冲突:或属性。
  • E-R图合并时的优化：
    (1)实体类型的合并:两个具有1:1 联系或1:联系的实体，可以予以合并，使实体个数减少有利于减少将来数据库操作过程中的连接开销
    (2)几余属性的消除:一般在各分E-R 图中的属性是不存在余的，但合并后就可能出现几余因为合并后的E-R 图中的实体继承了合并前该实体在分E-R 图中的全部属性，属性间就可能存在几余，即某一属性可以由其他属性确定。
    (3)几余联系的消除:在分E-R 图合并过程中，可能会出现实体联系的环状结构，即某一实体A另一实体B 间有直接联系，同时A 又通过其他实体与实体B 发生间接联系，通常直接联系可以通过间接联系所表达，可消除直接联系。

11.4 逻辑结构设计

  • 逻辑结构设计的主要任务:确定数据模型、将E-R图转换为指定的数据模型、确定完整性约束、确定用户视图。
  • E-R图转换为关系模式：
    1.实体向关系模式的转换:将E-R 图中的实体逐一转换成为一个关系模式实体名对应关系模式的名称，实体的属性转换为关系模式的属性，实体标识符就是关系的码。
    2.联系向关系模式的转换：
    (1)一对一联系的转换。通常一对一联系不需要将其转换为一个独立的关系模式，只需要将联系归并到关联的两个实体的任一方，给待归并的一方实体属性集中增加另一方实体的码和该联系的属性即可，归并后的实体码保持不变。
    (2)一对多联系的转换。通常一对多联系也不需要将其转换为一个独立的关系模式，只需要将联系归并到关联的两个实体的多方，给待归并的多方实体属性集中增加一方实体的码和该联系的属性即可，归并后的多方实体码保持不变。
    (3)多对多联系的转换。多对多联系只能转换成一个独立的关系模式，关系模式的名称取联系的名称，关系模式的属性取该联系所关联的两个多方实体的码及联系的属性，关系的码是多方实体的码构成的属性组。
  • 由E-R图转换得来的初始关系模式并不完全符合要求，还会有数据几余或更新异常存在，需要经过进一步的规范化处理，步骤如下:
    (1)根据语义确定各关系模式的数据依赖
    (2)根据数据依赖确定关系模式的范式
    (3)如果关系模式不符合要求，要根据关系模式的分解算法进行分解，达到规定范式级别(4)关系模式的评价及修正。根据处理要求，可能还需要增加部分几余以满足处理要求，这就需要做部分关系模式的处理，分解、合并或增加几余属性，提高存储效率和处理效率。
  • 确定完整性约束:根据规范化理论确定了关系模式之后，还要对关系模式加以约束包括数据项的约束、表级约束及表间约束等
  • 确定用户视图:确定了整个系统的关系模式之后，还要根据数据流图及用户信息建立视图模式提高数据的安全性和独立性：
    (1)根据数据流图确定处理过程使用的视图。
    (2)根据用户类型确定不同用户使用的视图。

11.5 物理结构设计

  • 数据库在物理设备上的存储结构与存取方法称为数据库的物理结构，它依赖于给定的计算机系统。为一个给定的逻辑数据模型设计个最适合应用要求的物理结构的过程，就是数据库的物理设计。
  • 数据库物理设计的目标：
    （1）使设计出的物理数据库占用较少的存储空间。
    （2）对数据库的操作具有尽可能高的速度。
  • 物理设计的步骤：
    1.确定数据分布:从企业计算机应用环境出发，需要确定数据是集中管理还是分布式管理，但目前企业内部网及因特网的应用越来越广泛，大都采用分布式管理。对于数据如何分布需要从以下几个方面考虑：
    (1)根据不同应用分布数据。
    (2)根据处理要求确定数据的分布。
    (3)对数据的分布存储必然会导致数据的逻辑结构的变化，要对关系模式做新的调整，回到数据库逻辑设计阶段做必要的修改。
    2.确定数据的存储结构:存储结构具体指数据文件中记录之间的物理结构。在文件中，数据是以记录为单位存储的，可以采用顺序存储、哈希存储、堆存储和B + 树存储等方式。为提高数据的访问速度，通常会采用索引技术。
    3.确定数据的访问方式:数据的访问方式是由其存储结构所决定的，采用什么样的存储结构，就使用什么样的访问方式。数据库物理结构主要由存储记录格式、记录在物理设备上的安排及访问路径(存取方法)等构成包括记录的组成、数据项的类型、长度和数据项间的联系，以及逻辑记录：
    1)存储记录结构设计:到存储记录的映射。
    2)存储记录布局:就是确定数据的存放位置。存储记录作为一个整体，如何分布在物理区域上是数据库物理结构设计的重要环节。采用聚簇功能可以大大提高按聚簇码进行查询的效率。建立聚簇索引的原则如下:
    (1)聚簇码的值相对稳定，没有或很少需要进行修改。
    (2)表主要用于查询，并且通过聚簇码进行访问或连接是该表的主要应用。
    (3)对应每个聚簇码值的平均元组数既不太多，也不太少。
    3)存取方法的设计:是为存储在物理设备 (通常是外存储器)上的数据提供存储和检索的能力是快速存取数据库中数据的技术。存取方法包括存储结构和检索机制两部分。其中:存储结构限定了可能访问的路径和存储记录:检索机制定义每个应用的访问路径。在数据库中建立存取路径最普遍的方法是建立索引。确定索引的一般顺序如下:
    （1）首先可确定关系的存储结构，即记录的存放是无序的，还是按某属性(或属性组)聚簇存放。
    （2）确定不宜建立索引的属性或表。
    （3）确定宜建立索引的属性。

11.6 实施阶段

  • 根据逻辑和物理设计的结果，在计算机上建立起实际的数据库结构，数据加载(或称装入)进行试运行和评价的过程，叫作数据库的实施(或称实现)。
  • 1)建立实际的数据库结构: 用DBMS 提供的数据定义语言(DDL)编写描述逻辑设计和物理设计结果的程序(一般称为数据库脚本程序)，经计算机编译处理和执行后，就生成了实际的数据库结构。应包含以下内容：
    （1）数据库模式与子模式以及数据库空间等的描述；
    （2）数据库完整性描述；
    （3）数据库安全性描述；
    （4）数据库物理存储参数描述。
  • 2)数据加载:数据库应用程序的设计应该与数据库设计同时进行。一般地，应用程序的设计应该包括数据库加载程序的设计。
  • 3)数据库试运行和评价:一般将数据库的试运行和评价结合起来的目的是测试应用程序的功能测试数据库的运行效率是否达到设计目标，是否为用户所容忍。

11.7 运行与维护

11.7.1 数据库系统的运行

  • 数据库系统的运行计划主要包括三个方面: 数据库系统运行策略、数据库系统监控对象和监控方式以及数据库系统管理计划。
  1. 制定运行策略:要考虑正常运行策略和非正常运行策略两个方面。
    (1)正常运行策略是指在正常运行状态下的数据库执行策略，包括：
    系统运行对物理环境的要求；
    系统运行对人员的要求;
    数据库的安全性策略;
    数据库备份和恢复策略
    (2)非正常运行策略是指在特殊时期的数据库运行策略，包括：
    突发事件的应对策略;
    高负载状态的应对策略
  2. 确定数据库系统监控对象和监控方式
    （1）依照监控对象的不同，系数据库系统监控的对象分别是系统性能系统故障和系统安全00统监控分为性能监控、故障监控、安全监控。
    ●性能监控是掌握系统运行性能的手段。
    ●性能监控应当从资源占用率、事务响应时间、事务量死锁、用户量等方面实现。
    ●故障监控是保障数据库系统正常运行的手段。从数据库系统故障的类型入手，监控事务故障系统故障和介质故障，出现需要管理员干预的故障时及时恢复。
    ●安全监控是对破坏数据库安全事件的监控，包括入侵监控、用户访问监控、病毒监控等。
    （2）数据库系统的监控方式分为系统监控和应用程序监控系统。
    ●监控是通过DBMS 提供的监控功能，进行参数设定后，由系统自动监控。
    ●应用程序监控需要管理人员根据具体情况编制应用程序进行系统监控，是对DBMS监控功能的补充。
  3. 需要注意的是，系统日志是监控中的主要依据。日志文件详细记录了系统运行中的各种信息管理员可以从日志文件中了解系统运行状态和事件，以此为据发现系统运行中的问题。
  • 1.监控数据的收集与分析:系统监控能够动态地掌握数据库的运行状态，监控就是对系统运行信息的记录，称为监控数据，监控数据是发现系统问题和改进系统性能的依据。依照监控的类型，监控数据分为性能监控数据、故障监控数据和安全监控数据
  • 2.稳定运行中的业务持续性:业务持续性是指一个组织的主要业务流程、营运服务，以及IT 服务能够得到连续性处理。业务持续性需要从以下方面考虑：
    (1)界定哪些是不允许停工的持续性业务，哪些是允许有一定时间的停工期的弹性业务；
    (2)要有业务持续性的技术体系，如高效率服务器、存储系统、网络、DBMS;
    (3)检测和响应管理，包括紧急决策制定、准备工作、最初的紧急响应和系统恢复等所有详细程序;
    (4)要有保障业务持续性的设备
    (5)界定相关人员的职务和权责包括各类技术人员(程序员、管理员和操作员》，执行经理(紧急事件决策者)，设备管理人员(电力、供冷、电缆)，人力资源 (人事问题和需求)，业务实体(业务流程)，以及外部组织(外包机构、电信、供应商等》。

11.7.2 数据库系统的维护

  • 数据库维护：在数据库运行阶段，对数据库的维护主要由DBA 完成：
    1)对数据库性能的监测和改善;
    2)数据库的备份及故障恢复;
    3)数据库重组和重构:数据库的重组是指在不改变数据库逻辑和物理结构的情况下，去除数据库存储文件中的废弃空间以及碎片空间中的指针链，使数据库记录在物理上紧连。
  • 在数据库系统的运行过程中，可能会由于某些原因需要修改数据库的结构，称为数据库重构.对于如下情况，数据库重组和重构的处理方法为：
    (1)修改属性列名或数据类型:由于修改表中的属性列名或数据类型，必须修改使用该表的应用程序，所以应尽量减少这样的修改。
    (2)增加和删除属性:只修改使用该列的应用程序。
    (3)约束的修改:如果是DBMS 支持的约束，如主码约束、参照完整性约束和检查约束，一般不需要修改应用程序，复杂的约束可以通过修改触发器程序实现。
    (4)表的分解:可以通过建立与分解前表同名的视图来避免修改应用程序。但这样会相应引起性能的下降，如果分解是为了提高性能，则需要修改应用程序，只访问分解后的一个表。
    (5)表的合并:通常也是为了提高系统性能，可以通过建立两个与原表同名的视图来避免应用程序的修改。
  • 在数据库重构过程中引入或修改视图，可能会影响数据的安全性，因此必须对视图进行评价和验证，保证不会因为数据库的重构而引起数据的泄密。
  • 文档必须与系统保持一致性，否则会造成人为的困难和错误。修改历史必须在文档中体现。

11.7.3 数据库系统的管理

  • 数据字典的管理:当用户使用DDL 语言定义数据库对象或某些DML语言进行表扩展等操作时系统会自动修改数据字典中的元数据。数据字典是只读的，可以利用DBMS 提供相应的数据字典访问命令，访问数据字典的内容。
  • 数据完整性维护和管理: 是通过DBMS 系统提供的完整性约束机制和应用程序来实现，以保证运行过程中数据的正确性。在系统运行过程中对数据完整性的维护和管理采用两种方式：
    (1)对于DBMS 管理的约束，通过修改数据库的定义，如增加或删除实体完整性约束、参照完整性约束、检查约束来实现。
    (2)对于应用程序实现的复杂的完整性约束，通过分析和修改应用程序，通常是采用触发器程序来实现。
  • 数据库的存储管理:通过以下手段进行存储管理，可有效地提高系统性能：
    （1）索引文件和数据文件分开存储，事务日志文件存储在高速设备上。
    （2）适时修改数据文件和索引文件的页面大小。
    （3）定期对数据进行排序。
    （4）增加必要的索引项。除进行数据库的存储管理之外，也可以通过增加计算机内存、引入高速存储设备等方式来提高系统的访问效率。
  • 备份和恢复:备份计划的制订和实施，有以下建议:
    (1)根据数据变更情况，设定合理的备份周期和备份时间，最好是在业务量最小的时段进行备份。
    (2)事务日志文件保存在最稳定的存储设备上。
    (3)定期在事务日志文件中加入检查点(Checkpoint)。
  • 并发控制与死锁管理:管理员通过系统监控了或系统日志，找出频繁产生死锁的事务，分析死锁的原因，修改事务程序来减少死锁，提高系统的井发性。
  • 数据安全性管理:实际运行中的数据库系统可以从以下几个方面实现安全性管理：
    （1）建立网络级安全，主要是防火墙的设置。
    （2）操作系统级安全，进行登录用户的管理。
    （3）DBMS级安全，对访问数据库的用户进行密码验证。
    （4）角色和用户的授权管理。
    （5）建立视图和存储过程加强安全性。
    （6）使用审计功能，为追纠非法入侵者法律责任提供证据，发现安全漏洞。

11.7.4 性能调整

  • SQL语句的编码校验：
    ●尽可能的减少多表查询或建立物化视图
    ●以不相关子查询代替相关子查询。
    ●只检索需要的列。
    ●用带IN的条件子句等价替换OR子句。
    ●经常提交commit，以尽早释放锁。
  • 表设计的评价：
    ●如果频繁的对两个相关表进行连接操作，考虑将其合并；
    ●如果频繁的访问表中的某一部分字段，考虑分解表，将该部分单独作为一个表;
    ●对于很少更新的表，引入物化视图。
  • 索引维护和改进：
    ●如果查询时瓶颈则在关系上建立适当的索引，通常，在作为查询条件的属性上建立索引可以提高查询效率;
    ●如果更新是瓶颈，考虑删除某些索引;
    ●选择适当的索引类型，如果经常使用范围查询，则B树索引比散列索引更高效;
    ●将有利于大多数数据查询和更新的索引设为聚簇索引。
  • 设备增强:在数据库系统运行过程中，如果经过各种调整之后，仍不能满足性能要求，则应当考虑增强系统设备。例如，引入高速的计算机、增加系统内存、使用高速的网络设备和高速的存储设备等方面。

第十二章 事务管理

12.1 事务的基本概念

  • DBMS运行的基本工作单位是事务。
  • 事务是用户定义的一个数据库操作序列，这些操作序列要么全做，要么全不做，是一个不可分割的工作单位，事务和程序是两个不同的概念，一般一个程序可包含多个事务。一个事务由应用程序的一组操作序列组成，事务定义的语句如下：
    （1）BEGIN TRANSACTION: 事务开始；
    （2）END TRANSACTION: 事务结束；
    （3）COMMIT:事务提交。该操作表示事务成功地结束，它将通知事务管理器该事务的所有更新操作现在可以被提交或永久地保留；
    （4）ROLLBACK:事务回滚。该操作表示事务非成功地结束，它将通知事务管理器出故障了，数据库可能处于不一致状态，该事务的所有更新操作必须回滚或撤销。
  • 事务状态：
    如果不出现故障，那么所有事务都能执行完成。一旦在执行过程中发生故障，不能执行完成的事务称为中止事务;将中止事务对数据库的更新撤销称为事务回滚;成功执行完成的事务称为己提交事务。
  • 中止的事务是可以回滚的，通过回滚恢复数据库，保持数据库的一致性，这是DBMS的责任。己提交的事务是不能回滚的，必须由程序员或DBA 手工执行一个“补偿事务”才能撤销提交的事务对数据库的影响。
  • 为了更明确地描述事务的执行过程，一般将事务的执行状态分为五种:
    (1)活动状态:事务的初始状态，事务执行时处于这个状态。
    (2)部分提交状态:当操作序列的最后一条语句自动执行后，事务处于部分提交状态。这时事务虽然己经完全执行，但由于实际输出可能还临时驻留在内存中，在事务成功完成前仍有可能出现硬件故障，事务仍有可能不得不中止。因此，部分提交状态并不等于事务成功执行。
    (3)失败状态:由于硬件或逻辑等错误，使得事务不能继续正常执行，事务就进入了失败状态处于失败状态的事务必须进行回滚 (ROLLBACK) 。这样，事务就进入了中止状态。
    (4)中止状态:事务回滚并且数据库恢复到事务开始执行前的状态。可选重启事务或杀死事务。
    (5)提交状态:当事务成功完成后，称事务处于提交状态。只有事务处于提交状态后，才能说事务已经提交。

12.2 数据库的并发控制

  • 事务：由一系列操作组成，这些操作，要么全做，要么全不做，拥有四种特性，详解如下：(操作)原子性：要么全做，要么全不做。(数据)一致性：事务发生后数据是一致的，例如银行转账，不会存在A账户转出，但是B账户没收到的情况。(执行)隔离性：任一事务的更新操作直到其成功提交的整个过程对其他事务都是不可见的，不同事务之间是隔离的，互不干涉。(改变)持续性：事务操作的结果是持续性的。
  • 事务是并发控制的前提条件，并发控制就是控制不同的事务并发执行，提高系统效率，但是并发控制中存在下面三个问题：
    丢失更新：事务1对数据A进行了修改并写回事务2也对A进行了修改并写回此时事务2写回的数据会覆盖事务1写回的数据，就丢失了事务1对A的更新。即对数据A的更新会被覆盖
    不可重复读：事务2读A，而后事务1对数据A进行了修改并写回，此时若事务2再读A，发现数据不对。即一个事务重复读A两次，会发现数据A有误。
    读脏数据：事务1对数据A进行了修改后，事务2读数据A，而后事务1回滚，数据A恢复了原来的值，那么事务2对数据A做的事是无效的，读到了脏数据。

  • X锁是排它锁(写锁)。若事务T对数据对象A加上X锁，则只允许T读取和修改其他事务都不能再对A加任何类型的锁，直到T释放A上的锁。
  • S锁是共享锁(读锁)。若事务T对数据对象A加上S锁，则只允许T读取A，但不能修改A，其他事务只能再对A加S锁 (也即能读不能修改)，直到T释放A上的S锁。

共分为三级封锁协议，如下：
一级封锁协议:事务在修改数据R之前必须先对其加X锁，直到事务结束才释放。可解决丢失更新问题：

二级封锁协议：
一级封锁协议的基础上加上事务T在读数据R之前必须先对其加S锁，读完后即可释放S锁。
可解决丢失更新、读脏数据问题：

三级封锁协议：
级封锁协议加上事务T在读取数据R之前先对其加S锁，直到事务结束才释放可解决丢失更新读脏数据、数据重复读问题

  • 串行调度(serial schedule) 是指多个事务依次串行执行，且只有当一个事务的所有操作都执行完后才执行另一个事务的所有操作。
  • 并发调度 (concurrent schedule): 利用分时的方法同时处理多事务”其执行的结果与串行调度执行的结果相同，则称这个并发调度是正确的。可恢复调度:若事务Ti提交失败，则应当撤销Ti的影响以保证其原子性。在允许并发执行的系统中，还必须确保依赖于Ti的任何事务也中止。例如，Ti要读Ti写的数据，则称T 依赖于Ti。
  • 可恢复调度(recoverable schedule) 应满足: 当事务 要读事务Ti 写的数据时，事务Ti必须要先于事务Ti 提交
  • 可串行化的调度:多个事务的并发执行是正确的当且仅当其结果与某一次序串行地执行它们时的结果相同，称这种调度策略是可串行化的调度(serializability schedule)。
  • 冲突可串行化
    冲突 (conflict)：当li和li是不同事务在相同的数据项上操作的命令，月至少有一个是write 命令时，则称i与ii是冲突的。
  • 等价调度:设l与i是调度S 的两条连续的命令，若与是不同事务的命令且不冲突，则可以交换li与ij的顺序得到一个新的调度S*。我们称S 与S*是等价的。

【两段锁协议】

  • 两段锁协议:是指对任何数据进行读写之前必须对该数据加锁在释放一个封锁之后，事务不生长阶段(加锁、扩展阶段)再申请和获得任何其他封锁。每个事务的执行可以分为两个阶段和衰退阶段 (解锁、收缩阶段)。
  • 加锁阶段:在该阶段可以进行加锁操作。在对任何数据进行读操作之前要申请并获得S锁，在进行写操作之前要申请并获得X锁。加锁不成功，则事务进入等待状态，直到加锁成功才继续执行。
  • 解锁阶段:当事务释放了一个封锁以后，事务进入解锁阶段，在该阶段只能进行解锁操作不能再进行加锁操作
  • 如果事务部遵循两段锁协议，那么它们的并发调度是可串行化的。两段锁是可串行化的充分条件，但不是必要条件。需要注意的是采用两段锁协议也有可能产生死锁，这是因为每个事务都不能及时解除被它封锁的数据，可能会导致多个事务互相都要求对方己封锁的数据不能继续运行。
  • 封锁的粒度封锁的粒度是被封锁数据目标的大小，在关系数据库中封锁粒度有属性值、属性值集、元组关系、索引项、整个关系数据库等几种。
  • 封锁粒度小则并发性高，但开销大，封锁粒度大则并发性低，但开销小。

【数据库事务的四种隔离级别】
数据库事务的四种隔离级别数据库事务的隔离级别有4个，由低到高依次为Readuncommitted、Read committed.Repeatable read、Serializable.

  • READ UNCOMMITTED:读未提交，这是事务最低的隔离级别，它允许另外一个事务可以看到这个事务未提交的数据
  • READ COMMITTED: 读提交，保证一个事务修改的数据提交后才能被另外一个事务读取另外一个事务不能读取该事务未提交的数据。解决丢失更新、读脏数据问题。
  • REPEATABLE READ:重复读，在开始读事务时，不允许修改操作。进一步解决了不可重复读问题。
  • SERIALIZABLE:这是花费最高代价但是最可靠的事务隔离级别。事务被处理为串行化执行。

12.3 数据库的故障与恢复

12.3.1 事务故障

  • 数据库故障主要分:事务故障、系统故障和介质故障。
  • 事务故障:是由于程序执行错误而引起事务非预期的、异常终止的故障。通常有如下两类错误引起事务执行失败。
    （1）逻辑错误。如非法输入、找不到数据、溢出、超出资源限制等原因引起的事务执行失败（2）系统错误。系统进入一种不良状态(如死锁)，导致事务无法继续执行
  • 对于不可以预期的错误应用程序无法处理，是由DBMS 系统实现故障恢复的。如非法输入、运算溢出等。非预期的故障如非法输入是由约束机制检查并恢复的。事务故障通常指非预期的故障事务故障意味着事务没有达到预期的终点，因此数据库可能处于不正确状态。恢复程序要在不影响其他事务运行的情况下，强行回滚该事务，即撤销该事务己经做出的任何对数据库的修改，这类恢复操作称为事务撤销 (UNDO)。
    恢复过程：
    （1）反向 (从后向前)扫描日志文件查找该事务的更新操作；
    （2）对该事务的更新操作执行逆操作，也就是将日志记录更新前的值写入数据库；
    （3）继续反向扫描日志文件，查找该事务的其他更新操作，并作同样处理；
    （4）如此处理下去，直到读到了此事务的开始标记，事务故障恢复就完成了。
  • 事务故障的恢复由系统自动完成，对用户是透明的。

12.3.2 系统故障

系统故障(通常称为软故障):是指硬件故障、软件(如DBMS、OS 或应用程》漏的影响，导致丢失了内存中的信息，影响正在执行的事务，但未破坏存储在外存上的信息。这种情况称为故障 – 停止假设。

  • 系统故障会使数据库的数据不一致，原因有两个:
    （1）是未完成的事务对数据库的更新可能己写入数据库；
    （2）是己提交的事务对数据库的更新可能还在缓冲区中没来得及写入数据库。因此恢复操作就是要撤销故障发生时未完成的事务，重做 (REDO) 已提交的事务。
  • 恢复过程：
    （1）正向 (从头到尾)扫描日志文件，找出故障发生前已经提交的事务 (这些事务既有BEGINTRANSACTION 记录，也有COMMIT记录)，将其事务标识记入重做 (REDO) 队列。同时找出故障发生时尚未完成的事务 (这些事务只有BEGIN TRANSACTION 记录，无相应的COMMIT记录)，将其事务标识记入撤销 (UNDO) 队列；
    （2）反向扫描日志文件，对每个UNDO事务的更新操作执行逆操作，也就是将日志记录中更新前的值写入数据库。对每个REDO事务重新执行日志文件登记的操作，也就是将日志记录中更；
    （3）正向扫描日志文件，新后的值写入数据库。
  • 系统故障是在系统重启之后自动执行的，对用户是透明的

12.3.3介质故障

介质故障(称为硬件故障):是指外存故障，例如磁盘损坏、磁头碰撞，瞬时强磁场干扰等。这类故障将破坏数据库或部分数据库，并影响正在存取这部分数据的所有事务，日志文件也被破坏。

  • 恢复过程：
    （1）装入最新的数据库后备副本，使数据库恢复到最近一次转储时的一致性状态；
    （2）转入相应的日志文件副本，重做已完成的事务。
  • 介质故障的恢复需要DBA的介入，具体的恢复操作仍由DBMS完成。

12.3.4数据库备份

  • 静态转储:即冷备份，指在转储期间不许对数据库进行任何存取、修改操作;优点是非常快速的备份方法、容易归档(直接物理复制操作);缺点是只能提供到某一时间点上的恢复，不能做其他工作，不能按表或按用户恢复。
  • 动态转储:即热备份，在转储期间允许对数据库进行存取、修改操作，因此，转储和用户事务可并发执行，优点是可在表空间或数据库文件级备份，数据库仍可使用，可达到秒级恢复;缺点是不能出错，否则后果严重，若热备份不成功，所得结果几平全部无效。
  • 海量转储和增量转储。海量转储是指每次转储全部数据，增量转储是指每次只转储上次转储后更新过的数据。
    ●完全备份:备份所有数据。
    ●差量备份:仅备份上一次完全备份之后变化的数据。
    ●增量备份:备份上一次备份之后变化的数据。
  • 日志文件
    ●在事务处理过程中，DBMS把事务开始、事务结束以及对数据库的插入、删除和修改的每一次操作写入日志文件。一旦发生故障，DBMS的恢复子系统利用日志文件撤销事务对数据库的改变回退到事务的初始状态。
    ●备份毕竟是有时间节点的，不是实时的，例如:上一次备份到这次备份之间数据库出现了故障则这期间的数据无法恢复，因此，引入日志文件，可以实时记录针对数据库的任何操作，保证数据库可以实时恢复。
  • 数据库镜像：
    根据DBA的要求，自动把整个数据库或其中的关键数据复制到另一个磁盘上。DBMS自动保证镜像数据与主数据的一致性。
    作用：用于数据库的恢复;用于并发操作。

12.4 数据库的安全性与完整性

  • 恶意访问的形式主要包括: 未经授权读取数据(窃取信息);未经授权修改数据，未经授权破坏数据。
  • 数据库安全性(data base security) 指保护数据库不受恶意访问。为了保护数据库的安全可以在以下五个层次上采取安全性措施:
    (1)数据库系统层次 (database system)。数据库系统的某些用户获得的授权可能只允许他访问数据库中有限的部分，而另外一些用户获得的授权可能允许他提出查询，但不允许他修改数据保证这样的授权限制不被违反是数据库系统的责任。
    (2)操作系统层次 (operating system)。不管数据库系统多安全，操作系统安全性方面的弱点总是可能成为对数据库进行未授权访问的一种手段。
    (3)网络层次(network)。由于几乎所有的数据库系统都允许通过终端或网络进行远程访问网络软件的软件层安全性和物理安全性一样重要，不管在因特网上还是在私有的网络内。
    (4)物理层次(physical)。计算机系统所位于的结点(一个或多个)必须在物理上受到保护，以防止入侵者强行闯入或暗中潜入。
    (5)人员层次(human)。对用户的授权必须格外小心，以减少授权用户接受贿赂或其他好处而给入侵者提供访问机会的可能性。
  • 为了保证数据库安全，用户必须在上述所有层次上进行安全性维护。如果较低层次上(物理层次或人员层次)安全性存在缺陷，高层安全性措施即使很严格也可能被绕过。下面主要在数据库系统层次上讨论安全性，主要包括: 权限机制、视图机制和数据加密。
  • 授权:通过DBMA提供的授权功能赋予用户在数据库各个部分上的几种形式的授权，其中包括read、insert、update、 delete。
  • 用户还可以获得修改数据库模式的授权: index 授权允许创建和删除索引。resource 授权允许创建新关系。alteration 授权允许添加或删除关系中的属性。drop 授权允许删除关系。
  • 用户角色是具有相同操作权限的用户集合，不同角色的用户授予不同的数据管理和访问操作权限。一般可以将权限角色分为三类: 数据库登录权限类、资源管理权限类、DBA权限类。
  • 存取控制(数据授权):数据库授权可以分为静态授权和动态授权：
    ●静态授权是DBMS的隐性授权，也即用户对于本身所拥有的信息是不需要有指定的授权动作就拥有管理和操作权限的。
    ●动态授权指数据对象的所有者或者DBA默认的拥有对数据的存取权，允许他们把这些权利授子其他的用户。
  • 访问控制可以对用户访问的数据对象进行控制，数据对象粒度从大到小分为如下四个级别:数●据库级别;
    ●表级，判断用户是否可以访问关系里面的内容;
    ●记录级，判断用户是否能访问关系中的一行记录的内容属性级，判断用户是否能访问某列的内容。
  • 视图控制:建立视图，将表中的数据按应用展现和隐藏，有助于隐藏表中的关键信息，增强安全性。
  • 审计功能:是一种事后监督的手段。审计作为一种安全检查的措施，会把系统的运行状况和用户访问数据库的行为记录以日志保存下来，该日志作为稽查用户行为的一种证据。数据库系统的审计工作包括: 设备安全审计、操作审计、应用设计、攻击审计
  • 数据加密:防止数据库的敏感信息在存储和传输过程中被窃取的有效手段。包括数据传输加密技术、数据存储加密技术、数据完整性鉴别技术、密钥管理技术。

第十三章 云计算与大数据处理

13.1 云计算

13.1.1 云计算的关键特征

  • 云计算是与信息技术、软件、互联网相关的一种服务，这种计算资源共享池叫作“云”，，云计算把许多计算资源集合起来，通过软件实现自动化管理，只需要很少的人参与，就能让资源被快速提供。
  • 云计算的关键特征：
    1)广泛的网络接入:用户可以通过网络，采用标准机制访问云中的物理和虚拟资源的特性。标准机制有助于用户通过异构平台使用资源。
    2)可测量的服务:通过可计量的服务交付使得服务使用情况可监控、控制和计费的特性。这个特性强调用户只为自己使用的服务付费，降低用户成本，为用户带来价值。
    3)多租户:通过对物理或虚拟资源的分配保证多个租户以及他们的计算和数据彼此隔离和不可访问的特性。在云中可以实现多种不同形式的租户组织。
    4)按需自服务:客户能够根据自身的实际需求，自动或在最少交互的情况下，配置计算能力的特性。
    5)快速的弹性和可扩展性:物理或虚拟资源能够快速、弹性，有时是自动化地供应，以达到快速增减资源目的的特性。
    6)资源池化:将云服务提供者的物理或虚拟资源进行集成，以便服务于一个或多个云服务客户的特性。该特性通过抽象对用户屏蔽了资源处理和分配的复杂性，用户无需知道资源是如何分布，如何分配的。
  • 其他关键特征:.
    1) 虚拟化技术 虚拟化突破了时间、空间的界限，是云计算最为显著的特点。
    2) 可靠性高:倘若服务器故障也不影响计算与应用的正常运行。
    3)性价比高。

13.1.2 云计算分类

  • 根据云部署模式和云应用范围分类
    1)公有云:云的基础设施一般是被一个云计算服务提供商所拥有，该组织将云计算服务销售给
    公众。
    2)社区云:云的基础设施被一些组织共享，并为一个有共同关注点的社区服务(例如任务、安全要求、政策和遵守的考虑)。
    3)私有云:云的基础设施是为一个客户单独使用而构建的。
    4)混合云:云的基础设施是由两种或两种以上的云(私有、社区或公有)组成，每种云仍然保持独立，但用标准的或专有的技术将它们组合起来，具有数据和应用程序的可移植性《例如，可以用来处理突发负载)，混合云有助于提供按需和外部供应方面的扩展。
  • 根据云计算的服务层次和服务类型分类：
    1)基础设施即服务(aas): 基础设施即服务是主要的服务类别之一，提供虚拟化计算资源，如虚拟机、存储、网络和操作系统。通过网络作为标准化服务提供按需付费的弹性基础设施服务其核心技术是虚拟化。
    2)平台即服务(PaaS):平台即服务是一种服务类别，为开发人员提供通过全球互联网构建应用程序和服务的平台。Paas 为开发、测试和管理软件应用程序提供按需开发环境。其核心技术是分布式并行计算。
    3)软件即服务(Saas): 软件即服务也是其服务的一类，通过互联网提供按需软件付费应用程序云计算提供商托管和管理软件应用程序，并允许其用户连接到应用程序井通过互联网访问应用程字。、

13.1.3 云关键技术

1.虚拟化技术 是一种资源管理技术，是将计算机的各种实体资源(CPU、内存、磁盘空间、网络适配器等)予以抽象、转换后呈现出来，并可供分割、组合为一个或多个电脑配置环境。云计算中的虚拟化往往指的是系统虚拟化。系统虚拟化是指将一台物理计算机系统虚拟化为一台或多台虚拟计算机系统。
2.分布式数据存储:包含非结构化数据存储和结构化数据存储。其中，非结构化数据存储主要采用文件存储和对象存技术62而结构化数据荐储生要采用分布式数据库技术，特别是NOSQL数据库。
3.并行计算:云计算下把海量数据分布到多个结点上，将计算并行化，利用多机的计算资源，加快数据处理的速度。云计算下的并行处理需要考虑以下关键问题，任务划分、任务调度和自动容错处理机制。
4.运营支撑管理:为了支持规模巨大的云计算环境，需要成千上万台服务器来支撑。如何对数以万计的服务器进行稳定高效地运营管理，成为云服务被用户认可的关键因素之一。

13.1.4 云计算的安全

云计算面临的主要数据安全问题和风险包括：
（1）数据存储及访问控制:数据丢失或损坏，数据被非法访问和篡改，多租户之间的数据干扰泄露，数据服务被阻塞，过期数据的妥善保管或销毁等等。
（2）数据传输保护:数据在分布式应用中传递时被窃取或攻击。
（3）数据隐私及敏感信息保护:数据所有权问题，非法授信，隐私泄露等。
（4）数据可用性:异常崩溃、业务中断等。
（4）依从性管理:数据服务违反了法律及政策的要求等。

针对上述计算面临的主要数据安全问题和风险，相应可采取的数据安全管理技术列举如下:
(1)数据保护及隐私保护:包括虚拟镜像安全、数据加密及解密、数据验证、密钥管理、数据恢复、云迁移的数据安全等。
(2)身份及访问管理: 包括身份验证、目录服务、联邦身份鉴别/单点登录(Single Sign、个人身份信息保护、安全断言置标语言、虚拟资源访问、多租用数据授权、基于角色on,sso)的数据访问、云防火墙技术等。
(3)数据传输:包括传输加密及解密、密钥管理、信任管理等。
(4)可用性管理:包括单点失败 (SPOF)、主机防攻击、容灾保护等。
(5)日志管理:包括日志系统、可用性监控、流量监控、数据完整性监控、网络入侵监控等。
(6)审计管理:包括审计信任管理、审计数据加密等。
(7)依从性管理:包括确保数据存储和使用等符合相关的风险管理和安全管理的规定要求。

13.1.5 云安全实施的步骤

（1）确保拥有有效的治理、风险及合规性流程；
（2）审计运维和业务流程报告；
（3）管理人员、角色及身份；
（4）的确保对数据和信息的合理保护；
（5）实行隐私策略；
（6）评估云应用程序的安全规定；
（7）确保云网络和连接的安全性；
（8）的评估物理基础设施和设备的安全管理；
（9）管理云服务水平协议(SLA)的安全条款；
（10）了解退出过程的安全需要。

13.2 大数据

  • 大数据是具有数量巨大、来源多样、生成极快且多变等特征且难以使用传统数据体系结构有效处理的包含大量数据集的数据。
  • 大数据的5V特征: Variety (多样性)、Velocity (速度) 、Volume (数量) 、Value (价值)Veracity (真实性)。
  • 从大数据生命周期的角度看，大数据处理的基本流程包括:数据采集、数据分析和数据解释。

第十四章 数据库主流应用技术

14.1 分布式数据库

  • 分布式数据库是一个物理上分布在计算机网络的不同地点，而逻辑上又属于同一系统的数据集合。网络的每个站点的数据库都有自治能力，能够完成局部应用，同时每个站点的数据库又属于整个系统，通过网络也可以完成全局应用。其组成如下图:

满足下面条件的数据库系统被称为完全分布式数据库系统:
(1)分布性:即数据存储在多个不同的节点上。
(2)逻辑相关性:即数据库系统内的数据在逻辑上具有相互关联的特性。
(3)场地透明性:即使用分布式数据库中的数据时不需指明数据所在的位置。
(4)场地自治性:即每一个单独的节点能够执行局部的应用请求。

  • 分布式数据库的特点:数据的集中控制性数据独立性;数据几余可控性;场地自治性存取的有效性。
  • 局部数据库位于不同的物理位置，使用一个全局DBMS将所有局部数据库联网管理。其四层体系结构如下图所示:

  • 从分布透明特性来说，分布式数据库的全局概念层应具有三种模式描述信息：
    （1）全局概念模式：
    （2）分片模式:描述全局数据逻辑划分的视图它是全局数据的逻辑结构根据某种条件的划分每一个逻辑划分即一个片段，或称为分片。
    （3）分配模式:描述局部逻辑的局部物理结构，是划分后的片段(或分片)的物理分配视图它与集中式数据库物理存储结构的概念不同，是全局概念层的内容。
  • 分片模式：
    水平分片:将表中水平的记录分别存放在不同的地方。
    垂直分片:将表中的垂直的列值分别存放在不同的地方。
    水平和垂直结合的分片:以上两种的混合。
  • 分布透明性：
    分片透明性:用户或应用程序不需要知道逻辑上访问的表具体是如何分块存储的。
    位置透明性:应用程序不关心数据存储物理位置的改变。
    逻辑透明性:用户或应用程序无需知道局部使用的是哪种数据模型。
    复制透明性:用户或应用程序不关心复制的数据从何而来。
  • 分布式数据库的查询和优化与集中式数据库相比，分布式数据库查询还要考虑以下两方面:
    （1）数据和信息均要通过通信线路进行传输，存在的延迟问题将减慢整个查询的执行过程。（2）网络中多处理器的存在提供了并行数据处理和传输的机会，应充分利用以加快查询速度.查询优化:查询执行代价的优化、查询响应时间的优化。
  • 分布式数据库管理系统DDBMS包括综合型和联合型两种体系结构:
    (1)综合型体系结构:是指在分布式数据库建立之前，还没有建立独立的集中式数据库管理系统，设计人员根据用户的需求，设计出一个全新的完整的数据库管理系统。
    (2)联合型体系结构:是指每个节点的数据库管理系统已经存在，在此基础上建立的分布式数据库系统。同时，联合型体系结构又分为同构系统和异构系统。
  • 分布式数据库管理系统由四部分组成:LDBMS(局部数据库管理系统)、GDBMS(全局数据).、库管理系统)、全局数据字典 (GDD)、通信管理(CM)。
  • 分布式事务特性:原子性、可串行性或一致性、隔离性、持久性。与集中式数据库事务区别：
    (1)执行特性:创建一个控制进程协调各子事务的操作。
    (2)操作特性:需要加入大量通信原语负责协调进程和代理进程之间的数据传送等。
    (3)控制制板文“事务操作进行协调。
  • 分布式数据库故障:介质故障、系统故障、事务故障、网络分割故障、报文故障分布式数据库的恢复原则:
    1)孤立和逐步退出事务的原则: 对于不影响其他事务的可排除性局部故障，例如事务操作的删除超时、违反完整性规则、资源、限制、死锁等，应令某个事务孤立地和逐步地退出，将其所做过的修改复原，即做UNDO。
    2)成功结束事务原则:成功结束事务所做过的修改应超越各种故障，当故障发生时，应该重做(REDO) 事务的所有操作。
    3)天折事务的原则:若发生了非局部性的不可排除的故障，例如系统崩愤，则撤销全部事务，恢复到初态。这有两种做法:一种是利用数据库的备份实现:另一种是按反向顺序操作，复原其启动以来所做过的一切修改。
  • 两阶段提交2PC:保证分布式事务的原子性。由于数据库分布在不同的地址位置，其事务可能涉及到不同数据库的操作，需要二阶段提交来保证原子性。
  • 第一阶段是表决阶段，目的是形成一个共同的决定，由协调者发起开始提交的记录，所有参与者决定是否能提交本地事务，只要有一个参与者做出建议撤销的提议，为了保证原子性，协调者就必须整体上撤销这个提交。
  • 第二阶段是执行阶段，协调者依据第一阶段的决定执行撤销或提交该事务。

14.2 Web与数据库

  • 数据与资源共享这两种技术的结合即成为今天广泛应用的Web 数据库(也叫网络数据库)个Web 数据库就是用户利用浏览器作为输入接口，输入所需要的数据，浏览器将这些数据传送给网站，由网站对这些数据进行处理。网站上的后台数据库就是Web 数据库。
  • 连接数据库的常用方法: ODBC、DAO、RDO、ADO。
  • Web和数据库的运行模式:

14.3 XML与数据库

  • XML，意为可扩展的标记语言。XML是一套定义语义标记的规则，这些标记将文档分成许多部件并对这些部件加以标识。
  • 采用文件存储XML，那么会受到文件系统的限制，出现如下问题: 大小、并发性、工具选择.版本、安全、综合性(集中和重复)。
  • XML文档中的数据视图模型:
    (1)表格模型:许多中间件软件包都采用表格模型在XML和关系型数据库之间进行转换。它把XML的模型看成是一个单独的表格或者是一系列的表格。
    (2)特定数据对象模型:在该模型中，元素类型通常对应对象，而XML 中的内容模型、属性和PCDATA则对应对象的属性。这种模型直接映射成面向对象的数据库和层次型数据库，当然借助于传统的对象-关系映射技术和SOL对象视图也可以映射成关系数据库。

14.4 面向对象数据库

  • 数据库技术与面向对象程序设计方法相结合形成了面向对象数据库系统(OODBS)，它是支持将数据当作对象来模拟和创造的一种数据库管理系统。通常认为，对象数据库必须满足两项标准:它必须是一个数据库管理系统，并且必须是面向对象的系统。
  • 面向对象数据库系统的特征:
    （1）面向对象数据库系统应该具有表达和管理对象的能力。
    （2）面向对象数据库系统中的对象可以具有任意复杂度的对象结构。
    （3）面向对象数据库系统必须具有与面向对象编程语言交互的接口。
    （4）面向对象数据库应具有表达和管理数据库变化的能力。
  • 面向对象数据模型的基本概念有对象、类、继承、对象标识、对象嵌套等。
    1.对象结构我们可以认为一个对象对应着E-R 模型中的一个实体。对象中封装的属性和方法对外界是不可见的，对象之间的相互作用要通过消息来实现。一般来讲，一个对象包括:属性集合方法集合、消息集合。
    2.对象类:在面向对象数据库中，类是一系列相似对象的集合，对应于E-R 模型中的实体集概念3.继承与多重继承。
    4.对象标识:每个对象有一个唯一的、由系统生成的对象标识。
    5.对象嵌套:对象的一个属性可以是一个单一值，也可以是一个来自于值域的值集，即一个对象的属性可以是一个对象，形成了嵌套关系。一个对象被称为复杂对象，如果它的某个属性的值是另一个对象。
  • 面向对象数据库语言主要包括对象定义语言和对象操纵语言。对象查询语言是对象操纵语言的个重要子集。面向对象数据库语言一般应具备功能:类的定义和操纵、操作/方法的定义、对象的操纵。
  • 对象关系数据模型扩展关系数据模型的方式是通过提供一个包括复杂数据类型和面向对象的更丰富的类型系统。有如下手段:
    （1）嵌套关系
    （2）复杂类型
    （3）继承、引用类型
    （4）与复杂类型有关的查询
    （5）函数与过程。
    （6）面向对象与对象关系

14.5 大数据与数据库

  • 大数据是一种具有海量的数据规模，在获取、存储、管理和分析等方面都远远超过传统数据库处理范围的数据集合。
  • 工业界便用三大特征作为大数据的分类标准。第一个维度是体量大，第二个维度是速度快，第个维度是多样性。
  • 大数据之数据仓库设计:数据仓库相关内容在数据库技术基础已经阐述过，这里不再整述。
  • 数据转移，也称为数据转换或数据变换，就是把多种传统资源或外部资源信息中不完善的数据自动转换为商务中准确可靠的数据。在数据仓库环境中进行数据转移的目的应该有两个:
    第一，改进数据仓库中数据的质量；
    第二，提高数据仓库中数据的可用性。
  • 包括四种转移类型:
    (1)简单转移。简单转移是所有数据转移的基本构成单元。
    (2)清洗。清洗的目的是保证前后一致地格式化和使用某–字段或相关的字段群。
    (3)集成。集成是指将业务数据从一个或几个来源中取出，并逐字段地将数据映射到数据仓库的新数据结构上。
    (4)聚集和概括。聚集和概括是把业务环境中找到的零星数据压缩成仓库环境中的较少数据块.。

14.6 NewSQL

  • NewSQL 是一种新型关系数据库管理系统是对各种新的可扩展和高性能数据库的简称，这类数据库不仅具有NoSQL 对海量数据的存储管理力，试图为联机事务处理(OLTP)读写工作负载提供与NOSQL系统相同的可伸缩性能，还保持了传统数据库支持ACID 和SQL等特性。
  • NewSQL 系统虽然在的内部结构变化很大，但是它们有两个显著的共同特点: 支持关系数据模型和使用SQL 作为其主要的接口。目前NewSQL 系统可通过架构、SQL引擎和数据分片分成三类：
    （1）新架构:采用新架构的NewSQL 系统是全新的数据库平台，使用两种不同的设计方法：
    第一种设计的数据库工作在一个分布式集群的节点上，其中每个节点拥有一个数据子集。SQI查询被分成查询片段发送给自己所在的数据的节点上执行。
    第二种设计的数据库系统通常有一个单一的主节点的数据源。它们有一组节点用来做事务处理这些节点接到特定的SQL 查询后，会把它所需的所有数据从主节点上取回来后执行SQL查询，再返回结果。
    （2）SQL引擎:第二类是高度优化的SQL 存储引警。这些系统提供了MySQL 相同的编程接口，但扩展性比MySQL内置的引警更好。
    （3）数据分片:关系型数据库不能满足每秒大量的数据操作和写入率。为了解决这个问题，提供了分片的中间件层，数据库自动分割在多个节点运行。

第十五章 知识产权和标准化

15.1 知识产权概述

  • 知识产权是指公民、法人、非法人单位对自己的创造性智力成果和其他科技成果依法享有的民事权。是智力成果的创造人依法享有的权利和在生产经营活动中标记所有人依法所享有的权利的总称。包含著作权、专利权、商标权、商业秘密权、植物新品种权、集成电路布图设计权和地理标志权等
  • 无体性:知识产权的对象是没有具体形体，是智力创造成果，是一种抽象的财富。
  • 专有性:指除权利人同意或法律规定外，权利人以外的任何人不得享有或使用该项权利。
  • 地域性:指知识产权只在授予其权利的国家或确认其权利的国家产生，并且只能在该国范围内受法律保护，而其他国家则不受保护。
  • 时间性:仅在法律规定的期限内受到保护，一旦超过期限，权利自行消灭相关知识产品即成为整个社会的共同财富，为全人类所共同使用。

15.2 保护期限

知识产权具有地域限制，保护期限各种情况如下表所示：

15.3 知识产权人的确定

知识产权人的确定：
（1）职务作品

（2）委托作品
单位和委托的区别在于，当合同中未规定著作权的归属时，著作权默认归于单位，而委托创作中，著作权默认归属于创作方个人，具体如下:

15.4 侵权判断

  • 中国公民、法人或者其他组织的作品，不论是否发表，都享有著作权开发软件所用的思想、处理过程、操作方法或者数学概念不受保护。
  • 著作权法不适用于下列情形法律、法规、国家机关的决议、决定、命令和其他具有立法、行政、司法性质的文件，及其官方正式译文;时事新闻;历法、通用数表、通用表格和公式。

侵权判定：

15.5 标准划分

根据标准制定机构和适用范围的不同，可分为国际标准、国家标准、行业标准、区域/地方标准和企业标准：
(1)国际标准是指国际标准化组织 (IS0)、国际电工委员会 (IEC) 和国际电信联盟 (ITU)制定的标准以及国际标准化组织确认并公布的其他国际组织制定的标准。国际标准在世界范围内统一使用,提供各国参考；
(2)国家标准:是指由国家标准化主管机构制定或批准发布，在全国范围内统一适用的标准。比如:GB-.中华人民共和国国家标准;强制性国家标准代号为GB，推荐性国家标准代号为GB/T，国家标准指导性文件代号为GBZ，国军标代号为GJB，ANSI(American National Standards nstitute) —美国国家标准协会标准；
(3)行业标准:是由某个行业机构、团体等制定的，适用于某个特定行业业务领域的标准。比如:IEEE美国电气电子工程师学会标准;GA—公共安全标准，YD—通信行业标准。
(4)区域/地方标准:是由某一区域/地方内的标准化主管机构制定、批准发布的，适用于某个特定区域/地方的标准。比如:EN—欧洲标准；
(5)企业标准:是企业范围内根据需要协调、统一的技术要求、管理要求和工作要求所制定的标准，适用于本企业内部的标准。一般以Q字开头，比如Q/320101 RER 007–2012，其中320101代表地区，RER代表企业名称代号，001代表该企业该标准的序号，2012代表年号。

相关章节：

【软考数据库】第一章 计算机系统基础知识
【软考数据库】第二章 程序语言基础知识
【软考数据库】第三章 数据结构与算法
【软考数据库】第四章 操作系统知识
【软考数据库】第五章 计算机网络
【软考数据库】第六章 数据库技术基础
【软考数据库】第七章 关系数据库
【软考数据库】第八章 数据库SQL语言
【软考数据库】第九章 非关系型数据库NOSQL
【软考数据库】第十章 系统开发与运行
【软考数据库】第十一章 数据库设计
【软考数据库】第十二章 事务管理
【软考数据库】第十三章 云计算与大数据处理
【软考数据库】第十四章 数据库主流应用技术
【软考数据库】第十五章 知识产权和标准化