2023年数据库笔记

ｌeｃ１数据库概述1.数据daｔa:事实或观测的结果，是对客观事物的逻辑归纳，是用于表达客观事物的未经加工的的原始素材数据库Dａｔabａsｅ：Ｄata＋Base，大的结构化数据集合，模拟现实中组织，由实体entｉties和联系ｒeｌａtｉonshipｓ构成数据库管理系统DBMS：用于数据库储存、管理和查询的软件数据库系统DａｔabaｓeSystｅｍ=Ｄatａbasｅs+DBMS2.描述数据数据模型dａtamoｄel：描述数据的一组概念集合模式schema:使用数据模型对数据集合的描述关系数据模型relationａldatamodel:广泛使用的数据模型,由行列表组成，每个关系相应一个模式3．DBMS的抽象层次（由外到内）：外模式:定义视图，针对不同用户展示不同视图概念模式：定义逻辑结构，储存关系物理模式:定义物理结构，逻辑关系如何物理储存在磁盘上数据独立性：应用程序不受数据结构和储存方式的影响在DＢMS中查询关系:以非程序方式执行，由数据库优化查询方案,SQL语言，用户程序并发执行并发控制ConcurrｅncｙControl：保证不同用户程序之间互不影响事务Transａction:数据操作的原子序列，每个被完全执行的事务都保证数据库处在一致状态，不完整的事务导致系统崩溃先写日记WAＬ:在更改数据库前,写日记到安全位置，崩溃后由日记完毕不完整的事务ｌec2实体关系模型1．数据库设计：需求分析,概念设计（ＥR模型),逻辑设计，模式细化，物理设计,安全设计概念设计：实体和联系的储存,完整性约束inｔｅｇritycｏnsｔraints,关系模式<＝＞ＥR图实体Ｅｎｔiｔｙ:现实世界中的对象,DB中使用一组属性描述实体集Entiｔy（方框)：每个实体集中的对象都有相同的属性(椭圆),每个属性有一个域ｄomain,每个实体集有一个键key键key：最小的属性集，值唯一标记集合中的实体候选键Caｎｄｉdａteｋey：一个实体可以有多个键主键Ｐrｉｍaｒｙkey（下划线）:选定一个候选键为主键联系Ｒelatioｎsｈip：关联两个或更多实体,由参与的实体唯一标记,联系集Rｅlａtioｎshipset（菱形):相似联系的集合；ｎ个实体的联系集成为n元(n-arｙ)联系集;相同实体集可参与不同联系集,或在相同联系集中扮演不同角色键约束ＫeｙCｏnstraiｎｔs(箭头):每个发出箭头的对象最多拥有一个被箭头指向的对象参与约束ParticiｐaｔｉoｎConstraints：完全参与ｔotal(粗线):一个实体集中每个实体都参与到粗线连接的联系中部分参与partｉal：一个实体集中部分实体参与到连接的联系中弱实体ＷeakEntitieｓ：只能通过与所有者实体的关系来标记，一个实体可以关系多个弱实体，弱实体必须完全参与标记的关系，弱实体只有部分键pａrtialkey(虚下划线）类层次ClassHiｅrarchies(三角形中ISA):交迭约束Ｏvｅrlapcｏnsｔｒaｉnts：三角形下方连接的n个实体对于上方连接的实体是ｎ选１的关系(不反复)覆盖约束Ｃｏveringcoｎｓtrａints：三角形上方连接的实体至少要与一个下方连接的实体关系(完全参与）聚合Aggregatiｏｎ：允许建立实体集和关系之间的关系2．关系数据库:定义：关系的集合关系模式Schema:指定关联名称和每个字段的名称和类型 关系实例Instancｅ：一组元组，包含关系模式的每个字段查询语言：SQL,声明性语言数据定义语言DDＬ：创建、修改、删除关系,指定约束，管理用户数据操作语言DML：指定查询，创建、修改、删除元组创建关系:CREATETABLE+关系名＋（属性名+字段类型)插入元组:INＳERTINＴO+关系名+（属性名）+VALUES+（属性值)删除元组：ＤELEＴＥﻩFROM+关系名ﻩWHＥRＥ+条件键:不同关系中关联语言的一种方法,是一种完整性约束，保证数据独立性主键/超键ｓｕｐerｋey:关系中任意两个元组的超键值均不同;当一个关系有多个键时，仅有一个键是超键，其他是候选键ＳQＬ定义超键：PRIMＡＲYＫＥY+（属性名）外键Fｏｒｅigｎｋeｙ：一个关系中的字段用于引用另一个关系中的元组，必须相应另一个关系的主键,类似逻辑指针；执行所有的外键约束实现引用完整性SＱL定义外键:ＦOＲＥIGNKEY＋(属性名)+REFERENCES+关系名删除被引用关系中元组时保证引用完整性的方案: 同时删除引用关系中的相应元组（Cascaｄe) 严禁删除被引用关系中被引用的元组（NoAcｔｉon)将引用的值设为deｆａｕｌｔ(SetＤefaulｔ)将引用的值设为ｎull,显示unkｎown或inａpplicablｅ（SｅtNULＬ)完整性约束ＩＣ：保证数据库中任何实例都对的，在定义关系模式时定义,在修改关系时检查查询语义:概念评价方法：FＲOM做各个关系叉积,ＷHＥRE检查条件并选择符合条件的元组，SＥLＥCT删除不需要的字段；实际将做效率更高的调整弱实体集：被转换为单个表，当所有者实体被删除时,弱实体集也被删除；FOＲEＩＧNKＥＹ+（属性名)ＲＥFEＲＥNCES+关系名+ONＤＥLＥＴECASCADElｅｃ3关系查询语言1.查询语言：负责数据库的操作和检索关系代数RelationａlAlgebra：更多操作,善于表达执行计划关系演算ReｌatioｎaｌCalculｕｓ:善于描述,不表达计算,非过程，声明式２.关系代数基本运算符:ﻩ选择Seｌｅctｉon(σ)：选择适当的行 投影Proｊectiｏｎ(ｐ)：选择适当的列,消除反复(真实系统中通常忽略）ﻩ叉积Ｃrｏss-produｃt(ｘ）：连接两个关系，继承字段名（可自行指定同名字段：Ｃ(第n个字段－>字段名)) 差Set-diffeｒencｅ（-):包含在第一个关系,但不在第二个关系中的元组ﻩ并Uniｏn:包含在第一个关系或第二个关系中的元组，两关系需满足并相容uniｏn-compａｔibｌe(各字段数量和类型均依次相同）每个基本运算操作都返回一个关系，因此可以组合操作，如:Ｒ交Ｓ=R-(R－S)连接ｊoiｎ:计算叉积，选择合并在两关系中都出现的属性的相同值的元组,删除其他元组；条件连接、相等连接3.关系演算查询:{T|ｐ（T)},返回ｐ(T)为真的元组原子公式: T属于RelatiｏnﻩT.aopＴ.bﻩT.aop常数（ｏｐ=>/<／=/>=/<＝/!=)公式:原子公式非p、p或q、p且q、p推出ｑ(等价于非p或ｑ）存在Ｒ(p(R))、一切R（p(R))变量：自由变量FｒｅｅVariableｓ:{T|p(T)}中T是自由变量绑定变量BoundＶariabｌes:除T外所有变量是绑定变量,由全称量词/存在量词指定不安全查询:语法对的但答案无限的查询,｛T|非（T属于某关系）｝关系完整性ＲelａtioｎaｌCompleteneｓs：查询语言可以表达关系代数中的任何查询ｌeｃ4查询语言SQＬ1.SQL基础ﻩＳＥＬECT[DISTINCT］targｅt-lｉｓt FROＭrelatiｏn-lｉsｔ WＨＥREｑｕaliｆiｃａtion GＲOUPBＹｇrouｐinｇ-lisｔﻩHAVINＧgｒoup－quａlificａtｉonFROM:计算表的叉积ＷHEＲE:检查条件,丢弃不满足的行SELECT：删除不需要的属性GROUＰBY:组和集合的形式ＨＡVING：消除GROUPDISTINCT：可选，表达查询结果消除反复的行２.计算优化Ｑueryoptiｍｉｚeｒ：选择性能最佳的计算方式得到相同的答案通配符：Ｓ．snａmｅＬIKE'B_%Ｂ'表达满足条件的属性值"_＂:任意一个字符＂%"：任意数量字符集合运算:UNIＯN:两个查找结果集合的并ＩNTＥＲSＥCＴ：两个查找结果集合的交EXCEＰＴ：两个查找结果集合的差IN：用法同LIKE,选择属于ＩN后集合的属性值NOＴIN:与IN相反ＥXＩSＴS：选择补集ｏｐANY/ＡLＬ（ｏp=>／＜/=/>=／<=／！＝)：选择满足条件的属性值空值ＮULL：表达未知ｕnｋnowｎ或无关inａpｐlicable的字段值,使问题复杂,需要设立三值逻辑tｒue/ｆalse/uｎknoｗn3．连接Joins： SELECT(coluｍｎ_ｌist) ＦRＯMtable1_ｎａme[INＮER|{ＬEFT|ＲＩGＨＴ|FULL}OUTER]JＯINtaｂｌe２_naｍｅONｑuａlificａtion＿listﻩWＨＥREｑuaｌification内连接InｎerJｏin:默认连接,只返回匹配的行左外连接LｅftＯuｔerJｏin:返回所有匹配的行和左关系中未匹配的行,null表达未匹配的属性右外链接RigｈtOutｅrJｏiｎ：与左外连接相似全外连接RightＯutｅｒJｏin:返回所有匹配的行和左右关系中未匹配的行，nｕｌl表达未匹配的属性4.视图Views:定义数据库外部模式 CRＥAＴEVIＥＷview＿naｍe ASselｅct_staｔeｍｅnｔ有些情况下，视图可以代替数据库查询5.一般性约束GeｎeralＣonｓtｒaiｎts CREATＥTＡBLE+关系名＋（属性名+字段类型,CONSTＲAINT＋约束名+CHECＫ＋条件)在完整性约束IＣ涉及到更多键时使用,可以使用查询表达约束,在插入和更新时检查,约束可以被命名lec5数据储存：磁盘和文献１.DBMS结构(自顶向下)：查询优化和执行->关系运算符->文献和访问方法->缓冲区管理->磁盘空间管理ＤＢMS储存在磁盘(随机存储）/磁带(连续存储)中,读写需通过内存完毕,开销较大，磁盘检索时间与存储位置有关单位固定：读写最小单位为磁盘块/数据页(8K）２．磁盘组成：自旋盘、磁头组,同一时刻仅一个磁头在完毕读/写,磁盘快大小是扇区大小的整数倍访问磁盘时间：寻道时间ｓeektiｍｅ：伸缩磁头臂使磁头移动到对的的轨道，0-１0ｍs旋转时间rｏtaｔionaldeｌaｙ：等待自旋盘旋转岛对的的扇区,０-3ms传输时间trａnｓfｅrtime:磁头读／写磁盘上的数据,０.2mｓ/8K数据块减少I/O开销需减少寻道、旋转时间：文献块按序列排列在磁盘上（同一轨道/同一柱面／相邻柱面），连续扫面,预读取磁盘空间管理:最底层DBMS负责管理,以供上层调用３.缓冲区管理:DBMＳ只能解决读入内存的文献,缓冲区管理隐藏了并非所有文献都在内存中的事实上层请求->缓冲池(内存中）->数据库（磁盘中）缓冲池信息表包含<数据页,页号，是否被钉住pin_count，是否修改dｉrｔy>假如选择的页面不在缓冲池中:选择一个pin_counｔ＝＝０的页面替换假如被选中的页面被修改过(dirty),将它写回磁盘将请求的页读入池中钉住ｐin一页将返回它的地址，同时piｎ_count＋+被请求的页面最终会解钉并根据ｄｉｒｔy判断是否需要写回磁盘选择缓冲池中替换的页的策略：最近最少使用LRＵ、MRU、clock等，对I/O时间影响很大最近最少使用ＬＲＵ：通过一个指向缓冲池中页的指针队列,依次保存解钉的页,优先替换队列首页优点:直观简洁,对经常反复访问页有效缺陷:连续扩散Ｓequentialfｌooｄing，假设缓冲池大小为10,文献大小为11，对文献的每次扫描都需要重新读文献的每一页时钟替换cｌocｋ:与LRU类似,较之多设计1位,即替换第二次移动到队列首的页4．记录文献：DBMＳ上层仅操作记录和记录文献文献fｉle:一组页面，每个页面包含记录的集合,支持插入、删除、查找、修改、遍历堆文献ＨeapFｉles:没有特定顺序的记录集合，根据文献增减而增删磁盘页,需要跟踪文献中的页、页中空白和记录页链表:用头指针分表链接满数据页和有空数据页页目录：目录是一组页,包含<页指针,空白字节数>索引Iｎdｅxes:有效回答基于属性值查询的文献结构记录格式:定长记录FixｅdLenｇth：将文献中所有记录字段的类型信息储存在目录中，可以直接计算第i个元组的储存位置紧缩型:空白记录所有在页尾,最后记录一个数字表达该页记录条数离散型：空白记录分散在全页，最后记录一个大小为n的数组表达第n条记录是否为空和数字ｎ表达该页记录条数变长记录VariablｅLｅnｇth:记录之间用特殊字符分隔,或在页头部设立n个分别指向页中保存的n个记录的指针页末记录一个大小为n的指针数组表达第n条记录的位置和长度和数字n表达该页记录条数5．系统目录对每个文献：保存名称、文献位置、文献结构,对每个属性保存属性名称和类型,对于每个索引保存索引名称，实现完整性约束对每个索引:保存结构和搜索键对每个视图:保存视图名称和定义记录、授权、缓冲池大小等lec6文献和索引1．RecorｄId：由存储这个记录的槽所在的数据页ＩD和槽的编号组成,<paｇｅId,sloｔ#>逻辑上,文献由记录组成;物理上，文献由数据页组成，而每个页包含一组记录从随机访问的角度来说,读写一条记录需要一次磁盘I/O文献在磁盘上的结构对数据库访问开销影响很大2.文献组织FileＯrｇanizaｔions:堆文献Heaｐｆileｓ：合用于经常遍历扫描文献的系统排序文献SortedFiles:合用于检索搜索键或范围擦找聚簇文献ClｕsteｒｅdＦｉles：数据记录顺序与索引中数据项顺序相同或接近３．分析代价模型ＣlｕsｔereｄFiles：分析均匀平均工作的负载情况忽略：连续或随机I/O,预读取,所有内存操作假设:单记录插入删除等值选择堆文献：总是插入到文献末尾排序文献：文献删除后需要压紧，仅搜索搜索键内容4.索引Indexes:基于磁盘的快速查找程序用途:允许在一个或多个字段中按值检索搜索键Searchkey：关系中任何一列的子集,不一定是键，可以有多个匹配查找的元组索引文献组成:底部：数据项ＤataEntrｙ<=>数据记录dataｒecoｒd直接链接数据记录,一个文献只能有一个索引，聚簇<k,rid＞匹配符合的记录id，每个文献可以有多个不同的索引＜k，rｉｄ＞匹配符合的记录链表，每个文献可以有多个不同的索引,定长记录中比记录id更紧凑顶部：引导部分,由树索引或Hasｈ索引组成聚簇文献：优点：范围速锁高效,磁盘调度、预读取高效缺陷：维护成本高，堆文献需要先排序5.开销小结堆文献排序文献聚簇文献遍历BDBＤ1.5BＤ等值搜索0．５BDＤ＊log(2）BD*lｏｇ（Ｆ)1．5B范围搜索BD[log(2)B+#maｔｃhＰG]*D［lｏg（F)Ｂ+#mａtchPG］*D插入２DD*(ｌoｇ（2)B+B）D＊(log(F)1.5B＋1)删除0.5BD+ＤＤ*(ｌoｇ(２）B+B)D*(lｏｇ(Ｆ)１.5Ｂ+1)规定：B:数据库的数量R:每个数据块中的记录数量D：读写一块的平均时间F：索引树的扇出(平均分支数）#matchPG:匹配的页数６．复合搜索键ComposｉteSｅaｒchKｅyｓ：搜索键是字段的组合，如<age,sal>,可按字典序排序lｅｃ7树形结构索引1.树形索引支持等值和范围检索,Hash索引仅支持等值检索索引顺序存取方法ISＡM:静态树,插入删除仅影响叶节点创建:顺序分派数据记录，按搜索键排序，链接索引页，必要时增长溢出页搜索：从根节点起，依次比较搜索键直到叶节点,开销Ｃｏｓt=log（F)N，无需“下一页”指针插入：查找该页所属的叶节点并插入，所有页满时增长溢出页,用链表连接删除:查找并删除，若获得一个空的溢出页，则删除该页并从链表中取消B+树:动态，在插入和删除时调整结构，每个节点包含ｄ<=ｍ<＝２d个元素（d是树的秩)，每个子树高度相同(平衡树）,各个节点都是＜key,ｐageｉd>例：一颗秩为１0０的树,填充因子通常为66．7%，则平均扇出为２*100*66.7%＝133,4级树可检索１９G数据插入算法:找到插入节点L,若Ｌ不满，直接插入；若L满,将Ｌ均匀分裂为L和L2，最中间的值向上插入到父节点中,也许递归执行，使树长高假如不希望分裂节点,可以重分布节点，将被插入的节点与它左/右不满的节点重分布以容纳新元素删除算法：找到删除节点L，若L中元素个数＞ｄ，直接删除若L中元素个数<=d，尝试与它的左/右节点重分布，若重分布失败，和左/右节点合并若发生合并,需要删除父节点中指向它们之间的元素，也许递归执行,使树变矮块加载:若数据量大，可将多个相邻元素合并视为一个，参与树运算ｌec8Hａｓh索引1.Hash索引支持等值检索，与树形相似的有静态和动态静态哈希SｔatiｃHasｈing:索引文献由一系列桶组成，每个桶有一个主页，也许链接溢出页桶数量固定，主页按顺序分派，不会清理桶内包含数据项，由公式h(k)modＮ拟定搜索键为ｋ的数据在N号桶中哈希函数h(k)作用于搜索键k，将各个元素散列到N个桶中，例:h（k)=（a*k+b)缺陷：长溢出链影响性能可扩展哈希ExteｎｄｉbleＨａｓhing：桶满时重新组织文献,将桶数翻倍使用桶指针目录，翻倍桶数只需要翻倍目录(体积更小）目录的全局深度Gloｂalｄeptｈ:用于检索属于哪个桶的最大位数桶的局部深度Lｏcaldepth：用于检索是否属于这个桶的位数，也许比全局深度小1（桶指针尚未扩展到该桶）当插入导致桶的局部深度比全局深度大时，需要做桶扩展低位哈希扩展、高位哈希扩展等值检索：假如目录可以所有读入内存，等值检索只需要1次I/O删除：假如删除导致一个桶空，将它的桶指针指向上次分裂得到的另一个桶线性哈希LinearHashing:另一种动态哈希方案，是可扩展哈希的另一种选择，用溢出页解决长溢出链的问题哈希函数族hｉ(k）＝ｈ(k)moｄ(N*2^i)桶分裂方式:循环分裂外循环：循环分裂级别ｌeveｌ从0递增内循环:在第level级,从0到第N*2＾level-1个桶逐个分裂，nexｔ指针指向要分裂的桶,循环结束得到N*2^（level+１）个桶,接着进入下一个循环查找：假如hlevｅｌ（k)的结果在[next,Nk]之间，该结果相应的桶是查找结果,否则结果也许在hlｅvｅl（ｋ)和hleｖel(ｋ）+Ｎk两个桶中（已分裂)插入:若目的桶有空，直接插入，若桶满,执行内循环直到分裂该桶lec9外排序ExternａｌSｏrｔiｎg1．外排序：对数据多遍解决,使用较少内存排序庞大数据集两路归并外排序Two-WａyEｘterｎａlＭeｒgeSort:逐页依次读入内存,按搜索键排序并写回，占用1页空间反复加倍有序段长，排序并写回,占用3页空间总开销：Cost=2N*([log(２)N]+1),其中[x]表达比x大的最小整数外归并排序GeneｒａlEｘterｎalMergeＳort:若内存中B页空间可用,则开销Cost=２N*([lｏｇ(Ｂ－1)[N/Ｂ]]+1)改善：连续读块，双缓冲，不排序聚簇Ｂ+树应用于排序,通常只需1次Ｉ/Olec10关系操作实现１.运用关系代数等价性，调整运算顺序,以盼望用更小的性能代价计算得到同样的答案运算开销取决于：结果大小:可近似表达为(ｓizeofR)*selｅctｉvitｙ,其中selectｉvity为选择因子可用的索引:若没有可用的索引,则需遍历整个关系,开销为关系总页数若有可用索引，则通过索引查找,开销Cosｔ=通过索引查找符合条件的数据项开销＋链接相应数据记录开销(区别聚簇与非聚簇索引）改善非聚簇索引:找到符合条件的数据记录，将他们按键值排序,仅取他们的键一般选择条件:合取范式CＮF：(AorB)ａnd(CｏｒD),ＡBＣD代表选择条件在搜索键前缀创建合取体的B+树,如:<a,b,c>ｍatchesa=5ANDb=3一般选择方法：a.查找开销最低的访问途径(预估索引或遍历中需要最少页面开销的方法)，用它检索其他没有直接索引的元组b.应用两个或更多匹配的索引,从每个索引中得到键的集合，计算叉积，从交叉处检索键的记录投影Ｐｒoｊeｃtiｏｎ：用于消除反复环节:扫描整个关系并筛选需要的属性,排序,删除相邻反复的属性值开销:在每个环节完毕时都写入临时表改善:为避免临时文献，在运营时工作其他技巧:假如索引中包含了所有需要的属性，可以只扫描索引（唯索引）假如B+树前缀包含所有需要的属性,可以只比较相邻索引(有序唯索引）连接Jｏinｓ：简朴嵌套循环连接:若两关系均不能完全读入内存，ＡｘＢ的开销Cost＝Ａ的页数+A的页数*A每页的元组数＊B的页数若至少一个关系能完全读入内存，AxB的开销Cost＝Ａ的页数+B的页数页嵌套循环连接:若两关系均不能完全读入内存,AxB的开销Ｃoｓｔ=A的页数＋Ａ的页数＊B的页数块嵌套循环连接:若两关系均不能完全读入内存，AxＢ的开销Cost＝A的页数+A的页数＊B的页数/内存能提供的空间页数索引嵌套循环链接：AxB的开销Cｏst=A的页数+A的页数*Ａ每页的元组数*索引查找相应B元组的开销若索引直接链接数据记录,查找相应元素开销Cｏsｔ=从根节点查找到叶节点的开销若索引链接符合的记录iｄ或链表＜k,riｄ>,开销Cosｔ=查找rid的开销（Ｂ+树通常为2-４次I／O）+通过ｒid查找数据记录的开销若为聚簇索引,通过rid查找记录开销Cost=每页数据１次I／O若为非聚簇索引,开销Cost＝至多每条数据1次I/O排序归并链接算法：先将两关系分别排序，再计算连接AｘB的开销Cosｔ＝排序A+排序B+（A的页数+Ｂ的页数)，极差情况下最后一项也许为两者乘积其他注意：在合并的最后过程再做连接操作若内存足够大,可以先将两关系分别读入排序写出,再读入做连接,AxB的开销Ｃost＝3*(A的页数+Ｂ的页数）当两关系或任一关系已经排序，或规定输出有序元组时,最佳选择排序归并连接ｌｅc１1关系查询优化１.查询转化为关系代数,再转化为树，连接关系分支,每个操作符可以以不同顺序实现执行计划Plａn:关系代数运算数和每个操作的算法选择，尽也许选择最佳情况，避免最坏情况基于成本的查询子系统:基于之前的环节开销进行修改的启发式方法２.优化目的：找到更快的计划来得到同样的答案优化方法:基于关系等价的不同实现方法下推（优先执行）选择操作使用索引连接运算时更少页数的关系在前排序后连接成本估算：估计树中每个操作的大小成本计算公式数据大小估计考虑ＣPU和I/Ｏ开销总和搜索算法:对计划进行估计，选择开销最小的方案单位优化：查询块QueryBlocks将查询分解为多个查询块，逐个优化，再通过操作合并左深连接树lｅft-deｅpjointreeｓ：查询块连接后作为左子树和其他查询块连接3.关系查询等价：选择级联：选择符合ｃ1且c2且…且ｃn条件(关系R)<=>选择符合c１条件（选择符合c２条件(…(选择符合cn条件（关系R）)））选择互换:选择符合c1条件(选择符合ｃ２条件(关系Ｒ））＜=>选择符合c2条件(选择符合ｃ１条件(关系R）)投影级联:投影属性ａ１(关系R)<=>投影属性ａ1（投影属性a１、a２(…(投影属性a1、a2…aｎ(关系R))）)叉积结合：(RｘS)ｘT＜=>Rx(SxT）叉积互换：RxS<=＞ＳxR4.优化方法:加速投影,尽快投影除去不需要的属性跨越关系的选择等价于连接若选择关系只涉及连接的其中一个关系,先做选择估算缩减因素RF：输出基数/输入基数选择计算(假设属性中所有值均匀分派且互相独立）：某属性=某值：RF＝1/该属性不同值个数关系A某属性值＝关系Ｂ某属性值：ＲF＝1／max(关系Ａ该属性不同值个数,关系B该属性不同值个数)某属性>某值:RF=(该属性最大值-该值)/(该属性最大值－最小值)缺少相关数据,直接计算ＲＦ＝１/10连接计算(将R加入Ｓ，属性A相同)：若A是Ｒ指向S的外键：ＲF=1/R的元组数对Ｒ中每个元组:RF＝Ｒ元组数*S元组数/S中Ａ的不同值个数对Ｓ中每个元组：RＦ=R元组数*S元组数／R中A的不同值个数替代枚计算方法：单表查询：涉及选择、投影、组/集合运算考虑每个可用途径，选择开销最低的选择/投影运算在读文献时同时进行组/集合运算结果流水写出内存开销：存在选择属性相应的索引：Cost=B+树高度+1存在一个或更多选择属性的聚簇索引:Cost=(索引的页数+关系的页数)*各个条件RＦ的乘积存在一个或更多选择属性的非聚簇索引：Coｓt＝(索引的页数+关系的元组数)*各个条件RF的乘积顺序扫描：Ｃｏｓｔ=关系的页数查询多个关系：左深连接树，便于找到所有生成计划并比较开销，中间结果不写入临时文献生成计划:关系加入树的顺序每个关系的访问方式每个链接的方法N次计算:第一次：用最小的开销读入一个关系第Ｎ次：用最小的开销读入一个关系，并和之前的关系树连接成新关系树对每次关系加入都保持当前连接树开销最小,同时保证每次加入操作开销最小排序、分组、集合计算最后进行,注意剪枝lec１2模式求精和表单1．模式求精SchemaRefｉｎｅment：一致性，标准化冗余:与关系模式相关的问题的根源,导致插入/删除/修改异常完整性约束：辨认冗余并加以改善重要改善方式:分解decompositｉon2.函数依赖FD：用于检测冗余，Ｘ->Y表达对于关系Ｒ中所有元组,假如X属性相同,则Ｙ属性一定相同假如K->关系Ｒ中所有属性,则K是R的超键问题：插入/删除/修改异常,根源是数据冗余解决:模式分解，将依赖属性分解为单独的表，需要时再做连接函数依赖推理:Ａ->Ｂ,C<=>Ａ->Ｂ且A->CA->B且B－>Ｃ=>A－>CF+:函数依赖集Ｆ的闭包推导规则:自反率Reflｅxivitｙ：假如X包含Ｙ，则X->Y增补率Ａuｇmentatioｎ:假如X->Y，则XZ->YZ传递率Trａnsiｔivity:假如X->Y且Y->Z，则X->Z合并Ｕniｏｎ/分解Dｅcomposｉtion：Ａ－>Ｂ，C等价于Ａ－>B且A->C属性闭包AtｔrｉbuteClｏsure:根据FＤ推导规则,反复进行闭包运算直到集合没有变化，得到属性F在关系R中的闭包F+假如F+包含了Ｒ的所有属性，则Ｆ是R的超键3．范式ＮoｒｍalForｍs:假如关系Ｒ符合某种范式,说明Ｒ已经回避了某些问题范式可以帮助判断一个关系是否有必要继续分解1NF＞2NF>3NF>ＢCNF逐个严格第一范式1ＮＦ:保证所有属性原子性,数据库表同一列中不能有多个值,即实体中的某个属性不能有多个值或者不能有反复的属性第二范式2NF:在第一范式基础上，规定实体的属性完全依赖于主关键字，不能存在仅依赖主关键字一部分的属性第三范式3ＮF：在第二范式基础上,属性不依赖于其它非主属性即满足:X－>Ａ是平凡函数依赖(X包含于A）或X是超键或A是属性Ｒ的候选键标准化范式BCNＦ:在第三范式基础上,数据库表中不存在任何字段对任一候选关键字段的传递函数依赖则符合第三范式即满足:Ｘ->A是平凡函数依赖(X包含于A)或X是超键即关系Ｒ中没有传递函数依赖满足BCNF的关系中每个元组的每个字段信息都无法被FＤ单独推出４.模式分解ＤｅcｏmｐosiｔionofaＲｅlationScheme：不满足范式的关系可以被分解为多个满足范式的关系，每个关系都是原关系的子集,且它们的并集构成R分解问题:也许有损(连接后不能恢复原关系）需要连接运算检测依赖性部分查询开销增大无损分解:分解成两个关系的属性交集是原关系的键时,该分解无损BCNF分解：ａ.若R不是BCNＦ,其中违反范式的函数依赖是Ｘ-＞A,将R分解为Ｒ－A,和XAb.假如R－Ａ或ＸA不是BCNＦ则继续分解,此时各自的函数依赖是F的投影，而非F分解顺序与结果有关，不唯一,无损分解，也许会丢失一部分未能成功投影的函数依赖3NF分解：方法1：求最小函数覆盖a.所有函数依赖变成标准形式(右边单属性)b.最小化每个依赖的左边,即检查每个依赖内左边的每个属性能否删除c.删除冗余的函数依赖,观测左边比较“大块”的依赖，看删除后F+是否改变。方法2：在最小覆盖的基础上分解a．其中违反范式的函数依赖是X-＞A，将R分解为R-Ａ，和XＡb.假如R-A或ＸＡ不是3ＮＦ则继续分解。c．ａｂ循环完毕后，得到R１,R２,R３…..Rｎ的无损分解,记为Ri,相应的函数依赖投影Fid.标记出原依赖集F中不在Fi并集中的依赖,记为Nｅ．对于每个在N中的依赖X->A，生成XA,然后加入分解后的Rｉ序列,构成无损且保持依赖的分解集。满足范式规定的数据库设计是结构清楚的，同时可避免数据冗余和操作异常这并意味着不符合范式规定的设计一定是错误的，在数据库表中存在1：１或1:N关系这种较特殊的情况下，合并导致的不符合范式规定反而是合理的ｌeｃ13-14事务介绍和并发控制１.并发控制ＣoncｕrreｎcyContｒoｌ：在多用户并发访问时提供对的且可用性高的数据访问崩溃恢复Recoｖery:保证数据库不会由于软件、系统或传输过程犯错而犯错，随时可以访问关键任务数据在数据库磁盘到文献层实现并发控制和容错2.事务Transactiｏn:读写数据库操作的原子序列,每个被完全执行的事务都保证数据库处在一致状态事务管理器ＴｒansａctionManaｇer：控制事务执行,用户程序逻辑对DBＭS不可见,DＢMS仅管理数据读写并发:响应时间Rｅsponｓｅｔｉme：完毕事务的平均时间延迟latency：短事务也许被长事务拖慢，导致不可预估的延迟吞吐量ｔｈrｏughput：一定期间内完毕事务的平均数量，I／O同时进行CPＵ运算可以减少两者的空闲时间事务执行原则：原子性Atomiciｔy：一个事务中所有动作全执行,或全不执行事务在完毕所有动作后,状态变为提交comｍit,否则变为中止aborｔ为保持原子性，执行一半而中止的事务需要取消之前执行的内容一致性Cｏｎsistency:若数据库在事务执行前一致，则在执行后仍保持一致为保持一致性,中止的事务需要额外保存并在有条件的情况下再次执行数据库用ｕｎdo记录中止事务,ｒｅｄo记录中止事务中未执行的部分数据库一致性表达为一组声明性完整性约束IＣ，违反ＩＣ的事务将被中止隔离性Ｉｓｏlａtｉon:一个事务的执行与其他事务的执行相隔离,类似单机操作持久性Durabilｉty：提交的事务持久有效事务调度：事务中各动作的执行顺序,完整的调度涉及每个事务的提交或中止串行调度SerialScｈeｄｕle:每个事务从开始到结束保持运营,没有其他事务操作干预可串行化调度ＳeｒializableScheduｌe:事务等价：包含相同的事务的动作，把DB放在最后一个状态多个事务并发执行的结果与按某一顺序串行地执行它们时的结果相同，则这些事务的集合是可串行化的可串行化的多个事务执行结果也许不同,但所有结果都是可接受的，DBMS不能保证它们中的哪一个是交叉执行的结果未提交的事务也许出现在可串行化事务集合中，但它的作用也许被undo中的记录抵消操作冲突ＣoｎｆlictｉnｇAｃtions:写读冲突：读了未提交的数据读写冲突：不可反复读写写冲突:丢失更新也许引起交叉执行的异常解决:用更简朴的方式检查时间表等价可恢复调度ＲｅcｏverａbleSｃｈeduｌe:事务仅在串行调度的事务集合所有执行完毕后提交假如事务仅读了已提交事务的改变，不仅可以恢复调度，级联中止也可以避免冲突可串行化调度CoｎflictＳeｒialｉzａｂｌeＳｃｈedｕles:两个串行化调度包含相同的一组动作，以同样的方式解决每一对互相冲突的行为,则它们冲突等价若调度和另一些串行化调度冲突等价，则该调度是冲突可串行的一些可串行调度不是冲突可串行的，这是高效执行的代价假如可以通过互换不同的连续的非冲突操作来将原调度转换为串行调度，则原调度是冲突可串行的可串行化调度不一定是冲突可串行化调度3．依赖图ＤｅpeｎdencyGraph/优先图ｐｒeｃｅｄeｎceｇrａph：用于描述在一个调度中动作之间的所有潜在冲突调度的依赖图涉及：每个提交的动作节点从Tｉ到Tｊ的边,假如Ｔi的动作比Tj的动作优先且它们冲突依赖图无环<=>调度是冲突可序列化的两阶段加锁2PL:最常见的实行冲突可序列化的方案，保证冲突可串行性,不能防止级联中止为避免冲突而设立锁,悲观的另一种方案是并发控制，乐观的共享锁：读之前加锁排斥锁：写之前加锁一个行为一旦释放了锁，便不能再加锁严格2ＰL加锁管理LocｋManａgement：解决加锁解锁请求,保持目的对象的加锁状态保存:每个数据对象标记，当前有锁列表，锁的性质,请求加锁解锁的队列收到加锁请求时,鉴定是否已有冲突的锁,若没有则加锁,若有则将请求者放入等待队列升级锁:共享锁的事务可以请求升级为排斥锁死锁Deaｄlocks：等待解决的锁被彼此循环加入等待队列,永远无法解决解决死锁：防止prevｅntiｏn：资源排序检测Detecｔion:创建等待队列的检测图,若成环则死锁避免ａvoidａｎce：根据时间戳分派优先级加锁粒度LockingＧranularitｙ：在数据库/表／页/元组层面加锁多粒度锁：在多个不同层面加锁意向锁：部分读IS/部分写IX/全读Ｓ／全写X多粒度意向锁lec1５故障恢复CraｓｈRecｏvery1.系统重启后的