Formula Sheets: Transaction & Concurrency Control

 Page 1


T r ansaction and Concurrency Con trol
T ransaction Prop erties
A CID Prop erties
• A t omicit y: T ransaction executes completely or not at all.
• Consistency: T ransaction preserv es database in tegrit y constrain ts.
• Isolation: P artial c hanges in visible to other transactions.
• Durabilit y: Committed c hanges are p ermanen tly sa v ed.
Sc h edule T yp es
Serial Sc hedule
• T ransactions execute one after another.
• Time Complexit y: O(n) , where n is n um b er of transactions.
Concurren t Sc hedule
• I n terlea v ed execution of m ultiple transactions.
Conflict Serializabilit y
• Sc hedule equiv alen t to a serial sc hedule based on conflicting op erations (Read-W rite, W rite-Read,
W rite-W rite).
• Pre cedence Graph: Directed edge T
i
?T
j
if T
i
has op eration conflicting with and p receding T
j
.
• T est: A cyclic precedence graph =? conflict serializable.
View Serializabilit y
• Sc hedule equiv alen t to serial sc hedule if: same reads-from relations and same final writes.
Reco v erabilit y
• Reco v erable: If T
j
reads from T
i
, T
i
commits b efore T
j
.
• Cascadeless: No transaction reads uncommitted data (a v oids cascading rollbac k).
• Strict: No transaction reads/writes uncommitted data.
Concurrency Con trol Proto cols
Lo c k-Based Proto col
• Lo c ks: Shared (S) for read, Exclusiv e (X) for write.
• Compatibilit y: S-S compatible, S-X and X-X incompatible.
T w o-Phase Lo c king (2PL)
• Phases: Gro wing (acquire lo c ks), Shrinking (release lo c ks).
• Ensures conflict serializabilit y , ma y cause deadlo c k.
Timestamp-Based Proto col
• Eac h transaction T
i
assigned unique timestamp TS(T
i
) .
• Read R ule: Allo w read if TS(T
i
)=W -timestamp(item) .
• W rite R ule: Allo w write if TS(T
i
)=R -timestamp(item) and TS(T
i
)=W -timestamp(item) .
• T homas W rite R ule: Ignore write if TS(T
i
)<W -timestamp(item) .
Multiple Gran ularit y Lo c king
• Lo c k hie rarc h y: Database, T able, P age, T uple.
1
Page 2


T r ansaction and Concurrency Con trol
T ransaction Prop erties
A CID Prop erties
• A t omicit y: T ransaction executes completely or not at all.
• Consistency: T ransaction preserv es database in tegrit y constrain ts.
• Isolation: P artial c hanges in visible to other transactions.
• Durabilit y: Committed c hanges are p ermanen tly sa v ed.
Sc h edule T yp es
Serial Sc hedule
• T ransactions execute one after another.
• Time Complexit y: O(n) , where n is n um b er of transactions.
Concurren t Sc hedule
• I n terlea v ed execution of m ultiple transactions.
Conflict Serializabilit y
• Sc hedule equiv alen t to a serial sc hedule based on conflicting op erations (Read-W rite, W rite-Read,
W rite-W rite).
• Pre cedence Graph: Directed edge T
i
?T
j
if T
i
has op eration conflicting with and p receding T
j
.
• T est: A cyclic precedence graph =? conflict serializable.
View Serializabilit y
• Sc hedule equiv alen t to serial sc hedule if: same reads-from relations and same final writes.
Reco v erabilit y
• Reco v erable: If T
j
reads from T
i
, T
i
commits b efore T
j
.
• Cascadeless: No transaction reads uncommitted data (a v oids cascading rollbac k).
• Strict: No transaction reads/writes uncommitted data.
Concurrency Con trol Proto cols
Lo c k-Based Proto col
• Lo c ks: Shared (S) for read, Exclusiv e (X) for write.
• Compatibilit y: S-S compatible, S-X and X-X incompatible.
T w o-Phase Lo c king (2PL)
• Phases: Gro wing (acquire lo c ks), Shrinking (release lo c ks).
• Ensures conflict serializabilit y , ma y cause deadlo c k.
Timestamp-Based Proto col
• Eac h transaction T
i
assigned unique timestamp TS(T
i
) .
• Read R ule: Allo w read if TS(T
i
)=W -timestamp(item) .
• W rite R ule: Allo w write if TS(T
i
)=R -timestamp(item) and TS(T
i
)=W -timestamp(item) .
• T homas W rite R ule: Ignore write if TS(T
i
)<W -timestamp(item) .
Multiple Gran ularit y Lo c king
• Lo c k hie rarc h y: Database, T able, P age, T uple.
1
• Lo c ks: Shared (S), Exclusiv e (X), In ten tion-Shared (IS), In ten tion-Exclusiv e (IX), Shared-In ten tion-
Exclusiv e (SIX).
• Compatibilit y Matrix: IS compatible with IS, S; IX compatible with IS, IX; S, X, SIX incompatible
with most.
Graph-Based Proto col
• Uses tree structure for lo c k ordering to prev en t deadlo c k.
• Lo c k paren t b efore c hild, release in an y order.
Deadlo c k and Starv ation
Deadlo c k Detection
• W ait-for Graph: Edge T
i
?T
j
if T
i
w aits for resource held b y T
j
.
• Cycle in graph =? deadlo c k.
• Detection Time: O(V +E) , where V is transactions, E is edges.
Deadlo c k Prev en tion
• W ait-Die: If TS(T
i
)<TS(T
j
) , T
i
w aits; else T
i
ab orts.
• W ound-W ait: If TS(T
i
)<TS(T
j
) , T
j
ab orts; else T
i
w aits.
Reco v ery T ec hniques
Log-Based Reco v ery
• Log Record: <T
i
,X,old _value,new _value> for eac h up date.
• Undo: Rollbac k uncommitted transactions using old v alues.
• Redo: Reapply committed transactions using new v alues.
Isolation Lev els
• Read Uncommitted: Allo ws dirt y reads.
• Read Committed: Prev en ts dirt y reads.
• Rep eatable Read: Prev en ts dirt y and non-rep eatable reads.
• Serializable: Ensures conflict serializabilit y .
2