Bagian IV: Pemrosesan Query Terdistribusi

Pengantar: Dalam posting bagian ini akan dibahas masalah (issue) lainnya dalam basis data terdistribusi, yaitu pemrosesan query terdistirbusi, berikut pertimbangan dan contoh kasus dalam pembuatan query.

Pemrosesan query pada basis data terdistribusi berbeda dari pemrosesan query pada basis data terpusat. Query-query pada relasi global perlu disesuaikan agar dapat menganani relasi-relasi dalam fragmen. Pembuatan query pada perancangan basis data terdistribusi dapat diilustrasikan dengan bagan di bawah ini.

Bagan pembuatan query terdistribusi

Pada basis data terpusat, evaluasi query harus memperhatikan faktor pengaksesan storage (disk), yakni jumlah blok pada hard disk yang dibaca/tulis. Sementara itu, dalam pemrosesan query pada basis data terdistribusi, diperlukan pula pertimbangan dari sisi

1. transmisi data melalui jaringan
2. peningkatan kinerja yang potensial akibat pemrosesan query secara paralel

Dalam membuat query pada basis data terdistribusi, perlu diperhatikan hal-hal sebagai berikut:

• penyesuaian dari query relasi global ke query terhadap fragmen, yaitu bahwa ekspresi relasi global dalam query harus disesuaikan menjadi ekspresi relasi fragmen; relasi global harus dapat direkonstruksi (dibuat terlihat global) dari fragmen-fragmennya
• penyederhanaan ekspresi aljabar relasional, juga deteksi dan penghilangan redundant
• pemilihan strategi join yang optimal (khususnya pada program yang melakukan “semi-join“)
• pemilihan rencana pemrosesan query yang optimal

Sebagai contoh, jika dimisalkan terdapat relasi global PARTS(PartNo, OrderNo, Price) yang dipartisi menjadi

• PARTS1:= σ_{0≤PartNo≤300}(PARTS)
• PARTS2:= σ_{301≤PartNo≤500}(PARTS)
• PARTS3:= σ_{501≤PartNo≤999}(PARTS)

Query Q = σ_{25≤PartNo≤350}(PARTS) pada relasi global dapat diubah menjadi bentuk query fragmen berikut:

• mengganti relasi global menjadi definisi fragmen-fragmennya:
  Q1 = σ_{25≤PartNo≤350}(PARTS1 ∪ PARTS2 ∪ PARTS3)
• melakukan pushdown pada tiap-tiap fragmen:
  Q2 = σ_{25≤PartNo≤350}(PARTS1) ∪ σ_{25≤PartNo≤350}(PARTS2) ∪ σ_{25≤PartNo≤350}(PARTS3)

Pemrosesan Paralel pada Query Fragmen

• Jika dimisalkan sebuah relasi R difragmentasi secara horizontal (seperti contoh sebelumnya) menjadi R₁ ∪ … ∪ R_n, aljabar relasional seleksi dan proyeksi menjadi
  σ_F(R) ≡ (σ_F(R₁)) ∪ … ∪ (σ_F(R_n))
  π_attr(R) ≡ (π_attr(R₁)) ∪ … ∪ (π_attr(R_n))
• Fungsi-fungsi agregat (query Q(R) diasumsikan menghasilkan relasi satu kolom)
  • min(Q(R)) ≡ min(Q(R₁), …, Q(R_n))
  • max(Q(R)) ≡ max(Q(R₁), …, Q(R_n))
  • sum(Q(R)) ≡ sum(Q(R₁)) + … + sum(Q(R_n))
• Operasi R join S
  Jika dimisalkan relasi S difragmentasi berdasarkan fragmentasi relasi R, sedemikian sehingga R = R₁ ∪ R₂ dan S = S₁ ∪ S₂, setiap fragmen dari R hanya perlu digabungkan (di-join) dengan fragmen dari S yang bersesuaian dengannya.

Pemrosesan Join Query

Jika terdapat relasi-relasi pada tempat (situs) yang terpisah, misalnya relasi R di situs A₁, S di A₂, dan T di A₃, query R join S join T yang dilakukan pada situs A_i, harus ditampilkan hasilnya pada situs A_i. Strategi pemrosesan query yang mungkin adalah sebagai berikut:

• Meng-copy salinan semua relasi R, S, dan T ke situs A_i, kemudian melakukan join secara lokal di A_i
• Melakukan join secara bertahap, sbb:
  1. menyalin R ke A₂ dan menghasilkan temp1 = R join S
  2. temp1 disalin ke A₃ dan menghasilkan temp2 = temp1 join T
  3. temp2 sebagai hasil akhir dipindahkan ke A_i

Strategi join di atas dapat dipilih dengan mempertimbangkan faktor-faktor berikut:

• jumlah data yang ditransfer (salin)
• biaya (resource) yang diperlukan untuk transfer data antarsitus
• kecepatan pemrosesan di tiap situs

Operasi join dapat pula dioptimalkan dengan menggunakan strategi semijoin. R semijoin S ≡ π_attr(R) (R join S). Jika dimisalkan relasi R disimpan di A₁ dan S di A₂, kemudian dilakukan operasi R join S pada A₁), strategi semijoin dapat diilustrasikan sebagai berikut:

1. lakukan proyeksi di A₁ hanya dengan atribut yang dimiliki R dan S; temp1 := π_{attr(R) ∩ attr(s)}(R)
2. hasil temp1 disalin ke A₂ dan di-join dengan S; temp2 := S join temp1; perhatikan bahwa temp2 adalah juga S semijoin R
3. temp2 disalin ke A₁ dan dilakukan operasi R join temp2

Strategi semijoin di atas dapat meningkatkan efisiensi operasi join karena data yang dipertukarkan melalui jaringan menjadi lebih kecil. Untuk membuat join lebih efisien, dapat diimplementasikan program (semi-)join yang memiliki pemroses query (query processor) untuk membuat partisi dari sederetan join seperti R₁ join R₂ join … R_n menjadi kumpulan semijoin yang lebih efisien. Pemilihan semijoin dilakukan dengan mempertimbangkan perpindahan data (resource dan waktu) beserta konstrain yang terkait, misalnya waktu respon maksimum dari query.

---