CSC 457/557

Assignment 9 - logging and isolation - Due Monday, 9 April 2018

1. There has been a power failure, and on restart, The following is found on the REDO log.
In redo logging, a <commit T> entry must be in the log on disk before any data written by T can be on the disk. Thus, recently committed transactions will have to be redone.
Values in the redo log are the new values written (but may not have reached the disk.)
This log also shows a "checkpoint. The entry <start ckpt(t1)> means that only t1 is an active transaction when the checkpoint started, so there is no need to look back in the log farther than <start t1>, so I have not shown it.
The procedure for recovering with a REDO log is:
  1. scan the log backwards, looking for commit and abort records, make a list of each, until you come to start checkpoint.
  2. Continue backwards until you reach start t1.
  3. Go forwards, redo every committed transaction. You don't need to redo t0, and you shouldn't redo any aborted transactions.

Show, for a, b and c, the successive values they should take.
			a	b	c
			0	9	5	-- disk after crash.
<start t1>
<t0, a, 0>					-- note this value will be on disk
<commit t0>
<t1, b, 3>		
<start ckpt(t1)>				-- can't assume t1's changes on disk
<t1, a, 3>		
<start t2>
<t1, c, 7>
<commit t1>
<t2, a,  13>
<end ckpt>
<start t3>
<t2, c, 5>
<start t4>
<t4, b, 6>
<abort t2>
<start t5>
<start t6>
<t4, a, 6>
<commit t4>
<t6, a, 16>
<t5, c, 100>
<t6, b, 16>
<commit t6>
<t5, b, 116>

2. Serializability. What happens when 3 transactions are "concurrent?" For this assignment, use Locking, part a. Locking is the most common. There are two other methods, b. timestamps, and c. validation. I have left them in for future reference.

  1. In a locking scheduler, transactions will be serializable, that is, equivalent to some serial order of execution, (not necessarily the same as their numbers.)
    Use strict two-phase locking (to avoid "dirty data", i.e. don't unlock until all writes have occurred, so you know the transaction won't abort.)

    2. ------------------------ (skip)
  2. In a timestamp scheduler, timestamps are assigned based upon the order in which transactions start. Consider the transaction numbers to be their timestamps.
    Assume multiversion timestamping  with a commit bit. -- (or state your other assumptions)
  3. When using validation for concurrency control, the equivalent serial order is based upon when each transaction validates, that is: after doing all reads, and before doing any writes. Note that, during validation, it is known which elements it is going to write. In other words, the scheduler knows both the read set (RS) and write set (WS) of the transaction.
    A validated transaction always commits. When validation fails, the transaction is aborted (rolled back).

Try carrying out the actions in some interleaved manner, such as left-to-right across each line. of course, soon someone will have to wait for a lock.
Show:
Notation: Let A = B+2 stand for:  read(B,t); t = t+2; write(A,t), where t is a local variable of the transaction. The write happens some time after the read.
(initially, a=b=c=2)
t1			t2			t3
a = a+10		read a			b = b*2
b = b+10		read c			a = a*2

If an action must be delayed, delay it as necessary.  If a deadlock develops, note that, then abort. If a transaction must be aborted, you may restart it once at most.

  1. (locking) Show the order things will happen, especially when locks are granted, and released. On abort, undo all writes and release all locks.
    Choose lock types:  Either one kind of (exclusive) lock □, or both read (shared) and write (exclusive) locks. □
    2. ------------------------ (you are done)
  2. For timestamps, remember to record the write timestamp for each version, and also the highest read timestamp. Delay a read if the value that should be read is not yet committed.
  3. In the case of validation, all the reads precede validation and all the write items are known. If the transaction validates, then the writes are done.Assume this order, then validate in validation order. *( put near "read" the new local value.) Naturally, if a transaction fails to validate, it cannot write or commit.