2023年数据库笔记

数据库概述led数据事实或观测的成果是对客观事物的逻辑归纳,是用于表达客观事物的未经加工时的原始素材L data:数据库大的构造化数据集合,模拟现实中组织，由实体和联络构成Database:Data+Base,entities relationships数据库管理系统用于数据库储存、管理和查询的软件DBMS:I数据库系统Database System=Databases+DBMS.描述数据2数据模型描述数据的一组概念集合data model:模式使用数据模型对数据集合的描述schema:关系数据模型广泛使用的数据模型，由行列表构成,每个关系对应一种模式relational datamodel:的抽象层次（由外到内）:

3.DBMS外模式:定义视图,针对不一样顾客展示不一样视图概念模式:定义逻辑构造，储存关系物理模式:定义物理构造,逻辑关系怎样物理储存在磁盘上数据独立性:应用程序不受数据构造和储存方式的影响I在中查询关系以非程序方式执行，由数据库优化查询方案,语言,顾客程序并发执行DBMS SQL并发控制保证不一样顾客程序之间互不影响Concurrency Control:事务数据操作的原子序列，每个被完全执行日勺事务都保证数据库处在一致状态，不完整日勺事务导致系统瓦解Transaction:先写日志在更改数据库前,写日志到安全位置,瓦解后由日志完毕不完整的事务WAL实体关系模型Iec2数据库设计:需求分析,概念设计（模型），逻辑设计,模式细化,物理设计,安全设计

1.ER概念设计:实体和联络的储存,完整性约束关系模式图integrity constraints,=ER实体现实世界中日勺对象,中使用一组属性描述Entity:DB实体集（方框）每个实体集中的）对象均有相似的属性（椭圆）,每个属性有一种域每个实体集有一种键Entity domain,key长处:范围速锁高效,磁盘调度、预读取高效缺陷维护成本高，堆文献需要先排序堆文献排序文献聚簇文献遍历BD BD

1.5BD等值搜索

0.5BD D*log2B D*logF

1.5B.开销小结5范围搜索BD[log2B+#matchPG]*D[logFB+#matchPG]*D插入2D D*log2B+B D*logF1,5B+l删除

0.5BD+D D*log2B+B D*logF

1.5B+l规定数据库的数量B:I每个数据块中日勺记录数量R读写一块日勺平均时间D:索引树的扇出平均分支数F:匹配日勺页数#matchPG:复合搜索键:搜索键是字段的组合,如可按字典序排序6Composite SearchKeys age,sal,树形构造索引Iec

7.树形索弓支持等值和范围检索,索引仅支持等值检索1I Hash索引次序存取措施静态树,插入删除仅影响叶节点ISAM:创立:次序分派数据记录,按搜索键排序,链接索引页,必要时增长溢出页搜索:从根节点起,依次比较搜索键直到叶节点，开销日无需“下一页”指针Cos ogFN,插入:查找该页所属长］叶节点并插入,所有页满时增长溢出页，用链表连接删除查找并删除若获得一种空的溢出页,则删除该页并从链表中取消树动态，在插入和删除时调整构造，每个节点包括〈=个元素是树日勺秩，每个子树高度相似平B+d m=2d d衡树，各个节点都是＜＞key,page id例一颗秩为的树,填充因子一般为则平均扇出为级树可检索数据

10066.7%,2*100*

66.7%=133,419G插入算法找到插入节点若不满，直接插入；若满，将均匀分裂为和最中间日勺值向上插入到父节点中，也许L,L L LLL2,递归执行，使树长高假如不但愿分裂节点,可以重分布节点,将被插入日勺节点与它左/右不满的节点重分布以容纳新元素删除算法找到删除节点若中元素个数〉直接删除L,L d,若中元素个数＜尝试与它的左/右节点重分布,若重分布失败,和左/右节点合并L=d,若发生合并,需要删除父节点中指向它们之间的元素,也许递归执行，使树变矮块加载若数据量大,可将多种相邻元素合并视为一种，参与树运算索弓Iec8Hash I索引支持等值检索,与树形相似的有静态和动态l.Hash静态哈希Static Hashing:索引文献由一系列桶构成,每个桶有一种主页,也许链接溢出页桶数量固定,主页按次序分派,不会清理桶内包括数据项，由公式确定搜索键为日勺数据在号桶中hk modN kN哈希函数作用于搜索键将各个元素散列到个桶中，例hk k,N hk=a*k+b缺陷:长溢出链影响性能可扩展哈希Extendible Hashing:桶满时重新组织文献,将桶数翻倍使用桶指针目录,翻倍桶数只需要翻倍目录体积更小目录日勺全局深度用于检索属于哪个桶的最大位数Global depth:桶的局部深度用于检索与否属于这个桶的位数,也许比全局深度小桶指针尚未扩展到该桶Local depth:1当插入导致桶日勺局部深度比全局深度大时需要做桶扩展低位哈希扩展、高位哈希扩展等值检索:假如目录可以所有读入内存,等值检索只需要次1I/O删除假如删除导致一种桶空,将它的桶指针指向上次分裂得到的!另一种桶线性哈希Linear Hashing:另一种动态哈希方案,是可扩展哈希的]另一种选择,用溢出页处理长溢出链日勺问题哈希函数族Ahik=hk modN*2i桶分裂方式:循环分裂外循环:循环分裂级别从递增level0内循环在第级，从到第个桶逐一分裂，指针指向要分裂的桶，循环结束得到level0N*2A|evel-l next个桶,接着进入下一种循环N*2Nlevel+l查找假如肥成果在之间，该成果对应的桶是查找成果，否则成果也许在和两个桶中已分hlevdk[next,Nk]hlevelk hlevelk+Nk裂插入若目的]桶有空直接插入,若桶满,执行内循环直到分裂该桶外排序Iec9External Sorting.外排序:对数据多遍处理，使用较少内存排序庞大数据集1两路归并外排序Two-Way ExternalMerge Sort:逐页依次读入内存按搜索键排序并写回，占用页空间1反复加倍有序段长,排序并写回，占用页空间3总开销其中冈表达比大日勺最小整数Cost=2N*[log2N]+1,x外归并排序General ExternalMerge Sort:若内存中页空间可用，则开销B Cost=2N*[logB-l[N/B]]+1改善:持续读块,双缓冲,不排序聚簇树应用于排序,一般只需次B+1I/O关系操作实现leclO运用关系代数等价性,调整运算次序以期望用更小的］性能代价计算得到同样的答案L运算开销取决于成果大小:可近似表达为（）其中为选择因子size ofR*selectivity,selectivity可用时索弓I若没有可用的索弓则需遍历整个关系,开销为关系总页数I L若有可用索引，则通过索引查找开销二通过索引查找符合条件日勺数据项开销+链接对应数据记录开销（区Cost别聚簇与非聚簇索引）改善非聚簇索引找到符合条件的数据记录，将他们按键值排序，仅取他们日勺键一般选择条件合取范式（）（）代表选择条件CNF:A orB andC orD,ABCD在搜索键前缀创立合取体勺树,如H B+a,b,c matchesa=5AND b=3一般选择措施查找开销最低日勺访问途径（预估索引或遍历中需要至少页面开销的）措施），用它检索其他没有直接索引的元组a.应用两个或更多匹配的索引，从每个索引中得到键时集合,计算叉积,从交叉处检索键的］记录b.投影用于消除反复Projection:环节扫描整个关系并筛选需要的］属性,排序,删除相邻反复的属性值I开销:在每个环节完毕时都写入临时表改善:为防止临时文献,在运行时工作其他技巧假如索弓中包括了所有需要时属生可以只扫描索引（唯索引）I假如树前缀包括所有需要的属性,可以只比较相邻索弓（有序唯索引）B+I连接Joins:简朴嵌套循环连接:若两关系均不能完全读入内存,的开销二日勺页数］页数*每页日勺元组数*日勺页数A xB CostA+Aa A8若至少一种关系能完全读入内存,的开销的页数的页数A xB Cost=A+B页嵌套循环连接:若两关系均不能完全读入内存,的）开销的页数%）页数*的页数A xB Cost=A+A B块嵌套循环连接若两关系均不能完全读入内存,的开销的页数日勺页数*的页数/内存能提供的空间页数A xB Cost=A+A8索引嵌套循环链接的］开销%］页数+日勺页数*庆每页时元组数*索引查找对应元组的开销AxB Cost=A A B若索引直接链接数据记录,查找对应元素开销;从根节点查找到叶节点的开销Cost若索引链接符合日勺记录或链表开销二查找的开销（树一般为次）+通过查找数据记录时开销id k,rid,Cost ridB+2-4I/O rid若为聚簇索弓通过查找记录开销二每页数据次L ridCost1I/O若为非聚簇索弓开销二至多每条数据次cost1I/O排序归并链接算法先将两关系分别排序,再计算连接的开销二排序排序（的页数的页数）,极差状况下最终一项也许为两者乘积A xB CostA+B+A+B其他注意在合并时最终过程再做连接操作若内存足够大,可以先将两关系分别读入排序写出,再读入做连接,日勺开销（%）页数日勺页数）当两关系或A xB Cost=3*A+B任一关系已经排序,或规定输出有序元组时,最佳选择排序归并连接关系查询优化lecll.查询转化为关系代数,再转化为树,连接关系分支,每个操作符可以以不一样次序实现1执行计划关系代数运算数和每个操作长］算法选择,尽量选择最佳状况,防止最坏状况Plan:基于成本的查询子系统:基于之前的环节开销进行修改日勺启发式措施.优化目时找到更快的计划来得到同样日勺答案2优化措施:基于关系等价时不一样实现措施下推（优先执行）选择操作使用索引连接运算时更少页数的）关系在前排序后连接成本估算:估计树中每个操作日勺大小成本计算公式数据大小估计考虑和开销总和CPU I/O搜索算法:对计划进行估计,选择开销最小的方案单位优化:查询块Query Blocks将查询分解为多种查询块,逐一优化,再通过操作合并左深连接树查询块连接后作为左子树和其他查询块连接left-deep jointrees:.关系查询等价3选择级联选择符合且且…且条件（关系）选择符合条件（选择符合条件（…（选择符合条件cl c2cn R=cl c2cn（关系））））R选择互换:选择符合条件（选择符合条件（关系））选择符合条件（选择符合条件（关系））cl c2R=c2cl R投影级联:投影属性（关系）投影属性（投影属性（（投影属性（关系））））al R=al al.a2…al.a2…an R叉积结合:（）（）RxS xT=Rx SxT叉积互换R xS=S xR.优化措施4加速投影,尽快投影除去不需要的属性跨越关系的选择等价于连接若选择关系只波及连接的其中一种关系,先做选择估算缩减原因输出基数/输入基数RF:选择计算（假设属性中所有值均匀分派且互相独立）某属性:某值:该属性不一样值个数RF=1/关系某属性值二关系某属性值:（关系该属性不一样值个数关系该属性不一样值个数）ABRF=1/max AB某属性〉某值:二（该属性最大值-该值）/（该属性最大值-最小值）RF缺乏有关数据,直接计算RF=1/1O连接计算（将加入属性相似）R S,A若是指向日勺外键:时元组数A R S RF=1/R对中每个元组:元组数*元组数中的）不一样值个数R RF=R S/S A对中每个元组:元组数*元组数中时不一样值个数S RF=R S/R A替代枚计算措施单表查询包括选择、投影、组/集合运算考虑每个可用途径选择开销最低的选择/投影运算在读文献时同步进行组/集合运算成果流水写出内存开销存在选择属性对应的索弓树高度I Cost=B++1存在一种或更多选择属性日勺聚簇索弓二（索弓页数+关系日勺页数）*各个条件的乘积I CostRF存在一种或更多选择属性的非聚簇索弓二（索引的页数十关系的元组数）*各个条件的乘积I CostRF次序扫描:二关系日勺页数Cost查询多种关系:左深连接树，便于找到所有生成计划并比较开销，中间成果不写入临时文献生成计划关系加入树的次序每个关系的访问方式I每个链接的措施次计算N第一次:用最小时开销读入一种关系第次:用最小时开销读入一种关系,并和之前的关系树连接成新关系树N对每次关系加入都保持目前连接树开销最小，同步保证每次加入操作开销最小排序、分组、集合计算最终进行，注意剪枝模式求精和表单Iecl2模式求精一致性,原则化L Schema Refinement:冗余与关系模式有关的问题的本源,导致插入/删除/修改异常完整性约束:识别冗余并加以改善重要改善方式:分解decomposition.函数依赖2FD:用于检测冗余,表达对于关系中所有元组，假如属性相似,则属性一定相似X-Y RX Y假如关系中所有属性，则是的超键K-R KR问题:插入/删除/修改异常,本源是数据冗余处理:模式分解将依赖属性分解为单独的表,需要时再做连接函数依赖推理A-B,C=A-B HA-C且〉二〉A-B B-C A-C函数依赖集时闭包F+:F推导规则:自反率假如包括则Reflexivity:X Y,X-Y增补率假如则Augmentation:X-Y,XZ-YZ传递率:假如且丫一〉乙贝【Transitivity X-Y JX-Z合并分解等价于且Union/Decomposition:A-B,C A-B A-C属性闭包Attribute Closure:根据推导规贝（反复进行闭包运算直到集合没有变化，得到属性在关系中的）闭包FD FR F+假如包括了的所有属性,则是的超键F+R FR.范式3Normal Forms:假如关系符合某种范式，阐明已经回避了某些问题R R范式可以协助判断一种关系与否有必要继续分解逐一严格INF2NF3NFBCNF第一范式保证所有属性原子性，数据库表同一列中不能有多种值，即实体中的某个属性不能有多种值或者不能有反复的属性1NF:第二范式在第一范式基础上,规定实体附属性完全依赖于主关键字,不能存在仅依赖主关键字一部分的属性2NF:第三范式在第二范式基础上,属性不依赖于其他非主属性3NF即满足:〉是平凡函数依赖（包括于）或是超键或是属性的］候选键X-A XA XA R原则化范式在第三范式基础上，数据库表中不存在任何字段对任一候选关键字段的传递函数依赖则符合第三范式BCNF即满足:是平凡函数依赖（包括于）或是超键X-A XA X即关系中没有传递函数依赖R满足的关系中每个元组的每个字段信息都无法被单独推出BCNF FD.模式分解4Decomposition ofa RelationScheme:不满足范式日勺关系可以被分解为多种满足范式日勺关系,每个关系都是原关系的］子集,且它们的］并集构成R分解问题也许有损（连接后不能恢复原关系）需要连接运算检测依赖性部分查询开销增大无损分解分解成两个关系的属性交集是原关系日勺键时,该分解无损分解BCNF.若不是其中违反范式的函数依赖是将分解为和aRBCNF,X-A,R R-A,XA假如或不是则继续分解，此时各自的函数依赖是的投影,而非b R-A XABCNF FF分解次序与成果有关,不唯一,无损分解,也许会丢失一部分未能成功投影的函数依赖分解:3NF措施求最小函数覆盖1所有函数依赖变成原则形式（右边单属性）a.最小化每个依赖的左边,即检查每个依赖内左边的每个属性能否删除b.删除冗余的函数依赖，观测左边比较“大块”的依赖看删除后与否变化c.F+措施在最小覆盖的基础上分解2:其中违反范式的函数依赖是将分解为和a.X-A,R R-A,XA假如或不是则继续分解b.R-A XA3NF循环完毕后,得到日勺无损分解记为对应日勺函数依赖投影c.ab RI,R2,R3…..Rn Ri,Fi标识出原依赖集中不在并集中的）依赖,记为d.F FiN.对于每个在中的依赖生成然后加入分解后的序列构成无损且保持依赖的分解集e NX-A,XA,Ri满足范式规定的数据库设计是构造清晰的同步可防止数据冗余和操作异常I这并意味着不符合范式规定的设计一定是错误日勺，在数据库表中存在或「关系这种较特殊的状况下，合并导致的不符合11N范式规定反而是合理日勺键最小时属性集，值唯一标识集合中日勺实体key:候选键一种实体可以有多种键Candidate key:主键（下划线）选定一种候选键为主键Primary key联络关联两个或更多实体,由参与的实体唯一标识，Relationship:联络集（菱形）:相似联络的集合；个实体的）联络集成为元（）联络集；相似实体集Relationship setn n n-ary可参与不一样联络集,或在相似联络集中饰演不一样角色键约束（箭头）每个发出箭头日勺对象最多拥有一种被箭头指向日勺对象Key Constraints参与约束Participation Constraints:完全参与（粗线）一种实体集中每个实体都参与到粗线连接的联络中total部分参与一种实体集中部分实体参与到连接的联络中partial:弱实体只能通过与所有者实体的）关系来标识一种实体可以关系多种弱实体，弱实体必须完全参Weak Entities:与标识的关系，弱实体只有部分键（虚下划线）partial key类层次（三角形中）Class HierarchiesISA:交迭约束三角形下方连接的个实体对于上方连接的实体是选的关系（不反复）Overlap constraints:n n1覆盖约束三角形上方连接的实体至少要与一种下方连接的实体关系（完全参与）Covering constraints:聚合容许建立实体集和关系之间的）关系Aggregation:.关系数据库2定义:关系日勺集合关系模式指定关联名称和每个字段的名称和类型Schema:关系实例一组亓组,包括关系模式的每个字段Instance:查询语言:申明性语言SQL,数据定义语言创立、修改、删除关系，指定约束，管理顾客DDL:数据操作语言指定查询,创立、修改、删除元组DML事务简介和并发控制Iecl3-

14.并发控制在多顾客并发访问时提供对的且可用性高的数据访问1Concurrency Control:瓦解恢复保证数据库不会由于软件、系统或传播过程出错而出错,随时可以访问关键任务数据Recovery:在数据库磁盘到文献层实现并发控制和容错.事务读写数据库操作日勺原子序歹％每个被完全执行的）事务都保证数据库处在一致状态2Transaction:事务管理器控制事务执行,顾客程序逻辑对不可见仅管理数据读写Transaction Manager:DBMS DBMS并发响应时间完毕事务日勺平均时间Response time:延迟短事务也许被长事务拖慢,导致不可预估的延迟latency:吞吐量一定期间内完毕事务的平均数量同步进行运算可以减少两者的空闲时间throughput:CPU事务执行原则原子性一种事务中所有动作全执行,或全不执行Atomidty:事务在完毕所有动作后,状态变为提交否则变为中断commit,abort为保持原子性，执行二分之一而中断的事务需要取消之前执行的内容一致性若数据库在事务执行前一致,则在执行后仍保持一致Consistency:为保持一致性,中断的事务需要额外保留并在有条件的状况下再次执行I数据库用记录中断事务,记录中断事务中未执行的）部分undo red数据库一致性表达为一组申明性完整性约束违反日勺事务将被中断IC,IC隔离性一种事务时执行与其他事务时执行相隔离,类似单机操作Isolation:持久性提交的事务持久有效Durability:事务调度:事务中各动作的执行次序,完整的调度包括每个事务的提交或中断串行调度每个事务从开始到结束保持运行,没有其他事务操作干预Serial Schedule可串行化调度Serializable Schedule:事务等价:包括相似的］事务的动作,把放在最终一种状态DB多种事务并发执行的成果与按某一次序串行地执行它们时的成果相似，则这些事务时集合是可串行化的可串行化的多种事务执行成果也许不一样，但所有成果都是可接受的，不能保证它们中的哪一种是交叉执DBMS行的成果未提交的事务也许出目前可串行化事务集合中，但它的）作用也许被中的）记录抵消undo操作冲突Conflicting Actions:写读冲突:读了未提交的数据读写冲突:不可反复读写写冲突丢失更新也许引起交叉执行的异常处理:用更简朴日勺方式检查时间表等价可恢复调度Recoverable Schedule:事务仅在串行调度的事务集合所有执行完毕后提交假如事务仅读了已提交事务的变化,不仅可以恢复调度,级联中断也可以防止冲突可串行化调度Conflict SerializableSchedules:两个串行化调度包括相似日勺一组动作,以同样的方式处理每一对互相冲突的行为，则它们冲突等价J J若调度和另某些串行化调度冲突等价，则该调度是冲突可串行的1某些可串行调度不是冲突可串行时这是高效执行日勺代价假如可以通过互换不一样的持续日勺非冲突操作来将原调度转换为串行调度,则原调度是冲突可串行的］可串行化调度不一定是冲突可串行化调度.依赖图优先图3Dependency Graph/precedence graph:用于描述在一种调度中动作之间的所有潜在冲突调度日勺依赖图包括:每个提交的动作节点从到的边，假如日勺动作比动作优先且它们冲突Ti TjTi TjaI依赖图无环=调度是冲突可序列化的I两阶段加锁2PL:最常见日勺实行冲突可序列化的方案,保证冲突可串行性,不能防止级联中断为防止冲突而设置锁,消极时另一种方案是并发控制,乐观时共享锁:读之前加锁排斥锁:写之前加锁一种行为一旦释放了锁,便不能再加锁严格2PL加锁管理Lock Management:处理加锁解锁祈求保持目的对象的加锁状态保留:每个数据对象标识，目前有锁列表,锁的性质,祈求加锁解锁的队列收到加锁祈求时,鉴定与否已经有冲突的锁,若没有则加锁,若有则将祈求者放入等待队列升级锁:共享锁的事务可以祈求升级为排斥锁死锁等待处理的锁被彼此循环加入等待队列,永远无法处理Deadlocks:处理死锁防止资源排序prevention:检测创立等待队列的检测图,若成环则死锁Detection:防止根据时间戳分派优先级avoidance:加锁粒度Locking Granularity:在数据库/表/页/元组层面加锁多粒度锁:在多种不一样层面加锁意向锁:部分读部分写全读全写5/IX/S/X多粒度意向锁故障恢复Iecl5Crash Recovery.系统重启后的期望状态:提交的内容持久保留,未完毕的内容被中断1假设:并发控制,适时更新,写操作有原子性.提交前写在提交前将脏页写入磁盘,也许导致下一种调度偷帧（提高并发度）2偷帧难以强制执行原子性STEAL:不偷难以强制执行持久性NO FORCE:提交后写先提交再将脏页写入磁盘,强制写.写日志3Logging:为每次更新记录和妁］信息,次序写入日志,放在单独的磁盘上redo undoJ日志记录动作勺最小信息，因此多种更新可以记录在单个日志页面上H和额外日勺控制信息Log:XID,pagelD,offset,length,old data,new data先写日志WAL:在对应的数据页抵达磁盘之前,必须强制将所有的日志记录更新到磁盘保证操作的原子性、持久性,用于实现偷帧、非强制写每个日志有单独的）日志次序码依次递增,系统跟踪最大日勺码LSN,每页有一种页最新的］日志的记录更新到该页面,在页被写入磁盘前有页日志LSN,1LSN LSN=LSN日志记录包括、、和更新记录的信息LogRecord:LSN prevLSNXID.type事务表目前活动日勺动作条目，直到动作提交或中断时删除该条目，包括、Transaction Table:XID status.lastLSN脏页表目前在缓冲池中所有修改正的页条目，包括（记录页面修改的次序）Dirty PageTable:recLSN.事务执行过程:4一系列读写,直到提交或中断,遵守严格偷帧,不强制写,2PL WAL事务提交提交记录写入日志,刷新磁盘中所有该动作的提交记录，保证flushedLSN=lastLSN事务中断获得动作表中日勺lastLSN在开始回滚操作之前中断日志记录通过跟踪记录时日志记录链（反向链表）prevLSN为未执行的）操作写赔偿日志记录CLR为了执行将数据上锁undo,执行结束后写日志undo end检查点Checkpointing:周期性创立检查点,最小化瓦解后的恢复时间DBMS写日志开始点:记录检查点开始日勺位置结束点:包括目前日勺动作表和脏页表将近来的检查点记录存储在一种安全的地方事务恢复从一种检查点开始,分析找出在检查点之后执行失败的动作Analysis-*正向扫描日志文献，找出在故障发生前已经提交的）事务队列（队列）和未完毕日勺事务队列（队列）REDO UNDO通过事务表和脏页表重新建立检查点欧）内容执行结束的动作从动作表中删除将其他动作添加到动作表,设置在提交记录上更改动作状态,并将修改日勺页添加到脏页表中lastLSN=LSN,动作表记录了瓦解时正在执行的）动作记录了没有写入磁盘的］脏页DPT-重新执行之前执行过时所有动作来重建瓦解的状态REDO CLR士正向扫描日志文献，对每个事务重新执行日志文献登记的操作，即将日志记录中“更新后时值”写入数据库REDO I在中对包括最小的）日志记录进行扫描DPT recLSN对每个更新日志记录或中日勺动作除了CLR动作影响的页不在中I DPT动作影响的］页在中但或DPT recLSNLSN pageLSNLSN执行:再次申请日志操作，设置pageLSN-不执行导致中断的动作UNDO*反向扫描日志文献,对每个事务的更新操作执行逆操作，即将日志记录中“更新前时值”写入数据库UNDO I选择动作表中最大的lastLSN假如这个是且为这个动作写记录LSN CLRundonextLSN==NULL,end假如这个是且将这个动作添加到（所有动作表中日勺集合）LSN CLRundonextLSN!=NULL,ToUndo lastLSNs反复执行直到为空ToUndo限制工作量:后台异步刷新redo限制工作量:防止耗时长日勺动作undo创立关系+关系名+（属性名+字段类型）CREATE TABLE插入元组:+关系名+（属性名）（属性值）INSERT INTO+VALUES+删除元组+关系名+条件DELETE FROM WHERE键:不一样关系中关联语言的一种措施,是一种完整性约束，保证数据独立性J主键/超键关系中任意两个元组的］超键值均不一样；当一种关系有多种键时，仅有一种键是超键，其他是候选键superkey:定义超键:（属性名）SQL PRIMARYKEY+外键一种关系中的字段用于引用另一种关系中日勺元组，必须对应另一种关系的主键，类似逻辑指针；执行所有的Foreign key:外键约束实现引用完整性定义外键:日（属性名）++关系名SQL FORGN KEY+REFERENCES删除被弓用关系中元组时保证引用完整性的方案I1同步删除引用关系中的）对应元组（）Cascade严禁删除被引用关系中被引用的元组（）N Action将弓用日勺值设为（）I defaultSet Default将弓用日勺值设为显示或（）I null,unknown inapplicableSet NULL完整性约束保证数据库中任何实例都对日勺,在定义关系模式时定义在修改关系时检查IC:查询语义概念评价措施做各个关系叉积，检查条件并选择符合条件欧］元组，删除不需要的字段；实FROMWHERESELECT际将做效率更高的调整1弱实体集.被转换为单个表，当所有者实体被删除时，弱实体集也被删除；（属性名）+关系名+FOREIGN KEY+REFERENCESON DELETECASCADE关系查询语言Iec3查询语言:负责数据库日勺操作和检索L关系代数更多操作,善于表达执行计划Relational Algebra:关系演算善于描述,不表达计算，非过程,申明式Relational Calculus.关系代数2基本运算符选择选择合适的行Selectiono:投影选择合适的列,消除反复真实系统中一般忽视Projectionp:叉积连接两个关系,继承字段名可自行指定同名字段:第个字段—字段名Cross-productx:C n差包括在第一种关系，但不在第二个关系中的］元组Set-difference-:并包括在第一种关系或第二个关系中日勺元组，两关系需满足并相容各字段数量和类型均依次Union:umon-compatible相似每个基本运算操作都返回一种关系，因此可以组合操作,如交RS=R-R-S连接计算叉积，选择合并在两关系中都出现的属性的相似值的元组,删除其他元组；条件连接、相等连接Qn:.关系演算3查询:，返回为真日勺元组TIPT}PT原子公式属于T RelationT.a opT.b常数T.a opop=//=/=/=/!=公式原子公式非、或、且、推出等价于非或p pq pq pq pq存在、一切RpR RpR变量自由变量中是自由变量Free Variables:{T|pT}T绑定变量除外所有变量是绑定变量，由全称量词/存在量词指定Bound Variables:T不安全查询语法对日勺但答案无限的查询非属于某关系}iT|T关系完整性查询语言可以体现关系代数中的任何查询Relational Completeness:查询语言Iec4SQL基础LSQL［］SELECT DISTINCTtarget-listFROM relation-listWHERE qualificationGROUP BY grouping-listHAVING group-qualification计算表日勺叉积FROM:检查条件,丢弃不满足的行WHERE删除不需要的属性SELECT:组和集合日勺形式GROUPBY:消除HAVING:GROUP可选,表达查询成果消除反复日勺行DISTINCT.计算优化选择性能最佳长］计算方式得到相似日勺答案2Query optimizer:通配符:表达满足条件日勺属性值S.sname LIKEBJB任意一种字符%:任意数量字符集合运算两个查找成果集合的］并UNION:两个查找成果集合的］交INTERSECT:两个查找成果集合日勺差EXCEPT::使用方法同选择属于后集合附属性值IN LIKE,IN与相反NOT IN:IN选择补集EXISTS:（）:选择满足条件的属性值op ANY/ALL op=//=/=/=/!=空值表达未知或无关的]字段值，使问题复杂,需要设置三值逻辑NULL:unknown inapplicabletrue/false/unknown.连接3Joins:（）SELECT columnjistFROMtablel_name[INNER|{LEFT|RIGHT|FULL}OUTER]JOIN table2_name ONqualificationjistWHERE qualification内连接默认连接,只返回匹配的行Inner Join:左外连接返回所有匹配的行和左关系中未匹配的行表达未匹配附属性Left OuterJoin:null右外链接与左外连接相似Right OuterJoin:全外连接返回所有匹配日勺行和左右关系中未匹配内]行,表达未匹配的）属性Right OuterJoin:null.视图定义数据库外部模式4Views:CREATE VIEWview.nameAS select_statement有些状况下,视图可以替代数据库查询.一般性约束5General Constraints+关系名+（属性名+字段类型,+约束名++条件）在完整性约束波及到更多键CREATE TABLECONSTRAINT CHECKIC时使用，可以使用查询表达约束,在插入和更新时检查,约束可以被命名数据储存:磁盘和文献Iec5构造（自顶向下）查询优化和执行-关系运算符-文献和访问措施-缓冲区管理-磁盘空间管理储存在磁盘（随

1.DBMS DBMS机存储）/磁带（持续存储）中,读写需通过内存完毕,开销较大,磁盘检索时间与存储位置有关单位固定:读写最小单位为磁盘块/数据页（）8K.磁盘构成自旋盘、磁头组，同一时刻仅一种磁头在完毕读/写，磁盘快大小是扇区大小的整数倍2访问磁盘时间:寻道时间伸缩磁头臂使磁头移动到对欧］日勺轨道,seek time:0-10ms旋转时间等待自旋回旋转岛对时时扇区,rotational delay:0-3ms传播时间磁头读/写磁盘上的数据,数据块transfer time:

0.2ms/8K减少开销需减少寻道、旋转时间文献块按序列排列在磁盘上（同一轨道/同一柱面/相邻柱面），持续扫面,预读取I/O磁盘空间管理:最底层负责管理,以供上层调用DBMS.缓冲区管理只能处理读入内存的］文献,缓冲区管理隐藏了并非所有文献都在内存中的］事实3DBMS上层祈求-缓冲池（内存中）-〉数据库（磁盘中）缓冲池信息表包括〈数据页,页号,与否被钉住与否修改pin_count,dirty假如选择的页面不在缓冲池中选择一种%］页面替代pin_count==0假如被选中的页面被修改正（）将它写回磁盘1dirty,将祈求日勺页读入池中钉住一页将返回它的］地址，同步pin pin_count++被祈求的页面最终会解钉并根据判断与否需要写回磁盘dirty选择缓冲池中替代的页的方略近来至少使用、、等，对时间影响很大J JLRU MRUclock I/O近来至少使用LRU:通过一种指向缓冲池中页的）指针队列依次保留解钉的页，优先替代队列首页长处:直观简洁,对常常反复访问页有效缺陷持续扩散假设缓冲池大小为文献大小为对文献时每次扫描都需要重新读文献的每一页Sequential flooding,10,11,时钟替代与类似,较之多设计位即替代第二次移动到队列首的页clock LRU

1.记录文献:上层仅操作记录和记录文献4DBMS文献一组页面，每个页面包括记录日勺集合，支持插入、删除、查找、修改、遍历file堆文献没有特定次序的记录集合，根据文献增减而增删磁盘页，需要跟踪文献中的页、页中空白和记Heap Files:录页链表:用头指针分表链接满数据页和有空数据页页目录目录是一组页，包括〈页指针,空白字节数〉索引有效回答基于属性值查询的文献构造Indexes:记录格式定长记录将文献中所有记录字段的］类型信息储存在目录中，可以直接计算第个元组的储存位置Fixed Length:i紧缩型:空白记录所有在页尾,最终记录一种数字表达该页记录条数离散型:空白记录分散在全页,最终记录一种大小为时数组表达第条记录与否为空和数字表达该页记录条n n n数变长记录记录之间用特殊字符分隔,或在页头部设置个分别指向页中保留日勺个记录妁）指针页末记录一种Vanable Length:nn大小为的指针数组表达第条记录的位置和长度和数字表达该页记录条数nnn.系统目录5对每个文献:保留名称、文献位置、文献构造，对每个属性保留属性名称和类型，对于每个索弓保留索弓名称，实现I I完整性约束对每个索弓保留构造和搜索键I:对每个视图:保留视图名称和定义记录、授权、缓冲池大小等文献和索引Iec6由存储这个记录的槽所在的数据页和槽的编号构成,

1.Recordld:ID pageld,slot#逻辑上,文献由记录构成；物理上,文献由数据页构成,而每个页包括一组记录从随机访问日勺角度来说,读写一条记录需要一次磁盘I/O文献在磁盘上的）构造对数据库访问开销影响很大.文献组织2File Organizations:堆文献合用于常常遍历扫描文献的系统Heap files:排序文献合用于检索搜索键或范围擦找Sorted Files:聚簇文献数据记录次序与索弓中数据项次序相似或靠近Clustered Files:I.分析代价模型3Clustered Files:分析均匀平均工作的］负载状况忽视:持续或随机预读取,所有内存操作I/O,假设单记录插入删除等值选择堆文献:总是插入到文献末尾排序文献文献删除后需要压紧仅搜索搜索键内容.索弓基于磁盘时迅速查找程序4I Indexes:用途:容许在一种或多种字段中按值检索搜索键关系中任何一列的子集,不一定是键,可以有多种匹配查找的元组Search key:1索引文献构成底部:数据项数据记录Data Entry=data record直接链接数据记录，一种文献只能有一种索弓聚簇L〉匹配符合的记录每个文献可以有多种不一样日勺索引k,nd id,匹配符合的记录链表,每个文献可以有多种不一样的索弓定长记录中比记录更紧凑k,rid Lid顶部弓导部分，由树索引或索弓构成I HashI聚簇文献。