W6 L1 - More Transactions

Avoiding conflicts - ACID

Atomicity

Consistency

Isolation

Durability

Atomicity of Transactions

• Property guaranteed by DBMS

• Each transaction executes all its actions in one step

• Transaction might commit after completing all actions, or abort after executing some actions

Consistency

Property that every transaction sees a consistent database instance

Isolation

Guarantee that the net effect is identical to executuing the transaction serially

Eg: If T1 and T2 executed concurrently, net effect is equivalent to executing

• T1 then T2 or

• T2 then T1

Durability

• DBMS uses log to ensure durability

• If system crashes before changes made by a transaction are written to disk, log used to remember and restore these changes

Equivalent Schedules

Different schedules which end up with the same result

Serialisable Schedule

When a schedule is equivalent to some serial execution of the transactions

Conflict types

1. Reading Uncommited Data (WR Conflict)

2. Unrepeatable Reads (RW Conflict)

3. Overwriting Uncommited Data (WW Conflict)

Commit and Abort

Commit - Makes prior RWs permanent

Abort - Undoes everything in a transaction not yet commited

Lock-Based Concurrency Control

Each transaction must

• Obtain S (shared) lock on object before reading

• Obtain X (exclusive) lock on object before writing

• S or X lock released when corresponding object no longer needed

Eg: T1: S(A), R(A), Release_S(A), X(B), W(B), Release_X(B)

X and S locks

X conflicts with X and S

• No transaction can obtain X lock on object if other transaction has X or S lock on that object

S conflicts with X

• No transaction can obtain S lock on object if other transaction has X lock on that object

• Multiple transactions may obtain an S lock on the same object

Conflict Equivalent Schedules

Two schedules are conflict equivalent if

• They involve the same actions of the same transactions

• Every pair of conflicting actions are ordered in the same way

Conflict Serialisable Schedules

A schedule is Conflict Serialisable if it equivalent to some serial schedule

• Must maintain order or writes

How to check conflict serialisability - Precedence graphs

Nodes - Transactions

Edges - Draw an edge wherever there is a conflict between transactions

If there is a cycle in the precedence graph, the schedule is not conflict serialisable

Deadlocks

Cycle of transactions waiting for locks to be released by eachother

Deadlock Detection

Wait-for graph:

Nodes - Transactions

Edges - Edge from Ta to Tb if Ta is waiting for Tb to release lock

If a loop forms, there is a deadlock

Deadlock Prevention

Assign priorities based on timestamps

Eg: If Ta wants a lock that Tb holds, two policies are possible

• Wait-Die: If Ta has higher priority, Ta waits for Tb

  • Otherwise, Ta aborts

• Wound-Wait: If Ta has higher priority, Tb aborts

  • Otherwise, Ta waits

Recoverable Schedules

Recoverable: no transaction commits until all the data it read has been committed.

Long explanation:

• If Transaction T read some data, it can’t commit until the transactions that wrote that data have commited first

• The data is recoverable as long as T doesn’t commit before the transactions that wrote that data

• If T commits before the transactions that wrote that data, the other transactions data is unrecoverable

Cascading Aborts

If T1 reads an action that T2 has written on, and T2 is aborted, T1 must be aborted as well