2023年数据库笔记.docx

lec1 数据库概述
1.数据data：事实或观测的结果，是对客观事物的逻辑归纳，是用于表达客观事物的未经加工的的原始素材
数据库Database：Data + Base，大的结构化数据集合，模拟现实中组织，由实体entities和联系relationships构成
数据库管理系统DBMS：用于数据库储存、管理和查询的软件
数据库系统Database System = Databases + DBMS
2.描述数据
数据模型data model：描述数据的一组概念集合
模式schema：使用数据模型对数据集合的描述
关系数据模型relational data model：广泛使用的数据模型，由行列表组成，每个关系相应一个模式
3.DBMS的抽象层次（由外到内）：
外模式：定义视图，针对不同用户展示不同视图
概念模式：定义逻辑结构，储存关系
物理模式：定义物理结构，逻辑关系如何物理储存在磁盘上
数据独立性：应用程序不受数据结构和储存方式的影响
在DBMS中查询关系：以非程序方式执行，由数据库优化查询方案，SQL语言，用户程序并发执行
并发控制Concurrency Control：保证不同用户程序之间互不影响
事务Transaction：数据操作的原子序列，每个被完全执行的事务都保证数据库处在一致状态，不完整的事务导致系统崩溃
先写日记WAL：在更改数据库前，写日记到安全位置，崩溃后由日记完毕不完整的事务

lec2 实体关系模型
1.数据库设计：需求分析，概念设计（ER模型），逻辑设计，模式细化，物理设计，安全设计
概念设计：实体和联系的储存，完整性约束integrity constraints，关系模式<=>ER图
实体Entity：现实世界中的对象，DB中使用一组属性描述
实体集Entity（方框）：每个实体集中的对象都有相同的属性（椭圆），每个属性有一个域domain，每个实体集有一个键key
键key：最小的属性集，值唯一标记集合中的实体
候选键Candidate key：一个实体可以有多个键
主键Primary key（下划线）：选定一个候选键为主键
联系Relationship：关联两个或更多实体，由参与的实体唯一标记，
联系集Relationship set（菱形）：相似联系的集合；n个实体的联系集成为n元（n-ary）联系集；相同实体集可参与不同联系集，或在相同联系集中扮演不同角色
键约束Key Constraints（箭头）：每个发出箭头的对象最多拥有一个被箭头指向的对象
参与约束Participation Constraints：
完全参与total（粗线）：一个实体集中每个实体都参与到粗线连接的联系中
部分参与partial：一个实体集中部分实体参与到连接的联系中
弱实体Weak Entities：只能通过与所有者实体的关系来标记，一个实体可以关系多个弱实体，弱实体必须完全参与标记的关系，弱实体只有部分键partial key（虚下划线）
类层次Class Hierarchies（三角形中ISA）：
交迭约束Overlap constraints：三角形下方连接的n个实体对于上方连接的实体是n选1的关系（不反复）
覆盖约束Covering constraints：三角形上方连接的实体至少要与一个下方连接的实体关系（完全参与）
聚合Aggregation：允许建立实体集和关系之间的关系
2.关系数据库：
定义：关系的集合
关系模式Schema：指定关联名称和每个字段的名称和类型
关系实例Instance：一组元组，包含关系模式的每个字段
查询语言：SQL，声明性语言
数据定义语言DDL：创建、修改、删除关系，指定约束，管理用户
数据操作语言DML：指定查询，创建、修改、删除元组
创建关系：CREATE TABLE + 关系名 + （属性名 + 字段类型）
插入元组：INSERT INTO + 关系名 + （属性名） + VALUES + （属性值）
删除元组：DELETE FROM + 关系名 WHERE + 条件
键：不同关系中关联语言的一种方法，是一种完整性约束，保证数据独立性
主键/超键superkey：关系中任意两个元组的超键值均不同；当一个关系有多个键时，仅有一个键是超键，其他是候选键
SQL定义超键：PRIMARY KEY + （属性名）
外键Foreign key：一个关系中的字段用于引用另一个关系中的元组，必须相应另一个关系的主键，类似逻辑指针；执行所有的外键约束实现引用完整性
SQL定义外键：FOREIGN KEY + （属性名） + REFERENCES + 关系名
删除被引用关系中元组时保证引用完整性的方案：
同时删除引用关系中的相应元组（Cascade）
严禁删除被引用关系中被引用的元组（No Action）
将引用的值设为default（Set Default）
将引用的值设为null，显示unknown或inapplicable（Set NULL）
完整性约束IC：保证数据库中任何实例都对的，在定义关系模式时定义，在修改关系时检查
查询语义：概念评价方法：FROM做各个关系叉积，WHERE检查条件并选择符合条件的元组，SELECT删除不需要的字段；实际将做效率更高的调整
弱实体集：被转换为单个表，当所有者实体被删除时，弱实体集也被删除；FOREIGN KEY + （属性名） REFERENCES + 关系名 + ON DELETE CASCADE

lec3 关系查询语言
1.查询语言：负责数据库的操作和检索
关系代数Relational Algebra：更多操作，善于表达执行计划
关系演算Relational Calculus：善于描述，不表达计算，非过程，声明式
2.关系代数
基本运算符：
选择Selection(σ)：选择适当的行
投影Projection(p)：选择适当的列，消除反复（真实系统中通常忽略）
叉积Cross-product(x)：连接两个关系，继承字段名（可自行指定同名字段：C(第n个字段->字段名)）
差Set-difference(-)：包含在第一个关系，但不在第二个关系中的元组
并Union：包含在第一个关系或第二个关系中的元组，两关系需满足并相容union-compatible（各字段数量和类型均依次相同）
每个基本运算操作都返回一个关系，因此可以组合操作，如：R 交 S = R - (R - S)
连接join：计算叉积，选择合并在两关系中都出现的属性的相同值的元组，删除其他元组；条件连接、相等连接
3.关系演算
查询：{T|p(T)}，返回p(T)为真的元组
原子公式：
T 属于 Relation
T.a op T.b
T.a op 常数（op = >/</=/>=/<=/!=）
公式：
原子公式
非p、p或q、p且q、p推出q（等价于非p或q）
存在R(p(R))、一切R(p(R))
变量：
自由变量Free Variables：{T|p(T)}中T是自由变量
绑定变量Bound Variables：除T外所有变量是绑定变量，由全称量词/存在量词指定
不安全查询：语法对的但答案无限的查询，{T|非(T属于某关系)}
关系完整性Relational Completeness：查询语言可以表达关系代数中的任何查询

lec4 查询语言SQL
1.SQL基础
SELECT [DISTINCT] target-list
FROM relation-list
WHERE qualification
GROUP BY grouping-list
HAVING group-qualification
FROM：计算表的叉积
WHERE：检查条件，丢弃不满足的行
SELECT：删除不需要的属性
GROUP BY：组和集合的形式
HAVING：消除GROUP
DISTINCT：可选，表达查询结果消除反复的行
2.计算优化Query optimizer：选择性能最佳的计算方式得到相同的答案
通配符：S.sname LIKE 'B_%B'表达满足条件的属性值
"_"：任意一个字符
"%"：任意数量字符
集合运算：
UNION：两个查找结果集合的并
INTERSECT：两个查找结果集合的交
EXCEPT：两个查找结果集合的差
IN：用法同LIKE，选择属于IN后集合的属性值
NOT IN：与IN相反
EXISTS：选择补集
op ANY/ALL（op = >/</=/>=/<=/!=）：选择满足条件的属性值
空值NULL：表达未知unknown或无关inapplicable的字段值，使问题复杂，需要设立三值逻辑true/false/unknown
3.连接Joins：
SELECT (column_list)
FROM table1_name [INNER | {LEFT |RIGHT | FULL } OUTER] JOIN table2_name ON qualification_list
WHERE qualification
内连接Inner Join：默认连接，只返回匹配的行
左外连接Left Outer Join：返回所有匹配的行和左关系中未匹配的行，null表达未匹配的属性
右外链接Right Outer Join：与左外连接相似
全外连接Right Outer Join：返回所有匹配的行和左右关系中未匹配的行，null表达未匹配的属性
4.视图Views：定义数据库外部模式
CREATE VIEW view_name
AS select_statement
有些情况下，视图可以代替数据库查询
5.一般性约束General Constraints
CREATE TABLE + 关系名 + （属性名 + 字段类型, CONSTRAINT + 约束名 + CHECK + 条件）
在完整性约束IC涉及到更多键时使用，可以使用查询表达约束，在插入和更新时检查，约束可以被命名

lec5 数据储存：磁盘和文献
1.DBMS结构（自顶向下）：查询优化和执行->关系运算符->文献和访问方法->缓冲区管理->磁盘空间管理
DBMS储存在磁盘(随机存储)/磁带(连续存储)中，读写需通过内存完毕，开销较大，磁盘检索时间与存储位置有关
单位固定：读写最小单位为磁盘块/数据页(8K)
2.磁盘组成：自旋盘、磁头组，同一时刻仅一个磁头在完毕读/写，磁盘快大小是扇区大小的整数倍
访问磁盘时间：
寻道时间seek time：伸缩磁头臂使磁头移动到对的的轨道，0-10ms
旋转时间rotational delay：等待自旋盘旋转岛对的的扇区，0-3ms
传输时间transfer time：磁头读/写磁盘上的数据，0.2ms/8K数据块
减少I/O开销需减少寻道、旋转时间：文献块按序列排列在磁盘上（同一轨道/同一柱面/相邻柱面），连续扫面，预读取
磁盘空间管理：最底层DBMS负责管理，以供上层调用
3.缓冲区管理：DBMS只能解决读入内存的文献，缓冲区管理隐藏了并非所有文献都在内存中的事实
上层请求->缓冲池（内存中）->数据库（磁盘中）
缓冲池信息表包含<数据页，页号，是否被钉住pin_count，是否修改dirty>
假如选择的页面不在缓冲池中：
选择一个pin_count == 0的页面替换
假如被选中的页面被修改过(dirty)，将它写回磁盘
将请求的页读入池中
钉住pin一页将返回它的地址，同时pin_count++
被请求的页面最终会解钉并根据dirty判断是否需要写回磁盘
选择缓冲池中替换的页的策略：最近最少使用LRU、MRU、clock等，对I/O时间影响很大
最近最少使用LRU：
通过一个指向缓冲池中页的指针队列，依次保存解钉的页，优先替换队列首页
优点：直观简洁，对经常反复访问页有效
缺陷：连续扩散Sequential flooding，假设缓冲池大小为10，文献大小为11，对文献的每次扫描都需要重新读文献的每一页
时钟替换clock：与LRU类似，较之多设计1位，即替换第二次移动到队列首的页
4.记录文献：DBMS上层仅操作记录和记录文献
文献file：一组页面，每个页面包含记录的集合，支持插入、删除、查找、修改、遍历
堆文献Heap Files：没有特定顺序的记录集合，根据文献增减而增删磁盘页，需要跟踪文献中的页、页中空白和记录
页链表：用头指针分表链接满数据页和有空数据页
页目录：目录是一组页，包含<页指针,空白字节数>
索引Indexes：有效回答基于属性值查询的文献结构
记录格式：
定长记录Fixed Length：将文献中所有记录字段的类型信息储存在目录中，可以直接计算第i个元组的储存位置
紧缩型：空白记录所有在页尾，最后记录一个数字表达该页记录条数
离散型：空白记录分散在全页，最后记录一个大小为n的数组表达第n条记录是否为空和数字n表达该页记录条数
变长记录Variable Length：记录之间用特殊字符分隔，或在页头部设立n个分别指向页中保存的n个记录的指针
页末记录一个大小为n的指针数组表达第n条记录的位置和长度和数字n表达该页记录条数
5.系统目录
对每个文献：保存名称、文献位置、文献结构，对每个属性保存属性名称和类型，对于每个索引保存索引名称，实现完整性约束
对每个索引：保存结构和搜索键
对每个视图：保存视图名称和定义
记录、授权、缓冲池大小等

lec6 文献和索引
1.RecordId：由存储这个记录的槽所在的数据页ID和槽的编号组成，<pageId, slot#>
逻辑上，文献由记录组成；物理上，文献由数据页组成，而每个页包含一组记录
从随机访问的角度来说，读写一条记录需要一次磁盘I/O
文献在磁盘上的结构对数据库访问开销影响很大
2.文献组织File Organizations：
堆文献Heap files：合用于经常遍历扫描文献的系统
排序文献Sorted Files：合用于检索搜索键或范围擦找
聚簇文献Clustered Files：数据记录顺序与索引中数据项顺序相同或接近
3.分析代价模型Clustered Files：
分析均匀平均工作的负载情况
忽略：连续或随机I/O，预读取，所有内存操作
假设：
单记录插入删除
等值选择
堆文献：总是插入到文献末尾
排序文献：文献删除后需要压紧，仅搜索搜索键内容
4.索引Indexes：基于磁盘的快速查找程序
用途：允许在一个或多个字段中按值检索
搜索键Search key：关系中任何一列的子集，不一定是键，可以有多个匹配查找的元组
索引文献组成：
底部：数据项Data Entry <=> 数据记录data record
直接链接数据记录，一个文献只能有一个索引，聚簇
<k, rid>匹配符合的记录id，每个文献可以有多个不同的索引
<k, rid>匹配符合的记录链表，每个文献可以有多个不同的索引，定长记录中比记录id更紧凑
顶部：引导部分，由树索引或Hash索引组成
聚簇文献：
优点：范围速锁高效，磁盘调度、预读取高效
缺陷：维护成本高，堆文献需要先排序
5.开销小结
堆文献 排序文献 聚簇文献
遍历 BD BD 1.5BD
等值搜索 0.5BD D*log(2)B D*log(F)1.5B
范围搜索 BD [log(2)B + #matchPG]*D [log(F)B + #matchPG]*D
插入 2D D*(log(2)B+B) D*(log(F)1.5B+1)
删除 0.5BD+D D*(log(2)B+B) D*(log(F)1.5B+1)
规定：
B：数据库的数量
R：每个数据块中的记录数量
D：读写一块的平均时间
F：索引树的扇出（平均分支数）
#matchPG：匹配的页数
6.复合搜索键Composite Search Keys：搜索键是字段的组合，如<age, sal>，可按字典序排序

lec7 树形结构索引
1.树形索引支持等值和范围检索，Hash索引仅支持等值检索
索引顺序存取方法ISAM：静态树，插入删除仅影响叶节点
创建：顺序分派数据记录，按搜索键排序，链接索引页，必要时增长溢出页
搜索：从根节点起，依次比较搜索键直到叶节点，开销Cost=log(F)N，无需“下一页”指针
插入：查找该页所属的叶节点并插入，所有页满时增长溢出页，用链表连接
删除：查找并删除，若获得一个空的溢出页，则删除该页并从链表中取消
B+树：动态，在插入和删除时调整结构，每个节点包含d<=m<=2d个元素（d是树的秩），每个子树高度相同（平衡树），各个节点都是<key, page id>
例：一颗秩为100的树，填充因子通常为66.7%，则平均扇出为2*100*66.7%=133，4级树可检索19G数据
插入算法：
找到插入节点L，若L不满，直接插入；若L满，将L均匀分裂为L和L2，最中间的值向上插入到父节点中，也许递归执行，使树长高
假如不希望分裂节点，可以重分布节点，将被插入的节点与它左/右不满的节点重分布以容纳新元素
删除算法：
找到删除节点L，若L中元素个数>d，直接删除
若L中元素个数<=d，尝试与它的左/右节点重分布，若重分布失败，和左/右节点合并
若发生合并，需要删除父节点中指向它们之间的元素，也许递归执行，使树变矮
块加载：若数据量大，可将多个相邻元素合并视为一个，参与树运算

lec8 Hash索引
1.Hash索引支持等值检索，与树形相似的有静态和动态
静态哈希Static Hashing：
索引文献由一系列桶组成，每个桶有一个主页，也许链接溢出页
桶数量固定，主页按顺序分派，不会清理
桶内包含数据项，由公式h(k) mod N拟定搜索键为k的数据在N号桶中
哈希函数h(k)作用于搜索键k，将各个元素散列到N个桶中，例：h(k)=(a*k+b)
缺陷：长溢出链影响性能
可扩展哈希Extendible Hashing：
桶满时重新组织文献，将桶数翻倍
使用桶指针目录，翻倍桶数只需要翻倍目录（体积更小）
目录的全局深度Global depth：用于检索属于哪个桶的最大位数
桶的局部深度Local depth：用于检索是否属于这个桶的位数，也许比全局深度小1（桶指针尚未扩展到该桶）
当插入导致桶的局部深度比全局深度大时，需要做桶扩展
低位哈希扩展、高位哈希扩展
等值检索：假如目录可以所有读入内存，等值检索只需要1次I/O
删除：假如删除导致一个桶空，将它的桶指针指向上次分裂得到的另一个桶
线性哈希Linear Hashing：
另一种动态哈希方案，是可扩展哈希的另一种选择，用溢出页解决长溢出链的问题
哈希函数族hi(k)=h(k) mod (N*2^i)
桶分裂方式：循环分裂
外循环：循环分裂级别level从0递增
内循环：在第level级，从0到第N*2^level-1个桶逐个分裂，next指针指向要分裂的桶，循环结束得到N*2^(level+1)个桶，接着进入下一个循环
查找：假如hlevel(k)的结果在[next, Nk]之间，该结果相应的桶是查找结果，否则结果也许在hlevel(k)和hlevel(k)+Nk两个桶中（已分裂）
插入：若目的桶有空，直接插入，若桶满，执行内循环直到分裂该桶

lec9 外排序External Sorting
1.外排序：对数据多遍解决，使用较少内存排序庞大数据集
两路归并外排序Two-Way External Merge Sort：
逐页依次读入内存，按搜索键排序并写回，占用1页空间
反复加倍有序段长，排序并写回，占用3页空间
总开销：Cost = 2N * ([log(2)N] + 1)，其中[x]表达比x大的最小整数
外归并排序General External Merge Sort：
若内存中B页空间可用，则开销Cost = 2N * ([log(B-1) [N/B]] + 1)
改善：连续读块，双缓冲，不排序
聚簇B+树应用于排序，通常只需1次I/O

lec10 关系操作实现
1.运用关系代数等价性，调整运算顺序，以盼望用更小的性能代价计算得到同样的答案
运算开销取决于：
结果大小：可近似表达为(size of R) * selectivity，其中selectivity为选择因子
可用的索引：
若没有可用的索引，则需遍历整个关系，开销为关系总页数
若有可用索引，则通过索引查找，开销Cost=通过索引查找符合条件的数据项开销+链接相应数据记录开销（区别聚簇与非聚簇索引）
改善非聚簇索引：找到符合条件的数据记录，将他们按键值排序，仅取他们的键
一般选择条件：
合取范式CNF：(A or B) and (C or D)，ABCD代表选择条件
在搜索键前缀创建合取体的B+树，如：<a, b, c> matches a=5 AND b=3
一般选择方法：
a.查找开销最低的访问途径（预估索引或遍历中需要最少页面开销的方法），用它检索其他没有直接索引的元组
b.应用两个或更多匹配的索引，从每个索引中得到键的集合，计算叉积，从交叉处检索键的记录
投影Projection：用于消除反复
环节：扫描整个关系并筛选需要的属性，排序，删除相邻反复的属性值
开销：在每个环节完毕时都写入临时表
改善：为避免临时文献，在运营时工作
其他技巧：
假如索引中包含了所有需要的属性，可以只扫描索引（唯索引）
假如B+树前缀包含所有需要的属性，可以只比较相邻索引（有序唯索引）
连接Joins：
简朴嵌套循环连接：
若两关系均不能完全读入内存，A x B的开销Cost=A的页数+A的页数*A每页的元组数*B的页数
若至少一个关系能完全读入内存，A x B的开销Cost=A的页数+B的页数
页嵌套循环连接：若两关系均不能完全读入内存，A x B的开销Cost=A的页数+A的页数*B的页数
块嵌套循环连接：若两关系均不能完全读入内存，A x B的开销Cost=A的页数+A的页数*B的页数/内存能提供的空间页数
索引嵌套循环链接：
A x B的开销Cost=A的页数+A的页数*A每页的元组数*索引查找相应B元组的开销
若索引直接链接数据记录，查找相应元素开销Cost=从根节点查找到叶节点的开销
若索引链接符合的记录id或链表<k, rid>，开销Cost=查找rid的开销（B+树通常为2-4次I/O）+通过rid查找数据记录的开销
若为聚簇索引，通过rid查找记录开销Cost=每页数据1次I/O
若为非聚簇索引，开销Cost=至多每条数据1次I/O
排序归并链接算法：
先将两关系分别排序，再计算连接
A x B的开销Cost=排序A+排序B+(A的页数+B的页数)，极差情况下最后一项也许为两者乘积
其他注意：
在合并的最后过程再做连接操作
若内存足够大，可以先将两关系分别读入排序写出，再读入做连接，A x B的开销Cost=3*(A的页数+B的页数)
当两关系或任一关系已经排序，或规定输出有序元组时，最佳选择排序归并连接

lec11 关系查询优化
1.查询转化为关系代数，再转化为树，连接关系分支，每个操作符可以以不同顺序实现
执行计划Plan：关系代数运算数和每个操作的算法选择，尽也许选择最佳情况，避免最坏情况
基于成本的查询子系统：基于之前的环节开销进行修改的启发式方法
2.优化目的：找到更快的计划来得到同样的答案
优化方法：基于关系等价的不同实现方法
下推（优先执行）选择操作
使用索引
连接运算时更少页数的关系在前
排序后连接
成本估算：估计树中每个操作的大小
成本计算公式
数据大小估计
考虑CPU和I/O开销总和
搜索算法：对计划进行估计，选择开销最小的方案
单位优化：查询块Query Blocks
将查询分解为多个查询块，逐个优化，再通过操作合并
左深连接树left-deep join trees：查询块连接后作为左子树和其他查询块连接
3.关系查询等价：
选择级联：选择符合c1且c2且…且cn条件(关系R) <=> 选择符合c1条件(选择符合c2条件(…(选择符合cn条件(关系R))))
选择互换：选择符合c1条件(选择符合c2条件(关系R)) <=> 选择符合c2条件(选择符合c1条件(关系R))
投影级联：投影属性a1(关系R) <=> 投影属性a1(投影属性a1、a2(…(投影属性a1、a2…an(关系R))))
叉积结合：(R x S) x T <=> R x (S x T)
叉积互换：R x S <=> S x R
4.优化方法：
加速投影，尽快投影除去不需要的属性
跨越关系的选择等价于连接
若选择关系只涉及连接的其中一个关系，先做选择
估算缩减因素RF：输出基数/输入基数
选择计算（假设属性中所有值均匀分派且互相独立）：
某属性=某值：RF=1/该属性不同值个数
关系A某属性值=关系B某属性值：RF=1/max(关系A该属性不同值个数, 关系B该属性不同值个数)
某属性>某值：RF=(该属性最大值-该值)/(该属性最大值-最小值)
缺少相关数据，直接计算RF=1/10
连接计算（将R加入S，属性A相同）：
若A是R指向S的外键：RF=1/R的元组数
对R中每个元组：RF=R元组数*S元组数/S中A的不同值个数
对S中每个元组：RF=R元组数*S元组数/R中A的不同值个数
替代枚计算方法：
单表查询：
涉及选择、投影、组/集合运算
考虑每个可用途径，选择开销最低的
选择/投影运算在读文献时同时进行
组/集合运算结果流水写出内存
开销：
存在选择属性相应的索引：Cost=B+树高度+1
存在一个或更多选择属性的聚簇索引：Cost=(索引的页数+关系的页数)*各个条件RF的乘积
存在一个或更多选择属性的非聚簇索引：Cost=(索引的页数+关系的元组数)*各个条件RF的乘积
顺序扫描：Cost=关系的页数
查询多个关系：
左深连接树，便于找到所有生成计划并比较开销，中间结果不写入临时文献
生成计划：
关系加入树的顺序
每个关系的访问方式
每个链接的方法
N次计算：
第一次：用最小的开销读入一个关系
第N次：用最小的开销读入一个关系，并和之前的关系树连接成新关系树
对每次关系加入都保持当前连接树开销最小，同时保证每次加入操作开销最小
排序、分组、集合计算最后进行，注意剪枝

lec12 模式求精和表单
1.模式求精Schema Refinement：一致性，标准化
冗余：与关系模式相关的问题的根源，导致插入/删除/修改异常
完整性约束：辨认冗余并加以改善
重要改善方式：分解decomposition
2.函数依赖FD：
用于检测冗余，X->Y表达对于关系R中所有元组，假如X属性相同，则Y属性一定相同
假如K->关系R中所有属性，则K是R的超键
问题：插入/删除/修改异常，根源是数据冗余
解决：模式分解，将依赖属性分解为单独的表，需要时再做连接
函数依赖推理：
A->B,C <=> A->B 且 A->C
A->B 且 B->C => A->C
F+：函数依赖集F的闭包
推导规则：
自反率Reflexivity：假如X包含Y，则X->Y
增补率Augmentation：假如X->Y，则XZ->YZ
传递率Transitivity：假如X->Y且Y->Z，则 X->Z
合并Union/分解Decomposition：A->B,C 等价于 A->B 且 A->C
属性闭包Attribute Closure：
根据FD推导规则，反复进行闭包运算直到集合没有变化，得到属性F在关系R中的闭包F+
假如F+包含了R的所有属性，则F是R的超键
3.范式Normal Forms：
假如关系R符合某种范式，说明R已经回避了某些问题
范式可以帮助判断一个关系是否有必要继续分解
1NF > 2NF > 3NF > BCNF逐个严格
第一范式1NF：保证所有属性原子性，数据库表同一列中不能有多个值，即实体中的某个属性不能有多个值或者不能有反复的属性
第二范式2NF：在第一范式基础上，规定实体的属性完全依赖于主关键字，不能存在仅依赖主关键字一部分的属性
第三范式3NF：在第二范式基础上，属性不依赖于其它非主属性
即满足：X->A是平凡函数依赖（X包含于A） 或 X是超键 或 A是属性R的候选键
标准化范式BCNF：在第三范式基础上，数据库表中不存在任何字段对任一候选关键字段的传递函数依赖则符合第三范式
即满足：X->A是平凡函数依赖（X包含于A） 或 X是超键
即关系R中没有传递函数依赖
满足BCNF的关系中每个元组的每个字段信息都无法被FD单独推出
4.模式分解Decomposition of a Relation Scheme：
不满足范式的关系可以被分解为多个满足范式的关系，每个关系都是原关系的子集，且它们的并集构成R
分解问题：
也许有损（连接后不能恢复原关系）
需要连接运算检测依赖性
部分查询开销增大
无损分解：分解成两个关系的属性交集是原关系的键时，该分解无损
BCNF分解：
a.若 R 不是 BCNF，其中违反范式的函数依赖是 X->A，将 R 分解为 R-A，和 XA
b.假如 R-A 或 XA 不是 BCNF 则继续分解，此时各自的函数依赖是 F 的投影，而非 F
分解顺序与结果有关，不唯一，无损分解，也许会丢失一部分未能成功投影的函数依赖
3NF分解：
方法1：求最小函数覆盖
a.所有函数依赖变成标准形式（右边单属性）
b.最小化每个依赖的左边，即检查每个依赖内左边的每个属性能否删除
c.删除冗余的函数依赖，观测左边比较“大块”的依赖，看删除后 F+是否改变。
方法2：在最小覆盖的基础上分解
a.其中违反范式的函数依赖是 X->A，将 R 分解为 R-A，和 XA
b.假如 R-A 或 XA 不是 3NF 则继续分解。
c.ab循环完毕后，得到 R1，R2，R3…..Rn 的无损分解，记为 Ri，相应的函数依赖投影 Fi
d.标记出原依赖集 F 中不在 Fi 并集中的依赖，记为 N
e.对于每个在 N 中的依赖 X->A, 生成 XA，然后加入分解后的 Ri 序列，构成无损且保持依赖的分解集。
满足范式规定的数据库设计是结构清楚的，同时可避免数据冗余和操作异常
这并意味着不符合范式规定的设计一定是错误的，在数据库表中存在1：1或1：N关 系这种较特殊的情况下，合并导致的不符合范式规定反而是合理的

lec13-14 事务介绍和并发控制
1.并发控制Concurrency Control：在多用户并发访问时提供对的且可用性高的数据访问
崩溃恢复Recovery：保证数据库不会由于软件、系统或传输过程犯错而犯错，随时可以访问关键任务数据
在数据库磁盘到文献层实现并发控制和容错
2.事务Transaction：读写数据库操作的原子序列，每个被完全执行的事务都保证数据库处在一致状态
事务管理器Transaction Manager：控制事务执行，用户程序逻辑对DBMS不可见，DBMS仅管理数据读写
并发：
响应时间Response time：完毕事务的平均时间
延迟latency：短事务也许被长事务拖慢，导致不可预估的延迟
吞吐量throughput：一定期间内完毕事务的平均数量，I/O同时进行CPU运算可以减少两者的空闲时间
事务执行原则：
原子性Atomicity：一个事务中所有动作全执行，或全不执行
事务在完毕所有动作后，状态变为