Department of Electrical Engineering and Computer ScienceMASSACHUSETTS INSTITUTE OF TECHNOLOGY6.830 Database Systems: Fall 2008 Quiz IIThere are 14 questions and 11 pages in this quiz booklet. To receive credit for a question, answerit according to the instructions given. You can receive partial credit on questions. You have 80minutes to answer the questions.Write your name on this cover sheet AND at the bottom of each page of this booklet.Some questions may be harder than others. Attack them in the order that allows you to makethe most progress. If you find a question ambiguous, be sure to write down any assumptions youmake. Be neat. If we can’t understand your answer, we can’t give you credit!THIS IS AN OPEN BOOK, OPEN NOTES QUIZ.NO PHONES, NO LAPTOPS, NO PDAS, ETC.YOU MAY USE A CALCULATOR.Do not write in the boxes below1-3 (xx/14) 4-6 (xx/26) 7-8 (xx/10) 9-11 (xx/26) 12-14 (xx/24) Total (xx/100)Name: 2008 Quiz 26.830 Fall 2008, Quiz 2 Page 2 of 11I Short Answer1. [4 points]: List two reasons why a column-oriented design is advantageous in a data warehouseenvironment.(Write your answer in the spaces below.)A.B.2. [4 points]:Which of the following statements about the MapReduce system are true:(Circle T or F for each statement.)T F A MapReduce job will complete even if one of the worker nodes fails.T F A MapReduce job will complete even if the master node fails.T F Map workers send their results directly to reduce workers.T F If there are M map tasks, using more than M map workers may improve MapReduce performance.Name:6.830 Fall 2008, Quiz 2 Page 3 of 113. [6 points]:Which of the following statements about the two-phase commit (2PC) protocol are true:(Circle T or F for each statement.)T F In the “no information” case (i.e., when a subordinate asks the coordinator about the outcome of atransaction that the coordinator has no information about), the coordinator running the presumed abortversion of 2PC returns the same response to a subordinate as it would in basic 2PC.T F The Presumed Commit protocol reduces the number of forced writes required by the coordinator com-pared to basic 2PC for transactions that successfully commit.T F The Presumed Abort protocol reduces the number of forced writes required of the coordinator comparedto basic 2PC for transactions that abort.F F In basic 2PC, a subordinate that votes to abort a transaction T receives no more messages pertaining toT , assuming neither T ’s coordinator nor any of T’s subordinate nodes fail.Name:6.830 Fall 2008, Quiz 2 Page 4 of 11II C-StoreDana Bass is trying to understand the performance difference between row- and column- oriented databases.Her computer’s disk can perform sequential I/O at 20 MB/sec, and takes 10 ms per seek; it has 10 MB ofmemory. She is performing range queries on a table with 10 4-byte integer columns, and 100 million rows.Data is not compressed in either system, and all columns are sorted in the same order. Assume each columnis laid out completely sequentially on disk, as is the row-oriented table.4. [16 points]: Fill in the table below with your estimates of the minimal I/O time for each operation,in a row-store and a column-store. Assume that all reads are on contiguous groups of rows, and thatqueries output row-oriented tuples.Num. Columns Num. Rows Column-Oriented System Row-Oriented SystemRead Read1 10 Million10 10 MillionName:6.830 Fall 2008, Quiz 2 Page 5 of 11III BigTableConsider an example table storing bank accounts in Google’s BigTable system:Key Value“adam” $300“evan” $600“sam” $9000The bank programmer implements the deposit function as follows:function deposit(account, amount):currentBalance = bigtable.get(account)currentBalance += amountbigtable.put(account, currentBalance)5. [4 points]: Given the table above, a user executes deposit(“sam”, $500). The program crashessomewhere during execution. What are the possible states of the “sam” row in the table? Provide ashort explanation for your answer.(Write your answer in the space below.)6. [6 points]: Given the table above, a user executes deposit(“sam”, $500). The program completes.Immediately after the program completes, the power goes out in the BigTable data center, and all themachines reboot. When BigTable recovers, what are the possible states of the “sam” row in the table?Provide a short explanation for your answer.(Write your answer in the space below.)Name:6.830 Fall 2008, Quiz 2 Page 6 of 11Now consider the following pair of functions:function transfer(sourceAccount, destinationAccount, amount):sourceBalance = bigtable.get(sourceAccount)if sourceBalance < amount:raise Exception("not enough money to transfer")sourceBalance −= amountdestinationBalance = bigtable.get(destinationAccount)destinationBalance += amountbigtable.put(sourceAccount, sourceBalance)bigtable.put(destinationAccount, destinationBalance)function totalAssets():assets = 0for account, balance in bigtable:assets += balancereturn assets7. [6 points]: Given the table above, a program executes transfer(“evan”, “adam”, 200). While thatfunction is executing, another program executes totalAssets(). What return values from totalAssets()are possible? For the purposes of this question, assume there is only one version of each value, and thatthe values in BigTable are stored and processed in the order given above (i.e., “adam”, “evan”, “sam”).Provide a short explanation for your answer.(Write your answer in the space below.)8. [4 points]: If the data were stored in a traditional relational database system using strict two-phaselocking, and transfer() and totalAssets() were each implemented as single transactions, what would thepossible results of totalAssets() be? Provide a short explanation for your answer.(Write your answer in the space below.)Name:6.830 Fall 2008, Quiz 2 Page 7 of 11IV Distributed Query ExecutionSuppose you have a database with two tables with the following schema:T1 : (A int PRIMARY KEY, B int, C varchar)T2 : (D int REFERENCES T1.A, E varchar)And suppose you are running the following query:SELECT T1.A,COUNT(*)FROM T1,T2AND T1.A = T2.DAND T1.B > nGROUP BY T1.AYour system has the following configuration:Parameter Description Value|T 1| Size of table T1 300 MB|T 2| Size of table T2 600 MB|M| Size of memory of a single node 100 MB||T 1|| Number of records in T 1 10 million|int| Size of integer, in bytes 4T Disk throughput, in bytes / sec 20 MB/secN Network transmit rate, in bytes / sec 10