数据库系统实现(第二版_英文版)部分答案.ppt

SolutionsforDatabaseSystemImplementation GanLinQQ 85906478Email 85906478 Chapter13 Thecapacityofthedisk Thediskhas8 100 000 800 000tracks Theaveragetrackhas2000 1024 2048 000bytes Thus thecapacityis214 108bytesThemaximumseektime Themaximumseektimeoccurswhentheheadshavetomoveacrossallthetracks Thus substitute100 000tracts really99999 fornintheformula1 0003ntoget31 30 9997 ms Themaximumrotationallatency Themaximumrotationallatencyisonefullrevolution Sincethediskrotatesat6 000rpm ittakes1 6000ofaminute or0 01storotate Exercise13 2 1 2 2 1 Transfertimeofablock Sinceatrackhas2000sectorsand2000gaps and10 ofatrackisusedforgaps thereare36oforgapsand324oforsectorsofatrackcircle Sothereare36o 2000foreachgapand324o 2000foreachsector Thisblockis65546bytes i e 64sectors theheadsmustthereforepassover63gapsand64gaps i e 63 36o 2000 64 324o 2000 Asthemaximumrotationallatencyis0 01s wecanhavethetransfertimeoftheblockis 63 36o 2000 64 324o 2000 0 01 360o 0 0003195sor0 3195ms Exercise13 2 1 2 2 1 Theaverageseektime Theaveragenistracks 3ofasurface i e 100 000 3 Sotheaverageseektimeis1 0003 n 1 0003 100 000 3 11ms Theaveragerotationallatency Theaveragerotationallatencyis0 01 2 0 005sTheaveragedensityofbitsinthesectorsofaoutertrack Atrackhas2000sectors eachsectorholds1024bytes andeverybytetakes8bits soatrackis2000 1024 8bits Forthe3 5inchdisk thedensityoftheoutertrackis2000 1024 8 3 5 90 1655615 6394bit inch Exercise13 2 1 2 2 1 Theaveragetrackstheheadshavetomove 1 2 4095 1 2 65536 4096 65536 28928Seektime 1 28928 4000 8 232msTransfertime 0 13msRotationallatency 4 17msAverageseektime averagerotationallatency averagetransfertime 12 532ms Exercise13 2 4 2 2 2 Seektime 1 tracks 4000Transfertime 0 13Rotationallatency 4 17Completetime dealtime seektime transfertime rotationallatency Exercise13 3 1 2 4 1 块传输时间为0 13ms 平均旋转等待时间为4 17ms 平均寻道时间为1 65536 3 4000 2 3 72ms 所以平均读取一个块的时间为8 02ms无约束的megatron镜像平均速度提高1倍 所以平均读取时间约为10 76 2 5 38ms该系统缺陷主要在于无法同时处理同侧柱面的读取请求 大量同侧请求到来时会导致一边队列累积而另一边空闲 Exercise13 3 2 Exercise13 4 9 2 6 7 Modulo 2sumofthenewvalue01111111andtheoldvalue01010101is00101010 Exercise13 5 3 3 2 2 8 25 1 10 44bytes8 32 8 16 64bytes8 28 4 12 52bytesExercise13 6 5 3 3 4 IPaddress4 8 32bits 4BDevicenumber14bits 2B as213 10 000 214 Blockaddress4 16 6 26bits 4B becausethereare24surfaces 216tracksand26blocks seeP564 So totallyrequire10B Thefirstthreefieldsneed9 3 27Byte Andthefirstvariable lengthfielddoesnotneedapointer whilethesecondoneandthethirdoneneedpointers Sothereare8 2 16Byteforpointers andeveryrecordtakes27 16 43Byte Sincethelengthofarecordisa2 byteinteger therecordhas45Byte Exercise13 7 1 Chapter14 Exercise14 1 2 4 1 2 n 50 80 blocksareneededforthedatafile and n 500 80 fortheindex foratotalof n 40 n 400 blocks Weagainneed n 50 80 forthedatafile butnowneedonlyroomfor n 50 80 500 80 pointersintheindexfile Thelattertakes n 16000 blocks foratotalof n 40 n 16000 blocks Exercise14 1 7 4 2 8 Obtainallthebucketentriesfor cat and dog Sortthesebytype andwithintype byposition Scantherecords keepinga window withrecordsofthecurrenttype extendinguptofivepositionspriortothecurrenttype Compareeachnewrecordwiththerecordsinthewindow Ifwefindonethat 1 Hastheoppositeword e g dog ifthecurrentbucketrecordhas cat and 2 Haveidenticaldocumententries Thenthecommondocumentisoneofthosewewanttoretrieve Exercise14 1 7 4 2 8 Obtainallthebucketentriesfor dog Sortthesebyposition Scantherecords keepinga window withrecordsofonepositionpriortothecurrentposition Compareeachnewrecordwiththerecordsinthewindow Ifwefindonethat 1 hastheoppositeword cat and 2 haveidenticaldocumententries Thenthecommondocumentisoneofthosewewanttoretrieve Wefollowthepointerassociatedwith cat tofindtheoccurrencesofthisword Selectfromthebucketpointerstodocumentsassociatedwithoccurrencesof cat wherethetypeis title Thenwefindthebucketentriesfor dog andSelectfromthebucketpointerstodocumentsassociatedwithoccurrencesof cat wherethetypeis title intersectthistwosetsofpointers wecanhavethedocumentsthatmeettheconditions Exercise14 2 1 4 3 1 Thesequential100000records and20records block First thereare5000datablocks Ifthereareof69keysperblockonaverageinthebottom levelnodesoftheB tree thenthereare1450B treeblocksatthatlevel ThenextleveloftheB treerequires1 70thofthat or21blocks Thethreelevelhasonlytherootblock Thenumberofblocksneededis5000 1450 21 1 6472blocks SincetheB treehasthreelevels wemustmakeatotalof4diskreadstogothroughtheB treetothedesireddatablock as a Exercise14 2 1 4 3 1 Thesequential100000records and20records block First thereare5000datablocks Withthesparseindex ablockhasanindex andthenthereare5000 69 73B treeblocksatthatlevel ThenextleveloftheB treerequires1 70thofthat or2blocks andthethirdlevelhasonlytherootblock Thenumberofblocksneededistherefore50000 73 2 1 5076blocks SincetheB treehas3levels wemustmakeatotalof4diskreadstogothroughtheB treetothedesireddatablock Exercise14 2 1 4 3 1 Ifoneprimaryblockhas20recordswithitsoverflowblockshaving10records 100000recordsneed100000 30or3334primaryblocks andthesamenumberofoverflowblocks Thenumberoffirst levelB treeblocksis3334 69 49 Andthesecondlevelhasonlytheroot foratotalof3334 3334 49 1 6718blocks AsearchrequirestwodiskI O stogothroughtheB treetothedatafile Oncethere wesurelyneedtoreadtheprimaryblock and1 3ofthetimeweshallneedtoseetheoverflowblockaswell Thus theaveragenumberofdiskI O sis10 3 as3 2 3 4 1 3 Exercise14 2 1 4 3 1 Tobegin thereare100000 7 or14286primaryblocks Thenumberoffirst levelB treeblocksis14286 70 205 Atthesecondlevelthereare205 70 3 andthethirdlevelhasonlytheroot foratotalof14286 205 3 1 14495blocks SincetheB treehas3levels wemustmakeatotalof4diskreadstogothroughtheB treetothedesireddatablock 以下情况会出现递归处理 该块可能存储的数据条数 2n 例如散列键值为四位数 且某块j值为1 存储第一位为0的数据 但n 3 而可能存储的数据为0000 0111共有8条数据 分裂后每个子块最多有4条数据 仍然 n 如果分裂前的数据为0000 0011 则分裂后数据仍全归于前两位为00的块 仍需递归分裂 Exercise14 3 4 Exercise14 3 5 4 4 6 Exercise14 3 5 4 4 6 Exercise14 5 1 5 2 1 若同一条线上多于两个点 则必须分开 180 280 2 15 2 5 3230 280 2 15 2 7 Exercise14 5 5 5 2 5 4 6 24Thedistancebetween 110 245 and 115 230 issqrt 250 i e 15 16 Lowleftcorner 80 200 80 250 100 250 120 250 120 200 Exercise14 6 1 Showamultiple keyindexforthedataofthetableiftheindexesareon Ram thenhard disk Speed thenramSpeed thenhard disk thenram Exercise14 6 1 Ram thenhard disk 512 1024 2048 80 250 160 200 250 320 160 250 300 Exercise14 6 1 b Speed thenram 1 42 1 86 2 00 2 10 2 20 2 66 2 80 3 20 512 2048 1024 512 1024 2048 1024 1024 2048 512 1024 Exercise14 6 1 Speed thenhard disk thenram 512 1 42 1 86 2 00 2 10 2 20 2 66 2 80 3 20 80 160 250 250 200 250 250 160 250 300 250 320 2048 1024 512 1024 2048 1024 1024 1024 2048 512 1024 Exercise14 6 2 5 3 2 Exercise14 6 2 5 3 2 Exercise14 7 2 5 4 2 Wefirstfindthebit vectorsfortheagevaluesintherange 40 60 therearethreebit vectors 010000000100 001110000010 000000000001 for45 50 60 respectively IfwetaketheirbitwiseOR wecanhaveanewbit vector 011110000111 inwhich1isinpositioniifandonlyiftheithrecordhasanageinthedesiredrange wefindthebit vectorsforthesalariesbetween100and200thousand Therearefourbit vectors 000100000000 000001000000 000010000000 000000100000 correspondingtosalaries100 110 120and140 TheirbitwiseORis000111100000 wetakethebitwiseANDofthetwobit vectors 011110000111and000111100000 thenwecanhave011110000111AND000111100000 000110000000 whichmeansthefourthandfifthrecords 50 100 50 120 arethetargets Chapter15 Exercise15 2 1 6 3 1 Open PerformR1 Open andinitializetoemptythesetS GetNext IfCurRel R1thenperformt R1 GetNext IfFound True theninserttintoSandreturnt IfFound False thenR1isexhausted PerformR1 Close R2 Open setCurRel R2 andrepeatedlyperformt R2 GetNext untileithertisinS inwhichcasedeletethetinS orFound False inwhichcasejustreturn Close PerformR2 Close Exercise15 3 2 6 4 3 SupposeB R B S 10000 B S B S B R M 1 528Exercise15 4 4 6 5 3 3 B R B S 3 20 000 60 000Exercise15 5 1 6 6 2 3 2M B S B R B S 3 2 500 10000 10000 10000 58000 AssumingB S B R Exercise15 6 1 Theindexisnotclustering thecostisT R V R a 500000 kTheindexisclustering thecostisB R V R a 10000 kRisclustered andtheindexisnotused thecostisB R 10000 Two pass sort basedjoinMax B R B S M 2 2 M2 4 B R B S M 2 2 M2 4 Exercise15 7 1 6 8 1 Chapter16 Exercise16 1 3 7 1 3 Exercise16 1 3 7 1 3 R a b 1 2 1 3 dR R pa dR 1 1 paR 1 1 d paR 1 notequalR a b 1 2 1 2 S a b 1 2 R BS 1 2 d R BS 1 2 dR B dS 1 2 B 1 2 notequal R BS 1 2 1 2 1 2 d R BS 1 2 dR B dS 1 2 B 1 2 1 2 1 2 notequal R a b 1 2 S a b 1 3 pa R S 1 paR paS 1 1 notequal Exercise16 2 1 7 2 2 paRR b a pa RR b S bS pa c RR b S bS Exercise16 3 1 7 3 2 R a b S b c T c d U a d pR a a R b b S c c T d d RSTU Commutativenotassociativegroup R b S b S c T cR a U c T d U d Exercise16 3 2 7 3 1 Exercise16 4 1 FornaturaljoinR X Y S Y Z thecostis T R S T R T S max V R Y V S Y sothecostofW X Y Zcanbeeveluatedby T W X Y Z T W T X max V W b V X b T X T Y max V X c V Y c T Y T Z max V Y d V Z d 20000 Exercise16 4 1 T a 10 W T W V W a 8T c 20 Y T Y V Y c 4T c 20 Y Z T c 20 Y T Z max V c 20 Y d V Z d 40T W Y T W T Y 80000T d 10 Z T Z 3 33T a 1ANDb 2 W T W V W a V W b 0 2T a 1ANDb 2 W T W V W a 3 2 67T X X c Y cY T X T Y 3 20000 ThefrequencyoftheothersinRis36 20 4 inSis50 20 4 Sotheoutputsize 5 10 4 8 10 5 5 50 16 7 36 16 15 36 16 50 16 269ThesimplerestimateisT RS T R T S max V R b S b 60 80 20 240269 240 Exercise16 5 1 7 5 1 01234others R b5410536S b1085750 Leftdeeptreesonly Exercise16 6 1 7 6 1 Leftdeeptreesonly Exercise16 6 1 7 6 1 AlltreesLeft deeptreeshavebeendiscussedRight deeptreesbushy Exercise16 6 1 7 6 1 1 tablescan B R 5002 aindex a 1 B R V R a 103 cb 2 T R V R b 54 cindex c 3 T R 3 1667故最佳查询计划为第三种 即搜索所有b 2的元组 另外两个条件过滤 代价为5次I O1 tablescan B R 5002 aindex a 1 B R V R a 103 aindex b 3 T R 3 1667故最佳查询计划为第二种 即搜索所有a 1的元组 另外两个条件过滤 代价为10次I O Exercise16 7 1 7 7 1 Chapter17 i Sistheonlyactivetransaction sothelogrecordis Wecanwritetherecordaftertherecord ii Ifthecrashoccursafterthattime wehavetosearchbackonlytothe Thesearchmustcontinuebackasfarastherecord i Tistheonlyactivetransaction sothelogrecordis Wecanwritetherecordaftertherecord ii Ifthecrashoccursafterthattime wehavetosearchbackonlytothe However forcrashespriortotherecord thesearchmustcontinuebackasfarastherecord sincethatisthe lone transactionthatwasactiveatthestartofthecheckpoint Exercise17 2 7 8 2 7 Thereareseveneventsofinterest whichweshallcall A databaseelementAiswrittentodisk B databaseelementBiswrittentodisk C databaseelementCiswrittentodisk LA thelogrecordforAiswrittentodisk LB thelogrecordforBiswrittentodisk LC thelogrecordforCiswrittentodisk D thecommitrecordiswrittentodisk Withredologging thewritingoftheelementsAandBmustoccurafteralllogrecordsarewritten Thus theonlyoptioniswhichelementgetswrittenfirst andthelegalsequencesofeventsareLA LB D A BandLA LB D B A Exercise17 3 3 8 3 2 Legalsequencesofeventsare LA LB LC D A B CLA LB LC D B A CLA LB LC D C B ALA LB LC D C A BLA LB LC D A C BLA LB LC D B C A Exercise17 3 3 8 3 2 i TheENDCKPTrecordcouldappearanywhereaftertherecord Thereasonisthatthewritingofdirtyblockscanbeperformedindependentofwhateveractionsthetransactionsareperformingintheinterrumii TheonlyactivetransactionwhenthecheckpointbeganwasS IfthecrashoccursaftertheENDCKPT thenweneedonlygobackasfarasthe However ifthecrashoccursbetweentheandthe weneedgobacktothe whileweneedgobacktothe ifthecrashoccursbefore Exercise17 4 4 8 4 5 i TheENDCKPTrecordcouldappearanywhereaftertherecord Thereasonisthatthewritingofdirtyblockscanbeperformedindependentofwhateveractionsthetransactionsareperformingintheinterrumii TheactivetransactionswhenthecheckpointbeganwereTandV IfthecrashoccursaftertheENDCKPT thenweneedonlygobackasfarasthe However ifthecrashoccursbeforethecheckpointended thenwemustlookbacktothe Exercise17 4 4 8 4 5 Chapter18 T1 T2 R A t t t 2 W A t R A s s s 3 W A s R B t t t 3 W B t R B s s s 2 W B s 2serialschedulesand402serializableschedules Exercise18 2 1 9 2 1 T1 T2 T1 R A t t t 2 W A t R B t t t 3 W B t A0 23B0T2 R B s s s 2 W B s R A s s s 3 W A s 6B0A0 5 T2 T1 T2 R B s s s 2 W B s R A s s s 3 W A s 2B0A0 3T1 R A t t t 2 W A t R B t t t 3 W B t A0 56B0 ThethreewritescreatethreeversionsofA WhenT2triestoreadA itisgiventhevaluethatititselfwrote sincethatistheversionwiththegreatesttimestampthatdoesnotexceedthetimestampofT2 Thatmakessense althoughinpractice wedoubtthatawellwrittentransactionwouldreaditsownvaluethroughthedatabasestoragesystem WhenT4triestoreadAthesystemfindsthatT4 stimestampislargerthanthatofanyversionofAwritten Thus T4getstheversionwiththelargestofthetimestamps theonewrittenbyT3 Thatmakessense becauseinthehypotheticalserialorderbasedonthetimestampsofthetransactions T3wouldbethelasttowriteA Exercise18 8 3 9 8 2 AsT1isthefirsttovalidate thereisnothingtocheck T1validatessuccessfully T3validatesnext TheonlyothervalidatedtransactionisT1 andT1hasnotyetfinished Thus boththeread andwrite setsofT3mustbecomparedwiththewrite setofT1 However T1writesonlyA andT3neitherreadsnorwritesA soT3 svalidationsucceeds Last T2validates BothT1andT3finishafterT2started sowemustcomparetheread setofT2withthewrite setsofbothT1andT3 SinceBisinbothW3andR2 wecannotvalidateT2 Noteth