Testing for serializability

Serializability : pengontrolan secara konkurensi kepada kebenaran dari kriteria yang membutuhkan eksekusi konkuren dari transaksi harus ekuivalen terhadap efek dari eksekusi serial transaksi tersebut.

Tujuan dari protokol kontrol concurrency adalah menjadwalkan transaksi dengan suatu cara untuk menghindari saling mempengaruhi/mengganggu satu dengan yang lain. Hal yang paling umum dilakukan adalah menjalankan satu transaksi dalam satu waktu, tetapi tujuan dari multi user DBMS adalah memaksimalkan tingkat concurrency atau parallelism dalam sistem, sehingga traksaksi-transaksi dapat dieksekusi secara parallel tanpa mengganggu transaksi lainnya. Serializability mengidentifikasi eksekusieksekusi dari transaksi dijamin untuk kepastian konsistensi.

-          Penjadwalan (Schedule) adalah Serangkaian operasi dari sekumpulan transaksi konkuren yang menjaga perintah dari operasi-operasi dalam setiap transaksi individual.

-          Serial Schedule adalah penjadwalan yang dilakukan dimana operasi-operasi disetiap transaksi dieksekusi secara berurutan tanpa terjadi penyelakan operasi dari transaksi lainnya. Dalam eksekusi serial tidak akan ada interferensi antar transaksi, tetapi tidak menjamin hasil dari keseluruh eksekusi serial dari himpunan transaksi akan sama/identik.

-          Nonserial Schedule adalah penjadwalan yang dilakukan dimana operasi-operasi dari sekumpulan transaksi konkuren saling berselakan (interleaved).

Tujuan dari serializability adalah menemukan nonserial schedule yang memungkinkan transaksi untuk mengeksekusi secara konkuren tanpa mengganggu/interferen yang lainnya dan menghasilkan state database yang dapat dihasilkan oleh eksekusi serial. Dengan kata lain, jika terdapat nonserial schedule yang ekuivalen dengan beberapa serial schedule disebut dengan serializability.

Dalam serializability, perintah operasi pembacaan/penulisan sangat penting:

-          Jika terdapat dua transaksi hanya membaca data item, maka tidak akan terjadi konflik dan perintah tidak diperlukan.

-           Jika terdapat dua transaksi yang membaca atau menulis data item yang terpisah, maka tidak akan terjadi konfilk dan perintah tidak diperlukan.

-           Jika satu transaksi menuliskan data item dan transaksi lainnya membaca atau menulis data item yang sama, maka perintah eksekusi diperlukan.

Contoh konflik dalam Serializability

a.       nonserial schedule S1

b.      nonserial schedule S2, ekuvalen dengan S1

c.       serial schedule S3, ekuivalen dengan S1dan S2

Schedule S3 merupakan serial schedule dan ketika S1 dan S2 ekuivalen dengan S3, maka S1 dan S2 merupakan serializability schedule. Jenis serializability yang seperti ini dikenal sebagai conflict serializability, yaitu memerintahkan operasi yang saling bertentangan dengan suatu cara sama seperti eksekusi serial.

Dengan constrained write rule (transaksi yang mengubah data item berdasarkan padanilai awal, yang pertama kali dibaca), menggunakan precedence (or serializability) graph untuk memeriksa serializability. Precedence Graph merupakan directed graph G = (N,E) yang berisi dari himpunan node N dan edge E, sbb :

Buat node untuk setiap transaksi

-          Buat edge penghubung Ti -> Tj, jika Tj membaca nilai dari item yang ditulis oleh Ti

-          Buat edge penghubung Ti -> Tj, jika Tj menuliskan nilai ke item setelah dibaca oleh Ti

-          Buat edge penghubung Ti -> Tj, jika Tj menuliskan nilai ke item setelah ditulis oleh Ti

Jika edge Ti -> Tj terdapat dalam precedence graph untuk S, kemudian terdapat serial schedule S’ yang ekuivalen dengan S, maka Ti harus ditampilkan sebelum Tj. Jika precedence graph mengandung siklus schedule maka tidak akan terjadi conflict serializability.

Contoh - Non-conflict serializable schedule:

-          T9 memindahkan £100 dari variabel balx ke variabel baly.

-          T10 mengurangi kedua variabel tersebut sebesar 10%.

-          Precedence grah untuk schedule ini memiliki siklus, sehingga bukan merupakan conflict serializability.

View Serializability

Terdapat beberapa jenis serializability yang menawarkan definisi yang tidak terlalu kaku (less stringent definition) dari schedule ekuivalen dari pada conflict serializability. Definisi yang lebih sedikit batasannya disebut dengan view schedule. Dua schedule S1 dan S2 disebut equivalent jika:

-          Untuk setiap data item x, jika Ti membaca nilai awal dari x dalam S1, Ti juga harus membaca nilai awal dari x dalam S2.

-          Untuk setiap pembacaan atas x oleh Ti dalam S1, jika nilai dibaca oleh x dituliskan oleh Tj, Ti juga harus membaca nilai dari x yang dihasilkan oleh Tj dalam S2.

-          Untuk setiap data item x, jika penulisan terskhir dari x ditampilkan oleh Ti dalam S1, beberapa transaksi harus menampilkan penulisan akhir dari x dalam S2.

Schedule dikatakan view serializable jika view tersebut ekuivalen dengan serial schedule. setiap conflict serializable schedule merupakan view serializable, walaupun kebalikannya tidak benar. Dapat menampilkan bahwa view serializable schedule yang tidak conflict serializable terdiri dari satu atau lebih blind writes.

RECOVERABILITY

-          Serializability mengidentifikasikan schedule yang memelihara konsistensi database, diasumsikan tidak ada transaksi yang gagal. Juga memeriksa recoverability dari transaksi dalan schedule. Jika transaksi gagal, atomicity membutuhkan akibat dari transaksi yang harus diselesaikan.

-          Durability state ketika transaksi commit, perubahannya tidak dapat diselesaikan (tanpa menjalankan yang lain, penggantian, transaksi).

-          Recoverable Schedule merupakan schedule yang setiap pasang dari transaksi Ti dan Tj, jika Tj membaca sebuah data item sebelum dituliskan oleh Ti, maka operasi commit dari Ti mendahului operasi commit dari Tj.