《數(shù)據(jù)庫(kù)理論與技術(shù)》復(fù)習(xí)題

《數(shù)據(jù)庫(kù)理論與技術(shù)》期終考試復(fù)習(xí)題一、選擇題:Chubbypresentsitselftoclientsasthisservice:a)Centralizedmutualexclusionb)Hierarchicalmutualexclusionc)Token-basedmutualexclusiond)Contention-basedmutualexclusion.Whichstatementbestdescribesaclient'sinteractionwithChubby?AclientcontactsanyChubbyserver,whichthenforwardstherequesttotheappropriateserverintheChubbycell.AclientcontactsanyChubbyserver,whichcanprocesstherequestsinceallChubbyserversarereplicated.AclientcontactstheChubbymaster,whichthenforwardstherequesttotheappropriateserverintheChubbycell.AclientcontactstheChubbymaster,whichhandlesallclientrequests.BysendingmessagesthroughPaxos,processescanensurethatconcurrentmessagesbecome:a)Globaltimeorderedmulticasts.b)Totallyorderedmulticasts.c)Causallyorderedmulticasts.d)Unorderedmulticasts.Basedontheirvectortimestamps,whicheventcausallyprecedes(4,2,8,5)?a)(3,1,7,7)b)(5,1,6,2)c)(4,2,8,4)d)(4,3,8,5)WithPaxos,messagesequencenumbersareassignedbythe:a)Acceptorb)Clientc)Learnerd)ProposerPaxosreachesagreementwhen:Allproposersagreeonavaluetosendtotheacceptors.Allacceptorsagreetoaproposedvalue.Themajorityproposersagreeonavaluetosendtotheacceptors.Themajorityofacceptorsagreetoaproposedvalue.Awrite-aheadlogdoesNOTenableaprocessto:a)Undochangesincaseofanabort.b)Recordthatatransactionhascommitted.c)Recordtheresponsethatwassenttoavoteinacommitprotocol.d)Achievehigherperformancebyprefetchingdata.Toabortadistributedtransaction:Atleastoneparticipantmustvotetoabort.Themajorityofparticipantsmustvotetoabort.Alloftheparticipantsmustvotetoabort.Allliveparticipantsmustvotetoabort.Themotivationforaneventualconsistencymodelwas:Itisimpossibletohavehighlyavailablereplicateddatathatisfullyconsistentinasystemthatcansurvivenetworkpartitioning.Datainconsistenciesarehighlyundesirable,sotheprimaryfocusshouldbeonensuringthatallreplicasareconsistent.Distributedcommitprotocolscanneverworkreliably,sodataisboundtobecomeinconsistentonsomeparticipants.Datamightbeinaninconsistentstateduringtheexecutionoftransactionsbutwillbemadeconsistentwhentheycommit.InBigtable,eachserverisresponsibleforservingtablets.Atabletis:Asubsetofrowsandcolumnfamilies.Asubsetofrowsbutstoresallcolumnfamilydataforthoserows.Asetofoneormorecolumnfamiliesbutitstoresallrowdataforthosecolumnfamilies.Exactlyonerowandonecolumnfamily.Differingfromadistributedhashtable,Bigtable:a)Cansupportreplicationforfaulttolerance.b)Supportsmorethanoneprimarykeyforlookingupdata.c)Canassociatelargeamountsofdatawithakey.d)Sortsitsdatabythekeyandallowsiterationoverrowsofsorteddata.Whichoftheseoperationsismostefficientlyimplementedonalarge-scaleGFS(GoogleFileSystem)system?a)Readone1TBfile.b)Read1million1MBfiles.c)Writeone1TBfile.d)Write1million1MBfiles.ThepartitioningfunctioninMapReducea)Determineswhichshardwillbeassignedtoaspecificmapworker.b)Filtersoutunnecessaryinputdatapriortobeingprocessedbythemapworker.c)Determinesthedivisionofavailableserversintomapworkersandreduceworkers.d)Determineswhichreduceworkerwillprocessdataassociatedwithaparticularkey.AmazonDynamoallowsanadministratortoaddagreaterloadtoabiggerserverinthegroupby

a)Configuringtheclientlibrarytoissueahigherpercentageofitsrequeststothatserver.b)Configuringotherserverstoforwardsomepercentageoftheirrequeststothebiggerserver.c)Usingconsistenthashingandgivingalargerconsecutiverangeofthehashspacetotheserver.d)Assigningmorevirtualnodestothatserver.WhichofthefollowingisNOTaresponsibilityofamapworkerintheMapReduceframework:a)Generate(key,value)pairs.b)Target(key,value)dataforoneofRreduceworkers.c)Partitionoriginaldataintoshards.d)Discarddataofnointerest.AkeydesignprincipleoftheGoogleclusterarchitectureisa)Mergingisfast;breakupdatabasesintolotsofpiecesanduselotsofprocesses,eachworkingonapieceofthedata.b)Minimizethenumberofphasesinatask;createmanyreplicasofadatabaseandalloweachsystemfullaccesstoitwithouttheneedforsharingorlocking.c)Minimizecontextswitchoverhead;machinesarecheapandit'smoreefficienttodevoteanodetoonetaskexclusively.d)Machinesandsoftwarefail;runthesametaskredundantlyinparalleltoensuresuccessfulexecution.二、簡(jiǎn)答題:考慮用二元聯(lián)系（圖1）對(duì)三元聯(lián)系（圖2）的表示：ABABECRARCRBBARC圖1圖1圖2分別給出圖1中E，A，B，C，RA，RB和RC的一個(gè)實(shí)例，這些實(shí)例不對(duì)應(yīng)圖2中A，B，C和R的任何實(shí)例；更改圖1中的ER圖，引入適當(dāng)?shù)募s束以確保滿(mǎn)足約束的E，A，B，C，RA，RB和RC的任何實(shí)例都對(duì)應(yīng)于A，B，C和R的一個(gè)實(shí)例；更改以上的轉(zhuǎn)化以表示在三元聯(lián)系上的全參與約束；Supposethatweareusingextendablehashingonafilethatcontainsrecordswiththefollowingsearch-keyvalues:2,3,5,7,11,17,19,23,29,31,35,27Showtheextendablehashstructureforthisfileifthehashfunctionish(x)=xmod11andbucketscanholdthreerecords.Showhowtheextendablehashstructureofpart1)changesastheresultofeachofthefollowingsteps:a.Delete11.b.Insert15.c.Delete31.d.Insert25.Thekey-valuestoreusesquorumsforconsistency.Thetotalnumberofreplicas,N,forakey,isfixed–however,Nmaybedifferentfordifferentkeys.Eachreadhastoaccessatleastrreplicas(andreturnsifallofthemagree),whileeachwritehastowritetoatleastwreplicas.Foreachofthefollowingdesignchoices,saywhetherit(byitself)doesordoesnotguaranteestrongconsistency,i.e.,onecopyserializability?a.w=3,r=1b.w=2N/3c.r+w=Nd.w=Ne.r+w>N/2f.r+w>3N/2g.r+w>3N/2,w>2N/3Thefollowingscenarioisadistributedfilesystemwhichspansmultipledatacenters.Thereareseveralchoicesforhowtohandlenetworkpartitionsthatoccurinbetweendatacenters(givenbelow).Foreachofthesechoices,tellme:ifitviolatesconsistency？Allowallpartitionstoprocessbothreadsandwrites.Allowallpartitionstoprocessreads,butonlyonespecialpartition(prechosen)toprocesswrites.Allowonlythepartitionwhichhasatleastaquorumnumberofservers(measuredacrossalldatacenters)toexecutewrites.Untilpartitionsarerepaired,allowonlyreadsbutnowrites.Allowonlypartitionswithaquorumofservers(measuredacrossalldatacenters)toexecutewritesandreads.Lamport’sLogicalClocks,amongotherthings,helpmakeinferencesaboutconsistencyofreplicateddataitemsoperateduponconcurrently.Thefollowingfigureshowsthetime-linediagramsofthreeprocessesP,QandR.Fillinthelogicaltimesforeachevent(a)–(o)inthethreeprocessesusingtherulesoflocalordering,send/receiveorderingandtransitiveclosure.Assumingyouaregivenonlythelogicaltimesforeacheventinaprocess,answerthefollowingTrue,FalseorUnknownquestionsEventbhappenedbeforeeventa.Eventsa,handmhappenedconcurrently.Eventnhappen