Transaction Management (part 5) – Test Conflict Serializability with Precedence Graph

Precedence Graph atau sebutan lainnya Serialization Graph, biasanya digunakan untuk menguji Conflict Serializability dari sebuah schedule.

Berikut ini contoh Precedence Graph. Tapi belum tentu hasil akhir dari grafik akan seperti ini. Pada artikel ini kita akan belajar bagaimana membuat grafik ini dan apa hubungan dengan Conflict Serializability.

Pertama setiap transaksi kita akan buat node (lingkaran) seperti gambar (T9, T10). Setelah itu akan ada gambar garis pada setiap kejadian tertentu. Berikut ini kejadian-kejadian yang akan membuat kita menggambar garis. Kita akan menggambar garis saat ada operasi konflik antara transaksi.

1. Operasi read(x) dan write(x). Jika transaksi T10 mengeksekusi read(x) setelah T9 mengeksekusi write(x) maka gambarlah garis dari T9 ke T10.
2. Operasi write(x) dan read(x). Jika transaksi T10 mengeksekusi write(x) setelah T9 mengeksekusi read(x) maka gambarlah garis dari T9 ke T10.
3. Operasi write(x) dan write(x). Jika transaksi T10 mengeksekusi write(x) setelah T9 mengeksekusi write(x) maka gambarlah garis dari T9 ke T10.

Jika hasil dari grafik tidak terjadi siklus maka conflict serializable yang artinya schedule bisa dibuat serial. Kita akan lihat 2 contoh:

S : r1(x) r1(y) w2(x) w1(x) r2(y)

1. Kita buatkan node untuk setiap transaksi
2. Untuk operasi yang konflik r1(x) w2(x), dimana r1(x) terjadi sebelum w2(x), gambar garis dari T1 ke T2.
3. Untuk operasi yang konflik w2(x) w1(x), dimana w2(x) terjadi sebelum w1(x), gambar garis dari T2 ke T1.

Dari grafik yang terakhir terlihat siklus T1 dan T2, kita dapat simpulkan bahwa schedule ini tidak conflict serializable. Mari kita coba menyimpulkan jadwal serial dari grafik ini menggunakan pengurutan topologi.

Garis T1–> T2 mengatakan bahwa T1 harus datang sebelum T2 dalam urutan linier.
Garis T2 -> T1 memberi tahu bahwa T2 harus berada sebelum T1 dalam urutan linier.
Jadi, kami tidak dapat memprediksi urutan tertentu (saat grafik berbentuk siklik). Oleh karena itu, tidak ada jadwal serial yang dapat diperoleh dari grafik ini.

Kita coba schedule yang lain:

S1: r1(x) r3(y) w1(x) w2(y) r3(x) w2(x)

Kalian bisa coba sendiri untuk membuat Precedence Graph sendiri sebelum melihat gambar.

Karena grafiknya tidak terjadi siklus, jadwal konflik dapat diserialkan. Melakukan Pengurutan Topologis pada grafik ini akan memberi kita kemungkinan jadwal serial yang bertentangan dengan jadwal S1.

Pada Topological Sort, pertama kita pilih node dengan indegree 0, yaitu T1. Ini akan diikuti oleh T3 dan T2.

Jadi, S1 adalah conflict serializable karena konflik tersebut setara dengan jadwal serial T1 T3 T2.