View-Äquivalenz

Zwei Schedules sind view-äquivalent, wenn für sie die gleiche Reads-From Relation gilt. Diese Relation ist durch einen Graph darstellbar (Reads-From Graph).

Zusätzlich zu den am Schedule beteiligten Transaktionen wird

• eine Transaktion betrachtet, die alle Datenobjekte schreibt und vor allen anderen Transaktionen ausgeführt wird (in der Abbildung als 0 bezeichnet) und
• eine Transaktion eingefügt, die nach Abschluß aller anderen Transaktionen alle Datenobjekte liest (Transaktion 4).

Es wird eine Kante in den Graph eingefügt, wenn eine Transaktion den Wert eines Datenobjekts liest, den eine andere Transaktion geschrieben hat.

Wenn beim Konfliktgraph (siehe Konflikt-Äquivalenz) die Transaktionen 0 und 4 ebenfalls berücksichtigt wären, würde es sich beim Reads-From Graph um einen echten Teilgraph desKonfliktgraphen handeln. Deswegen ist die Menge der konflikt-serialisierbaren Schedules eine Teilmenge der view-serialisierbaren Schedules.

Es gibt für Reads-From Graphen keine so effiziente Möglichkeit, wie die Prüfung auf Kreisfreiheit beim Konfliktgraph, um die Äquivalenz zu einem Reads-From Graphen eines seriellen Schedules zu überprüfen. Anstatt dessen muß man die Graphen aller seriellen Schedules bilden und einzeln auf Gleichheit testen. Das Problem, festzustellen, ob der Reads-From Graph zu einem entsprechenden Graphen eines seriellen Schedules äquivalent ist, ist NP-vollständig.


Anlage

Abbildung: Reads-From Graph für den Schedule r2(X) r1(X) w1(Z) w2(X) w2(Y) c2 w1(Y) c1 r3(X) r3(Y) w3(Z) c3.