数据库系统习题评讲期末复习

数据库系统

习题评讲&期末复习1数据库模型和数据库开发过程2需求分析数据流图3概念模型设计E-R模型4逻辑模型设计关系模式及其优化5数据库实现关系代数、SQL6数据物理存储7索引与散列8查询处理与优化9事物机制10并发控制11恢复系统知识框架6数据物理存储7索引与散列8查询处理与优化9事物机制10并发控制11恢复系统知识框架10.4考虑从图10-6的文件中删除记录5。比较下列实现删除的技术的相对优点：移动记录6到记录5所占用的空间，然后移动记录7到记录6所占用的空间。移动记录7到记录5所占用的空间。标记记录5被删除，不移动任何记录。数据存储33456GoldPhysics8700045565KatzComp.Sci.7500058583CalifieriHistory62000记录5记录6记录710.4考虑从图10-6的文件中删除记录5。比较下列实现删除的技术的相对优点：a.移动记录6到记录5所占用的空间，然后移动记录7到记录6所占用的空间。移动了最多的记录，进行了多次数据存取（access）b.移动记录7到记录5所占用的空间。移动了少量记录，但是破坏了文件内数据的排序c.标记记录5被删除，不移动任何记录。没有移动任何数据，但是需要额外的开销来记录文件中空闲空间。这种方式会导致文件中出现很多空洞（holes），长此以往会降低存储效率和查询性能。数据存储67…476…4567467410.18在顺序文件组织中，为什么即使当前只有一条溢出记录，也要使用一个溢出块？数据存储10.18在顺序文件组织中，为什么即使当前只有一条溢出记录，也要使用一个溢出块？由于文件被组织成物理块的形式，当数据块放满时，只能再申请一个溢出块存放这个记录。数据存储33456GoldPhysics8700045565KatzComp.Sci.7500058583CalifieriHistory6200050000AMusic60000搜索码搜索码链表溢出块文件中记录的组织：堆文件组织：一条记录可以放在文件中的任何地方，记录没有顺序。顺序文件组织：记录根据“搜索码”的值顺序存储。搜索码是任何一个属性或者属性的集合。散列文件组织：在每条记录的某个属性上计算一个散列函数，来确定记录放到文件的哪个块中。1数据库模型和数据库开发过程2需求分析数据流图3概念模型设计E-R模型4逻辑模型设计关系模式及其优化5数据库实现关系代数、SQL6数据物理存储7索引与散列8查询处理与优化9事物机制10并发控制11恢复系统知识框架11.3用下面的关键码值集合建立一个B+树（2,3,5,7,11,17,19,23,29,31）假设树初始为空，值按上升顺序加入。根据一个结点所能容纳指针数的下列情况分别构造B+树。468索引与散列search-keyvalueB+树索引搜索码值指针B+树索引235（2,3,5,7,11,17,19,23,29,31）2357523575111117空的结点按照B+树的准则插入数据结点满，创建新的结点（2,3,5,7,11,17,19,23,29,31）索引与散列11.17对习题11.3中的每一棵B+树，给出下列查询中涉及的步骤：找出搜索码值为11的记录索引与散列B+树索引Findrecordwithsearch-keyvalueV.（搜索算法）C=rootWhileCisnotaleafnode{1）

Letibeleastvalues.t.满足

V

Ki.2）

Ifnosuchexists,setC=lastnon-nullpointerinC

3）

Else{if(V=Ki)SetC=Pi+1else

setC=Pi}}取右方指针取左方指针Letibeleastvalues.t.Ki=V(inC)Ifthereissuchavaluei,followpointerPi

tothedesiredrecord.Elsenorecordwithsearch-keyvaluekexists.tothedesiredrecord①②③11.17对习题11.3中的每一棵B+树，给出下列查询中涉及的步骤：找出搜索码值为11的记录索引与散列11.6假设我们在一个文件上使用可扩充散列，该文件所含记录的搜索码值如下：2、3、5、7、11、17、19、23、29、31如果散列函数为h(x)=xmod8，且每个桶可以容纳3条记录。给出此文件的可扩充散列结构。索引与散列可扩充散列，与静态散列对比，是一种动态散列的方式为桶引入了一个间接层，即用一个指向块的指针数组来表示桶，而不是用数据块本身组成的数组来表示桶。索引与散列h(x)的前i位共同的散列前缀长度文件所含记录的搜索码值：2、3、5、7、11、17、19、23、29、31散列函数为h(x)=xmod8，且每个桶可以容纳3条记录索引与散列搜索码值2357111719232931h(x)2357313757h(x)二进制0100111011110110010111111011110··1··12(010)3(011)11(011)5(101)7(111)1100··01··10··11··217(001)5(101)7(111)122(010)3(011)11(011)2桶分裂成两个前缀位数+117(001)插入搜索码值17索引与散列000001010011100101110111317(001)23(011)11(011)19(011)35(101)7(111)12(010)3搜索码值1719232931h(x)13757h(x)二进制001011111101111插入搜索码值19可扩充散列结果11.20在散列文件组织中导致桶溢出的原因是什么？如何减少桶溢出的发生？索引与散列11.20在散列文件组织中导致桶溢出的原因是什么？如何减少桶溢出的发生？如果桶没有足够的空间，就会发生桶溢出。桶溢出发生的几个原因：桶不足：桶数目的选择必须满足n>总记录数N/每个桶的容量f偏斜：由于多个记录可能具有相同的搜索码，或者所选的散列函数造成搜索码分布不均，导致某些桶分配到的记录比其他桶多。即使其他桶有空间，某个桶仍有可能溢出。解决：桶的数目选为(N/f)*(1+d)，d常取0.2，即大约20%的空间是空的。溢出桶索引与散列桶1溢出桶1溢出桶2桶0···1数据库模型和数据库开发过程2需求分析数据流图3概念模型设计E-R模型4逻辑模型设计关系模式及其优化5数据库实现关系代数、SQL6数据物理存储7索引与散列8查询处理与优化9事物机制10并发控制11恢复系统知识框架12.2考虑图12-13中银行数据库的例子，其中主码以下划线标出。考虑下面的SQL语句： selectT.branch_name frombranchT,branchS whereT.assets>S.assetsandS.branch_city=“Brooklyn”写出一个与此等价的、高效的关系代数表达式，并论证你的选择。查询处理12.2考虑图12-13中银行数据库的例子，其中主码以下划线标出。考虑下面的SQL语句： selectT.branch_name frombranchT,branchS whereT.assets>S.assetsandS.branch_city=“Brooklyn”写出一个与此等价的、高效的关系代数表达式，并论证你的选择。查询优化一般规则：尽量减少中间结果选择连接次序尽早执行选择和投影运算查询处理selectT.branch_namefrombranchT,branchSwhereT.assets>S.assetsandS.branch_city=“Brooklyn”查询处理ΠT.branch_nameσ

T.assets>S.assets∧S.branch_city=“Brooklyn”branchTbranchSΠT.branch_nameΠbranch_name,assetsΠassetsσ

S.branch_city=“Brooklyn”branchTbranchST.assets>S.assets查询处理12.3设关系r1(A,B,C)，r2(C,D,E)有如下特性：r1有20000个元组，r2有45000个元组，一块中可容纳25个r1元组或者30个r2元组。估计使用以下连接策略计算r1r2需几次块传输和磁盘搜索。a.嵌套循环连接b.块嵌套循环连接r1需要20000/25=800块，r2需要45000/30=1500块。连接r1r2，n是r中的元组数，b是r中元组的磁盘块数a.对于嵌套循环连接，需n1*b2+b1次块传输，n1+b1次磁盘搜索b.对于块嵌套循环连接，需b1*b2+b1次块传输，2*b1次磁盘搜索假设r1是外循环：a.20000*1500+800=30000800次块传输，20000+800=20800次磁盘搜索b.800*1500+800=1200800次块传输，2*800=1600次磁盘搜索查询处理连接r1r2，n是r中的元组数，b是r中元组的磁盘块数a.对于嵌套循环连接，需n1*b2+b1次块传输，n1+b1次磁盘搜索b.对于块嵌套循环连接，需b1*b2+b1次块传输，2*b1次磁盘搜索元组0元组1元组2元组3…元组n1元组0元组1元组0元组1元组2元组3…元组n1元组0元组1元组2元组3块0块0块1块0块1…块0块1…块0块0块1磁盘内存块对块0块1块b1n1块0块1块b2块传输：r1需b1次，r2需n1*b2次磁盘搜索：r1需b1次，r2需n1*1次块传输：r1需b1次，r2需b1*b2次磁盘搜索：r1需b1次，r2需b1*1次嵌套循环连接块嵌套循环连接b1b212.6考虑12-13的银行数据库，其中主码用下划线标出。假设关系branch在branch_city属性上有B+树索引，此外别无其他索引。列出处理下列包含取反运算的选择操作的不同的方法。σ¬(branch_city<“Brooklyn”)(branch)查询处理12.6考虑12-13的银行数据库，其中主码用下划线标出。假设关系branch在branch_city属性上有B+树索引，此外别无其他索引。列出处理下列包含取反运算的选择操作的不同的方法。σ¬(branch_city<“Brooklyn”)(branch)查询处理由branch_city属性上的B+树索引找到搜索码为“Brooklyn”的元组。从该元组开始，沿着指针链就可找到branch_city>=“Brooklyn”的所有元组。13.6假设关系department在building属性上有B+树索引，此外别无其他索引。处理下列包含否定条件的选择操作的最佳方法是什么？

a.σ¬(building<“Watson”)(department)13.4考虑关系r1(A,B,C)，r2(C,D,E)和r3(E,F)，它们的主码分别为A、C、E。假设r1有1000个元组，r2有1500个元组，r3有750个元组。估计r1连r2连r3的大小，给出一个有效的计算这个连接的策略。查询优化（1）由于连接运算满足交换律，r1、r2、r3不论以何种顺序连接，结果都是一样的。因此考虑((r1r2)r3：r1与r2连接得到一个1000元组的关系r12（C是r2的主码）r12与r3连接得到一个1000元组的关系r123（E是r3的主码）因此最终的连接结果有1000个元组。（2）在r2上对C属性建立索引，在r3上对E属性建立索引。然后对r1的每一个元组：以r2.C索引，在r2钟找到一个（最多找到一个）与r1中C匹配的元组；以r3.E索引，在r3中找到一个（最多找到一个）与r2中E匹配的元组。13.7考虑查询 select

* fromr,s whereupper(r.A)=upper(s.A);其中“upper”是个函数，该函数返回输入参数中所有小写字母替换成相应大写字母后的结果。b.有些数据库系统对这个查询会采用非常低效的（块）嵌套循环连接。简单解释对于该查询，如何使用散列连接或者归并连接。查询优化select

*fromr,swhereupper(r.A)=upper(s.A);查询优化ABa1C2b3d4ACc5A6r：s：ABA1C2B3D4ACC5A6ABA1B3C2D4ACA6C5prps012012h(A)=Amod3散列连接归并连接①upper(A)；②按连接属性散列；③对r中的每个元组利用散列索引找出可与其连接的s中元组①upper(A)；②按连接属性排序；④移动pr、ps指针寻找属性值相同元组连接1数据库模型和数据库开发过程2需求分析数据流图3概念模型设计E-R模型4逻辑模型设计关系模式及其优化5数据库实现关系代数、SQL6数据物理存储7索引与散列8查询处理与优化9事物机制10并发控制11恢复系统知识框架14.6考虑图14-16所示的优先图，相应的调度是冲突可串行化的吗？解释你的回答。事务机制若一个调度S与串行调度冲突等价，称调度S是冲突可串行化的。14.6考虑图14-16所示的优先图，相应的调度是冲突可串行化的吗？解释你的回答。事务机制若一个调度S与串行调度冲突等价，称调度S是冲突可串行化的。题中的调度是冲突可串行化的，因为该调度优先图是无环的。如：T1,T2,T3,T4,T5或者：T1,T2,T4,T3,T5依次去掉“仅有出弧”的事务节点14.12列出ACID特性，解释每一特性的用途。事务机制14.12列出ACID特性，解释每一特性的用途。原子性Atomicity事务的所有操作要么全部正确执行，要么不执行一致性Consistency隔离执行事务时，保持数据库的一致性隔离性Isolation让事务感觉不到其他事务在并发执行（避免并发执行导致的不一致状态）持久性Durability一个事务完成后，对数据库的改变的永久的，即使出现故障事务机制14.15考虑以下两个事务：T13: read(A); read(B); IfA=0thenB:=B+1; write(B);T14: read(B); read(A); ifB=0thenA:=A+1; write(A);设置一致性需求为A=0或B=0，初值是A=B=0。b.给出T13和T14的一次并发执行，执行产生不可串行化调度。事务机制14.15设置一致性需求为A=0或B=0，初值是A=B=0。给出T13和T14的一次并发执行，执行产生不可串行化调度。事务机制T13T14read(A);read(B);IfA=0thenB:=B+1;write(B);B=1A=0A=0A=0B=0B=1read(B);read(A);ifB=0thenA:=A+1;write(A);T13T14read(A);read(B);IfA=0thenB:=B+1;B=0A=0A=1write(B);A=0B=0B=1read(B);read(A);ifB=0thenA:=A+1;write(A);串行化调度T13T14非不可串行化调度对同一数据的读写操作冲突14.16给出两个事务的一个串行化调度的例子，其中事务的提交顺序与串行化序列不同。事务机制T1T2read(A);A:=A+1;A:=A+1;write(A);commit;read(B);B:=B+1;write(B);commit;可串行化为T1T2，因无任何冲突操作（不存在对同一数据项的读写操作）。串行化顺序与事务提交次序不同。T1T2read(A);A:=A+1;A:=A+1;write(A);commit;read(B);B:=B+1;write(B);commit;1数据库模型和数据库开发过程2需求分析数据流图3概念模型设计E-R模型4逻辑模型设计关系模式及其优化5数据库实现关系代数、SQL6数据物理存储7索引与散列8查询处理与优化9事物机制10并发控制基于锁的协议、基于时间戳的协议等11恢复系统知识框架15.2考虑下面两个事务：T34: read(A); read(B); ifA=0thenB:=B+1; write(B);T35: read(B); read(A); ifB=0thenA:=A+1; write(A);给事务T34与T35增加加锁、解锁指令，使它们遵从两阶段封锁协议。这两个事务会引起死锁吗？并发控制两阶段封锁协议：1.增长阶段：事务可以获得锁，但不能释放锁；2.缩减阶段：事务可以释放锁，但不能获得新锁。——保证冲突可串行化，不保证不发生死锁a.Lockandunlockinstructions:T34: lock-S(A) read(A)

lock-X(B) read(B) ifA=0 thenB:=B+1 write(B)

unlock(A) unlock(B)b.有可能发生死锁。如：T35: lock-S(B) read(B)

lock-X(A) read(A) ifB=0 thenA:=A+1 write(A)

unlock(B) unlock(A)等待T35释放对资源B的共享锁等待T34释放对资源A的共享锁T34T35lock-S(A)read(A)lock-X(B)lock-S(B)read(B)lock-X(A)15.3强两阶段封锁协议带来什么好处？它与其他形式的两阶段封锁协议相比有何异同？并发控制两阶段封锁协议的两种变体严格两阶段封锁协议：除了要求封锁是两阶段之外，还要求事务持有的所有排他锁必须在事务提交之后方可释放。这个要求保证未提交事务所写的任何数据在该事务提交之前均以排他方式加锁，防止其他事务读取这些数据；强两阶段封锁协议：它要求事务提交之前不得释放任何锁。它旨在让冲突的事务尽可能地串行执行，这样的话，调度中的事务可以按其提交的顺序串行化。1数据库模型和数据库开发过程2需求分析数据流图3概念模型设计E-R模型4逻辑模型设计关系模式及其优化5数据库实现关系代数、SQL6数据物理存储7索引与散列8查询处理与优化9事物机制10并发控制11恢复系统知识框架16.1请解释为什么undo-list中事务的日志记录必须有后往前进行处理，而redo-list中事务的日志记录必须由前往后进行处理。

并发控制如对一个单一的事务做undo。假设一个数据项在这个事务中被修改了多次，首先从1修改为2，又从2修改为3。如果undo-list的日记记录从前往后处理，那么最后这个数据项的值会被恢复为2。而从后往前处理，结果是1，这才是希望恢复到的结果。对多个事务进行undo，同理。同样的例子，假设事务已提交，对其进行redo。若从后往前执行，结果是2（不正确的）；若从前往后执行，结果是3（正确的）。16.5假设在数据库中使用延迟修改技术。更新日志记录中的旧值还需要吗？为什么？并发控制不需要。如果事务已经提交，那么旧值就不再需要了，因为已提交的事务不再进行undo操作；如果事务没有提交，如在执行过程中遇到系统崩溃，那么旧值依然会保存在稳定的存储中，并没有被修改。延迟修改技术：通过在日志记录中记录所有数据库修改，将一个事物的所有write操作拖延到事务部分提交时才执行，来保证事务的原子性。复习BCNF分解3NF分解BCNF满足以下条件之一αβ是平凡的函数依赖α是模式R的一个超码3NF满足以下条件之一αβ是平凡的函数依赖α是模式R的一个超码β-α中的每个属性A都包含在R的一个候选码中BCNF保持无损连接3NF保持无损连接，且保持函数依赖BCNF&3NF8.19给出模式R的一个BCNF分解和3NF分解。R=(A,B,C,D,E)函数依赖集F：ABCCDEBDEABCNF&3NFR的超码是A,E,CD,BCBD中B不是R的超码，R不满足BCNF

=>将R分解为R1(B,D)和R2(A,B,C,E)R1上的函数依赖F1={BD}，满足BCNFR2上的函数依赖F2={ABC,EA}ABC中A不是R2的超码，不满足BCNF=>将R2分解为R3(A,B,C)和R4(A,E)R3上的函数依赖F3={ABC}，满足BCNFR2上的函数依赖F4={EA}，满足BCNFR的BCNF分解为：(B,D)(A,B,C)(A,E)BCNF&3NF8.19给出模式R的一个BCNF分解和3NF分解。R=(A,B,C,D,E)函数依赖集F：ABCCDEBDEAABC=>AB,ACAB,BD=>ADACD,CDE=>AE=>AABCDEEA=>EABCDECDE=>CDABCDEBD=>BCCD=>BCABCDER的候选码是A,E,CD,BC。R=(A,B,C,D,E)F：ABCCDEBDEABCNF&3NFR的超码是A,E,CD,BCBD中B不是R的超码，R不满足BCNF

=>将R分解为R1(B,D)和R2(A,B,C,E)R1上的函数依赖F1={BD}，满足BCNFR2上的函数依赖F2={ABC,EA}ABC中A不是R2的超码，不满足BCNF=>将R2分解为R3(A,B,C)和R4(A,E)R3上的函数依赖F3={ABC}，满足BCNFR2上的函数依赖F4={EA}，满足BCNFR的BCNF分解为：(B,D)(A,B,C)(A,E)BCNF&3NF8.19给出模式R的一个BCNF分解和3NF分解。R=(A,B,C,D,E)函数依赖集F：ABCCDEBDEABCNF&3NF8.19给出模式R的一个BCNF分解和3NF分解。R=(A,B,C,D,E)函数依赖集F：ABCCDEBDEA没有需要合并的函数依赖没有无关属性Fc=F={ABC,CDE,BD,EA}计算正则覆盖FcFc=Frepeat

合并ab1,ab2为ab1b2

删除ab中的无关属性untilFc不变---------