UAS Manajemen Basis Data 2025

Soal 1a — Tiga operasi bersamaan pada B+ tree (25%)

Inti soal: B+ tree indeks NIM (Gambar 1: root A = [17, 50], node internal B = [25, 30, 39, 45] dan C = [55, 67, 80, 85], daun D–M). Tiga transaksi berjalan bersamaan: T1 mencari NIM 23, T2 menyisipkan 35, T3 menghapus 72. Jelaskan concurrency control, penanganan split/merge, dan isolasi.

Dari gambar, setiap daun maksimal 4 entri, jadi minimal 2 entri (order d = 2).

Jalur masing-masing operasi:

Transaksi	Jalur	Efek di daun
T1 search 23	A (17 ≤ 23 < 50) → B (23 < 25) → D [18, 20, 22, 23]	ketemu, tidak ada perubahan
T2 insert 35	A → B (30 ≤ 35 < 39) → F [31, 32]	F menjadi [31, 32, 35], masih muat, tidak split
T3 delete 72	A (72 ≥ 50) → C (67 ≤ 72 < 80) → K [70, 72]	K menjadi [70], underflow (< 2 entri)

Operasi pada daun B+ tree

1 / 4

Pencarian 23

T1 mengikuti A lalu B dan menemukan 23 di daun D.

A17 | 50

B25 | 30 | 39 | 45

D18 | 20 | 22 | 23

↺SebelumnyaPutarBerikutnyaLangkah

Kapasitas empat dan minimum dua entri diambil dari struktur daun pada gambar soal.

i. Bagaimana concurrency control mengatur ketiganya?

Struktur indeks dilindungi latch (kunci fisik jangka pendek) dengan protokol latch crabbing (lock coupling): saat turun dari parent ke child, latch child diambil dulu, lalu latch parent dilepas jika child “aman”.

• T1 (search): S-latch A → S-latch B → lepas A → S-latch D → lepas B → baca D → lepas D.
• T2 (insert): node aman untuk insert jika tidak penuh. Dengan pendekatan optimis, T2 turun dengan S-latch dan hanya mengambil X-latch di daun F. F belum penuh, jadi insert langsung selesai tanpa mengunci ancestor.
• T3 (delete): node aman untuk delete jika lebih dari setengah penuh. K tepat setengah (2 entri), jadi tidak aman: X-latch C harus ditahan selama T3 bekerja di K, karena C mungkin berubah. C sendiri berisi 4 kunci (aman), jadi X-latch pada root A bisa dilepas.

T1 dan T2 sama-sama melewati B, tetapi keduanya hanya memegang latch shared di B, sehingga tidak saling menunggu. T3 bekerja di subtree C yang terpisah. Ketiga operasi bisa berjalan paralel tanpa saling blokir.

ii. Jika terjadi split/merge

Delete 72 (benar-benar terjadi): K = [70] underflow. Cek sibling:

• Redistribusi dengan J [56, 58, 60] (punya 3 > 2 entri): pindahkan 60 ke K, sehingga J = [56, 58] dan K = [60, 70]. Separator di C berubah 67 → 60 (kunci terkecil di K). C = [55, 60, 80, 85].
• (Bisa juga dengan sibling kanan L: pinjam 81, K = [70, 81], separator 80 → 82.)
• Merge baru diperlukan jika tidak ada sibling yang bisa meminjamkan. Merge mengurangi satu kunci di parent dan bisa merambat ke atas.

Jika insert memicu split (misalnya F sudah penuh): F dipecah, kunci tengah naik ke B. B sendiri sudah penuh (4 kunci) dan ikut split, sehingga kunci naik ke A. Pada kasus ini T2 harus memegang X-latch dari A ke bawah (pessimistic crabbing) atau mengulang turun dengan X-latch setelah percobaan optimis gagal. Selama itu T1 yang ingin melewati B harus menunggu sampai split selesai, supaya tidak membaca node yang setengah terbagi.

iii. Isolasi transaksi

Latch hanya menjaga struktur fisik pohon dan dilepas segera. Isolasi logis butuh lock pada record/kunci yang ditahan sampai commit (Strict 2PL):

• T1 memegang S-lock pada NIM 23; T2 X-lock pada 35; T3 X-lock pada 72. Kunci berbeda, jadi tidak ada konflik.
• Untuk mencegah phantom (misal ada transaksi lain yang men-scan rentang NIM 30–40 saat 35 disisipkan), dipakai key-range / next-key locking: insert 35 harus mendapat lock pada kunci berikutnya (39). Jika ada scan yang memegang lock tersebut, insert menunggu sampai scan selesai.
• Tingkat isolasi (Read Committed, Repeatable Read, Serializable) menentukan seberapa lama dan seluas apa lock ini ditahan.

Soal 1b — Hashing untuk range selection? Salah.

Fungsi hash sengaja menyebarkan kunci secara acak ke bucket. NIM 30 dan 31 bisa jatuh di bucket yang berjauhan, sehingga query WHERE nim BETWEEN 30 AND 40 harus memeriksa semua bucket (setara full scan). Linear hashing maupun extendible hashing sangat bagus untuk equality search (nim = 23, rata-rata O(1) I/O), tetapi untuk range selection pilihan yang tepat adalah indeks terurut seperti B+ tree: cari batas bawah, lalu telusuri daun-daun yang saling tertaut.

Soal 2 — View serializable tapi tidak conflict serializable (25%)

Transaksi: T1 = R1(A), W1(A); T2 = W2(A); T3 = R3(A), W3(A).

Kuncinya adalah blind write W2(A) (menulis tanpa membaca). Jadwal:

$$S:\; R_1(A),\; W_2(A),\; R_3(A),\; W_1(A),\; W_3(A)$$

Bukti tidak conflict serializable. Pasangan operasi konflik (beda transaksi, item sama, minimal satu write):

Pasangan	Sisi
R1(A) … W2(A)	T1 → T2
W2(A) … R3(A)	T2 → T3
R3(A) … W1(A)	T3 → T1
W2(A) … W1(A)	T2 → T1
W1(A) … W3(A)	T1 → T3

Memuat diagram…

Bukti view serializable. Bandingkan dengan jadwal serial T1 → T2 → T3: R1, W1, W2, R3, W3.

Syarat view equivalence	Di S	Di serial T1, T2, T3
Pembacaan awal	R1(A) membaca nilai awal	sama
Sumber setiap read	R3(A) membaca hasil W2	sama
Penulis terakhir	W3(A)	sama

Ketiga syarat terpenuhi, jadi S view-equivalent dengan jadwal serial, berarti view serializable. W1(A) di S adalah dead write: nilainya tidak pernah dibaca dan langsung ditimpa W3, sehingga posisinya tidak memengaruhi hasil.

Soal 3 — Deadlock dari daftar tunggu (25%)

Memuat diagram…

a. Siapa yang deadlock?

Cari siklus di wait-for graph:

• T1 → T4 → T1: deadlock antara T1 dan T4.
• T2 → T7 → T6 → T2: deadlock antara T2, T6, T7.
• T3 menunggu T2. T3 tidak berada di siklus, jadi bukan penyebab deadlock, tetapi ikut terblokir selamanya selama siklus T2–T6–T7 belum diputus.
• T5 menunggu T8, dan T8 tidak menunggu siapa pun. T5 hanya menunggu biasa dan akan jalan setelah T8 selesai.

b. Penanganannya

Karena deadlock sudah terjadi, lakukan deteksi dan pemulihan: pilih satu korban di setiap siklus, abort dan rollback korban itu, lalu lepaskan semua lock-nya.

Kriteria memilih korban: biaya rollback terkecil (pekerjaan paling sedikit / paling muda), jumlah lock paling banyak yang bisa dibebaskan, dan berapa kali transaksi itu sudah pernah jadi korban (mencegah starvation).

• Siklus 1: abort T1 atau T4 (misalnya yang lebih muda).
• Siklus 2: abort T2 adalah pilihan menarik, karena sekaligus membebaskan T3 yang menunggu T2. Setelah rollback, T2 di-restart nanti.

Untuk ke depannya, deadlock bisa dicegah dengan timeout, protokol wait-die/wound-wait, atau urutan akuisisi lock yang seragam.

Soal 4 — Recovery ARIES (25%)

Daftar record lengkap dengan prevLSN dan undoNextLSN (CLR):

LSN	Record	prevLSN	undoNextLSN
10	begin checkpoint	–
20	T1 update A 100 → 200	–
30	T1 update B 50 → 250	20
40	T1 commit	30
60	T2 update C 300 → 400	–
80	T3 update D 10 → 60	–
90	T2 update E 500 → 600	60
100	T3 update F 700 → 800	80
110	crash
120	CLR T3: undo 100 (F 800 → 700)	100	80
130	CLR T3: undo 80 (D 60 → 10)	120	– (null)
140	crash
160	T4 update G 900 → 1000	–
170	T4 commit	160

Recovery setelah crash pertama (LSN 110)

Analysis (scan dari LSN 10):

• T1 commit di 40, lalu END, jadi bukan loser.
• ATT: T2 (lastLSN 90), T3 (lastLSN 100).
• DPT: A:20, B:30, C:60, D:80, E:90, F:100.

Redo dari recLSN terkecil = 20: redo 20, 30, 60, 80, 90, 100 (repeating history, termasuk update T1 yang sudah commit, karena belum tentu sudah tertulis ke disk).

Undo loser T2 dan T3. ToUndo = { 100 (T3), 90 (T2) }:

1. Undo 100, tulis CLR 120 (F → 700), undoNext = 80.
2. ARIES murni berikutnya mengambil LSN terbesar, yaitu 90 (T2). Log soal justru mencatat CLR 130 untuk LSN 80 (T3). Hasil akhirnya tetap benar karena undo antar transaksi berbeda boleh diselang-seling.
3. CLR 130 (D → 10) dengan undoNext = null, artinya T3 selesai di-undo (tinggal menulis END).
4. Crash terjadi lagi di LSN 140, sebelum END T3 dan sebelum undo T2.

Recovery setelah crash kedua (LSN 140)

Analysis: ATT = { T2: lastLSN 90, T3: lastLSN 130 (CLR, undoNext null) }. DPT sama seperti di atas.

Redo dari LSN 20: 20, 30, 60, 80, 90, 100, 120, 130 (CLR ikut di-redo).

Undo. ToUndo = { 130 (T3), 90 (T2) }:

1. 130 adalah CLR dengan undoNext null, jadi T3 sudah tuntas. Tulis END T3. Update 100 dan 80 tidak diulang: ini jaminan dari undoNextLSN.
2. Undo 90 (T2), tulis CLR (E 600 → 500), undoNext = 60.
3. Undo 60 (T2), tulis CLR (C 400 → 300), undoNext = null, lalu tulis END T2.

Record-record ini berada di antara LSN 140 dan 160 (soal tidak menampilkannya). Setelah recovery selesai, sistem berjalan normal: T4 update G (160) dan commit (170).

Nilai akhir: A = 200, B = 250 (T1 commit), C = 300, E = 500 (T2 dibatalkan), D = 10, F = 700 (T3 dibatalkan), G = 1000 (T4 commit).