Problem Set: Concurrency Control (Paket C - Advanced)

Mata Pelajaran: Sistem Basis Data

Estimasi Waktu: 120 Menit

Total Nilai: 100 Poin

Petunjuk Umum

Jawablah soal teori dengan ringkas dan tepat.
Untuk soal studi kasus, sertakan tracing langkah demi langkah.
Gunakan matriks kompatibilitas dan aturan protokol yang sesuai dengan materi pendukung.

SOAL 1: Lock-Based & Compatibility Matrix (20 Poin)

A. Teori: Matriks Kompatibilitas (10 Poin)

Lengkapilah tabel matriks kompatibilitas berikut dengan memberikan tanda (v) jika kompatibel dan (x) jika tidak kompatibel. Berikan satu kalimat penjelasan mengapa kunci SIX memiliki sifat tersebut terhadap IX.

Status	IS	IX	S	SIX	X
IS
IX
S
SIX
X

Penjelasan SIX vs IX: __________________________________________________________________

B. Studi Kasus: Rigorous 2PL dengan Upgrade Lock (10 Poin)

Diberikan urutan kedatangan instruksi: $R_{1} (A); R_{2} (B); R_{1} (B); W_{2} (B); W_{1} (A); C_{1}; C_{2};$ .

Gunakan protokol Rigorous 2PL dengan aturan Transaction Manager:

Transaksi meminta kunci $S L$ saat read dan melakukan Upgrade ke $X L$ saat write.
Jika terblokir, instruksi masuk Blocking Queue. Saat bebas, antrian diprioritaskan.

Pertanyaan: Tuliskan schedule eksekusi lengkap (Lock, Op, Unlock) dan status Blocking Queue.

SOAL 2: Tree Protocol & Path Analysis (20 Poin)

A. Teori: Isian Terstruktur (5 Poin)

Jelaskan perbedaan kondisi yang menyebabkan sebuah transaksi di-abort pada protokol Tree Protocol dibandingkan dengan Basic 2PL. Jika Tree Protocol tidak mengenal fase shrinking, apakah ia masih menjamin Conflict Serializability? Mengapa?

B. Studi Kasus: E-Learning Hierarchy (15 Poin)

Perhatikan struktur hirarki sistem E-Learning berikut:

graph TD
    DB[E-Learning_DB] --> C1[Course_SBD]
    DB --> C2[Course_Alpro]
    C1 --> M1[Modul_1]
    C1 --> M2[Modul_2]
    M1 --> Q1[Kuis_1]
    M1 --> Q2[Kuis_2]
    M2 --> Q3[Kuis_3]
    C2 --> M3[Modul_3]

Pertanyaan:

i. Transaksi T1 perlu mengubah Kuis_1 dan Kuis_3. Tuliskan urutan $l oc k - X$ dan $u n l oc k$ yang paling efisien agar T1 tidak mengunci seluruh database terlalu lama.

ii. Transaksi T2 mulai setelah T1 melakukan $l oc k - X$ pada Course_SBD. T2 ingin membaca Kuis_2. Tunjukkan pada node mana T2 akan tertahan (wait).

SOAL 3: Multiple Granularity & Lock Escalation (20 Poin)

A. Teori: Analisis Trade-off (5 Poin)

Dalam konteks Multiple Granularity, jelaskan fenomena Lock Escalation. Kapan sebuah DBMS sebaiknya menaikkan granularitas kunci dari level Record ke level Table?

B. Studi Kasus: Operasi Batch vs Point (15 Poin)

Hirarki: DB → Table → Page → Record.

T3: “Menghitung total nilai seluruh mahasiswa pada tabel Nilai (Read All) dan memberikan bonus 5 poin pada record mahasiswa dengan ID = 135.”

T4: “Mengubah alamat mahasiswa dengan ID = 140 pada tabel yang sama.”

Pertanyaan:

i. Tentukan daftar kunci niat ( $I S, I X, S I X, S, X$ ) untuk T3 agar pengerjaan efisien.

ii. Jika T3 memegang kunci pada level tabel, apakah T4 dapat mengeksekusi operasinya secara paralel? Sertakan alasan berdasarkan jenis kunci yang dipegang.

SOAL 4: Non-Locking Protocols & Obsolete Writes (20 Poin)

A. Teori: Fase Validation (5 Poin)

Pada Validation-Based Protocol, jelaskan apa yang terjadi jika sebuah transaksi $T_{i}$ berada pada Validation Phase dan ditemukan bahwa $F ini s h (T_{j}) > St a r t (T_{i})$ sementara $W S (T_{j}) \cap RS (T_{i}) \neq = \emptyset$ .

B. Studi Kasus: Thomas’ Write Rule Challenge (15 Poin)

Schedule: $R_{1} (A); R_{2} (A); W_{2} (A); W_{1} (A); C_{2}; C_{1};$ .

Asumsikan $TS (T_{1}) = 10$ dan $TS (T_{2}) = 20$ .

Pertanyaan:

i. Lakukan tracing menggunakan Basic Timestamp Ordering. Manakah transaksi yang gagal?

ii. Lakukan tracing menggunakan Thomas’ Write Rule.

SOAL 5: MVCC & Snapshot Isolation Anomaly (20 Poin)

A. Teori: Write Skew Analysis (5 Poin)

Jelaskan mengapa Snapshot Isolation (SI) yang menggunakan logika First-Committer Wins tidak dapat mencegah anomali Write Skew. Berikan satu contoh skenario dunia nyata di mana Write Skew merugikan konsistensi data.

B. Studi Kasus: Multiversion Tracing (15 Poin)

Data awal: $X_{0} (W - TS = 0, R - TS = 0)$ . Transaksi:

$T_{5} (TS = 5) : R (X), W (X)$
$T_{6} (TS = 6) : R (X)$
$T_{7} (TS = 7) : W (X)$

Urutan Eksekusi:

$R_{5} (X)$
$R_{6} (X)$
$W_{7} (X)$
$W_{5} (X)$

Pertanyaan:

Tuliskan versi data yang tercipta, nilai $R - TS$ dan $W - TS$ setiap versi, serta transaksi mana yang harus abort menurut protokol Multiversion Timestamp Ordering.

# Kunci Jawaban & Pembahasan Paket C

Solusi 1: Locking

A. Matriks Kompatibilitas:

Status IS IX S SIX X
IS v v v v x
IX v v x x x
S v x v x x
SIX v x x x x
X x x x x x

Penjelasan: SIX dan IX tidak kompatibel karena SIX sudah memegang S-lock pada seluruh sub-pohon, sedangkan IX berniat melakukan penulisan yang bisa merusak konsistensi pembacaan SIX.

B. Tracing 2PL:

$S L_{1} (A); R_{1} (A);$

$S L_{2} (B); R_{2} (B);$

$S L_{1} (B); R_{1} (B);$ (Kompatibel dengan $S L_{2}$ )

$W_{2} (B) :$ Minta $X L_{2} (B)$ . Konflik karena $S L_{1} (B)$ . T2 WAIT. Antrian $T_{2} : [W_{2} (B), C_{2}]$ .

$W_{1} (A) :$ Minta $X L_{1} (A)$ . Karena $T_{1}$ adalah pemegang tunggal, Upgrade Berhasil. $X L_{1} (A); W_{1} (A);$

$C_{1} : C o mmi t; U L_{1} (A); U L_{1} (B);$

Bebas: $T_{2}$ bangun. $X L_{2} (B); W_{2} (B); C_{2}; U L_{2} (B);$

Solusi 2: Tree Protocol

A. Teori: Pada Tree Protocol, transaksi tidak pernah di-abort karena deadlock (bebas deadlock). Ia menjamin Conflict Serializability karena urutan penguncian dari atas ke bawah memaksa urutan eksekusi yang konsisten secara topologi.

B. Tracing:

i. T1: $l oc k - X (D B) \to l oc k - X (C 1) \to l oc k - X (M 1) \to l oc k - X (Q 1) \to l oc k - X (C 2) \to l oc k - X (M 3) \to l oc k - X (Q 3)$ . (Pelepasan kunci bisa dilakukan segera setelah anak dikunci).

ii. T2 akan tertahan pada node C1 (Course_SBD) karena $T_{1}$ memegang $l oc k - X$ pada node tersebut dan $T_{2}$ harus melewati node tersebut untuk sampai ke Q2.

Solusi 3: Multiple Granularity

A. Teori: DBMS melakukan eskalasi ketika jumlah kunci level rendah (misal 5000 record) terlalu banyak sehingga membebani memori Lock Manager.

B. Tracing:

i. T3: $I X (D B), S I X (T ab l e_N i l ai), I X (P a g e_I D 135), X (R ec_I D 135)$ .

ii. T4 membutuhkan $I X$ pada level tabel untuk sampai ke $R ecor d_I D 140$ . Karena $T_{3}$ memegang $S I X$ , dan $S I X$ vs $I X$ adalah KONFLIK, maka T4 WAIT.

Solusi 4: Timestamping

i. Basic TO: $W_{1} (A)$ datang saat $R - TS (A) = 20$ (dari $T_{2}$ ) dan $W - TS (A) = 20$ (dari $T_{2}$ ). Karena $TS (T_{1}) = 10 < 20$ , maka T1 ABORT.

ii. Thomas’ Write Rule: $W_{1} (A)$ diabaikan (ignored) karena $TS (10) < W - TS (20)$ . Namun, karena $TS (10) < R - TS (20)$ , Transaksi T1 tetap perlu abort. Nilai akhir $W - TS (A)$ tetap 20.

Solusi 5: MVCC & SI

A. Teori: SI hanya mengecek irisan Write Set. Write Skew terjadi ketika dua transaksi membaca data yang sama namun menulis ke item data yang berbeda (irisan WS kosong), sehingga keduanya commit namun melanggar batasan integritas global.

B. Tracing MVCC:

$R_{5} (X) :$ Baca $X_{0}, R - TS (X_{0}) = 5$ .

$R_{6} (X) :$ Baca $X_{0}, R - TS (X_{0}) = 6$ .

$W_{7} (X) :$ Buat $X_{7} (W - TS = 7, R - TS = 7)$ .

$W_{5} (X) :$ Cek $TS (5) < R - TS (X_{0}) = 6$ . Karena versi yang dibaca $T_{5}$ sudah dibaca transaksi lebih muda, T5 ABORT.

Status	IS	IX	S	SIX	X
IS	v	v	v	v	x
IX	v	v	x	x	x
S	v	x	v	x	x
SIX	v	x	x	x	x
X	x	x	x	x	x

Tips Advanced:

Hati-hati pada SIX lock, ia sering menjadi penjebak dalam soal paralelisme tabel.
Pada MVCC, selalu perhatikan $R - TS$ pada versi yang spesifik dibaca oleh transaksi tersebut.

IF Notes

Explorer

Latihan UAS IF3140-CC C

Problem Set: Concurrency Control (Paket C - Advanced)

Petunjuk Umum

SOAL 1: Lock-Based & Compatibility Matrix (20 Poin)

SOAL 2: Tree Protocol & Path Analysis (20 Poin)

SOAL 3: Multiple Granularity & Lock Escalation (20 Poin)

SOAL 4: Non-Locking Protocols & Obsolete Writes (20 Poin)

SOAL 5: MVCC & Snapshot Isolation Anomaly (20 Poin)

Solusi 1: Locking

Solusi 2: Tree Protocol

Solusi 3: Multiple Granularity

Solusi 4: Timestamping

Solusi 5: MVCC & SI

Graph View

Table of Contents

Backlinks