Redigerer Historie (databaser) (avsnitt)

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