basis data lanjut

BASIS DATA LANJUT

Bab 5 – Pemrosesan Transaksikonsep dan teori

Universitas Al Azhar Indonesia

Endang R. Nizar

28 Mar 2011

1

2

T o p i k

Konsep Dasar Transaksi

Pemrosesan Transaksi

Penjadwalan (scheduling)Conflict serializability View serializability

3

Review:

Struktur sistem basis data secara menyeluruh

4

Komponen manajer basis data (Database Manager)

Program object code

Query processor

Catalog manager

Integrity checker

Command processor

Query optimizer

Authorization control

Transaction manager Scheduler

Accessmethod File manager

System buffer

Database & system catalog

Databasemanager

Buffer manager Recoverymanager

Datamanager

Menguji hak user

Bila user mempunyai hak akses, kendali diserahkan

ke command processor

Menguji operasi apakah memenuhi integrity

constraint

Menentukan strategi optimal untuk

melaksanakan query

Melaksanakan transaksi

Menjamin tidak terjadi konflik dalam hal

concurency

Menjamin basis data tetap dalam kondisi yang

konsisten dalam failureMentransfer data antara

main memory dan secondary storage

5

Konsep Transaksi

Sistem Basis Data Single-user vs Multi-userSingle-user – hanya dapat melayani 1 pengguna

pada satu saat.Multi-user – banyak pengguna dapat

memanfaatkan basisdata pada satu saat secara bersamaan.○ Contoh: bank, reservasi tiket pesawat, pasar

swalayan, bursa saham, dll.

Multi-user dimungkinkan karena adanya konsep multiprogramming:Single CPU bekerja secara interleavingMultiple CPU memungkinkan parallel processing

Konsep Transaksi Transaksi adalah satuan eksekusi program yang

mengakses dan mungkin memodifikasi berbagai data item. Contoh: transaksi untuk transfer $50 dari akun A ke akun B:

1. read(A)

2. A := A – 50

3. write(A)

4. read(B)

5. B := B + 50

6. write(B)

Dua masalah yang harus ditangani:Berbagai kemungkinan kegagalan, seperti kegagalan hardware

atau system crashes.Eksekusi beberapa transaksi secara bersamaan.

Konsep TransaksiContoh: transfer uang … (1)

Kebutuhan Atomicity Bila transaksi gagal setelah langkah 3 dan sebelum langkah 6 uang

akan ‘hilang’ basis data tidak konsisten Sistem harus menjamin bahwa eksekusi transaksi yang tidak tuntas tidak

boleh direfleksikan ke dalam basis data. Kebutuhan Durability — bila pengguna sudah diberi notifikasi

bahwa transaksi sudah lengkap, maka perubahan oleh transaksi itu harus tersimpan meskipun kemudian terjadi kegagalan software ataupun hardware.

transaksi untuk transfer $50 dari akun A ke akun B :1. read(A)2. A := A – 503. write(A)4. read(B)5. B := B + 506. write(B)


Kebutuhan Consistency: Jumlah akun A + B tidak boleh berubah dengan adanya eksekusi transaksi tersebut

Pengertian consistency secara umum:○ Eksplisit: integritas constraints seperti primary keys dan foreign keys○ Implisit: contoh integrity constraints – menjaga total balance dari semua akun

Transaksi harus melihat basis data yang konsisten. Selama eksekusi transaksi, mungkin basis data untuk sementara berada dalam keadaan

tidak konsisten. Bila eksekusi transaksi selesai, maka basis data harus berada dalam keadaan yang

konsisten.○ Logika transaksi yang salah dapat menyebabkan ketidakkonsistenan basis data.

transaksi untuk transfer $50 dari akun A ke akun B :1. read(A)2. A := A – 503. write(A)4. read(B)5. B := B + 506. write(B)


Kebutuhan Isolation — bila antara langkah 3 dan 6, ada transaksi lain T2 yang diijinkan untuk mengakses basis data yang sedang partially updated, maka T2 akan melihat basis data yang tidak konsisten.

Isolasi dapat dijamin bila semua transaksi dijalankan secara serial.

transaksi untuk transfer $50 dari akun A ke akun B:T1 T2

1. read(A)2. A := A – 503. write(A)

read(A), read(B), print(A+B)4. read(B)5. B := B + 506. write(B)

Konsep Transaksi Properti ACID Untuk menjaga integritas data, DBMS harus menjamin:

Atomicity – semua operasi dalam transaksi harus dilaksanakan atau tidak dilaksanakan sama sekali.

Consistency – operasi transaksi dalam isolasi menjamin basisdata tetap konsisten.

Isolation – meskipun beberapa transaksi dapat dilaksanakan secara bersama, setiap transaksi tidak tahu keberadaan transaksi lain dan hasil transaksi antara (intermediate result) harus tidak diketahui oleh transaksi lain.

Durability – sesudah transaksi selesai dengan sukses, perubahan yang terjadi harus bersifat menetap, meskipun terjadi kegagalan sistem.

11

Konsep Transaksi Pemrosesan Transaksi

Untuk menjamin konsistensi dibutuhkan: Pengendalian eksekusi bersama (concurrency) Mekanisma recovery

Parallel processingt1

t2 t3 t4

waktu

A A

B B

C

D

CPU1

CPU2

Interleaved processing

12


Transaksi adalah eksekusi program yang membentuk suatu unit logikal pemrosesan basisdata yang dilaksanakan secara lengkap atau tidak sama sekaliMencakup operasi insert, delete, modify, retrieveBila operasi dalam transaksi hanya mencakup retrieve tanpa

merubah data, maka disebut read-only transactionPembatas transaksi:

BEGIN TRANSACTION

…

…

END TRANSACTION

Semua operasi di antara kedua pembatas itu disebut satu transaksi

Operasi yang biasa terlibat dalam transaksi adalah;read_item (X)

write_item (X)

13


Langkah-langkah dalam read_item(X):Temukan address dari blok disk yang mengandung item

X.Copy isi blok disk ke dalam buffer dalam main memory.Copy item X dari buffer ke variabel program bernama X.

Langkah-langkah dalam write_item(X):Temukan address dari blok disk yang mengandung item

X.Copy isi blok disk ke dalam buffer dalam main memory.Copy item X dari variabel program bernama X ke lokasi

yang benar dalam buffer.Simpan blok yang sudah diubah isinya ke dalam disk.

14

Konsep Transaksi Eksekusi bersama (concurrent)

Beberapa transaksi dimungkinkan untuk berjalan bersamaan dalam suatu sistem. Keuntungan:Meningkatkan utilisasi prosesor dan disk, menuju

transaksi throughput lebih baik; 1 transaksi dapat menggunakan CPU sementara transaksi lain menulis ke dalam disk

Menekan rata-rata waktu respon untuk transaksi; transaksi pendek tidak perlu menunggu lama sebelum suatu transaksi yang panjang

Skema pengendalian concurrency – mekanisma untuk mencapai isolasi.Untuk mengendalikan interaksi antar transaksi yang

bersamaan agar konsistensi basisdata tidak terganggu.

15

Konsep Transaksi Mengapa perlu pengendalian eksekusi bersama Masalah lost

update – terjadi bila 2 transaksi mengakses data item yang sama sementara operasi interleaved dapat mengakibatkan nilai akhir data item tidak benar.

T1 T2

read_item(X)X := X – N

read_item(X)X := X + M

write_item(X)read_item(Y)

write_item(X)

Y := Y + Nwrite_item(Y)

waktu

Nilai item (X) salah karena perubahan oleh T1 ‘hilang’

(overwritten)

16

Konsep Transaksi Mengapa perlu pengendalian eksekusi bersama

Masalah temporary update (dirty read) – terjadi bila 1 transaksi merubah data item dan kemudian transaksi tersebut gagal (harus roll back), sementara item yang sudah berubah sudah digunakan oleh transaksi lain sebelum ia dikembalikan ke kondisi semula.

T1 T2

read_item(X)X := X – N write_item(X)

read_item(X)X := X + M write_item(X)

read_item(Y)waktu

Transaksi T1 gagal dan harus dikembalikan ke kondisi semula, sementara T2 sudah membaca

nilai temporary item X yang salah

17

Konsep Transaksi Mengapa perlu pengendalian eksekusi bersama Masalah incorrect

summary – terjadi bila suatu transaksi melakukan fungsi agregat sementara transaksi lain merubah sebagian tupel.

T1 T3

sum := 0read_item (A)sum := sum + A

read_item(X)X := X – N write_item(X)

read_item(X)sum := sum + X read_item(Y)sum := sum + Y

read_item(Y)Y := Y + N write_item(X)

waktu

Transaksi T3 membaca X setelah X – N dan membaca Y sebelum Y + N; summary salah

18

Konsep Transaksi Operasi dalam pemrosesan transaksi

Operasi yang berhubungan dengan transaksi:BEGIN TRANSACTION – menandai awal eksekusi

transaksiREAD atau WRITE – menunjukkan operasi baca/tulis yang

dieksekusi sebagai bagian transaksiEND TRANSACTION – menandai akhir eksekusi transaksiCOMMIT TRANSACTION – menunjukkan transaksi

selesai dengan sukses sehingga setiap perubahan dapat disimpan secara permanen dalam basisdata dan tidak ada undo (committed)

ROLLBACK (atau ABORT) – menunjukkan transaksi tidak selesai dengan sukses sehingga setiap perubahan harus dikembalikan ke kondisi awal atau undo

Konsep Transaksi Kondisi Transaksi (transaction states)

Active – kondisi awal, transaksi tetap di kondisi ini selama eksekusi Partially committed – setelah perintah terakhir dilaksanakan Committed – setelah transaksi selesai dilaksanakan dengan

sukses.

Failed – setelah diketahui bahwa eksekusi normal tidak dapat dilanjutkan

Aborted – setelah transaksi di-rollback dan basisdata dikembalikan ke posisi sebelum transaksi dimulai.

activeBEGIN TRANSACTION

partially committed

END TRANSACTION

failedABORT

ABORT

committedCOMMIT

terminated

Penjadwalan (scheduling) Schedule – serangkaian instruksi yang menunjukkan urutan

kronologi transaksi yang dieksekusi bersamaan (concurrent transactions) Jadwal dari sekumpulan transaksi harus mencakup

semua instruksi dalam transaksi yang terlibat. Tetap menjaga urutan instruksi sesuai transaksi

individual.

Transaksi yang sukses dieksekusi secara lengkap akan mempunyai instruksi commit sebagai perintah terakhirnya By default diasumsikan setiap transaksi akan

mengeksekusi instruksi commit sebagai langkah terakhir. Transaksi yang gagal melaksanakan eksekusi secara

lengkap akan mempunyai instruksi abort sebagai langkah terakhir.

21

Penjadwalan (scheduling) Contoh:

T1 mentransfer $50 dari A ke B dan T2 mentransfer 10% dari saldo A ke B.

T1 T2

read_item(A)A := A – 50write_item(A)read_item(B)B := B + 50write_item(B)

read_item(A)temp := A * 0.1A := A – tempwrite_item(A)read_item(B)B := B + tempwrite_item(B)

Schedule 1 – serial schedule

T1 T2



Schedule 2 – serial schedule

22

Penjadwalan (scheduling)

T1 T2

read_item(A)A := A – 50write_item(A)

read_item(A)temp := A * 0.1A := A – tempwrite_item(A)

read_item(B)B := B + 50write_item(B)

read_item(B)B := B + tempwrite_item(B)

Schedule 3 – non-serial schedule, tapi ekivalen dengan Schedule 1

T1 T2

read_item(A)A := A – 50

read_item(A)temp := A * 0.1A := A – tempwrite_item(A) read_item(B)

write_item(A)read_item(B)B := B + 50write_item(B)

B := B + tempwrite_item(B)

Schedule 4 – non-serial schedule, dengan operasi interleaving jumlah A + B tidak terjaga

23

Penjadwalan (scheduling) Jika eksekusi concurrent diserahkan

sepenuhnya kepada sistem operasi, ada banyak kemungkinan jadwal yang dilaksanakan sistem, termasuk jadwal yang menyebabkan ketidak-konsistenan basisdata.

Komponen concurrency-control dalam DBMS bertugas menjaga pelaksanaan jadwal agar ekivalen dengan jadwal serial dan menghasilkan kondisi basisdata yang konsisten.

24

Serializability

Asumsi dasar – setiap transaksi menjaga konsistensi basisdata. Setiap eksekusi serial dari transaksi menjaga konsistensi

basisdata. Suatu jadwal (bisa concurrent) disebut serializable bila

ia ekivalen dengan serial schedule. Bentuk lain dari serial schedule antara lain: Conflict serializability View serializability

Dalam contoh-contoh berikutnya jadwal disederhana-kan hanya menyangkut instruksi read_item dan write_item karena operasi antara keduanya bisa berupa operasi apapun.

25

Conflict serializability Instruksi Ii dan Ij dari transaksi Ti dan Tj – akan terjadi konflik jika dan

hanya jika ada item Q yang diakses oleh Ii dan Ij dan setidaknya ada satu instruksi Q menulis Ii = read(Q), Ij = read(Q) tidak ada konflik, tidak terpengaruh urutan

Ii = read(Q), Ij = write(Q) konflik urutan eksekusi Ii dan Ij menjadi penting

Ii = write(Q), Ij = read(Q) konflik

Ii = write(Q), Ij = write(Q) konflik

Secara intuitif, konflik antara Ii dan Ij mengakibatkan logikal urutan sementara. Jika Ii dan Ij berurutan dalam schedule dan tidak konflik, maka hasilnya akan konsisten meskipun urutannya diubah.

Schedule S dan S’ disebut conflict equivalent jika S dapat ditransformasi ke S’ melalui swapping urutan instruksi yang tidak menimbulkan konflik.

S disebut conflict serializable jika S adalah conflict equivalent terhadap sekelompok serial schedule.

Conflict serializability Schedule 3 dapat ditransformasi

ke Schedule 1, urutan schedule di mana T2 mengikuti T1 dengan urutan swap yang tidak menyebabkan konflik. Sehingga Schedule 3 adalah conflict serializable.

Schedule 5 – conflict serializable terhadap Schedule 1

Schedule 6 – conflict serializable terhadap Schedule 3

T1 T2

read_item(A)write_item(A)


read_item(B)write_item(B)


Write_item(A) pada T2 tidak konflik dengan read_item(B) pada T1 instruksi bisa di-swap

T1 T2


read_item(A)

read_item(B)

write_item(A)

write_item(B)


T1 T2


read_item(B)

read_item(A)

write_item(A)

write_item(B)


T1 T2


read_item(B)

read_item(A)

write_item(B)

write_item(A)


T1 T2


read_item(B)

write_item(B)

read_item(A)

write_item(A)


Conflict serializability

Schedule 7 – contoh schedule yang tidak conflict serializable:

Instruksi di atas tidak dapat di-swap untuk mendapat urutan serial schedule <T3, T4> atau urutan serial schedule <T4, T3>.

T3 T4

read_item(Q)

write_item(Q)

write_item(Q)

28

Pengujian conflict serializability – precedence graph

1. Untuk setiap transaksi Ti yang berpartisipasi dalam schedule S, buat node berlabel Ti dalam precedence graph.

2. Untuk setiap operasi dalam S di mana Tj mengeksekusi read_item(X) setelah Ti mengeksekusi write_item(X), buat garis yang menghubungkan Ti Tj

3. Untuk setiap operasi dalam S di mana Tj mengeksekusi write_item(X) setelah Ti mengeksekusi read_item(X), buat garis yang menghubungkan Ti Tj

4. Untuk setiap operasi dalam S di mana Tj mengeksekusi write_item(X) setelah Ti mengeksekusi write_item(X), buat garis yang menghubungkan Ti Tj

5. Schedule S disebut serializable jika dan hanya jika dalam precedence graph tidak terdapat lingkaran tertutup (cycle)

29

Contoh pengujian conflict serializability schedule

S: r1(X), r2(X), w1(X), r1(Y), w2(X), w1(Y)

T1 T2

X

X

Non-serializable schedule

A serializable schedule gives the benefits of concurrent execution without giving up any

correctness.

30

View Serializability S dan S’ adalah 2 schedule dengan kumpulan transaksi yang

sama. S dan S’ disebut view equivalent jika memenuhi 3 kondisi di bawah ini:

1. Untuk setiap data item Q, jika transaksi Ti membaca nilai awal Q dalam schedule S, maka transaksi Ti dalam schedule S’, juga harus membaca nilai awal Q.

2. Untuk setiap data item Q dalam Ti mengeksekusi read_item(Q) dalam S, dan nilai itu diproduksi oleh transaksi Tj (jika ada), maka transaksi Ti

dalam S’ juga harus membaca nilai Q yang diproduksi Tj.

3. Untuk setiap data item Q, transaksi (jika ada) yang melakukan write_item(Q) terakhir dalam Schedule S harus melakukan write_item(Q) terakhir di Schedule S’.

View Serializability

Dalam contoh terdahulu – Schedule 1 tidak view equivalent terhadap Schedule 2, Schedule 1 adalah view equivalent terhadap Schedule 3,

T1 T2



T1 T2



Schedule 1 Schedule 2 T1 T2

read_item(A)A := A – 50write_item(A)

read_item(A)temp := A * 0.1A := A – tempwrite_item(A)

read_item(B)B := B + 50write_item(B)

read_item(B)B := B + tempwrite_item(B)

Schedule 3

Schedule S adalah view serializable jika ia view equivalent terhadap suatu serial schedule.

32

Setiap schedule yang conflict serializable juga merupakan view serializable, tapi belum tentu sebaliknya.

View Serializability

Schedule 9 – adalah view serializable, karena ia view equivalent terhadap serial schedule <T3,T4, T6> karena instruksi read_item dilakukan oleh T3 pada kedua schedule dan T6 yang melakukan write_item terakhir, ada di kedua schedule.

Setiap view serializable yang bukan conflict serializable mempunyai blind writes.

T3 T4 T6

read_item(Q)

write_item(Q)

write_item(Q)

write_item(Q)

Schedule 9

33

Recoverability

Penting untuk menangani dampak dari kegagalan transaksi concurrent yang sedang berjalan.Jika Ti gagal karena sesuatu hal, sistem harus

melakukan undo untuk menjaga properti atomicity.

Pada sistem yang menyediakan eksekusi concurrent, perlu dijamin bahwa ○ Transaksi Tj yang memiliki ketergantungan terhadap Ti harus

dihentikan.○ Semua nilai harus dikembalikan ke kondisi awal.

34

Recoverability

Recoverability schedule – terjadi jika transaksi Tj membaca data item yang sebelumnya ditulis oleh transaksi Ti, sementara operasi commit Ti muncul sebelum operasi commit Tj.

Schedule 11 tidak recoverable jika T9 di-commit langsung sesudah read_item.

Jika T8 harus batal (abort), T9 mungkin sudah membaca (dan mungkin sudah dikirim ke pengguna) basisdata dalam kondisi tidak konsisten. Maka basisdata harus menjamin bahwa schedule bersifat recoverable.

T8 T9


read_item(A)

read_item(B)

35

Recoverability

Cascading rollback – kegagalan sebuah transaksi yang menyebabkan sekelompok transaksi dikembalikan ke kondisi asal (rollback) secara berjenjang. Contoh schedule di mana T10 gagal di mana T11 dan T12 harus di-rollback – bila belum ada transaksi yang di-commit, sehingga schedule recoverable.

Tidak terlalu disukai karena dapat menimbulkan undo untuk sejumlah transaksi yang signifikan.

T10 T11 T12

read_item(A)read_item(B)write_item(A)


read_item(A)

36

Penerapan isolasi

Schedule harus conflict serializable atau view serializable, dan recoverable, untuk menjamin konsistensi basisdata, dan tidak mengandung jenjang (cascade).

Untuk mencapai kondisi di atas, bisa diterapkan kebijakan untuk me-lock basisdata sementara suatu transaksi berjalan menyebabkan kinerja rendah.

basis data lanjut

Documents