-------------------------------------------------------------------------------- LAB 9 | Recovery algorithm. -------------------------------------------------------------------------------- -------------------------------------------------------------------------------- PRACTICE EXERCISES -------------------------------------------------------------------------------- (1) Get familiar with the terms: - log records and their types, - redo and undo of a log record, - checkpoint, - recovery algorithm (redo and undo phases, compensation log records), by attending the lecture and reading chapters 16.3, 16.4 from the textbook. (2) Consider the following schedule. T1: T2: T3: START read(A) A:=A+1 START read(B) B:=B+1 write(A) COMMIT START read(A) read(B) A:=A+B write(A) (a) Write the log file for that schedule if the initial values of the data items are A=0 and B=1. (b) Identify the transactions that need to be redone and undone if the crash happens at the end of the log. (3) With the initial values A=100, B=200, C=300, write the log file for the following schedule. What happens during the recovery according to the recovery algorithm? Specify the resulting compensation log records. T1: T2: T3: START START START read(C) read(B) read(A) A:=A-20 C:=C+40 write(C) B:=B-80 write(A) write(B) COMMIT ------------CRASH--------------- (4) [Ex. 16.18 from textbook] Consider the following log. What happens during the recovery according to the recovery algorithm? Mark the start and end points of the redo and undo phases. Specify the transactions in the undo list. Log: --------CRASH--------- (5) With the starting values A=3, B=100, write the log file for the following schedule. What happens during the recovery according to the recovery algorithm when the system crashes (a) after commit of T3, (b) after write(B) of T1? Mark the start and end points of the redo and undo phases. Specify the resulting compensation log records. T1: T2: T3: START read(A) A:=A+1 START read(B) B:=B+10 write(A) COMMIT START read(A) read(B) A:=A+B write(A) COMMIT ---------CHECKPOINT--------- read(A) A:=A+B write(B) COMMIT (6) CHECKLIST: - I can explain the purpose of recovery algorithms. - I can identify the transaction that need to be redone and undone after a crash happens. - I can list the log entries for a given schedule. - I can apply the recovery algorithm to bring the database to a consistent state after a crash. - I can explain the purpose of checkpoints and apply them in the recovery process. -------------------------------------------------------------------------------- HOMEWORK -------------------------------------------------------------------------------- DEADLINE: 19.01.2018, 21:59 Write a Python program that implements the validation protocol (Section 15.5 of the text book). The program should be executable with Python 3. Please submit a single python file called 'validate.py'. Your program must execute with the command 'python validate.py ' where is the input file. The output of your program must be printed to the standard output. Your program must execute. If it does not execute, you obtain 0 points. Test it thoroughly. The program will be tested automatically. If it passes >50% of the tests you get 1 point. If it passes >70% of the tests you get 1.5 points. Correct results for >90% of the tests result with 2 points. The input is a text file with operations issued by concurrent transactions. The file contains one operation per line. The format of the operations is the following: 'r 1 a' means that transaction 1 reads data item a 'w 2 b' means that transaction 2 reads data item b 'v 1' means that transaction 1 tries to validate The 'v' operation is the last operation that a transaction may issue. According to the validation protocol, the 'w' operations are write operations and are local to the transactions. They indicate what write operations should be performed if a transaction validates. We assume that, if a transaction validates, the writes will be applied on the database. We are interested only in validation testing. A transaction starts when its first operation is issued. We assume that a transaction finishes just after successful validation test and the validation timestamp equals the finish timestamp. If a transaction does not validate, it should be rolled back. In our case, it means that that transaction should be no longer considered in validation testing. Your program should process the operations from the input file one by one. Each time the 'v' operation is met, the program reports the output of the validation test. An example output should have the following format (the numbers indicate transaction IDs, the boolean value indicates if the transaction validates): 1 True 3 False 2 True You must not change the order of the operations in the input file. The results of validation test must be reported in the order of issued 'v' operations. Mind the order of the operations in the input file. For each validation test ('v' operation) only the operations from the beginning of the file until the validation should be considered. Sample input ('sample-input.txt'): r 1 a r 2 d r 1 b w 1 a v 1 r 2 c r 3 c r 3 d w 3 d v 3 r 2 c w 2 a v 2 Sample output: 1 True 3 True 2 False