高级数据库技术问答题(附答案)

DatabaseSystemProblem1Thehashjoinalgorithmdescribedinthetextbookcomputesthenaturaljoinoftworelations.Writepseudocodeforaniteratorthatimplementsahashbasedalgorithmforcomputinganoperation:Ranti-joinScontainsalltuplesinRthathavenomatchingtuplesinS.Althoughanti-joinisnotanoperationthatcanbespecifieddirectlyinSQL,itisimplementedinthequeryprocessortosupportsometypesofqueries.Yourpseudocodemustdefinethestandarditeratorfunctionsopen(),next(),andclose(),andmustfetchtheinputtuplesusingiteratorcalls(inotherwords,RandSmaynotbebaserelations,butmaybeoutputsofotheroperators).Showwhatstateinformationtheiteratormustmaintainbetweencalls.Forsimplicity,youcanassumethatSissmallandeasilyfitsinmemory.Herearemoredetailsonanti-join:/wiki/Relational_algebra#AntijoinProblem2ConsideranindexorganizedasaB+tree.TheleafnodescontainpointerstoatotalofNrecords,andeachblockthatmakesuptheindexhasmpointers.Wewishtochoosethevalueofmthatwillminimizesearchtimesonaparticulardiskdevice.Wearegiventhefollowinginformation:(a)Forthediskthatwillholdtheindex,thetimetoreadagivenblockintomemorycanbeapproximatedby(25+.02*m)milliseconds.The25millisecondsrepresenttheseekandlatencycomponentsoftheread,the.02*mmillisecondsisthetransfertime.(Thatis,asmbecomeslarger,thelargertheblockwillbeandthemoretimeitwilltaketoreaditintomemory.)(b)Oncetheblockisinmemoryabinarysearchisusedtofindtherightpointer.Sothetimetoprocessablockinmainmemoryis(a+blog_2m)milliseconds,forsomeconstantsa,b.("log_2m"meanslogbase2ofm.)(c)Themainmemorytimeconstant"a"ismuchsmallerthanthediskseekandlatencytimeof25milliseconds.(d)Theindexisfull,sothatthenumberofblocksthatmustbeexaminedpersearchislog_mN.Questions:(i)Whatvalueofmminimizesthetimetosearchforagivenrecord?AnapproximateanswerisOK.(HINT:Ifyoucomeupwithanequationwhichishardtosolvealgebraically,tryplugginginvaluestolocatetherootoftheequation.)Thevalueyouobtainshouldbeindependentof"b"!(ii)Whathappensastheseekandlatencyconstant(25ms)decreases?Forinstance,ifthisconstantiscutinhalf,howdoestheoptimummvaluechange?Answer:LetTbethetimetakentoreadoneblockintomainmemoryandTbethetimetoprocessthat12blockinmemory.Ifnblocksareexaminedtosearchforagivenrecord,thenthetimetakenforthissearchis:n*(T+T)12Substitutingtheappropriateexpressionsforallthevariables,wegetT(m)=[(25+0.02m)+(a+b]*logN2mIgnoringaincomparisonwith,wegetT(m)=[25+0.02m+b*logN2mSubstitutinglogmbyln(m)/ln(2)andlogNbyln(N)/ln(m),weget2mT(m)=[(25+0.02m)/ln(m)]*ln(N)+b*ln(N)/ln(2)Hence,tominimizeT(m),weneedtominimizef(m)=(25+0.02m)/ln(m.Anumberoftechniquescanbeappliedtodeterminethevalueofmthatminimizesthisexpression.Forexample,takingthederivativeandsettingittozero(f'(m)=),wegetm*(ln(m)-1)=1250Thiscanbesolvedtoyieldanintegralvalueof272.Itiseasytoverifythatthisvaluedoesindeedminimizef(m)andhenceT(m).Seek+latencyconstantdecreases:LetussplitT(m)intothreecomponentsasfollows(here,tistheseek+latencytimeconstantwhichwas30intheabovecase):s=t*ln(N)/ln(m)Ta•••Totalseekandlatencytime=0.02*m*ln(N)/ln(m)sTotaltransfertimeTb=b*ln(N)/ln(2)TotalbinarysearchtimeTcOfthese,Tisindependentof,TisadecreasingfunctionofmwhereasTisanincreasingcabfunctionof.Iftisverysmall,thenTisnegligiblecomparedtoT.Hence,wemustchooseasabsmallvalueofmtominimizethesearchtime.Ontheotherhand,ifTisverylargecomparedtoT,abthentheformerdominatesandwechoosealargevalueofmtominimizesearchtimes.Fromtheselimitingcases,itiseasytoseethatiftdecreases,theoptimumvalueofmdecreases.Insparticular,ift=25/2=12.5,wegetanoptimumvalueof155(byproceedingalongthesameslinesasabove).Problem3Tobuildahashindexforamulti-attributesearchkey,wecanuseanapproachcalledpartitionedhashing.Thepartitionedhashfunctionisreallyalistofhashfunctions,oneforeachattributeinthesearchkey.SupposethatwewishtobuildapartitionedhashindexonR(A,B)with2nbucketsnumbered0to2n1.Inthiscase,thepartitionedhashfunctionconsistsoftwohashfunctionshAandhB.HashfunctionhAtakesavalueofAasinputandproducesaresultwithnAbits,andhBtakesavalueofBasinputandproducesaresultwith(nnA)bits.Thetworesultsareconcatenatedtogethertoproducetheresultofthepartitionedhashfunction,whichisthenusedtoindexthebuckets.TolocaterecordswithA=aandB=b,wesimplygodirectlytothebucketnumberedhA(a)hB(b)(inbinary).(a)WhichbucketsdowehavetoexamineinordertolocateallrecordswithA=a?(b)Supposewearegivenaquerymix.EachqueryinthismixwilleitheraskforrecordswithagivenvalueofA,oritwillaskforrecordswithagivenvalueofB(butneverboth).Withprobabilityp,thevalueofAwillbespecified.Giveaformulaintermsofn,nA,andpfortheexpectednumbe