Esercizi controllo concorrenza

esercitazione Esercizi controllo concorrenza
	Tipo: esercitazione
	Materia: Basi di dati 2

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)$

Soluzione

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:

Questo grafo è evidentemente ciclico, quindi lo schedule non è in CSR. È VSR? Dobbiamo verificare se i cicli sono causati da coppie di scritture cieche. Nel nostro testo evidenziamo una sola coppia di scritture cieche

w_{1}, w_{2}

relative alla risorsa y. Possiamo quindi invertire l'arco 1-2 che però non elimina il ciclo formato da 1-3-4. Lo schedule non è quindi in VSR (non possiamo eliminare tutti i cicli con le scritture cieche) e di conseguenza non può essere trasformato in CSR.

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)$

Soluzione

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^[1] 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)$

Soluzione

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

Lo schedule è in VSR.

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)$

Soluzione

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.

Si poteva anche notare che il grafo dei conflitti generato da questo schedule è ciclico, quindi non CSR e di conseguenza nemmeno 2PL.

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)$

Soluzione

$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.

Di conseguenza NON è Mono-TS.

Note

↑ Un nodo è detto pozzo se ha solo archi entranti

[1] Un nodo è detto pozzo se ha solo archi entranti

[1]