CMPS 377 Final, Fall 2001

AMERICAN CNIVERSIT LIBRARY OF BEIRUT American University of Beirut CMPS 377 Advanced Algorithms and Data Structures Fall 2001-2002 Final Exam Date: Feb. 6", 2002, 3:00 — 5:00pm. Instructor: Jihad Boulos Name: cca eeeccceccccceneeeeeeesseeee AMERICAN CNIVERSIT LIBRARY Of BEIRUT This is an open-book, open-note exam. Your exam should have 16 pages, and there are 10 questions totaling 100 points. You may use your notes, class handouts, and the main course textbook. You are NOT allowed to use any external notes. Your answers should be concise, and when possible should be a list of important points rather than prose. Solve us much problems as you can. I advise each one of you to pick the problems that he/she thinks are easiest for him/her and work on them. I also advise you to spend time on understanding the problem and budget your time for solving each problem, or else you will be wasting a lot of time on one problem and will run out of time for other problems. LIBRARY OF BEIKUT Exercise 1 (10 points): Suppose we have two relations: R(a, b, c) and S(c, d, e). Give 6 valid logical plans (either in relational algebra or as logical plan trees) for the following SQL query: SELECT B, C.D FROM R, S WHERE R.c = S.c AND Ruu=5 Exercise 2 (5 points): Suppose we have two relations: R(a, b, c) and S(c, d, €). Consider the following relational algebra expression: IL. [Op esaRacWARe=S: (Rx S)] Transform this expression into an equivalent expression that: - Has no Cartesian products - Performs projections as early as possible - Performs selections as early as possible An “early” selection/projection is a selection/projection that occurs as close as possible to the leaves in the logical plan tree form of the expression. Give projections priority over selections. Exercise 3 (15 points): Suppose relations R and S are not stored in any particular order. Suppose furthermore that two indexes exist on relation R, one on column a and one on column c. No other indexes are present. Give 7 valid physical plans (as physical plan trees) for the following logical plan: [O28 (R)] x Re=Sc {S} Exercise 4 (15 points): Here are the statistics about four relations: W, X, Y, and Z: W(a, b} X(b, ¢} Y(c, d) Z(d, e) T(W) = 100 T(X) = 400 T(Y) = 200 T(Z) = 300 V(W, a) = 80 V(X.) = 200 VCY, c) = 200 ViZ, d) = 200 V(W, b) = 10 V(X.c)= 1 V(Y, d) = 120 VIZ, e) = 80 Estimate the sizes of the following expressions: a) O,235(W) (assume that 35 is present in column a of relation W) b) Osers +h =3(W) (assume that 35 is present in column a and 5 is present in column b) c) wll X (natural join) e) WI xl yz Exercise 5 (9 points): Suppose we have a transaction TI that performs the following two actions: A= A+5:B:=Bt5 Say that UNDO/REDO jogaing is in use, and that initially, A = 5 and B = 5. For each hypothetical disk state shown below, state whether it is a legal state for UNDO/REDO logging. If itis nota legal state. explain why not. Assume the log entries are in the format <Tid, Variable, Old value, New value> a) DB Log ANSWER: b) . <T1, start> DB : <T1, A, 5. 10> <T1. B, 5. 10> ANSWER: <T1, start> DB <T1, A, 5, 10> <T1,B, 5, 10> ANSWER: Exercise 6 (8 points): Say the system reboots after a crash and finds the following disk state: a <T1, start> <T2, start> <TI,A.5> <T1, Commit> <T2, B.5> <T2, A, 15> (CRASH) a CO a) If the system is using UNDO logging, give the initial state of the database before T1 and T2 began executing (i.e.. what were the initial values of A and B on the disk?). b) If the system is using UNDO logging, what will be the final state of the database after recovery (i.e., what will be the values of A and B on the disk after the recovery process has finished?). c) If the system is using REDO logging, give the initial state of the database before T1 and T2 began executing (i.e.. what were the initial values of A and B on the disk?). d) If the system is using REDO logging, what will be the final! state of the database after recovery (i.e.. what will be the values of A and B on the disk after the recovery process has finished?). Exercise 7 (10 points): The following table describes the undo/redo log found on a system after a failure. Action Id Action Type Transaction Dd Other Info trans start T; db write T; ta| to trans start Th db write T2 tn] fe start dump System T; active nN trans Start Ts al db write T3 n end dump System oO db write S trans start db write ) t db write commit commit start checkpoint T,, T3 active db write db write (rans start db write trans start db write end checkpoint System lb write Ts db write db write commit T, db write 28 commit 39 end of log The database dump that occurs between actions 5 and 8 writes a complete copy of the database to tape, to be used in case of medial failure. a) Assume that at action 29 the system crashes but the database is nor lost. Assume that a two pass algorithm is run for recovery, where actions are first undone, and then actions are redone. In the two lines below indicate what actions are undone in the first pass, and what actions are redone. Write the actions in the order they would be undone or redone (left to right). Identify each action by its id given in the first column in the table. b) Now assume that the database is Jost at action 29. In this case we load the saved database from tape and bring it up to date. In the two lines below again indicate what actions are undone and redone to bring the dumped database up to date.