数据库系统实现部分习题参考答案.docx

数据库系统实现部分习题参考答案.docx

《数据库系统实现部分习题参考答案.docx》由会员分享，可在线阅读，更多相关《数据库系统实现部分习题参考答案.docx（43页珍藏版）》请在冰点文库上搜索。

数据库系统实现部分习题参考答案

习题2.2.1

Megatron777磁盘具有以下特性：

1〕有10个盘面，每个盘面有100000个磁道。

2〕磁道平均有1000个扇区，每个扇区为1024字节

3〕每个磁道的20%被用于间隙。

4〕磁盘旋转为10000转/min。

5〕磁头移动n个磁道所需要的时间是1+0.0002nms。

答复以下有关Megatron777的问题。

a〕磁盘的容量是多少？

b〕如果磁道是在直径3.5英寸的圆面上，那么一个磁道的扇区中的平均位密度是多少？

c〕最大寻道时间是多少？

d〕最大旋转等待时间是多少？

e〕如果一个块是65536字节〔即64扇区〕，一个块得传输时间是多少？

f〕平均寻道时间是多少？

g〕平均旋转等待时间是多少？

参考答案：

a）磁盘容量=盘面数*磁道数*扇区数*扇区容量

=10*100000*1000*1024字节

=210*109字节

注释：

1〕有10个盘面，每个盘面有100000个磁道。

2〕磁道平均有1000个扇区，每个扇区为1024字节.

b）一个磁道存放存放1000*1024*8=8192000bits.

直径为3.5英尺那么中间磁道直径为3.5π/2〔英寸〕中间扇区所占的周长是80％*3.5π/2〔英寸〕所以，每个磁道的扇区中的平均密度是

注释：

：

2〕磁道平均有1000个扇区，每个扇区为1024字节.

3〕每个磁道的20%被用于间隙.

c）最大寻道时间是磁头跨越全部柱面所花费的时间。

即1+0.0002*99999=20.9998ms

：

1〕有10个盘面，每个盘面有100000个磁道。

5〕磁头移动n个磁道所需要的时间是1+0.0002nms。

d）最大旋转等待时间是磁头旋转一圈的时间。

即1/（10000/60）=6ms

：

4〕磁盘旋转为10000转/min。

e）该块占用64个扇区，为此，磁头必须越过64个扇区和扇区之间的63个间隙。

由于间隙合在一起占72度圆弧，而扇区覆盖剩余288度圆弧，那么被它们覆盖的圆弧的总度数为：

72*（63/1000）+288*（64/1000）=22.968那么传输时间是〔22.968/360〕*0.6ms=0.03828ms

：

3〕每个磁道的20%被用于间隙。

2〕磁道平均有1000个扇区。

d〕中最大旋转等待时间为6ms。

f）磁头行进的平均距离是跨越柱面的1/3，那么平均寻道时间是：

1+0.001*〔100000/3〕=34.33ms

g）平均旋转等待时间为磁盘旋转半周所需时间:

（1/2）*6ms=3ms

Exercise2.2.1（a）Thediskhas10*10,000=100,000tracks.Theaveragetrackhas1000*512=512,000bytes.Thus,thecapacityis51.2gigabytes.Exercise2.2.1（c）Themaximumseektimeoccurswhentheheadshavetomoveacrossallthetracks.Thus,substitute10,000（really9999）fornintheformula1+.001ntoget11milliseconds.Exercise2.2.1（d）Themaximumrotationallatencyisonefullrevolution.Sincethediskrotatesat10,000rpm,ittakes1/10000ofaminute,or1/167ofasecondtorotate,orabout6milliseconds.

2.4.1计算以下位序列的奇偶校验位：

a〕00111011。

b〕00000000。

c〕10101101。

解：

定义：

如果有奇数个数据盘的第j位为1，在冗余盘中，我们选取位j为1,；如果在数据盘中的第j位有偶数个1，我们选取冗余盘的位j为0。

即：

有奇数个1，为1；有偶数个1，为0。

00111011

00000000

10101101

-------------------------

10010110

习题2.4.9

如果我们有例2.13的RAID6级方案，4个数据盘的块分别为00110100、11100111、01010101和10000100。

a）冗余盘的相应块是什么？

b）如果第3个盘的块被重写成01111111，必须采取哪些步骤以改变其他盘？

[注]例2.13内容：

假设块只有8位长，并且关注在我们的RAID6级例如中用到的7个磁盘的第一块。

首先，假设数据盘和冗余盘的第一块的内容如图2-11所示。

请注意，盘5的块是前3个盘的块模2和，第6行是行1、2、4的模2和，而最后一行是行1、3、4的模2和。

磁盘

内容

数据块1）

11110000

2）

10101010

3）

01010101

4）

10000100

冗余块5）

01100010

6）

00011011

7）

10001001

图2-11所有磁盘的第一块

答案：

a）前4个盘是数据盘,盘5~7是冗余盘.

盘5的块是前3个盘的块的模2和,盘5块是10000110；

盘6是盘1,2和4的模2和,盘6块是01010111；

盘7是盘1,3,4的模2和,盘7块是11100101。

磁盘

内容

数据块1）

00110100

2）

11100111

3）

01010101

4）

10000100

冗余块5）

10000110

6）

01010111

7）

11100101

b）如果第3个盘的块被重写成01111111，求这个序列和序列01010101（该块的旧值）的模2和，那么得到00101010；其中为1的位为3、5、7，所以只要对冗余块5和7的3、5、7位取反，故盘5和盘7的重写值分别为10101100、11001111。

磁盘

内容

数据块1）

00110100

2）

11100111

3）

01111111

4）

10000100

冗余块5）

10101100

6）

01010111

7）

11001111

2.4.10

RAID6方案从磁盘崩溃中恢复

使用足够多的冗余盘处理多个磁盘的崩溃，例如，基于海明码的纠错技术

7个盘，其中1～4为数据盘，5～7为冗余盘。

数据盘与冗余盘之间的关系由一个37矩阵描述如下：

1.盘5的位是盘1,2,3相应位的模2和。

2.盘6的位是盘1,2,4相应位的模2和。

3.盘7的位是盘1,3,4相应位的模2和。

习题2.4.10假设块只有8位长，采用带有7个磁盘的RAID6级方案，描述从以下故障中恢复所要采取的步骤：

a）盘1和盘4；b）盘1和盘7；c）盘2和盘5。

2.5.1

假设一条记录有如下所示顺序的字段:

一个长度为15的字符串，一个2字节整数，

一个SQL2日期，一个SQL2时间〔无小数点〕。

如果

a）字段可在任何字节处开场；

b）字段必须在4的倍数的字节处开场；

c）字段必须在8的倍数的字节处开场；

这条记录占用多少个字节？

First,notethatSQL2datesrequire10bytes,andSQL2timesrequire8bytesifthereisnodecimalpoint;thismaterialisinSection3.1.3.

a）Thebytesrequirsedbyeachofthefieldsis15+2+10+8=35.

b）Roundeachofthefourfieldlengthsuptoamultipleof4,toget16+4+12+8=40.

c）Roundupagain,toamultipleof8,toget16+8+16+8=48.

首先，请注意SQL2日期需要10个字节，SQL2次需要8个字节〔没有小数点〕，点，这种材料是在3.1.3节。

A〕由每个字段需要的字节是15+2+10+8=35。

B〕每此循环的四个字段长度为4的倍数,即所有字段长度为4的倍数，得到16+4+12+8=40。

C〕再次循环，到8的倍数,即所有字段长度为8的倍数，得到16+8+16+8=48。

2.6.5

采用如习题2.6.4一样的RAID4级方案，假设数据盘1有故障。

在以下情况下恢复该磁盘的块：

a）盘2～盘4的内容为01010110、11000000和00111011，同时冗余盘保存着11111011。

b）盘2～盘4的内容为11110000、11111000和00111111，同时冗余盘保存着00000001。

答案:

a、磁盘1的内容：

01010110

b、磁盘1的内容：

00110110

2.6.7

如果我们有例2.22的RAID6级方案，4个数据盘的块分别为

00111100、11000111、01010101和10000100。

a）冗余盘的相应块是什么？

b）如果第三个盘的块被重写成10000000，必须采取哪些步骤以改变其他盘？

答案：

RAID6级方案，4个数据块，3个冗余块〔第1对应数据块123的模2和，第2对应124的模2和，第3对应134的模2和〕

a

数据块1

00111100

2

11000111

3

01010101

4

10000100

冗余块1

10101110

2

01111111

3

11101101

b原第三块01010101与重写块10000000模2和为11010101，其中为1的位为1、2、4、6、8

所以只要对冗余块1、2块的1、2、4、6、8位求反得01111011，10101010

习题3.1.1

假定一个存储块可存放5个记录，或20个键-指针对。

有n个记录，如果表示成n的函数，创立以下两种数据文件各需要多少个数据块：

a〕稠密索引；b〕稀疏索引

答案：

解:

a.稠密索引

因为一个存储块存储5个记录，n个存储记录需要n/5个数据块，稠密索引需要为每个记录建立键-指针对，所以键-指针需要n/20个数据库，所以表示成n的函数是n/5+n/20=n/4

b.稀疏索引

因为一个存储块存储5个记录，n个存储记录需要n/5个数据块，但是稀疏索引需要为每个数据块建立键-指针对，所以键-指针对需要（n/5）/20个数据块，所以表示成n的函数是n/5+（n/5）/20=21n/100

习题3.1.2

如果数据块中可以存放50个记录，或500个键-指针对，但是存放数据和索引的数据块都要求最多只能填满80%，重做习题3.1.1.

答案:

答：

我们知道一个记录在存放时有数据文件和索引文件，它们分别占用存储块，由题中所述可知在索引块中我们采用了稠密索引和稀疏索引，这样两种形式。

只要分别计算出这两个局部的存储块的大小，再求和就能求出需要的存储块。

下面分别来求：

a）一个数据文件和一个稠密索引数据文件的大小容易知道，由给定的记录数为n，且每个存储块可存放50个记录,数据块充满度不许超过80%。

我们得到数据文件所占用的存储块大小为：

n/（50*0.8）;

稠密索引是指块中只存放记录的键以及指向记录本身的指针，数据文件中每个键在索引中都被表示出来，且稠密索引文件中的索引块保持键的顺序和文件中的排序顺序一致，又由每个存储块可存放500个键-指针对，索引块充满度不许超过80%。

这样我们就能得到索引文件所占用的存储块大小为：

n/（500*0.8）。

所以总的结果=数据文件所占用的存储块+索引文件所占用的存储块=n/（50*0.8）+n/（500*0.8）

=〔11/400〕*n

b）一个数据文件和一个稀疏索引

同上，数据文件的大小容易知道，由给定的记录数为n，且每个存储块可存放50个记录,数据块充满度不许超过80%。

我们得到数据文件所占用的存储块大小为：

n/（50*0.8）;

稀疏索引与稠密索引不同点在于，稀疏索引在索引中只为每个数据块存放一个键。

但要注意如果此题按照书中所给出的稀疏索引的比例存放记录的话，参见P92.那么又由每个存储块可存放500个键-指针对，索引块充满度不许超过80%。

这样我们就能得到索引文件所占用的存储块大小为：

n/（50*500*0.8）。

这样才能保证结果的正确性。

所以总的结果=数据文件所占用的存储块+索引文件所占用的存储块=n/（50*0.8）+（n/50*0.8）/500*0.8

=401n/16000

3.2.1假定存储块能放10个记录或者99个键和100个指针，再假定B树结点的平均充满程度为70%；即有69个键和70个指针。

我们可以用B树作为几种不同构造的一局部。

对下面描述的每种构造，确定：

〔1〕1000000个记录的文件所需的总块数；〔2〕检索一个给定键值的记录所需的平均磁盘I/O数。

可以假定最初在主存中不存在任何东西，并且查找键是记录的主键。

*a）数据文件是按查找键排序的顺序文件，每块存放10个记录。

B树为稠密索引。

b）同a〕一样，但组成数据文件的记录没有特定顺序；每块存放10个记录。

c）同a〕一样，但B树为稀疏索引。

!

d）B树的叶结点中不放指向数据记录的指针，而是保存记录本身。

每块可存放10个记录，

但平均每个叶结点的充满度为70%，即每个叶结点存入7个记录。

*e）数据文件是顺序文件，且B树是稀疏索引，但数据文件的每个根本块有一个溢出块。

平

均来讲，根本块是满的，而溢出块只半满。

不过，记录在根本块和溢出块中没有特定的

顺序。

〔X恩斌2141287〕习题3.2.1

假定存储块能放10个记录或者99个键和100个指针，再假定B树结点的平均充满程度为70%；即有69个键和70个指针。

我们可以用B树作为几种不同构造的一局部。

对下面描述的每种构造，确定：

〔1〕1000000个记录的文件所需的总块数；〔2〕检索一个给定键值的记录所需的平均磁盘I/O数。

可以假定最初在主存中不存在任何东西，并且查找键是记录的主键。

a）数据文件是按查找键排序的顺序文件，每块存放20个记录。

B-树为稠密索引

[a]

（1）1000000/10=100000块。

B树为稠密索引，叶结点中为数据文件的每一个记录设有一个键指针对。

首先有100000数据块，如果在B树底层结点平均每块有70个指针，然后有1000000/70=14286个B树块在最底层，下一层的B树需要14286/70=205个B树块，第三层需要205/70=3块，第四层需要1个根块，所以需要100000+14286+205+3+1=114495块。

（2）匹配记录有1000个，首先1000/10=100数据块，1000/70=15块，15/70=1块，第三层需要1块，第四层需要1块。

所以需要100+15+1+1+1=118块。

b〕同a〕一样，但组成数据文件的记录没有特定顺序；每块存放20个记录。

[b]

（1）1000000/10=100000块。

首先有100000数据块，如果在B树底层结点平均每块有70个指针，然后有1000000/70=14286个B树块在最底层，下一层的B树需要14286/70=205个B树块，第三层需要205/70=3块，第四层需要1个根块，所以需要100000+14286+205+3+1=114495块。

（2）匹配记录有1000个，首先1000/10=100数据块，1000/70=15块，15/70=1块，第三层需要1块，第四层需要1块。

1000个记录可能分布在1000个块中，所以需要1000+15+1+1+1=1018块。

c〕同a〕一样，但B树为稀疏索引。

[c]

（1）1000000/10=100000块。

假设B树为稀疏索引，在叶结点中为数据文件的每个块设有一个键指针对。

首先有100000数据块，如果在B树底层结点平均每块有70个指针，然后有100000/70=1429个B树块在最底层，下一层的B树需要1429/70=21个B树块，第三层需要21/70=1块，第四层需要1个根块。

所以需要100000+1429+21+1+1=101452

（2）匹配记录有1000个，1000/10=100，首先100/70=2块，2/70=1块，第三层需要1块，第四层需要1块。

所以需要100+2+1+1+1=105块。

d〕数据文件是顺序文件，且B-树是稀疏索引，但数据文件的每个根本块有一个溢出块。

平均来讲，根本块是满的，而溢出块只半满。

不过，记录在根本块和溢出块中没有特定的顺序。

[d]

（1）但数据文件的每个根本块有一个溢出块。

平均来讲根本块是满的，而溢出块只是半满。

所以根本快的记录为10个，溢出块记录为5个。

所以有1000000/15=66667个数据块。

然后有66667/70=953个B树块在最低层，下一层的B树需要953/70=14个B树块，第三层需要14/70=1。

因此有66667的数据块和953+14+1=968块个索引块。

一共67635块。

（2）1000/15=67块，67/70=1块，第二层需要1块，第三层需要1块。

因此有67个数据块和3个索引块。

总共70块磁盘I/O。

e〕B树的叶结点中不放指向数据记录的指针，而是保存记录本身。

每块可存放10个记录，但平均每个叶结点的充满度为70%，即每个叶结点存放7个记录。

[e]

（1）1000000/7=142858块

如果在B树底层结点平均每块有70个指针，然后有142858/70=2041个B树块在最底层，下一层的B树需要2041/70=30个B树块，第三层需要30/70=1块，所以需要142858+2041+30+1=144930块。

（2）查询匹配的记录有1000个，就需要1000/7=143块，143/70=3块，3/70=1块，第三层需要1块。

所以总共需要143+3+1+1=148块。

3.2.5

假设字段如3.2.1，记录有个首部，它由两个四字节的指针和一个字符组成，且我们希望在一个4096个字节的块中装入尽可能多的记录，使用的块首部由10个4字节的整数组成，对习题3.2.1中的三个情况，我们各能将多少记录装入块中

参考3.2.1题答案

a）（4096–40）/35

b）（4096–40）/40

c）（4096–80）/48

3.3.3假假设在图散列表中发生以下插入和删除，请说明将产生什么情况：

1）记录g到记录j分别插入桶0到桶3。

2）记录a和b记录被删除。

3）记录k到n分别插入桶0到桶3。

4）记录c和d被删除。

答案：

（题目没给出是否顺序产生这4种情况还是各自独立发生？

）设4种情况独立发生

1、g直接插入到桶0中的第二个存储块；

增加一个新存储块在该存储块的第一块上存储h，并到桶1的第一块上；

i直接插入到桶2中的第二个存储块；

增加一个新存储块在该存储块的第一块上存储j，并到桶1的第一块上；

2、在桶3上删除该a记录并将剩下的记录移动到块前部以使其紧凑；

在桶2上直接删除该b记录

习题3.7.4

利用3.7.2节的方法，编码以下位图

a）100

b）1010001

c）00010000

答案：

a）位向量有4个段（1,0,6,7），1的编码是01；0的编码是00；6的编码110110；7的编码110111。

它的编码是10111

b）位向量有6个段（0,7,5,2,1,3），0的编码是00；7的编码110111；5的编码110101；2的编码是1010；1的编码是01；3的编码是1011。

它的编码是0011011

c）位向量有3个段（3,11,4），3的编码是1011；11的编码是11101011；4的编码是110100。

它的编码是0

Exercise4.2.1（a）Theiteratorforpi_L（R）canbedescribedinformallyasfollows:

Open（）:

R.Open（）GetNext（）:

Lett=R.GetNext（）.IfFound=False,return.Else,constructandreturnthetupleconsistingoftheelementsoflistLevaluatedfortuplet.Close（）:

R.Close（）Exercise4.2.1（b）Hereistheiteratorfordelta（R）:

Open（）:

FirstperformR.Open（）.Then,initializeamain-memorystructureSthatwillrepresentasetoftuplesofRseensofar.Forexample,ahashtablecouldbeused.Initially,setSisempty.GetNext（）:

RepeatR.GetNext（）untileitherFound=FalseoratupletthatisnotinsetSisreturned.Inthelatercase,inserttintoSandreturnthattuple.Close（）:

R.Close（）Exercise4.2.1（d）ForthesetunionR1unionR2weneedbothasetSthatwillstorethetuplesofR1andaflagCurRelasinExample6.13.Hereisasummaryoftheiterator:

Open（）PerformR1.Open（）andinitializetoemptythesetS.GetNext（）IfCurRel=R1thenperformt=R1.GetNext（）.IfFound=True,theninserttintoSandreturnt.IfFound=False,thenR1isexhausted.PerformR1.Close（）,R2.Open（）,setCurRel=R2,andrepeatedlyperformt=R2.GetNext（）untileitherFound=False（inwhichcase,justreturn）,ortisnotinS.Inthelattercase,returnt.Close（）:

PerformR2.Close（）

题4.3.1

假设B（R）=B（S）=10000,并且M=1000.计算嵌套连接的磁盘I/O代价。

因为M=1000，我们将用999个内存块来按照大小为999块的chunk对S进展缓冲，我们需要10