Kamis, 04 Februari 2010

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

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 R1 ∪ … ∪ Rn, aljabar relasional seleksi dan proyeksi menjadi
    σF(R) ≡ (σF(R1)) ∪ … ∪ (σF(Rn))
    πattr(R) ≡ (πattr(R1)) ∪ … ∪ (πattr(Rn))
  • Fungsi-fungsi agregat (query Q(R) diasumsikan menghasilkan relasi satu kolom)
    • min(Q(R)) ≡ min(Q(R1), …, Q(Rn))
    • max(Q(R)) ≡ max(Q(R1), …, Q(Rn))
    • sum(Q(R)) ≡ sum(Q(R1)) + … + sum(Q(Rn))
  • Operasi R join S
    Jika dimisalkan relasi S difragmentasi berdasarkan fragmentasi relasi R, sedemikian sehingga R = R1 ∪ R2 dan S = S1 ∪ S2, 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 A1, S di A2, dan T di A3, query R join S join T yang dilakukan pada situs Ai, harus ditampilkan hasilnya pada situs Ai. Strategi pemrosesan query yang mungkin adalah sebagai berikut:

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

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 A1 dan S di A2, kemudian dilakukan operasi R join S pada A1), strategi semijoin dapat diilustrasikan sebagai berikut:

  1. lakukan proyeksi di A1 hanya dengan atribut yang dimiliki R dan S; temp1 := πattr(R) ∩ attr(s)(R)
  2. hasil temp1 disalin ke A2 dan di-join dengan S; temp2 := S join temp1; perhatikan bahwa temp2 adalah juga S semijoin R
  3. temp2 disalin ke A1 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 R1 join R2 join … Rn 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.


Tidak ada komentar:

Posting Komentar