Next: 3.1.2 Isolationsgrade
Up: Klassische Systeme und
Previous: Klassische Systeme und
Die meisten in der Literatur vorgestellten (klassischen) Transaktionssysteme werden daran gemessen, inwiefern sie die ACID--Prinzipien
[HR83,Gra81]
erfüllen. Sie sollen darum hier kurz wiederholt werden:
- Atomicity / Atomarität
- Eine Transaktion wird entweder vollständig oder gar nicht
ausgeführt.
- Consistency / Konsistenz
- Eine Transaktion überführt einen konsistenten Zustand
der Datenbank in einen anderen konsistenten Zustand.
- Isolation
- Die Zwischenergebnisse gleichzeitig ablaufender Transaktionen
dürfen jeweils für die anderen Transaktionen nicht sichtbar sein. Man
könnte auch sagen: Keine Transaktion merkt, daß andere Transaktionen parallel
zu ihr laufen.
- Durability / Dauerhaftigkeit
- Die Ergebnisse einer erfolgreichen Transaktion werden gegen
Versagen der Hard-- und Software gesichert und können nur
durch eine weitere Transaktion wieder geändert werden.
Im klassischen Fall werden die Punkte 'Consistency' und 'Isolation'
normalerweise dadurch erreicht, daß man verlangt, daß die Transaktionen
serialisierbar ablaufen. Serialisierbar
[3] (s. z.B. [BHG87])
bedeutet vereinfacht, daß die Abfolge der atomaren Aktionen
(auch 'Schedule' oder Historie genannt)
der Transaktionen äquivalent zu einer
Abfolge sein muß, die sich bei serieller Hintereinanderausführung der
Transaktionen ergäbe. Verschiedene Definitionen der ``Äquivalenz``
führen dann zu den unterschiedlichen Versionen der Serialisierbarkeit, die
unten behandelt werden.
Die Erhaltung von Konsistenz und Isolation bei Serialisierbarkeit läßt sich
anschaulich folgendermaßen begründen:
Unter der Voraussetzung, daß jede Transaktion im Einzelbetrieb die
Konsistenz der Daten erhält, bleibt diese auch bei serieller
Hintereinanderausführung erhalten. Da aber jeder 'Schedule' paralleler
Transaktionen zu einer solchen seriellen Ausführung äquivalent sein muß,
erhalten auch
serialisierbar ausgeführte Transaktionen die Konsistenz.
Die Isolation ergibt sich (zumindest bei Sichten-- und
Konflikt--Serialisierbarkeit, vgl. unten) dadurch, daß in der äquivalenten seriellen
Auführung jede Transaktion nur Endergebnisse der anderen lesen kann.
Für die Äquivalenz der 'Schedules' von Transaktionen gibt es drei
verschiedene Definitionen [Pap86, Kap.2,] und [VGH93]:
- Zustands--Serialisierbarkeit (ZSR)
- Dies ist die intuitivste Definiton. Zwei
Abfolgen der gleichen Transaktionen
sind äquivalent, wenn für alle möglichen Anfangszustände und
Semantiken der Transaktionen die Endzustände jeweils gleich sind.
- Sichten--Serialisierbarkeit (SSR)
- ist eine Verschärfung der
Zustands--Serialisierbarkeit. Es wird zusätzlich verlangt, daß jede
Leseoperation in den beiden 'Schedules' jeweils den Wert von derselben
Schreiboperation erhält.
- Konflikt--Serialisierbarkeit (KSR)
- verlangt, daß die Reihenfolge jeweils
zweier in Konflikt stehenden Operationen in beiden 'Schedules' gleich bleibt.
Bei der Definition der Konflikt--Serialisierbarkeit wurde der Begriff
``Konflikt`` verwendet. Zwei Operationen stehen in Konflikt, wenn sie dasselbe
Datum behandeln, und wenigstens eine das Datum ändert, also schreibt. Den
englischen Bezeichnungen für Lesen (Read) und
Schreiben (Write) folgend, unterscheidet man
R/W--, W/R-- und W/W--Konflikte.
In der Praxis wird meist nur die Konflikt--Serialisierbarkeit verwendet,
da -- wie z.B.
[Pap86] zeigt -- der Test auf eines der beiden anderen Kriterien
NP--vollständig ist. Allerdings
ist KSR auch am restriktivsten, d.h. für die Mengen der serialisierbaren
'Schedules' gilt 
. Es gibt
aber sogar Abfolgen, die die Konsistenz wahren, jedoch nicht in
ZSR liegen.
Nicht alle Schedules, die korrekt sind, sind also auch serialisierbar. Ein
Transaktionskonzept, das auf die (Konflikt--)Serialisierbarkeit als
Korrektheitskriterium verzichtet, erlaubt darum eine höhere Parallelität.
Ein Verfahren, welches obigen Ablauf als korrekt erkennen würde, wird z.B.
in Abschnitt 3.2.1 vorgestellt.
Figure: 
Next: 3.1.2 Isolationsgrade
Up: Klassische Systeme und
Previous: Klassische Systeme und
Markus Baumeister
Fri Jun 9 15:38:00 MET DST 1995