2-Mehrbenutzersync.

• BOT_i -> Begin of Transaction

• r_i(A) -> read A

• w_i(A) -> write A

• a_i -> abbort TA

• c_i -> commit TA

-> Beide auf selbem Objekt, eine davon write()

—> wenn in Konflik: dürfen nicht parallel ausgeführt werden

• SR: serialisierbar

• RC: rücksetzbar

• ACA: vermeidet kaskadierendes Rücksetzen

• ST: strikt

• ST&SR: seriell

1. Jede committete Transaktion ist ein Knoten im Graph

2. Jede Konfliktoperationen Kij ist eine Kante im Graph ➡ Zeichne einen Pfeil von Ti nach Tj, wenn σi < σj

SR —> wenn SG azyklisch —> Historie serialisierbar

RC (ReCoverable):

• Write() muss vor Read() commiten

Steps:

• commit Reihenfolge aufschreiben

• Konfilke mit w < r prüfen

• Gewünschte commit Reihenfolge mit echter abgleichen

• wenn gleich -> Rücksetzbar

ACA (Avoiding Cascading Aborts):

• w(X) < c(X) < r(X)

Steps:

• Konfilkte mit w < r

• w_i < c_i < r_j

ST (STrict):

• w(X) < c(X) or a(X) < r(X) or w(X)

Ordnet eingehende Operationen um serielle & rücksetzbare Historien zu garantieren

Möglichkeiten für Eingangsoperationen:

• sofortige Ausführung

• zurückweisen -> abbruch

• verzögern

• Optimistisch:

  • schnelles arbeiten

  • anschließend Probleme aufräumen

• Pessimistisch: Möglichst geschickt

Snapshot Isolation

• Jede Transaktion arbeitet in einer eigenen Version der DB

• Commit -> Änderungen eingefügt => Überschneiden des Write-Sets wird abgebrochen

• TA stoppen bei Problem

  • —> im Anschluss keine Probleme

• Zeitstempelbasiert:

  • Jedes Datum: -> wann wurde zuletzt r()/w()

  • Jede TA -> wann start

  • —> TA trifft auf neuen Zeitstempel —> Abbruch

• Jedes X hat eine Sperre

• TA muss Zugriff auf X anfordern

  • wenn gesperrt: TA wartet

  • wenn offen: TA startet

  • TA Ende -> Sperre offen

• 2 Arten:

  • Shared Lock (Lesesperre)

  • Exclusive Lock (Schreibesperre)

• Benutzen? -> Obj. muss gesperrt sein

• TA kann Sperre nur ein Mal anfordern

  • wenn schon zu -> in Warteschlange

• TA Ende -> alle Sperren öffnen

Strenges:

—> Haken = verhindert Problem

Verklemmungen —> Deadlocks

-> entstehen durch Zyklen im Wartegraph von TAs

-> können beide w() auch wenn Bedingung für TA eig. nur für 1 gleichzeitig zutrifft

geht nicht bei optimistischer

• Timeouts

• Wartgraphen auf Zyklen prüfen —> ideal, aber teuer

• Preclaiming

  • TA fragt alle Sperren an —> kaum Parallelität

• Zeitstempel

  • TA Abbruch je nach TS -> viele FPs und Live Lock möglich