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

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

[[Torna alla pagina di Basi di Dati - Complementi -> BDComplementi]]

----
[[!UniCrema]]

Restore

March 05, 2008, at 05:57 PM by dario -

Changed lines 25-26 from:

to:

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:
t'_1_': r'_1_'(x) w'_1_'(x) r'_1_'(y) w'_1_'(y)
t'_2_': r'_2_'(y) w'_2_'(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'_1_', poi tutta t'_2_' 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.

Restore

March 05, 2008, at 05:49 PM by dario -

Added lines 1-26:

(:title Basi di Dati - Complementi - Lezione del 4 marzo 2008:)
%titolo%''':: Basi di Dati - Complementi - Lezione del 4 marzo 2008 ::'''

!!!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
%warning%'''¡¡¡ Questa è materia da esercizio !!!'''

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 -> BDC3marzo2008]]).
Esempio:
t'_1_' : r'_1_'(x) r'_1_'(y) w'_1_'(x) w'_1_'(z)

Restore