Γράφος Σειριοποιησιμότητας

Ένας τρόπος ελέγχου αν ένα χρονοπρόγραμμα είναι σειριοποιήσιμο είναι ο γράφος συγκρούσεων ή γράφο προήγησης (precedence graph) ή γράφο σειριοποιησιμότητας (serialization graph). Ο γράφος χρησιμοποιείται στο πλαίσιο του Ελέγχου Ταυτοχρονισμου στις Βασεις δεδομένων. Με τον γράφο σειριοποιησιμότητας μοντελοποιούμε τις συγκρούσεις μέσα σε ένα χρονοπρόγραμμα με ένα γράφο ο οποίος περιέχει:

• Ένα κόμβο για κάθε συναλλαγή

• Μια κατευθυνόμενη ακμή από την συναλλαγή T_i στην συναλλαγή T_j, αν μια ενέργεια της T_i συγκρούεται με μια επακόλουθή της, της T_j. Δηλαδή για παράδειγμα αν έχουμε την εξής σύγκρουση R1(A);W2(A) τότε θα σχεδιάσουμε μία ακμή από τον προηγούμενο κόμβο στον επόμενο δηλαδή από το 1 προς το 2.

Το χρονοπρόγραμμα είναι σειριοποιήσιμο συγκρούσεων αν ο γράφος δεν περιέχει κύκλο. Σε αντίθετη περίπτωση δηλαδή αν ο γράφος έχει κύκλο δεν είναι σειριοποιήσιμο συγκρούσεων.

Αλγόριθμος Γράφου Συγκρούσεων

Υπάρχει ένας απλός αλγόριθμος για να προσδιοριστεί αν ένα χρονοπρόγραμμα είναι σειριοποιήσιμο συγκρούσεων. Στην πράξη οι περισσότερες μέθοδοι ελέγχου σειριοποιησιμότητας δεν ελέγχουν αν ένα χρονοπρόγραμμα είναι σειριοποιήσιμο συγκρούσεων αλλά αναπτύσσοντας πρωτόκολλα ή κανόνες εγγυούνται ότι ένα χρονοπρόγραμμα είναι σειριοποιήσιμο. Δύο τέτοιες μέθοδοι είναι το Κλείδωμα δύο Φάσεων (2PL – 2 Phase Locking) και μια παραλλαγή αυτού ο αυστηρός 2PL.

Ο αλγόριθμος χρησιμοποιείται για να ελεγθεί αν ένα χρονοπρόγραμμα είναι σειριοποιήσιμο συγκρούσεων. Θεωρούμε μόνο τις πράξεις ανάγνωση_αντικειμένου και εγγραφή_αντικειμένου για την κατασκευή του γράφου συγκρούσεων.

Ο αλγόριθμος σχεδίασης του γράφου συγκρούσεων είναι η εξής:

1. Για κάθε συναλλαγή Τ_i η οποία συμμετέχει στο χρονοπρόγραμμα S δημιουργούμε έναν κόμβο με όνομα το όνομα της συναλλαγής Τ_i
2. Για κάθε περίπτωση στο S όπου η T_j εκτελεί μια πράξη ανάγνωση _αντικ(Χ) μετά από μία πράξη εγγραφή_αντικ(Χ) που εκτελείται από την T_i δημιούργησε μία ακμή (T_i--> T_j) στον γράφο.
3. Για κάθε περίπτωση στο S όπου η T_j εκτελεί μια πράξη εγγραφή_αντικ(Χ) μετά από μία πράξη ανάγνωση _αντικ(Χ) που εκτελείται από την T_i δημιούργησε μία ακμή (T_i--> T_j) στον γράφο.
4. Για κάθε περίπτωση στο S όπου η T_j εκτελεί μια πράξη εγγραφή_αντικ(Χ) μετά από μία πράξη εγγραφή_αντικ(Χ) που εκτελείται από την T_i δημιούργησε μία ακμή (T_i--> T_j) στον γράφο.
5. Το χρονοπρόγραμμα S είναι σειριοποιήσιμο αν ο γράφος σειριοποιησιμότητας δεν έχει κύκλους. Αν ο γράφος σειριοποιησιμότητας έχει κύκλους, τότε δεν μπορούμε να βγάλουμε συμπέρασμα για το αν το χρονοπρόγραμμα S είναι ή όχι σειριοποιήσιμο και η σειριοποιησιμότητα θα πρέπει να ελεγθεί με άλλες τεχνικές.

Ο γράφος σειριοποιησιμότητας κατασκευάζεται σύμφωνα με τον παραπάνω αλγόριθμο. Αν δεν υπάρχει κύκλος στο γράφο τότε το χρονοπρόγραμμα είναι σειριοποιήσιμο. Κύκλος σε έναν κατευθυνόμενο γράφο είναι μία ακολουθία ακμών με την ιδιότητα ότι ο αρχικός κόμβος ενός μονοπατιού είναι ίδιος με τον τελικό.

Ισοδύναμο Σειριακό Χρονοπρόγραμμα

Στον γράφο σειριοποιησιμότητας μια ακμή από τον κόμβο T_i στον κόμβο T_j σημαίνει ότι η συναλλαγή T_i πρέπει να προηγείται της T_j σε κάθε σειριακό χρονοπρόγραμμα που είναι ισοδύναμο με το χρονοπρόγραμμα S, διότι κάθε ζεύγος συγκρουόμενων πράξεων εμφανίζεται στο χρονοπρόγραμμα με την συγκεκριμένη σειρά. Αν στο γράφο σειριοποιησιμότητας δεν υπάρχει κύκλος τότε μπορούμε να δημιουργήσουμε ένα ισοδύναμο σειριακό χρονοπρόγραμμα S΄ το οποίο θα είναι ισοδύναμο με το S διατάσσοντας με τον ακόλουθο τρόπο τις συναλλαγές που συμμετέχουν στο S: όταν υπάρχει μία ακμή στο γράφο σειριοποιησιμότητας από τον κόμβο T_i στον T_j, η συναλλαγή T_i πρέπει να προηγείται της T_j στο ισοδύναμο σειριακό χρονοπρόγραμμα S΄.

Παράδειγμα Έστω το χρονοπρόγραμμα S: R1(X) R2(X) R3(Y) W2(X) W1(Z) W2(Y) R4(X) W2(Z). Σχεδιάζουμε τον γράφο σειριοποιησιμότητας:

Στον παραπάνω γράφο δεν υπάρχει κανένας κύκλος συνεπώς το αντίστοιχο πρόγραμμα είναι σειριοποιήσιμο. Τα ισοδύναμα σειριακά προγράμματα είναι τα:

1. Τ1 -> Τ3 -> Τ2 -> Τ4
2. Τ3 -> Τ1 -> Τ2 -> Τ4.

Παραδείγματα εφαρμογής αλγορίθμου

Παράδειγμα 1 - Εφαρμογή Αλγορίθμου

S1: R1(A),R1(B),W1(A),R2(A),R1(C),W1(C),R3(C),W2(A),R3(B),W3(A)

1. Δημιουργούμε 3 κόμβους με ονόματα Τ1, Τ2, Τ3 όσες και οι συναλλαγές του χρονοπρογράμματος S1.

2. Για κάθε περίπτωση στο S όπου η T_j εκτελεί μια πράξη ανάγνωση _αντικ(Χ) μετά από μία πράξη εγγραφή_αντικ(Χ) που εκτελείται από την T_i δημιούργησε μία ακμή (T_i--> T_j) στον γράφο.

• Για το αντικείμενο Α έχουμε: W1(Α) και μετά ανάγνωση R2(Α) άρα ακμή Τ1->Τ2.
• Για το αντικείμενο B δεν υπάρχει κάποια σύγκρουση για αυτόν τον κανόνα.
• Για το αντικείμενο C έχουμε: W1(C) και μετά ανάγνωση R3(C) άρα ακμή Τ1->Τ3

3. Για κάθε περίπτωση στο S όπου η T_j εκτελεί μια πράξη εγγραφή_αντικ(Χ) μετά από μία πράξη ανάγνωση _αντικ(Χ) που εκτελείται από την T_i δημιούργησε μία ακμή (T_i--> T_j) στον γράφο.

• Για το αντικείμενο Α έχουμε: α) R1(Α) και μετά εγγραφή W2(Α) άρα ακμή Τ1->Τ2 η οποία υπάρχει ήδη λόγω άλλης σύγκρουσης άρα δεν χρειάζεται να την ξανασχεδιάσουμε και β) R1(Α) και μετά εγγραφή W3(Α) άρα ακμή Τ1->Τ3 η οποία υπάρχει ήδη λόγω άλλης σύγκρουσης άρα δεν χρειάζεται να την ξανασχεδιάσουμε.
• Για το αντικείμενο B δεν υπάρχει κάποια σύγκρουση για αυτόν τον κανόνα.
• Για το αντικείμενο C υπάρχει κάποια σύγκρουση για αυτόν τον κανόνα.

4. Για κάθε περίπτωση στο S όπου η T_j εκτελεί μια πράξη εγγραφή_αντικ(Χ) μετά από μία πράξη εγγραφή_αντικ(Χ) που εκτελείται από την T_i δημιούργησε μία ακμή (T_i--> T_j) στον γράφο.

• Για το αντικείμενο Α έχουμε: α) W1(Α) και μετά εγγραφή W2(Α) άρα ακμή Τ1->Τ2 η οποία υπάρχει ήδη λόγω άλλης σύγκρουσης άρα δεν χρειάζεται να την ξανασχεδιάσουμε, β) W1(Α) και μετά εγγραφή W3(Α) άρα ακμή Τ1->Τ3 η οποία υπάρχει ήδη λόγω άλλης σύγκρουσης άρα δεν χρειάζεται να την ξανασχεδιάσουμε και γ) W2(Α) και μετά εγγραφή W3(Α) άρα ακμή Τ2->Τ3.
• Για το αντικείμενο B δεν υπάρχει κάποια σύγκρουση για αυτόν τον κανόνα.
• Για το αντικείμενο C υπάρχει κάποια σύγκρουση για αυτόν τον κανόνα.

5. Στον παρακάτω γράφο δεν υπάρχει κανένας κύκλος συνεπώς το χρονοπρόγραμμα S1 είναι σειριοποιήσιμο.

• Ο γράφος σειριοποιησιμότητας θα έχει την εξής μορφή: (Η παρακάτω εικόνα έχει αντίστροφη την ακμή Τ3->Τ1, καθώς πρέπει να είναι Τ1->Τ3, και θα διορθωθεί σύντομα.)

• Το ισοδύναμο σειριακό πρόγραμμα είναι το: Τ1 -> Τ2 -> Τ3.

Παράδειγμα 2 - Εφαρμογή Αλγορίθμου

S2: W2(Ζ), R5(Χ), W5(Ζ), W5(Χ), W4(Ζ), W4(Χ), R2(Χ), R3(Ζ), W3(Υ), W4(Υ)

1. Δημιουργούμε 4 κόμβους με ονόματα Τ2, Τ3, Τ4, Τ5 όσες και οι συναλλαγές του χρονοπρογράμματος S2.

2. Για κάθε περίπτωση στο S όπου η T_j εκτελεί μια πράξη ανάγνωση _αντικ(Χ) μετά από μία πράξη εγγραφή_αντικ(Χ) που εκτελείται από την T_i δημιούργησε μία ακμή (T_i--> T_j) στον γράφο.

• Για το αντικείμενο Ζ έχουμε: α) W2(Ζ) και μετά ανάγνωση R3(Ζ) άρα ακμή Τ2->Τ3 β) W5(Ζ) και μετά ανάγνωση R3(Ζ) άρα ακμή Τ5->Τ3 γ) W4(Ζ) και μετά ανάγνωση R3(Ζ) άρα ακμή Τ4->Τ3
• Για το αντικείμενο Χ έχουμε: α) W5(Χ) και μετά ανάγνωση R2(Χ) άρα ακμή Τ5->Τ2 β) W4(Χ) και μετά ανάγνωση R2(Χ) άρα ακμή Τ4->Τ2
• Για το αντικείμενο Υ δεν υπάρχει κάποια σύγκρουση για αυτόν τον κανόνα.

3.Για κάθε περίπτωση στο S όπου η T_j εκτελεί μια πράξη εγγραφή_αντικ(Χ) μετά από μία πράξη ανάγνωση _αντικ(Χ) που εκτελείται από την T_i δημιούργησε μία ακμή (T_i--> T_j) στον γράφο.

• Για το αντικείμενο X έχουμε: R5(Ζ) και μετά εγγραφή W4(Ζ) άρα ακμή Τ5->Τ4
• Για το αντικείμενο Z δεν υπάρχει κάποια σύγκρουση για αυτόν τον κανόνα.
• Για το αντικείμενο Υ δεν υπάρχει κάποια σύγκρουση για αυτόν τον κανόνα.

4. Για κάθε περίπτωση στο S όπου η T_j εκτελεί μια πράξη εγγραφή_αντικ(Χ) μετά από μία πράξη εγγραφή_αντικ(Χ) που εκτελείται από την T_i δημιούργησε μία ακμή (T_i--> T_j) στον γράφο.

• Για το αντικείμενο Ζ έχουμε: α) W2(Ζ) και μετά εγγραφή W5(Ζ) άρα ακμή Τ2->Τ5 β) W2(Ζ) και μετά ανάγνωση W4(Ζ) άρα ακμή Τ2->T4.
• Για το αντικείμενο Χ έχουμε: W5(Χ) και μετά εγγραφή W4(Χ) άρα ακμή Τ5->Τ4 η οποία υπάρχει ήδη λόγω άλλης σύγκρουσης άρα δεν χρειάζεται να την ξανασχεδιάσουμε.
• Για το αντικείμενο Y έχουμε: W3(Χ) και μετά εγγραφή W4(Χ) άρα ακμή Τ3->Τ4.

5. Το χρονοπρόγραμμα S2 δεν είναι σειριοποιήσιμο διότι υπάρχουν κατευθυνόμενες ακμές οι οποίες σχηματίζουν κύκλο. Μερικοί κύκλοι στον γράφο είναι 1) Τ2, Τ4 2) Τ2, Τ5 3)Τ2, Τ3, Τ4.

Ο γράφος σειριοποιησιμοτητας θα έχει την εξής μορφή (όπου παρατηρούμε τους κύκλους που σχηματίζονται):

Δεν έχει ισοδύναμα σειριακά χρονοπρογράμματα διότι έχει κύκλους.

Εξωτερικά links

• The Fundamentals of Database Systems, 5th Edition the use of precedence graphs is discussed in chapter 17, as they relate to tests for conflict serializability.
• basic precedence graph generator by Laurens Stötzel, University of Duisburg-Essen, Germany