uni
La concorrenza è fondamentale, decine o centinaia di transazioni al secondo non possono essere seriali. Si appoggia sulla Gestione delle Transazioni.
Senza una gestione accurata la concorrenza causerebbe però anomalie: per esempio se due transazioni operano sullo stesso valore possono leggere un valore intermedio “sporco”.
Ci sono diversi tipi di anomalie:

perdita di aggiornamento: W-W
Lettura sporca: R-W o W-W con aborto
Lettura inconsistente: R-W
Aggiornamento Fantasma: R-W
Inserimento fantasma: R-W su dato “nuovo”

Schedule

Uno schedule $S$ è una sequenza di operazioni di lettura/ scrittura di transazioni concorrenti.
Esempio: $S : r_{1} (x) r_{2} (z) w_{1} (x) w_{2} (z)$ dove $r_{2} (x)$ rappresenta la lettura dell’oggetto $x$ da parte della transazione $T_{1}$ .
Le operazioni compaiono nello schedule nell’ordine temporale di esecuzione sul database.

Schedule seriale

Uno schedule di transazioni $T = {T_{1}, ..., T_{n}}$ è detto seriale se per ogni coppia di transazioni tutte le operazioni di una delle due sono eseguite prima di qualsiasi operazione dell’altra.
Esempio: $T = {T_{0}, T_{1}} \to S = r_{0} (x) r_{0} (y) r_{1} (x) w_{1} (y)$

Schedule Serializzabile

Questo è un insieme di transazioni che produce lo stesso risultato di uno schedule seriale sulle stesse transazioni. Questa definizione richiede però un concetto di equivalenza fra schedule.

View-Serializzabilità

Diciamo che esiste una relazione legge-da tra le operazioni $r_{i} (x)$ e $w_{j} (x)$ presenti in uno schedule $S$ se $w$ precede $r$ e se tra le due non ci sono altre $w$ . La scrittura $w_{j} (x)$ in $S$ è detta scrittura finale su $x$ se è l’ultima $w$ su $x$ in $S$ .
Due schedule $S_{i}$ e $S_{j}$ sono detti view-equivalenti, $S_{i} \approx_{v} S_{j}$ se hanno la stessa relazione legge-da e le stesse scritture finali su ogni oggetto.
Uno schedule $S$ è view-serializzabile se è view-equivalente ad un qualche schedule seriale.
L’insieme degli schedule view-serializzabili è indicato con VSR.
La verifica della view-equivalenza di due dati schedule ha complessità polinomiale.
La verifica sulla view-serializzabilità di uno schedule è un problema NP-completo poiché è necessario confrontare lo schedule con tutti i possibili schedule seriali, questo lo rende inutilizzabile nella pratica.
Poiché l’uso della view-serializzabilità nella pratiac è impossibile definiamo una condizione di equivalenza più ristretta ma che sia utilizzabile nella pratica, quindi che abbia una complessità inferiore.

Conflict-Serializzabilità

Un’operazione $a_{i}$ è in conflitto con un’altra operazione $a_{j}$ se operano sullo stesso oggetto e almeno una di esse è una scrittura. Nota bene: nei conflitti conta l’ordine.
Il conflitto può essere:

R-W oppure W-R
W-W
Due schedule $S_{i}$ e $S_{j}$ sono detti conflict-equivalenti, $S_{i} \approx_{c} S_{j}$ se hanno le stesse operazioni e ogni coppia di operazioni in conflitto compare nello stesso ordine in entrambi.
Uno schedule $S$ è conflict-serializzabile se è conflict-equivalente ad un qualche schedule seriale.
L’insieme degli schedule conflict-serializzabili è indicato con CSR.

Teorema

ogni schedule conflict-serializzabile è view-serializzabile, ma non necessariamente viceversa, quindi $CSR ⟹ V SR$ poiché $\approx_{c} ⟹ \approx_{v}$ .

Verifica della Conflict-Serializzabilità

Si fa tramite il grafo dei conflitti (Grafo):

Un nodo per ogni transazione $T_{i}$
un arco (orientato) da $T_{i}$ a $T_{j}$ se c’è almeno un conflitto fra un’azione $a_{i}$ e un’azione $a_{j}$ tale che $a_{i}$ precede $a_{j}$
Teorema: Uno schedule è in CSR se e solo se il grafo è aciclico.
Esempio:
- S = $w_{1} (x) w_{2} (x) r_{3} (x) r_{1} (y) w_{2} (y) r_{1} (z) w_{3} (z) r_{4} (z) w_{4} (y) w_{5} (y)$
- $x : w_{1} w_{2} r_{3}$
- $y : r_{1} w_{2} w_{4} w_{5}$
- $z : r_{1} w_{3} r_{4}$
- Il grafo è aciclico $\to$ $S$ è CSR, quindi anche VSR

graph LR
    1((1)) --> 2((2))
    1 --> 3((3))
    1 --> 4((4))
    1 --> 5((5))
    2 --> 3
    2 --> 4
    2 --> 5
    3 --> 4
    3 --> 5
    4 --> 5

Controllo di Concorrenza

Il controllo della concorrenza è eseguito dallo scheduler, che traccia tutte le operazioni eseguite sul database dalle transazioni e decide se accettare o rifiutare le operazioni che vengono richieste, il suo obiettivo è evitare le anomalie.
Per il momento assumiamo che l’esito delle transazioni sia noto a priori (ipotesi commit-proiezione), così facendo possiamo rimuovere dallo schedule tutte le transazioni abortite, questa assunzione però non ci consente di trattare anomalie come la lettura sporca.

Media

graph TD
    A[Gestore dei metodi d'accesso] -->|read, write| B[Gestore della concorrenza]
    C[Gestore delle transazioni] -->|begin, commit, abort| B
    B --> D(Tabella dei lock)
    B --> |read,write: non tutte e in ordine ev. diverso| E[Gestore della memoria secondaria]
    E --> F[(BD)]

flowchart TB
    subgraph S1[ ]
        direction TB
        subgraph S2[ ]
            direction TB
            subgraph S3[ ]
                ScheduleSeriali(Schedule Seriali)
            end
            ScheduleCSR(Schedule CSR)
        end
        ScheduleVSR(Schedule VSR)
    end
    Schedule(Schedule)

    S1 --- Schedule
    S1 --- ScheduleVSR
    S2 --- ScheduleCSR
    S3 --- ScheduleSeriali

🪴 Quartz 4.0

Explorer

Gestione della Concorrenza