完整word版,高级数据库技术问答题(附答案)

DatabaseSystem

Problem1

Thehashjoinalgorithmdescribedinthetextbookcomputesthenaturaljoinoftworelations.Writepseudocodeforaniteratorthatimplementsahashbasedalgorithmforcomputingan“anti-join”operation:Ranti-joinScontainsalltuplesinRthathavenomatchingtuplesinS.Althoughanti-joinisnotanoperationthatcanbespecifieddirectlyinSQL,itisimplementedinthequeryprocessortosupportsometypesofqueries.Yourpseudocodemustdefinethestandarditeratorfunctionsopen(),next(),andclose(),andmustfetchtheinputtuplesusingiteratorcalls(inotherwords,RandSmaynotbebaserelations,butmaybeoutputsofotheroperators).Showwhatstateinformationtheiteratormustmaintainbetweencalls.Forsimplicity,youcanassumethatSissmallandeasilyfitsinmemory.Herearemoredetailsonanti-join:

/wiki/Relational_algebra#Antijoin

Problem2

ConsideranindexorganizedasaB+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,sothatthenumberofblocksthatmustbe

examinedpersearchislog_mN.

Questions:

(i)Whatvalueofmminimizesthetimetosearchforagivenrecord?AnapproximateanswerisOK.(HINT:Ifyoucomeupwithanequationwhichishardtosolvealgebraically,tryplugginginvaluestolocatetherootoftheequation.)Thevalueyouobtainshouldbeindependent

of"b"!

(ii)Whathappensastheseekandlatencyconstant(25ms)decreases?Forinstance,ifthisconstantiscutinhalf,howdoestheoptimummvaluechange?

Answer:

Let

T1

bethetimetakentoreadoneblockintomainmemoryand

T2

bethetimetoprocessthatblockinmemory.If

n

blocksareexaminedtosearchforagivenrecord,thenthetimetakenforthissearchis:

n*(T1

+T2)

Substitutingtheappropriateexpressionsforallthevariables,weget

T(m)=[(25+0.02m)+(a+blog2m)]*logmN

Ignoring

a

incomparisonwith

30,weget

T(m)=[25+0.02m+blog2m]*logmN

Substituting

log2m

by

ln(m)/ln(2)

and

logmN

by

ln(N)/ln(m),weget

T(m)=[(25+0.02m)/ln(m)]*ln(N)+b*ln(N)/ln(2)

Hence,tominimizeT(m),weneedtominimize

f(m)=(25+0.02m)/ln(m).Anumberoftechniquescanbeappliedtodeterminethevalueof

m

thatminimizesthisexpression.Forexample,takingthederivativeandsettingittozero(f'(m)=0),weget

m*(ln(m)-1)=1250

Thiscanbesolvedtoyieldanintegralvalueof

272.Itiseasytoverifythatthisvaluedoesindeedminimize

f(m)

andhence

T(m).

Seek+latencyconstantdecreases:

Letussplit

T(m)

intothreecomponentsasfollows(here,

ts

istheseek+latencytimeconstantwhichwas30intheabovecase):

Totalseekandlatencytime

Ta

=ts

*ln(N)/ln(m)

Totaltransfertime

Tb

=0.02*m*ln(N)/ln(m)

Totalbinarysearchtime

Tc

=b*ln(N)/ln(2)

Ofthese,

Tc

isindependentof

m,

Ta

isadecreasingfunctionof

m

whereas

Tb

isanincreasingfunctionof

m.If

ts

isverysmall,then

Ta

isnegligiblecomparedto

Tb.Hence,wemustchooseasmallvalueof

m

tominimizethesearchtime.Ontheotherhand,if

Ta

isverylargecomparedto

Tb,thentheformerdominatesandwechoosealargevalueof

m

tominimizesearchtimes.Fromtheselimitingcases,itiseasytoseethatif

ts

decreases,theoptimumvalueof

m

decreases.Inparticular,if

ts

=25/2=12.5,wegetanoptimumvalueof

155

(byproceedingalongthesamelinesasabove).

Problem3

Tobuildahashindexforamulti-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,andpfortheexpectednumberofbucketsthatmustbe