# DB2 - lesson 03
#### Paraboschi
##### 13 October 2015
## Concurrency Control pt.II

### Conflict Graph
It is used to test __conflict-serializability__

#### Structure:
- One node for each transaction $T_i$
- One arc from $T_i$ to $T_j$ if it exists at least one conflict between an action of $T_i$ and an action of $T_j$ such as $a_i$ precedes $a_j$.

A schedule is in __CSR__ iff its __conflict graph__ is __acyclic__.

#### Properties:
- if $S$'s graph is *acyclic*, then it has a
    - __topological sort__: An ordering of the nodes such that the graph only contains arcs (i,j) with i<j
- The serial schedule whose transactions are ordered according to the *topological sort* is __conflict-equivalent__ to $S$, because for all conflicting pairs (i,j) it is always i<j
- In general there can be many topological sorts, i.e. serializations for the same acyclic graph

#### Concurrency control in practice
The *conflict-graph* technique would be efficient if we knew the graph from the beginning, but we don't.  

A scheduler must work __incrementally__: decide for each operation to execute it or not.

It is not *feasible* to mantain the graph, update it, and verify its acyclicity at each operation request.

### Locking

It's the most common method in commercial systems

A transaction is well-formed wrt locking if:
- __read__ operations are preceded by __r_lock__ (shared lock) and followed by __unlock__
- __write__ operations are preceded by __w_lock__ (exclusive lock) and followed by __unlock__

When a transaction first reads and then writes and object, it can:
- Use a __w_lock__
- Modify a __r_lock__ into a __w_lock__ (lock escalation)

#### Lock primitives
-  __r_lock__: read lock
-  __w_lock__: write lock
- __unlock__
#### Possible states of an object
- __free__
- __r_locked__: locked by a reader
- __w_locked__: locked by a writer

#### Behaviour of the lock manager

The lock manager receives the primitives from the transactions and grants resources according to the __conflict table__
- When a __lock__ request is granted, the resource is acquired
- When an __unlock__ is executed, the resource becomes available.

Request|free|r_locked|w_locked
---|---|---|---
__r_lock__|OK - __r_locked__|OK - __r_locked__|NO - __w_locked__
__w_lock__|OK - __w_locked__|OK - __r_locked__|NO - __w_locked__
__unlock__|__ERROR__|OK - __DEPENDS__|OK - __FREE__

### Two-Phase Locking
Requirements:
- A transaction cannot acquire any other lock after releasing a lock
- Locks on a transaction can be released only after commit/abort operations

A scheduler which:
- Uses well-formed transactions
- grants locks according to conflicts
- is Two-Phase
Produces the schedule class called __2PL__

Schedules is __2PL__ are __serializable__

#### 2PL and CSR
Every __2PL__ schedule is also *conflict-serializable*, but the converse is not necessarily true.

##### Counter example  
$r_1(x)w_1(x)r_2(x)w_2(x)r_3(y)w_1(y)$  
- It violates 2PL  

$r_1(x)w_1(x)$ |T1 rel $r_2(x)w_2(x)r_3(y)$ |T1 acq $w_1(y)$  
- It is conflict-serializable  
T3 < T1 < T2

#### 2PL implies CSR
$$2PL\subset CSR\subset VSR$$
- Consider for each transaction the moment in which it has all resources and is going to release the first one
- We sort the transactions by this temporal value and consider the corresponding serial schedule
- We want to prove that this schedule is conflict-equivalent to $S$
    - We then consider a conflict between an action from $t_i$ and an action from the $t_j's$ with $i<j$
    - Can they occur in the reverse order in $S$?
    - No, because then $t_j$ should have released the resource in question before $t_i$ has acquired it.

#### Strict 2PL

We were still using the hypotesis of commit-projection

To remove this hypotesis we need to add a constraint to __2PL__, thus obtaining __strict 2PL__

>Locks on a transaction can be released only after commit/rollback

This version of 2PL is used in commercial DBMSs

#### Implementation of 2-Phase Locking

Lock tables are in reality __main memory data structures__
- Resource state can be:
    - free
    - read-locked
    - write-locked
- Every resource has also a __read counter__
- Some late '90 systems only supported exclusive locks (binary info, no counter)

A transaction asking for a lock is either franted a lock or __queued and suspended__,  
 the queue is FIFO, there is danger of:
 - __Deadlock__: endless wait
 - __Starvation__: individual transaction waiting forever  
 Starvation can occur for write transactions waiting for resources which are higly used for reading (e.g. index roots)