TESTING FOR SERIALIZABILITY

Pada saat mendesain skema kontrol konkurensi, kita harus tunjukan bahwa jadwal yang dibuat oleh skema tersebut adalah serializable. Terdapat metode simpel dan efisien untuk menentukan conflict serializability dari suatu jadwal.

Misalkan sebuah jadwal S. Kita dapat membuat suatu grafik langsung yang diberi nama grafik preseden (presedence graph). Grafik preseden terdiri dari sepasang G = (V,E), dimana V adalah serangkaian simpul dan E adalah serangkaian tepian / busur. Serangkaian simpul terdiri dari semua transaksi yang berperan serta di dalam penjadwalan. Serangkaian tepian / busur terdiri dari semua bentuk T_i -> T_j untuk masing – masing dari ketiga kondisi berikut :

§  T_i eksekusi write(Q) sebelum T_j eksekusi read(Q)

§  T_i eksekusi read(Q) sebelum T_j eksekusi write(Q)

§  T_i eksekusi write(Q) sebelum T_j eksekusi write(Q)

Jika bentuk T_i -> T_j ada di dalam grafik
preseden, maka di setiap jadwal S’ serial yang ekivalen ke jadwal S, T_i harus muncul sebelum T_j

                          

Sebagai contoh, grafik preseden untuk penjadwalan 1 digambarkan di (a), terdiri dari bentuk dasar T₁ -> T₂ , dimana semua instruksi T₁ dieksekusi sebelum instruksi pertama pada T₂ dieksekusi. Begitu juga sebaliknya untuk contoh yang digambarkan di (b).

Grafik preseden untuk jadwal 4, terdiri dari bentuk T₁ -> T₂ , karena T₁ mengeksekusi
read(A) sebelum T₂ mengeksekusi write(A). Grafik ini jg terdiri dari bentuk T₂ -> T₁ , karena T₂ mengeksekusi read(B) sebelum T₁ eksekusi write(B). Jika grafik preseden untuk S membentuk suatu lingkaran, maka jadwal S tidak conflict serializable. Jika sebaliknya, maka jadwal S conflict serializable