數(shù)據(jù)庫復習題2(答案解析)

1、完美WORD格式專業(yè)整理知識分享復習題1、試分別判斷下列圖中G儕口 G2a/VGi=/bcGi a v b c否互模擬(bisimulation),并說明理由： a .G2=b/cG2Ab ccdJ答案:在圖中標出各點的狀態(tài)，我們構造關系”明曲倡向色&的）,可知G2可以*II擬G1,下面我們討論是否可模擬，在G2中2)有一個a變換可對應到G1中2個變換，即(&國小4。但0有兩個變換b, c,而在G1中僅存在只有b或只有c的狀態(tài)點,可知G1和G2不能互模擬。(2)如圖，標出各狀態(tài)點，構造有關系S=狷胤縱說以國心出0)戲而可知其中G1中的點均可由G2中的點模擬，下面我們考慮電q6歌

2、。百創(chuàng)可知同樣其中G2中的點均可由G1中的點模擬.所以G1和G2為互模擬的。試給出其Strong DataGuide 圖答案:3、Consider the relation, following query :r , shown in Figure 5.27 . Give theresult ofthebuildingrooHumnibcrconrseJdsecddGarfield359ABIO-1011Garfield359BBIO-1012Saucon651ACS-1012Saucon550CCS-3191Painter705DMU-1991Painter403DFIN-2011Figur

3、e 5.27Query 1 :select building , room number; time_slo_ id , count (*) from rgroup by rollup (building , room number； time_slo_ id )Query 1 :select building ； room number; time_slo_ id ； count (*) from rgroup by cube ( building ； room number; time_slo_ id )答案：Query 1返回結果集：為以下四種分組統(tǒng)計結果集的并集且未去掉重復數(shù)據(jù)。bui

4、ldingroom numbertime_slo_ idcount (*)產生的分組種數(shù)：4種；種：group by A,B,CGarfield359A1Garfield359B1Saucon651A1Saucon550C1Painter705D1Painter403D1第二種：group by A,BGarfield359A2Garfield359B2Saucon651A1Saucon550C1Painter705D1Painter403D1第三種：group by AGarfield359A2Garfield359B2Saucon651A2Saucon550C2Painter705D2Pa

5、inter403D2第四種：group by NULL 。本沒有group by NULL 的寫法，在這里指是為了方便說明，而采用之。含義是：沒有分組，也就是所有數(shù)據(jù)做一個統(tǒng)計。例如聚合函數(shù)是SUM的話，那就是對所有滿足條件的數(shù)據(jù)進行求和。Garfield359A6Garfield359B6Saucon651A6Saucon550C6Painter705D6Painter403D6Query 2 :group by后帶rollup 子句與group by后帶cube子句的 唯一區(qū)別 就是：帶cube子句的group by會產生更多的分組統(tǒng)計數(shù)據(jù)。cube后的列有多少種組合（注意組合是與順序無關

6、的）就會有多少種分組。返回結果集：為以下八種分組統(tǒng)計結果集的并集且未去掉重復數(shù)據(jù)。buildingroom numbertime_slo_ idcount (*)產生的分組種數(shù)：8種笫L 種：group by A,B,CGarfield359A1Garfield359B1Saucon651A1Saucon550C1Painter705D1Painter403D1第二種：group by A,BGarfield359A2Garfield359B2Saucon651A1Saucon550C1Painter705D1Painter403D1第三種：group by A,CGarfield359A1G

7、arfield359B1Saucon651A1Saucon550C1Painter705D2Painter403D2第四種：group by B,CGarfield359A2Garfield359B2Saucon651A1Saucon550C1Painter705D1Painter403D1第五種：group by AGarfield359A2Garfield359B2Saucon651A2Saucon550C2Painter705D2Painter403D2種：group by BGarfield359A2Garfield359B2Saucon651A1Saucon550C1Painter7

8、05D1Painter403D1第七種：group by CGarfield359A2Garfield359B1Saucon651A2Saucon550C1Painter705D2Painter403D2第八種：group by NULLGarfield359A6Garfield359B6Saucon651A6Saucon550C6Painter705D6Painter403D64、 Disks and Access Time Consider a disk with a sector 扇區(qū) size of 512 bytes, 63 sectors per track 磁道，16,383 t

9、racks per surface 盤面,8 double-sided platters 柱面(i.e., 16 surfaces). The disk plattersrotate at 7,200 rpm (revolutions per minute). The average seek time is 9 msec, whereas the track-to-track seek time is 1 msec.Suppose that a page size of 4096 bytes is chosen. Suppose that a file containing 1,000,00

10、0 records of 256 bytes each is to be stored on such a disk. No record is allowed to span two pages (use these numbers in appropriate places in your calculation).(a) What is the capacity of the disk?(b) If the file is arranged sequentially on the disk, how many cylinders are needed?(c) How much time

11、is required to read this file sequentially?(d) Howmuchtime is needed to read 10%of the pages in the file randomly?Answer:(a) Capacity = sector size * num. of sectors per track * num. of tracks per surface * num of surfaces = 512 * 63 * 16383 * 16 = 8 455 200 768 (b) File: 1,000,000 records of 256 by

12、tes each Num of records per page: 4096/256 = 16 1,000,000/ 16 = 62,500 pages or 62,500 * 8 = 500,000 sectors Each cylinder has 63 * 16 = 1,008 sectorsSo we need 496.031746 cylinders.(c) We analyze the cost using the following three components:Seek time: This access seeks the initial position of the

13、file (whose cost can be approximated using the average seek time) and then seeks between adjacent tracks 496 times (whose cost is the track-to-track seek time). So the seek time is 0.009 + 496*0.001 = 0.505 seconds.Rotational delay:The transfer time of one track of data is 1/ (7200/60) = 0.0083 seco

14、nds. For this question, we use 0.0083/2 as an estimate of the rotational delay (other numbers between 0 and 0.00415 are also fine). So the rotational delay for 497 seeks is 0.00415 * 497 = 2.06255.Transfer time: It takes 0.0083*(500000/63)= 65.8730159 seconds to transfer data in 500,000 sectors.Ther

15、efore, total access time is 0.505 + 2.06255 + 65.8730159 = 68.4405659 seconds.(d) number of pages = 6250time cost per page: 0.009 (seek) + 0.0083/2 (rotational delay) + 0.0083*8/63 (transfer) = 0.0142 seconds total cost = 6250 * 0.0142 = 88.77 seconds5、Disk Page Layout The figure below shows a page

16、containing variable length records. The page size is 1KB(1024 bytes). It contains 3 records, some free space, and a slot directory in that order. Each record has its record id, in the form of Rid=(page id, slot number), as well as its start and end addresses in the page, as shown in the figure.321St

17、art of(J fret spaceSLOT DIRECTORYNowa new record of size 200 bytes needs to be inserted into this page. Apply the record insertion operation with page compaction, if necessary. Showthe content of the slot directory after the new record is inserted. Assumethat you have only the page, not any other te

18、mporary space, to work with.Page Format: Variable Length RecordsSLOT DIRECTORYPointer to 占 3Tt of free space* CompncHoti: get nil slots whose offset is not -1, st)rf bi/ startddresw move their records up in sorted order. No change of rids!Answer:Content of the slot directory, from left to right, is:

19、 (650, 200), (0, 200), (500, 150), (200, 300), 4, 8506、Buffer Management for File and Index Accesses Consider the following two relations:student(snum:integer, sname:char(30), major:char(25), standing:char(2), age:integer)enrolled(snum:integer, cname:char(40)The following index is available:A B+ Tre

20、e index on the <snum> attribute of the student relation.Assume that the buffer size is large enough to store multiple paths of each B+ Tree but not an entire tree.(a) Consider Query 1 and Query 2 that retrieve the snuM s of students who have taken (Database Systems' and (Operating Systems

21、', respectively, from the enrolled table. We know that Query 1 will be executed before Query 2, and both queries are executed using a file scan of the enrolled table.Which replacement policy would you recommend for the buffer manager to use to support this workload?(b) Nowassumethat we have retr

22、ieved the snumi s of students who have taken ( Database Systems' from the enrolled table. In the exact order of the retrieved snum ' s (not necessarily in sorted order),we then retrieve the names of those students via repeated lookups in the B+ Tree on <snum>.For these repeated accesse

23、s to the index on student.snum, which replacement policy would you recommend for efficient buffer management?Query 1: select snum from student s, enrolled e where s.snum=e.snum and cname like ' Database Systems'Query 2: select snum from student s, enrolled e where s.snum=e.snum and cname lik