Name ____________________________1UNIVERISTY OF CALIFORNIA, BERKELEYCollege of EngineeringDepartment of EECS, Computer Science DivisionCS186J. HellersteinSpring 2003Final ExamFinal Exam: Introduction to Database SystemsThis exam has seven problems, each worth a different amount of points. Each problem ismade up of multiple questions. You should read through the exam quickly and plan yourtime-management accordingly. Before beginning to answer a question, be sure to read itcarefully and to answer all parts of every question! Please do not spend timeexplaining your answers unless we explicitly ask that you do so. We will not begiving extra or partial credit for explanations unless we ask for them.Good luck!You must write your answers on the exam. You also must write your name at the top ofevery page, and you must turn in all the pages of the exam. Do not remove pages fromthe stapled exam! Extra answer space is provided in case you run out of space whileanswering. If you run out of space, be sure to make a “forward reference” to the pagenumber where your answer continues.Class Account ____________________________Do not write in this spaceName ____________________________21. Recovery [20 points]In this question we explore the interplay between buffer management andrecovery. We present four scenarios below. For each scenario, you must followthe following guidelines:— Choose a maximally efficient protocol!— Among all protocols with the same level of efficiency, choose the simplest.Each scenario corresponds to exactly one of the four quadrants in the chart at thebottom of the page. Place the letter of each scenario (a, b, c, d) in theappropriate quadrant. Note that while each letter goes in only one quadrant, itis possible that some quadrants will have more or less than one letter in them! [5points each]a. Scenario: Traditional ARIES. You have been told to implement theARIES recovery protocol as discussed in class.b. Scenario: Buffer Pool Bigger than Database. Modern servers ship withas much as 32GB of RAM. Hence for many customers, their databaseswill never be larger than available RAM. You have a startup companythat is designing a special-purpose DBMS for these customers.c. Scenario: Before-Image Logging. In order to keep your logs morecompact, you store only the “before-image” of the data in update logrecords, and not the “after-image”. (Recall that the before-image has thestate of the page before the update; the after-image would have also shownthe state of the page after the update.)d. Scenario: Untrusted Buffer Manager. No matter how many times youexplain it, the engineers implementing the buffer manager cannotunderstand the log manager. So you’re going to have to choose a protocolthat can handle any mix of page replacement decisions.No Steal StealForce No ForceName ____________________________32. ARIES [20 points]Consider the following log where the DPT represents the Dirty Page Table andTT represents the Transaction TableLSNContentsprevLSNundonextLSN10Update T1 writes p120Begin Checkpoint30End CheckpointDPT: (1,10)TT: (T1, Running, 10)40Update: T1 writes p31050Insert: T2 writes p560Update: T1 writes p34070Update: T2 writes p85080Abort: T16090CLR: T1 Undo p3 LSN 608040100Commit: T270110End T2100CRASH, RESTARTAnswer the following questions:a. What is the smallest LSN accessed during the Analysis phase. [2 points]b. Fill in the contents of the Dirty Page Table and the Transaction Table at theend of the Analysis phase. (you may not need all the space we give you) [10points]PageIDRecLSNc. At which LSN does the Redo phase begin? [2 points]d. What entries (specify only LSNs) do get undone as part of the Undo phase? [6points]XIDStatusLastLSNName ____________________________43. Functional Dependencies and Normalization [20 points]Consider the relation schema R = (A, B, C, D, E, F) and the set of functionaldependencies F: A->B, A->C, BC->E, BC->D, E->F, BC->FNote that in all the following, you will never have to compute F+, the closure ofF!a. List the minimal candidate key(s) for R. Write ‘none’ if you think thereare no candidate keys. [2 points]b. List the FDs in F that violate BCNF. (Hint: There are four) [4 points]c. Is R in 3NF (yes or no)? [2 points]d. Is F a minimal cover? [2 points](continued)Name ____________________________5e. Suppose we decompose R into the following tables:R1 = (B, C, E)R2 = (B, C, F)R3 = (B, C, D) andR4 = (A, B, C).This decomposed schema is indeed in BCNF (you can trust us on this!)Unfortunately, this decomposition is not dependency-preserving; inparticular, the dependency E->F cannot be checked on a single table. ACHECK ASSERTION can be used to enforce E->F.Complete the following SQL statement for this particular CHECKASSERTION needed to guarantee E->F. [8 points]CREATE ASSERTION checkDepCHECK ( NOT EXISTS( SELECT * FROM R1, R2WHERE _______________________GROUP BY _____________________HAVING COUNT(__________________________)__________))f. Why might the ASSERTION in (e) be expensive? [2 points] i. Updates to R1 and R2 are frequent ii. Inserts to R1 and R2 are frequent iii. Insertions to R2 are frequent; R1 rarely changes. iv. Reads to R1 and R2 are frequent v. (i) and (ii) vi. (i), (ii), (iii) vii. All of the aboveAnswer (choose one): ___________Name ____________________________64. Database Tuning [14 points]Consider the following BCNF relationalApartment (aid, capacity)GraduateStudent (SID, age, sex, dept, GPA, aid)— GraduateStudent.aid is a foreign key referencing Apartment.— There are very few “single” apartments (i.e. where capacity=1)— 50% of the Graduate Students are males.a. You are told that the following three queries are the most common. Foreach of these queries, we have listed three different indexes as possibleaccess methods. Pick the access method that would benefit the query mostin terms of I/O performance. Assume that these queries occur much morefrequently than updates. [3 points each]Query 1: List aids of apartments with capacity=1 i. Clustered B+Tree index for Apartment on aid field ii. Unclustered B+Tree index for Apartment on capacity field iii. Clustered B+Tree index for Apartment on capacity field.Answer (choose one): ___________Query 2: List SIDs of male graduate students i. No indexes. Use a file scan on GraduateStudent. ii. Unclustered B+Tree index for GraduateStudent on sex iii. Clustered B+Tree index for GraduateStudent on SIDAnswer
View Full Document
Unlocking...