Back to Latihan UAS IF3140

Problem Set: Concurrency Control (Paket B)

Mata Pelajaran: Sistem Basis Data

Estimasi Waktu: 120 Menit

Total Nilai: 100 Poin

Tujuan Pembelajaran

Setelah menyelesaikan paket soal ini, mahasiswa diharapkan dapat:

Melakukan tracing perolehan kunci dan manajemen antrian (Blocking Queue) pada protokol Two-Phase Locking.
Menerapkan mekanisme perolehan kunci top-down pada struktur pohon data yang kompleks.
Menganalisis interaksi kunci niat (Intention Locks) pada hirarki data Multiple Granularity.
Mengevaluasi jadwal transaksi menggunakan Timestamp Ordering dan Thomas’ Write Rule.
Memahami fase eksekusi pada protokol berbasis validasi dan multiversion.

SOAL 1: 2PL & Transaction Manager Logic (25 Poin)

Diberikan urutan kedatangan operasi dari 3 transaksi ( $T_{1}, T_{2}, T_{3}$ ) sebagai berikut:

Urutan: $R_{1} (A); R_{2} (A); W_{3} (B); W_{1} (B); W_{2} (B); C_{1}; C_{3}; C_{2};$

Aturan Transaction Manager:

Gunakan Rigorous Two-Phase Locking.
Operasi diproses berdasarkan urutan kedatangan.
Jika transaksi terblokir (menunggu lock), semua operasi berikutnya dari transaksi tersebut masuk ke Blocking Queue.
Saat transaksi yang terblokir aktif kembali, operasi di antriannya mendapat prioritas utama sebelum melayani urutan kedatangan baru.

Pertanyaan:

Tuliskan schedule eksekusi yang dihasilkan, mencakup perolehan lock ( $S L, X L$ ), pelepasan lock ( $UL$ ), dan status Blocking Queue. Berikan penjelasan untuk setiap langkahnya.

SOAL 2: Tree Protocol - University System (15 Poin)

Perhatikan struktur data hirarkis berikut yang merepresentasikan data universitas:

graph TD
    UNIV[Universitas] --> FAK[Fakultas_Teknik]
    UNIV --> ADM[Administrasi_Pusat]
    FAK --> PRODI[Prodi_Informatika]
    FAK --> LAB[Lab_Riset]
    PRODI --> MHS[Data_Mahasiswa]
    PRODI --> KUR[Kurikulum]
    LAB --> ALAT[Inventaris_Alat]

i. Prosedur Lock:

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

T4: Memperbarui Kurikulum dan Inventaris_Alat.
T5: Membaca data pada Data_Mahasiswa dan memperbarui Inventaris_Alat.

ii. Karakteristik:

Jelaskan perbedaan mendasar antara cara pelepasan kunci (unlock) pada Tree Protocol dibandingkan dengan protokol 2PL standar.

SOAL 3: Multiple Granularity - E-Commerce (20 Poin)

Hirarki data: Database (DB) → Store (S) → Category (C) → Product (P).

Terdapat Toko “Elektronik-X” yang memiliki kategori “Smartphone”. Kategori ini memiliki ribuan produk.

Skenario:

Transaksi T6 sedang melakukan update harga pada seluruh produk di kategori “Smartphone”.
Transaksi T7 ingin membaca spesifikasi satu produk spesifik (misal: P-001) yang berada di bawah kategori “Smartphone”.
Transaksi T8 ingin melakukan pengecekan stok pada seluruh produk di Toko “Elektronik-X”.

Pertanyaan:

i. Tentukan jenis kunci ( $I S, I X, S, S I X, X$ ) paling efisien yang harus dimiliki $T_{6}$ pada level Category dan Product.

ii. Tuliskan daftar perolehan kunci lengkap untuk T7 dan T8.

iii. Berdasarkan matriks kompatibilitas, apakah T7 harus menunggu T6? Bagaimana dengan T8 terhadap T6? Jelaskan.

SOAL 4: Timestamp Ordering & Thomas’ Write Rule (20 Poin)

Diberikan schedule sebagai berikut:

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

Asumsikan $TS (T_{1}) = 1, TS (T_{2}) = 2, TS (T_{3}) = 3$ . Nilai awal $R - TS$ dan $W - TS$ adalah 0.

Pertanyaan:

i. Lakukan tracing eksekusi menggunakan Basic Timestamp Ordering. Transaksi mana yang mengalami abort?

ii. Jika sistem menerapkan Thomas’ Write Rule, apakah ada perbedaan nasib transaksi? Jelaskan mekanismenya pada operasi $W_{1} (X)$ jika $W_{3} (X)$ sudah dilakukan lebih dulu.

SOAL 5: Validation & Multiversion Schemes (20 Poin)

i. Validation-Based Protocol:

Lakukan tracing untuk schedule: $R_{1} (A); R_{2} (B); W_{1} (B); W_{2} (A); C_{1}; C_{2};$ .

Tentukan apakah $T_{2}$ lolos fase validasi jika $Va l i d a t i o n (T_{1}) < Va l i d a t i o n (T_{2})$ . Gunakan kriteria irisan Read Set dan Write Set.

ii. Multiversion 2PL:

Jelaskan keuntungan mekanisme pembacaan pada Multiversion 2PL untuk transaksi yang bersifat Read-Only. Mengapa transaksi Read-Only pada protokol ini dijamin tidak akan pernah menunggu lock dari transaksi Update?

# Kunci Jawaban & Pembahasan Paket B

Bagian 1: 2PL dengan Blocking Queue

$S L_{1} (A); R_{1} (A)$ : $T_{1}$ dapat S-lock A.

$S L_{2} (A); R_{2} (A)$ : $T_{2}$ dapat S-lock A (kompatibel).

$X L_{3} (B); W_{3} (B)$ : $T_{3}$ dapat X-lock B.

$W_{1} (B)$ : $T_{1}$ minta $X L (B)$ . Konflik dengan $T_{3}$ . $T_{1}$ WAIT. Antrian $T_{1} : [W_{1} (B), C_{1}]$ .

$W_{2} (B)$ : $T_{2}$ minta $X L (B)$ . Konflik dengan $T_{3}$ . $T_{2}$ WAIT. Antrian $T_{2} : [W_{2} (B), C_{2}]$ .

$C_{3}$ : $T_{3}$ commit. Semua lock dilepas ( $U L_{3} (B)$ ).

Prioritas Eksekusi: Karena $T_{1}$ lebih dulu mengantri untuk B, $T_{1}$ bangun.

$X L_{1} (B); W_{1} (B); C_{1}; U L_{1} (A); U L_{1} (B);$

Pelepasan Lock $T_{1}$ : Membangunkan $T_{2}$ .

$X L_{2} (B); W_{2} (B); C_{2}; U L_{2} (A); U L_{2} (B);$

Bagian 2: Tree Protocol

i. Urutan Lock:

T4: $l oc k - X (U N I V) \to l oc k - X (F A K) \to l oc k - X (PRO D I) \to l oc k - X (K U R) \to l oc k - X (L A B) \to l oc k - X (A L A T)$ .

T5: $l oc k - X (U N I V) \to l oc k - X (F A K) \to l oc k - X (PRO D I) \to l oc k - X (M H S) \to l oc k - X (L A B) \to l oc k - X (A L A T)$ .

ii. Pembahasan: Pada 2PL, unlock hanya boleh di fase shrinking. Pada Tree Protocol, unlock bisa dilakukan kapan saja setelah proses pada node tersebut selesai, asal tidak melanggar aturan bahwa node yang sudah di-unlock tidak boleh di-lock kembali.

Bagian 3: Multiple Granularity

i. T6: Pada level Category butuh $I X$ , pada level Product butuh $X$ (untuk setiap produk). Namun, karena mencakup seluruh produk, lebih efisien menggunakan $X$ langsung pada level Category.

ii. Daftar Lock:

T7: $I S (D B) \to I S (S) \to I S (C) \to S (P - 001)$ .

T8: $I S (D B) \to S (S_El e k t ro nik_X)$ .

iii. Analisis: $T_{7}$ butuh $I S (C)$ , sedangkan $T_{6}$ memegang $X (C)$ . T7 WAIT. $T_{8}$ butuh $S (S)$ , sedangkan $T_{6}$ punya $I X (S)$ (via ancestor). Berdasarkan matriks, $S$ dan $I X$ konflik, maka T8 WAIT.

Bagian 4: Timestamp Ordering

i. Tracing TO:

$R_{2} (X) : O K (R - TS (X) = 2)$ .

$W_{3} (X) : O K (W - TS (X) = 3)$ .

$R_{1} (Y) : O K (R - TS (Y) = 1)$ .

$W_{1} (X) : TS (1) < R - TS (X) = 2$ . Abort T1.

ii. Thomas’ Write Rule: Jika $W_{1} (X)$ datang setelah $W_{3} (X)$ , dan $TS (1) < W - TS (X) = 3$ , maka operasi $W_{1} (X)$ cukup diabaikan (ignored) tanpa melakukan abort pada $T_{1}$ , asalkan tidak melanggar $R - TS$ . Namun, karena $TS (1) < R - TS (X) = 2$ , $T_{1}$ tetap harus Abort.

Bagian 5: Validation & MVCC

i. Validation:

$RS (T_{1}) = {A}, W S (T_{1}) = {B}$

$RS (T_{2}) = {B}, W S (T_{2}) = {A}$

Saat $T_{2}$ validasi: $W S (T_{1}) \cap RS (T_{2}) = {B}$ . Karena ada irisan, $T_{2}$ melanggar kondisi validasi. T2 Abort.

ii. MV-2PL: Karena transaksi Read-Only membaca versi data yang sudah di-commit sebelum transaksi tersebut dimulai. Versi tersebut tidak akan berubah oleh transaksi Update yang sedang berjalan, sehingga tidak perlu meminta lock.

Tips Strategi:

Fokus pada Blocking Queue di Soal 1, karena urutan eksekusi berubah total setelah pelepasan kunci.
Pada Soal 3, perhatikan bahwa mengunci level yang terlalu tinggi bisa mematikan konkurensi, tapi level terlalu rendah meningkatkan overhead.

IF Notes

Explorer

Latihan UAS IF3140-CC B

Problem Set: Concurrency Control (Paket B)

Tujuan Pembelajaran

SOAL 1: 2PL & Transaction Manager Logic (25 Poin)

SOAL 2: Tree Protocol - University System (15 Poin)

SOAL 3: Multiple Granularity - E-Commerce (20 Poin)

SOAL 4: Timestamp Ordering & Thomas’ Write Rule (20 Poin)

SOAL 5: Validation & Multiversion Schemes (20 Poin)

Bagian 1: 2PL dengan Blocking Queue

Bagian 2: Tree Protocol

Bagian 3: Multiple Granularity

Bagian 4: Timestamp Ordering

Bagian 5: Validation & MVCC

Graph View

Table of Contents

Backlinks