数据库系统实现习题汇总(共13页).doc

《数据库系统实现习题汇总(共13页).doc》由会员分享，可在线阅读，更多相关《数据库系统实现习题汇总(共13页).doc（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上数据库系统实现复习资料2.2.2习题2.2.2假设Megatron 747磁道的磁头位于磁道4096，即跨越磁道的1/16距离处。假设下一个请求是对一随机磁道上一个块。计算读这个块的平均时间。答案2 平均移动的磁道：（1+2+4096）+（1+2+(65536-4096)）/ 65536 = 28928; 存道时间：1+28928/4000 = 8.232ms; 传输时间 = 0.13ms； 旋转等待时间 = 4.17ms； 所以总的平均时间为 8.232 + 0.13 + 4.17 = 12.532ms；2.7.3假设在习题2.7.1的病人记录上添加另外的可重复字段

2、，表示胆固醇化验，每一次胆固醇化验需要一个24字节的日期和化验的整数结果。如果a）重复化验保存在记录中。b）化验存储在另外一个块中，记录中存储指向化验的指针。分别给出病人记录的格式。1其他首部信息 指向住址 指向病史 记录长度 指向化验 （化验记录）出生日期社会保险号码病人ID姓名住址病史2记录首部信息 姓名的长度 住址的长度 病史的长度 指向姓名 指向住址 指向病史 指向化验 出生日期社会保险号码病人ID （化验记录）姓名住址病史3.1.7如果我们使用一个扩充的倒排索引，如图3-10所示，那我们就能执行许多其他类型的查询。说明如何使用这种索引去找到：a)“cat”和“dog”彼此相距不超过5

3、个位置并且出现在同一类元素（如标题、正文或锚）中的文档。b)“cat”后刚好隔一个位置就跟有“dog”的文档。c)题目中同时出现“dog”和“cat”的文档。A.获得所有的桶条目“猫”和“狗”。通过类型分类这些条目,在类型中通过位置进行分类。扫描记录,保持一个“窗口”,记录当前的类型。在当前类型上延长到五个位置之前。拿所有的新记录和当前窗口中的记录作比较。如果我们找到一个条目:(1)有相反的词,比如“狗”，如果当前记录为“猫”,和(2)有相同的文档条目。那么这个文档就是我们想要检索的。B.获得所有的桶条目“狗”。通过位置分类这些条目。扫描记录,保持一个“窗口”,记录一个位置之前的当前位置。拿新

4、记录和当前窗口中的记录作比较。如果我们找到一个:记录(1)有相反的词“猫”,和(2)有相同的文档条目。那么这个文档是我们想要检索的。C.我们沿着指针与“猫”来找到这个词的出现。选择从与猫有关的桶文件指针开始找，“猫”的类型是“标题”。然后同样我们找出桶条目“狗”的指针。如果这两套指针相交,这个文档就是满足我们条件的。答案23.1.7A找到所有包含“cat”和“dog”的文档的指针集，然后按类型分类，然后按位置分类。选择其中相距不超过5个位置且键值相反的记录，即满足条件。B找到所有包含“dog”的文档指针列表，然后再按位置分类，找出所有指示位置信息的指针列表，记录所有指针往前移动两个位置的位置信

5、息。然后求得所有包含“cat”的文档的位置指针列表，与刚才的位置信息的交集即满足条件。C从桶文件中选择有“cat”出现且类型为“标题”的文档指针。接着，找到“dog”的桶中项目，并从中选择类型为“标题”的文档指针。求两个指针集相交，就得到满足条件的文档。3.2.6在例3.17中我们提出，如果我们使用更复杂的维护内部结点键的算法，那么可以从右（或左）边的非兄弟结点中借键。描述一个合适的算法，它可以通过从同层相邻结点中借键来重新达到平衡，而不管这些相邻结点是否是键-指针对太多或太少的结点的兄弟结点。1、如果node的节点数大于等于min+1，删除key,到52、如果node相邻左节点的节点数大于等

6、于min+1，从node左节点借值key，将node的root值改为key，到53、如果node相邻右节点的节点数大于等于min+1，从node右节点借值key，将node的root值改为key，到54、删除key，与其左节点合并，node=root到15、结束3.3.5假定键散列为4位序列，就像这一部分中可扩展散列表和线性散列表的例子一样。但是，假定块中可存放三个记录而非两个记录。如果开始时散列表中有两个空存储块（对应于0和1），请给出插入键值如下的记录后的结构：a)1111，1110，0000，且散列方法是可扩展散列b）1111，1110，0000，且散列方法是线性散列，其充满度阈值为75

7、%。c)0000，0001，1111，且散列方法是可扩展散列。d)0000，0001，1111，且散列方法是线性散列，其充满度阈值为100%。(a) i=3 (c)、与(a)的结构相同，当然顺序可以升序也可以降序(d)、与(b)的相同，顺序也可以反过来。3.3.7实际中有些散列函数并不像理论上那样好。假定我们在整数键值i上定义一个散列函数h(i)=i2mod B，其中B表示桶数。a)如果B=10，该散列函数会出现什么问题？b)如果B=16，该散列函数又有什么好处？c)该散列函数对哪些B值有用？答案1（1） B=10时散列函数值=0,1,4,5,6,9，其中桶2,3,7,8的空间就被浪费掉了，没

8、有键值存进去，然后桶1,4,6,9这四个桶要记录双倍的键值（2）B=16时散列函数值=0,1,4,9所有的键值均匀分布在这四个桶中，方便集中管理（3）B=2幂或其开方仍为整数3.5.2选择一个分段散列函数，且速度、内存和硬盘大小三属性各为一位二进制数，使它能很好地划分图3-36中的数据。3.6.2把图3-36的数据放到一棵kd-树中。假定每块能存放两个记录，给每一层挑选一个使数据划分尽可能均匀的划分值。分裂属性的顺序选择：a)速度，然后内存，再交替;b)速度，然后内存，最后硬盘，再交替;c)不论什么属性，只要它在每个结点产生最均匀的分裂。第三问不会，需要讨论6.1.2对习题6.1.1中的每个事

9、务，在计算中加入读写动作，并给出各步骤对主存和磁盘产生的影响。假设最初A=50且B=25.此外，请说明当OUTPUT动作顺序恰当时，是否可能即使在事务的执行过程中发生了故障，一致性仍能得到保持。6.1.1事务：a) B:=A+B;A:=A+B;b)A:=B+1;B:=A+1;c)A:=A+B;B:=A+B; a)动作t内存中的A内存中的B磁盘中的A磁盘中的BREAD(B,t1)25255025READ(A,t2)5050255025t1:=t2+t17550255025WRITE(B,t1)7550755025t2:=t2+t112550755025WRITE(A,t2)12512575502

10、5Output（B,t1)75125755075Output(A,t2)1251257512575b)动作t内存中的A内存中的B磁盘中的A磁盘中的BREAD(A,t1)50505025READ(B,t2)2550255025t1:=t2+12650255025WRITE(A,t1)2626255025t2:=t1+12726255025WRITE(B,t2)2726275025Output（A,t1)2626272625Output(B,t2)2726272627c)动作t内存中的A内存中的B磁盘中的A磁盘中的BREAD(A,t1)50505025READ(B,t2)2550255025t1:

11、=t1+t27550255025WRITE(A,t1)7575255025t2:=t1+t210075255025WRITE(B,t2)100751005025Output（A,t1)75751007525Output(B,t2)1007510075100如果OUTPUT动作顺序恰当，即使在事务执行过程中发生故障，一致性仍能得到保持。6.2.3下面是两个事务T和U的一系列日志记录：;。请描述恢复管理器的行为，包括对磁盘和日志所作的改变，假设故障发生且出现在磁盘上的最后一条日志记录为：a) b) c) d)答案1若题目是:; ; .则答案是a) 首先扫描日志,发现事务T和U都未commit,将其

12、连接到未完成事务列.按照未完成事务列,从后往前逐步扫描日志并执行undo操作，按照将磁盘中A值写为10,将和写入日志中并刷新日志。b) 首先扫描日志,发现事务T已经commit，将其连接到已完成事务列,事务U未完成，将其连接到未完成事务列。按照未完成事务列，从后往前扫描日志执行undo操作，按照将磁盘中C值写为30，将磁盘A值写为10。将写入日志中并刷新日志。c) 首先扫描日志,发现事务T已经commit，将其连接到已完成事务列,事务U未完成，将其连接到未完成事务列。按照未完成事务列从后往前扫描日志执行undo操作，按照将磁盘中E值写为50，将磁盘中C值写为30，将磁盘A值写为10。将写入日志

13、中并刷新日志。d)首先扫描日志,发现事务T、U已经commit，将其连接到已完成列，未完成列为空，不做任何操作。6.2.4对于习题6.2.3描述的每种情况，T和U所写的哪些值必然出现在磁盘上？哪些值可能出现在磁盘上？6.3.2使用习题6.2.7的数据，对该习题中（a）到（e）的各个位置回答：I：何时能写入记录Ii：对每一个可能发生的故障的时刻，为了找到所有可能未完成的事务，我们需要在日志中向后看多远。请考虑记录在崩溃发生以前写入和未写入的两种情况。习题6.2.7数据：日志记录序列：;假设在如下日志中的某一条写入后立即开始一个非静止检查点：A)B)C)D)E)第一问1在a）后写入START CK

14、PT时，此时，只有s是活跃的，在后写入记录；2.在b）后写入START CKPT时，此时，只有T是活跃的，在后写入记录；3.在C）后写入START CKPT时，此时，只有U、T都是活跃的，在后写入录；4.在d）后写入START CKPT时，此时，只有U、T、V都是活跃的，在后写入记录；5.在e）后写入START CKPT时，此时，只有T、V都是活跃的，在后写入录；第二问1、 在a）处，如果记录在崩溃前写入的话，此时需要在日志中向后看到记录；如果记录在崩溃后写入的话，此时需要在日志中向后看到记录;2. 在b）处，如果记录在崩溃前写入的话，此时需要在日志中向后看到记录；如果记录在崩溃后写入的话，此

15、时需要在日志中向后看到记录;3. 在C）处，如果记录在崩溃前写入的话，此时需要在日志中向后看到记录；如果记录在崩溃后写入的话，此时需要在日志中向后看到记录;4、在d）处，如果记录在崩溃前写入的话，此时需要在日志中向后看到记录；如果记录在崩溃后写入的话，此时需要在日志中向后看到记录;5、在e）处，如果记录在崩溃前写入的话，此时需要在日志中向后看到记录；如果记录在崩溃后写入的话，此时需要在日志中向后看到记录;6.4.2下面是两个事务T和U的一系列日志记录：;。描述恢复管理器的行为，包括对磁盘和日志所作的改变，假设故障发生且出现在磁盘上的最后一条日志记录如下：a） b) c） d）答案1：a）首先扫

16、描日志，发现事务U、T均未commit，将其连接到未完成列。按照未完成列，从后往前逐步扫描日志并执行undo操作，按照将磁盘中A值写为10.b）首先扫描日志，发现事务T已为commit而U未commit，故将T连接到已完成列而U连接到未完成列。按照未完成列，从后往前扫描日志，按照将磁盘中C写为30，将磁盘中A值写为10。按照已完成列，从前往后扫描日志，按照将磁盘中B写为21，将磁盘中D写为41.c) 最后一条记录为这时我们为E往磁盘上写入值51，但是崩溃在记录到达前发生，则E在磁盘上的值为50。d) 最后一条记录为，这时U被认为是已提交的事务。我们为E往磁盘上写入值51，E已经具有值51。7.

17、2.5对一下的每个调度：w3(A);r1(A);w1(B);r2(B);w2(C);r3(C);r1(A);r2(A);w1(B);w2(B);r1(B);r2(B);w2(C);w1(D);r1(A);r2(A);r1(B);r2(B);r3(A);r4(B);w1(A);w2(B);r1(A);r2(A);r3(B);w1(A);r3(C);r2(B);w2(B);w1(C);r1(A);w1(B);r2(B);w2(C);r3(C);w3(A);回答如下问题：I：调度的优先图是什么；Ii：调度是冲突可串行化的吗？如果是，等价的串行调度有哪些；Iii：是否有等价的调度（不管事务对数据做什么

18、），但又不是冲突等价的？7.2.5(i)每一个调度的优先图如下所示：a)b)12c)d)321e) (ii)由优先图的定义知，存在环路的优先图是不能串行化的。从(i)调度知a)，b)，c)均不是冲突可串行化的，而调度d)、e)是冲突可串行化的并且与其等价的串行调度有：（T3，T2，T1）、（T1，T2，T3）。（iii）在上述调度中没有等价的调度同时又不是冲突等价的。7.4.2对下面的每个调度，在每个动作前插入适当的锁（读，写或增量），并在事务末尾插入解锁动作。然后说明该调度在一个支持这三类锁的调度器上运行时会发生什么。r1(A);r2(B);inc1(B);inc2(A);w1(C);w2(

19、D);inc1(A);inc2(B);inc1(B);inc2(C);w1(C);w2(D);r1(A);r2(B);inc1(B);inc2(C);w1(C);w2(D)答案暂定为此，有待修改，详见明日终稿a)sl1(A);r1(A);sl2(B);r2(B);il1(B);inc1(B);u1(B);u1(A);il2(A);inc2(A);u2(A);xl1(C);r1(C);w1(C);u1(C); xl2(D);r2(D);w2(D);u2(D);T1:读A，增加B；写CT2:读B，增加A；写Db)Il1(A);inc1(A);u1(A);il2(B);inc2(B);u2(B);i

20、l2(C);inc2(C);u2(C);xl1(C);r1(C);w1(C);u1(C); xl2(D);r2(D);w2(D);u2(D); T1:增加A，写CT2增加B，增加C；写Dc)sl1(A);r1(A);sl2(B);r2(B);il1(B);inc1(B);u1(B);il2(C);inc2(C);u2(C);xl1(C);r1(C);w1(C);u1(C); xl2(D);r2(D);w2(D);u2(D);T1:读A，增加B；写CT2:读B，增加C；写D7.7.1假设我们在图3-13中的B-树上执行下列动作。如果我们使用树协议，什么时候我们可以释放各个被搜索节点上的写锁：插入

21、4 b）插入30 c）删除37 d）删除7a)l(A),l(B),u(A),l(D),调整D，将其分裂为（2、3、 ）和（4、5、 ），将B调整为（4、7、 ），u(B),u(D)b)l(A),l(C),u(A),l(G),将30写入节点H，u(C),u(G)c) l(A),l(C),u(A),l(H),在H中删除37、41向前移动一位，u(C),u(H)d) l(A),l(B),u(A),l(F),将D中7删除，将11合并到E中（4、5、11），将B修改为（4、 、 ），u(C),u(F)a) 首先到达根节点，这时需要把根节点锁住，但插入4不需要修改根节点，于是往下走到左子树并获取7所在的左

22、子树的锁，同时释放根节点的写锁。因为插入4，所以7所在的左子树需要调整，于是锁先不能释放，同时锁住（2、3、5）所在的左子树，并进行调整，拆分成（2、3、 ） 和（4、5、 ）， 同时调整7所在的左子树，调整完后释放7所在的左子树和2、3、5所在的左子树。b). 首先到达根节点，因为根节点不需要修改，于是释放根节点的锁，并且获取（23、31、43）所在的右子树的锁，但该节点也不需要调整，于是再向下获取（23、29、 ）所在的节点的锁，同时释放父节点的写锁，插入完30后，释放该节点的写锁。c）删除37我们每到达一个节点时，都先对其加写锁、首先到达根节点（13. . ）根节点不需要修改。考虑其右节

23、点（23.31.43），我们发现此节点，在删除一个元素之后不为空，因此没有理由去改变根节点，所以当即释放根节点的写锁我们走到第三排的叶子节点（31.37.41），发现删除37后，叶子节点也不为空，所以没有理由去改写（23.31.43）所以我们可以解开节点（23.361.43）的写锁当且仅当我们对叶子节点（31.37.41）完成删除操作时，释放其写锁d）删除7我们每到达一个节点时，都先对其加写锁、首先到达根节点（13. . ），根节点不需要修改，释放跟节点的写锁。考虑其左节点（7. . ），对当前节点可能造成修改，所以暂不释放（7， ， ）写锁，继续找到叶子节点（7,.11. ）完成对7的删除，当即解除对叶子节点的写锁，对父节点进行平衡调整，将11写入到原父节点，释放原父节点的写锁。专心-专注-专业