首页  思维导图  详情

软考-软件设计师

2021-08-06 15:29:05   4  举报





AI智能生成

软考复习提纲

软件设计师

作者其他创作

大纲/内容

下午

数据流图(第六章)

实体名字

存储名字

缺失的数据流

结构化语言描述某加工

某数据流组成

数据流如何保持平衡

父图中某个加工的输入输出数据流必须与其子图的输入输出数据流在数量和名字上相同.

父图的一个输入输出数据流对应子图中几个输入输出数据流,而子图中的组成这些数据流的数据项正好是父图中的一个数据流.

父加工,分解为了哪几个子加工

技巧

1、父图子图平衡

2、看圆角矩形（加工）是否缺少输入，或者输出

3、数据守恒（换句话说，输入是否足够产生输出）

UML(第七章)

图的类型

用例图

包含<include> 抽取公共用例,必然会执行的用例

扩展 <extend> 可选用例

泛化关系<generalization> 父子关系

参与者是组织或者人某某系统,某某人

extend 如果,则分支条件 查询用例 <--<extends>--修改 扩展用例指向基准用例

include 包含必须完成用例1 才会执行用例2  登陆用例<--<include>--查询用例 先登陆才能查询

类图

属性

方法

多重度

0.. *

n..* 至少几个

乐队 0..* 歌手  一名歌手可以属于 0个或多个乐队

歌手 2..* 乐队乐队由两名以上的歌手组成

关系

依赖

--▶ 依赖关系虚线实心箭头 (使用)

泛化

-▷ 实线空心箭头父子关系对于类

聚合

-◇ 实现空心菱形不同声明周期 

组合

-◆ 实线实心菱形同一生命周期

实现

-----▷ 虚线空心箭头对于接口实现

对象图

类图的实例,有生命周期

时序图

活动图

类似于流程图

粗横线并行分支

菱形分支

状态图

通信图

又叫通讯图

实例消息 1 1.1 1.2 等等

构件图

数据库分析与设计,ER图(第九章)

ER模型补充

联系类型

1:1

1:*

*:*

部门 1 <--> * 员工

员工 * <--> 1 部门

学生 * <--> * 科目

ER模型转关系模式

关系模式补充

数据结构与算法应用(第三章&第八章)

贪心

0-1背包问题

每一步取最优,但得不到最优解

回溯

迷宫

到底再回来

分治

快排归并排序

分而治之

动态规划

局部最优解

每一步都是最优解,存在下最优解查表来解决后面的问题.

面向对象程序设计(第十二章)

设计模式概念

java语法

作用域

+ public

- private

# protected

抽象类

abstract

抽象类中都是抽象方法要写 abstract

接口

interface

implements

上午

计算机组成原理与体系结构(第一章)

数据的表示

进制转换

按权展开法(任意进制转换为十进制)

R^k 底数是R(R进制) 指数是k k是小数点的距离

七进制:605.02 = 6*7^2+5*7^0+2*7^-2

二进制:10101.01=1*2^4+1*2^2+1+1*2^-2

十进制转换为R进制

短除法

除R,取余然后逆序排列

整数

37/2=18 1 18/2=9 0 9/2=4 1 4/2=2 0 2/2=1 0 2/1=0 1 二进制:100101

2/8/16进制转换

2转8

每三位转换

10101 补0 010 101 = 25  010 = 2 101 = 5

2转16

每四位转换

1C00 0001 1100 0000

浮点进制

乘法

乘以R,取整

0.375=

最高位,首位符号位0正数,1负数,不足字节数补0

原码

1  = 0000 0001

-1 = 1000 0001

1 -1 = 1000 0010

= -2 原码不能在计算机中直接进行计算的

范围 8位

-(2^x-1 - 1) ~ 2x^1-1 = 2^7 -127 ~  127

反码

1 = 正数与原码相同 0000 0001

-1 = 1111 1110 除了符号位与原码取反

1 -1 = 1111 1111

= -2 原码不能在计算机中直接进行计算的

范围 8位

-(2^x-1 - 1) ~ 2x^1-1 = 2^7 -127 ~  127

补码

1 = 正数与原码相同 0000 0001

-1 = 原来反码的基础上+1 1111 1111

1 -1 = 0000 0000

范围 8位

-(2^x-1 ) ~ 2x^1-1 = 2^7 -128 ~  127

由于±0 都是 0000 0000 所以少占用了一位

移码

浮点运算的阶码在补码的基础上首位取反

1 = 1000 0001

-1 = 0111 1111

1 -1 = 1000 0000

浮点数运算

N=M*R^e M是尾数 e是指数 R是基数

1000= 1.0*10^3 1.0->尾数 10->基数 3->指数 119= 1.19*10^2 低对高 0.119*10^3 1.119*10^3 = 1119 格式化->小数点左边的数据不能超过一位,也不能是0.

对阶->尾数计算->结果格式化

考点例题

多少块芯片组成多大的存储空间

计算IP地址,子网掩码

计算机结构

CPU如何划分

运算器(运算/加减法)

算术逻辑单元(ALU) 

运算职能,加减法

累加寄存器(AC)

运算过程中存储中间值

数据缓冲寄存器(DR)

内存读写操作,暂存数据

状态条件寄存器(PSW)

运算过程中相关标志位例如进位/中断等状态信息

控制器

程序计数器PC

记录执行下一条指令

指令寄存器IR

暂存当前正在执行的指令

指令译码器ID

指令通常由操作码和地址码两部分组成,译码器去解释指令

时序部件

主机(CPU/主存)+外设(鼠标/显卡/声卡/硬盘)

Flynn分类法

单指令流单数据流 SISD

控制器:1 处理器:1 主存模块:1

单处理器系统

单指令流多数据流 SIMD

控制器:1 处理器:多个 主存模块:多个

一条指令会有多个运算部件去同时处理

各处理器以以部的形式执行一条指令

并行处理机 阵列处理机(处理数组类型的运算) 超级向量处理机

多指令流单数据流 MISD

控制器:多个 处理器:1个 主存模块:多个

理论模型 被证明不实际

多指令流多数据流 MIMD

控制器:多个 处理器:多个 主存模块:多个

能够实现作业/任务指令等各级全面并行

多处理机系统 多计算机

CISC&RISC

CISC(Complex Instruction Set Computers,复杂指令集计算集)

指令:数量多,使用频率差别大,可变长格式. 寻址方式:支持多种 实现方式:微程序控制术(微码) 其他:研制周期长

定制划,指令数量多.

RISC(Reduced Instruction Set Computers)

指令:数量少,使用频率接近,定长格式,大部分为单周期指令,操作寄存器.只有load/store操作内存. 寻址方式:支持方式少 实现方式:增加了通用寄存器,硬不限逻辑控制为主,适合采用流水线 其他:优化编译,有

流水线技术(pipeline)

程序执行时多条指令重叠进行操作的一种准并行处理实现技术

取指->分析->执行,无需等待第一条指令执行,则开始第二条指令取指

流水线周期=执行时间最长的一段

指令执行时间+(指令条数-1)*流水线周期

取值2ns,分析2ns,执行1ns

理论时间=(t1+t2+tk)+(n-1)Dt Dt:流水线周期 (2+2+1)+99*2=203 首先用理论公式

实践公式=(k+n-1)*Dt  k分成几段就是几 (3+99)*2=204

流水线吞吐率

单位时间能够处理任务的数量

TP=指令条数/流水线执行时间 

依照上个例子指令条数100 流水线执行时间 203 100/203

最大吞吐率:TP(max)=Lim(n->∞)*n/(k+n-1)&Dt = 1/Dt

流水线加速比

完成同一批任务不使用流水线执行时间与使用流水线时间的比值

不适用流水线时间/使用流水线时间

存储系统

存储的结构

CPU->寄存器

cache-->按内容存取

提高CPU输入输出的速率,突破冯诺伊曼瓶颈

依据局部性原理改善系统性能

cache访问命中率(H),t1周期时间,t2为主存储的周期时间.  t3=h*t1+(1-H)*t2

例如:t1=1ns,t2=1ms=1000ns,H=95%   95%*1ns+5%*1000ns=50.95ns 提升约 20倍

局部性原理

时间局部性

循环体

空间局部性

数组

工作集理论

工作集是进程运行时被频繁访问页面的集合

内存(主存)

分类

随机存储器(内存)

DRAM(Dynamic RAM) - SDRAM

SRAM(Static RAM)

只读存储器

MROM(Mask ROM)

PROM(Programmable ROM)

EPROM(Erasable PROM 可擦除的PROM)

flash member(闪存)

编址

内存地址AC000H到C7FFFH,共有()k个地质单元. 大的减小的+1

AC000H到C7FFFH = (C7FFF+1)-AC000=C8000-AC000=C8-AC=11 - 10 | 8+16-12 = 1|12 = 1C000H

k个=1024b=2^10

1C000 转十进制=1*16^4+12*16^3=114668 / 1024 = 112

如果上诉内存地址(112)按字编址(16bit),由28片存储构成,已知构成此内存的芯片每片有16k存储单元,则该芯片每个存储单元存储(N)位.

112k*16bit/28*16k*N 则 N=4

外存(辅存)-->硬盘/光盘/U盘

磁盘

磁道

类似于年轮一圈一圈

扇面

类似于蛋糕一角

扇区

扇面被磁道分割的一小块,数据存储于此

存取时间=寻道时间+等待时间(定位磁道+旋转时间)

旋转时间=平均时间(磁盘转一圈时间),最好情况不需要转动,最坏情况是转一圈的时间.

假设某磁盘划分成11个物理块(扇区),每块存放1个逻辑记录R0-R10,如果磁盘的旋转周期是33ms,磁头当前处于R0位置, 若系统使用单缓冲区顺序处理这些记录,每个记录处理时间为3ms,则处理这11个记录最长时间为(X);若对信息存储进行优化分布后,处理11个记录的最少时间为(Y)

转一圈=33ms,转动一格是3ms,写入缓存处理是3ms (33+3)*10+6 r0写入缓存区,转动到了r2,当r0处理完需要转动一圈到r1,反复处理以上内容到r9. 0-9=10相当于转动+处理 *10,加最后一个处理写入转动一格3+3; R0R6R1 R0处理完正好读到 R1,读取和处理分别是3ms,那么最快是11*(3+3)=66ms

总线系统

分类

内部总线

计算机内部外围的芯片与处理器的级别,芯片级别的

系统总线

插线板

PCI

VGA

数据总线

32位则一个字就是32个bit位数据的宽度

地址总线

32 2^32 = 4g

控制总线

外部总线

模型

串联(其中一个子系统失效则失效)

可靠度

R1-RN 串联 = R1*R2*R3...*Rn

失效率

累加 H1+H2+H3

近似公式,可能有误差

并联(全部子系统失效才失效)

可靠度

R=1-(1-R1)*(1-R2)*....(1-Rn)

失效率

1-可靠度

模冗余系统与混合系统(多个同样系统冗余计算,汇总到表决器(少数服从多数),输出)

混合系统先识别最终是串联还是并联

效验码

CRC校验码

可以检错但不能纠错的一种编码

原始报文为11001010101,生成多项式为x^4+x^3+x+1 转为二进制 11011(根据多项式成成进制位数为是1或0)

11001010101 ,在原始编码加多项式长度-1个0

11001010101 0000 摸二 11011 = CRC编码 0011

海明校验码

可以检错也可以纠错

校验位:信息为 2^r>=4+r+1

检错(检查错误)&纠错(纠正错误)

码距

二进制举例,当一位长度A=1 B=0则码距是1

若用2位长度 A=11 B=00 码距是2

若用3位长度可选用111,000作为合法编码,最小码距是3

在一个码组内为了检测e个误码,最小码距d应该满足 d>=e+1

在一个码组内为了纠正t个误码,要求最小码距d应该满足 d>=2t+1

数据结构与算法基础(第三章)

数组与矩阵

数组(存储地址的计算)

一维数组

a[i]的存储地址为:a+i*len len是元素的字节数

二维数组a[m][n]

a[i][j]按行存储 a+(i*n+j)*len 

1|2|3|4| 5|6|7|8|

a[i][j]按列存储 a+(j*m+i)*len

1|3|5|7| 2|4|6|8|

5*5的二维数组,元素占2个字节,求a[2][3]按行优先的存储地址

a[2][3]=a+(2*5+3)*2=a+13*2

矩阵

稀疏矩阵(大量元素都是0)

上三角矩阵(上面是满的,下面大部分是0)

(2n-i+1)*i/2+j

下三角矩阵(下面是满的,上面大部分是0)

在矩阵中下标分别为i和j的元素,对应的一维数组的下标公式为:(i+1)*i/2+j

计算某一个元素一维数组的下标

线性表

栈(弹夹)

先进后出

队列(排队)

先进先出(FIFO)

循环队列

头尾相接,一个环.

(tail+1)%size=head

链表(指针&数据)

单链表

有头节点(不存储数据),所有的操作是一致的,否则需要特殊处理头节点.

循环链表

尾元素指向头节点,无需重新定位到头节点

双向链表

广义表

冠以表是n个元素组成的有限序列,是线性表的推广,通常用递归形式定义.

长度:最外层的表长度

深度:包含括号的重数,

head=最外层的第一个表元素

tail=表尾,除了第一个元素外的所有元素

有广义表 LS1=(a,(b,c),(d,e)) 长度? 深度? 3,2

有广义表 LS1=(a,(b,c),(d,e))  要把广义表的b元素取出? tail(b,c),(d,e) head(b,c) head(b)

树与二叉树

概念

结点的度

拥有的孩子的个数

树的度

所有节点数最高的,就是树的度(二叉树整个树的度为2),子节点的个数

叶子节点

没有孩子节点,末端节点,结点的度是0

分支节点

子主题

内部节点

非叶子节点,非根节点

父节点

子节点

兄弟节点

平级节点

层次

根节点1层,叶子节点=树的高度,

二叉树

满二叉树

所有子节点没有缺失的部分

完全二叉树

除右边叶子节点缺失,其余都是满的 1,2,3,4,5,6

非完全二叉树

1,2,3,4,5,7 | 1,2,4,5

二叉树第i层上最多有 2^i-1

二叉树遍历       1     (2,3) (4,5) (0,6)     (7,0)         (0,8)

前序

根,左,右.

1,2,4,5,7,8,3,6

中序

左,根,右

4,2,7,8,5,1,3,6

后序

左,右,根

4,8,7,5,2,6,3,1

层次遍历

1,2,3,4,5,6,7,8

树转二叉树

孩子节点-转为左子树节点

兄弟节点 - 转为右子树节点

排序二叉树

左小于根,根小于右

插入:1.若节点已存在,则不再插入.2.若树为空树,则插入3.将要插入的值与父节点比较确定左子节点还是右子节点

删除 1.若是叶子节点直接删除,2.删除的节点只有一个孩子节点,则将父节点与子节点相连.3.若p节点有两个子节点,则在其左子树上用中序遍历查找关键之最大的节点s,用节点s的值代替节点p的值(左子树的最大值).删掉s节点,再执行上诉1,2.

最优二叉树(哈夫曼树)

概念

树的路径长度=一段一段(边)累加

权:某个叶子节点的数值出现的频度

带权的路径长度:累加所有叶子节点(路径长度*权值(边*权值))

树的带权路径长度:累加所有的带权路径长度(树的代价),排除构造出的节点累加叶子节点的路径长度

构建一条哈夫曼树目标是树的带权路径长度要最短(缩短权重大的路径,把权重大的放在上面)

如何构造哈夫曼树

5,29,7,8,14,23,3,11

选权值最小的,构造一棵小树

哈夫曼编码

0,1编码左节点为0,右节点是1.到此节点的编码就是哈夫曼编码

线索二叉树

二叉树的叶子节点有大量空的指针,利用空闲资源.方便遍历

有虚线的渐线把节点串起来

前序线索二叉树

左子树的指针指向当前遍历节点的前驱节点,右子树指向后序节点

中序线索二叉树

后序线索二叉树

平衡二叉树

定义

提高排序二叉树的平衡,让其层更少.

任意节点的深度相差不超过一

每节点的平衡度只能为-1,0,或1

平衡度,叶子节点的平衡度是0. 左是正数的边累加,右是负数边累加. 根的是左子树的层数 - 右子树的层数

动态平衡问题

旋转

图

图的概念

存在环路-连成一个圈

无向图

节点间(边)没有方向

有向图

边有方向,

完全图

所有的边都连满了

邻接矩阵存储图

5个节点=矩阵5*5矩阵,矩阵的值,有边就记1,没有边就记0

对角是有一致性,可以存上三角或下三角矩阵

邻接表

节点的表

用链表存储

节点-距离

图的遍历

深度优先

先访问下一层次,类似于树的前需遍历

广度优先

先访问相邻节点,再访问下一层次

拓扑排序

用一个序列表达一个图当中哪些事件可以先执行,哪些事件可以后执行.

执行完的边可以划掉,如果没有节点指向自己就可以执行了.

图的最小生成树

普利姆算法

红点选出边最短的,且不能形成环,一旦选出则蓝点变红点

克鲁斯卡尔算法

1.先确定边数,2.选最短的边,且不成环

树的节点是N , N-1条边就是树 >=N条边就是图

排序与查找

排序

算法

归并排序

计数排序

桶排序

基数排序

插入类

直接插入排次序

顺序比较,插入到合适的地方. n,稳定

1.从第二个开始,向前比较,如果小于前一个则交换,

希尔排序

分为len/2个组,逐个组用直接插入排序

交换类

冒泡排序

快速排序

选择类

选择排序

堆排序

概念

稳定:排序后顺序是否一致,稳定:一致,不稳定:不一致

内排序/外排序:内:只在内存,外:外部存储

查找

顺序查找

n+1/2(等差队列)

O(n)

二分查找

序列首先要有序(ASC/DESC)

1+12/2=6,下标中间值->取整; 确定左右. 1+5/2=3 确定左右.

O(logn)

散列表

hashtable

算法基础及常见的算法

分治算法(分解Divide|解决Conquer|合并Combine)

贪心

回溯

算法的特性

有穷性,确定性,有效性

输入>=0,输出>=1

操作系统知识(6-8分)(第四章)

进程管理

进程状态

三态模型

运行/就绪/等待

等待(等待某个事件发生)-->就绪(调度)-->运行

运行(等待某资源/事件)-->等待

运行(时间片轮转,让出cpu)-->就绪

五态模型

运行/活跃就绪/活跃阻塞  新增静止就绪/静止阻塞

前趋图

表达并行以及执行的先后约束关系

同步与互斥

互斥

在某一时刻,只允许某一个进程访问资源. e.g. 独木桥 ,反义词是共享

同步

执行速度存在差异,在一定情况下等待.反义词是异步.

生产者消费者

单缓冲区

缓冲区只有一个资源(互斥资源),同一时刻只能由一个生产者或者消费者访问资源

多缓冲区

缓冲区有多个资源,待缓冲区满了后才会进行同步等待.

PV操作

临界资源

进程间需要互斥方式对其进行共享的资源,如打印机/磁带机等

临界区

每个进程中访问临界资源的那段代码称为临界区(访问临界资源的代码段)

信号量

一种特殊的变量

P操作

s=s-1;s<0?push queue&wait:goon

V操作

s=s+1;s<=0?pull queue&wait:goon

PV操作与前趋图

无依赖则V(S自己),有依赖则先P(S前置节点)之后V(S自己)

每个箭头对应一个信号量,从左到右,从上到下,减头的起点操作是V操作,减头的结尾是P操作.

死锁问题

最少多少个资源不会产生死锁

大于每个资源的n-1个,比如ABC各需要5各,则3*4+1=13个就不会

k*(n-1)+1

死锁条件

互斥

共享则不会死锁

环路等待

A->B B->C C->A

保持和等待

这个进程会保持自己的资源,等待别人释放资源

不剥夺

系统不会把某个进程的资源剥夺掉分配个其他系统

避免死锁

共享资源

打破四大条件

有序资源分配法

银行家算法

如果无法偿还资源,则不会分配资源

计算所剩资源数

总数-已分配

还需资源数

最大需求-已分配

当前置进程执行完,会释放刚刚分配的资源和已占用的资源

存储管理

段页式存储

逻辑地址和物理地址的转化

将页号和页内地址分开

根据页面大小 4k=2^12 说明一个页的页内地址是12位 ,高于12位的就是页号

逻辑地址 5A29H 每4位是一个16进制位所以 5是页号页内地址是A29H

页号5 对应的物理块号(页帧号)

页面淘汰(按照顺序在内存没有访问 

状态位=在内存中淘汰在内存中的

访问位=没有淘汰没有访问的 

修改位= 没有修改过

页式存储

用户程序等分为4k的页

按页大小存储

段式存储

按程序段存储

段页式存储

混合段和页

快表

按内容存储

页面置换算法-分区存储组织

首次适应算法

第一个匹配够的

最佳适应算法

第一个匹配够的,则分配剩余的空间链到之前的空间

最差适应算法

最小的块分配

循环首次适应算法

空闲区域连城环状,按顺序链接

典型算法

最优

随机

先进先出

最少使用

试题

访问了多少次内存

如果用了快表直接访问内存则是页面数*1, 否则每次都需要操作两次内存页面数*2

meifou 

缺页中断次数

指令1次操作数2次

文件管理

索引文件

索引分类

直接索引,一级/二级/三级简介索引

数据块1KB,每个地址4字节,每个数据块快也存储256个地址, 逻辑块号5(0开始)  和261的信息分别对应物理块是(一级索引 256 一块) 261则在一级索引的第二块里

101物理块存放的是二级索引地址

空闲存储空间的管理

空闲区表法

空闲链表法

位示图

字长32位,4195号物理块

多少字是从1开始算

多少位是从0开始算

成组链接法

文件和属性目录结构

绝对路径/相对路径

作业管理

设备管理

数据传输控制

程序控制

程序中断

DMA

不需要CPU接入

通道

输入输出处理机

微内核操作系统

虚设备与SPOOLING技术

要打印的内容,放入缓冲区输出井,排队打印

概述:管理软硬件/数据资源,控制程序运行,人机之间接口,应用软件与硬件之间的接口

软件工程基础知识(第五章)

系统开发与设计(第六章)

耦合

内容:一个模块直接访问另一个模块的内容公共:一组模块访问同一个全局数据结构外部:一组模块访问同一个全局简单变量控制:模块间传递的不是数据信息,二十标志/开关量等.一个模块控制另一个模块的功能. 标记:传递数据结构而不是简单数据数据:传递简单的数据项非直接:没有之间关系,通过主模块的控制和调用来实现.

内聚

功能 顺序 通讯 过程 时间 逻辑 偶然

功能:一个模块内所有处理元素仅完成一个功能. 顺序:处理元素必须按顺序执行通讯:使用同一个数据缠身同一个输出数据过程:必须以特定次序执行时间:必须在同一时间内执行逻辑:逻辑上属于相同或相似的一类偶然:毫无关系处理元素偶然组合.

面向对象技术(第七章)

UML

静态结构图Static Structure Diagram

类图

关系

依赖

泛化

关联

组合

整体-部分(同生命周期)

聚合

整体-部分(不同生命周期)

实现

用例图

用例会无条件发生

用例有条件发生

泛化

组件图

包图

交互图Interaction Diagram

时序图

协作图

状态图

活动图

描述活动的流程

实现图Implementation Diagrams

组件图

部署图

算法设计与分析(第八章)

数据库技术基础(第九章)

数据库模式

三级模式-两级映射

内模式

与物理文件打交道

概念模式

表

概念模式的映射

外模式

视图

内模式->概念模式-内模式映射->概念模式->外模式-概念模式映射->外模式

数据库设计

需求分析

数据流图

数据字典

需求说明书

概念结构设计

ER模型

逻辑结构设计

关系模式

物理设计

OS/硬件/DBMS特性

ER模型

ER图说明

方框

实体

子实体方框加竖线

椭圆

属性

菱形

联系 M:N

<ul><li>一个实体转换为一个关系模式</li></ul>

多对多用一个单独的实体记录

关系代数

并

A(a,b,c)∪B(b,c,d)

A∪B(a,b,c,d)

交

A(a,b,c)∩B(b,c,d)

A∩B(b,c)

差

A(a,b,c)差B(b,c,d)

A有B没有的 a

笛卡尔积

AXB

前面的字段来自t1,后面的字段来自t2

属性数为t1与t2的属性数之和,记录为t1,t2的积

t1(1-1-1,2-2-2,3-3-3) t2(4-4-4,5-5-5,6-6-6)

t1Xt2(1-1-1-4-4-4,1-1-1-5-5-5,1-1-1-6-6-6 2-2-2-4-4-4,2-2-2-5-5-5,2-2-2-6-6-6 3-3-3-4-4-4-3-3-3-5-5-5,3-3-3-6-6-6)

投影

t1(c1,c2)

选列的操作

选择

t1(row3)

选行的操作

连接操作

子主题

规范化理论

函数依赖

部分函数依赖

学号,课程号,姓名

主键的一部分可以确定某一个属性

传递函数依赖

A确定B,B确定C,则能推到A能确定C

但B不能确定A,否则A与B就是等价

价值与用途

非规范化,可能存在,数据冗余,更新异常,插入异常,删除异常

数据冗余

员工:部门=1:N 员工表记录部门名称,则部门名称就是冗余的

更新异常

冗余数据更新不一致

插入异常

存在部分依赖时,没有联合主键中其他的属性无法插入

删除异常

部份依赖的信息也被删除了,比如学分,城市.

键

超键

唯一标识元组(单个或者属性的组合)

可能存在冗余属性(多余的标识,,学号,姓名,性别学号或学号,姓名可以确定性别学号与姓名就是超键,去掉一个就是主键)

候选键

超键消除冗余的属性,就是候选键

主键

候选键可以有多个,主键只有一个(学号,身份证号)选其中一个作为主键

外键

别的关系的主键

求候选键

将关系模式的函数依赖关系用有向图标识

找到入度为0的属性,尝试遍历有向图,若能正常遍历途中所有节点,则为候选键

若入度为0的属性不能遍历所有节点,则需要尝试将一些中间节点并入入度为0的属性集种,直至可以遍历所有节点,集合为候选键.

若没有入度为0的,则选择既有入度又有出度的节点

范式

三范式

1NF

属性都是不可分的原子值

列不可拆分

2NF

消除非主属性对候选键的部份依赖

非主属性完全依赖主键(不存在部分依赖)

学号,课程号,成绩,学分

学号与课程号可以确定唯一的成绩

学分快也根据课程号确定,课程号和学分是1:1

所以课程号就是部分依赖

3NF

消除非主属性的传递依赖

主键单属性,单主键不可能有部分依赖

BCNF

消除主属性对候选键的传递依赖

设R是一个关系模式,F是它的依赖集,R属于BCNF当且仅当其F种每个依赖的决定因素必定包含R的候选码

子主题

级别越高,规范程度越高,更有可能解决,插入异常,删除异常,数据冗余.

并发控制

事务

原子

一致

隔离

持久性

一旦提交永久有效

并发产生的问题

丢失更新

不可重复读

脏读

封锁协议

读写锁

S锁

shared lock 共享锁读锁

<span style="color: rgb(51, 51, 51); font-family: -apple-system, BlinkMacSystemFont, "Apple Color Emoji", "Segoe UI Emoji", "Segoe UI Symbol", "Segoe UI", "PingFang SC", "Hiragino Sans GB", "Microsoft YaHei", "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 16px;">又称读锁，若事务T对数据对象A加上S锁，则事务T可以读A但不能修改A，其他事务只能再对A加S锁，而不能加X锁，直到T释放A上的S锁。

X锁

exclusive lock 排他锁写锁

又称写锁。若事务T对数据对象A加上X锁，事务T可以读A也可以修改A，其他事务不能再对A加任何锁，直到T释放A上的锁。

一级封锁协议

事务T在修改数据前必须对其加X锁,可防止丢失修改.

二级封锁协议

读数据前先对其加S锁,读完即释放S锁.可防止丢失修改,防止读藏数据

三级封锁协议

一级加上读加S锁,直到事务释放才释放.

二段锁协议

可串行化

死锁问题