Zurück

Serialisierbarkeit am Beispiel

In diesem Beispiel soll verdeutlicht werden, wie ein Ablaufplan mit mehreren Transaktionen auf Serialisierbarkeit überprüft werden kann. Hierfür werden alle Operationen schrittweise auf Abhängigkeiten zu anderen Operationen überprüft. Wenn Abhängigkeiten im Ablaufplan links gefunden werden, werden sie im Graphen rechts eingezeichnet, sodass am Schluss leicht ablesbar ist, ob der Ablaufplan konfliktfrei ist.

Definition Eine Menge von Datenbank-Transaktionen lässt sich genau dann serialisieren, wenn der zugehörige Serialisierbarkeitsgraph zyklenfrei ist.

Serialisierbarkeitsgraph

Schritt zurück Nächster Schritt Transaktionen neu laden Zyklen finden Der Graph ist zyklenfrei.

Ablaufplan

Serialisierbarkeitsgraph

Der Algorithmus geht schrittweise durch den Ablaufplan unten und hebt die Abhängigkeiten der aktiven Transaktion zu allen anderen Transaktionen hervor. Hierfür werden in allen nachfolgenden Schritten solche Operationen gesucht, die einen Konflikt mit der aktuellen Operation hervorrufen. Konflikt-Operationen sind: read after write, write after read und write after write auf dasselbe Datenobjekt.

Benutze die Pfeile und , um zum nächsten oder vorherigen Schritt im Ablaufplan zu springen. Die aktuelle Zeile wird in der Tabelle blau hervorgehoben. Wenn nachfolgende Operationen anderer Transaktionen mit der aktuellen Operation im Konflikt stehen, dann wird die entsprechende Zeile rot hervorgehoben. Im Graphen rechts erscheint dann eine gerichtete Kante zwischen den beiden Transaktions-Knoten.

Der Rücksetzen Button liefert dir einen neuen, zufälligen Ablaufplan mit einer zufälligen Anzahl an Transaktionen. Der Überprüfen-Button untersucht den Graphen (nach Überprüfung aller Operationen) auf Zyklen und hebt betroffene Transaktions-Knoten rot hervor.

Hinweis Du kannst die Position der Knoten im Graphen per drag-and-drop verschieben, um die Sichtbarkeit zu verbessern.