Grafico della precedenza - Precedence graph

Un grafo di precedenza , anche chiamato grafo dei conflitti e serializzabilità grafico , viene utilizzato nel contesto di controllo della concorrenza in banche dati .

Il grafico di precedenza per una pianificazione S contiene:

• Un nodo per ogni transazione sottoposta a commit in S
• Un arco da _Ti a T _j se un'azione di _Ti precede e va in conflitto con una delle azioni di T _j . Cioè le azioni appartengono a transazioni diverse, almeno una delle azioni è un'operazione di scrittura e le azioni accedono allo stesso oggetto (lettura o scrittura).

Esempi di grafici di precedenza

Esempio 1

Esempio 2

${\ Displaystyle S = {\ begin {bmatrix} T1 & T2 \\ R (A) & R (A) \\ A = A * 5 & R (B) \\ W (A) & B = B + A \\ R (B) & W (B) \\ B = B * 10 & \\ W (B) & \\\ end {bmatrix}}}$

Esempio 2

${\ displaystyle D = R1 (A)}$ ${\ displaystyle R2 (B)}$ ${\ displaystyle W2 (A)}$ ${\ displaystyle Com.2}$ ${\ displaystyle W1 (A)}$ ${\ displaystyle Com.1}$ ${\ displaystyle W3 (A)}$ ${\ displaystyle Com.3}$

Un grafico di precedenza della pianificazione D, con 3 transazioni. Poiché esiste un ciclo (di lunghezza 2; con due fronti) attraverso le transazioni impegnate T1 e T2, questa pianificazione (cronologia) non è serializzabile in conflitto . Si noti che il commit della Transazione 2 non ha alcun significato per quanto riguarda la creazione di un grafico di precedenza.

Test della serializzabilità con il grafico delle precedenza

Esempio di serializzabilità di test

Algoritmo per testare la serializzabilità dei conflitti di una pianificazione S insieme a una pianificazione di esempio.

${\ displaystyle S = {\ begin {bmatrix} T1 & T2 & T3 \\ R (A) && \\ & W (A) & \\ & Com. & \\ W (A) && \\ Com. && \\ && W (A) \ \ && Com. \\\ end {bmatrix}}}$

o

${\ displaystyle S = R1 (A)}$ ${\ displaystyle W2 (A)}$ ${\ displaystyle Com.2}$ ${\ displaystyle W1 (A)}$ ${\ displaystyle Com.1}$ ${\ displaystyle W3 (A)}$ ${\ displaystyle Com.3}$

1. Per ogni transazione T _{x che} partecipa alla pianificazione S, creare un nodo etichettato _Ti nel grafico delle precedenza. Quindi il grafico delle precedenza contiene T ₁ , T ₂ , T ₃ .
2. Per ogni caso in S in cui T _j esegue un read_item (X) dopo che T _i esegue un write_item (X), creare un arco (T _i → T _j ) nel grafico delle precedenze. Ciò non si verifica da nessuna parte nell'esempio precedente, poiché non c'è lettura dopo la scrittura.
3. Per ogni caso in S dove T _j esegue un write_item (X) dopo T _i esegue un read_item (X), crea un bordo (T _i → T _j ) nel grafico precedenza. Ciò si traduce in un fronte diretto da T ₁ a T ₂ (poiché T ₁ ha R (A) prima che T ₂ abbia W (A) ).
4. Per ogni caso in S dove T _j esegue un write_item (X) dopo T _i esegue un write_item (X), crea un bordo (T _i → T _j ) nel grafico precedenza. Ciò si traduce in bordi diretti da T ₂ a T ₁ , T ₂ a T ₃ e T ₁ a T ₃ .
5. La pianificazione S è serializzabile se e solo se il grafico delle precedenza non ha cicli. Poiché T ₁ e T ₂ costituiscono un ciclo, l'esempio precedente non è serializzabile (conflitto).

Riferimenti

link esterno

• The Fundamentals of Database Systems, 5th Edition l'uso dei grafici di precedenza è discusso nel capitolo 17, poiché si riferiscono ai test per la serializzabilità dei conflitti .
• Abraham Silberschatz, Henry Korth e S. Sudarshan. 2005. Database Systems Concepts (5 ed.), PP. 628–630. McGraw-Hill, Inc., New York, NY, USA.