Esercizi controllo concorrenza

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

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

Classificazione di scheduling CSR/VSRModifica

Esercizio 1Modifica

Si determini se il seguente scheduling è VSR e/o CSR, e in caso negativo si proponga - se esiste - una soluzione:

 

Soluzione

Suddividiamo per risorsa le azioni delle transazioni:

  •  
  •  
  •  

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   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 2Modifica

Si determini se il seguente scheduling è VSR e/o CSR, e in caso negativo si proponga - se esiste - una soluzione:

 

Soluzione

Suddividiamo per risorsa le azioni delle transazioni:

  •  
  •  
  •  
  •  

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   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   in   lo schedule risultante è CSR.

Esercizio 3Modifica

Si determini se il seguente scheduling è VSR e/o CSR, e in caso negativo si proponga - se esiste - una soluzione:

 

Soluzione

Suddividiamo per risorsa le azioni delle transazioni:

  •  
  •  
  •  
  •  
  •  

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   in  , risolvendo il conflitto 1->2
  • per la risorsa t possiamo scambiare la scrittura cieca   in  , risolvendo il conflitto 6->2
Lo schedule è in VSR.

Classificazione di scheduling 2PL e TSModifica

Esercizio 1Modifica

Dato il seguente scheduling, stabilire se è 2PL, 2PLStrict o nessuno dei due.

 

Soluzione

Costruiamo la seguente tabella:

Tempo x y z
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  

Da questa tabella possiamo dedurre che:

  • La transazione 1 deve acquisire un w-lock su x necessariamente dopo   (in particolare eseguire escalation dell'r-lock acquisito a  );
  • 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:

  •  
  •  

quindi:

  •  

Ma se fosse in 2PL, risulterebbe:

  •  
  •  

ma come visto prima   e   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 2Modifica

Stabilire se il seguente scheduling è Mono-TS, Multi-TS o nessuno dei due (il valore a pedice indica il timestamp):  

Soluzione

 
 
 

Poiché rispetto alla risorsa   si ha che   precede   e   allora si evince che lo scedule NON è Multi-TS.

Di conseguenza NON è Mono-TS.

NoteModifica

  1. Un nodo è detto pozzo se ha solo archi entranti