scrapy笔记

2020-01-09

pyopenssl 19.1.0 has requirement cryptography>=2.8, but you'll have cryptography 2.3 which is incompatible.

微电子期末

2020-01-04

半导体物理基础

半导体材料

导体:$\rho < 10^{-4}\Omega\cdot cm$
绝缘体:$\rho > 10^{9}\Omega\cdot cm$

本征半导体,空穴及其导电作用

载流子:可以自由移动的带电粒子
电导率:与材料单位体积中所含载流子数有关,载流子浓度越高,电导率越高
本征激发:当半导体受热或光照激发时,某些电子从外界获得足够的能量而挣脱共价键的束缚,离开原子成为自由电子,同时在共价键中留下相同数量的空穴
空穴:共价键中的空位
电子空穴对:由热激发而产生的自由电子和空穴对

半导体的重要特性

在本征半导体中自由电子和空穴总是成对产生,其自由电子-空穴对随温度的增高而显著增加
空穴的导电作用

本证半导体的缺点:载流子少,导电性差,温度稳定性差

杂质半导体

参入杂质的本征半导体称为杂质半导体

P型半导体

参入3价杂质元素(如硼,镓和铟)的半导体
空穴(p)是多数载流子(多子),它主要由掺杂形成;自由电子(n)是少数载流子(少子),由热激发形成
空穴很容易俘获电子,使杂质原子成为负离子.3价杂质因而也称为受主杂质($N_A$)
$$ N_A + n = p $$

N型半导体

参入5价杂质元素(如磷)的半导体
自由电子(n)是多数载流子,主要由杂质原子提供;空穴(p)是少数载流子,由热激发形成
提供自由电子的5价杂质原子因带正电荷而成为正离子.因此5价杂质原子也称为施主杂质($N_D$)
$$ n = p + N_D $$

载流子的漂移与扩散

漂移电流:在电场作用下,载流子(自由电子/空穴)在电场作用下的漂移运动形成的电流
扩散电流:因浓度差,载流子从浓度高处向浓度低处扩散运动,形成的电流

PN结

对于P型半导体和N型半导体的结合面,离子薄层形成的空间电荷区称为PN结

在空间电荷区,由于缺少多子,所以也称耗尽层

PN结的单向导电性

当外加电压使PN结中P区的电位高于N区的电位,称为加正向电压,简称正偏;反之称为加反向电压,简称反偏
PN结加正向电压时,呈现低电阻,具有较大的正向扩散电流
PN结加反向电压时,呈现高电阻,具有很小的反向漂移电流
PN结$V$-$I$特性表达式:$i_D=I_S(e^{v_D/V_r}-1)$
$I_S$:反向饱和电流
$V_T$:温度的电压当量.在常温下$V_T=\dfrac{kT}{q}=26mV$

PN结的反向击穿

电击穿(可逆)
- 雪崩击穿:有正温度系数
- 齐纳击穿:有负温度系数
热击穿(不可逆)

PN结的电容效应

扩散电容$C_D$:TODO
势垒电容$C_B$:TODO

二极管

二极管的$V$-$I$特性

二极管的伏安特性曲线可表示:$i_D=I_S(e^{v_D/V_T}-1)$

硅二极管的死区电压$V_{th}=0.5-0.8V$左右
锗二极管的死区电压$V_{th}=0.1-0.3V$左右

二极管的主要参数

最大整流电流$I_F$
反向击穿电压$V_{BR}$和最大反向工作电压$V_{RM}$:实际工作时,最大反向工作电压一般只按反向击穿电压的一半计算
反向电流$I_R$在室温下,最大反向工作电压下的反向电流值.硅二极管的反向电流一般在$nA$级;锗二极管在$\mu A$级
极间电容$C_d=C_B+C_D$(TODO)
反向恢复时间$T_{RR}$
正向压降$V_F$:二极管能够导通的正向最低电压.硅二极管约$0.6-0.8V$,锗二极管约$0.2-0.3V$

二极管电路的简化模型分析方法

理想模型

恒压降模型

管压降恒定:

硅管$0.7V$
锗管$0.3V$

折线模型

硅管:

门槛电压$V_{th}=0.5V$
导通电流为1$mA$时,管压降为$0.7V$
$r_D=200\Omega$

小信号模型

常温下微变电阻$(300K)r_d=\dfrac{V_T}{I_D}=\dfrac{26(mV)}{I_D}$

模型分析法应用举例

限幅电路

开关电路

低电压稳压电路

小信号工作情况分析

TODO

齐纳二极管

半导体三极管

三极管的结构和符号

集电极$c$ollector,集电区,集电结
基极$b$ase,基区
发射极$e$mitter,发射区,发射结

放大状态下三极管的工作原理

实现放大的外部条件:发射结正偏,集电结反偏

实现放大的内部条件:发射区杂质浓度远大于基区杂质浓度,且基区很薄

共基极直流放大系数$\bar{\alpha}=\dfrac{\text{传输到集电极的电流}}{\text{发射极注入电流}}=\dfrac{I_{C}-I_{CBO}}{I_{E}}\approx\dfrac{I_C}{I_E}$

共射极直流放大系数$\bar{\beta}=\dfrac{\bar{\alpha}}{1-\bar{\alpha}}$

反向饱和电流/穿透电流$I_{CEO}=(1+\bar{\beta})I_{CBO}$

当$I_C >> I_{CEO}$时,忽略$I_{CEO}$,则$\bar{\beta}\approx\dfrac{I_C}{I_B}$

三极管的三种组态

共发射极接法:CE
共基极接法:CB
共集电极接法:CC

BJT的$I$-$V$特性曲线

输入特性曲线

$$i_B=f(v_{BE})|_{v_{CE}=const}$$

死区
非线性区
近似线性区

输出特性曲线

$$i_C=f(v_{CE})|_{i_B=const}$$

饱和区:$i_C$明显受$v_{CE}$控制的区域,该区域内,一般$v_{CE} < 0.7V$(硅管).此时,发射结正偏,集电结正偏或反偏电压很小
截止区:$i_C$接近0的区域,相当$i_B=0$的曲线的下方.此时,$v_{BE}$小于死区电压
放大区:$i_C$平行于$v_{CE}$轴的区域,曲线基本平行等距.此时,发射结正偏,集电结反偏
Early效应
输出特性比较平坦的部分随着$V_{CE}$的增加略向上倾斜

BJT的主要参数

电流放大系数
- 共发射极直流电流放大系数$\bar{\beta}=\dfrac{I_C-I_{CEO}}{I_B}\approx\dfrac{I_C}{I_B}|_{v_{CE}=const}$
- 共发射极交流电流放大系数$\beta=\dfrac{\Delta I_C}{\Delta I_B}|_{v_{CE}=const}$
- 共基极直流电流放大系数$\bar{\alpha}=\dfrac{I_C-I_{CBO}}{I_E}\approx\dfrac{I_C}{I_E}$
- 共基极交流电流放大系数$\alpha=\dfrac{\Delta I_C}{\Delta I_E}|_{v_{CB}=const}$
  当$I_{CBO}$和$I_{CEO}$很小时,$\bar{\alpha}\approx\alpha,\bar{\beta}\approx\beta$,可以不加区分
极间反向电流
极限参数
- 集电极最大允许电流$I_{CM}$
- 集电极最大允许功率损耗$P_{CM}=I_CV_{CE}$
- 反向击穿电压
- $V_{(BR)CBO}$:发射极开路时的集电结反向击穿电压
- $V_{(BR)EBO}$:集电极开路时的发射结的反向击穿电压
- $V_{(BR)CEO}$:基极开路时的集电极和发射极间的击穿电压

温度对BJT参数及特性的影响

温度对BJT参数的影响

温度对BJT特性曲线的影响

三极管放大电路

共射极放大电路的工作原理

静态

静态工作点(TODO)

动态

BJT放大电路的图解分析法

静态工作点的图解分析

负载线
- 输入:$V_{BE}=V_{BB}-i_BR_b$
- 输出:$V_{CE}=V_{CC}-i_CR_c$

动态工作情况的图解分析

静态工作点对波形失真的影响

放大电路的动态范围

温度对工作点的影响(定性)

温度变化对$I_{CBO}$的影响

$I_{CBO}=I_{CBO(T_0=25^{\circ}C)}\cdot e^{k(T-T_0)}$

温度$T$上升$\to$输出特性曲线上移

温度变化对输入特性曲线的影响

$V_{BE}=V_{BE(T_0=25^{\circ}C)}-(T-T_0)\times2.2\times10^{-3}V$

温度$T$上升$\to$输入特性曲线左移

温度变化对$\beta$的影响

温度每升高1$^{\circ}C,\beta$要增加$0.5\%\sim1.0\%$

温度$T$上升$\to$输出特性曲线族间距增大

基极分压式射极偏置电路

工作原理

TODO

场效应管

场效应管的分类

MOSFET(IGFET)绝缘栅型
1. 增强型
  - N沟道
  - P沟道
2. 耗尽型
  - N沟道
  - P沟道
JFET结型(耗尽型)
1. N沟道
2. P沟道

耗尽型:场效应管没有加偏置电压时,就有导电沟道存在
增强型:场效应管没有加偏置电压时,没有导电沟道

结构

源极$s$ource
栅极$g$ate
漏极$d$rain

特性曲线

输出特性曲线

截止区
可变电阻区(非饱和区)
饱和区(恒流区,放大区):必须让FET工作在饱和区(放大区)才有放大作用

N沟道:$v_{GS},v_{DS}\uparrow,i_D\uparrow$
P沟道:$v_{GS},v_{DS}\downarrow,|i_D|\uparrow$

转移特性曲线

N沟道:$v_{GS},i_D\uparrow$
P沟道:$v_{GS},|i_D|\uparrow$

主要参数

$V_T$:(增强型参数)开启电压
$V_{TN}$:N沟道增强型开启电压
$V_P$:(耗尽型/结型参数)夹断电压
饱和漏电流$I_{DSS}$(耗尽型):在$V_{GS}=0$的情况下,当$V_{DS} > V_P$时的漏极电流称为饱和漏极电流.通常令$|V_{DS}|=10V,V_{GS}=0V$时测出的$i_D$就是$I_{DSS}$.在转移特性上,就是$V_{GS}=0$时的漏极电流
直流输入电阻$R_{GS}$:在漏源之间短路的条件下,漏源之间加一定电压时的栅源直流电阻就是直流输入电阻

N沟道增强型MOSFET

工作原理

$V_{GS}$对沟道的控制作用
- 当$V_{GS}\le0$时
  无导电沟道.$d,s$间加电压时,也无电流产生
- 当$0 < V_{GS} < V_{TN}$时
  产生电场,但未形成导电沟道(反型层),$d,s$间加电压后,没有电流产生
- 当$V_{GS} > V_{TN}$时
  在电场作用下产生导电沟道,$d,s$间加电压后,将有电流产生.$V_{GS}$越大,导电沟道越厚
$V_{DS}$对沟道的控制作用
当$V_{GS}$一定($V_{GS} > V_{TN}$)时
- $V_{DS}$增加$\to I_D$增加$\to$沟道电位梯度增加$\to$靠近漏极$d$处的电位升高$\to(d)$电场强度减小$\to(d)$沟道变薄
- 当$V_{DS}$增加到使$V_{GD}=V_{TN}$时,在紧靠漏极处出现预夹断
- 预夹断后,$V_{DS}$增加$\to$夹断区延长$\to$沟道电阻增加$\to I_D$基本不变
$V_{DS}$和$V_{GS}$同时作用时
$V_{DS}$一定,$V_{GS}$变化时,给定一个$V_{GS}$,就有一条不同的$i_D$-$V_{DS}$曲线

N沟道耗尽型MOSFET

P沟道MOSFET

沟道长度调制等几种效应

沟道长度调制效应
饱和区的曲线并不是平坦的
衬底调制效应(体效应)
- 衬底未与源极并接时,衬底与源极间的偏压$V_{BS}$将影响实际的开启/夹断电压和转移特性
  - 阈值电压升高
  - TODO
- 为保证导电沟道与衬底之间的PN结反偏,要求
  - N沟道:$V_{BS}\le0$
  - P沟道:$V_{BS}\ge0$
击穿效应
1. 漏衬击穿:外加的漏源电压过高,将导致漏极到衬底的PN结击穿
2. 栅极击穿:栅极电压过高,绝缘层击穿
  - 通常在MOS管的栅源间接入双向稳压管,限制栅极电压

JFET的结构和工作原理

工作原理

$V_{GS}$对沟道的控制作用
当$V_{GS} < 0$时:PN结反偏$\to$耗尽层加厚$\to$沟道变窄
$V_{GS}$继续减小,沟道继续变窄
当沟道夹断时,对应的栅源电压$V_{GS}$称为夹断电压$V_P$或$V_{GS(off)}$
对于N沟道的JFET,$V_P < 0$
$V_{DS}$对沟道的控制作用
当$V_{GS}=0$时:$V_{DS}$增加$\to g,d$间PN结的反向电压增加,使靠近漏极处的耗尽层加宽,沟道变窄,从上至下呈楔形分布
当$V_{DS}$增加到使$V_{GD}=V_P$时,在紧靠漏极处出现预夹断.此时$V_{DS}$增加$\to$夹断区延长$\to$沟道电阻增加$\to i_D$基本不变
$V_{GS}$和$V_{DS}$同时作用时
当$V_P < V_{GS} < 0$时,导电沟道更容易夹断,对于同样的$V_{DS},i_D$的值比$V_{GS}=0$时的值要小
在预夹断处:$V_{GD}=V_{GS}-V_{DS}=V_P$

FET和BJT重要特性的比较

对应关系
输入对输出的控制
- BJT:基-射极间电压$V_{BE}$控制集电极电流$i_C$
- MOS管:栅源电压$V_{GS}$控制漏极$i_D$
- 在放大区域内,MOS管的$i_D$与$V_{GS}$之间是平方关系,而BJT的$i_C$与$V_{BE}$之间是指数关系.所以通常BJT的跨导要大于MOS管的跨导
- 因MOS管的栅极电流$i_G=0$而BJT的基极电流$i_B\not=0$,且电压$V_{BE}$首先影响$i_B$(或$i_E$)然后通过$i_B$()实现对$i_E$()的控制,故常将BJT称为电流控制器件,MOS管称为电压控制器件
跨导:TODO
输出电阻:TODO
MOS管的$K_n$与BJT的$\beta$或$\alpha$:TODO

场效应管放大电路

基本共源极放大电路的组成

TODO

基本共源放大电路的工作原理

TODO

用图解方法确定静态工作点$Q$

TODO

放大电路模型

信号

信号:信息的载体
电信号:用电量来描述信息的变化

模拟信号和数字信号

时间连续,数值连续:模拟信号
事件离散,数值连续:AD(analog,digital)转换新号
时间连续,数值离散:DA转换新号
事件离散,数值离散:数字信号

放大电路

放大电路的符号及模拟信号放大

放大电路模型

电压放大模型

$A_v=\dfrac{v_o}{v_i}=A_{vo}\dfrac{R_L}{R_o+R_L}$

负载大小会影响增益的大小
减小负载的影响
减小输入回路对信号的衰减影响

电流放大模型

$A_i=\dfrac{i_o}{i_i}=A_{is}\dfrac{R_o}{R_o+R_L}$

减小负载的影响
减小对信号源的衰减

互阻放大模型

TODO

互导放大模型

TODO

隔离放大电路模型

TODO

放大电路的主要性能指标

输入电阻

$R_i=\dfrac{v_i}{i_i}$

决定了放大电路从信号源吸取信号幅值的大小

电压放大和互导放大->输入信号为电压-> $R_i$大
电流放大和互阻放大->输入信号为电流-> $R_i$小

输出电阻

$R_o=\dfrac{v_t}{i_t}|_{v_s=0,R_L=\infty}$

决定了放大电路带负载的能力

电压放大和互阻放大->输出信号为电压-> $R_o$小
电流放大和互导放大->输出信号为电流-> $R_o$大

增益

电压增益$A_v=\dfrac{v_o}{v_i}$
电流增益$A_i=\dfrac{i_o}{i_i}$
互阻增益$A_r=\dfrac{v_o}{i_i}$
互导增益$A_g=\dfrac{i_o}{v_i}$

其中$A_v,A_i$常用分贝$(dB)$表示

电压增益$=20\lg|A_v|$
电流增益$=20\lg|A_i|$
功率增益$=10\lg A_p$

频率响应(基本概念)及带宽(识图)

频率响应:在输入正弦信号下,输出随输入信号频率连续变化的稳态响应
频率失真
- 幅度失真:对不同频率信号增益不同产生的失真
- 相位失真:对不同频率的信号相移不同产生的失真

非线性失真

由元件非线性特性引起的失真
在频谱图上表现为新的频率分量产生

频谱图

运算放大器

符号
电路模型

集成电路运算放大器

当$A_{V_O}(v_P-v_N)\ge V_+$时,$v_O=V_+$
当$A_{V_O}(v_P-v_N)\le V_-$时,$v_O=V_-$
电压传输特性$v_O=f(V_P-V_N)$

运算放大器的电压传输特性

设$v_p > v_N$

线性区

$V_- < A_{V_O}(v_p-v_N) < V_+$
$v_O=A_{V_O}(v_p-v_N)$

饱和区
- $A_{V_O}(v_p-v_N)\ge V_+$
  $v_O=+V_{om}=V_+$
- $A_{V_O}(v_p-v_N)\le V_-$
  $v_O=-V_{om}=V_-$

理想运算放大器

理想运算放大器特点

开环差模电压增益$A_{V_O}=\infty$
差模输入电阻$r_{id}=\infty$
输出电阻$r_O=0$

反馈(概念)

讲系统的输出返回到输入端并以某种方式改变输入,进而影响系统功能的过程

正反馈
负反馈

反馈的电压增益

深度负反馈

$1+A_{V_O}F_V >> 1$
闭环增益$A\approx\dfrac{1}{F}$(反馈系数)

$A_V=\dfrac{v_o}{v_i}\approx\dfrac{1}{F_V}=1+\dfrac{R_2}{R_1}$

虚短和虚断

$A_V=\dfrac{v_o}{v_i}\approx\dfrac{1}{F_V}=\dfrac{v_o}{v_f}=\dfrac{v_o}{v_N} \Rightarrow v_i\approx v_f$或$v_P\approx v_N$

虚短:在深度负反馈作用下,$v_N$自动跟踪$v_P$,净输入电压$(v_P-v_N)\to0$,即$P$端与$N$端相当于短路
虚断:由于$(v_P\approx v_N)$,而运放的输入电阻阻值又很高,因此流经两输入端之间的电流$i_P=i_N\approx0$

同相放大电路

电压增益

根据虚短和虚断的概念

$v_n=v_p=v_i$
$\dfrac{v_n-0}{R_1}=\dfrac{v_o-v_n}{R_2}$
$\to A_V=\dfrac{v_o}{v_i}=\dfrac{R_1+R_2}{R_1}=1+\dfrac{R_2}{R_1}$

输入电阻

$R_i=\dfrac{v_i}{i_i}\to\infty$

输出电阻

$R_O=r_O\parallel[(R_1\parallel r_i)+R_2]\to0$

同相放大电路-电压跟随器

$v_o=v_n\approx v_p=v_i$

反相放大电路

电压增益

根据虚短和虚断的概念

$v_n\approx v_p=0$(虚地)
$\dfrac{v_i-v_n}{R_1}=\dfrac{v_n-v_O}{R_2}$
$\to A_V=\dfrac{v_O}{v_i}=-\dfrac{R_2}{R_1}$(负号表示输出与输入反向)

输入电阻

$R_i=\dfrac{v_i}{i_i}=\dfrac{v_i}{v_i/R_1}=R_1$

输出电阻

$R_O=r_O\parallel R_2\to0$

求差电路

$R_4=R_1,R_2=R_3$

电压增益:$A_v=\dfrac{v_o}{v_{i2}-v_{i1}}$
输入电阻:$R_i=\dfrac{v_{i2}-v_{i1}}{i_2}$
输出电阻:$R_o\to0$

求和电路

$R_1=R_2=R_3$

输出再接一级反向电路

数字逻辑

数字信号

模拟信号:时间和数值均连续变化的电信号,如正弦波,三角波
数字信号:在时间上和数值上均是离散的信号
模拟信号的数字表示:由于数字信号便与存储,分析和传输,通常将模拟信号转换为数字信号

数字信号的描述方法

二值数字逻辑和逻辑电平
- 二值数字逻辑:0,1数码
  - 二进制数:表示数量
  - 二值逻辑:表示事物状态
- 表示方式:在电路中用低,高电平表示0,1两种逻辑状态
数字波形:信号逻辑电平对时间的图形表示
- 主要参数
  - 周期($T$):两个相邻脉冲之间的时间间隔
  - 脉冲宽度($t_w$):脉冲幅值的50%所跨越的时间
  - 占空比($Q$):脉冲宽度栈整个周期的百分比
  - 上升/下降时间($t_r/t_f$):从脉冲幅值10%到90%锁经历的时间

二值逻辑变量与基本逻辑运算

逻辑符号/逻辑表达式

逻辑门电路

一般特性

输入和输出的高,低电平
- $V_{IL(max)}$:输入低电平的上限值
- $V_{IH(min)}$:输入高电平的下限值
- $V_{OL(max)}$:输出低电平的上限值
- $V_{OH(min)}$:输出高电平的下限值
噪声容限

在保证输出电平不变的条件下,输出电平允许波动的范围

负载门输入高电平时的噪声容限:$V_{NH}-$当前级门输出高电平的最小值时允许负向噪声电压的最大值
$V_{NH}=V_{OH(min)}-V_{IH(min)}$

负载门输入低电平时的噪声容限:$V_{NL}-$当前级门输出低电平的最大值时允许正向噪声电压的最大值
$V_{NL}=V_{IL(max)}-V_{OL(max)}$

传输延迟时间

开关速度的参数,说明门电路在输入脉冲波形的作用下,其输出波形相对于输入波形延迟了多长的时间

功耗
- 静态功耗:电路没有状态转换时的功耗,即门电路空载时电源总电流$I_D$与电源电压$V_{DD}$的乘积
- 动态功耗:电路在输出状态转换时的功耗
- 对于TTL门电路,静态功耗是主要的.CMOS电路的静态功耗非常低,有动态功耗
延时-功耗积
是速度功耗综合性的指标,用符号$DP$表示
$DP=\dfrac{t_{pLH}+t_{pHL}}{2}P_D$
扇入与扇出数
- 扇入数:取决于逻辑门的输入端的个数
- 扇出数:在正常工作情况下,所能带同类门电路的最大数目

MOS开关及其等效电路

当$v_1 < V_T$:MOS管截止,输出高电平
当$v_1 > V_T$并且比较大:MOS管工作在可变电阻区,输出低电平

当输入为低电平时
MOS管截止,相当于开关断开,输出为高电平
当输入为高电平时
MOS管工作在可变电阻区,相当于开关闭合,输出为低电平

MOS管相当于一个由$V_{GS}$控制的无触点开关

CMOS反向器

CMOS逻辑门

CMOS传输门

TODO

TTL

TTL反向器
TTL与非门
TTL或非门

半导体存储器(基本概念)

RAM(随机存取存储器):在运行状态可以随时进行读或写操作.存储的数据必须有电源供应才能保存,一旦掉电,数据全部丢失
ROM(只读存储器):在正常工作状态只能读出信息.断电后信息不会丢失
字长(位数)
字数
地址
存储容量=字数$\times$位数
掩摸ROM
- 存储矩阵的每个交叉点是一个存储单元,存储单元中有期间存入1,无器件存入0
- 出厂时已经固定,适合大量生产,便宜,非易失性
可变长ROM(PROM)
- 存储单元与掩摸ROM不同
- 熔丝由易熔合金制成,出厂时每个节点上都有,编程时讲不用的熔断.一次性编程,不能改写
可擦除的的可编程ROM(EPROM)
- 存储单元与掩摸ROM不同
- 用紫外线擦除的PROM(UVEPROM)
- SIMOS 叠栅注入MOS管
  - 若$G_f$上充负电荷,则$G_c$处于正常逻辑高电平下不导通
  - 若$G_f$上为充负电荷,则$G_c$处于正常逻辑高电平下导通
  - 写入:雪崩注入.$D$-$S$间加高压($20-25V$),发生雪崩击穿,同时在$G_c$上加$25V,50ms$宽的正脉冲,吸引高速电子穿过$SiO_2$到达$G_f$,形成注入电荷
  - 擦除:通过照射产生电子-空穴对,提供泄放通道.紫外线照射20-30分钟,阳光下一周,荧光灯下3年
电可擦除的可编程ROM(E$^2$PROM)
- 微客服UVEPROM擦除慢,操作不便的缺点,采用FLOTOX(浮栅隧道氧化层MOS管)
- $G_f$与$D$之间有小的隧道区,$SiO_2$厚度$< 2\times10^{-8}m$
- 当场强大到一定大小($10^7V/cm$)时,电子会穿越隧道
- TODO
快闪存储器(Flash Memory)
静态随机存储器SRAM
- 存储单元:6个N沟道增强型MOS管
动态随机存储器DRAM
- 利用MOS管栅极电容可以存储电荷的原理
SRAM和DRAM的区别
- SRAM:速度快,贵

微电子学的新发展(基本概念)

冯诺依曼架构:用数学模型和算法来描述和模仿神经元的行为和相互关系,但计算仍然运行在传统的计算机上
非冯诺依曼架构:用电子器件模拟生物神经元的功能,构建新的神经计算机
忆阻器:$V(t)=M(q(t))I(t)$.功能如同电阻,但在关掉电源后,仍能记忆先前通过的电荷量.忆阻器的电阻值取决于多少电荷经过了这个器件:让电荷以一个方向流过,电阻会增加;让点何以相反的方向流过,电阻就会减小
- 工作原理:一块极薄的二氧化钛($TiO_2$)被夹在两个电极中间,分成2个部分,一般是正常的二氧化钛,另一半进行了掺杂,少了几个氧原子($TiO_{2-x}$),掺杂的那一半带正电.当电流从掺杂的一边通向正常的一边时,在电场的影响下缺氧的掺杂物会往正常的一侧游移,使得掺杂的部分会占较高的比重,整体的电阻降低
- 特点
  - 输入输出关系是非线性的
  - 输入和输出都是连续的,其存储的精度理论上是无限的
  - 无源电路元器件,方便将其应用在电路中,形成混合型电路
  - 非易失性
  - 高集成密度,高读写速度,低功耗,多值计算
- 应用前景
  - TODO
  - 存算一体
石墨烯:一种由碳原子构成的单层片状结构的新材料
- 极薄极轻,比表面积$2630m^2/g$
- 导热率为$3000-5000W/mK$
- 极强的力学性能
- 优良的导电性
- 制备方法
  - 物理方法
    - 机械剥离法
    - 液相或气相直接剥离法
  - 化学方法
    - 表面析出生长法
    - 氧化石墨还原法
    - 化学气相沉积法
    - 化学合成法
- 应用前景
  - 低成本石墨烯电池
  - 可折叠弯曲屏
  - 石墨烯传感器
  - 石墨烯过滤器
  - 石墨烯生物器件
  - 石墨烯感光元件
  - 太阳能电池
  - 柔性微处理器
- 由石墨烯到二维材料
  1. 结构有序
  2. 在二维平面生长
  3. 在第三维度超薄
自旋场效应晶体管
- 电子的电荷与自旋:在半导体材料中有电子和空穴两种载流子,极化电子优自旋向上和向下两种载流子
- 电子的自旋极化:TODO
柔性电子学
- 概念:涵盖有机电子,塑料电子,生物电子,纳米电子,印刷电子等技术,是将有机/无机材料电子器件制作在柔性/可延性基板上的新兴电子技术.相对于传统电子,柔性电子具有更大的灵活性.
- 应用场景:TODO,柔性显示,有机电致发光显示与照明,化学与生物传感器,柔性光伏,柔性逻辑与存储,柔性电池,可穿戴设备
- 柔性电子器件的材料
  - 碳纳米管
  - 金属氧化物半导体薄膜
  - 金属纳米薄膜,金属纳米线
  - 有机高分子薄膜
  - 水凝胶离子导体
  - 液态金属
- 柔性电子制造方法
  - 转移印刷
  - 喷墨印刷
  - 纤维结构形成
- 可拉伸结构的设计:TODO

提纲

半导体三极管

输入特性曲线
输出特性曲线
- 区域,含义
主要参数

三极管放大电路

共射极放大电路
- 工作原理
- 计算静态工作点
- 负载线
- 失真和静态工作点的关系
- 温度对工作点的影响(定性)
- 基极分压式射极偏置电路(认识,工作原理)

场效应管

不同类型的管子
- 符号
- 结构
- 工作原理
- 特性曲线
  - 输出(分区)
  - 转移
- 几种效应
- 主要(直流)参数

场效应管放大电路

基本共源极放大电路
- 工作原理(不要求公式)
图解法求静态工作点
- 负载线与输出特性曲线

放大电路模型

基本定义
符号
增益的定义
几种模型
性能指标
- 输入电阻
- 输出电阻
- 增益
- 频率响应和带宽:基本概念,识图
- 非线性失真:概念,识图(不要求计算)

运算放大器

组成单元
结构框图
符号
电路模型
参数特点
理想运放
反馈:概念
深度负反馈:概念
虚短,虚断
几种电路
- 基本形式
- 特征

数字逻辑

概念
逻辑符号,逻辑表达式

逻辑门电路(不要求分析)

基本参数
反向器,与非门,或非门,传输门
TTL(反向器)(认识)

ubuntu使用

2019-02-25

零散笔记

摄像头(webcam)

sudo apt install v4l-util cheese
sudo cheese

修改摄像头权限

ls -ltrh /dev/video*
sudo chmod 777 /dev/video0
cheese

重启驱动

重启触摸板驱动

sudo modprobe -r psmouse
sudo modprobe psmouse

或

sudo rmmode psmouse
sudo modprobe psmouse

或

xinput list
xinput --disable {编号}
xinput --enable {编号}

在文件夹中执行脚本

在文件$\to$首选项$\to$行为$\to$可执行文本文件

快捷键

不要出现fn+super的组合

截屏

复制截图到剪切板:ctrl+print
复制窗口截图到剪切板:ctrl+alt+print
复制选区截图到剪切板:shift+ctrl+print
保存截图到图片:print
保存窗口截图到图片:alt+print
保存选区截图到图片:shift+print
录屏:shift+ctrl+alt+r

禁用快捷键

backspace

WLAN

wifi连接

参考:askubuntu

查看网卡名:iwconfig
扫描:nmcli dev wifi
连接:nmcli dev wifi connect WLAN_NAME password PASSWORD
忘记:nmcli c delete WLAN_NAME
关闭热点:nmcli dev disconnect wlp2s0

热点

nm-connection-editor

+->Wifi->Mode:Hotspot
开启热点
- 设置->(右上角)Connect to Hidden Network
- 设置$\to$wifi$\to$打开wifi热点

共享wifi

create_ap:github

误删`PATH`救急

Linux通用?

export PATH=/usr/local/sbin:/usr/local/bin:/sbin:/bin:/usr/sbin:/usr/bin:$PATH

不要忘记加:PATH

安装字体

sudo mkdir /usr/share/fonts/{name}
sudo cp {font}.ttf /usr/share/fonts/{name}
cd /usr/share/fonts/{name}
sudo mkfontscale
sudo mkfontdir
sudo fc-cache -fv

文件编码

功能性软件

文件管理器

由于ubuntu自带的文件管理器太睿智,推荐以下文件管理器

pcmanfm
nemo
thunar
dolphin

修改默认文件管理器

TODO:/etc/gnome/defaults.list(直接修改好像没用)

# what's the current default file manager?
xdg-mime query default inode/directory

# set nautilus as a default file manager
xdg-mime default nautilus.desktop inode/directory # application/x-gnome-saved-search

软件对应/usr/share/applications下的desktop名

matlab

参考:CSDN

mathematica

报错

CRITICAL FAILURE: PrintIntroduction() Error
$ProductTitle not defined.

路径不能有空格

一个解决包依赖问题的软件

sudo apt install aptitude

(示例)卸载libreoffice

sudo aptitude purge libreoffice6.0

字体编辑

sudo add-apt-repository ppa:fontforge/fontforge
sudo apt-get update
sudo apt-get install fontforge

修改字体名称

打开字体文件
基础->字体信息
文件->生成字体->(可选)选择TrueType(ttf)

图像编辑

sudo apt install gimp

sudo apt install krita
sudo apt install krita-l10n

图像转换

sudo apt install sam2p
sam2p shit.png shit.gif

gif录屏

byzanz

sudo apt install byzanz 
byzanz-record --duration=50 --delay=3 --x=1030 --y=100 --height=500 demo1.gif

桌面便签(Indicator Stickynotes)

sudo add-apt-repository ppa:umang/indicator-stickynotes
sudo apt-get update
sudo apt-get install indicator-stickynotes

下载器(TODO)

wget:单线程
curl:单线程
axel:多线程
aria2:可以设置线程
mwget:多线程版wget
Prozilla:多线程,cmd,gui
Downloader for X:多线程,gui
MyGet:多线程
Linuxdown:多线程,cmd
Transmission:磁力,gui(不会用)
Uget:cURL+aria2

基本没用

屏幕管理

arandr

sudo apt install arandr

镜像源

/etc/apt/sources.list

ubuntu 19.04

deb http://cn.archive.ubuntu.com/ubuntu/ disco main restricted
deb http://cn.archive.ubuntu.com/ubuntu/ disco-updates main restricted
deb http://cn.archive.ubuntu.com/ubuntu/ disco universe
deb http://cn.archive.ubuntu.com/ubuntu/ disco-updates universe
deb http://cn.archive.ubuntu.com/ubuntu/ disco multiverse
deb http://cn.archive.ubuntu.com/ubuntu/ disco-updates multiverse
deb http://cn.archive.ubuntu.com/ubuntu/ disco-backports main restricted universe multiverse
deb http://security.ubuntu.com/ubuntu disco-security main restricted
deb http://security.ubuntu.com/ubuntu disco-security universe
deb http://security.ubuntu.com/ubuntu disco-security multiverse

中科大

deb https://mirrors.ustc.edu.cn/ubuntu/ bionic main restricted universe multiverse
deb-src https://mirrors.ustc.edu.cn/ubuntu/ bionic main restricted universe multiverse
deb https://mirrors.ustc.edu.cn/ubuntu/ bionic-updates main restricted universe multiverse
deb-src https://mirrors.ustc.edu.cn/ubuntu/ bionic-updates main restricted universe multiverse
deb https://mirrors.ustc.edu.cn/ubuntu/ bionic-backports main restricted universe multiverse
deb-src https://mirrors.ustc.edu.cn/ubuntu/ bionic-backports main restricted universe multiverse
deb https://mirrors.ustc.edu.cn/ubuntu/ bionic-security main restricted universe multiverse
deb-src https://mirrors.ustc.edu.cn/ubuntu/ bionic-security main restricted universe multiverse
deb https://mirrors.ustc.edu.cn/ubuntu/ bionic-proposed main restricted universe multiverse
deb-src https://mirrors.ustc.edu.cn/ubuntu/ bionic-proposed main restricted universe multiverse

清华

deb https://mirrors.tuna.tsinghua.edu.cn/ubuntu/ bionic main restricted universe multiverse
deb-src https://mirrors.tuna.tsinghua.edu.cn/ubuntu/ bionic main restricted universe multiverse
deb https://mirrors.tuna.tsinghua.edu.cn/ubuntu/ bionic-updates main restricted universe multiverse
deb-src https://mirrors.tuna.tsinghua.edu.cn/ubuntu/ bionic-updates main restricted universe multiverse
deb https://mirrors.tuna.tsinghua.edu.cn/ubuntu/ bionic-backports main restricted universe multiverse
deb-src https://mirrors.tuna.tsinghua.edu.cn/ubuntu/ bionic-backports main restricted universe multiverse
deb https://mirrors.tuna.tsinghua.edu.cn/ubuntu/ bionic-security main restricted universe multiverse
deb-src https://mirrors.tuna.tsinghua.edu.cn/ubuntu/ bionic-security main restricted universe multiverse
deb https://mirrors.tuna.tsinghua.edu.cn/ubuntu/ bionic-proposed main restricted universe multiverse
deb-src https://mirrors.tuna.tsinghua.edu.cn/ubuntu/ bionic-proposed main restricted universe multiverse

网易

deb http://mirrors.163.com/ubuntu/ bionic main restricted universe multiverse
deb http://mirrors.163.com/ubuntu/ bionic-security main restricted universe multiverse
deb http://mirrors.163.com/ubuntu/ bionic-updates main restricted universe multiverse
deb http://mirrors.163.com/ubuntu/ bionic-proposed main restricted universe multiverse
deb http://mirrors.163.com/ubuntu/ bionic-backports main restricted universe multiverse
deb-src http://mirrors.163.com/ubuntu/ bionic main restricted universe multiverse
deb-src http://mirrors.163.com/ubuntu/ bionic-security main restricted universe multiverse
deb-src http://mirrors.163.com/ubuntu/ bionic-updates main restricted universe multiverse
deb-src http://mirrors.163.com/ubuntu/ bionic-proposed main restricted universe multiverse
deb-src http://mirrors.163.com/ubuntu/ bionic-backports main restricted universe multiverse

阿里

deb http://mirrors.aliyun.com/ubuntu/ bionic main restricted universe multiverse
deb http://mirrors.aliyun.com/ubuntu/ bionic-security main restricted universe multiverse
deb http://mirrors.aliyun.com/ubuntu/ bionic-updates main restricted universe multiverse
deb http://mirrors.aliyun.com/ubuntu/ bionic-proposed main restricted universe multiverse
deb http://mirrors.aliyun.com/ubuntu/ bionic-backports main restricted universe multiverse
deb-src http://mirrors.aliyun.com/ubuntu/ bionic main restricted universe multiverse
deb-src http://mirrors.aliyun.com/ubuntu/ bionic-security main restricted universe multiverse
deb-src http://mirrors.aliyun.com/ubuntu/ bionic-updates main restricted universe multiverse
deb-src http://mirrors.aliyun.com/ubuntu/ bionic-proposed main restricted universe multiverse
deb-src http://mirrors.aliyun.com/ubuntu/ bionic-backports main restricted universe multiverse

apt

系统监视器安装

sudo apt install gnome-system-monitor

ubuntu配置

2019-01-22

分盘

安装失败

swap:1024M,主分区
/:10G,主分区
/boot:128M,主分区
/home:剩余,主分区

安装成功

swap:4096M,逻辑分区
/:剩余,主分区

未知

swap:4096M,逻辑分区
/boot:200M,主分区
/:10G,主分区
/home:剩余,逻辑分区

未知

/:全部,主分区

驱动

ubuntu安装mac设备驱动

总览:github
触摸板/键盘:github

参考代码(不适用于macbook8,1)

sudo echo -e "\n# applespi\napplespi\nspi_pxa2xx_platform\nintel_lpss_pci" >> /etc/initramfs-tools/modules
sudo
sudo apt install dkms
sudo git clone https://github.com/roadrunner2/macbook12-spi-driver.git /usr/src/applespi-0.1
sudo dkms install -m applespi -v 0.1

安装软件

基本

sublime
chromium:注意数据备份.config/chromium
- tamper monkey
- Adblock Plus
- SwitchyOmega
- crxMouse Top Gestures
dukto:3系统互传软件
hyper:配置文件~/.hyper.js
vscode
gnome-tweak:如果还在用gnome
- dash to panel
- topicons plus
- user themes
搜狗输入法:CSDN
- 官网下载deb
- sudo apt install -f && sudo dpkg -i sougou.deb
- 设置->区域和语言->键盘输入法系统
gparted:磁盘分区
exfat-utils:支持exfat格式的u盘

非基本

Indicator Stickynotes
QQ(见wine)
wps

`deepin wine`软件

QQ
TIM
QQ轻聊版
微信
Foxmail
百度网盘
360压缩
WinRAR
迅雷极速版

详细,github

软件的文件存放位置

/home/lynx/.deepinwine/Deepin-QQ/dosdevices/c:/users/lynx/My Documents/Tencent Files/$account/FileRecv

`deepin wine`字体异常处理

修改注册表(TODO)

新建(任何位置,文件名随意)zh.reg
1.1. 字体链接

[HKEY_LOCAL_MACHINE\Software\Microsoft\Windows NT\CurrentVersion\FontLink\SystemLin]
"字体名"="字体文件"

1.2. 字体(强制)替换

[HKEY_LOCAL_MACHINE\Software\Microsoft\Windows NT\CurrentVersion\FontSubstitutes]
"字体名"="字体文件"

1.3 字体(缺失)替换

[HKEY_CURRENT_USER\Software\\Wine\\Fonts\\Replacements]
"字体名"="字体文件"

修改注册表(貌似没用)

deepin-wine regedit zh.reg

补充字体文件

字体文件存放位置:./deepin-wine/软件名/driver_c/windows/fonts/

wps软件

缺少字体的处理方法

下载并解压字体文件夹wps-font-symbols

git clone https://github.com/pengphei/wps-font-symbols
sudo cp -r wps-font-symbols /usr/share/fonts
# cd /usr/share/fonts
# sudo chmod 755 wps-font-symbols
cd /usr/share/fonts/wps-font-symbols
# sudo chmod 644 *
sudo mkfontdir
sudo mkfontscale
fc-cache

系统设置

笔记本行为设定

合盖不休眠:/etc/systemd/logind.conf

HandleLidSwitch=ignore

CSDN

密钥环

密码和密钥$\to$默认密钥环$\overset{\mbox{右键}}{\to}$更改密码$\to$空白

grub配置

位置

/etc/default/grub

内容修改

GRUB_DEFAULT=saved
GRUB_SAVEDEFAULT=true

生效设置

sudo grub-set-default 2
sudo update-grub

数字任意

时间配置

sudo apt-get install ntpdate
sudo ntpdate time.windows.com
sudo hwclock --localtime --systohc

`gnome-shell-entensions`

chrome扩展

sudo apt-get install chrome-gnome-shell

chrome浏览器插件

重启`gnome-shell`

alt+f2$\to$r

`extension`位置

~/.local/share/gnome-shell/extensions
/usr/share/gnome-shell/extensions

解决`显示应用程序`2个dock

cd /usr/share/gnome-shell/extensions
sudo rm -rf ubuntu-dock@ubuntu.com

解决桌面图标在重启后乱序

安装一个新的桌面图标扩展,关闭gnome-tweaks的桌面图标显示

外观修改

修改登录背景图片

/etc/alternatives/gdm3.css:

#lockDialogGroup {
  background: url(file:///usr/share/backgrounds/Aatrox.jpg);
  background-position: center;
  background-size: cover; }

默认开机动画

sudo update-alternatives --config default.plymouth

修改开机动画

ubuntugeek
更多

创建新文件夹

sudo mkdir /usr/share/plymouth/themes/myTheme

vi myTheme/myTheme.plymouth

[Plymouth Theme]
Name=MyTheme
Description=随你
ModuleName=script

[script]
ImageDir=/usr/share/plymouth/themes/myTheme
ScriptFile=/usr/share/plymouth/themes/myTheme.script

复制png(必须)图片到myTheme
vi myTheme/myTheme.script

wallpaper_image = Image("Aatrox_1080.png");
screen_width = Window.GetWidth();
screen_height = Window.GetHeight();
resized_wallpaper_img = wallpaper_image.Scale(screen_width, screen_height);
wallpaper_sprite = Sprite(resized_wallpaper_img);
wallpaper_sprite.SetZ(-100);

安装主题

sudo update-alternatives --install /usr/share/plymouth/themes/default.plymouth default.plymouth /usr/share/plymouth/themes/myTheme/myTheme.plymouth 100
sudo update-alternatives --config default.plymouth
sudo update-initramfs -u

修改grub主题

/boot/grub/themes文件夹创建
配置文件/etc/grub.d/00_header:

# You should have received a copy of the GNU General Public License
# along with GRUB.  If not, see <http://www.gnu.org/licenses/>.

GRUB_THEME="/boot/grub/themes/Vimix/theme.txt"
GRUB_GFXMODE="1920x1080x32"

可按照尺寸修改背景图片

更新配置

sudo update-grub

语言和文字

对彩色表情的支持(TODO):
- fonts-noto-color-emoji
- fonts-emojione
对特定软件使用特定语言打开(不能已经打开其他窗口)

sh -c "LANGUAGE=en /bin/chromium-browser %U"

修改语言和编码
- 位置:/etc/default/locale
- 查看当前语言:locale
locale备份

LANG=zh_CN.UTF-8
LANGUAGE=zh_CN:en_US:en
LC_CTYPE="zh_CN.UTF-8"
LC_NUMERIC="zh_CN.UTF-8"
LC_TIME="zh_CN.UTF-8"
LC_COLLATE="zh_CN.UTF-8"
LC_MONETARY="zh_CN.UTF-8"
LC_MESSAGES="zh_CN.UTF-8"
LC_PAPER="zh_CN.UTF-8"
LC_NAME="zh_CN.UTF-8"
LC_ADDRESS="zh_CN.UTF-8"
LC_TELEPHONE="zh_CN.UTF-8"
LC_MEASUREMENT="zh_CN.UTF-8"
LC_IDENTIFICATION="zh_CN.UTF-8"
LC_ALL=

Linux命令笔记

2019-01-20

sudo

在sudo模式下使用用户的.vimrc

sudo -E vim file

当前目录,只保留file

xargs

find /当前目录 -type f ! -name "file"|xargs rm -f

find自带命令

find /当前目录 -type f ! -name "file" -exec rm -f {} \

递归删除

除.java

find ./ -name "*.java" | xargs rm -rfv

批量修改文件名

rename 's/原内容/改后内容/' *

打包

tar czvf FileName.tar DirName

du -h --max-depth=1 .

合并文件夹

cp -frp new/* old/

-f强制覆盖,-r递归,-p保持新文件的属性不变

dpkg

查找已装软件?

dpkg -l|grep filename

卸载软件

dpkg -r filename

或?

dpkg -P filename

彻底删除标识为rc的配置信息

rc:软件已卸载,配置文件还在

dpkg -l | grep ^rc | cut -d' ' -f3 | sudo xargs dpkg --purge

目录分析(du)

示例

du -d1 -b -a .
du -d0 -m .

cat

输出固定行数

cat $file | head -n +6
``` 

[详细](https://blog.csdn.net/NFR413/article/details/78966085)

## curl

- 下载`$file`

```bash
curl -O $pathtofile

命令行中输出表达式的值

echo $[1 == 2]

Linux的算术运算

进程

切换到后台

<ctrl+z>

查看后台进程

jobs

使第N个进程在前台/后台运行

fg %N
bg %N

不加N默认对最后一个进程操作

ctags

vim设定源

固定

set tags=$path

先当前目录,后向上找

set tags=tags;
set autochdir

`ln`链接

文件夹软链接

ln -s $exists $new

`wc`统计行数

find -maxdepth 10 -type f | xargs wc -l
wc -l `find -name '*.*'`

更改用户/权限

sudo chmod -R 777 *
sudo chown -R user * # sudo chown -R user:usergroup *

`parallel`并行(TODO)

参考

数据库

2019-11-15

1 数据库系统概述

1.1 基本概念

数据库系统(Database System, DBS)
DBS的组成部分
- 数据库
- 数据库管理系统
- 数据库管理员
- 软件平台
- 硬件平台

1.4 数据库内部结构体系

数据库系统的三级模式
- 概念模式(模式)
- 外模式(子模式,用户模式)
- 内模式(物理模式)

2 数据模型

2.1 数据模型的基本概念

概念模型
- 常用的概念模型:实体-联系(E-R)模型,面向对象模型等
逻辑模型
- 常用的逻辑模型:关系模型,对象关系模型
物理模型:由DBMS负责实现

2.3.1 实体-联系(E-R)模型

关键字:关键字时可用于区分同一个实体集中不同实体的最小属性集合
函数对应:m

2.3.2 扩充E-R模型

扩充的实体-联系(EE-R)模型

IS-A联系:如果实体集$B$时实体集$A$的一个子集,且具有比实体集$A$更多的属性,则我们称实体集$A$与实体集$B$之间存在着一种特殊的IS-A联系,其中:
- 实体集$A$被称为超(实体)集
- 实体集$B$被称为子(实体)集
  子集$B$可以通过IS-A联系继承超集$A$中的所有属性
弱实体(Weak Entity)
- 如果一个实体$A$的存在需要依赖于其他某个实体的存在,那么实体$A$被称为弱实体
属性的划分
属性基数(Cardinality of Attributes)
Cardinality of Entity Participation in a Relationship(实体在一个联系中的参与基数)
参与方式:(0,m)

2.3.3 面向对象模型

2.3.4 谓词模型

2.4.1 关系模型与关系模型数据库系统

关系中的基本概念

关系模式
关系数据库模式
元组
关键字(键/key)
- 主关键字
- 外关键字

3 关系数据库系统

3.3.0.1 关系数据结构

表结构

表框架(Frame)
元组(Tuple)
- 在表框架中可按行(row)存放数据,其中的每一行数据被称为一个元组
- 在一$n$元表中,一个元组由$n$个元组分量组成,其中:第$j$个元组分量就对应着表框架中的第$j$个属性($j=1,2…n$)

关系(Relation)

具有$n$个属性的关系称为$n$元关系
关系名及其所有属性的属性名构成了关系框架.设关系的名为$R$,其属性名为$A_1,A_2…A_n$,则该关系的框架是$R(A_1,A_2…A_n)$

键(Key)

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

候选键(Candidate Key)
主键(Primary key)

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

外键(Foreign Key)
- 如果表$A$中的属性集$F$时表$B$的键,则称该属性集$F$为表$A$的外键(或称外关键字)
- 其中
  - 表$A$被称为引用表,表$B$被称为被引用表
  - 表$A$和表$B$可以是同一张二维表

3.3.0.2 关系操纵

空值处理

在算术表达式中出现空值,其运算结果也为空值
在逻辑运算表达式中出现空值,其运算结果为逻辑假

3.3.0.3 关系中的数据约束

三类数据完整性约束

实体完整性约束:主键中的属性不能有空值
参照完整性约束:外键要么取空值,要么是被引用表中当前存在的某元组上的主键值
用户定义的完整性:用户自己定义的属性取值约束

3.3.1 关系的表示

笛卡尔乘积

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

$D_1,D_2,…,D_n$是$n$个集合
设集合$D_i$的元素个数为$r_i(i=1,2,…,n)$,则他们的笛卡尔乘积的结果元素个数为$r_1\times r_2\times…\times r_n$

关系$R$

$n$元关系$R$是一个$n$元有序组的集合
设$n$元关系$R$的属性域分别是$D_1,D_2,…,D_n$,那么这$n$个域的笛卡尔乘积也是一个$n$元有序组的集合,并且与关系$R$存在联系:$R\subseteq D_1\times D_2\times…\times D_n$

3.3.2 关系操纵的表示

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

相容表

投影运算

选择运算

关系的笛卡尔乘积

笛卡尔乘积满足交换律和结合律
如果关系$R$和$S$中存在相同的属性名,则必须在结果关系中对其中的一个进行换名

3.3.3 关系模型与关系代数

3.3.4 关系代数中的扩充运算

交运算

除运算

除运算的推导过程
若$Head(R)=\{A_1…A_nB_1…B_n\},Head(S)=\{B_1…B_m\}$
$R\div S=\pi_{A_1…A_n}(R)-\pi_{A_1…A_n}((\pi_{A_1…A_n}(R)\times S)-R)$
1. $T_{\max}=\pi_{A_1…A_n}(R)$
2. $R_{\max}=T_{\max}\times S$
3. $T_1=R_{\max}-R$
4. $T_2=\pi_{A_1…A_n}(T_1)$
5. $R\div S=T_{\max}-T_2$

join运算

又称$\theta$-联接运算,可以将关系$R$和关系$S$根据join条件$F$合并为一个关系
联接条件$F$的构造方式
join运算的推导公式
$R\underset{F}{\bowtie}S=\sigma_F(R\times S)$
联接运算与笛卡尔乘积运算的关系

natural join运算

功能:根据两个关系中的同名属性进行等值联接
运算结果
- 结果关系中的元组
natural join运算的推导公式

A 关系演算

A.1 一阶谓词演算

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

A.1.3 谓词

A.1.4 指派

A.2 关系的表示

关系演算系统

元组关系演算
域关系演算

A.3 关系操纵的表示

设$R$和$S$时两个模式相同的关系表,他们对应的谓词分别为$R(t)$和$S(t)$,则
1. $R\cup S=\{t|R(t)\vee S(t)\}$
2. $R-S=\{t|R(t)\wedge\lnot S(t)\}$
3. $\sigma_F(R)=\{t|R(t)\wedge F\}$
4. $\pi_{A_{i_1},A_{i_2},…,A_{i_k}}(R)=$TODO
设有$m$元的关系$R$和$n$元的关系$S$,他们对应的谓词分别为$R(u)$和$S(v)$,则
$R\times S=$TODO

关系演算表达式

关系演算表达式$\{t|\varphi(t)\}$表示由公式$\varphi(t)$的所有成真指派所构成的集合
可将$\{t|\varphi(t)\}$简写为$\varphi(t)$

关系演算的原子公式

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

A.4 关系演算的例子

关系的联结

可以通过相关谓词的逻辑与运算实现两个关系的笛卡尔乘积
$R(p)\wedge S(q)$
通过选择条件$F$实现两个关系的$\theta$-联结
$R(p)\wedge S(q)\wedge F$
可以通过两个谓词中的公共变元(同名变元)实现两个关系的自然联结
$R(x,y,z)\wedge S(y,u,v)$

自联结:谓词名不变,对部分变元进行重命名,从而实现关系的自联结(同名变元取值相等)

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

删除:$S(sno, sn, sd, sa)\wedge\lnot S(‘S_1’, sn, sd, sa)$
插入:$S(t)\vee R(t)$
修改:
$R(sno, sn, sd, sa)=\exists x(S(sno, sn, sd, x)\wedge sno=S_7\wedge sa=29)$
$(S(sno, sn, sd, sa)\wedge sno\not=S_7)\vee R(sno, sn, sd, sa))$

A.5 关系演算的安全限制

无限关系

无穷验证

B 关系数据库语言SQL

B.2 SQL数据定义功能

基表创建

B.3 SQL数据操纵功能

B.3.1 SQL的基本查询功能

B.3.1.2 常用谓词

`like`谓词的使用方法

column [ NOT ] like val1 [ escape val2 ]

模板(pattern):val1
- _:可以匹配任意一个字符
- %:可以匹配任意一个字符串(包括空字符串)
转移指示字符:val2
- 紧跟在val2之后的_或%不再是通配符,而是其自身

B.3.1.5 自连接

B.3.1.6 结果排序

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

升序asc,降序desc,默认升序

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

`where`子句中的集合谓词

in谓词:标量与集合量之间的属于比较

expr [ not ] in ( subquery )

限定比较谓词:标量与集合中元素之间的量化比较

expr 运算符 some|any|all ( subquery )

exists谓词:是否为空集的判断谓词

[ not ] exists ( subquery )

B.3.3 `select`语句间的运算

union [all]
intersect [all]
except [all]

不加all只选取不同的值

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

B.3.4.1 统计功能

count统计:
- count(*):返回集合中的元组个数
- count(colname):返回在colname属性上取值非空的元组个数
- count(distinct colname):返回colname取值非空且互不相同的元组个数
sum,avg,max,min统计
null在统计函数中的处理:TODO

B.3.4.3 分类功能

分类统计查询
- 分组查询子句
  group by colname { ,
  colname ...}
根据属性colname的取值的不同,将满足where条件的元组划分为不同的集合
分组选择子句:having group_condition

B.3.5 `select`语句使用的一般规则

B.4 SQL的更新功能

元组删除

delete from table_name
[ where search_condition ];

元组插入

insert into table_name [ ( colname {, colname ... } ) ]
values ( expr | null {, expr | null ...} ) | subquery;

元组修改

update table_name
set colname = expr | null | subquery, ...
[ where search_condition ];

B.5 视图

B.5.2 视图的删除

在执行视图的删除操作时,将连带删除定义在该视图上的其他视图

B.5.3 视图上的操作

对视图可以作查询操作
- 视图上的查询操作将首先被改写为基表上的查询操作,然后才能得到执行
一般不允许执行视图上的更新操作,只有在特殊情况下才可以进行
可更新视图

4 数据库的安全性与完整性保护

4.1 数据库的安全性

4.1.2 数据库安全的基本概念与内容

客体:数据库中的数据及其载体
主体:数据库中数据的访问者

4.1.4 SQL对数据库安全的支持

操作对象
- 表,视图
- 属性
- 域(type),udt(用户定义数据类型)
- 存储过程/函数,触发器
授权语句
grant <操作权限列表> on <操作对象> to <用户名列表> [ with grant option ]
回收语句
revoke <操作权限列表> on <操作对象> from <用户名列表> [ restrict | cascade ]
- cascade:连锁回收
- restrict:在不存在连锁回收问题时才能回收权限,否则拒绝回收

4.2 数据库的完整性

TODO

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

5.1 事务处理

5.1.1 事务

事务
一个事务是指由一条SQL语句或者一组SQL语句所构成的一个执行过程,并具有ACID四个特性
由每个用户所执行的一个不能被打断的对数据库的操作序列被称为事务

5.1.2 事务的性质

原子性(Atomicity)
一致性(Consistency)
数据库的一致的状态可以理解为数据库中所有数据的正确性,他要求数据库中的数据必须满足
- 在数据库中显式定义的各种完整性约束
- 用户心目中的隐式数据约束

5.1.4 有关事务的语句

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

设置事务的隔离级别
- readuncommitted:未提交读
- readcommitted:提交读
- readrepeatable:可重复读
- serializable:可序列化(可串行化)

5.1.5 事务的组成

事务控制操作
- 事务的开始:start T
- 提交事务:commit T
- 回退(放弃)事务:abort T
数据访问操作
- input(A):将数据对象A的值从磁盘中读入内存缓冲区
- output(A):将内存缓冲区中数据对象A的至写入磁盘
- read(A, t):将内存缓冲区中数据对象A的值读入内存变量t
  
  在一个read操作中,有可能隐含着一个input操作
- write(A, t):将内存变量t的值写入内存缓冲区中数据对象A

5.2 并发控制技术

5.2.1 事务的并发执行

多个事务的执行方式
- 串行执行
  - 以事务为单位,多个事务依次顺序执行
- 并发执行
- 并发执行的可串行化
  - 如果一组事务并发执行的结果等价于他们之间的某种串行执行的结果,则称其为可串行化调度
并发控制的目标:实现并发事务的可串行化调度
调度:一个或多个事务中的数据库访问操作,按照这些操作在DBMS(database management system)被执行的时间先后,排序所形成的一个操作序列
给定一组并发事务$T_1,T_2…T_k$,他们之间的调度$H$必须满足
1. 必须包括所有事物的所有操作,包括每一个事务的结束命令(commit/abort)
2. 单个事物内部的操作顺序必须保持不变
串行调度
可串行化调度
事务及调度的表示方法
- 事务用符号$T_1,T_2…$表示
- $r_i(X)$表示事务$T_i$读数据库对象$X$
- $w_i(X)$表示事务$T_i$写数据库对象$X$
冲突可串行化
- 冲突(conflict):指调度中的一对相邻操作(op1; op2),他们满足:如果交换它们两者的执行顺序,那么涉及的事务中至少有一个的行为会改变
- 冲突的判断办法
  - 同一事务的任意两个相邻的操作都是冲突
  - 不同事物对统一数据对象的写/读-写冲突
- 冲突等价:如果通过一系列相邻操作的非冲突交换能够将一个调度转换为另一个调度,称这两个调度是冲突等价的
- 冲突可串行化:如果一个调度$S$冲突等价于这一组事务之间的一个串行调度,称$S$时冲突可串行化的
  - 冲突可串行化调度必定是一个可串行化调度
  - 一个可串行化调度不一定是冲突可串行化的
冲突可串行化的判断:优先图
视图等价
- 一个冲突可串行化调度一定是视图可串行化调度
三种数据不一致现象
- 丢失修改(lost updata)
  - 一个事务的修改结果破坏了另一个事务的修改结果
  - 对多个事务并发修改同一个数据对象的情况未加控制
- 脏读(dirty read)
  - 读到了错误的数据
  - 一个事务读取了另一个事务未提交的修改结果
- 不可重复读(unrepeatable read)
  - 在一个事务的执行过程中,前后两次读同一个数据对象所获得的值出现了不一致
  - 在两次读操作之间插入了另一个事务的写操作

5.2.2 封锁

排它锁(X锁)
共享锁(S锁)
锁相容矩阵
锁的申请与释放

5.2.3 封锁协议

一级封锁协议
事务$T$在写数据对象$A$之前,必须先申请并获得$A$上的X锁,并维持到事务$T$的执行结束(包括commit与rollback)才释放加在$A$上的锁
防止丢失修改
二级封锁协议
事务$T$在读数据对象$A$之前,必须先申请并获得$A$上的S锁,在读操作完成后可以释放$A$上的S锁
防止丢失修改,脏读
三级封锁协议
事务$T$在读数据对象$A$之前,必须先申请并获得$A$上的S锁,并维持到事务$T$的执行结束才释放被加在$A$上的S锁
防止丢失修改,脏读,不可重复读

5.2.4 两阶段封锁协议

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

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

第一个阶段:申请并获得锁
第二个阶段:释放持有的锁

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

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

$sl_i(A)$:事务$T_i$申请数据对象$A$上的一个S锁
$xl_i(A)$:事务$T_i$申请数据对象$A$上的一个X锁
$u_i(A)$:事务$T_i$释放自己在数据对象$A$上所持有的锁
封锁的使用规定:在每一个事务$T_i$中
1. 采用如下的封锁协议
  - $r_i(A)$之前必须有$sl_i(A)$或$xl_i(A)$,而且在两者之间没有$u_i(A)$
  - $w_i(A)$之前必须有$xl_i(A)$,而且在两者之间没有$u_i(A)$
  - 每一个$sl_i(A)$或$xl_i(A)$之后必须有一个$u_i(A)$
2. 必须遵循两阶段封锁协议
3. 保证事务调度的合法性
  - 如果$xl_i(A)$出现在调度中,那么后面不能再有$sl_i(A)$或$xl_j(A)$,除非中间插入了$u_i(A)$
  - 如果$sl_i(A)$出现在调度中,那么后面不能再有$xl_j(A)$,除非中间插入了$u_i(A)$

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

5.2.5 封锁粒度

封锁粒度	系统并发度	并发控制的开销
大	低	小
小	高	大

多粒度封锁
- 如果在一个系统中同时支持多种封锁粒度供事务选择使用,这种封锁方法被称为多粒度封锁
- 可以按照封锁粒度的大小构造出一颗多粒度树,以树中的每个节点作为封锁对象,可以构成一个多粒度封锁协议
意向锁
- 使用规定
  - 如果对一个节点加意向锁,则说明该节点的下层节点正在被加锁
  - 对任一节点加锁时,必须先对它的上层节点加意向锁
- 三种常见的意向锁
  - 意向共享锁(IS锁):如果对节点$N$加IS锁,表示准备在节点$N$的某些后裔节点上加S锁
  - 意向排它锁(IX锁):如果对节点$N$加IX锁,表示准备在节点$N$的某些后裔节点上加X锁
  - 共享意向排它锁(SIX锁):如果对节点$N$加SIX锁,表示对节点$N$本身加S锁,并准备在$N$的某些后裔节点上加X锁

其他事务已持有的锁$\to$	S锁	X锁	IS锁	IX锁	SIX锁
S锁	y	n	y	n	n
X锁	n	n	n	n	n
IS锁	y	n	y	y	y
IX锁	n	n	y	y	n
SIX锁	n	n	y	n	n

多粒度封锁协议
- 申请封锁的顺序:上->下
- 释放封锁的顺序:下->上

5.2.6 活锁与死锁

死锁

例子:$r_1(B),r_2(B),w_1(B)$
解除法
- 超时死锁检测法
  - 事务的执行时间超时
  - 锁申请的等待时间超时
- 等待图法
- 时间戳死锁检测法
  - 每个事物都具有一个用于死锁检测的时间戳
  - 如果事务$T$必须等待另一个事务$U$所持有的锁
    - 等待-死亡方案:
      - 如果$T$比$U$老,那么允许$T$等待$U$持有的锁
      - 如果$U$比$T$老,那么事务$T$死亡(被回滚)
    - 伤害-等待方案:
      - 如果$T$比$U$老,他将伤害$U$,$U$必须被回滚
      - 如果$U$比$T$老,那么$T$等待$U$持有的锁

活锁

例子:
- $T_1$(卖票):$xl_1(A),r_1(A),w_1(A),u_1(A)$
- $T_2$(剩余票额查询):$sl_2(A),r_2(A),u_2(A)$
- 先启动一个$T_2$,再启动一个$T_1$:$T_1$处于等待状态,在已经运行的$T_2$结束之前,不断有新启动的$T_2$加进来
解决方法:先来先服务

5.3 数据库恢复技术

5.3.2 数据库故障分类

小型故障
- 事物内部故障
中性故障
- 系统故障
- 外部影响
大型故障
- 磁盘故障
- 计算机病毒
- 黑客入侵

5.3.3.1 转储

静态转储:无事务运行时
动态转储
海量转储:每次转储全部数据库
增量转储:更新过的

5.3.3.2 日志

undo日志

记录格式
- 开始一个事务:<Start T>
- 提交事务$T$:<Commit T>
- 放弃事务$T$:<Abort T>
- 更新记录:<T, X, V>,事务$T$修改了数据库元素$X$的值,$X$的旧值是$V$
记载规则
1. 如果事务$T$修改了数据库元素$X$,则<T, X, V>必须在$X$的新值写到磁盘前写到磁盘
2. 如果事务$T$提交,则<Commit T>必须在事务$T$改变的所有DB元素写到磁盘后再写到磁盘
恢复过程
1. 将所有事务划分为两种类型
  - 已提交事务:有<Start T>和<Commit T>
  - 未提交事务:有<Start T>没有<Commit T>
2. 从undo日志的尾部向头部扫描整个日志,对每条更新记录<T, X, Y>:
  - 如果<Commit T>已被扫描到,则继续扫描下一条日志记录
  - 否则,由恢复管理器将数据库中的$X$的值改为$V$
3. 在日志的尾部为每个未结束的事务$T$写入一条日志记录<Abort T>,并刷新日志(flush log)
检查点
在日志中插入检查点的处理过程
1. 系统停止接受启动新事务的请求
2. 等所有当前活跃的事务提交或中止,并且在日志中写入<Commit T>或<Abort T>
3. 将日志记录刷新到磁盘
4. 写入日志记录<CKPT>,并再次刷新日志
5. 重新开始接受新的事务
在故障恢复时,只要逆向扫描到第一条<CKPT>记录,就可以结束故障恢复工作
非静止检查点
设置非静止检查点的步骤
1. 写入日志记录<Start CKPT(T1, ..., Tk)>
2. 等待$T_1, …, T_k$所有事务的提交或终止,在这个过程中允许启动执行新的事务
3. 当$T_1, …, T_k$都已经完成时,写入日志记录<End CKPT>并刷新日志
带有非静止检查点undo日志的恢复
1. 先遇到<End CKPT>记录
  - 继续向后(头部)扫描,直到出现与之相对应的<Start CKPT(...)>记录就可以结束故障恢复工作
2. 先遇到<Start CKPT(T1, ..., Tk)>记录,故障恢复工作需要撤销两类事务的操作
  - 在<Start CKPT(T1, ..., Tk)>记录之后启动的事务
  - $T_1, …, T_k$中在系统崩溃前尚未完成的事务
undo日志的不足
- 在将事务改变的所有数据写到磁盘前不能提交该事务
- 在事务的提交过程中需要执行许多写磁盘操作,增加了事务提交的时间开销

redo日志

记录格式
- redo日志的记录格式与undo一样,唯一区别:在更新记录<T, X, V>中记载的是更新后的值
记载规则
- 在修改磁盘上的任何数据库元素$X$之前,要保证所有与$X$这一修改有关的日志记录(包括提交记录<Commit T>)都必须出现在磁盘上
恢复过程
1. 先扫描一遍日志文件,确定所有已经提交的事务
2. 再从日志头部开始扫描,对每条更新记录<T, X, V>
  - 如果$T$时未提交事务,则继续扫描日志
  - 如果$T$是已提交的事务,则为数据库元素$X$写入新值$V$(有可能是冗余的写操作)
3. 对每个未完成的事务(提交记录<Commit T>没有写入磁盘),在日志的尾部写入<Abort T>并刷新日志
非静止检查点
1. 写入日志记录<Start CKPT(T1, ..., Tk)>($T_1, …, T_k$时当前所有活跃事务的标识符),并刷新日志.同时获得当时所有已提交事务的标识符集合$S$
2. 将集合$S$中的事务已经写到内存缓冲区但还没有写道数据库磁盘的数据库元素写入磁盘
3. 写入日志记录<End CKPT>并刷新日志,不需等待事务$T_1, …, T_k$或新开始事务的结束
带检查点redo日志的恢复
- 找到最后一个被记入日志的<End CKPT>,假设与之对应的检查点记录时<Start CKPT(T1, ..., Tk)>,并找到最早出现的<Start Ti>
- 重做$T_1, …, T_k$,以及在<Start CKPT()>后开始的已经被提交事务
redo日志的不足
- 要求事务提交和日志就刷新之前将所有修改过的数据保留在内存缓冲区中,可能增加事务需要的平均缓冲区的数量
- 如果被访问的数据对象$X$不是完整的磁盘块,那么在undo日志与redo日志之间可能产生相互矛盾的请求

undo/redo日志

记录格式
- 更新记录的格式<T, X, v, w>,不仅记录更新前的值$v$,同时也要记录更新后的值$w$
记载规则
1. 在由于某个事务$T$所做的改变而修改磁盘上的数据库元素$X$之前,更新记录<T, X, v, w>必须出现在磁盘上
2. 在每一条<Commit T>后面必须紧跟一条Flush Log操作
  
  事务提交(Commit)和写数据库磁盘(Output)的操作顺序是随机的
恢复过程
1. 根据<Commit T>是否已经出现在磁盘中来确定事务$T$是否已经被提交
2. 从后往前,撤销(undo)所有未提交的事务
3. 从前往后,重做(redo)所有已提交的事务
检查点
1. 写入日志记录<Start CKPT(T1, ..., Tk)>($T_1, …, T_k$是当前所有活跃事务的标识符),并刷新日志
2. 将所有被修改过的缓冲区写到数据库的磁盘中去
3. 写入日志记录<End CKPT>并刷新日志
带检查点日志的恢复

5.3.4 恢复策略

小型故障的恢复
- 利用未结束事务的undo操作进行恢复
中型故障的恢复
- 非正常中止的事务:undo
- 已完成提交的事务:redo
大型故障的恢复
- 先利用后备副本进行数据库恢复,再利用日志进行数据库的恢复

5.3.5 数据库镜像

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

5.4 事务处理实现技术

6 数据库中的数据交换

7 数据库的物理组织

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

8.2.1 函数依赖

平凡.非平凡函数依赖
完全函数依赖
在关系模式$R(U)$中,如有$X\subseteq U,Y\subseteq U$,满足$X\to Y$,且对任何$X$的真子集$X’$都有$X’\not\to Y$,则称$Y$完全函数依赖于$X$,记作$X\overset{f}{\to}Y$
部分函数依赖
传递函数依赖
在关系模式$R(U)$中,如有$X\subseteq U,Y\subseteq U,X\subseteq U$且满足$X\to Y,Y\not\subset X,Y\not\to X,Y\to Z$,则称$Z$传递函数依赖于$X$.否则称为非传递函数依赖(直接函数依赖)
Armstrong公理系统
- 基本规则
  - 自反规则:如果$Y$是$X$子集,则$X\to Y$
  - 增广规则:如果$X\to Y$,则$XZ\to YZ$
  - 传递规则:如果$X\to Y,Y\to Z$,则$X\to Z$
- 扩充规则
  - 分解规则:如果$X\to YZ$,则$X\to Y$且$X\to Z$
  - 合并规则:如果$X\to Y$且$X\to Z$,则$X\to YZ$
  - 伪传递规则:如果$X\to Y$且$WY\to Z$,则$WX\to Z$
关键字(码,键,key)
在关系模式$R(U,F)$中,如有$K\subseteq U$且满足$K\overset{f}{\to}U$,则称$K$为关系$R$的关键字
主属性集
- 由关系模式$R$的所有关键字中的属性所构成的集合被称为关系模式$R$的主属性集
- 主属性集中的属性被称为关系模式$R$的主属性
非主属性集

计算属性集$X$在函数依赖集$F$上的闭包$X_F^+$(简写为$X^+$)

$X^+=X$
repeat
$oldX^+=X^+$
foreach 函数依赖 $Y\to Z\in F$ do
if $Y\subseteq X^+$ then $X^+=X^+\cup Z$
until ($oldX^+ == X^+$)

寻找关系模式$R(U,F)$的关键字$K$

输入:关系模式$R(U,F)$
输出:关系$R$的一个关键字$K$

$K=U$
foreach 属性 $A\in K$ {
计算 $(K-A)_F^+$
if $(K-A)_F^+$ 包含了$R$的所有属性 then {
$K=K-A$
}
}
return $K$

优化算法:设$F$时关系上的最小函数依赖集.根据$F$中的函数依赖,可将$U$划分为

只在函数依赖的左边出现过的属性的集合$U_L$
只在函数依赖的右边出现过的属性的集合$U_R$
在两边都出现的属性的集合$U_A$
其中

$U_L$中的属性时没一个关键字的组成部分
$U_R$中的属性不可能出现在任何一个关键字中
在关键自己算算法中,只需针对$U_A$中的属性进行for循环计算

$K=U-U_R$
foreach 属性 $A\in U_A$ {
计算 $(K-A)_F^+$
if $(K-A)_F^+$ 包含了$R$的所有属性 then {
$K=K-A$
}
}
return $K$

8.2.2 与函数依赖有关的范式

第一范式
关系模式$R(U)$中的每个属性值都是一个不可分割的数据量
如果不满足第一范式,那么也就不能被称为关系
第二范式
关系模式$R(U)\in1NF$,且每个非主属性都完全函数依赖于关键字
判断一个关系$R$是否满足2NF:
1. 找到关系$R$的所有非主属性和所有候选关键字
2. 检查每一个非主属性$A$和每一个关键字$K$之间的函数依赖,判断是否存在非主属性对于关键字的部分函数依赖

模式分解的方法

设关系模式$R$属性集合为$Head(R),F$时其函数依赖集.将其分解到满足范式$M$的步骤如下

找出所有不满足范式$M$要求的函数依赖关系
选择一个不符合要求的函数依赖关系作如下的分解
假设$X\overset{f}{\to}Y\in F^+$且不满足范式$M$的要求,则将关系模式$R$分解为如下的两个子关系
- $R_1(X\cup Y,\{X\to Y\})$
- $R_2(Head(R)-Y,F_2)$,其中$F_2=\{A\to B|A\to B\in F^+$且$(A\cup B)\subseteq Head(R_2)\}$
对于分解得到的子关系模式$R_2$重复上述的步骤1和2,直到所有的子关系模式都能满足范式$M$的要求
合并那些具有相同关键字的子关系模式

第三范式
设关系模式$R(U)\in$2NF,且每个非主属性都不传递函数依赖于关键字,则称关系模式$R(U)$满足第三范式
如果关系$R\not\in$3NF,那么在关系$R$中必然存在以下形式的函数依赖$X\overset{f}{\to}Y$,其中$Y$是单个的非主属性,$X$不是关系$R$的关键字
BCNF
设关系模式$R(U)$满足1NF,且若$X\to Y$是$X$必含有该关系模式的关键字,则称关系模式$R(U)$满足BCNF范式
若$R(U)\in$BCNF,则$R(U)\in$3NF

8.2.3 多值依赖与第四范式

多值依赖(MVD)
- 设有关系模式$R(U),X,Y\subseteq U$
- $R(U)$满足
  1. 多$X$的一个确定值,存在$Y$的一组值与之对应
  2. 且$Y$的这组值又与关系中的其他属性$(U-X-Y)$的取值不相关
- 称$Y$多值依赖于$X$,记为$X\to\to Y$
非平凡的多值依赖
设在关系模式$R(U)$中,$X\to\to Y$且$U-X-Y\not=\emptyset$,则称$X\to\to Y$是非平凡的多值依赖,否则称其为平凡的多值依赖
多值依赖的性质
在一个关系模式$R(U)$中
1. 如有$X\to\to Y$,则必有$X\to\to(U-X-Y)$
2. 如有$X\to Y$,则必有$X\to\to Y$
有关FD和MVD的推导规则
第四范式
在$R(U)$中,如果$X\to\to Y$是非平凡多值依赖,则$X$必含有关键字,此时称关系模式$R$满足第四范式
特点
1. 函数依赖:要满足BCNF
2. 不是函数依赖的多值依赖:只允许出现平凡多值依赖

8.3.1 函数依赖理论

函数依赖集的等价
如果两个函数依赖集$F_1$和$F_2$的闭包是相等的,称函数依赖集$F_1$等价于函数依赖集$F_2$
最小函数依赖集
- 与函数依赖集$F$向等价的所有函数依赖集中的最小者被称为函数依赖集$F$的最小函数依赖集
- 也被称为最小覆盖

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

对于$F$中的每一个FD关系$X\to A$均作如下判断

依赖因素$A$为单个属性
不存在冗余的函数依赖:令$F_1=F-\{X\to A\}$,则$F_1^+\not=F^+$
不存在部分函数依赖:对于决定因素$X$的每一个真子集$Y(Y\subset X)$均作如下判断:
令$F_2=F-\{X\to A\}\cup\{Y\to A\}$,则$F_2^+\not=F^+$

如果$F$中的每一个函数依赖$X\to A$均符合上述要求,则$F$是一个最小函数依赖集

条件1不是必需的,只是为了方便条件2和3的判断

寻找与函数依赖集$F$等价的最小函数依赖集$G$

输入:函数依赖集$F$
输出:与$F$等价的最小函数依赖集$G$
算法:

消除$F$中的部分函数依赖(化简为完全函数依赖)
消除冗余的函数依赖

具体计算过程

$G=F$
将$G$中每一个形如$X\to(A_1,A_2…A_n)$的函数依赖替换为$X\to A_1,X\to A_2…X\to A_n$
对$G$中的每个函数依赖$X\to A$作如下处理
对$X$中的每一个属性$B$:
1. 计算属性集的闭包$(X-B)_G^+$
2. 如果$A\in(X-B)_G^+$,则用新的函数依赖$(X-B)\to A$替换原来的$X\to A$
对$G$中的每个函数依赖$X\to A$作如下处理
1. 令$N=G-\{X\to A\}$
2. 计算属性集的闭包$X_N^+$
3. 如果$A\in X_N^+$,那么$G=G-\{X\to A\}$
将$G$中的每一组$X\to A_1,X\to A_2…X\to A_n$合并为一个函数依赖$X\to(A_1,A_2…A_n)$

8.3.2 模式分解的研究

无损连接性:分解后,原关系中的信息不会被丢失
设$R$是一个关系模式,$F$时$R$的函数依赖集,$\rho=\{R_1,R_2…R_k\}$是对$R$的一个分解,如果对$R$中满足$F$的每一个关系实例$r$都有$r=\pi_{R_1}(r)\bowtie\pi_{R_2}(r)\bowtie…\bowtie\pi_{R_k}(r)$,则称$\rho$相对于$F$是无损联结分解,或称分解$\rho$具有无损联结性
依赖保持性:原有的函数依赖关系在分解后的关系模式上依然存在
设$\rho=\{R_1,R_2…R_k\},F$是$R$的函数依赖集,如果$F^+=(\pi_{R_1}(F)\cup\pi_{R_2}\cup…\cup\pi_{R_k}(F))^+$,则称分解$\rho$具有依赖保持性
无损联接性的充要条件:$\rho={R_1, R_2}:R_1\cap R_2\to(R_1-R_2)$或$R_1\cap R_2\to(R_2-R_1)$

到3NF的分解算法

假设$S$时分解所获得的子关系模式的集合

$F=F$的最小函数依赖集
$S=\emptyset$
对$F$中每一个函数依赖$X\to Y$
如果在集合$S$中找不到满足下述条件的子关系模式$Z$
$X\cup Y\subseteq Heading(Z)$
则由$X$和$Y$构成一个新的子关系加入到$S$中($S=S\cup Heading(X\cup Y)$)
如果找不到一个关键字$K$和一个子关系模式$Z$满足$K\subseteq Z$
那么从关系$R$中任选一个候选关键字$K$单独构成一个子关系模式($S=S\cup Heading(K)$)

9 数据库设计

9.2 需求分析

确定需要在数据库保存其信息的客观事物及其相互关系

9.3 概念设计

目的:建立一个抽象的概念数据模型
工具
- E-R模型
- EE-R模型
- 面向对象模型

9.4 逻辑设计

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

9.5 物理设计

存取方法的设计
存储结构的设计

计算机网络

2019-12-23

1 计算机网络和因特网

1.3 网络核心

1.4 分组交换网中的时延,丢包和吞吐量

节点总时延($d_{nodal}$)=节点处理时延($d_{proc}$)+排队时延($d_{queue}$)+传输时延($d_{trans}$)+传播时延($d_{prop}$)

1.4.2 排队时延和丢包

流量强度

1.5 协议层次及其服务模型

1.5.1 分层的体系结构

协议分层
1. 应用层
  http,smtp,ftp
2. 运输层
  tcp,udp
3. 网络层
  ip
4. 链路层
  CSMA,CSMA/CD,CSMA/CA
5. 物理层

1.5.2 封装

应用层报文
运输层报文段
网络层数据报
链路层帧
有效载荷字段

3 运输层

3.1 概述和运输层服务

运输层协议死在端系统中而不是在路由器中实现的.在发送端,运输层将接收到的报文转换成运输层分组,该分组称为运输层报文段(segment)

3.1.1 运输层和网络层的关系

网络层提供了主机之间的逻辑通信,而运输层为运行在不同主机上的进程之间提供了逻辑通信

3.1.2 因特网运输层概述

UDP(用户数据报协议):他为调用它的应用程序提供了一种不可靠,无连接的服务
TCP(传输控制协议):他为调用它的应用程序提供了一种可靠的,面向连接的服务

将TCP和UDP的分组统称为报文段(segment),而将数据报(datagram)名称留给网络层分组

ip的服务模型时尽力而为交付服务(best-effort delivery service).这意味着ip尽他最大的努力在通信的主机之间交付报文段,但他并不作任何确保.特别是不确保报文段的交付,不保证报文段的按序交付,不保证报文段中数据的完整性.由于这些原因,ip被称为不可靠服务

3.2 多路复用与多路分解(概念)

将运输层报文段中的数据交付到正确的套接字的工作称为多路分解(demultiplexing)

在源主机从不同套接字中收集数据块,并未每个数据块封装上首部信息(将在以后用于分解)从而生成报文段,然后将报文段传递到网络层,所有这些工作称为多路复用(multiplexing)

3.3 无连接运输:UDP(概念)

有许多应用更适合用UDP,原因主要以下几点

关于发送什么数据以及何时发送的应用层控制更为精细
无需连接建立
无连接状态
分组首部开销小

3.3.1 UDP报文段结构

周知端口号(well-known port):0-1023

其他首部字段
- 长度:2字节
- 校验和:2字节

3.3.2 UDP校验和

3.5 面向连接的运输:TCP

3.5.1 TCP连接

TCP连接提供的是全双工服务:如果一台主机上的进程A与另一台主机上的进程B存在一条TCP连接,那么应用层数据就可在从进程B流向进程A的同事,也从进程A流向进程B

发起连接的进程被称为客户进程,另一个进程被称为服务器进程

TCP可从缓存中取出并放入报文段中的数据数量受限于最大报文段长度(MSS).MSS通常根据最初确定的有本地发送主机发送的最大链路层帧长度(即最大传输单元(MTU))来设置.MSS是指在报文段里应用层数据的最大长度,而不是只包括首部的TCP报文段的最大长度

TCP为每块客户数据配上一个TCP首部,从而形成对个TCP报文段.这些报文段被下传给网络层,网络层间期分别封装在网络层ip数据包中

3.5.2 TCP报文段结构

序号字段,确认号字段:见后
接收窗口字段:见流量控制
首部长度字段:TCP首部长度/32比特.由于TCP选项字段,TCP首部的长度是可变的(通常选项字段为空,TCP首部的典型长度为20字节)
选项字段:在发送方与接收方协商最大报文段长度(MSS)时,或在高速网络环境下用作窗口调节因子时使用
标志字段
- ACK:指示确认字段中的值是有效的,即该报文段包括一个对已被成功接收报文段的确认
- RST,SYN,FIN:用于连接建立和拆除,见后
- CWR,ECE:明确拥塞通告
- PSH:指示接收方应立即将数据交给上层
- URG:指示报文段里存在着被发送端的上层实体置为紧急的数据,紧急数据的最后一个字节由16bit的紧急数据指针字段指出

序号和确认号
序号时建立在传送的字节流之上,而不是建立在传送的报文段的序列之上的.一个报文段的序号(sequence number for a segment)因此事该报文段首字节的字节流编号
主机A在向主机B发送数据的同事,也许也接受来自主机B的数据.主机A填充进报文段的确认号时主机A期望从主机B收到的下一字节的序号
假设主机A收到来自主机B包含字节0-535和900-1000的报文段,没有收到536-899的报文段.主机A为了重新构建主机B的数据流,仍在等待字节536,因此A到B的下一个报文段将在确认号字段中包含536.引文TCP只确认该流中至第一个丢失字节为止的字节,所以TCP被称为提供累积确认
当主机在一条TCP连接中收到失序报文段
1. 接收方立即丢弃失序报文段
2. (实践中采用)接收方保留失序的字节,并等待缺少的字节以填补该间隔
Telnet案例

3.5.3 往返时间的估计与超时

往返时间(RTT)

估计往返时间
大多数TCP的实现仅在某个时刻做一次SampleRTT测量,而不是为每个发送的报文段测量一个SampleRTT
$EstimatedRTT=(1-\alpha)\cdot EstimatedRTT+\alpha\cdot SampleRTT$
- 指数加权移动平均(EWMA):一个给定的SampleRTT的权值在更新的过程中呈指数型快速衰减
  RTT偏差DevRTT,用于估算SampleRTT一般会偏离EstimatedRTT的程度:
  $DevRTT=(1-\beta)\cdot DevRTT+\beta\cdot|SampleRTT-EstimatedRTT|$
设置和管理重传超时间隔
$TimeoutInterval=EstimatedRTT+4\cdot DevRTT$
当出现超时后,TimeoutInterval值将加倍,以免即将被确认的后继报文段过早出现超时.只要收到报文段并更新EstimatedRTT,就使用上述公式再次计算TimeoutInterval

3.5.4 可靠数据传输

推荐的定时器管理过程仅使用单一的重传定时器

TCP发送方的3个与发送和重传有关的主要事件
- 从上层应用程序接收数据
- 超时事件
- 到达一个来自接收方的包含了有效ACK字段值的报文段

超时间隔加倍
每次TCP重传时都会将下一次的超时间隔设为先前值的两倍

快速重传

事件	TCP接收方动作
具有所期望序号的按序报文段到达.所有在期望序号及以前的数据都已经被确认	延迟的ACK.对另一个按序报文段的到达最多等待500ms.如果下一个按序报文段在这个时间间隔内没有到达,则发送一个ACK(合并ACK,降低网络流量)
具有所期望序号的按序报文段到达.另一个按序报文段等待ACK传输	立即发送单个累计ACK,以确认两个按序报文段
比期望序号大的失序报文段到达.检测出间隔	立即发送冗余ACK,指示下一个期待字节的序号(为间隔的低端的序号)
能部分或完全填充接收数据间隔的报文段到达	若该报文段起始于间隔的低端,则立即发送ACK

一旦收到3个冗余ACK,TCP就执行快速重传

回退$N$步还是选择重传
选择确认:TCP接收方有选择地确认失序报文段,而不是累积地确认最后一个正确接收的有序报文段
选择重传机制:跳过重传那些已被接收方选择性地确认过的报文段

3.5.5 流量控制

流量控制服务
拥塞控制

TCP通过让发送方维护一个称为接收窗口的变量来提供流量控制.假设主机A通过一条TCP连接向主机B发送一个大文件,定义以下变量

RcvBuffer:主机B为该连接分配的接收缓存的大小
LastByteRead:主机B上的应用进程从缓存读出的数据流的最后一个字节的编号
LastByteRcvd:从网络中到达的并且已放入主机B接收缓存中的数据流的最后一个字节的编号

由于TCP不允许已分配的缓存溢出,下式必须成立
$LastByteRcvd-LastByteRead\le RcvBuffer$
接收窗口用rwnd表示(空闲空间)
$rwnd=RcvBuffer-[LastByteRcvd-LastByteRead]$

主机B通过把当前的rwnd值放入它发给主机A的报文段接收窗口字段中,通知主机A缓存中还有多少可用空间

主机A轮流跟踪2个变量LastByteSent,LastByteAcked,这两个变量之间的差LastByteSent-LastByteAcked就是主机A发送到连接中但未被确认的数据量.通过将未确认的数据量控制在rwnd以内,就可以保证主机A不会使主机B的接收缓存溢出.因此主机A必须保证$LastByteSent-LastByteAcked\le rwnd$

当主机B的接收窗口为0时,主机A继续发送只有一个字节数据的报文段.这些报文段将会被接收方确认.最终缓存将开始清空,并且确认报文里将包含一个非0的rwnd值

UDP并不提供流量控制,报文段由于缓存溢出可能在接收方丢失

3.5.6 TCP连接管理

3.6 拥塞控制原理

3.6.1 拥塞原因与代价

两个发送方和一台具有无穷大缓存的路由器

当分组的到达速率接近链路容量时,分组经历巨大的排队时延

两个发送方和一台具有有限缓存的路由器

用$\lambda_{in}$字节/秒表示应用程序将初始数据发送到套接字中的速率.运输层向网络中发送报文段(含有初始数据或重传数据)的速率用$\lambda_{in}’$字节/秒表示,$\lambda_{in}’$有时被称为网络的供给载荷

3.6.2 拥塞控制方法

3.7 TCP拥塞控制

慢启动

拥塞避免

快速恢复

TCP拥塞控制:回顾

对TCP吞吐量的宏观描述

3.7.1 公平性

3.7.2 明确拥塞通告:网络辅助拥塞控制

4 网络层:数据平面

4.2 路由器工作原理(关键)

4.2.1 输入端口处理和基于目的地转发

前缀(prefix)
最长前缀匹配规则(longest prefix matching rule):在转发表(forwarding table)中寻找最长的匹配项,冰箱与最长前缀匹配相关联的链路接口转发分组

4.2.2 交换

4.2.3 输出端口处理

4.2.4 何处出现排队

输入排队
输出排队

4.2.5 分组调度(packet scheduler)

先进先出(FIFO,也称为先来先服务,FCFS)
优先权排队(priority queuing)
每个优先权类通常都有自己的队列.当选择一个分组传输时,优先权排队规则将从队列为飞空的最高优先权类中传输一个分组.在同一优先权类的分组之间的选择通常以FIFO方式完成
- 非抢占式优先权排队
  一旦分组开始传输,就不能打断
循环排队规则
加权公平排队(Weighted Fair Queuing, WFQ)

4.3 网际协议(关键)

4.3.1 IPv4数据报格式

版本号:不同的ip版本使用不同的数据报格式
首部长度
服务类型(TOS):以便不同类型的ip数据报能相互区别开来
见3.7.2(网络辅助拥塞控制),9.5.2.1(促进思考的场景),9.5.3(区分服务)
数据包长度:ip数据包的总长度(首部加上数据),以字节计
标识,标志,片偏移:见后
寿命(TTL):每当一台路由器处理数据报时,该字段的值-1.若TTL字段减为0,则该数据报必须丢弃
上层协议:指示了ip数据报的数据部分应交给哪个特定的运输层协议
首部检验和
源ip地址
目的ip地址
选项
数据

4.3.2 IPv4数据报分片

最大传送单元(Maximum Transimission Unit, MTU)
片(fragment)

IPv4的设计者将数据报的重新组装工作放到端系统中,而不是放到网络路由器中

标识:当生成一个数据报时,发送主机在为数据报设置标识号,通常将发送的每个数据报的标识号+1
标志:最后一个片的标志比特设为0,所有其他片的标志比特设为1
片偏移:指定该片应放在初始ip数据报的哪个位置

4.3.3 IPv4编址

接口:主机与物理链路之间的边界叫做接口,路由器与它的任意一条链路之间的边界也叫做接口.ip要求每台主机和路由器接口拥有自己的ip地址.因此,一个ip地址与一个接口相关联,而不是与包括该接口的主机或路由器相关联
子网(subnet):互联主机接口与路由器接口的网络形成一个子网.分开主机和路由器的每个接口,产生几个隔离的网络岛,使用接口端接这些隔离的网络的端点,这些隔离的网络中的每一个都叫做一个子网
子网掩码(network mask):指示32比特中的最左侧$x$比特定义了子网地址
前缀(prefix)(或网络前缀):形式为$a.b.c.d/x$的地址的$x$最高比特构成了ip地址的网络部分,并且经常被称为该地址的前缀
无类别域间路由选择(Classless Interdomain Routing, CIDR)
分类编址(classful addressing),ABC类网络
广播地址:当一台主机发出一个目的地址为255.255.255.255的数据报时,该报文会交付给同一个网络中的所有主机

获取一块地址
获取主机地址:动态主机配置协议
- 动态主机配置协议(Dynamic Host Configuration, DHCP):
  网络管理员能够配置DHCP,使某给定主机每次与网络连接时能得到一个相同的ip地址,或者某主机将被分配一个临时的ip地址,每次与网络连接时该地址也许是不同的
  由于DHCP具有将主机连接进一个网络的网络相关方面的自动能力,故他又常被称为即插即用协议或零配置协议
  对于一台新到达的主机而言,DHCP协议是一个4个步骤的过程
  - DHCP服务器发现:客户在UDP分组中向端口67发送发现报文,该UDP分组封装在一个ip数据报中,使用广播目的地址255.255.255.255并且使用源ip地址0.0.0.0.DHCP客户将该ip数据报传递给链路层,链路层然后将该帧广播到所有与该子网连接的节点
  - DHCP服务器提供:DHCP服务器收到一个DHCP发现报文时,用DHCP提供报文向客户做出响应,该报文向该子网的所有节点广播,仍然使用ip广播地址255.255.255.255.每台服务器提供的报文包含有收到的发现报文的事务id,向客户推荐的ip地址,网络掩码以及ip地址租用期,服务器租用期通常设置为几小时或几天
  - DHCP请求:客户从一个或多个服务器提供中选择一个,并向选中的服务器提供用DHCP请求报文进行响应,回显配置的参数
  - DHCP ACK:服务器用DHCP ACK报文对DHCP请求报文进行响应,证实所要求的参数

4.3.4 网络地址转换(NAT)

NAT转换表

4.3.5 IPv6

IPv6数据报格式
- IPv6定义的字段
  - 版本:IPv6将该字段值设为6
  - 流量类型:与IPv4的TOS相似
  - 流标签:用于标识一条数据报的流,能够对一条流中的某些数据报给出优先权
  - 有效载荷长度:IPv6数据报中跟在定长40字节数据报首部后面的字节数量
  - 下一个首部:标识数据报中的内容(数据字段)需要交付给哪个协议.该字段使用与IPv4首部中协议字段相同的值
  - 跳限制:转发数据报的每台路由器将对该字段的内容-1.如果跳限制计数达到0,则该数据报将被丢弃
  - 数据
- IPv6的变化
- IPv6舍弃的字段
  - 分片/重新组装:IPv6不允许在中间路由器上进行分片与重新组装,这种操作只能在源/目的地执行.如果路由器收到的IPv6数据报因太大而不能转发到出链路上的话,则路由器只需丢掉该数据报,并向发送方发挥一个分组太大的ICMP(互联网控制报文协议)差错报文即可
  - 首部校验和:在网络层中具有该项功能实属多余
  - 选项:可能出现在IPv6首部中由下一首部指出的位置上
从IPv4到IPv6的迁移
- 建隧道

5 网络层:控制平面

5.2 路由选择算法

集中式路由选择算法/分散式路由选择算法:链路状态算法(LS),距离向量算法(DV)
静态路由选择算法/动态路由选择算法
负载敏感算法,负载迟钝的(如RIP,OSPF和BGP)

5.2.1 链路状态路由选择算法

初始化:
$N’=\{u\}$
对$N$中所有节点$v$:
if ($v$是$u$的邻接节点)
$D(v)=c(u,v)$
else
$D(v)=\infty$

循环(直到($N==N’$)):
在$N-N’$中找到$w$满足$D(w)$为最小值
$N’=N’\cup\{w\}$
更新$w$的所有不在$N’$中的邻接节点:
$D(v)=\min\{D(v),D(w)+c(w,v)\}$

5.2.2 距离向量路由选择算法

每个节点$x$维护下列路由选择信息

对于每个邻居$v$,从$x$到直接相连邻居$v$的开销为$c(x,v)$
$x$的距离向量($x$到$N$中所有目的地$y$的开销估计值):$\bm{D}_x=[D_x(y):y\in N]$
$x$的每个邻居$v$的距离向量:$\bm{D}_v=[D_v(y):y\in N]$

初始化:
对$N$中所有节点$y$:
$D_x(y)=c(x,y)$,如果$y$不是$x$的邻接节点,则$D_x(y)=\infty$
对$x$的所有邻接节点$w$:
对$N$中所有节点$y$:
$D_w(y)=?$($\infty$)
对$x$的所有邻接节点$w$:
向$w$发送$x$的距离向量$\bm{D}_x$

循环:
wait (有邻接节点$w$的开销发生变化/收到来自邻接节点$w$的距离向量)
对$N$中所有节点$y$:
$D_x(y)=\min\{c(x,v)+D_v(y)\}$
if ($D_x(y)$发生变化)
向所有邻接节点发送距离向量$\bm{D}_x=[D_x:y\in N]$

5.3 因特网中自制系统内部的路由选择:OSPF(开放最短路优先)

自治系统(AS),自治系统内部路由选择协议

OSPF是一种链路状态协议,使用洪泛链路状态信息和Dijkstra最低开销路径算法,各条链路开销是由网络管理员配置的

使用OSPF时,路由器向自治系统内所有其他路由器广播路由选择信息,而不仅仅是向其相邻的路由器广播.每当一条链路的状态发生变化时(如开销的变化或连接/中断状态的变化),路由器就会广播链路状态信息.计时链路状态未发生变化,它也要周期性地广播链路状态

OSPF的优点:

安全
多条相同开销的路径:当到达某目的地的多条路径具有相同的开销时,OSPF允许使用多条路径(无需仅选择单一的路径来承载所有的流量)
对单播与多播路由选择的综合支持
支持在单个AS中的层次结构

5.4 ISP之间的路由选择:BGP(边界网关协议)(概念)

5.4.1 BGP的作用

在BGP中,分组并不是路由到一个特定的目的地址.相反,时路由到CIDR(无类别域间路由选择)化的前缀,其中每个前缀表示一个子网或一个子网的集合

5.4.2 通告BGP路由信息

对于每个AS,每台路由器要么是一台网管路由器,要么是一台内部路由器

在BGP中,每队路由器通过使用179端口的半永久TCP连接交换路由选择信息.每条直接连接以及通过该连接发送的BGP报文,称为BGP连接.跨越两个AS的BGP连接称为外部BGP(eBGP)连接,在相同AS中的两台路由器之间的BGP会话称为内部BGP(iBGP)连接

5.4.3 确定最好的路由

当路由器通过BGP连接通告前缀时,他在前缀中包括一些BGP属性,前缀及其属性称为路由(route).每条BGP路由包含3个组件:NEXT-HOP,AS-PATH,目的前缀

AS-PATH属性包含了通告已经通过的AS的列表.BGP路由器还使用AS-PATH属性来检测和防止通告环路,如果一台路由器在路径列表中看到包含了他自己的AS,它将拒绝该通告

NEXT-HOP是AS-PATH起始的路由器接口的ip地址

5.6 ICMP:因特网控制报文协议

ICMP被主机和路由器用来彼此沟通网络层的信息.ICMP通常被认为是ip的一部分,但从体系结构上讲它位于ip之上.ICMP报文有一个类型字段和一个编码字段,并且包含引起该ICMP报文首次生成的ip数据报的首部和前8个字节(以便发送方能确定引发该差错的数据报)

ping程序发送一个ICMP类型8编码0的报文到指定主机,看到回显(echo)请求,目的主机发回一个类型0编码0的ICMP回显回答

ICMP报文类型:TODO

6 链路层和局域网

6.3 多路访问链路和协议

点对点链路
广播链路:能够让多个发送和接收节点都连接到相同的,单一的,共享的广播信道上
多路访问问题,多路访问协议
碰撞(collide):因为所有的节点都能够传输帧,所以多个节点可能会同时传输帧,所有节点同时接到多个帧.这就是说,传输的帧在所有的接收方处碰撞

在理想情况下,对于速率为$R$bps的广播信道,多路访问协议应该具有以下所希望的特性:

当仅有一个节点发送数据时,该节点具有$R$bps的吞吐量
当有$M$个节点发送数据时,每个节点在一些适当定义的时间间隔内应该有$R/M$的平均传输速率
协议是分散的:这就是说不会因某主节点故障而是整个系统崩溃
协议是简单的:实现不昂贵

6.3.1 信道划分协议

时分多路复用(TDM)
频分多路复用(FDM)
码分多址(CDMA)
CDMA对每个节点分配一种不同的编码,每个节点用它唯一的编码来对他发送的数据进行编码,不同的节点能够同时传输

6.3.2 随机接入协议

当一个节点经历一次碰撞时,它在重发该帧之前等待一个随机时延,涉及碰撞的每个节点独立地选择随机时延

时隙ALOHA

假设:

所有帧由$L$比特组成
时间被划分成长度为$L/R$秒的时隙
节点只在时隙起点开始传输帧
节点是同步的,每个节点都知道时隙何时开始
如果在一个时隙中有两个或者更多个帧碰撞,则所有节点在该时隙结束之前检测到该碰撞事件
如果没有碰撞,该节点成功的传输它的帧
如果有碰撞,该节点在时隙结束之前检测到这次碰撞.该节点以概率$p$在后续的每个时隙中重传它的帧,直到该帧被无碰撞地传输出去

刚好有一个节点传输的时隙称为一个成功时隙
时隙多路访问协议的效率:当有大量活跃节点且每个节点总有大量的帧要发送时,长期运行中成功时隙的份额

一个给定节点成功传送的概率是$p(1-p)^{N-1}$

ALOHA

如果一个传输的帧与一个或多个传输经历了碰撞,这个节点将立即以概率$p$重传该帧

一个给定节点成功传送的概率是$p(1-p)^{2(N-1)}$

载波侦听多路访问(CSMA)

载波侦听
碰撞检测
信道传播时延

具有碰撞检测的载波侦听多路访问(CSMA/CD)

适配器从网络层获得数据报,准备链路层帧,并将其放入帧适配器缓存中
如果适配器侦听到信道空闲,它开始传输帧.如果适配器侦听到信道正在忙,他将等待,直到侦听到没有信号能量时才开始传输帧
在传输过程中,适配器监视来自其他使用该广播信道的适配器的信号能量的存在
如果适配器在传输时检测到来自其他适配器的信号能量,他中止传输
中止传输后,适配器等待一个随机的时间量,然后返回步骤2

二进制指数后退算法
当传输一个给定帧时,该帧经历了$n$次碰撞后,节点随机地从$\{0, 1, 2, \cdots, 2^n-1\}$中选择一个$K$值
对于以太网,一个节点等待的实际时间量是$K\cdot 512$比特时间($K$被发送512比特进入以太网所需的时间量)

6.3.3 轮流协议

轮询协议
- 轮询时延:每次活跃节点发送了它最多数量的帧时,主节点必须依次轮询每一个非活跃的节点
- 如果主节点有故障,整个信道都变得不可操作
令牌传递协议
- 一个节点的故障可能会使整个信道崩溃

6.4 交换局域网

6.4.1 链路层寻址和ARP

MAC地址

并不是主机或路由器具有链路层地址,而是他们的适配器(网络接口)具有链路层地址

LAN地址,物理地址,MAC地址

没有两块适配器具有相同的地址

适配器的MAC地址具有扁平结构,不论适配器到哪里都不会变化

当某适配器要向某些目的适配器发送一个帧时,发送适配器将目的适配器的MAC地址插入到该帧中,并将该帧发送到局域网上.一块适配器可以接收一个并非向它寻址的帧.当适配器接收到一个帧时,将检查该帧中的目的MAC地址是否与他自己的MAC地址匹配.如果匹配,该适配器提取出封装的数据报,并将该数据报沿协议栈向上传递.如果不匹配,该适配器丢弃该帧

MAC广播地址:FF-FF-FF-FF-FF-FF

地址解析协议(ARP)

假设交换机广播所有帧

在发送主机中的ARP模块将取在相同局域网上的任何ip地址作为输入,然后返回相应的MAC地址

ARP将一个ip地址解析为一个MAC地址.ARP只为在同一个子网上的主机和路由器接口解析ip地址

每台主机或路由器在其内存中具有一个ARP表,这张表包含ip地址到MAC地址的映射关系.从一个表项放置到某ARP表中开始,一个表项通常的过期时间是20分钟

ARP分组有几个字段,包括发送和接收ip地址及MAC地址.ARP查询分组和响应分组都具有相同的格式.ARP查询分组的目的是询问子网上所有其他主机和路由器,以确定对应于要解析的ip地址的那个MAC地址
如果ARP表中当前没有目的主机的表项:发送方向它的适配器传递一个ARP查询分组,并且指示适配器应该用MAC广播地址(FF-FF-FF-FF-FF-FF)来发送这个分组.适配器在链路层帧中封装这个ARP分组,用广播地址作为帧的目的地址,并将该帧传输进子网中
包含该ARP查询的帧能被子网上所有其他的适配器接收到,并且每个适配器都把在该帧中的ARP分组向上传递给ARP模块.这些ARP模块中的每个都检查它的ip地址是否与ARP分组中的ip地址相匹配.与之匹配的一个给查询主机发送回一个带有所希望映射的相应ARP分组.然后查询主机能够更新它的ARP表

发送数据报到子网以外

一台路由器对它的每个接口都有一个ip地址.对路由器的每个接口,在路由器中也有一个ARP模块和一个适配器

具体例子见教材

6.4.2 以太网

集线器(hub)
交换机(switch)

以太网帧结构

发送适配器在一个以太网帧中封装了一个ip数据报,并把该帧传递到物理层

以太网帧的6个字段

数据字段(46-1500字节):承载ip数据报.如果ip数据报小于46字节,数据报必须被填充到46字节
目的地地址(6字节):目的适配器的MAC地址
源地址(6字节):传输该帧到局域网上的适配器的MAC地址
类型字段(2字节):允许以太网复用多种网络层协议.ip和其他链路层协议都有各自的标准化的类型编号
CRC(4字节):循环冗余检测
前同步码(8字节):以太网帧以一个8字节的前同步码字段开始.前同步码的前7字节的值都是10101010,最后一个字节是10101011.前同步码字段的前7字节用于唤醒接收适配器,并且将它们的时钟和发送方的时钟同步

以太网技术

转发器(repeater):是一种物理层设备,能在输入端接收信号并在输出端再生该信号

在基于交换机的以太局域网中,不会有碰撞,因此没有必要使用MAC协议了

6.4.3 链路层交换机

交换机转发和过滤

交换机表中的表项包括:

一个MAC地址
通向该MAC地址的交换机接口
表项放置在表中的时间

假定目的地址为DD-DD-DD-DD-DD-DD的帧从交换机接口$x$到达,交换机用MAC地址DD-DD-DD-DD-DD-DD索引它的表:

表中没有对于DD-DD-DD-DD-DD-DD的表项,交换机广播该帧
表中有一个表项将DD-DD-DD-DD-DD-DD与接口$x$联系起来,交换机通过丢弃该帧执行过滤功能即可
表中有一个表项将DD-DD-DD-DD-DD-DD与接口$y\not=x$联系起来,交换机通过将该帧放到接口$y$前面的输出缓存完成转发功能
表中

自学习

交换机表初始为空
对于每个接口接收到的每个入帧,该交换机在其表中存储:
1. 该帧源地址字段中的MAC地址
2. 该帧到达的接口
3. 当前时间
如果在一段时间(老化期)后,交换机没有收到以该地址作为源地址的帧,就在表中删除这个地址

交换机时即插即用设备,他们不需要网络管理员或用户的干预

链路层交换机的性质

消除碰撞:在使用交换机构建的局域网中,没有因碰撞而浪费的带宽.交换机的最大聚合带宽时该交换机所有接口速率之和
异质的链路:交换机将链路彼此隔离,因此局域网中的不同链路能够以不同的速率运行并且能够在不同的媒体上运行
管理

交换机和路由器比较

交换机

优点
- 交换机时即插即用的
- 交换机必须处理到高至第二层(链路层)的帧,路由器必须处理高至第三层(网络层)的帧
缺点
- 为了防止广播帧的循环,交换网络的活跃拓普限制为医科生成树
- 一个大型交换网络将要求在主机和路由器中有大的ARP表,这将生成可观的ARP流量和处理量

路由器

优点
- 网络寻址通常是分层次的,即使网络中存在冗余路径,分组通常也不会通过路由器循环(ip用寿命字段来限制循环).所以,分组不会限制到一颗生成树上,并可以使用源和目的地之间的最佳路径
- 他们对第二层的广播风暴提供了防火墙保护
缺点
- 路由器和连接到他们的主机都需要人为地配置ip地址
- 路由器对每个分组的处理时间通常比交换机更长

6.4.4 虚拟局域网

TODO

7 无线网络和移动网络

7.3 Wifi:802.11无线LAN(概念)

在IEEE 802.11协议族中几套有关无线LAN的802.11标准都使用相同的媒体访问协议CSMA/CA

7.3.1 802.11 体系结构

802.11体系结构的基本构建模块是基本服务集(BSS).一个BSS包含一个或多个无线站点和一个称为接入点(AP)的中央基站

配置AP的无线LAN经常被称作基础设施无线LAN,其中的基础设施是指AP,互联AP和一台路由器的有限以太网

信道与关联

在802.11中,每个无线站点在能够发送或者接收网络层数据之前,必须与一个AP相关联

当网络管理员安装一个AP时,管理员为该接入点分配一个单字或双字的服务集标识符(SSID)

Wifi丛林

802.11标准要求每个AP周期性地发送信标帧,每个信标帧包括该AP的SSID和MAC地址

扫描信道和监听信标帧的过程被称为被动扫描.无线主机也能够执行主动扫描,这是通过向位于无线主机范围内的所有AP广播探测帧完成的.AP用一个探测响应帧应答探测请求帧.无线主机则能够在响应的AP中选择某AP与之相关联

选定与之关联的AP后,无线主机向AP发送一个关联请求帧,并且该AP以一个关联响应帧进行响应.对于主动扫描需要这种第二次请求/响应握手.一旦与一个AP关联,该主机希望加入该AP所属的子网中,该主机通常将通过关联的AP向该子网发送一个DHCP发现报文(间DHCP协议)以获取在该AP子网中的一个ip地址

为了与特定的AP创建一个关联,某无线站点可能要向该AP鉴别他自身.802.11无线LAN提供了几种不同的鉴别和接入方法

基于一个站点的MAC地址允许其接入一个无线网络
应用用户名和口令

7.3.2 802.11 MAC协议

将无线设备或AP称为站点

带碰撞避免的CSMA(CSMA/CA)

两种MAC协议的区别

802.11使用碰撞避免而非碰撞检测
由于无线信道相对较高的误比特率,802.11使用链路层确认/重传(ARQ)方案

802.11未实现碰撞检测的原因

检测碰撞的能力要求站点具有同时发送和接收的能力.因为在802.11适配器上,接收信号的强度通常远远小于发送信号的强度,制造具有监测碰撞能力的硬件代价较大
适配器会由于隐藏终端问题和衰减问题而无法检测到所有的碰撞

由于802.11无线局域网不使用碰撞检测,一旦站点开始发送一个帧,就不会返回

假设一个站点(无线站点或者AP)有一个帧要发送

如果某站点最初监听到信道空闲,他将在一个被称作分布式帧间间隔(DIFS)的短时间段后发送该帧
否则,该站点选取一个随机回退值,并且在侦听信道空闲时递减该值
当计数值减为0时,该站点发送整个数据帧并等待确认
如果收到确认
- 如果要发送另一帧,将从第2步开始CSMA/CA协议
- 如果未收到确认,发送站点将重新进入第二步中的回退阶段,并从一个更大的范围内选取该随机值

802.11的链路层确认方案:目的站点收到一个通过CRC校验的帧后,他等待一个称作短帧间间隔(SIFS)的一小段时间,然后发回一个确认帧.如果发送站点在给定的时间内未收到确认帧,它假定出现了错误并重传该帧.如果在若干固定次重传后仍未收到确认,发送站点将放弃发送并丢弃该帧

处理隐藏终端:RTS和CTS

IEEE 802.11协议允许站点使用一个短请求发送(RTS)控制帧和一个短允许发送(CTS)控制帧来预约对信道的访问.当发送方要发送一个DATA帧时,它能够首先向AP发送一个RTS帧,指示传输DATA帧和确认(ACK)帧需要的总时间.当AP收到RTS帧后,他广播一个CTS作为响应:该发送方明确发送许可,指示其他站点在预约期内不要发送

RTS/CTS交换仅仅用于为长数据帧预约信道.每个无线站点可以设置一个RTS门限值,仅当帧长超过门限值时,才使用RTS/CTS序列

使用802.11作为一个点对点链路

7.3.3 IEEE 802.11帧

有效载荷与CRC字段
地址字段
序号,持续期和帧控制字段

7.3.4 在相同的ip子网中的移动性

TODO

7.3.5 802.11中的高级特色

7.3.6 个人域网络:蓝牙和ZigBee

蓝牙
ZigBee

9 多媒体网络

9.1 多媒体网络应用

9.1.1 视频的性质

9.1.2 音频的性质

9.1.3 多媒体网络应用的类型

流式存储音频和视频
会话式ip语音和视频
流式实况音频和视频

9.2 流式存储视频

9.2.1 UDP流

9.2.2 HTTP流

预取视频
客户应用缓存和TCP缓存
流式视频的分析

$B$表示客户应用缓存的长度,$Q$表示客户应用缓存开始播放之前必须被缓存的比特数量,$r$表示视频消耗速率.$t_p,t_f$TODO

视频的早期中止和重定位

9.3 ip语音

9.3.1 尽力而无服务的限制

丢包
端到端时延
分组时延抖动

9.3.2 在接收方消除音频的时延抖动

固定播放时延
实验性播放时延

9.3.3 从丢包中恢复

向前纠错
交织
差错掩盖

9.4 实时会话式应用的协议

9.4.1 RTP

9.4.2 SIP

数据库复习提纲

2019-12-26

1 数据库系统概述

1.1 基本概念

数据库,数据库管理系统,数据库系统,数据库管理员(相互之间的关系)

1.2 数据库系统的特点

数据集成化,数据独立性,数据共享,数据冗余,数据安全性,完整性和一致性,并发控制和故障恢复

1.3 数据库内部结构体系

数据模式
三级模式,二级映射
三级模式与数据独立性关系

2 数据模型

2.1 数据模型的基本概念

数据模型及其组成成分:数据结构,数据操作,数据约束
数据模型的核心,不同类型数据模型的区分依据
三个抽象层次上的数据模型概念:概念数据模型,逻辑数据模型,物理数据模型

2.2 数据模型的四个世界

现实世界,概念世界,信息世界,计算机世界

2.3 概念世界与概念模型

E-R模型与E-R图(包括扩充E-R模型)
- 实体,属性,联系
- 多值属性,组合属性
- 联系上的函数对应关系,参与方式
- IS-A联系,弱实体
面向对象模型:对象,对象标识符,类,方法,超类和子类,聚合和分解,继承和合成

2.4 信息世界和逻辑模型

关系模型:关系,属性,值域(域),元组,关系数据库,关键字

2.5 计算机世界与物理模型

逻辑模型的物理存储:项,记录,文件,索引,集簇
提高文件访问效率的常用方法:索引,集簇,hash

3 关系数据库系统

3.1 关系数据库系统概述

3.2 关系数据库系统的衡量准则

完全关系型的十二条衡量准则
空值(NULL)的定义

3.3 关系代数

3.3.0 关系模型(概念)

关系数据结构
- 表结构(表头):表框架,表的元数与基数
- 关系:关系的性质
- 关键字:候选关键字,主关键字,外关键字
- 关系数据库:关系子模式-视图(view)
关系操纵
- 数据查询:两个关系的合并,单个关系内的元组选择,单个关系内的属性指定
- 元组的删除,插入,修改
- 空值的处理
关系中的数据约束
- 实体完整性约束,参照完整性约束,用户定义的完整性

3.3.1 关系的表示

关系的表示,笛卡尔乘积

3.3.2 关系操纵的表示

关系代数中的五种基本运算:选择,投影,笛卡尔积,并,差(注意执行条件)

3.3.3 关系模型与关系代数

3.3.4 关系代数中的扩充运算

交,除法,联接,自然联接,$\theta$-联接
扩充运算与基本运算之间的关系

3.3.5 关系代数的应用

3.3.6 关系演算

原子公式,公式的定义
基于关系演算的数据查询表示:单表查询,多表连接查询,复杂查询的表示

3.4 关系数据库语言SQL

3.4.1 SQL概貌

SQL的基本概念与使用方式:表,行,列

3.4.2 数据定义功能

3.4.3 数据操纵功能

SQL语言与关系代数的关系
基本查询功能:distinct,like,is null,多表联接查询,表的自联接查询
嵌套查询:in,some/any/all,exists等谓词,相关子查询与独立子查询
子查询的合并:union/intersect/except [all]
统计查询(group by,having):统计与分组统计查询,空值与空集在统计函数中的处理方法
复杂数据查询
查询结果输出
- 结果元组去重:distinct
- 结果元组排序:order by

3.4.4 更新功能

元组删除
元组插入:常量元组的插入,带子查询的元组插入
元组修改

3.4.5 视图

视图概念,视图与基表的区别
视图的创建与删除
视图的嵌套定义
视图删除中的连锁反应
可更新视图的判断准则
视图的作用

4 数据库的安全性与完整性保护

4.1 数据库的安全性保护

数据库安全的基本概念与内容:主体,客体,身份标识与鉴别,自主访问控制,审计
SQL对数据库安全的支持
- SQL中的存储权限
- SQL中的授权命令grant和权限回收命令revoke

4.2 数据库的完整性保护

数据库完整性保护的功能:目的与常用实现措施
实体完整性,参照完整性,用户定义完整性
完整的create table命令
- 基表的创建
- 完整性约束的定义:主关键字,外关键字,check约束,unique,not null,default
触发器及其创建命令

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

5.1 事务处理(概念)

事务的定义与ACID性质
事务活动及其状态转换图
事务控制及相关的参数设置语句:事务的提交与回滚,事务的读/写类型与隔离级别
事务的语句组成成分

5.2 并发控制技术(概念)

事务
- 事务的并发性,并发控制
- 调度,串行调度,可串行化调度,冲突与冲突可串行化,视图可串行化
- 冲突可串行化的判定方法
- 不正确的事务所导致的数据不一致现象:丢失修改(lost-update),脏读(dirty-read),不可重复读(unrepeatable-read)
封锁
- 共享锁(S锁),排它锁(X锁),锁相容矩阵,锁申请/锁释放算法
- 基于封锁技术的并发控制实现方法
  - 三级封锁协议,三级封锁协议与数据不一致现象之间的关系
  - 两阶段封锁协议
  - 两阶段封锁协议与冲突可串行化的关系
多粒度封锁
- 封锁粒度/并发度/并发控制实现开销之间的关系
- 多粒度树,多粒度封锁
- 基于意向锁的多粒度封锁协议
  - 意向锁:IS,IX,SIX
  - 意向锁锁相容矩阵
  - 意向锁锁申请/释放算法
死锁的监测与预防
- 死锁,活锁
- 死锁的检测及其处理办法
  - 等待图法
  - 超时死锁检测法:锁申请等待超时,事务执行超时
  - 时间戳死锁检测法

5.3 数据库恢复技术

数据库恢复的含义,方法和常用措施
数据库故障的分类
数据库故障恢复三大技术:数据转储,日志,数据库镜像
数据转储:静态转储/动态转储,海量转储/增量转储
日志
- 日志的内容,组成,作用与记载原则
- 在日志中设置检查点的作用
- 事务的撤销(undo)与重做(redo)
- undo日志
- redo日志
- undo/redo日志
- 3种日志的优缺点
恢复策略:小型/中型/大型故障的恢复策略

6 7

游标管理

游标的作用
游标的定义,打开,使用,关闭
可滚动游标的定义及其在数据更新命令中的使用

索引

B+索引的数据结构,搜索算法

8 关系数据库规范化理论

8.1 概述

模式设计质量的评级指标:数据冗余度,插入/删除等更新异常
为什么要研究关系的规范化设计:规范化的目的与手段

8.2 规范化理论

8.2.1 函数依赖(FD)

函数依赖的定义
如何寻找函数依赖:函数依赖与数据完整性约束的关系
完全/部分FD,平凡/非平凡FD,直接/传递FD
Armstrong公理系统:3条基本原则+3条扩充原则
基于函数依赖的关键字定义
属性集闭包的计算算法
关键字的计算算法

8.2.2 与函数依赖有关的范式

范式定义:1NF,2NF,3NF,BCNF
理解各级范式与数据冗余度,插入/删除异常的关系

8.2.3 多值依赖与第四范式

多值依赖,平凡多值依赖,非平凡多值依赖
多值依赖与函数依赖的关系
4NF

8.3 规范化所引起的一些问题

函数依赖的逻辑蕴含,函数依赖集的等价
最小函数依赖集及其判定方法
最小函数依赖集的计算算法
模式分解的无损联结性,依赖保持性及其判定方法
直接到3NF且满足无损联结性和依赖保持性的模式分解算法
从3NF到BCNF,4NF的分解方法

9 数据库设计

9.1 数据库设计概述

9.2 数据库设计的需求分析

9.3 数据库的概念设计

9.4 数据库的逻辑设计

9.5 数据库的物理设计

微电子

2019-11-04

电路模型和电路定律

电流和电压的参考方向

关联参考方向:电流、电压方向一致
非关联参考方向:电流、电压方向不一致

电功率和能量

在$U,I$为关联参考方向下:

$U,I$同号,元件吸收功率
$U,I$异号,元件释放功率

电阻元件

线性电阻

电容元件

$dq=Cdv$

电容吸收的功率

电感元件

$d\phi=Ldi$

电压源和电流源

受控电源

控制系数

基尔霍夫定律

支路:组成电路的每一个二端元件称为一条支路
节点:支路的连接点称为节点
回路:由支路构成的闭合路径称为回路

KCL:基尔霍夫电流定律

在集总电路中,任何时刻,对任一节点,所有流出节点的支路电流的代数和恒等于0

KVL:基尔霍夫电压定律

在集总电路中,任何时刻,沿任一回路所有支路电压的代数和恒等于0

电阻电路的等效变换

电路的等效变换

等效电路:对电路的一部分进行简化,用简化的电路替代原电路.代换与被代换部分的电压,电流关系相同.这两部分电路互称等效电路

电阻的串联和并联

桥形连接

当满足条件$R_1R_4=R_2R_3$时,对角线支路中的电流为0,称为电桥处于平衡状态,这一条件也成为电桥的平衡条件

电阻的$Y$形联结和$\Delta$形联结的等效变换

$\Delta$形电阻$=\dfrac{Y\text{形电阻两两乘积之和}}{Y\text{形不相邻电阻}}$

$R_{12}=\dfrac{R_1R_2+R_2R_3+R_3R_1}{R_3}$
$R_{23}=\dfrac{R_1R_2+R_2R_3+R_3R_1}{R_1}$
$R_{31}=\dfrac{R_1R_2+R_2R_3+R_3R_1}{R_2}$

$Y$形电阻$=\dfrac{\Delta\text{形相邻电阻的乘积}}{\Delta\text{形电阻之和}}$

$R_1=\dfrac{R_{12}R_{31}}{R_{12}+R_{23}+R_{31}}$
$R_2=\dfrac{R_{23}R_{12}}{R_{12}+R_{23}+R_{31}}$
$R_3=\dfrac{R_{31}R_{23}}{R_{12}+R_{23}+R_{31}}$

电压源,电流源的串并联

只有电压相等极性一致的电压源才允许并联,等效电路为其中任一电压源
只有电流相等且方向一致的电流源才允许串联,等效电路为其中任一电流源

实际电源的两种模型及其等效变换

电压源转为电流源:$i_s=\dfrac{u_s}{R}$

(含受控源电路的)输入电阻

当一端口无源网络内含有受控源时,可以采用外加电压法或外加电流法求得输入电阻之和

电阻电路的一般分析

电路的图

线图(图)

用线段代替电路中的每个元件,线段称为支路,线段的端点称为结点,这样的以线,点组成的几何结构图称为线图或拓扑图,简称图,用$G$表示

树,树支,连支

树:包含图$G$的全部结点和部分支路,本身是连通的,不包含回路,用$T$表示
树支:构成树的各支路叫树支
连支:除树支以外的其他支路称为连支

KCL和KVL的独立方程数

对一个节点数为$n$,支路数为$b$的连通图
- KCL独立方程数为$n-1$个
- KVL独立方程数等于它的独立回路(连支)数$b-n+1$

支路电流法

选定各支路电流的参考方向
对$(n-1)$个独立结点列出KCL方程
选取$(b-n+1)$个独立回路,指定回路的绕行方向,列出KVL方程

网孔电流法

仅适用于平面电路

回路电流法

根据给定的电路,通过选择一个树确定一组基本回路,并指定各回路电流的参考方向
列出回路电流方程
当电路中优受控源或无伴电流源时,另行处理
对于平面电路可用网孔电流法

结点电压法

指定参考结点,其余结点对参考节点之间的电压就是节点电压.通常以参考结点为各节点电压的负极性
列出节点电压方程
当电路中有受控源或无伴电压源时需另行处理

电路定理

叠加定理

一个具有唯一解的线性电阻电路,任一处的电压(或电流)是各个独立电源单独作用时在该处产生的电压(或电流)的叠加

齐性定理

线性电路中当所有激励都增大或缩小$N$倍,则电路的相应也将增大或缩小$N$倍

替代定理

戴维宁定理和诺顿定理

戴维宁定理

一个含独立电源,线性电阻和受控源的一端口,对外电路来说,可以用一个电压源与电阻的串联组合来等效.其中电压源的电压等于一端口的开路电压$U_{OC}$,电阻等于一端口的全部独立电源均置0后的输入电阻$R_i$

诺顿定理

一个含独立电源,线性电阻和受控源的二端网络,可以等效为一个电流源和电导的并联组合.电流源的电流等于该网络的短路电流,电导等于该网络全部独立电源置0后的输入电导

动态电路

含有动态元件电容和电感的电路称为动态电路

特点:当动态电路状态发生改变时(换路)需要经历一个变化过程才能达到新的稳定状态.这个变化过程称为电路的过渡过程

过渡过程产生的原因:电路内部含有储能元件$L,C$,电路在换路时能量发生变化,而能量的存储和释放都需要一定的时间来完成

动态电路的方程

含有一个动态元件电容或电感的线性电路,其电路方程为一阶线性常微分方程,称一阶电路
含有两个动态元件的线性电路,其电路方程为二阶线性常微分方程,称二阶电路
结论

描述动态电路的电路方程为微分方程
动态电路方程的阶数通常等于电路中动态元件的个数

动态电路的初始条件

换路定律

换路瞬间,若电容电流保持为有限值,则电容电压(电荷)换路前后保持不变
换路瞬间,若电感电压保持为有限值,则电感电流(磁链)换路前后保持不变

正弦电路

同频率正弦量的相位差

$\phi=\psi_i-\psi_u$

$\psi < 0,u$超前$i$ $\phi$角($u$比$i$先到达最大值)

同相,反相

周期性电流,电压的有效值

电压有效值$U=\sqrt{\dfrac{1}{T}\int_0^Tu^2(t)dt}=\dfrac{1}{\sqrt{2}}U_m$

正弦稳态电路的功率

$u(t)=\sqrt{2}U\sin\omega t,i(t)=\sqrt{2}I\sin(\omega t-\phi)$

平均功率:$P=\dfrac{1}{T}\int_0^Tpdt=UIcos\phi$,表示电路实际消耗的功率,亦称为有功功率
无功功率:$Q=UI\sin\phi$,反映网络与外电路交换功率的大小,是由储能元件$L,C$的性质决定的.单位:var(乏)
视在功率(表观功率):$S=UI$,反映含源一端口的做功能力,反映电气设备的容量.单位:$VA$(伏安)

R,L,C元件的有功功率和无功功率

对电阻,$u,i$同相,故$Q=0$,电阻只吸收(消耗)功率,不发出功率

$P_R=UI\cos\phi=UI\cos0$
$Q_R=UI\sin\phi=UI\sin0$

对电感,$u$领先$i$ 90,故$P_L=0$,即电感不消耗功率.由于$Q_L > 0$,故电感吸收无功功率

$P_R=UI\cos\phi=UI\cos90$
$Q_R=UI\sin\phi=UI\sin90$

对电容,$i$领先$u$ 90,故$P_C=0$,即电容不消耗功率.由于$Q_C < 0$,故电容发出无功功率

电感,电容的无功补偿作用

当$L$发出功率时,$C$刚好吸收功率,则与外电路交换功率为$p_L+p_C$.因此$L,C$的无功具有互相补偿的作用

有功,无功,视在功率的关系

$S=\sqrt{P^2+Q^2}$

功率因数提高

设备容量$S$(额定)向负载送多少有功要由负载的阻抗角决定:$P=S\cos\phi$

功率因数低带来的问题:

设备不能充分利用,电流到了额定值,但功率容量还有
当输出相同的有功功率时,线路上的电流大,线路压降损耗大

解决办法:并联电容,提高功率因数(改进自身设备)

$P_R=UI\cos\phi=UI\cos0$
$Q_R=UI\sin\phi=UI\sin0$

Android开发笔记

2019-09-04

`Music`开发笔记

CSDN:实例
 cnblogs:其他几种方式

音乐进度

`MediaPlayer`

MediaPlayer参数–简书

时长

CSDN:数字格式化

total_time = MainPlayer.player.getDuration();
SimpleDateFormat format = new SimpleDateFormat("mm:ss");

// TODO 更新总时长
tmp = new Date(total_time);
formatTime = format.format(tmp);
MainPlayer.totalTime.setText(formatTime);

进度条

媒体信号

蓝牙

CSDN:配对全过程
 CSDN:简易

有线耳机

CSDN

创建一个继承BroadcastReceiver的类

public class MediaReceiver extends BroadcastReceiver {
  @Override
  public void onReceive(Context context, Intent intent) {// 重载方法
    String action = intent.getAction();
    if (action != null) {
      MainPlayer.infoLog("action: " + action);// TODO debug
      switch (action) {
        // 有线耳机状态改变
        case Intent.ACTION_HEADSET_PLUG:
          int mediaState = intent.getIntExtra("state", 0);// 判断插拔

          // 蓝牙连接状态改变
        case BluetoothAdapter.ACTION_CONNECTION_STATE_CHANGED:// 安卓端主动改变蓝牙状态
          int bluetoothState = intent.getIntExtra(BluetoothAdapter.EXTRA_STATE, 0);// 获取蓝牙状态

          // 接收蓝牙/媒体按键信号
        case Intent.ACTION_MEDIA_BUTTON:
          KeyEvent keyEvent = (KeyEvent) intent.getParcelableExtra(Intent.EXTRA_KEY_EVENT);// 获取键码
      }
    }
  }

  // receiver注册函数
  public void registerReceiver(Context context) {
    AudioManager audioManager = (AudioManager) context.getSystemService(Context.AUDIO_SERVICE);
    ComponentName name = new ComponentName(context.getPackageName(), MediaReceiver.class.getName());
    audioManager.registerMediaButtonEventReceiver(name);
  }

  public void unregisterReceiver(Context context){
    AudioManager audioManager = (AudioManager) context.getSystemService(Context.AUDIO_SERVICE);
    ComponentName name = new ComponentName(context.getPackageName(), MediaReceiver.class.getName());
    audioManager.unregisterMediaButtonEventReceiver(name);
  }
}

注意点:

注册函数的函数名随意,可以在onCreate或onResume等函数中调用注册函数
BroadcastReceiver子类必须要有无参的构造方法,否则会直接崩溃

修改AndroidManifest.xml

父节点为application,android:name要和BroadcastReceiver的子类名相同,priority可以不要

<receiver android:name=".MediaReceiver">
  <intent-filter android:priority="1000">
    <action android:name="android.intent.action.MEDIA_BUTTON"></action>
  </intent-filter>
</receiver>

初始化MediaReceiver

bluetoothAdapter = BluetoothAdapter.getDefaultAdapter();// 获取蓝牙适配器
receiver = new MediaReceiver(this);// 接收蓝牙信号

IntentFilter intentFilter = new IntentFilter();

intentFilter.addAction(BluetoothAdapter.ACTION_STATE_CHANGED);// 监视蓝牙设备与APP连接的状态
intentFilter.addAction(BluetoothDevice.ACTION_ACL_DISCONNECTED);
intentFilter.addAction(BluetoothDevice.ACTION_ACL_CONNECTED);
intentFilter.addAction(Intent.ACTION_HEADSET_PLUG);// 监听有线耳机的插拔
intentFilter.addAction(Intent.ACTION_MEDIA_BUTTON);// TODO

registerReceiver(this.receiver, intentFilter);// 注册广播
receiver.registerReceiver(this);// 初始化广播

adb

华为手机配置adb:*#*#2846579#*#*->后台设置->usb端口设置->生产模式

adb devices
adb tcpip 5555
# 拔掉数据线
adb connect 手机ip

若安卓设备显示offline,可能是由于adb版本过低

蓝牙连接管理

无需在AndroidManifest里注册

蓝牙连接

Method createBond = device.getClass().getMethod("createBond");
            createBond.setAccessible(true);
            result = (Boolean) createBond.invoke(device);

注意区分已经配对的设备
特殊的蓝牙设备仍未解决

状态栏部件

创建

简书:notification channel

可使用NotificationCompat或Notification,注意常量取值

NotificationManager notificationManager = null;

if (Build.VERSION.SDK_INT >= Build.VERSION_CODES.O) {
  notificationManager  = getSystemService(NotificationManager.class);
  CharSequence name = "fuck";// 通知渠道名称
  String description = "shit";
  String id = "111";
  NotificationChannel channel = new NotificationChannel(id, name, NotificationManager.IMPORTANCE_HIGH);
  channel.setDescription(description);
  notificationManager.createNotificationChannel(channel);
}

NotificationCompat.Builder builder = new NotificationCompat.Builder(MainActivity.this, id)
  .setSmallIcon(R.drawable.ic_launcher_background)
  // .setPriority(NotificationCompat.PRIORITY_MAX)
  .setVisibility(NotificationCompat.VISIBILITY_PUBLIC);

显示

首先保证系统更新并能够支持notification category
保证给应用程序提供锁屏通知权限

`startForeground`

常驻通知栏

for (int i = 0; i < 10; i ++) {
  stopForeground(true);
  Thread.sleep(500);
  startForeground(10, builder.build());
}

在mainifest节点下增加权限

<uses-permission android:name="android.permission.FOREGROUND_SERVICE" />

清除通知不要使用deleteNotificationChannel,否则无法控制音效/震动,使用stopForeground

`notify`

可以被作为通知清除

for (int i = 0; i < 10; i ++) {
  notificationManager.cancel(0);
  Thread.sleep(500);
  notificationManager.notify(0, builder.build());
}

注意channel的id和Builder的id要一致

通信

注意不同intent要使用不同的requestCode

切换到MainActivity,MainActivity要使用singleTask

Intent intent = new Intent(this, MusicList.class);
remoteViews.setOnClickPendingIntent(R.id.button_open, PendingIntent.getActivity(this, 6, intent, 0));

使用空pendingIntent来防止点击通知会消失

锁屏通知

只能够从系统中手动打开权限

事件	`intent`
亮屏	`Intent.ACTION_SCREEN_ON`
关屏	`Intent.ACTION_SCREEN_OFF`
解锁	`Intent.ACTION_USER_PRESENT`

桌面部件

在进程完全被杀死后通过widget启动app

PendingIntent.getActivity()/startActivity()
PendingIntent.getForegroundService()/startForegroundService(),不要使用Service

`Editor`开发笔记

获取读写权限

`AndroidManifest`

<!-- manifest节点下  -->
<uses-permission android:name="android.permission.WRITE_EXTERNAL_STORAGE"/>
<uses-permission android:name="android.permission.READ_EXTERNAL_STORAGE"/>

`Activity`

String permission = "android.permission.WRITE_EXTERNAL_STORAGE";
int check_result = ActivityCompat.checkSelfPermission(this, permission);// `允许`返回0,`拒绝`返回-1
if (check_result != PackageManager.PERMISSION_GRANTED) {// 没有`写`权限
  ActivityCompat.requestPermissions(this, new String[]{permission}, 1);// 获取`写`权限
}

关联文件类型

文本文件

<intent-filter android:scheme="http"
  tools:ignore="AppLinkUrlError">
  <action android:name="android.intent.action.VIEW"/>
  <category android:name="android.intent.category.DEFAULT"/>
  <data android:mimeType="text/*"/>
</intent-filter>

修改默认`Toast`

static public void info(Context context, String log) {
  Toast toast =  Toast.makeText(context, log, Toast.LENGTH_SHORT);
  View view = toast.getView();
  view.setBackgroundResource(R.drawable.toast);
  TextView textView = view.findViewById(android.R.id.message);
  textView.setTextColor(Color.rgb(0xff, 0xff, 0xff));
  toast.show();
}

由外部打开文件

Intent intent = getIntent();
String action = intent.getAction();// 判断本activity启动的方式
if (action.equals("android.intent.action.VIEW")) {// 由其他软件打开本软件
}

控制`activity`数目

<activity android:name=".Editor"
            android:launchMode="singleTask">

获取根`view`

View view = getWindow().getDecorView().findViewById(android.R.id.content);

数据保存

`SharedPreferences`

SharedPreferences:基于xml的键值对,存储于/data/data/应用程序包/shared_prefs

提示框/窗口

`Dialog`

参考

protected void onCreate(Bundle savedInstanceState) {
  super.onCreate(savedInstanceState);
  setContentView(R.layout.save_layout);

  // 初始化`保存`按钮
  yes.setOnClickListener(new View.OnClickListener() {//
    });

  // 初始化`取消`按钮
  cancel.setOnClickListener(new View.OnClickListener() {
    });

  // 初始化`删除`按钮
  no.setOnClickListener(new View.OnClickListener() {
    });
}

private void initButton() {
  // 初始化按钮
  yes = findViewById(R.id.yes_button);
  cancel = findViewById(R.id.cancel_button);
  no = findViewById(R.id.no_button);
}

myWindow = new MyWindow(MainActivity.this, R.style.save_style);
myWindow.setCanceledOnTouchOutside(false);
myWindow.setOnDismissListener(new DialogInterface.OnDismissListener() {
});
myWindow.show();// TODO 获取点击结果

`PopupWindow`

public class MyWindow extends PopupWindow {
  public Button yes;
  public Button cancel;
  public Button no;
  public int result;

  public MyWindow(Context context, View view) {
    super(context);
    this.setContentView(LayoutInflater.from(context).inflate(R.layout.manager_layout, null));
    // this.setOutsideTouchable(false);
    this.setFocusable(true);// 否则无法进行edittext输入

    this.showAsDropDown(view);
    this.setSoftInputMode(WindowManager.LayoutParams.SOFT_INPUT_ADJUST_RESIZE);
    this.setInputMethodMode(PopupWindow.INPUT_METHOD_NEEDED);
  }
}

响应键盘:this.setFocusable(true);,否则无法进行EditText输入

`DialogFragment`

参考

public class MyWindow extends DialogFragment {
  @Override
    public View onCreateView(LayoutInflater inflater, ViewGroup container, Bundle savedInstanceState) {
      View view = inflater.inflate(R.layout.manager_layout, container);
      getDialog().getWindow().setBackgroundDrawable(new ColorDrawable(0x00000000));
      return view;
    }

  @Override
    public void onCreate(Bundle savedInstanceState) {
      super.onCreate(savedInstanceState);
      setStyle(STYLE_NO_FRAME, android.R.style.Theme);
    }
}

myWindow = new MyWindow();
myWindow.show(getSupportFragmentManager(), "edit");

过期内容

调用系统文件浏览器

1.绑定点击事件

Intent intent = new Intent(Intent.ACTION_GET_CONTENT);
intent.setType("*/*");// 所有类型文件
intent.addCategory(Intent.CATEGORY_OPENABLE);
startActivityForResult(intent, 1);

2.根据`requestCode`接收数据

@Override
protected void onActivityResult(int requestCode, int resultCode, Intent data) {
  if (resultCode == Activity.RESULT_OK) {
    if (requestCode == 1) {// `打开`按钮
        ...
      }
    }
  }
}

Intent.ACTION_GET_CONTENT:用于调用系统程序,比如一个打开一个文件的时候会提示你用哪个软件打开
Intent.setType():设置默认打开格式,如"video/*","audio/amr"

调用相册

Intent intent = new Intent(Intent.ACTION_PICK);//intent  action属性
intent.setType("image/*");
startActivityForResult(intent, 2);

通用框架修改

`drawable`

添加button和dialog

`values`

删掉styles,修改colors,添加styles_button(按钮)和styles_tab(工具栏)

`manifests`

增加权限,删除label,增加android:launchMode="singleTask"

远程控制

2019-02-17

本地局域网`ssh`

Linux

准备

sudo apt-get install openssh-server
sudo apt-get install net-tools
sudo ifconfig

配置文件(修改ssh端口号):/etc/ssh/sshd_config
检查

netstat -tlp

ps -e | grep ssh

运行图形界面程序

ssh -X lynx@192.168.1.100

mac

设置$\to$共享$\to$远程登录

termux

pkg install openssh
sshd
sshd -p 22222
whoami
passwd

windows

安装freeSSHd
Users$\to$Add,设置密码
开启Shell等
powershell:ipconfig

windows真他妈没卵用

外网`ssh`访问公网ip

必须保证wlan分配的ip为公网ip:ip138.com上与上网设置中的ip地址要一致

Linux

配置路由(tp-link)

在192.186.1.1安装虚拟服务器应用
端口映射

外部端口	内部端口	ip地址	协议类型
用于外网访问的端口	进程的实际端口,ssh默认为22	局域网ip	`ALL`

连接内网

ubuntu查看外网ip

TODO

curl ifconfig.me

外网访问私网ip

ngrok:内网穿透软件

注册ngrok账号
./ngrok authtoken ***
./ngrok tcp 80(例)
另一台电脑./ssh -X lynx@***.ngrok.io -p ***,端口在Status查看

nat123:TODO
teamviewer

Linux从0开始配置

2019-01-20

git

全局设置

git config --global user.name "Lynx" # your student ID and name
git config --global user.email "1197225628@qq.com"   # your email
git config --global core.editor vim                 # your favorite editor
git config --global color.ui true

powerline

python安装pip

菜鸟教程

curl https://bootstrap.pypa.io/get-pip.py -o get-pip.py
sudo python get-pip.py
# or
sudo apt-get install python3-pip

pip安装powerline

详细

pip install powerline-status
pip3 install powerline-status

pip安装powerline-gitstatus

github

sudo apt install powerline-gitstatus
# or
pip install powerline-gitstatus
pip3 install powerline-gitstatus

复制配置文件

git clone https://github.com/aaaatrox/powerline.git
mv powerline .config/

安装powerline字体

详细

git clone https://github.com/powerline/fonts.git
cd fonts
./install.sh

修改终端字体设置
找不到powerline-config
1. mkdir $HOME/.local/lib/python3.6/site-packages/scripts/ if not exists
2. Find where powerline-config locates. For example $HOME/.local/bin/powerline-config
3. cp $HOME/.local/bin/powerline* $HOME/.local/lib/python3.6/site-packages/scripts/.

# export PATH=$PATH:/home/lynx/.local/bin/
# export PATH=$pathtopowerline-config:$PATH

vim

转移.vimrc,修改powerline相对路径

安装支持python的vim(查看vim --version),详细:

macOS

brew install vim --with-python

Linux

sudo apt install vim-gnome

如果需要使用系统剪切板功能,必须安装vim-gnome

复制插件(branch clean)

git clone https://github.com/aaaatrox/my_vim.git
mv my_vim .vim

注意:
- ubuntu默认只装了vi而不是vim
- 如果出现无法写入.vim/view的问题,直接把文件夹删掉
~~插件包含:~~推荐插件
- vim的gitdiff标识vim-gitgutter
- 彩虹括号升级版rainbow
- 插件管理器vim-plug
- 魔改自tokyo-metro的配色my.vim
- 手写的仿sublime补全插件vim-sb-complete

修改rtp

zsh

安装zsh

wget安装oh-my-zsh

sh -c "$(wget https://raw.github.com/robbyrussell/oh-my-zsh/master/tools/install.sh -O -)"

转移.zshrc,修改powerline相对路径
安装zsh-syntax-highlighting

详细
- macOS
brew install zsh-syntax-highlighting
然后将source /usr/local/share/zsh-syntax-highlighting/zsh-syntax-highlighting.zsh加到.zshrc
- oh-my-zsh
git clone https://github.com/zsh-users/zsh-syntax-highlighting.git
mv zsh-syntax-highlighting ~/zsh-syntax-highlighting
然后将source $HOME/zsh-syntax-highlighting/zsh-syntax-highlighting.git加到.zshrc

openCV安装

2019-10-21

AS和cmake笔记

android的cpu架构

android查看cpu架构(termux)

cat /proc/cpuinfo

AArch32是ARMv7架构的一种执行状态
AArch64是ARMv8架构的一种执行状态
- 参考
- 参考
64位ARMv8包含上面两种状态
- 参考
- 知乎
- 知乎

cmake在AS中的使用

不要把mk和cmake两种方法混淆

输出控制(`message`)

(TODO)如果想直接看到打印信息,使用WARNING以上的级别进行打印

message(WARNING "fuck")
- 在Build->Build Output->CMake warnings查看
- 在Build->Build Output->Toggle View查看

Android

Android Studio版本为3.5

`OpenCV for Android 3.x`:只使用`java`模块

参考:CSDN,示例:压缩图片

File->New->Import Module->选择opencv文件夹下的sdk/java文件夹,此时Android Studio会自动加载Module name
File->Project Structure->Dependencies->选择app->添加Module Dependency->选择opencv
将opencv文件夹下的sdk/native/libs下自己手机cpu对应的架构文件夹复制到app/libs下
将opencv模块的build.gradle的complieSdkVersion,buildToolVersion,minSdkVersion,targetSdkVersion改成和app的build.gradle一样

在app的build.gradle的android节点下添加

sourceSets {
  main {
    jni.srcDirs = []
    jniLibs.srcDirs = ['libs']
  }
}

然后点击sync now

在使用opencv前进行初始化

static {
  if (!OpenCVLoader.initDebug()) {
    ...
  }
}

常见问题

Caused by: CvException [org.opencv.core.CvException: OpenCV(4.1.1) /build/master_pack-android/opencv/modules/java/generator/src/cpp/utils.cpp:101: error: (-215:Assertion failed)

在Mat与Bitmap互转的时候长宽设置不对

`OpenCV for Android 3.x`:使用`native`模块

方法一

CMakeLists.txt编写

在CMakeLists.txt中确定两个关键路径

/sdk/native/jni/include:头文件位置
/sdk/native/libs/${ANDROID_ABI}/libopencv_java3.so:库位置

cmake_minimum_required(VERSION 3.4.1)

#1
set(opencv_version OpenCV4-android-sdk)
set(opencv_lib libopencv_java4.so)

#2
include_directories(/home/lynx/fuck_mount/Android/Proj/${opencv_version}/sdk/native/jni/include)
add_library(fuck SHARED IMPORTED)
  set_target_properties(fuck PROPERTIES IMPORTED_LOCATION
      /home/lynx/fuck_mount/Android/Proj/${opencv_version}/sdk/native/libs/${ANDROID_ABI}/${opencv_lib})


add_library(保持原样)

find_library(保持原样)

target_link_libraries(
        native-lib

        #3
        fuck

        ${log-lib})

修改app的build.gradle

在android节点下插入

sourceSets {
  main {
    jniLibs.srcDirs = ['/home/lynx/fuck_mount/Android/Proj/OpenCV4-android-sdk/sdk/native/libs']
  }
}

方法二

参考:CSDN

还没有成功

CMakeLists.txt编写

在CMakeLists.txt中确定一个关键路径

/sdk/native/jni/include:头文件位置

cmake_minimum_required(VERSION 3.4.1)

#1
set(opencv_version OpenCV4-android-sdk)
set(opencv_lib libopencv_java4.so)

#2
set(OpenCV_STATIC ON)
set(OpenCV_DIR /home/lynx/fuck_mount/Android/Proj/${opencv_version}/sdk/native/jni)
  find_package(OpenCV REQUIRED)
if (OpenCV_FOUND)
  message(WARNING "opencv libs: ${OpenCV_LIBS}")
else (OpenCV_FOUND)
  message(WARNING "opencv not found")
endif(OpenCV_FOUND)

add_library(保持原样)

find_library(保持原样)

target_link_libraries(
        native-lib

        ${log-lib}

        #3
        ${OpenCV_LIBS})

常见问题

java.lang.UnsatisfiedLinkError: dlopen failed: library "libopencv_java3.so" not found

这是由于忘记了上面的第2步.Android Studio默认的jni路径为app/src/main/jniLibs,除了在CMakeLists.txt中导入opencv的库以外还需要二选一

将对应版本opencv的库(libs/下一级的各个${ANDROID_ABI}文件夹)移动到jniLibs下
在build.gradle中修改默认jni路径(见上面第2步)

各种undefined reference to *

如std::ios_base::Init::Init()等

未解决

undefined reference to `AndroidBitmap_getInfo'

各类AndroidBitmap的问题

在CMakeLists.txt增加

target_link_libraries(
        # TODO 解决 AndroidBitmap 报错
        jnigraphics)

参考:CSDN,这是一个很小的库,展示一个稳定的,基于C语言的接口,使本机代码安全地访问Java对象的像素缓冲区的位图

`OpenCV for Android 4.x`:使用`native`模块

方法一

同3.x版本的方法一

常见问题

java.lang.UnsatisfiedLinkError: dlopen failed: library "libc++_shared.so" not found

stackoverflow

(不确定的解决方法)在app的gradle中修改

externalNativeBuild {
  cmake {
    cppFlags ""
      arguments "-DANDROID_STL=c++_shared"
  }
}

不要使用gnustl_shared或gnustl_static,已经过时

java.lang.UnsatisfiedLinkError: dlopen failed: library "libopencv_java4.so" not found

解决方案同3.x版本

`OpenCV for Android 4.x`:使用`java`+`native`模块

参考:CSDN

加载native模块
File->New->Import Module->选择opencv文件夹下的sdk/java文件夹,自己定义模块的名字
修改模块的gradle文件

// 将原来的application改成library
apply plugin: 'com.android.library'

android {
  // 将版本信息改得和`app`的`build.gradle`一样
  compileSdkVersion 29
  buildToolsVersion "29.0.2"
  defaultConfig {
    // 删除applicationId
    minSdkVersion 15
    targetSdkVersion 29
    versionCode 1
    versionName "1.0"
    testInstrumentationRunner "androidx.test.runner.AndroidJUnitRunner"
  }
  // 不改动
  buildTypes {
    release {
      minifyEnabled false
        proguardFiles getDefaultProguardFile('proguard-android.txt'), 'proguard-rules.txt'
    }
  }
}

(重复)修改app的gradle文件,加载native/lib模块

`javacv`(使用不完整`OpenCV 4.1.0`)

不同导入方法,import的class位置可能不同

`opencv`部分功能的初始化

github原文

Loader.load(opencv_java.class);// 不能直接放在class开头

使用远程导入

app的build.gradle示例(最外节点)

ext {
    versions = [
            'javacv': '1.4.4',
            'ffmpeg': '4.1',
            'opencv': '4.0.1'
    ]
}

dependencies {
    ...
    implementation(group: 'org.bytedeco', name: 'javacv-platform', version: versions.javacv) {
      exclude group: 'org.bytedeco.javacpp-presets'
    }
    implementation group: 'org.bytedeco.javacpp-presets', name: 'ffmpeg', version: "${versions.ffmpeg}-${versions.javacv}"
    implementation group: 'org.bytedeco.javacpp-presets', name: 'ffmpeg', version: "${versions.ffmpeg}-${versions.javacv}", classifier: 'android-arm'
    implementation group: 'org.bytedeco.javacpp-presets', name: 'ffmpeg', version: "${versions.ffmpeg}-${versions.javacv}", classifier: 'android-arm64'
    implementation group: 'org.bytedeco.javacpp-presets', name: 'opencv', version: "${versions.opencv}-${versions.javacv}"
    implementation group: 'org.bytedeco.javacpp-presets', name: 'opencv', version: "${versions.opencv}-${versions.javacv}", classifier: 'android-arm'
    implementation group: 'org.bytedeco.javacpp-presets', name: 'opencv', version: "${versions.opencv}-${versions.javacv}", classifier: 'android-arm64'
}

作为`lib`导入

根据手机具体的cpu架构进行导入

app的build.gradle

dependencies {
    implementation fileTree(dir: 'libs', include: ['*.jar'])
}

将文件(视具体情况)

javacpp.jar
javacv.jar
openblas.jar
openblas-android-arm64.jar
opencv.jar
opencv-android-arm64.jar
复制到app/libs/文件夹里

常见错误

cpu架构错误/缺少(需添加-android-arm之类的库)

2019-10-27 16:01:32.439 29256-29322/? E/AndroidRuntime: FATAL EXCEPTION: AsyncTask #1
    Process: com.github.crazyorr.ffmpegrecorder, PID: 29256
    java.lang.RuntimeException: An error occurred while executing doInBackground()

没有对opencv初始化

2019-10-27 16:00:43.930 28933-28933/? E/AndroidRuntime: FATAL EXCEPTION: main
    Process: com.example.javacv, PID: 28933
    java.lang.UnsatisfiedLinkError: No implementation found for long org.opencv.core.Mat.n_Mat() (tried Java_org_opencv_core_Mat_n_1Mat and Java_org_opencv_core_Mat_n_1Mat__)

缺少openblas的相关jar库

2019-10-27 15:59:23.158 28618-28618/? E/AndroidRuntime: FATAL EXCEPTION: main
    Process: com.example.javacv, PID: 28618
    java.lang.NoClassDefFoundError: Failed resolution of: Lorg/bytedeco/openblas/presets/openblas;

`OpenCV 4.x` source code

参考:CSDN

修改参数

Android Studio的sdk下的ndk:ndk/build/cmake/android.toolchain.cmake(第112行)

elseif(ANDROID_TOOLCHAIN_NAME MATCHES "-[0-9].[0-9]$")
  set(ANDROID_TOOLCHAIN clang) # 将gcc改成clang
endif()

opencv 4.x源码:/platforms/android/build_sdk.py(第113行)

self.cmake_vars = dict(
    ANDROID_STL="c++_static", # change `gnustl_static` to `c++_static` or `c++_shared`
    ANDROID_ABI=self.name,
    ANDROID_PLATFORM_ID=platform_id,
)

opencv 4.x源码:/CMakeLists.txt(第426行和429行)(可以根据需要修改)

# OCV_OPTION(BUILD_SHARED_LIBS        "Build shared libraries (.dll/.so) instead of static ones (.lib/.a)" NOT (ANDROID OR APPLE_FRAMEWORK) )
OCV_OPTION(BUILD_SHARED_LIBS        "Build shared libraries (.dll/.so) instead of static ones (.lib/.a)" ON ) # 生成动态库
OCV_OPTION(BUILD_opencv_apps        "Build utility applications (used for example to train classifiers)" (NOT ANDROID AND NOT WINRT) IF (NOT APPLE_FRAMEWORK) )
OCV_OPTION(BUILD_opencv_js          "Build JavaScript bindings by Emscripten" OFF )
OCV_OPTION(BUILD_ANDROID_PROJECTS   "Build Android projects providing .apk files" OFF )
# OCV_OPTION(BUILD_ANDROID_PROJECTS   "Build Android projects providing .apk files" ON  IF ANDROID )

配置JAVA_HOME

使用Android Studio的JDK位置

export JAVA_HOME=/home/lynx/fuck_mount/AS/jre

执行platforms/android/build_sdk.py,完成编译

./build_sdk.py --ndk-path {ndk路径} --sdk_path {android sdk路径} {目标位置} {opencv源码位置}
# example
/home/lynx/fuck_mount/opencv_4_1_0/opencv-4.1.0/platforms/android/build_sdk.py --ndk_path /home/lynx/fuck_mount/Android/SDK/ndk/18.1.5063045 --sdk_path /home/lynx/fuck_mount/Android/SDK /home/lynx/fuck_mount/opencv_4_1_0/android_build /home/lynx/fuck_mount/opencv_4_1_0/opencv-4.1.0

sdk-path:Android Studio的SDK目录
ndk-path:Android Studio的SDK目录下ndk/{ndk版本号文件}

额外说明

不需要额外安装的软件:jdk,ninja-build,ndk.直接使用android studio的即可
不需要安装的软件:ant,ccache

目前还没能成功编译android project

能够混合使用:

OpenCV 3.x的java库(配置见上)
TODO

常见问题

java.lang.UnsatisfiedLinkError: dalvik.system.PathClassLoader[DexPathList[[zip file "/data/app/com.example.stitch-sPWgBONIqUrdX9XLB1OY6w==/base.apk"],nativeLibraryDirectories=[/data/app/com.example.stitch-sPWgBONIqUrdX9XLB1OY6w==/lib/arm64, /data/app/com.example.stitch-sPWgBONIqUrdX9XLB1OY6w==/base.apk!/lib/arm64-v8a, /system/lib64, /product/lib64]]] couldn't find "libnative-lib.so"

缺少相应ABI的so库(目前计时在gradle里加入abiFilters也没有用),上述报错是因为没有编译全ABI.ABI配置:opencv-4.x/platforms/android/ndk-18-api-level-21.config.py

Linux

`OpenCV` source code `3.x`(`3.4.7`)

gui安装

和4.x一样

常见问题

fatal error: Eigen/Core: 没有那个文件或目录``#include <Eigen/Core>
1. 修改WITH_EIGEN=OFF
2. (或)
  - 先保证安装eigen:sudo apt install libeigen3-dev
  - 添加EIGEN_INCLUDE_PATH=/usr/include/eigen3(视具体情况)
ippicv_linux_20141027.tgz下载失败

CMake Error at 3rdparty/ippicv/downloader.cmake:71 (file):
  file DOWNLOAD HASH mismatch

    for file: [/home/lynx/fuck_mount/opencv_3_0_0/opencv/3rdparty/ippicv/downloads/linux-8b449a536a2157bcad08a2b9f266828b/ippicv_linux_20141027.tgz]
      expected hash: [8b449a536a2157bcad08a2b9f266828b]
        actual hash: [5c4f36bf7b2421d52289f0297ba1406f]
             status: [28;"Timeout was reached"]

TODO

`OpenCV` source code `4.x`(`4.1.0`)

依赖包

sudo apt install libgtk2.0-dev pkg-config

命令行安装(TODO)

cmake

cd {生成makefile的位置}
cmake {source的位置}

make

cd {生成makefile的位置}
make

make install

make install {安装的位置}

gui安装

参考:CSDN

安装cmake-gui

sudo apt install cmake-gui

启动cmake-gui

cd {build二进制文件的目录}
cmake-gui {opencv源代码}

Configure->Unix Makefiles:Use default native compilers->finish
狂点Configure知道没有红色区域
赋值

变量名	赋值
`CMAKE_BUILD_TYPE`	`Release`
`CMAKE_INSTALL_PREFIX`	{自己定的`cmake_install`路径}
`OPENCV_GENERATE_PKGCONFIG`	勾选
`OPENCV_EXTRA_MODULES_PATH`	`{opencv-contrib}源代码/modules`
`BUILD_EXAMPLES`	勾选

狂点Configure
Generate,等到Generating done
在源代码路径make

sudo make -j4 # 具体看有多少cpu
cat /proc/cpuinfo | grep "processor" | wc -l # 查看cpu个数
sudo make install

配置opencv4.pc(2选1)
- 修改PKG_CONFIG_PATH:增加{你cmake_install的路径}/lib/(opencv4.pc所在的文件夹路径)
- (TODO,没试过)复制opencv4.pc到/usr/lib/pkgconfig
配置库路径,(新建)/etc/ld.so.conf.d/opencv.conf

{你cmake_install路径}/lib/ # 自己的lib路径

sudo ldconfig

编译测试

如果是opencv.pc将opencv4改成opencv

pkg-config --modversion opencv4
g++ a.cpp `pkg-config --cflags --libs opencv4` -o test && ./test

常见问题

在其他项目中用CMake导入OpenCV模块:

find_package(OpenCV REQUIRED)
include_directories(${OpenCV_INCLUDE_DIRS})

之后cmake出现By not providing "FindOpenCV.cmake" in CMAKE_MODULE_PATH ...:

这是由于没有设置环境变量OpenCV_DIR,设置为OpenCV编译后的目录下含有OpenCVConfig.cmake的对应路径

mysql笔记

2019-11-09

通用

建表

create table if not exists customers(
    cid char(4) not null,
    cname char(20) not null,
    city char(20),
    discnt real,
    primary key ( cid )
) character set = utf8 -- 支持中文;

修改并查看注释(`comment`)

alter table customers
change column cid
cid char(4) not null comment '编号',
change column cname
cname char(20) not null comment '姓名',
change column city
city char(20) comment '城市',
change column discnt
discnt real comment '折扣';
show full columns from customers;

`insert`去重

ignore

insert ignore into table (column)
 values
 ...

on duplicate key update

TODO

replace into

TODO

更新表数据

update table_name set item="shit" where fuck="fuck";

每组前n

参考

计算时间差

SELECT TIMESTAMPDIFF(MONTH,'2009-10-01','2009-09-01');
SELECT TIMESTAMPDIFF(MONTH,'2009-10-01','2009-09-01') as a;

其中MONTH部分可以更改为

SECOND
MINUTE
HOUR
DAY
MONTH
YEAR

其他

添加用户

insert

use mysql
insert into user ( Host, User, Select_priv, Insert_priv, Update_priv, Delete_priv, Create_priv, Drop_priv, Reload_priv, Shutdown_priv, Process_priv, File_priv, Grant_priv, References_priv, Index_priv, Alter_priv, Show_db_priv, Super_priv, Create_tmp_table_priv, Lock_tables_priv, Execute_priv, Repl_slave_priv, Repl_client_priv, Create_view_priv, Show_view_priv, Create_routine_priv, Alter_routine_priv, Create_user_priv, Event_priv, Trigger_priv, Create_tablespace_priv, ssl_type, ssl_cipher, x509_issuer, x509_subject, max_questions, max_updates, max_connections, max_user_connections, plugin, authentication_string, password_expired, password_last_changed, password_lifetime, account_locked )
  values
  ('localhost', 'niabie', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', '', '', '', '', 0, 0, 0, 0, 'mysql_native_password', password(''), 'N', '2019-11-07 15:17:00', null, 'N');
flush privileges;# 更新

用户具有创建数据库等的权限

create

参考

create user lynx;
update user set Host='localhost', authentication_string=password('1111') where User='lynx';
flush privileges;# 更新
grant all on database.table to 'lynx'@'localhost';# 分配database的table权限给用户
show grants for lynx@localhost;# 显示用户权限

用户没有创建数据库的权限

其他

创建数据库并选择

create database homework3;
show databases;
use homework3;
show tables;

查看版本等

select version();
select now();
select user();

查看端口

show variables like 'port';

gcc笔记

2019-04-03

参数

-ldl:libdl

the dynamic linking library,如果程序中使用dlopen,dlsym,dlclose,dlerror**加载动态库,需要设置选项-ldl

查看可执行文件以来的动态链接库

ldd a.out

添加库/头文件

CSDN

显示系统信息

uname -r

安装内核头文件

sudo apt install linux-headers-5.0.0-36-generic # 你的版本号

定位头文件

locate slab.h

查找头文件

sudo apt install apt-file
sudo apt-file update
apt-file search ".h"

jni笔记

2019-11-21

`jni`与`java`间的交互

`jni`获取/修改`jobject`成员

参考:CSDN

`java`与`c`变量转换

jstring->char *:stackoverflow

JNIEXPORT void JNICALL Java_ClassName_MethodName(JNIEnv *env, jobject obj, jstring javaString)
{
  const char *nativeString = (*env)->GetStringUTFChars(env, javaString, 0);
  (*env)->ReleaseStringUTFChars(env, javaString, nativeString);
}

java`String[]`->c

参考:CSDN

public native void sendString(String[] imgPaths);// 函数声明

JNIEXPORT void JNICALL
Java_com_example_stitch_MainActivity_sendString(
    JNIEnv *env,
    jobject thiz,
    jobjectArray imgPaths) {
  // 获取String数组长度
  jsize str_len = env->GetArrayLength(imgPaths);

  for (int i = 0; i < str_len; i ++) {
    jstring tmp = (jstring) env->GetObjectArrayElement(imgPaths, i);
    const char *img_path = env->GetStringUTFChars(tmp, 0);

    LOG("img[%d]: %s", i, img_path);
  }
}

java`Mat`->c`Mat`

public native void findPoint(String imgPath, long result);// 函数声明

... {// 函数调用
  findPoint(appPath + "/img0.png", matBGR.getNativeObjAddr());
}

extern "C"
JNIEXPORT void JNICALL
Java_com_example_stitch_MainActivity_findPoint(
        JNIEnv *env,
        jobject thiz,
        jstring imgPath,
        jlong result) {
  *(Mat *)result = mat.clone();// 一定要用clone()
  umat.copyTo(*(Mat *)result);
}

`jni`的opencv`mat`与java`Bitmap`互转

参考:简书

`jni`新建图片返回到`java`

TODO

参考
 stackoverflow

cmake笔记

2019-11-25

变量

命令行参数传递

参考:CSDN

环境变量

Android Studio笔记

2019-09-02

安装

官方文档

Linux

运行程序:android-studio/bin/studio.sh
64位机器需要安装32位库

sudo apt-get install libc6:i386 libncurses5:i386 libstdc++6:i386 lib32z1 libbz2-1.0:i386

向前/后跳转:alt+shift+left/right

汉化

教程

汉化包

其他(TODO)

windows

配置文件夹位置:C:/Users/lynx/.AndroidStudio3.5

增加虚拟设备:Tools->AVD Manager

android device monitor位置:E:\Android\Sdk\tools\monitor.bat

memory monitor 打开:Run->Profiler

解决网络问题:Configure->Setting->System Setting->HTTP Proxy->Auto-detect proxy settings

布局编辑器打开:打开一个xml文件->底部选择Design

Linux

清除缓存:Build->Clear Project

常见错误

Android resource linking failed

查看app的gradle有没有缺少implementation

stitch笔记

2019-11-17

代码分析

特征点查找

默认使用orb算法,默认情况下还能够支持akaze算法.在安装了扩展模块后还能选择surf和sift算法

computeImageFeatures

特征点匹配

匹配方法的选择

homography

默认调用BestOf2NearestMatcher,可选BestOf2NearestRangeMatcher

affine

调用AffineBestOf2NearestMatcher.使用该方法进行匹配时会多丢弃一些图片

舍弃认为不属于同一张全景图的图片

leaveBiggestComponent

相机参数评估

`estimate::estimate`

AffineBasedEstimator
默认HomographyBasedEstimator

焦距评估:当评估计算得到多个焦距f时,可取这些f的中位数作为所有相机的焦距

计算最大生成树:以中心节点的图像为基准,计算其他图像与该图像的旋转矩阵

`BundleAdjusterBase::estimate`

基于以上方法,我们得到了相机的内外参数,但这样得到的参数忽略了多个图像间的约束,而且会产生累计误差.这时,我们就需要用到光束平差法(Bundle Adjustment)来精确化相机参数

BundleAdjusterReproj:光束平差法的重映射方法
默认BundleAdjusterRay:光束平差法的射线发散方法
BundleAdjusterAffinePartial

细化相机参数

波形矫正

光束平差法会引起波形效应,即拼接的图像会呈现蛇形分布,这是因为真实拍摄相片时不大可能都保持水平而不倾斜的

waveCorrect

图像投影变换

PlaneWarper
AffineWarper
CylindricalWarper:柱面
默认SphericalWarper:球面
FisheyeWarper
StereographicWarper
还有一堆

曝光补偿

对每幅图像进行曝光补偿,来使所有图像具有相同的曝光程度

ExposureCompensator

寻找接缝线

重叠部分最相似的像素的连线

接缝线有三个限制条件

如果重叠区域是宽大于高,则接缝是横向走向的,而如果重叠区域是宽小于高,则接缝是纵向走向的.所以要保证接缝线要有一定的长度
如果是横向的接缝,则不允许有绝对垂直的接缝线,而如果是纵向的接缝,则不允许有绝对水平的接缝线
三是重叠区域是矩形,接缝线从矩形的一边出发,必须到达与该边平行的另一边结束。

逐点法,动态规划法和图割法

图片融合

羽化

多频段融合

参数说明

matcher:匹配方式?
rangewidth:限制图片匹配的数目?
ba:拼接图像时的cost函数?
warp:投影变换
wave_correct:波形矫正
seam:寻找接缝线的方法
blend:图像融合方式

vscode笔记

2019-04-12

插件说明

插件位置

Linux:~/.vscode/

部分插件使用

`C/C++ IntelliSense`

Intelli Sense Cache Size(TODO)

软件设置

快捷键

Linux

从定义处跳回:ctrl+alt+-

settings.json

Linux:~/.config/Code/User/

快捷键设定(settings.json)

列选快捷键:"editor.multiCursorModifier":"alt"