UAS Manajemen Basis Data 2026

Data awal yang dipakai di seluruh soal: Stok[P4] = 20, Stok[P7] = 15, Peminjam[P9] = 100, Katalog[P6] = 50.

Soal 1 — Apakah 2PL membuat sistem “aman sepenuhnya”? (30%)

Inti soal: ada klaim bahwa karena sistem memakai Two-Phase Locking (2PL), semua transaksi pasti konsisten, tidak ada pembacaan stok yang salah, tidak ada data ganda, dan sistem bebas dari semua anomali konkurensi. Kita diminta menilai klaim itu dan membuktikannya dengan skenario.

Jawaban: klaim tersebut tidak sepenuhnya tepat. 2PL dasar memang menjamin jadwal conflict-serializable, tetapi ada beberapa hal yang tidak dijamin:

1. Dirty read & cascading abort. Pada 2PL dasar, transaksi boleh melepas lock (fase shrinking) sebelum commit. Transaksi lain bisa membaca nilai yang belum di-commit. Jika transaksi pertama kemudian abort, pembaca ikut harus dibatalkan (cascading rollback). Jika pembaca sudah commit, jadwalnya bahkan tidak recoverable.
2. Deadlock. 2PL sama sekali tidak mencegah deadlock.
3. Phantom. Lock pada item/halaman yang sudah ada tidak mengunci baris yang belum ada, sehingga query agregat (misalnya menghitung peminjam aktif) bisa memberi hasil berbeda bila ada insert di tengah transaksi.

Skenario pembuktian (dirty read pada 2PL dasar):

Langkah	T1: peminjaman 2 buku rak 4	T2: petugas cek stok rak 4
1	X-lock(P4), X-lock(P9) (fase growing selesai)
2	baca Stok[P4] = 20, tulis Stok[P4] = 18
3	unlock(P4) (fase shrinking dimulai, belum commit)
4		S-lock(P4), baca Stok[P4] = 18
5		menyetujui peminjaman lain berdasarkan stok 18, lalu commit
6	verifikasi anggota gagal, abort, Stok[P4] kembali 20

Jadwal ini mematuhi 2PL (T1 tidak pernah meminta lock setelah melepas lock), tetapi T2 sudah commit berdasarkan nilai 18 yang tidak pernah ada secara resmi. Inilah “anggota perpustakaan membaca data stok yang salah” yang dibantah oleh klaim tersebut.

Kenapa 2PL gagal di sini: 2PL hanya mengatur urutan akuisisi dan pelepasan lock, bukan kapan lock dilepas relatif terhadap commit. Perbaikannya:

• Strict 2PL: semua X-lock ditahan sampai commit/abort, sehingga mencegah dirty read dan cascading abort.
• Penanganan deadlock: timeout, deteksi lewat wait-for graph, atau pencegahan (wait-die / wound-wait).
• Predicate / index-range locking untuk mencegah phantom.

Soal 2 — Strict 2PL dan deadlock (35%)

Inti soal: lima transaksi dengan urutan permintaan lock yang direncanakan, lalu diberikan 10 langkah penjadwalan. Kita diminta (a) mencari kesalahan pada jadwal, (b) menentukan apakah terjadi deadlock, (c) menerapkan deadlock prevention.

Transaksi	Rencana akuisisi lock
T1	X(P4) → S(P9) → X(P6)
T2	S(P7) → X(P9) → S(P4)
T3	X(P7) → S(P6) → X(P4)
T4	S(P6) → X(P4) → S(P7)
T5	S(P4) → S(P7) → S(P9) → S(P6)

a. Analisis jadwal

Aturan kompatibilitas: S–S kompatibel, kombinasi lain dengan X tidak kompatibel. Transaksi yang sedang menunggu tidak bisa mengajukan permintaan berikutnya.

#	Langkah di soal	Pemegang saat itu	Seharusnya	Status
1	T1 X(P4) berhasil	P4 bebas	berhasil	✔
2	T5 S(P4) menunggu	T1 pegang X(P4)	menunggu	✔
3	T3 X(P7) berhasil	P7 bebas	berhasil	✔
4	T2 S(P7) menunggu	T3 pegang X(P7)	menunggu	✔
5	T4 S(P6) berhasil	P6 bebas	berhasil	✔
6	T1 S(P9) berhasil	P9 bebas	berhasil	✔
7	T2 X(P9) menunggu	—	tidak boleh terjadi	✘
8	T3 S(P6) menunggu	T4 pegang S(P6)	berhasil (S–S kompatibel)	✘
9	T4 X(P4) menunggu	T1 pegang X(P4)	menunggu	✔
10	T1 X(P6) menunggu	T4 (dan T3) pegang S(P6)	menunggu	✔

Kesalahan 1 (langkah 7): T2 masih terblokir di langkah 4 menunggu S(P7), dan di rencananya X(P9) baru diminta setelah S(P7) didapat. Transaksi yang sedang menunggu tidak bisa mengajukan permintaan lain, jadi langkah 7 harus dihapus; T2 tetap menunggu S(P7).

Kesalahan 2 (langkah 8): P6 hanya dipegang T4 dalam mode shared. Permintaan S(P6) oleh T3 kompatibel, jadi seharusnya berhasil. Setelah itu T3 melanjutkan ke rencana berikutnya, yaitu X(P4), dan menunggu T1.

b. Apakah terjadi deadlock? Ya.

Keadaan setelah jadwal diperbaiki:

• T1 memegang X(P4), S(P9), lalu menunggu X(P6) (dipegang S oleh T4 dan T3)
• T3 memegang X(P7), S(P6), lalu menunggu X(P4) (dipegang T1)
• T4 memegang S(P6), lalu menunggu X(P4) (dipegang T1)
• T2 menunggu S(P7) (dipegang T3); T5 menunggu S(P4) (dipegang T1)

Memuat diagram…

Ada siklus T1 → T4 → T1 dan T1 → T3 → T1, sehingga deadlock pasti terjadi. Karena Strict 2PL menahan X-lock sampai commit atau abort, dan tiap transaksi di siklus menunggu lock yang belum dilepas, tidak ada transaksi di siklus yang akan melepas lock. T2 dan T5 tidak berada di siklus, tetapi ikut tertahan selamanya karena menunggu transaksi yang ter-deadlock.

Terbentuknya deadlock

1 / 4

Lock awal

T1 memegang X(P4), T3 memegang X(P7), dan T4 memegang S(P6).

P4X: T1

P7X: T3

P6S: T4

↺SebelumnyaPutarBerikutnyaLangkah

Sisi berarti transaksi di asal menunggu pemegang lock di tujuan.

c. Deadlock prevention

Pakai timestamp, dengan asumsi TS(T1) < TS(T2) < … < TS(T5) (T1 paling tua).

Wait-die (yang tua boleh menunggu yang muda; yang muda yang meminta ke yang tua langsung die/abort, lalu restart dengan timestamp yang sama):

Langkah	Kejadian	Keputusan
2	T5 (muda) minta P4 dari T1 (tua)	T5 die
4	T2 (tua) minta P7 dari T3 (muda)	T2 menunggu
8	T3 minta S(P6), kompatibel dengan T4	diberikan
9	T4 (muda) minta X(P4) dari T1 (tua)	T4 die, S(P6) milik T4 dilepas
10	T1 (tua) minta X(P6) dari T3 (muda)	T1 menunggu
—	T3 (muda) minta X(P4) dari T1 (tua)	T3 die, X(P7) dan S(P6) dilepas

Setelah T3 abort, T1 mendapat X(P6) dan T2 mendapat S(P7). Semua sisi tunggu selalu dari tua ke muda, sehingga siklus tidak mungkin terbentuk.

Alternatif lain:

• Wound-wait: yang tua “melukai” (memaksa abort) yang muda yang menghalanginya; yang muda boleh menunggu yang tua.
• Conservative (static) 2PL: karena rencana lock setiap transaksi sudah diketahui, minta semua lock sekaligus di awal. Transaksi hanya mulai jika semua lock didapat, sehingga deadlock mustahil, dengan biaya konkurensi lebih rendah.
• Lock ordering: semua transaksi mengambil lock dalam urutan halaman yang sama (misalnya P4 → P6 → P7 → P9).

Soal 3 — ARIES dengan dua kali crash (35%)

Inti soal: log berisi update T1, T2, T3, checkpoint fuzzy di LSN 40, commit T2 di LSN 80, lalu crash setelah LSN 100. Saat recovery pertama, sistem sempat menulis CLR 110, 120, 130, lalu crash lagi. Kita diminta merekonstruksi DPT dan ATT, menjalankan Redo, dan menjalankan Undo untuk kedua crash.

Ringkasan log:

LSN	Trans	Page	PrevLSN	Isi
10	T1	P4	–	Stok[P4] 20 → 18
20	T2	P7	–	Stok[P7] 15 → 12
30	T1	P9	10	Peminjam[P9] 100 → 102
40				CHECKPOINT (fuzzy)
50	T2	P6	20	Katalog[P6] 50 → 48
60	T1	P4	30	Stok[P4] 18 → 16
70	T3	P7	–	Stok[P7] 12 → 10
80	T2		50	COMMIT
90	T3	P9	70	Peminjam[P9] 102 → 105
100	T1	P6	60	Katalog[P6] 48 → 45
110	T1	P6	CLR, undoNext = 60	undo 100: 45 → 48
120	T1	P4	CLR, undoNext = 30	undo 60: 16 → 18
130	T3	P9	CLR, undoNext = 70	undo 90: 105 → 102

a. Analysis: DPT dan ATT

Analysis dimulai dari checkpoint (LSN 40) dan memindai log ke depan.

Setelah crash pertama (log sampai LSN 100):

ATT	Status	lastLSN
T1	U (aktif)	100
T3	U (aktif)	90
T2	commit di LSN 80; ARIES menulis END, lalu T2 dikeluarkan dari ATT	—

DPT	recLSN
P4	10
P7	20
P9	30
P6	50 (masuk saat LSN 50)

Loser: T1 dan T3.

Setelah crash kedua (log sampai LSN 130): CLR juga memperbarui ATT.

ATT	Status	lastLSN	undoNext
T1	U	120 (CLR)	30
T3	U	130 (CLR)	70

DPT tetap P4:10, P7:20, P9:30, P6:50, karena halaman-halaman yang disentuh CLR sudah ada di DPT.

b. Redo

Redo dimulai dari recLSN terkecil di DPT = 10. Sebuah record update/CLR di-skip jika salah satu terpenuhi:

1. halamannya tidak ada di DPT, atau
2. LSN record < recLSN halaman itu, atau
3. pageLSN halaman di disk ≥ LSN record (perubahan sudah sampai di disk).

Crash pertama:

LSN	Keputusan	Alasan
10, 20, 30	redo	halaman ada di DPT, LSN ≥ recLSN, belum ada di disk
40	—	checkpoint, bukan update
50, 60, 70	redo	sama
80	—	commit, bukan update
90, 100	redo	sama

Crash kedua: semua record di atas di-redo lagi ditambah CLR 110, 120, 130 (ARIES repeating history: CLR juga di-redo). Dengan asumsi tidak ada flush, tidak ada record yang memenuhi kondisi skip. Sebagai contoh kapan skip terjadi: jika P7 sempat di-flush setelah LSN 70, pageLSN(P7) = 70, sehingga LSN 20 dan 70 di-skip karena kondisi 3.

c. Undo

Crash pertama. ToUndo = lastLSN para loser = { 100 (T1), 90 (T3) }. ARIES selalu mengambil LSN terbesar:

1. Undo 100 (T1, P6 45 → 48), tulis CLR 110, undoNext = prevLSN(100) = 60.
2. Berikutnya ToUndo = { 90 (T3), 60 (T1) }. Menurut ARIES murni yang diambil 90 dulu. Log di soal justru menulis CLR 120 untuk LSN 60 sebelum CLR 130 untuk LSN 90. Ini tetap menghasilkan state yang benar, karena undo antar transaksi berbeda boleh diselang-seling selama urutan undo dalam setiap transaksi tetap mundur.
3. CLR 120: undo 60 (T1, P4 16 → 18), undoNext = 30.
4. CLR 130: undo 90 (T3, P9 105 → 102), undoNext = 70.
5. Crash kedua terjadi di sini.

Crash kedua. Setelah redo, ToUndo = lastLSN dari ATT = { 130 (T3), 120 (T1) }.

1. 130 adalah CLR dan tidak di-undo. Lompat ke undoNext = 70 untuk T3.
2. 120 adalah CLR, lompat ke undoNext = 30 untuk T1. LSN 100 dan 60 tidak disentuh lagi: inilah fungsi UndoNextLSN, mencegah pekerjaan undo diulang.
3. ToUndo = { 70 (T3), 30 (T1) }. Undo 70 (T3, P7 10 → 12), tulis CLR 140, undoNext = null, lalu END T3 (150).
4. Undo 30 (T1, P9 102 → 100), tulis CLR 160, undoNext = 10.
5. Undo 10 (T1, P4 18 → 20), tulis CLR 170, undoNext = null, lalu END T1 (180).

(LSN 140–180 adalah penomoran yang kita pilih; soal tidak menampilkannya.)

Nilai akhir setelah recovery selesai:

Data	Nilai	Penjelasan
Stok[P4]	20	semua update T1 dibatalkan
Stok[P7]	12	update T2 (commit) bertahan, update T3 dibatalkan
Peminjam[P9]	100	update T1 dan T3 dibatalkan
Katalog[P6]	48	update T2 (commit) bertahan, update T1 dibatalkan