CS157b Spring 2023 Practice Final

If you did well on the midterm, the same approach to studying should work for the final. If not, if adjust the amount of studying you do for the final and experiment with how the way you are studying helps you remember the material and how it affects your ability to use the material flexibly.

Here are some facts about the actual final:

1. It is comprehensive covering all the material of the semester.
2. It is closed book, closed notes. Nothing will be permitted on your desk except your pen (pencil) and test.
3. You should bring photo ID.
4. There will be more than one version of the test. Each version will be of comparable difficulty.
5. It is 10 problems, 6 problems will be on material since the midterm, four problems will come from the topics covered prior to the midterm.
6. Two problems will be exactly (less typos) off of the practice final, and one will be off of practice midterm.

The practice final is below:

1. Imagine the partial log file `langle START\ T rangle, langle T, X, 9rangle, langle START\ S rangle, langle S, Y, 6 rangle, langle T, Y, 3 rangle, langle COMMIT\ S rangle`, crash. Suppose undo logging was being used. What elements would have had there values stored on disk? What would be undone during recovery?
2. Consider the sequence of operations and log records:
   `langle START\ T_1 rangle`, `I_1(A)`, `R_1(A,t_1)`, `t_1:=t_1 + 5`, `langle START\ T_2 rangle`,
   `langle T_1, A, 99 rangle`, `W_1(A,t_1)`, `langle START\ T_3 rangle`, `I_2(B)`, `R_2(B,t_2)`, `t_2:= t_2 + 3`,
   `langle T_2, B, 12 rangle`, `W_2(B,t)`, `langle T_3, C, 1 rangle`, `W_3(C,5)`, `O_1(A)`, `langle COMMIT\ T_1 rangle`, `O_2(B)`, `langle COMMIT\ T_2 rangle`.
   Suppose we started a non-quiescent checkpoint right after the `W_1(A,t_1)`, what transactions would be listed in the start checkpoint?
3. Briefly explain the log record format in ARIES. Explain how ARIES differs from undo/redo logging.
4. Define the following notions and give an example of a nontrivial schedule (no empty schedules please!) which satisfies the notion and one that does not: (a) serializable schedule (example should not be a serial or conflict serializable schedule), (b) conflict serializable schedule, (c) recoverable schedule.
5. Give an argument based on two transactions (you don't have to show the general `n` transaction case) that two phase locking guarantees conflict serializability.
6. Briefly explain how timestamp concurrency control ensures serializability of schedules. From your answer based on situations where serializability commonly fails. How does multi-version concurrency allow for greater concurrency than regular timestamp concurrency control? Briefly explain the connection between timestamp concurrency control, locking, and database isolation levels.
7. Give the parallel algorithm from class for computing the join of two relations $R \bowtie S$. Give its cost on `N` machines. Give the distributed algorithm from class for computing $R \bowtie S$ on two machines.
8. Explain how the Two Phase Commit protocol for distributed transactions works. Give a concrete example of a transaction on at least three machines and the messages they would send back and forth.
9. In terms of OLAP, what is a star schema? Suggest a star schema that might arise in the context of fitness tracking. Explain the SQL CUBE and ROLLUP operations. Give examples to illustrate how they differ.
10. Let `Y` be 4 + mod 2 of the rightmost nonzero digit of your student ID. So if your ID was 74547300 then `Y = 4 + 1 =5` as 3 mod 2 is 1. Come up with a list of `Y+2` household items to hoard. For example, you might hoard toilet paper. Make a table consisting of `Y` hoarders by these `Y+2` items. Roll a six-sided dice for each pair (user i, item j), if the dice comes up 1 or 2, say that item is hoarded by that user. Write the table your got. Show how the A Priori algorithm would operate on this table with support threshold 3.