Sichtserialisierbarkeit (view-serializability VSR)

[janpet]

Hallo,
kann mir jemand verdeutlichen, wie ich mir Sichtserialisierbarkeit bei Historien (Schedules) vorzustellen habe und warum die so genannte Monotonie-Eigenschaft nicht gewährleistet werden kann?

Vielen Dank
Gruß Jan

 

[thomas_w]

AW: Sichtserialisierbarkeit (view-serializability VSR)

Das sieht mir nach Informatik-Studium aus. Google findet folgendes dazu:

http://lmgtfy.com/?q=Sichtserialisierbarkeit+Monotonie-Eigenschaft

schau Dir mal das PDF an, dass als zweites aufgelistet wird.
=> "6 Realisierungen des Transaktionsprinzips"

Vielleicht hilft dass ja weiter.

Grüße
Thomas

 

[janpet]

AW: Sichtserialisierbarkeit (view-serializability VSR)

Hallo Thomas,
erst mal vielen Dank, die PDF habe ich schon mal gelesen.

Leider wird dort nur sehr kurz auf die Sicht-Serialisierbarkeit eingegangen, ohne konkret die Problem der Monotonie und Entscheidbarkeit zu erläutern.

Viele Grüße
Jan

 

[thomas_w]

AW: Sichtserialisierbarkeit (view-serializability VSR)

Hallo Jan,

vielleicht hilft es ja, das ganze aus der Theorie in die Praxis zu transformieren und ein kleines Beispiel dazu aufzubauen. Letzlich geht es doch um den konkurrierenden Zugriff mehrerer Benutzer, wie läßt sich die Datenkonsistenz sicherstellen (ACID) und was machen dabei Transaktionen.

Grüße
Thomas

 

[janpet]

AW: Sichtserialisierbarkeit (view-serializability VSR)

Hallo Thomas,
ich verstehe, dass durch durch Sperrverfahren und -protokolle (wie 2PL) die Konflikt-Serialisierbarkeit gewährleistet werden kann.

a) Zum einen ist es effektiv entscheidbar, ob der (zwar erst nach einer jeweiligen abgeschlossenen Transaktion, aber immerhin) entstandene Serialisierungsgraph Zyklen enthält oder doch azyklisch ist und

b) das durch das 2PL und dem Anfordern und Freigeben von Lese- und Schreibsperren die Konfliktserialisierbarkeit gewährleistet werden kann.

Leider habe ich überhaupt keine Vorstellung darüber, was konkret bei der Sicht-Serialisierbarkeit nicht gewährleistet werden kann. Da fehlt mir noch glatt das Verständnis.

Viele Grüße
Jan

 

[thomas_w]

AW: Sichtserialisierbarkeit (view-serializability VSR)

Hallo Jan,

also ich möchte Dich jetzt nicht auf eine falsche Fährte locken und die ganze Theorie habe ich schon lange wieder vergessen. Vermutlich habe ich es auch nicht richtig verstanden.

Aber ich stelle es mir wie folgt vor:

Tabelle:
 
wertA ! wertB
-------------
  1   !   2  
 
 
Zeitgleiche Änderung zweiter Benutzer:
---------------------------------------------------
1. User1 - UPDATE WertA 1 => 11
2. User2 - UPDATE WertB 2 => 22
3. User2 - COMMIT 
4. User1 - ROLLBACK
 
Tabelle inhalt:
wertA ! wertB
-------------
  1   !   2  
 
Hier gibt es einen verlorenen Update "Lost Update" des User2 (je nach dem welcher Isolation-Level verwendet worden ist)

http://de.wikipedia.org/wiki/Serialisierbarkeit#Sichtenserialisierbarkeit


Vielleicht hilft es ja, aber wie gesagt, alles ohne Garantie und doppelten Boden. Kannst Du nicht Deinen HiWi nochmal ausquetschen?

Grüße
Thomas

 

[janpet]

AW: Sichtserialisierbarkeit (view-serializability VSR)

Hallo Thomas,
ein lost update wäre es hier nicht, denn Transaktion User2 schreibt ja nur den wertB, was durch den Abbruch der Transaktion User1 nicht behindert wird.
Der Scheduler setzt einfach nur lt. ACID (alles oder nichts) die Transaktion User1 zurück, wodurch wertA bei 1 bleibt.

Unter Umständen hätte ein dirty read auftreten können, wenn die Transaktion User2 den geänderten wertA gelesen und für die Berechnung von wertB verwendet hätte (bzw. ein dirty write, wenn User2 den ermittelten wertB zurückschreibt).

Leider sind diese Anomalien noch nicht wirklich hilfreich für mein Verständnis der Sicht-Serialisierbarkeit.

Aber trotzdem vielen Dank erst mal, vielleich fällt Dir ja noch etwas ein.
Viele Grüße
Jan

 

[thomas_w]

AW: Sichtserialisierbarkeit (view-serializability VSR)

Aber trotzdem vielen Dank erst mal, vielleicht fällt Dir ja noch etwas ein.

Das zeigt mir auf jeden Fall, dass ich mich mal wieder dringend damit beschäftigen sollte.

Beispielweise sieht dies hier ganz erfolgversprechend aus:
http://www.kreissl.info/db_08.php

Bis dahin..und schönes Wochenende.

Grüße
Thomas

 

[thomas_w]

AW: Sichtserialisierbarkeit (view-serializability VSR)

Beispielweise sieht dies hier ganz erfolgversprechend aus:
http://www.kreissl.info/db_08.php

Sieht leider nur auf den ersten Blick gut aus, so richtig in die Tiefe geht es auch nicht, schade. Mal sehen, ob ich noch was im Bücherregal finde..

Grüße
Thomas

 

[janpet]

AW: Sichtserialisierbarkeit (view-serializability VSR)

Hi Thomas,
das ist doch schon mal viel wert.

Soll also heißen, dass der zu einer Historie H gehörende Serialisierbarkeitsgraph SG(H) nicht nur azyklisch sein muss, sondern dass sowohl in H als auch in dessen seriellen Historie H' alle Leseoperationen dieselbe Sicht auf die geschriebenen Werte haben müssen.

Jetzt wird's haarig:
Warum kann bei der Sichtserialisierbarkeit nicht die Monotonie-Eigenschaft gewährleistet werden?
Monotonie für die Historie H bedeutet wohl so viel, dass die aus einer Projektion einzelner Transaktionen entstandene Historie H'' von H dieselben Eigenschaften besitzt.

Viele Grüße
Jan

 

[thomas_w]

AW: Sichtserialisierbarkeit (view-serializability VSR)

Hallo Jan,

ich glaube, ich steige aus dem Thema aus, mir fehlt da jetzt einfach der theoretische Background und die formale Sprache dazu. Ich möchte auch keinen Unsinn verzapfen.

http://www.kreissl.info/db_08.php
Das Beste wird sein, Du wendest Dich direkt mal an den Verfasser des obigen Artikels. Sorry..

Grüße
Thomas

 

[janpet]

AW: Sichtserialisierbarkeit (view-serializability VSR)

Hallo Thomas,
trotzdem vielen Dank für Deine Hinweise, sie haben mir in Summe dann doch weiter geholfen.

Nach einigen Überlegungen bin ich zu dem Schluss gekommen, dass die Sichtserialisierbarkeit aus folgendem Grund nicht monoton ist:
Angenommen, eine Historie H enthält drei Transaktionen {TA1, TA2, TA3}, wobei TA1 und TA3 auf die geschriebenen Werte von TA2 lesend zugreifen.
Eine Historie H'' entsteht durch Projektion von TA1 und TA3 auf H.
H'' erfüllt nun aber die Lese-Eigenschaften von TA1 und TA3 auf die Schreiboperation von TA2 nicht mehr, da sich TA2 eben nicht in H'' befindet.

Ich hoffe, das ist so korrekt.
Viele Grüße
Jan