Historie (databaser)

En historie er en abstrakt modell som brukes for å beskrive utførelse av transaksjoner kjørt i et databasesystem. En historie representeres ofte ved en kronologisk liste av operasjoner utført av transaksjoner som kjøres sammen i systemet. Eksempler på en operasjon er lesing, skriving, avbrudd, fullføring (commit), låsing etc. Ikke alle operasjonstyper bør være med i alle historier, vanligvis representeres kun de operasjoner som er nødvendig for å beskrive et bestemt fenomen. Historier og historieegenskaper er fundamentale konsepter innenfor samtidighetskontroll.

Formell beskrivelse av en historie

Følgende er et eksempel på en historie:

$D={\begin{bmatrix}T1&T2&T3\\R(X)&&\\W(X)&&\\Com.&&\\&R(Y)&\\&W(Y)&\\&Com.&\\&&R(Z)\\&&W(Z)\\&&Com.\end{bmatrix}}$

I dette eksempelet, representerer den horisontale aksen de forskjellige transaksjonene i historie D. Den vertikale aksen representerer rekkefølgen til operasjonene. Historien ovenfor består av tre transaksjoner T1, T2 og T3. Historien beskriver handlingene til transaksjonene slik databasehåndteringssystemet (DBMS) ser det. Først leser og skriver T1 til objekt X. Deretter fullfører transaksjonen. Så leser og skriver T2 til objekt Y og fullfører. Til slutt leser og skriver T3 til objekt Z og fullfører. Dette er et eksempel på en seriell historie, fordi handlingene til de tre transaksjonene ikke er flettet.

Den samme historien kan uttrykkes som en liste, slik:

D = R1(X) W1(X) Com1 R2(Y) W2(Y) Com2 R3(Z) W3(Z) Com3

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.

$E={\begin{bmatrix}T1&T2&T3\\R(X)&&\\&R(Y)&\\&&R(Z)\\W(X)&&\\&W(Y)&\\&&W(Z)\\Com.&Com.&Com.\end{bmatrix}}$

Handlinger i konflikt

To eller flere handlinger er i konflikt hvis

1. Operasjonene tilhører forskjellige transaksjoner
2. Minst en av operasjonene er en skriveoperasjon
3. 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:

1. S1 og S2 inneholder de samme transaksjonene (inkludert rekkefølgen på operasjonene innenfor hver tranaksjon).
2. 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.

$G={\begin{bmatrix}T1&T2\\R(A)&\\&R(A)\\W(B)&\\Com.&\\&W(A)\\&Com.\\&\end{bmatrix}}$

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:

1. Hvis transaksjonen $T_{i}$ i S1 leser en initiell verdi for objekt X, gjør også transaksjon $T_{i}$ dette i S2.
2. Hvis transaksjon $T_{i}$ i S1 leser verdien X skrevet av transaksjon $T_{j}$ i S1, skjer det samme i S2.
3. Hvis transaksjonen $T_{i}$ er den siste transaksjonen som skriver en verdi for objekt X i S1, gjelder det samme for $T_{i}$ 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).

$G={\begin{bmatrix}T1&T2\\R(A)&\\&R(A)\\W(B)&\\\end{bmatrix}}$

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.

$H={\begin{bmatrix}T1&T2&T3\\R(A)&&\\&W(A)&\\&Com.&\\W(A)&&\\Com.&&\\&&W(A)\\&&Com.\\&&\end{bmatrix}}$

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

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

Gjenopprettelig (recoverable)

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

$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}}$

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.

$G={\begin{bmatrix}T1&T2\\R(A)&\\W(A)&\\&R(A)\\&W(A)\\&Com.\\Abort&\\&\end{bmatrix}}$

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.

$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}}$

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.

$F3={\begin{bmatrix}T1&T2\\&R(A)\\R(A)&\\W(A)&\\&W(A)\\Abort&\\&Commit\\&\end{bmatrix}}$

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

Hierarkisk forhold mellom serialiserbarhetsklasser

Følgende uttrykk illustrerer forholdet mellom klassene av serialiserbarhet

• Seriell ⊂ commitment-ordered ⊂ konflikt-serialiserbar ⊂ view-serialiserbar ⊂ alle historier
• Seriell ⊂ strikt ⊂ unngå galopperende avbrudd ⊂ gjenopprettelig ⊂ alle historier

Venn-diagrammet nedenfor uttrykker forholdet grafisk:

Forholdet mellom klassene av serialiserbarhet

Implementasjon

I praksis, anvender de fleste generelle databasesystemer konflikt-serialiserbare og gjenopprettelige (primært strikte) historier.

Litteratur

• Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems, Addison Wesley Publishing Company, 1987, ISBN 0-20110-715-5
• Gerhard Weikum, Gottfried Vossen: Transactional Information Systems, Elsevier, 2001, ISBN 1-55860-508-8