Redigerer Historie (databaser) (avsnitt)

==Typer historier==

===Seriell===

Transaksjonene utføres hver for seg, uten fletting (se eksempel ovenfor). I en seriell historie, er det ingen transaksjoner som starter før en kjørende transaksjon avslutter.

===Serialiserbar===

En historie som er ekvivalent (gir samme resultat) med en seriell historie er serialiserbar.

I historie E, er rekkefølgen operasjonene til transaksjonene ikke den samme som i D, men til resultatet av de to historiene er likt.

:<math>E = \begin{bmatrix}
T1 & T2 & T3 \\
R(X) &  &  \\
   & R(Y) & \\
 && R(Z) \\

W(X) &  &  \\
 & W(Y) & \\
 && W(Z) \\
Com. & Com. & Com. \end{bmatrix}</math>

====Handlinger i konflikt====

To eller flere handlinger er i konflikt hvis

# Operasjonene tilhører forskjellige transaksjoner
# Minst en av operasjonene er en skriveoperasjon
# Operasjonen utføres på samme objekt (lesing eller skriving)

Følgende operasjoner er i konflikt med hverandre:
* T1:R(X), T2:W(X), T3:W(X)

Følgende operasjoner er ikke i konflikt: 
* T1:R(X), T2:R(X), T3:R(X)
* T1:R(X), T2:W(Y), T3:R(X)

====Konflikt-ekvivalens====

To historier S1 og S2 er konflikt-ekvivalente hvis følgende vilkår er oppfylt:

# S1 og S2 inneholder de samme transaksjonene (inkludert rekkefølgen på operasjonene innenfor hver tranaksjon).
# Hvert par av operasjoner som er i konflikt har samme rekkefølge i S1 som i S2.

====Konflikt-serialiserbarhet====

En historie er konflikt-serialiserbar hvis historien er konflikt-ekvivalent med en eller flere serielle historier.

An annen definisjon av konflikt-serialiserbarhet, er at en historie er konflikt-serialiserbar hvis og bare hvis det eksisterer en asyklisk [[presedensgraf]] for historien.

:<math>G = \begin{bmatrix}
T1 & T2 \\
R(A) &   \\
 & R(A) \\
W(B) & \\
Com. & \\
 & W(A) \\
 & Com. \\
 &\end{bmatrix}</math>

G er konflikt-serialiserbar med <T1,T2>, men ikke <T2,T1>.

====View-ekvivalens====
To historier S1 og S2 er view-ekvivalente hvis følgende vilkår er oppfylt:

# Hvis transaksjonen <math>T_i</math> i S1 leser en initiell verdi for objekt X, gjør også transaksjon <math>T_i</math> dette i S2.
# Hvis transaksjon <math>T_i</math> i S1 leser verdien X skrevet av transaksjon <math>T_j</math> i S1, skjer det samme i S2.
# Hvis transaksjonen <math>T_i</math> er den siste transaksjonen som skriver en verdi for objekt X i S1, gjelder det samme for <math>T_i</math> i S2.

====View-serialiserbarhet====
En historie er view-serialiserbar hvis den er view-ekvivalent med en seriell historie. Per definisjon er alle konflikt-serialiserbare historier view-serialiserbare (men ikke omvendt).

:<math>G = \begin{bmatrix}
T1 & T2 \\
R(A) &   \\
 & R(A) \\
W(B) & \\
 \end{bmatrix}</math>

Eksempelet ovenfor er både view-serialiserbar og konflikt-serialiserbar. Transaksjoner som utfører ''blind write'' (skriving uten å lese først), kan gi historier som er view-serialiserbare, men ikke konflikt-serialiserbare.

:<math>H = \begin{bmatrix}
T1 & T2 & T3 \\
R(A) & & \\
 & W(A) & \\
 & Com. & \\
W(A) & & \\
Com. & & \\
 & & W(A) \\
 & & Com. \\
 & & \end{bmatrix}</math>

Eksempelet er ikke konflikt-serialiserbart, men det er view-serialiserbart siden den har en view-ekvivalent seriell historie <T1,&nbsp;T2,&nbsp;T3>.

Å bestemme om en historie er view-serialiserbar er [[NP-komplett]], og view-serialiserbarhet har derfor liten praktisk anvendelse.

===Gjenopprettelig (recoverable)===<!-- This section is linked from [[Concurrency control]] -->

Transaksjoner som leser endringer gjort av andre, fullfører bare etter at transaksjonene som har endret verdiene fullfører.

:<math>F = \begin{bmatrix}
T1 & T2 \\
R(A) &   \\
W(A) &   \\
 & R(A) \\
 & W(A) \\
Com. & \\
 & Com.\\
 &\end{bmatrix} 
F2 = \begin{bmatrix}
T1 & T2 \\
R(A) &   \\
W(A) &   \\
 & R(A) \\
 & W(A) \\
Abort &  \\
& Abort \\
 &\end{bmatrix}</math>

Disse historiene er gjenopprettelige. F er gjenopprettelig fordi T1 fullfører før T2, noe som gjør verdien lest av T2 korrekt. Dermed kan T2 også fullføre. I T2, må T2 avbryte hvis T1 avbyter, fordi verdien til A da viser seg å være feil. I begge tilfeller holdes databasen konsistent.

====Ugjenopprettelig====

Hvis transaksjon T1 avbryter og T2 fullfører, men T2 avhenger av T1, har man en ugjenopprettelig historie.

:<math>G = \begin{bmatrix}
T1 & T2 \\
R(A) &   \\
W(A) &   \\
 & R(A) \\
 & W(A) \\
 & Com. \\
Abort & \\
 &\end{bmatrix}</math>

I dette eksempelet, er G ugjenopprettelig, fordi T2 leste verdien til A skrevet av T1, og deretter fullførte. Senere avbryter imidlertid T1, noe som gjør verdien som T2 leste gal. Siden T2 allerede har fullført er historien ugjenopprettelig.

====Unngå galopperende avbrudd====

På engelsk kjent som ''avoids cascading aborts (ACA)'' eller ''cascadeless''. Hindrer at en transaksjonsavbrudd fører til en rekke andre avbrudd ved å forby transaksjoner å lese data som er endret av en annen transaksjon som ikke er fullført.

Følgende eksempler er de samme som under avsnittet om gjenopprettelighet.
:<math>F = \begin{bmatrix}
T1 & T2 \\
R(A) &   \\
W(A) &   \\
 & R(A) \\
 & W(A) \\
Com. & \\
 & Com.\\
 &\end{bmatrix} 
F2 = \begin{bmatrix}
T1 & T2 \\
R(A) &   \\
W(A) &   \\
 & R(A) \\
 & W(A) \\
Abort &  \\
& Abort \\
 &\end{bmatrix}</math>

Selv om F2 er gjenopprettelig, unngår den ikke galopperende avbrudd. Dersom T1 avbryter, må T2 også avbryte for å opprettholde riktighet, siden T2 allerede har lest den ubekreftede verdien som T1 skrev.

Den følgende historien er gjenopprettelig og unngår galopperende avbrudd. Legg imidlertid merke til at oppdateringen som T1 gjør av A, går tapt.

:<math>F3 = \begin{bmatrix}
T1 & T2 \\
 & R(A) \\
R(A) &   \\
W(A) &   \\
 & W(A) \\
Abort &  \\
& Commit \\
 &\end{bmatrix}</math>

Å unngå galopperende avbrudd er tilstrekkelig, men ikke nødvendig for at en historie skal være gjenopprettelig.

====Strikt====

En historie er strikt, hvis en følgende gjelder for to transaksjoner T1 og T2: Dersom en skriveoperasjon av T1 skjer før en konflikterende operasjon av T2 (lesing eller skriving), må T1 fullføre før operasjonen som er i konflikt kan gjennomføres.

Alle strikte historier unngår galopperende avbrudd, men ikke omvendt.