# Esercizi controllo concorrenza

Esercizi relativi alla lezione Proprietà ACID/Controllo di concorrenza.

## Classificazione di scheduling CSR/VSR
### Esercizio 1

Si determini se il seguente scheduling è VSR e/o CSR, e in caso negativo si proponga - se esiste - una soluzione:
$r_{3}(x)\ w_{4}(x)\ r_{2}(z)\ r_{1}(x)\ w_{1}(y)\ w_{2}(y)\ w_{2}(z)\ w_{3}(y)$
Suddividiamo per risorsa le azioni delle transazioni:
* $x:r_{3},w_{4},r_{1}$
* $y:w_{1},w_{2},w_{3}$
* $z:r_{2},w_{2}$
E generiamo il grafo dei conflitti:
$w_{1},w_{2}$

### Esercizio 2

Si determini se il seguente scheduling è VSR e/o CSR, e in caso negativo si proponga - se esiste - una soluzione:
$r_{1}(x)\ w_{2}(t)\ r_{1}(y)\ w_{3}(y)\ r_{4}(z)\ w_{4}(z)\ w_{1}(t)\ r_{4}(x)\ w_{5}(t)\ w_{4}(x)\ r_{6}(y)\ w_{3}(z)\ w_{2}(z)\ r_{6}(t)\ w_{6}(y)$
Suddividiamo per risorsa le azioni delle transazioni:
* $x:r_{1},r_{4},w_{4}$
* $y:r_{1},w_{3},r_{6},w_{6}$
* $z:r_{4},w_{4},w_{3},w_{2}$
* $t:w_{2},w_{1},w_{5},r_{6}$
E disegniamo il grafo dei conflitti:
Il grafo è ciclico:
* 1-4-2
* 1-3-2
* 1-4-3-2
Per semplificare il problema eliminiamo il nodo 6 perché pozzo quindi non può essere parte di un ciclo. Eliminiamo anche il nodo 5 (anch'esso diventato pozzo dopo l'eliminazione del 6).
Possiamo notare che gli archi 4-3 e 2-1 sono causati da scritture cieche. Notiamo che però 4-3 è causa anche di $r_{4}w_{3}$ quindi non possiamo invertirne la direzione. Possiamo invece invertire 2-1, che rende di fatto il grafico completamente aciclico.
Possiamo concludere che:
* Il grafo iniziale non è in CSR ;
* Il grafo iniziale è in VSR;
* Invertendo $w_{2}(t)\ w_{1}(t)$ in $w_{1}(t)\ w_{2}(t)$ lo schedule risultante è CSR.

### Esercizio 3

Si determini se il seguente scheduling è VSR e/o CSR, e in caso negativo si proponga - se esiste - una soluzione:
$r_{1}(x)\ w_{4}(k)\ r_{2}(x)\ w_{3}(y)\ r_{4}(y)\ w_{1}(x)\ w_{1}(z)\ r_{2}(k)\ w_{6}(t)\ w_{2}(t)\ r_{6}(x)\ w_{2}(z)\ w_{5}(t)\ r_{6}(y)\ w_{6}(z)$
Suddividiamo per risorsa le azioni delle transazioni:
* $x:r_{1},r_{2},w_{1},r_{6}$
* $y:w_{3},r_{4},r_{6}$
* $z:w_{1},w_{2},w_{6}$
* $t:w_{6},w_{2},w_{5}$
* $k:w_{4},r_{2}$
E disegnamo il grafo dei conflitti:
Il grafo è evidentemente ciclico: ciclo 1-2 e 2-6. Quindi non è in CSR.
Vediamo se è in VSR:
* per la risorsa z possiamo scambiare la scrittura cieca $w_{1},w_{2},w_{6}$ in $w_{2},w_{1},w_{6}$, risolvendo il conflitto 1->2
* per la risorsa t possiamo scambiare la scrittura cieca $w_{6},w_{2},w_{5}$ in $w_{2},w_{6},w_{5}$, risolvendo il conflitto 6->2

## Classificazione di scheduling 2PL e TS
### Esercizio 1

Dato il seguente scheduling, stabilire se è 2PL, 2PLStrict o nessuno dei due.
$r_{1}(x)\ w_{1}(z)\ r_{2}(y)\ r_{2}(x)\ w_{2}(z)\ r_{1}(y)\ r_{3}(z)\ r_{3}(y)\ w_{2}(y)\ w_{1}(x)\ w_{3}(x)$
Costruiamo la seguente tabella:
| Tempo | x | y | z |
| 1 | $r_{1}$ | | |
| 2 | | | $w_{1}$ |
| 3 | | $r_{2}$ | |
| 4 | $r_{2}$ | | |
| 5 | | | $w_{2}$ |
| 6 | | $r_{1}$ | |
| 7 | | | $r_{3}$ |
| 8 | | $r_{3}$ | |
| 9 | | $w_{2}$ | |
| 10 | $w_{1}$ | | |
| 11 | $w_{3}$ | | |
Da questa tabella possiamo dedurre che:
* La transazione 1 deve acquisire un w-lock su x necessariamente dopo $t_{4}$ (in particolare eseguire escalation dell'r-lock acquisito a $t_{1}$);
* La transazione 2 deve rilasciare l'r-lock per x prima che la transazione 1 effettui escalation;
* Per y, le transazioni 2,1,3 condividono l'r-lock ma 1 e 3 devono rilasciarlo prima di 9.
Quindi esprimendolo in formule abbiamo che:
* $4<U_{2}(x)<L_{1}(x)<10$
* $6<U_{1}(y)<8<U_{3}(y)<9$
quindi:
* $6<U_{1}(y)<8<U_{3}(y)<L_{2}(y)<9$
Ma se fosse in 2PL, risulterebbe:
* $L_{1}(x)<U_{1}(y)$
* $L_{2}(y)<U_{2}(x)$
ma come visto prima $U_{2}(x)<L_{1}(x)$ e $U_{1}(y)<L_{2}(y)$ che porta a una contraddizione. Quindi lo schedule non è in 2PL e tanto meno in 2PLStrict.

### Esercizio 2

Stabilire se il seguente scheduling è Mono-TS, Multi-TS o nessuno dei due (il valore a pedice indica il timestamp): $r_{4}(x)\ r_{2}(x)\ w_{2}(y)\ w_{5}(x)\ w_{4}(y)\ r_{3}(z)\ r_{3}(y)\ w_{3}(x)\ w_{4}(z)\ r_{6}(z)\ r_{9}(z)\ w_{6}(z)\ w_{10}(z)\ r_{5}(z)\ r_{20}(z)$
$x:r_{4}\ r_{2}\ w_{5}\ w_{3}$
$y:w_{2}\ w_{4}\ r_{3}$
$z:r_{3}\ w_{4}\ r_{6}\ r_{9}\ w_{6}\ w_{10}\ r_{5}\ r_{20}$
Poiché rispetto alla risorsa $z$ si ha che $r_{9}$ precede $w_{6}$ e $(9>6)$ allora si evince che lo scedule NON è Multi-TS.