Back to Latihan UAS IF3140

Problem Set: Concurrency Control (Paket A)

Mata Pelajaran: Sistem Basis Data

Estimasi Waktu: 120 Menit

Total Nilai: 100 Poin

Tujuan Pembelajaran

Setelah menyelesaikan problem set ini, mahasiswa diharapkan dapat:

Melakukan tracing perolehan kunci (locks) pada protokol Two-Phase Locking (Basic, Strict, dan Rigorous).
Mengimplementasikan Tree Protocol pada struktur data hirarkis.
Menganalisis perolehan Intention Locks pada protokol Multiple Granularity.
Menentukan validitas schedule berdasarkan Timestamp Ordering dan Validation-Based Protocol.
Mengevaluasi nasib transaksi pada protokol Multiversion dan Snapshot Isolation (First-Committer Wins).

SOAL 1: Two-Phase Locking Protocols (20 Poin)

Diberikan urutan masuk instruksi dari 3 buah transaksi ( $T_{1}, T_{2}, T_{3}$ ) ke DBMS sebagai berikut:

Schedule S: $R_{1} (A); R_{2} (B); W_{1} (A); R_{3} (C); R_{1} (B); W_{3} (C); W_{2} (B); W_{1} (B); C_{1}; C_{2}; C_{3};$

Asumsikan:

$R_{y} (X)$ dan $W_{y} (X)$ adalah operasi read dan write transaksi $T_{y}$ terhadap data $X$ .
DBMS menggunakan automatic acquisition of locks.
Tidak ada skema pencegahan deadlock (jika terjadi deadlock, instruksi terhenti).

Pertanyaan:

Tuliskan schedule eksekusi lengkap dengan perolehan kunci ( $S L_{y}$ : Shared Lock, $X L_{y}$ : Exclusive Lock, $U L_{y}$ : Unlock) untuk protokol berikut:

a. Basic Two-Phase Locking (2PL).

b. Strict Two-Phase Locking (Strict 2PL).

c. Rigorous Two-Phase Locking (Rigorous 2PL).

Catatan: Tunjukkan pada langkah mana transaksi harus menunggu (WAIT) jika terjadi konflik.

SOAL 2: Tree Protocol (15 Poin)

Diberikan partial ordering item data dalam struktur pohon sebagai berikut:

graph TD
    DB[Database] --> TA[Table_A]
    DB --> TB[Table_B]
    TA --> PA1[Page_A1]
    TA --> PA2[Page_A2]
    TB --> PB1[Page_B1]
    PA1 --> R1[Rec_1]
    PA1 --> R2[Rec_2]
    PA2 --> R3[Rec_3]
    PB1 --> R4[Rec_4]

i. Prosedur Lock/Unlock:

Tuliskan urutan instruksi $l oc k - X$ dan $u n l oc k$ yang valid sesuai Tree Protocol untuk transaksi berikut:

T4: Mengubah nilai pada Rec_1 dan Rec_3.
T5: Membaca dan mengubah nilai pada Rec_2 dan Rec_4.

ii. Analisis Keamanan:

Jelaskan mengapa Tree Protocol menjamin sistem bebas dari deadlock meskipun tidak menggunakan skema pencegahan tambahan (seperti timestamping atau deadlock detection).

SOAL 3: Multiple Granularity Locking (15 Poin)

Sebuah sistem basis data menggunakan hirarki: Database (DB) → Tabel (T) → Blok (B) → Record (R).

Tabel “Karyawan” terdiri dari 100 blok data. Transaksi $T_{6}$ ingin melakukan operasi sebagai berikut:

“Membaca seluruh record pada Tabel Karyawan, namun hanya mengubah nilai gaji pada record-record yang berada di Blok 15 dan Blok 50.”

Pertanyaan:

i. Sebutkan urutan perolehan lock ( $I S, I X, S, X, S I X$ ) yang diminta oleh $T_{6}$ dari level tertinggi hingga terendah.

ii. Jika pada saat yang sama transaksi $T_{7}$ sedang memegang $S - l oc k$ pada Blok 15, apakah $T_{6}$ dapat melanjutkan operasinya? Jelaskan menggunakan matriks kompatibilitas lock.

SOAL 4: Timestamp & Validation Protocols (25 Poin)

Diberikan schedule sebagai berikut:

Schedule S2: $R_{1} (X); R_{2} (Y); W_{2} (X); W_{1} (Y); C_{1}; C_{2};$

Asumsikan $TS (T_{1}) = 1$ dan $TS (T_{2}) = 2$ . Sebelum eksekusi, semua $W - TS$ dan $R - TS$ item data adalah 0.

Pertanyaan:

i. Apakah schedule tersebut diizinkan oleh Basic Timestamp Ordering Protocol? Lakukan tracing langkah demi langkah.

ii. Apakah schedule tersebut diizinkan jika menggunakan Thomas’ Write Rule? Jelaskan perbedaannya.

iii. Lakukan tracing Validation-Based Protocol untuk schedule tersebut. Tentukan apakah $T_{2}$ berhasil melewati fase validasi setelah $T_{1}$ commit.

(Gunakan 3 fase: Read, Validation, Write).

SOAL 5: Multiversion & Snapshot Isolation (25 Poin)

Diberikan transaksi dan nilai awal data $A = 10, B = 20$ .

T8: $R (A), B = B + A, W (B), C o mmi t$
T9: $R (B), A = A + B, W (A), C o mmi t$

Eksekusi interleaved yang terjadi adalah:

$R_{8} (A)$
$R_{9} (B)$
$B = B + A$ (T8)
$W_{8} (B)$
$A = A + B$ (T9)
$W_{9} (A)$
$C o mmi t T_{8}$
$C o mmi t T_{9}$

Pertanyaan:

i. Jika menggunakan Multiversion Timestamp Ordering, tuliskan versi data yang dihasilkan ( $A_{0}, A_{9}, B_{0}, B_{8}$ , dst) dan nilai $W - TS$ serta $R - TS$ pada setiap langkah.

ii. Jika menggunakan Snapshot Isolation dengan aturan First-Committer Wins, tentukan apakah $T_{9}$ berhasil commit. Berikan penjelasan mengenai Write Set dari kedua transaksi tersebut.

# Kunci Jawaban & Pembahasan

Bagian 1: 2PL

a. Basic 2PL:

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

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

$X L_{1} (A), W_{1} (A)$ (Upgrade)

$S L_{3} (C), R_{3} (C)$

$S L_{1} (B), R_{1} (B)$ (Boleh karena S-lock kompatibel)

$X L_{3} (C), W_{3} (C)$ (Upgrade)

$X L_{2} (B), W_{2} (B)$ (Upgrade)

$X L_{1} (B), W_{1} (B)$ → WAIT (Konflik dengan $X L_{2} (B)$ )

Keterangan: Pada Basic 2PL, transaksi bisa melepas lock kapan saja setelah lock point, namun di sini $T_{1}$ tertahan menunggu $T_{2}$ .

b. Strict 2PL:

Sama dengan Basic, namun $X L_{y} (X)$ hanya dilepas setelah Commit. $T_{1}$ tetap menunggu $T_{2}$ .

c. Rigorous 2PL:

Sama dengan Strict, namun seluruh lock (S dan X) ditahan hingga commit.

Bagian 2: Tree Protocol

i. Jawaban T4 & T5:

T4: $l oc k - X (D B) \to l oc k - X (T ab l e_A) \to l oc k - X (P a g e_A 1) \to l oc k - X (R ec_1) \to l oc k - X (P a g e_A 2) \to l oc k - X (R ec_3) \to u n l oc k \dots$

T5: $l oc k - X (D B) \to l oc k - X (T ab l e_A) \to l oc k - X (P a g e_A 1) \to l oc k - X (R ec_2) \to l oc k - X (T ab l e_B) \to l oc k - X (P a g e_B 1) \to l oc k - X (R ec_4) \dots$

ii. Pembahasan: Tree protocol menjamin bebas deadlock karena perolehan lock mengikuti urutan parsial (top-down). Tidak mungkin ada siklus tunggu (circular wait) karena arah perolehan lock selalu searah menjauhi root, sehingga siklus dalam Wait-for Graph tidak mungkin terbentuk.

Bagian 3: Multiple Granularity

i. Urutan Lock T6:

$I S (D B)$

$S I X (T ab e l_K a ry a w an)$ (SIX karena baca semua, update sebagian)

$I X (Bl o k_15), I X (Bl o k_50)$

$X (R ec_g aji_d i_B 15), X (R ec_g aji_d i_B 50)$

ii. Analisis: $T_{6}$ meminta $I X$ pada Blok 15. Karena $T_{7}$ memegang $S - l oc k$ , maka $T_{6}$ WAIT. Berdasarkan matriks kompatibilitas, $S$ dan $I X$ tidak kompatibel.

Bagian 4: Timestamp & Validation

i. Basic TO:

$R_{1} (X) : TS (1) \geq W - TS (X) = 0$ (OK, $R - TS (X) = 1$ )

$R_{2} (Y) : TS (2) \geq W - TS (Y) = 0$ (OK, $R - TS (Y) = 2$ )

$W_{2} (X) : TS (2) \geq R - TS (X) = 1$ dan $TS (2) \geq W - TS (X) = 0$ (OK, $W - TS (X) = 2$ )

$W_{1} (Y) : TS (1) < R - TS (Y) = 2$ → ABORT T1. T1 mencoba menulis data yang sudah dibaca transaksi lebih muda.

ii. Thomas’ Write Rule: Jika $TS (T_{i}) < W - TS (Q)$ , write diabaikan. Namun pada kasus $W_{1} (Y)$ , konfliknya adalah dengan $R - TS (Y)$ , maka tetap Abort.

iii. Validation: $T_{1}$ divalidasi lebih dulu. $T_{2}$ divalidasi terhadap $T_{1}$ . Karena $W S (T_{1}) = {Y}$ beririsan dengan $RS (T_{2}) = {Y}$ , maka $T_{2}$ gagal validasi (Kondisi 2 dilanggar).

Bagian 5: MVCC & SI

i. MVCC:

Langkah 4 ( $W_{8} (B)$ ) membuat versi $B_{8}$ dengan $W - TS = 8$ . Langkah 6 ( $W_{9} (A)$ ) membuat versi $A_{9}$ dengan $W - TS = 9$ . Semua lolos karena $TS (T i) \geq R - TS (Q_{o l d})$ .

ii. Snapshot Isolation:

$W S (T_{8}) = {B}$ , $W S (T_{9}) = {A}$ .

Karena $W S (T_{8}) \cap W S (T_{9}) = \emptyset$ , maka tidak ada konflik tulis-tulis.

Kedua transaksi COMMIT SUKSES. Terjadi anomali Write Skew karena hasil akhir bergantung pada urutan commit tanpa menghiraukan pembacaan data yang dilakukan secara konkuren.

Tips Pengerjaan untuk Peserta

Alokasikan 30 menit untuk Soal 1 karena tracing lock sangat rawan ketidaktelitian.
Pada Multiple Granularity, selalu mulai dari level Database.
Ingat: Pada Snapshot Isolation, transaksi membaca data yang sudah dicommit sebelum transaksi tersebut dimulai.

IF Notes

Explorer

Latihan UAS IF3140-CC A

Problem Set: Concurrency Control (Paket A)

Tujuan Pembelajaran

SOAL 1: Two-Phase Locking Protocols (20 Poin)

SOAL 2: Tree Protocol (15 Poin)

SOAL 3: Multiple Granularity Locking (15 Poin)

SOAL 4: Timestamp & Validation Protocols (25 Poin)

SOAL 5: Multiversion & Snapshot Isolation (25 Poin)

Bagian 1: 2PL

Bagian 2: Tree Protocol

Bagian 3: Multiple Granularity

Bagian 4: Timestamp & Validation

Bagian 5: MVCC & SI

Tips Pengerjaan untuk Peserta

Graph View

Table of Contents

Backlinks