--------------------------------------------------------------------------------
LAB 10 | Recovery with logical undo.
--------------------------------------------------------------------------------

--------------------------------------------------------------------------------
PRACTICE EXERCISES
--------------------------------------------------------------------------------

(1) Get familiar with the terms:
    - logical operation,
    - logical undo operation,
    - logical and physical logging,
    by attending the lecture and reading chapters 16.7 from the textbook.

(2) Consider the following log. Write the log records resulting from
    aborting transaction T1.

    Log:
    <T2,start>
    <T2,O1,operation-begin>
    <T2,B,200,100>
    <T2,O1,operation-end,(B,+100)>
    <T1,start>
    <T1,C,50,200>
    <T2,A,100,150>
    <T1,O2,operation-begin>
    <T1,B,100,400>
    <T1,O2,operation-end,(B,-300)>
    <T2,commit>
    <T1,C,200,300>


(3) [Ex. 16.20 from textbook] Consider the following log. Explain what would
    happen during recovery when the system crashes (a) before, (b) after the
    operation abort log record is written for operation O1.

    Log:
    <T0,start>
    <T0,B,2000,2050>
    <T0,O1,operation-begin>
    <T0,C,700,600>
    <T0,O1,operation-end,(C,+100)>
    <T1,start>
    <T1,O2,operation-begin>
    <T1,C,600,400>
    <T1,O2,operation-end,(C,+200)>
    <T0,C,400,500>
    <T0,O1,operation-abort>
    <T0,B,2000>
    <T0,abort>
    <T1,commit>


(4) Consider the following log. What would happen during the recovery if the
    system crashes at the end of the log? And what would happen if the system
    crashes again while recovering from the first crash, just before writing the
    abort log for T1?

    Log:
    <T2,start>
    <T2,O1,operation-begin>
    <T2,B,200,100>
    <T2,O1,operation-end,(B,+100)>
    <T1,start>
    <T1,C,50,200>
    <T2,A,100,150>
    <T1,O2,operation-begin>
    <T1,B,100,400>
    <T1,O2,operation-end,(B,-300)>
    <T1,C,200,300>
    ------------CRASH-------------


(5) CHECKLIST:
    - I can explain what is a logical operation and why it requires a special
      undo procedure.
    - I can explain the difference between logical and physical logging.
      - I can list the steps and perform a transaction rollback with logical undo.

--------------------------------------------------------------------------------
HOMEWORK
--------------------------------------------------------------------------------

DEADLINE: 02.02.2018, 21:59

Each of the exercises is worth 1 point.

(1) The following Venn diagram summarizes the relationships among several
    classes of schedules [1,2]. Give one example schedule for each of the
    regions S1-S12.

    ┌──────────────────────────────────────────────────────────┐
    │                                             All schedules│
    │         ┌──────────────────────────────────┐             │
    │         │                 View serializable│             │
    │         │     ┌──────────────────────────┐ │             │
    │      S1 │  S2 │  S3 Conflict serializable│ │             │
    │ ┌───────┼─────┼──────────────────────────┼─┼────────────┐│
    │ │    S4 │  S5 │  S6                      │ │Recoverable ││
    │ │┌──────┼─────┼──────────────────────────┼─┼───────────┐││
    │ ││   S7 │  S8 │  S9                      │ │Cascadeless│││
    │ ││┌─────┼─────┼──────────────────────────┼─┼──────┐    │││
    │ │││ S10 │ S11 │ S12                      │ │Strict│    │││
    │ │││     │     │                  ┌──────┐│ │      │    │││
    │ │││     │     │                  │Serial││ │      │    │││
    │ │││     │     │                  └──────┘│ │      │    │││
    │ ││└─────┼─────┼──────────────────────────┼─┼──────┘    │││
    │ │└──────┼─────┼──────────────────────────┼─┼───────────┘││
    │ └───────┼─────┼──────────────────────────┼─┼────────────┘│
    │         │     └──────────────────────────┘ │             │
    │         └──────────────────────────────────┘             │
    └──────────────────────────────────────────────────────────┘

    A schedule is strict, if for each pair of transactions Ti and Tj such that
    Tj reads or writes a data item previously written by Ti, the commit
    operation of Ti appears before the read or write operation of Tj.
    (In other words, transactions can neither read nor write a data item X
    until the last transaction that wrote X has committed or aborted.)

(2) Draw a Venn diagram that shows the relationships between the classes of
    schedules permitted by the following concurrency control protocols:

    2PL
    Timestamp-Ordering
    Validation
    Multiversion Timestamp-Ordering

    Give one example schedule for each of the regions.

--------------------------------------------------------------------------------
REFERENCES
--------------------------------------------------------------------------------

[1] Concurrency Control and Recovery in Database Systems. Philip A. Bernstein,
    Vassos Hadzilacos, Nathan Goodman. https://dl.acm.org/citation.cfm?id=17299
[2] Free copy of [1]: 'Other' tab on https://www.microsoft.com/en-us/research/people/philbe/