Basi di Dati - Complementi - Lezione del 4 marzo 2008

 :: Basi di Dati - Complementi - Lezione del 4 marzo 2008 ::

Appunti Glamour

Torna alla pagina di Basi di Dati - Complementi

Gestore della concorrenza

Il Gestore della Concorrenza si occupa di realizzare la proprietà Isolamento. Il punto è che in genere nelle applicazioni ci sono tante operazioni che vanno eseguite contemporaneamente, e questo non deve inficiarne la correttezza. Si parla di tps, ovvero transactions per second, e possono essere decine o migliaia. Questo gestore deve decidere se accettarle o no, e se le accetta, in che ordine eseguirle (scheduling).

Problemi legati alla concorrenza

Se la concorrenza non viene gestita bene, possono accadere spiacevoli inconvenienti, qui sotto classificati.

• Perdita di aggiornamenti: le modifiche di una transazione vengono perse perché sovrascritte da un'altra transazione concorrente.
• Lettura sporca: una trans legge il risultato intermedio di un'altra trans, la quale poi fallisce e fa il rollback. La prima trans si trova quindi a lavorare su dati non validi.
• Lettura inconsistente: una trans legge a più riprese oggetti che una seconda trans sta modificando: tra le due letture c'è inconsistenza, cioè non coincidono.
• Aggiornamento fantasma: una trans lavora su dati e li fa andare temporaneamente fuori dai vincoli di integrità; un'altra trans legge sti dati, li vede non validi e abortisce.
• Inserimento fantasma: tra due letture che una trans fa di una lista di oggetti, un'altra trans ne inserisce un'altro. Se per esempio sto confrontando dei valori medi, ciò sballa tutto.

In quest'ultimo caso non basta dire: "questo valore è lockato", perché se si tratta di una query nidificata che lavora su dati aggregati, essa prima fa un lock, poi lo rilascia, poi rifà il lock sugli stessi dati. Ma nel frattempo i dati sono liberi e altre applicazioni possono spaciugarli. Quindi occorre anche un lock sui predicati.

Teoria del controllo della concorrenza

¡¡¡ Questa è materia da esercizio !!!

Vai agli esercizi sugli schedule

In questa teoria, vediamo una transazione come una sequenza di operazioni di read e write, tutte marcate da un identificatore il quale ci permette di distinguere le op di una trans dalle op di un'altra. Inoltre, assumiamo le trans come ben formate (vedi lezione precedente). Esempio:

 t1 : r1(x) r1(y) w1(x) w1(z)

Uno schedule è una sequenza di operazioni di I/O presentate da trans concorrenti. Tutte le op di ciascuna trans devono essere nel loro ordine, anche se le op di una trans possono essere intervallate a op di un'altra trans.

OCIO: per ora, consideriamo che sia soddisfatta la commit-proiezione, ovvero che compaiano solo le trans che hanno fatto commit e trascuriamo l'abort.

Se ho queste due transazioni:

 t1: r1(x) w1(x) r1(y) w1(y)
 t2: r2(y) w2(y)

uno schedule è semplicemente una qualsiasi sequenza delle op di queste due trans, purché si rispetti l'ordine interno ad ogni trans.

Tipi di schedule

Sono divisibili in due classi:

• seriali: tutte le trans sono eseguite in sequenza, ovvero prima tutta t₁, poi tutta t₂ etc.
• serializzabili: sono schedule non seriali, ma che producono lo stesso risultato di uno schedule seriale.

Serializzabile vuol dire quindi che uno schedule non seriale è equivalente ad uno schedule seriale. Ciò vuol dire che lo stato finale in cui si trovano i miei dati deve essere lo stesso sia per uno schedule seriale che per uno schedule serializzabile ad esso equivalente.

Nota: si usano schedule serializzabili perché spesso raggruppando operazioni simili si guadagna tempo nell'accesso in memoria.

View-serializzabilità e View-equivalenza

Quando 1 schedule alla fine dà la stessa vista sui dati di uno schedule seriale, è view-serializzabili.

Per verificare ciò, si usano questi 2 concetti: leggi-da e scrittura finale.

La leggi-da è una relazione tra scritture e letture di uno stesso dato. Ad esempio, posso dire che

 r1(x) legge-da w2(x)

se l'operazione di scrittura w2(x) precede la lettura r1(x), e tra queste due non c'è nessun'altra operazione di scrittura sullo stesso dato x.

La scrittura finale invece è l'ultima scrittura di un certo dato x nel mio schedule. Dopo di essa, nessuno scrive più su x.

Quindi, posso ora dire che 2 schedule sono view-equivalenti se, sulle stesse trans, hanno le stesse leggi-da e le stesse scritture finali.

Chiamiamo poi VSR l'insieme di tutti gli schedule che sono view-serializzabili.

Lo scheduler quindi potrebbe prendere uno schedule serializzabile e vedere se è view-equivalente ad un qualsiasi schedule seriale su quelle stesse trans. Ad esempio, se ho 3 trans diverse, ho 3! schedule seriali. Devo quindi confrontare ciascun schedule per verificarne la view-serializzabilità, ovvero la view-equivalenza con uno qualsiasi dei miei 3! schedule seriali.

Tutto ciò è cosa bella, ma il costo è polinomiale, perché si tratta di un problema NP-difficile. Se le operazioni sono tante, occorrerà confrontare uno schedule serializzabile con gli n! schedule seriali possibili. Quindi, si usano altre condizioni, più strette di queste, ma più pratiche, per verificare la bontà di uno schedule.

Vai agli esercizi sugli schedule

Torna alla pagina di Basi di Dati - Complementi