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
        =
        
          
            [
            
              
                
                  T
                  1
                
                
                  T
                  2
                
                
                  T
                  3
                
              
              
                
                  R
                  (
                  X
                  )
                
                
                
              
              
                
                  W
                  (
                  X
                  )
                
                
                
              
              
                
                  C
                  o
                  m
                  .
                
                
                
              
              
                
                
                  R
                  (
                  Y
                  )
                
                
              
              
                
                
                  W
                  (
                  Y
                  )
                
                
              
              
                
                
                  C
                  o
                  m
                  .
                
                
              
              
                
                
                
                  R
                  (
                  Z
                  )
                
              
              
                
                
                
                  W
                  (
                  Z
                  )
                
              
              
                
                
                
                  C
                  o
                  m
                  .
                
              
            
            ]
          
        
      
    
    {\displaystyle 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
        =
        
          
            [
            
              
                
                  T
                  1
                
                
                  T
                  2
                
                
                  T
                  3
                
              
              
                
                  R
                  (
                  X
                  )
                
                
                
              
              
                
                
                  R
                  (
                  Y
                  )
                
                
              
              
                
                
                
                  R
                  (
                  Z
                  )
                
              
              
                
                  W
                  (
                  X
                  )
                
                
                
              
              
                
                
                  W
                  (
                  Y
                  )
                
                
              
              
                
                
                
                  W
                  (
                  Z
                  )
                
              
              
                
                  C
                  o
                  m
                  .
                
                
                  C
                  o
                  m
                  .
                
                
                  C
                  o
                  m
                  .
                
              
            
            ]
          
        
      
    
    {\displaystyle 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

Operasjonene tilhører forskjellige tranaksjoner
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.

  
    
      
        G
        =
        
          
            [
            
              
                
                  T
                  1
                
                
                  T
                  2
                
              
              
                
                  R
                  (
                  A
                  )
                
                
              
              
                
                
                  R
                  (
                  A
                  )
                
              
              
                
                  W
                  (
                  B
                  )
                
                
              
              
                
                  C
                  o
                  m
                  .
                
                
              
              
                
                
                  W
                  (
                  A
                  )
                
              
              
                
                
                  C
                  o
                  m
                  .
                
              
              
                
                
              
            
            ]
          
        
      
    
    {\displaystyle 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:

Hvis transaksjonen 
  
    
      
        
          T
          
            i
          
        
      
    
    {\displaystyle T_{i}}
   i S1 leser en initiell verdi for objekt X, gjør også transaksjon 
  
    
      
        
          T
          
            i
          
        
      
    
    {\displaystyle T_{i}}
   dette i S2.
Hvis transaksjon 
  
    
      
        
          T
          
            i
          
        
      
    
    {\displaystyle T_{i}}
   i S1 leser verdien X skrevet av transaksjon 
  
    
      
        
          T
          
            j
          
        
      
    
    {\displaystyle T_{j}}
   i S1, skjer det samme i S2.
Hvis transaksjonen 
  
    
      
        
          T
          
            i
          
        
      
    
    {\displaystyle T_{i}}
   er den siste transaksjonen som skriver en verdi for objekt X i S1, gjelder det samme for 
  
    
      
        
          T
          
            i
          
        
      
    
    {\displaystyle 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
        =
        
          
            [
            
              
                
                  T
                  1
                
                
                  T
                  2
                
              
              
                
                  R
                  (
                  A
                  )
                
                
              
              
                
                
                  R
                  (
                  A
                  )
                
              
              
                
                  W
                  (
                  B
                  )
                
                
              
            
            ]
          
        
      
    
    {\displaystyle 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
        =
        
          
            [
            
              
                
                  T
                  1
                
                
                  T
                  2
                
                
                  T
                  3
                
              
              
                
                  R
                  (
                  A
                  )
                
                
                
              
              
                
                
                  W
                  (
                  A
                  )
                
                
              
              
                
                
                  C
                  o
                  m
                  .
                
                
              
              
                
                  W
                  (
                  A
                  )
                
                
                
              
              
                
                  C
                  o
                  m
                  .
                
                
                
              
              
                
                
                
                  W
                  (
                  A
                  )
                
              
              
                
                
                
                  C
                  o
                  m
                  .
                
              
              
                
                
                
              
            
            ]
          
        
      
    
    {\displaystyle 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
        =
        
          
            [
            
              
                
                  T
                  1
                
                
                  T
                  2
                
              
              
                
                  R
                  (
                  A
                  )
                
                
              
              
                
                  W
                  (
                  A
                  )
                
                
              
              
                
                
                  R
                  (
                  A
                  )
                
              
              
                
                
                  W
                  (
                  A
                  )
                
              
              
                
                  C
                  o
                  m
                  .
                
                
              
              
                
                
                  C
                  o
                  m
                  .
                
              
              
                
                
              
            
            ]
          
        
        F
        2
        =
        
          
            [
            
              
                
                  T
                  1
                
                
                  T
                  2
                
              
              
                
                  R
                  (
                  A
                  )
                
                
              
              
                
                  W
                  (
                  A
                  )
                
                
              
              
                
                
                  R
                  (
                  A
                  )
                
              
              
                
                
                  W
                  (
                  A
                  )
                
              
              
                
                  A
                  b
                  o
                  r
                  t
                
                
              
              
                
                
                  A
                  b
                  o
                  r
                  t
                
              
              
                
                
              
            
            ]
          
        
      
    
    {\displaystyle 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
        =
        
          
            [
            
              
                
                  T
                  1
                
                
                  T
                  2
                
              
              
                
                  R
                  (
                  A
                  )
                
                
              
              
                
                  W
                  (
                  A
                  )
                
                
              
              
                
                
                  R
                  (
                  A
                  )
                
              
              
                
                
                  W
                  (
                  A
                  )
                
              
              
                
                
                  C
                  o
                  m
                  .
                
              
              
                
                  A
                  b
                  o
                  r
                  t
                
                
              
              
                
                
              
            
            ]
          
        
      
    
    {\displaystyle 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
        =
        
          
            [
            
              
                
                  T
                  1
                
                
                  T
                  2
                
              
              
                
                  R
                  (
                  A
                  )
                
                
              
              
                
                  W
                  (
                  A
                  )
                
                
              
              
                
                
                  R
                  (
                  A
                  )
                
              
              
                
                
                  W
                  (
                  A
                  )
                
              
              
                
                  C
                  o
                  m
                  .
                
                
              
              
                
                
                  C
                  o
                  m
                  .
                
              
              
                
                
              
            
            ]
          
        
        F
        2
        =
        
          
            [
            
              
                
                  T
                  1
                
                
                  T
                  2
                
              
              
                
                  R
                  (
                  A
                  )
                
                
              
              
                
                  W
                  (
                  A
                  )
                
                
              
              
                
                
                  R
                  (
                  A
                  )
                
              
              
                
                
                  W
                  (
                  A
                  )
                
              
              
                
                  A
                  b
                  o
                  r
                  t
                
                
              
              
                
                
                  A
                  b
                  o
                  r
                  t
                
              
              
                
                
              
            
            ]
          
        
      
    
    {\displaystyle 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.

  
    
      
        F
        3
        =
        
          
            [
            
              
                
                  T
                  1
                
                
                  T
                  2
                
              
              
                
                
                  R
                  (
                  A
                  )
                
              
              
                
                  R
                  (
                  A
                  )
                
                
              
              
                
                  W
                  (
                  A
                  )
                
                
              
              
                
                
                  W
                  (
                  A
                  )
                
              
              
                
                  A
                  b
                  o
                  r
                  t
                
                
              
              
                
                
                  C
                  o
                  m
                  m
                  i
                  t
                
              
              
                
                
              
            
            ]
          
        
      
    
    {\displaystyle 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 historierVenn-diagrammet nedenfor uttrykker forholdet grafisk:


== 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