数据库系统实现习题汇总

WORD格式--可编辑--专业资料完整版学习资料分享《数据库系统实现》复习资料2.2.2 22.7.3 23.1.7 33.2.6 53.3.5 53.3.7 73.5.2 83.6.2 96.1.2 106.2.3 116.2.4 136.3.2 146.4.2 157.2.5 167.4.2 187.7.1 182.2.2习题2.2.2假设Megatron747磁道的磁头位于磁道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的病人记录上添加另外的可重复字段，表示胆固醇化验，每一次胆固醇化验需要一个24字节的日期和化验的整数结果。如果a）重复化验保存在记录中。b）化验存储在另外一个块中，记录中存储指向化验的指针。分别给出病人记录的格式。1其他首部信息指向住址指向病史记录长度指向化验（化验记录）出生日期社会保险号码病人ID姓名住址病史2记录首部信息姓名的长度住址的长度病史的长度指向姓名指向住址指向病史指向化验出生日期社会保险号码病人ID（化验记录）姓名住址病史3.1.7如果我们使用一个扩充的倒排索引，如图3-10所示，那我们就能执行许多其他类型的查询。说明如何使用这种索引去找到：a)“cat”和“dog”彼此相距不超过5个位置并且出现在同一类元素（如标题、正文或锚）中的文档。b)“cat”后刚好隔一个位置就跟有“dog”的文档。c)题目中同时出现“dog”和“cat”的文档。A.获得所有的桶条目“猫”和“狗”。通过类型分类这些条目,在类型中通过位置进行分类。扫描记录,保持一个“窗口”,记录当前的类型。在当前类型上延长到五个位置之前。拿所有的新记录和当前窗口中的记录作比较。如果我们找到一个条目:(1)有相反的词,比如“狗”，如果当前记录为“猫”,和(2)有相同的文档条目。那么这个文档就是我们想要检索的。B.获得所有的桶条目“狗”。通过位置分类这些条目。扫描记录,保持一个“窗口”,记录一个位置之前的当前位置。拿新记录和当前窗口中的记录作比较。如果我们找到一个:记录(1)有相反的词“猫”,和(2)有相同的文档条目。那么这个文档是我们想要检索的。C.我们沿着指针与“猫”来找到这个词的出现。选择从与猫有关的桶文件指针开始找，“猫”的类型是“标题”。然后同样我们找出桶条目“狗”的指针。如果这两套指针相交,这个文档就是满足我们条件的。答案23.1.7A>找到所有包含“cat”和“dog”的文档的指针集，然后按类型分类，然后按位置分类。选择其中相距不超过5个位置且键值相反的记录，即满足条件。B>找到所有包含“dog”的文档指针列表，然后再按位置分类，找出所有指示位置信息的指针列表，记录所有指针往前移动两个位置的位置信息。然后求得所有包含“cat”的文档的位置指针列表，与刚才的位置信息的交集即满足条件。C>从桶文件中选择有“cat”出现且类型为“标题”的文档指针。接着，找到“dog”的桶中项目，并从中选择类型为“标题”的文档指针。求两个指针集相交，就得到满足条件的文档。3.2.6在例3.17中我们提出，如果我们使用更复杂的维护内部结点键的算法，那么可以从右（或左）边的非兄弟结点中借键。描述一个合适的算法，它可以通过从同层相邻结点中借键来重新达到平衡，而不管这些相邻结点是否是键-指针对太多或太少的结点的兄弟结点。1、如果node的节点数大于等于min+1，删除key,到52、如果node相邻左节点的节点数大于等于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%。c)0000，0001，……1111，且散列方法是可扩展散列。d)0000，0001，……1111，且散列方法是线性散列，其充满度阈值为100%。(a)i=3(c)、与(a)的结构相同，当然顺序可以升序也可以降序(d)、与(b)的相同，顺序也可以反过来。3.3.7实际中有些散列函数并不像理论上那样好。假定我们在整数键值i上定义一个散列函数h(i)=i2modB，其中B表示桶数。a)如果B=10，该散列函数会出现什么问题？b)如果B=16，该散列函数又有什么好处？c)该散列函数对哪些B值有用？答案1B=10时散列函数值=0,1,4,5,6,9，其中桶2,3,7,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中的每个事务，在计算中加入读写动作，并给出各步骤对主存和磁盘产生的影响。假设最初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+RITE(B,t1)7550755025t2:=t2+t112550755025WRITE(A,t2)125125755025Output（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:=t1+t27550255025WRITE(A,t1)7575255025t2:=t1+t210075255025WRITE(B,t2)100751005025Output（A,t1)75751007525Output(B,t2)1007510075100如果OUTPUT动作顺序恰当，即使在事务执行过程中发生故障，一致性仍能得到保持。6.2.3下面是两个事务T和U的一系列日志记录：<STARTU>;<U,A,10>;<STARTT>;<T,B,20>;<U,C,30>;<T,D,40>;<COMMITT>;<U,E,50>;<COMMITU>。请描述恢复管理器的行为，包括对磁盘和日志所作的改变，假设故障发生且出现在磁盘上的最后一条日志记录为：a)<STARTT>b)<COMMITT>c)<U,E,50>d)<COMMITU>答案1若题目是:<STARTU>;<U,A,10>;<STARTT>….则答案是首先扫描日志,发现事务T和U都未commit,将其连接到未完成事务列.按照未完成事务列,从后往前逐步扫描日志并执行undo操作，按照<U,A,10>将磁盘中A值写为10,将<ABORTT>和<ABORTU>写入日志中并刷新日志。首先扫描日志,发现事务T已经commit，将其连接到已完成事务列,事务U未完成，将其连接到未完成事务列。按照未完成事务列，从后往前扫描日志执行undo操作，按照<U,C,30>将磁盘中C值写为30，<U,A,10>将磁盘A值写为10。将<ABORTU>写入日志中并刷新日志。首先扫描日志,发现事务T已经commit，将其连接到已完成事务列,事务U未完成，将其连接到未完成事务列。按照未完成事务列从后往前扫描日志执行undo操作，按照<U,E,50>将磁盘中E值写为50，<U,C,30>将磁盘中C值写为30，<U,A,10>将磁盘A值写为10。将<ABORTU>写入日志中并刷新日志。d)首先扫描日志,发现事务T、U已经commit，将其连接到已完成列，未完成列为空，不做任何操作。6.2.4对于习题6.2.3描述的每种情况，T和U所写的哪些值必然出现在磁盘上？哪些值可能出现在磁盘上？6.3.2使用习题6.2.7的数据，对该习题中（a）到（e）的各个位置回答：I：何时能写入<CKPT>记录Ii：对每一个可能发生的故障的时刻，为了找到所有可能未完成的事务，我们需要在日志中向后看多远。请考虑<ENDCKPT>记录在崩溃发生以前写入和未写入的两种情况。习题6.2.7数据：日志记录序列：<STARTS>;<<S,A,60>;<COMMITS>;<STARTT>;<T,A,10>;<STARTU>;<U,B,20>;<T,C,30>;<STARTV>;<U,D,40>;<V,F,70>;<COMMITU>;<T,E,50>;<COMMITT>;<V,B,80>;<COMMITV>;假设在如下日志中的某一条写入后立即开始一个非静止检查点：A)<S,A,60>B)<T,A,10>C)<U,B,20>D)<U,D,40>E)<T,E,50>第一问1在a）<S,A,60>后写入STARTCKPT时，此时，只有s是活跃的，在<COMMITS>后写入<ENDCKPT>记录；2.在b）后写入STARTCKPT时，此时，只有T是活跃的，在<COMMITT>后写入<ENDCKPT>记录；3.在C）后写入STARTCKPT时，此时，只有U、T都是活跃的，在<COMMITT>后写入<ENDCKPT>录；4.在d）后写入STARTCKPT时，此时，只有U、T、V都是活跃的，在<COMMITV>后写入<ENDCKPT>记录；5.在e）后写入STARTCKPT时，此时，只有T、V都是活跃的，在<COMMITV>后写入<ENDCKPT>录；第二问在a）处，如果<ENDCKPT>记录在崩溃前写入的话，此时需要在日志中向后看到记录<STARTCKPT(S)>；如果<ENDCKPT>记录在崩溃后写入的话，此时需要在日志中向后看到记录<STARTS>;2.在b）处，如果<ENDCKPT>记录在崩溃前写入的话，此时需要在日志中向后看到记录<STARTCKPT(T)>；如果<ENDCKPT>记录在崩溃后写入的话，此时需要在日志中向后看到记录<STARTT>;3.在C）处，如果<ENDCKPT>记录在崩溃前写入的话，此时需要在日志中向后看到记录<STARTCKPT(T，U)>；如果<ENDCKPT>记录在崩溃后写入的话，此时需要在日志中向后看到记录<STARTT>;4、在d）处，如果<ENDCKPT>记录在崩溃前写入的话，此时需要在日志中向后看到记录<STARTCKPT(T,U,V)>；如果<ENDCKPT>记录在崩溃后写入的话，此时需要在日志中向后看到记录<STARTT>;5、在e）处，如果<ENDCKPT>记录在崩溃前写入的话，此时需要在日志中向后看到记录<STARTCKPT(T，V)>；如果<ENDCKPT>记录在崩溃后写入的话，此时需要在日志中向后看到记录<STARTT>;6.4.2下面是两个事务T和U的一系列日志记录：<STARTU>;<U,A,10,11>;<STARTT>;<T,B,20,21>;<U,C,30,31>;<T,D,40,41>;<COMMITT>;<U,E,50,51>;<COMMITU>。描述恢复管理器的行为，包括对磁盘和日志所作的改变，假设故障发生且出现在磁盘上的最后一条日志记录如下：a）<STARTT>b)<COMMITT>c）<U,E,50,51>d）<COMMITU>答案1：a）首先扫描日志，发现事务U、T均未commit，将其连接到未完成列。按照未完成列，从后往前逐步扫描日志并执行undo操作，按照<U,A,10,11>将磁盘中A值写为10.b）首先扫描日志，发现事务T已为commit而U未commit，故将T连接到已完成列而U连接到未完成列。按照未完成列，从后往前扫描日志，按照<U,C,30,31>将磁盘中C写为30，<U,A,10,11>将磁盘中A值写为10。按照已完成列，从前往后扫描日志，按照<T,B,20,21>将磁盘中B写为21，<T,D,40,41>将磁盘中D写为41.c)最后一条记录为<U,E,50，51>这时我们为E往磁盘上写入值51，但是崩溃在<COMMITU>记录到达前发生，则E在磁盘上的值为50。d)最后一条记录为<COMMITU>，这时U被认为是已提交的事务。我们为E往磁盘上写入值51，E已经具有值51。7.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：是否有等价的调度（不管事务对数据做什么），但又不是冲突等价的？7.2.5(i)每一个调度的优先图如下所示：a)b)112c)d)3——》2——》1e)(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(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);il2(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-树上执行下列动作。如果我们使用树协议，什么时候我们可以释放各个被搜索节点上的写锁：插入4b）插入30c）删除37d）删除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