《数据库理论与技术》复习题

《数据库理论与技术》期终考试复习题一、选择题: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.二、简答题:考虑用二元联系（图1）对三元联系（图2）的表示：ABABECRARCRBBARC图1图1图2分别给出图1中E，A，B，C，RA，RB和RC的一个实例，这些实例不对应图2中A，B，C和R的任何实例；更改图1中的ER图，引入适当的约束以确保满足约束的E，A，B，C，RA，RB和RC的任何实例都对应于A，B，C和R的一个实例；更改以上的转化以表示在三元联系上的全参与约束；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