Pemrosesan Kueri Terdistribusi : Infrastruktur dan Platform untuk Data Sains

 Notasi kalkulus algebra

Perbedaan kalkulus relasional dengan kalkulus algebra

Prinsip-prinsip Sistem Basis Data Terdistribusi

Masalah Umum Pemrosesan Query pada Basis Data Terdistribusi

• Relational Calculus Query --> Relational Calculus Algebra (ini tidak tunggal), setiap urutan ini bisa mengkonsumsi sumber daya computer yang berbeda walaupun nanti outputnya sama

• Melibatkan fragmen data yang tersebar pada masing-masing situs mengakibatkan waktu yang dibutuhkan untuk mengirimkan pesan & mendapat respon ( query) menjadi lebih lama dibanding kalau basis data terpusat.

• Tujuan : meminimalisir konsumsi sumber daya

Query Optimization

Untuk mengoptimalkan eksekusi query pada sistem basis data terdistribusi setidaknya ada 4 unsur yang dapat dipertimbangkan, yaitu :

1. Ruang Pencarian Solusi : Minimalisir ruang pencarian kemungkinan solusi yang akan dieksekusi karena ada sangat banyak kemungkinan strategi eksekusi yang dapat dilakukan
2. Minimalisir Cost
3. Strategi Pencarian yang optimal dengan algoritma-algoritma tertentu
4. Database Statistic : estimasi ukuran relasi sementara yang terbentuk akibat operasi aljabar pada tabel -> dipikirkan cara meminimalisir ukuran relasi sementara ini.

Distributed Cost Model

Biaya untuk mengeksekusi strategy query terdistribusi dapat diperhitungkan sebagai total waktu atau hanya waktu respon (responses time).

Tcpu : waktu pemrosesan untuk menjalanlan instruksi-instruksi CPU

TI/O : waktu pengaksesan disk I/O

Tmsg : waktu tetap untuk menginisiasi dan menerima pesan

TTR : waktu untuk mentransmisikan unit data dari satu situs ke situs lainnya.

    Komponen pertama dan kedua adalah waktu pemrosesan di masing-masing situs (local) , sedangkan komponen ketiga dan keempat adalah komponen waktu pemrosesan untuk berkomunikasi. Tentunya untuk tipe topology jaringan yang melibatkan internet akan mendominasi waktau total pada komponen waktu komunikasinya.

Data Lokalisasi

Merupakan salah satu teknik yang digunakan untuk menyederhanakan query yang telah ditransformasikan dalam calculus algebra, agar query-query tersebut sesuai dengan kondisi fragment data.

   Teknik penyederhanaan tetap menggunakan operator-operator kalkulus aljabar namun disesuaikan dengan fragmentasi data pada masing-masing situs, sehingga operasi diharapkan dapat dilakukan secara local dan dapat meminimalisir transfer data antar situs, atau meminimalisir data yang harus ditransfer antar situs.

Join Ordering

• Merupakan aspek penting mengoptimasi eksekusi query karena operasi join bisa meningkatkan waktu komunikasi antar situs jika fragement-fragment dari tabel yang akan dijoinkan berada pada situs yang berbeda.

• Unsur yang dipertimbangkan dalam menentukan urutan proses join

yang paling optimal adalah :

1. Urutan proses
2. Ukuran “intermediate table” --> sehingga menentukan di situs mana operasi join akan dilakukan

Query Execution Planning Approach

• Dynamic Approach

• Mengabaikan biaya transmisi data pada situs hasil
• Hanya menangani fragmentasi horizontal
• Mempertimbangkan topology jaringan sistem
• Algoritma ini dieksekusi pada master site ( tempa query diinisiasi)
• Mengoptimasi dengan mencari fragmentasi data yang sekecil mungkin untuk ditransmisikan

• Static Approach

• Mencari semua alternatif strategi eskekusi untuk memperoleh cost yang seminimal mungkin, dengan harapan biaya proses pencarian bisa semakin kecil jika query sering digunakan.
• Berfokus pada optimasi urutan join, metoda join, lokasi situs eksekusi, jalur akses pada relasi local dan mode transfer antar situs.
• Menunjukkan performa yang baik jika didukung pada jaringan dengan kecepatan tinggi dan kecepatan menengah untuk jaringan local.

• Hybrid Approach : kombinasi dari kelebihan-kelebih dynamic approach dan static approach

• Adaptive Query Processing : menganalisis QEP dengan mempertimbangkan semua perubahan

kondisi basis data selama proses berjalan. Dapat dilakukan jika sistem basis data sudah

digunakan.

Referensi : Özsu, M. Tamer, and Patrick Valduriez. Principles of distributed database systems. Vol. 2. Englewood Cliffs: Prentice Hall, 1999.