Managemen transaksi
Eksekusi konkurensi- Pada eksekusi konkurensi, banyak transaksi dimungkinkan untuk diproses secara bersama – sama dalam suatu sistem.
- Memperbolehkan banyak transaksi untuk mengupdate data secara konkuren akan menyebabkan beberapa komplikasi dengan konsistensi data.
- Untuk memastikan bahwa konsistensi tetap terjaga dengan baik pada eksekusi konkuren, membutuhkan usaha yang lebih kuat. Akan lebih mudah jika transaksi berjalan secara serial.
- Meningkatkan utilitas disk dan prosesor
- Mengurangi rata – rata waktu respon transaksi
Dalam konkurensi dikenal dengan konsep penjadwalan (schedule) yang akan membantu
mengidentifikasi eksekusi agar konsistensi datanya tetap terjaga.
Sistem Basis Data harus mengontrol interaksi diantara transaksi konkuren supaya transaksi – transaksi tersebut tidak menghancurkan konsistensi basis datanya (data menjadi tidak konsisten).
Eksekusi konkurensi schedule
Penjadwalan / Schedule merupakan urutan yang mengindikasikan urutan kronologis instruksi
yang mana dari transaksi konkuren yang akan dieksekusi.
Sebuah jadwal merupakan bagian dari suatu transaksi yang harus terdiri dari semua instruksi yang ada di dalamnya.
Sebuah jadwal harus menjaga urutan instruksi yang muncul di setiap transaksi.
Misal T1 adalah transaksi transfer $50 dari A ke B, dan T2 adalah transfer 10% dari jumlah rekening A ke B. Penjadwalan berikut adalah pada transaksi serial, dimana T1 dulu yang diselesaikan baru diikuti oleh T2
Penjadwalan 1 di text book
Contoh penjadwalan selanjutnya, dengan transaksi yang sama, tetapidalam bentuk transaksi konkurensi, tapi ekivalen dengan penjadwalansebelumnya.
Penjadwalan 3 padaText book
Pada contoh penjadwalan yang pertama dan yang kedua, jumlahrekening A + B sebelum dan sesudah transaksi sama, tapi tidak dengan contoh penjawalan konkurensi berikut :
Penjadwalan 4 pada text book
Serializability
- Sistem basis data harus dapat mengontrol eksekusi konkurensi dari suatu transaksi untuk memastikan database tetap terjaga konsistensinya.
- Asumsi dasar, bahwa setiap transaksi harus tetap menjaga konsistensi database.
- Eksekusi secara serial pada suatu transaksi dapat menjaga database tetap konsisten.
- Sebuah jadwal (yang mungkin konkuren), serializable jika setara dengan penjadwalan secara serial. Pada bagian ini ada dua bentuk ekivalensi penjadwalan (Schedule Equivalence) : Conflict dan View Serializability.
- Pada serializability kita abaikan operasi selain dari instruksi read dan write, serta diasumsikan bahwa transaksi dapat melakukan perhitungan terhadap data di dalam buffer lokal diantara instruksi read dan write.
Conflict Serializability
Instruksi Ii dan Ij masing – masing dari transaksi Ti dan Tj , konflik jika dan hanya jika ada beberapa item data yang sama (Q) diakses secara bersama – sama baik oleh Ii dan Ij , serta setidaknya salah satu dari instruksi melakukan operasi write (Q).
1. Jika Ii = read(Q) dan Ij = read(Q), maka Ii dan Ij tidak konflik
2. Jika Ii = read(Q) dan Ij = write(Q), maka Ii dan Ij konflik
3. Jika Ii = write(Q) dan Ij = read(Q), maka Ii dan Ij konflik
4. Jika Ii = write(Q) dan Ij = write(Q), maka Ii dan Ij konflik
Secara intuitif, konflik diantara Ii dan Ij memaksakan perintah logika temporal diantara keduanya.
Jika Ii dan Ij merupakan instruksi dari transaksi berbeda dan tidak konflik, maka urutan instruksi Ii dan Ij dapat ditukar sehingga menghasilkan jadwal baru dengan hasil yang tetap sama.
Jika jadwal S dapat ditransformasikan menjadi jadwalan S’oleh serangkaian pertukaran instruksi yang non-konflik, maka bisa dikatakan S dan S’ adalah conflict equivalent.
Bisa dikatakan bahwa jadwal S adalah conflict serializable jika conflict equivalent terhadap penjadwalan serial.
Contoh penjadwalan yang tidak conflict serializable
T3 T4
read(Q)
write(Q)
write(Q)
Penjadwalan 3 di bawah bisa ditransformasikan ke penjadwalan 1, penjadwalan serial dimana T2 diikuti T1 , dengan serangkaian penukaran instruksi yang tidak konflik. Oleh karena itu penjadwalan di bawah ini conflict serializability.
Misalkan S dan S’ adalah dua jadwal dengan serangkaian transaksi yang
sama. S dan S’ adalah view equivalent.
S dan S’ adalah view equivalent jika memenuhi kondisi sebagai berikut :
1. Untuk masing – masing data item Q , jika transaksi Ti membaca inisialisasi nilai pada Q di dalam jadwal S, maka transaksi Ti yang ada di jadwal S’ juga harus membaca inisialisasi nilai pada Q.
2. Untuk masing – masing data item Q, jika transaksi Ti mengeksekusi read(Q) di dalam jadwal S, dan jika nilai yang dihasilkan oleh operasi write(Q) dieksekusi oleh transaksi Tj , maka operasi read(Q) pada transaksi Ti yang harus ada di jadwal S‘ juga membaca nilai Q yang dihasilkan oleh operasi write(Q) yang sama pada transaksi Tj
3. Untuk masing – masing data item Q, transaksi yang sampai ke tahap akhir operasi write(Q) di dalam jadwal S
Seperti yang terlihat, view serializability juga dilihat berdasarkan pada operasi read dan write saja
Sebuah jadwal S adalah view seralizable , setara dengan penjadwalan serial.
Setiap penjadwalan conflict serializable juga view serializable.
Penjadwalan di bawah ini (penjadwalan 9 di text book) adalah penjadwalan yang view serializable tapi tidak conflict serializable.
Penjadwalan di bawah (penjadwalan 9 di text book) menghasilkan outcome yang sama sebagai jadwal serial (T1, T2)
Recoverability
Recoverable Schedule – Jika transaksi Tj membaca sebuah item data yang sebelumnya ditulis oleh transaksi Ti , maka operasi commit Ti muncul sebelum operasi commit Tj .
Jadwal berikut (jadwal 11 di text book) tidak recoverable jika T9 commit segera setelah read
Jika T8 dibatalkan, maka T9 bisa jadi akan membaca state database inkonsisten. Maka dengan demikian database harus memastikan bahwa jadwal dapat dipulihkan jika terjadi sesuatu hal.
Cascading Rollback – kesalahan pada satu transaksi yang yang dapat berpengaruh pada serangkaian transaksi lainnya sehingga keseluruhan transaksi akan di-rollback.
Misalkan pada penjadwalan berikut dimana belum ada transaksi yang dicommit, sehingga jika terjadi masalah bisa dipulihkan.
Jika T10 transaksinya fail, maka T11 dan T12 juga harus di rollback. Jika tidak demikian, maka akan menyebabkan banyaknya pekerjaan yang tidak akan terselesaikan.
Cascadeless Schedule – cascading rollback tidak dapat terjadi, untuk setiap pasang
transaksi Ti dan Tj dimana Tj membaca sebuah item data yang sebelumnya ditulis oleh Ti dan operasi commit pada Ti muncul sebelum operasi read pada Tj.
Setiap cascadeless schedule juga dapat dipulihkan (recoverable);
Testing 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 Ti -> Tj untuk masing –
masing dari ketiga kondisi berikut :
1. Ti eksekusi write(Q) sebelum Tj eksekusi read(Q)
2. Ti eksekusi read(Q) sebelum Tj eksekusi write(Q)
3. Ti eksekusi write(Q) sebelum Tj eksekusi write(Q)
Jika bentuk Ti -> Tj ada di dalam grafik preseden, maka di setiap jadwal S’ serial yang ekivalen ke jadwal S, Ti harus muncul sebelum Tj.
Sebagai contoh, grafik preseden untuk penjadwalan 1 digambarkan di (a), terdiri dari bentuk dasar T1 -> T2 , dimana semua instruksi T1 dieksekusi sebelum instruksi pertama pada T2 dieksekusi. Begitu juga sebaliknya untuk contoh yang digambarkan
di (b).
Grafik preseden untuk jadwal 4, terdiri dari bentuk T1 - > T2 , karena T1 mengeksekusi read(A) sebelum T2 mengeksekusi write(A). Grafik ini jg terdiri dari bentuk T2 -> T1 , karena T2 mengeksekusi read(B) sebelum T1 eksekusi write(B).
Jika grafik preseden untuk S membentuk suatu lingkaran, maka jadwal S tidak conflict serializable. Jika sebaliknya, maka jadwal S conflict serializable.
