数据库小抄

这是我的数据库期末小抄,是对老师课件的总结。原文由formula编写,可点击此处下载。

# 1 形式关系查询语言

关系代数:选择formula,投影formula,并formula,差formula,笛卡尔积formula,更名formula推广的运算:交formula,自然连接formula,除法formula,赋值formula扩展的关系代数:泛化投影(投影的参数是函数或运算)、聚集函数(有avg、min、max、sum和count,formula)、外连接。谓词元组关系演算formula,由以下组成,1) 属性和常量,2) 比较运算符,3) 逻辑运算符,4) 量词。域关系演算formula

# 2 数据库设计和E-R图

E-R组成:实体集(实体是对象,矩形)、关系集(可以是多个实体之间,个数称为degree,菱形)、属性(可以是关系的,这时候是虚线)。属性分类:简单和组合(缩进表示),单值和多值(花括号括住),派生(末尾一对括号)。映射基数限制:一对一,一对多,多对一,多对多(箭头指向实体集代表一,无箭头代表多,可以用formula来代表更复杂基数限制,其中formula也可以是formula代表没有限制)。超键:可以决定其他属性的一组属性。候选键:最小的超键。主键:挑选出一个候选键(下划线属性)。全参与与部分参与:全参与(双线)是所有实体有至少一个关系,部分参与(单线)是存在实体没有关系。冗余属性:对于一些出现在两个实体集像外键的属性,在ER图需要移除。弱实体集:(双矩形,区分属性下划虚线,关系双菱形)所有属性不足以形成主键的实体,依赖于(被own)强实体(identifying entity),强实体与弱实体的关系(identifying relationship)只能是一对一或一对多且弱实体是全参与。角色:对于实体集多次参与同一关系集,每次参与都有个角色(线上文字)。E-R图转数据库schema强实体集转化为所有属性组成schema;弱实体集还带上强实体集的主键;多对多关系转化包含两者主键;一对多多对一如果多的一边是全参与则在多的一边添加一的一边的主键,如果不是全参与则使用null值;一对一两边都可以当做多的一边处理;弱实体集关系是冗余的;组合属性扁平化;多值属性则用单独表示包含主键和多值属性。多元关系:为了避免困惑,只有一个出箭头是允许的,可以转化为二元关系。特化和泛化:重合(箭头直接指向基础实体)、分离(箭头汇合后指向基础实体);两种转换方法:1) 派生实体包含基础实体的主键,2) 派生实体直接包含基础实体;完整性约束:全/部分(基础实体是否必须是派生实体)。

# 3 关系数据库设计

第一范式:属性的域都是原子的(不可分割)。函数依赖formula,如果formula超键formula是超键formula候选键formula是候选键formula平凡的函数依赖formula是平凡的。函数依赖集合的闭包:令formula是函数依赖的集合,所有formula隐含的函数依赖集合是formula的闭包,记作formula,一定有formulaBCNF范式formula是平凡的formulaformula是超键formula分解为BCNF范式:对于违反BCNF范式的函数依赖formula,分解为formulaformula,分解有时候不保留依赖关系。第三范式formula是平凡的或formula是超键或formula被某个候选键包含。符合BCNF范式一定符合第三范式,第三范式保留依赖关系。求解函数依赖闭包:反复应用下面3条法则,即可求出闭包:1) (自反性formula;2) (提升性formula;3) (传递性)formula闭包额外的性质:1) (联合formula;2) (分解formula;3) (伪传递formula属性的闭包:在函数依赖formula下,能够被属性集formula决定的属性集formula属性闭包的应用:1) 测试超键formulaformula;2) 测试函数依赖formulaformula;3) 计算函数依赖formula的闭包,对于每个formula,计算属性闭包formula,然后对于每个formula,输出依赖formulaCanonical覆盖:最小的函数依赖集合。无关属性:对于函数依赖集formula中的formula,1) formulaformula中无关的属性,如果formula逻辑上蕴含formula;2) formulaformula中无关的属性,如果formula逻辑上蕴含formula测试属性是否是无关的:对于函数依赖集formula中的formula,1) 测试formula,用formula计算formula,如果它包含formula,则formula是多余的;2) 测试formula,用formula计算formula,如果包含formula,则formula是多余的。计算Canonical覆盖:先使用联合规则合并函数依赖,在测试属性是否多余,循环往复。无损分解:将formula分解为formulaformula,如果formulaformula则为无损分解。依赖保留formula为各个分解的函数依赖集,如果formula,则分解为依赖保留的。测试BCNF分解算法:需要用到分解前的formula中相关的部分。第三范式分解:首先计算Canonical覆盖formula,对于formula中每个formula的函数依赖,将formula添加进分解中,如果没有一个分解包含候选键,则随便添加一个候选键到分解里,最后将那些被包含在其他分解里的分解移除。

# 4 存储和文件结构

架构层数:两层(直接操纵数据)、三层(通过服务端操纵数据)。存储分类:volatile(停电丢失数据)、non-volatile。存储层级:Cache缓存、内存、闪存(读快写慢擦除更慢,如SSD)、磁盘、光盘、磁带,分为一级(缓存、内存)、二级(闪存、磁盘),三级(光盘、磁带)。磁盘:柱面(多盘面的某一磁道组成)、盘面、磁道、扇区;网络连接方式有SAN(Storage Area Networks)和NAS(Network Attached Storage)。磁盘的性能测量:访问时间(寻道时间+旋转延时),数据传输速率,MTTF(Mean time to failure)。优化性能:块(多个连续的扇区),电梯算法,文件组织(去碎片),non-volatile缓存,Log disk,日志文件系统。存储访问:数据库文件被组织成固定长度的块,Buffer缓存用于存储磁盘块的副本。缓存置换策略:LRU策略(Least recently used)。文件组织:固定长度记录的删除,1) 将之后的记录往前移;2) 将最后的移到最前;3) 维护空闲列表,将它加入空闲列表。变长记录使用槽页结构,其头部包含了记录数目,空闲的末尾,每条记录的地址和大小。文件中记录的组织:堆,序列,哈希。序列文件组织:删除使用指针链;插入时如果有空闲则插入到空闲,否则插入到溢出块,最后更新指针链。

# 5 索引和哈希

搜索键:用于查找的键。索引文件:存放搜索键、指针二元组的文件,有顺序和哈希两种。有序索引主索引搜索键的顺序决定了索引的顺序,又称聚集索引;反之称之为二级索引非聚集索引密集索引每一个搜索键都有索引;反之称之为稀疏索引二级索引:索引指向,桶再指向记录。多级索引:如果主键索引不能放到内存,就将索引当做记录,对它创建稀疏索引。删除记录的索引更新:密集索引直接删除对应索引;稀疏索引将下一个搜索键作为索引,如果该搜索键已经有索引,则删除索引。插入记录的索引更新:密集索引直接插入索引;稀疏索引寻找对应位置插入。formula树性质:根节点到叶子节点的路径等长;非根非叶的节点有formulaformula个子节点;叶节点有formulaformula个节点;如果根不是叶,则至少有formula个子节点;如果根是叶,它有formulaformula个值;formula个搜索键的高度不超过formulaformula树节点结构:每个节点有formula个有序的搜索键formulaformula个指针formula;对于非叶节点指针指向孩子;对于叶节点指针指向记录或桶,最后一个指针指向下一个叶节点,formula重复搜索键formulaformula树的插入:如果查找键出现在了叶节点里,则添加入桶,否则将查找键和指针插入叶节点中,如果此时空间不够,则分裂节点;分裂叶节点时左边留formula个节点,剩余的留在右边,再对父节点插入元组,如果父节点满再将分裂传递下去;分裂非叶节点时,左边留formula,右边留formula,再将formula插入到父节点。formula树的删除:合并兄弟节点,并删除父节点到删除节点的搜索键和指针。静态哈希:哈希函数映射到桶,桶包含多条记录;如果溢出,存放在溢出桶里。哈希索引:采用哈希的索引,一定是二级索引。动态哈希:桶地址表规模为formula,初始formula,每个桶对应于一个formula;插入时如果桶满则分裂,对于桶formula,如果formula则插入一个新桶,如果formula则重新计算地址表;删除时,如果桶空,则合并。位图索引:应用于取值很少的属性,是位的数组。

# 6 查询处理

查询时间开销:A1 线性搜索formula;A2 formula树主索引,判相等,搜索键formula;A3 formula树主索引,判相等,非搜索键formula;A4 formula树二级索引,判相等,搜索键,同A1;A4 formula树二级索引,判相等,非搜索键formula;A5 formula树主索引,比较formula,同A3;A6 formula树二级索引,比较,同A4非搜索键;A7 利用1个索引合取选择;A8 使用组合索引合取选择;A9 通过标识符的交实现合取选择;A10 通过标识符的并实现合取选择排序操作:内存中可使用快排;否则使用外部排序(归并排序),令formula是内存块的个数,formula是每次归并读取的块数,其磁盘块传输总数formula,寻道总数为formula连接操作嵌套循环,块传输总数formula,寻道总数formula嵌套块循环,块传输总数formula,寻道总数formula索引嵌套循环,开销为formula合并连接,先对两个关系排序,再连接,块传输总数formula,寻道总数formula哈希连接,先哈希,再对每一个哈希的块连接,如果不能全部加载入内存会有递归划分,不考虑递归划分,块传输总数formula,寻道总数formula,考虑递归划分,块传输总数formula,寻道总数formula表达式求值物化流水线

# 7 查询优化

等价规则formula的级联及交换律formulaformula的级联formula选择、笛卡尔积及formula连接结合formulaformulaformula连接的交换性formula自然连接的结合律formulaformula连接的结合律,如果formula只涉及formulaformula的属性,则formula选择连接对formula连接的分配律,如果formula只涉及formula,则formula,如果formula只涉及formulaformula只涉及formula,则formula投影运算对formula连接的分配律,如果formulaformulaformulaformula的属性,假设formula只涉及formula中的属性,则formula,假设formula还涉及了formula中的属性,则formula集合的交和并有交换律集合的交和并有结合律选择对并、交、差的分配律投影对并的分配律转换的例子:先投影再连接,先连接小的。开销估计的统计信息formula元组的大下,formula一个块中的元组个数,formula,一定有formula选择大小估计formula的大小约为formulaformula的大小约为formula合取formula的大小约为formula,其中formula是对formula大小的估计;析取formula的大小约为formula取反formula的大小约为formula连接大小估计formula,用笛卡尔积估计;formulaformulaformula的键,不会超过formula的个数;formulaformula不是formula的键,formula其他操作大小估计formula大小约为formula;formula大小约为formulaformula大小约为formulaformula大小约为formulaformula大小约为formulaformula大小约为formulaformula大小约为formulaformula的估计**:若formula取特定值,估计为1;若formula取给定值,估计为给定值个数;若formula,估计为formulaformula是选中概率;其他情况,估计为formulaformula的估计:若formula属性全来自formula,则估计为formula;若formula包括了来自formula的属性formula和来自formula的属性formula,估计为formula

# 8 事务

事务的要求:原子性、隔离性、持久性、一致性(ACID)。稳定性存储器:永远不会丢失数据。事务的状态:活动的、部分提交的、失败的、终止的、提交的。可串行化:等价于串行调度的调度,有冲突可串行化和视图可串行化。冲突:如果两个指令访问了同一数据且有一个指令写了数据,则它们是冲突的。冲突等价:如果formula通过交换非冲突指令得到formula,则formulaformula冲突等价。冲突可串行化:与串行调度冲突等价的调度。优先图:画一条formulaformula的边,如果两个事务冲突且formula先访问数据,优先图无环则可串行序列化。视图可串行化:满足以下3条称为formulaformula视图等价,1) formula中某事务读取初始值,formula中也是如此;2) formula中某事务读取的值是另一事务的结果,formula中也是如此;3) formula中某事务最后写,formula中也是如此;冲突可序列化一定视图可序列化;每个非冲突可序列化的视图可序列化存在盲写可恢复调度formula读取了formula写入的数据,formula必须出现在formula的提交之前。级联回滚:一个事务的失败会造成一系列未提交事务的失败。无级联调度formula读取了formula写入的数据,formula的提交出现在formula的读之前。隔离性级别:可串行化、可重复读、已提交读、未提交读。

# 9 并发控制

锁的类型:排他锁(可读可写,lock-X获得)、共享锁(只读,lock-S获得);共享锁之间可以相容,别的情况都不可以;死锁可以通过回退事务解决。两阶段加锁协议:分为两阶段;先是增长阶段,事务只能获取锁,再是缩减阶段,事务只能释放锁;保证冲突串行化,但不保证不发生死锁,级联回滚可能发生;严格两阶段加锁,事务提交后方可释放排他锁,可避免级联回滚;强两阶段加锁,提交后方可释放资源。锁转换:第一阶段可将共享锁升级为排他锁,第二阶段可将排他锁降级为共享锁。锁表:哈希索引数据项的列表,元素为锁,保证了无饿死现象。树形协议基于图的协议,数据项formula,偏序关系formula,访问formula之前必须访问formula树形协议是一种简单的图协议;只有排他锁,首次加锁可以是任何数据,接下来的加锁必须是已加锁的子节点,可以随时解锁,解锁完了不能再加锁;保证冲突可串行化和无死锁,不保证可恢复和无级联回滚。死锁预防:一次全部加锁;规定加锁次序,如树形协议;wait-die机制(非抢占式),老的事务可以等待新的事务,当新的事务等待老的事务的时候回滚;wound-wait机制(抢占式),新的事务可以等待老的事务,当老的事务等待新的事务的时候回滚;超时机制死锁检测:使用等待图,顶点时事务,formula表示formula在等待formula释放所需要数据项,有环则有死锁。多粒度:细粒度、粗粒度;4层,数据库、区域、文件、记录。多粒度的意向锁:共享意向(IS,底层只能加共享锁)、排他意向(IX,底层可加共享或排他锁),共享排他意向锁(SIX,底层加了共享锁,更底层加了排他锁);IS-IS、IS-IX、IX-IX、IS-S、IS-SIX、S-S相容。基于时间戳的协议:为每个事务记录了时间戳formula,为每个数据记录了两个时间戳,formula最大执行formula的时间、formula最大执行formula的时间;formula发出formula,若formula则拒绝回滚,否则成功并更新时间戳;formula发出formula,若formula则拒绝并回滚,否则成功并更新时间戳;无死锁,可能出现及联合回滚,可能不可恢复。Thomas写规则:当formula,忽略写操作。基于有效性检查的协议:事务分为3阶段,读和执行、验证、写,又称为乐观并发控制,3阶段对应3个时间戳formulaformulaformula,其中formulaformula的有效性测试:对于所有的formula,满足下面2条条件之一,1) formula,2) formula写的数据与formula读的数据不相交且formula,则formula通过并提交,否则终止。多版本机制多版本时间戳排序多版本两阶段加锁多版本时间戳排序:存储一系列版本,每个版本包含内容和读写时间戳;formula写时读写时间戳初始化为formulaformula读时如果formula大于读时间戳则更新;令formula是小于等于formula的最大写时间戳的版本;formula时返回formula的内容;formula时,若formula则回滚,若formula则覆盖formula的内容,否则创建新的版本;不保证可恢复性和无级联性。多版本两阶段加锁:区分只读事务更新事务;数据项有时间戳formula;更新事务执行强两阶段加锁协议;只读事务开始时读取当前formula,读取小于formula的最大时间戳的版本的内容;更新数据项时,创建新版本,时间戳置为formula,提交时时间戳置为formula,再对formula加1;可恢复的和无级联的。

# 10 恢复系统

错误分类:事务错误(包含逻辑错误、系统错误)、系统崩溃(Fail-stop假设非易失存储的内容不会改变)、磁盘错误。基于日志的恢复:当事务formula启动的时候,插入日志formula;当formula执行formula,插入日志formulaformula是旧值,formula是新值;当formula执行完毕后,插入日志formula数据库修改延迟修改,知道提交都没修改数据库;立即修改,修改在事务活跃时发生。撤销和重做:撤销formula时将formula写入formula,重做formula时将formula写入formulaformula时,回退所有操作,并写入特殊日志formula,最后插入formulaformula时没有日志输出。检查点:隔段时间执行,写入所有日志到稳定存储,并插入日志formulaformula是所有活跃的事务。系统崩溃后的恢复重做阶段,1) 将undo-list设为formula中的formula,2) 遇到formulaformula,将formula赋给formula,3) 发现formula,将formula加入到undo-list,4) 发现formulaformula,将formula从undo-list中移除;撤销阶段,反向扫描日志,撤销undo-list中的操作。

2016-2020 Ziping Sun
京ICP备 17062397号