數(shù)據(jù)庫復(fù)習(xí)題2(答案)

1、資料收集于網(wǎng)絡(luò)如有侵權(quán)請聯(lián)系網(wǎng)站刪除謝謝復(fù)習(xí)題（ 2）1、 試分別判斷下列圖中 G1和G2是否互模擬 (bisimulation) ，并說明理由 :aaaG1=G2=bcbcG1G2ababcccddd答案：(1) 在圖中標(biāo)出各點(diǎn)的狀態(tài)，我們構(gòu)造關(guān)系，可知 G2 可以模擬G1，下面我們討論精品文檔資料收集于網(wǎng)絡(luò)如有侵權(quán)請聯(lián)系網(wǎng)站刪除謝謝是否可模擬，在G2 中有一個(gè) a 變換可對應(yīng)到G1 中 2 個(gè)變換，即，。但有兩個(gè)變換b，c，而在 G1 中僅存在只有b 或只有 c 的狀態(tài)點(diǎn)，可知 G1 和 G2 不能互模擬。(2) 如圖，標(biāo)出各狀態(tài)點(diǎn)，構(gòu)造有關(guān)系可知其中 G1 中的點(diǎn)均可由G2 中的點(diǎn)模擬，

2、下面我們考慮可知同樣其中G2 中的點(diǎn)均可由G1 中的點(diǎn)模擬 . 所以 G1 和 G2 為互模擬的。2、 給定如下數(shù)據(jù)圖 (Data Graph)：r1personcompanypersoncompanypersonmanagesworks-forc1employeep1ceop2c2ceop3nameposition works-fornameworks-fornamephonenameaddresspositionaddressnames0s2s3s4s5s6urls7s8s9s1“Widget”“Trenton ”“Jones ”“Gadget”“Paris ”“Dupont”“Sales

3、 ”“Smith ”“5552121 ”“Manager ”s10“www.gp.fr”試給出其 Strong DataGuide 圖精品文檔資料收集于網(wǎng)絡(luò)如有侵權(quán)請聯(lián)系網(wǎng)站刪除謝謝答案：r1personworks-formanagesemployeec1,c2p1,p2,p3p2ceonamephonep1,p3urlpositionnameaddresss0,s4,s8s1,s9s5s2,s6s3,s7s10Strong DataGuide 圖3、 Consider the relation,r , shown in Figure 5.27 . Give the result of the

4、 following query :Figure 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返回結(jié)果集：為以下四種分組統(tǒng)計(jì)

5、結(jié)果集的并集且未去掉重復(fù)數(shù)據(jù)。buildingroom numbertime_slo_ idcount(*)產(chǎn)生的分組種數(shù)：4 種；精品文檔資料收集于網(wǎng)絡(luò)如有侵權(quán)請聯(lián)系網(wǎng)站刪除 謝謝第一種： group by A,B,CGarfield359A1Garfield359B1Saucon651A1Saucon550C1Painter705D1Painter403D1第二種： group by A,BGarfield359A2Garfield359B2Saucon651A1Saucon550C1Painter705D1Painter403D1第三種： group by AGarfield359A2G

6、arfield359B2Saucon651A2Saucon550C2Painter705D2Painter403D2第四種： group by NULL。 本沒有 group by NULL的寫法，在這里指是為了方便說明，而采用之。含義是：沒有分組，也就是所有數(shù)據(jù)做一個(gè)統(tǒng)計(jì)。例如聚合函數(shù)是SUM 的話，那就是對所有滿足條件的數(shù)據(jù)進(jìn)行求和。Garfield359A6Garfield359B6Saucon651A6Saucon550C6Painter705D6Painter403D6Query 2:group by 后帶 rollup 子句與 group by 后帶 cube 子句的 唯一區(qū)別 就

7、是：帶 cube 子句的 group by 會產(chǎn)生更多的分組統(tǒng)計(jì)數(shù)據(jù)。cube 后的列有多少種組合（注意組合是與順序無關(guān)的）就會有多少種分組。返回結(jié)果集：為以下八種分組統(tǒng)計(jì)結(jié)果集的并集且未去掉重復(fù)數(shù)據(jù)。buildingroom numbertime_slo_ idcount(*)產(chǎn)生的分組種數(shù)：8 種第一種： group by A,B,CGarfield359A1Garfield359B1Saucon651A1精品文檔資料收集于網(wǎng)絡(luò)如有侵權(quán)請聯(lián)系網(wǎng)站刪除謝謝Saucon550C1Painter705D1Painter403D1第二種： group by A,BGarfield359A2Garf

8、ield359B2Saucon651A1Saucon550C1Painter705D1Painter403D1第三種： group by A,CGarfield359A1Garfield359B1Saucon651A1Saucon550C1Painter705D2Painter403D2第四種： group by B,CGarfield359A2Garfield359B2Saucon651A1Saucon550C1Painter705D1Painter403D1第五種： group by AGarfield359A2Garfield359B2Saucon651A2Saucon550C2Pain

9、ter705D2Painter403D2第六種： group by BGarfield359A2Garfield359B2Saucon651A1Saucon550C1Painter705D1Painter403D1第七種： group by CGarfield359A2Garfield359B1Saucon651A2Saucon550C1精品文檔資料收集于網(wǎng)絡(luò)如有侵權(quán)請聯(lián)系網(wǎng)站刪除謝謝Painter705D2Painter403D2第八種： group by NULLGarfield359A6Garfield359B6Saucon651A6Saucon550C6Painter705D6Pain

10、ter403D64、 Disks and Access TimeConsider a disk with a sector扇區(qū) size of 512 bytes,63 sectors per track磁道 , 16,383 tracks per surface盤面 , 8 double-sided platters柱面 (i.e., 16 surfaces). The disk platters rotate at 7,200 rpm (revolutions perminute). The average seek time is 9 msec, whereas the track-to

11、-track seek time is 1 msec.Suppose that a page size of 4096 bytes is chosen. Suppose that a file containing 1,000,000 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 capacit

12、y of the disk?(b) If the file is arranged sequentially on the disk, how many cylinders are needed?(c) How much time is required to read this file sequentially?(d) How much time is needed to read 10% of the pages in the file randomly?Answer:(a) Capacity = sector size * num. of sectors per track * num

13、. of tracks per surface * num of surfaces = 512 * 63 * 16383 * 16 = 8 455 200 768(b) File: 1,000,000 records of 256 bytes eachNum of records per page: 4096/256 = 161,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

14、) We analyze the cost using the following three components:Seek time: This access seeks the initial position of the file (whose cost can be approximated using the average seek time) and then seeks between adjacenttracks 496 times (whose cost is the track-to-track seek time). So the seek time is 0.00

15、9 + 496*0.001 = 0.505 seconds.Rotational delay:The transfer time of one track of data is 1/ (7200/60) = 0.0083 seconds.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

16、 = 2.06255.Transfer time: It takes 0.0083*(500000/63) = 65.8730159 seconds to transfer data in 500,000 sectors.精品文檔資料收集于網(wǎng)絡(luò)如有侵權(quán)請聯(lián)系網(wǎng)站刪除謝謝Therefore, 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

17、delay) + 0.0083*8/63 (transfer) = 0.0142 secondstotal cost = 6250 * 0.0142 = 88.77 seconds5、 Disk Page Layout The figure below shows a page 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 h

18、as 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.Now a new record of size 200 bytes needs to be inserted into this page. Apply the record insertion operation with page compaction, if necessary. Show the content of

19、 the slot directory after the new record is inserted. Assume that you have only the page, not any other temporary space, to work with.精品文檔資料收集于網(wǎng)絡(luò)如有侵權(quán)請聯(lián)系網(wǎng)站刪除謝謝Answer:Content of the slot directory, from left to right, is:(650, 200), (0, 200), (500, 150), (200, 300), 4, 8506、 Buffer Management for File

20、 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+ Tree index on the <snum> attribute of the student relation.Assume that the buf

21、fer 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 havetaken DatabaseSystems and Operating Systems , respectively, from theenrolled table. We know that Query 1 will be executed before Query

22、2, and bothqueries are executed using a file scan of the enrolled table.Which replacement policy would you recommend for the buffer manager to use tosupport this workload?(b) Now assume that wehave retrieved the snum s of students who have taken DatabaseSystems from the enrolled table. In the exact

23、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 accesses to the index on student.snum, which replacement policy would you recommend for efficient buffer management?精品文檔資料收集于網(wǎng)絡(luò)如有侵權(quán)請聯(lián)系網(wǎng)站刪除謝謝Query 1:selectsnumfrom student s, enrolled ewhere s.snum=e.snum and cname like DatabaseSystems ;Query 2:selectsnumfrom student s, enrolled ewhere s.snum=e