Zeitstempelverfahren (englisch timestamp ordering) werden in Datenbanksystemen eingesetzt, um die Forderung der Isolation des ACID-Prinzips bei Transaktionen zu erfüllen.
Zeitstempelverfahren fallen in die Kategorie der optimistischen Synchronisationsverfahren, das heißt, es wird bei dem Start einer Transaktion davon ausgegangen, dass die Wahrscheinlichkeit eines Konflikts mit einer parallel ablaufenden Transaktion (TA) niedrig ist.
Transaktionen werden nur dann zurückgesetzt, wenn es zu einem Konflikt gekommen ist, oder gekommen sein könnte.
Um die Konflikte erkennen zu können, bekommen Transaktionen und auch Objekte Zeitstempel. Nun kann vor jedem Lese- beziehungsweise Schreibzugriff auf ein Objekt geprüft werden, ob das Objekt bereits von einer parallel laufenden TA geändert worden ist, also ein Konflikt entstanden ist, andernfalls kann der Zeitstempel aktualisiert werden.
In praktischen Anwendungen findet nicht vor jedem Zugriff auf ein Objekt eine Validierung statt, sondern die Änderungen einer Transaktion befinden sich vorerst in einem Puffer, so dass das tatsächliche Einbringen in die Datenbank (Schreiben auf Festplatte) erst nach erfolgreicher Validierungsphase (vor dem Ausführen des Commits, des Schreibvorgangs) durchgeführt wird.
Grundlegende Validierungstechniken
Für jede Transaktion wird vom Datenbanksystem ein Read-Set (Menge der Objekte, die die TA gelesen hat) und ein Write-Set (Menge der Objekte, die von der TA geschrieben wurden) geführt. Ein Konflikt liegt zwischen zwei Transaktionen genau dann vor, wenn das Write- und Read-Set der Transaktionen gleiche Objekte beinhalten.
Man unterscheidet:
- BOCC (backward-oriented optimistic concurrency control)
- Rückwärtsgerichtete Validierung: Bei Beendigung einer TA werden alle Transaktionen überprüft, die während der Ausführung der TA erfolgreich validiert haben, im Konfliktfall wird die validierende TA zurückgesetzt.
- FOCC (forward-oriented optimistic concurrency control)
- Vorwärtsgerichtete Validierung: Bei Beendigung einer TA werden alle noch laufenden Transaktionen überprüft. Im Konfliktfall werden die noch laufenden Transaktionen zurückgesetzt („Kill“-Ansatz), oder die validierende TA wird zurückgesetzt („Die“-Ansatz).