DBMS: Scheduling e serializzabilità
Salve a tutti, avrei un paio di domande riguardante lo scheduling:
-Riguardo a uno scheduling con 2 transazioni, leggo la seguente affermazione :"2 istruzioni sono in conflitto se invertendole il risultto cambia"; non mi è molto chiaro questo concetto di inversione... con tale termine si intende il passaggio, ad esempio, da un read(x) a un read(y) (considerando che le variabili prese in considerazione dallo scheduling siano x e y), oppure da un read(x) a un write(x)?
-Possiamo conoscere se uno scheduling sia serializzabile o meno applicando la "tecnica dei conflitti" e verificando che il grafo ottenuto non sia ciclico; tuttavia nei grafi più complessi, con un maggior numero di nodi ed archi, non sempre è facile distinguere quando un grafo è ciclico o meno. C'è un modo formale e preciso per riconoscere la ciclicità di un grafo(non affidandosi cioè solo al proprio occhio)? O in alternativa qualcuno potrebbe postare un esempio di grafo ciclico(non semplice) e uno aciclico?
P.S. Questo argomento (riguardante il dbms) è stato affrontato in maniera generale e introduttiva, per cui mi accontento di risposte semplici adatte a tale livello...
-Riguardo a uno scheduling con 2 transazioni, leggo la seguente affermazione :"2 istruzioni sono in conflitto se invertendole il risultto cambia"; non mi è molto chiaro questo concetto di inversione... con tale termine si intende il passaggio, ad esempio, da un read(x) a un read(y) (considerando che le variabili prese in considerazione dallo scheduling siano x e y), oppure da un read(x) a un write(x)?
-Possiamo conoscere se uno scheduling sia serializzabile o meno applicando la "tecnica dei conflitti" e verificando che il grafo ottenuto non sia ciclico; tuttavia nei grafi più complessi, con un maggior numero di nodi ed archi, non sempre è facile distinguere quando un grafo è ciclico o meno. C'è un modo formale e preciso per riconoscere la ciclicità di un grafo(non affidandosi cioè solo al proprio occhio)? O in alternativa qualcuno potrebbe postare un esempio di grafo ciclico(non semplice) e uno aciclico?
P.S. Questo argomento (riguardante il dbms) è stato affrontato in maniera generale e introduttiva, per cui mi accontento di risposte semplici adatte a tale livello...
Risposte
Mi sembrano argomenti molto generali e non sono necessariamente legati ai DBMS.
- Due istruzioni sono conflittuali se agiscono sullo stesso dato e almeno una delle due lo modifica. Se infatti l'operazione di scrittura è la prima ad essere eseguita, l'altra istruzione lavora sul dato modificato; in caso contrario l'altra istruzione lavora sul dato prima che questo venga modificato. L'effetto è finale delle due istruzioni del dato cambia. Si tratta quindi di read/write oppure write/write.
- Sì, ci sono. Non avendo però mai visti i grafi applicati ai DBMS non so se i grafi in questione siano orientato o meno. Esistono comunque algoritmi per derminare la ciclicità in entrambi i casi. Nel caso più semplice consiste nel visitare tutti i nodi segnando gli archi in modo opportuno. Cercando con google dovresti trovare molte informazioni.
- Due istruzioni sono conflittuali se agiscono sullo stesso dato e almeno una delle due lo modifica. Se infatti l'operazione di scrittura è la prima ad essere eseguita, l'altra istruzione lavora sul dato modificato; in caso contrario l'altra istruzione lavora sul dato prima che questo venga modificato. L'effetto è finale delle due istruzioni del dato cambia. Si tratta quindi di read/write oppure write/write.
- Sì, ci sono. Non avendo però mai visti i grafi applicati ai DBMS non so se i grafi in questione siano orientato o meno. Esistono comunque algoritmi per derminare la ciclicità in entrambi i casi. Nel caso più semplice consiste nel visitare tutti i nodi segnando gli archi in modo opportuno. Cercando con google dovresti trovare molte informazioni.
Grazie mille per la risposta rapida e chiara....
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo