CS计算机代考程序代写 database concurrency 2021/4/28 Properties of Schedules

2021/4/28 Properties of Schedules
Properties of Schedules
Schedule Properties Serializable Schedules Transaction Failure Recoverability Cascading Aborts Strictness
Classes of Schedules
>>
COMP9315 21T1 ♢ Properties of Schedules ♢ [0/12]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-schedules/slides.html 1/14

2021/4/28 Properties of Schedules
∧ >>
❖ Schedule Properties
If a concurrent schedule on a set of tx’s TT …
produces the same effect as a serial schedule on TT
then we say that the schedule is
serializable
A goal of isolation mechanisms (see later) is
arrange execution of individual operations in tx’s in TT
to ensure that a serializable schedule is produced
Serializability is one property of a schedule, focusing on isolation
Other properties of schedules focus on recovering from failures
COMP9315 21T1 ♢ Properties of Schedules ♢ [1/12]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-schedules/slides.html 2/14

2021/4/28 Properties of Schedules
<< ∧ >> ❖ Serializable Schedules
Producing a serializable schedule
eliminatesallupdateanomalies ✓
may reduce opportunity for concurrency
✗
may reduce overall throughput of system
✗
If DB programmers know update anomalies are unlikely/tolerable
serializable schedules may not be neccessary
some DBMSs offer less strict isolation levels (e.g.repeatableread)
allowing more opportunity for concurrency ✓
COMP9315 21T1 ♢ Properties of Schedules ♢ [2/12]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-schedules/slides.html 3/14

2021/4/28 Properties of Schedules
<< ∧ >>
❖ Transaction Failure
So far, have implicitly assumed that all
transactions commit.
Additional problems can arise when transactions abort.
Consider the following schedule where transaction T1 fails:
T1: R(X) W(X) A
T2: R(X) W(X) C
Abort will rollback the changes to X, but … Consider three places where the rollback
might occur:
T1: R(X) W(X) A [1] [2] [3]
T2: R(X) W(X) C
COMP9315 21T1 ♢ Properties of Schedules ♢ [3/12]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-schedules/slides.html 4/14

2021/4/28 Properties of Schedules
<< ∧ >> ❖ Transaction Failure (cont)
Abort / rollback scenarios:
T1: R(X) W(X) A [1] [2] [3]
T2: R(X) W(X) C
Case [1] is ok
all effects of T1 vanish; nal effect is simply from T2
Case [2] is problematic
some of T1’s effects persist, even though T1 aborted
Case [3] is also problematic
T2’s effects are lost, even though T2 committed
COMP9315 21T1 ♢ Properties of Schedules ♢ [4/12]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-schedules/slides.html 5/14

2021/4/28 Properties of Schedules
<< ∧ >>
❖ Recoverability
Consider the serializable schedule:
T1: R(X) W(Y) C
T2: W(X)
A
(where the nal value of Y is dependent on the X value)
Notes:
the nal value of X is valid (change from T2 rolled back)
T1 reads/uses an X value that is eventually rolled-back
eventhoughT2 iscorrectlyaborted,ithas produced an effect
Produces an invalid database state, even though serializable.
COMP9315 21T1 ♢ Properties of Schedules ♢ [5/12]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-schedules/slides.html 6/14

2021/4/28 Properties of Schedules
<< ∧ >>
❖ Recoverability (cont)
Recoverable schedules avoid these kinds of
problems.
For a schedule to be recoverable, we require additional constraints
alltx’sTi thatwritevaluesusedbyTj must commitbeforeTj commits
and this property must hold for all transactions Tj
Note that recoverability does not prevent “dirty reads”.
In order to make schedules recoverable in the presence of dirty reads and aborts, may need to abort multiple transactions.
COMP9315 21T1 ♢ Properties of Schedules ♢ [6/12]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-schedules/slides.html 7/14

2021/4/28 Properties of Schedules
<< ∧ >>
❖ Cascading Aborts
Recall the earlier non-recoverable schedule:
T1: R(X) W(Y) C
T2: W(X)
A
To make it recoverable requires:
delayingT1’scommituntilT2 commits ifT2 aborts,cannotallowT1 tocommit
T1: R(X) W(Y) … C? A!
T2: W(X) A
Known as cascading aborts (or cascading rollback).
COMP9315 21T1 ♢ Properties of Schedules ♢ [7/12]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-schedules/slides.html 8/14

2021/4/28 Properties of Schedules
<< ∧ >> ❖ Cascading Aborts (cont)
Example:T3 aborts,causingT2 toabort, causingT1 toabort
T1:
T2:
T3: W(X)
R(Y) W(Z)
A
R(X) W(Y)
A
EventhoughT1 hasnodirectconnectionwith T3 (i.e.noshareddata).
This kind of problem …
can potentially affect very many concurrent transactions
could have a signicant impact on system throughput
COMP9315 21T1 ♢ Properties of Schedules ♢ [8/12]
A
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-schedules/slides.html 9/14

2021/4/28 Properties of Schedules
<< ∧ >> ❖ Cascading Aborts (cont)
Cascading aborts can be avoided if
transactions can only read values written by committed transactions
(alternative formulation: no tx can read data items written by an uncommitted tx)
Effectively: eliminate the possibility of reading dirtydata ✓
Downside: reduces opportunity for concurrency ✗
GUW call these ACR (avoid cascading rollback) schedules.
All ACR schedules are also recoverable.
COMP9315 21T1 ♢ Properties of Schedules ♢ [9/12]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-schedules/slides.html 10/14

2021/4/28 Properties of Schedules
<< ∧ >>
❖ Strictness
Strict schedules also eliminate the chance of
writing dirty data. A schedule is strict if
no tx can read values written by another uncommittedtx (ACR)
no tx can write a data item written by another uncommitted tx
Strict schedules simplify the task of rolling back after aborts.
COMP9315 21T1 ♢ Properties of Schedules ♢ [10/12]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-schedules/slides.html 11/14

2021/4/28 Properties of Schedules
❖ Strictness (cont) Example: non-strict schedule
<< ∧ >>
T1: W(X) A
T2: W(X)
A
Problems with handling rollback after aborts:
whenT1 aborts,don’trollback (needto retain value written by T2)
whenT2 aborts,needtorollbacktopre-T1 (not just pre-T2)
COMP9315 21T1 ♢ Properties of Schedules ♢ [11/12]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-schedules/slides.html 12/14

2021/4/28 Properties of Schedules
<< ∧ ❖ Classes of Schedules Relationship between various classes of schedules: Schedules ought to be serializable and strict. But more serializable/strict ⇒ less concurrency. DBMSs allow users to trade off "safety" against performance. COMP9315 21T1 ♢ Properties of Schedules ♢ [12/12] https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-schedules/slides.html 13/14 2021/4/28 Properties of Schedules Produced: 14 Apr 2021 https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-schedules/slides.html 14/14