ANALISIS OPTIMISASI FORMULA DISTRIBUTED QUERY DALAM BASIS DATA RELASIONAL
R. SUDRAJAT
SEKOLAH PASCASARJANA INSTITUT PERTANIAN BOGOR BOGOR 2007
ii
RINGKASAN Proses join query dalam sistem basis data terdistribusi adalah salah satu masalah penting dan cukup rumit dan dapat melibatkan proses komputasi dan formula yang cukup kompleks. Penelitian dalam tesis ini ditujukan untuk menganalisis optimisasi query secara teoritis yang didukung oleh percobaan dalam basis data relasional dengan melibatkan ukuran data yang besar. Analisis difokuskan pada join query dengan menggunakan Nested-LoopsJoin, Block-Nested-Loops-Join, Sort-Merge-Join dan Hash-Join yang didasarkan pada analisis fungsi biaya. Dalam penelitian ini kasus data yang digunakan diambil dari Perusahaan Asuransi yang secara transaksional data tersimpan tersebar di beberapa cabang perusahaan. Hasil dari analisis dan pecobaan menunjukkan bahwa metode Hash-Join dapat menyelesaikan join query dengan biaya terendah. Fragmentasi dan partisi dalam jumlah data yang besar diperlukan untuk menghasilkan join query yang lebih baik. Dengan demikian dalam melakukan proses transaksi dengan jumlah data yang besar (lebih dari satu juta record) fragmentasi dan optimisasi sangat diperlukan untuk mengurangi waktu proses. Proses komputasi secara paralel dengan menggunakan multi processors
sangat diperlukan agar dapat
meningkatkan unjuk kerja proses query dalam basis data terdistribusi.
Kata Kunci : basis data terdistribusi, optimisasi, join query, fragmentasi.
iii
ABSTRACT
Joined query is considered an expensive operation therefore specific optimization technique involving formulation, strategy and transformation is required. The purpose of this thesis is to perform optimization analysis of query, theroretically and experimentaly, on distributed relational databases comprising large size data tables. The analysis is focused on join query using Nested-Loops-Join, BlockNested-Loops-Join, Sort-Merge-Join and Hash-Join with respect to cost function analysis. The data case used in this research has been taken from an Insurance Company that maintains and operates transactional data stored distributively in several company branches. The result of the analysis and experiment shows that Hash-Join provides the best (smalest) cost for join query. It is also shown that fragmentation and partition of large data contributes to the better performace of join query. Therefore, it is recommended that the transactional data comprising large data records (one million records or more) needs to be well partitioned to reducethe query execution time. Furthermore, the use of parallel computation using multiple processors are recommended to improve futher the performance of query processing on distributed databases.
Keyword : distributed database, optimization, join query, fragmentation.
ANALISIS OPTIMISASI FORMULA DISTRIBUTED QUERY DALAM BASIS DATA RELASIONAL
R. SUDRAJAT Tesis Sebagai salah satu syarat untuk memperoleh gelar Magister Sains pada Program Studi Ilmu Komputer
SEKOLAH PASCASARJANA INSTITUT PERTANIAN BOGOR BOGOR 2007
i
SURAT PERNYATAAN Dengan ini menyatakan bahwa tesis saya yang berjudul : Analisis Optimisasi Formula Distributed Query dalam Basis Data Relasional adalah merupakan hasil karya saya sendiri dan belum pernah dipublikasikan. Sumber informasi berasal atau dikutip dari karya yang diterbitkan maupun tidak diterbitkan dari penulis lain telah disebutkan dalam teks dan dicantumkan dalam daftar pustaka di bagian akhir tesis ini.
Bogor, Juli 2007
Sudrajat, R. NRP: G651024024
JUDUL
: Analisis Optimisasi Formula Distributed Query dalam Basis Data Relasional
NAMA
: R. SUDRAJAT
NRP
: G651024024
Disetujui Komisi Pembimbing
Prof. Dr. Ir. Kudang Boro Seminar M.Sc.
Ir. Fahren Bukhari, M.Sc.
Ketua
Anggota
Diketahui
Ketua Program Studi Ilmu Komputer
Dr. Sugi Guritman
Tanggal Ujian : 14 Juli 2007
Dekan Sekolah Pascasarjana
Prof. Dr. Ir. Khairil A. Notodiputro, MS.
Tanggal Lulus :
iv
@ Hak cipta milik Institut Pertanian Bogor, tahun 2007 Hak cipta dilindungi Dilarang mengutip dan memperbanyak tanpa ijin tertulis dari Institut Pertanian Bogor, sebagian atau seluruhnya dalam bentuk apapun, baik cetak, fotokopi, microfilm, dan sebagainya
i
SURAT PERNYATAAN Dengan ini menyatakan bahwa tesis saya yang berjudul : Analisis Optimisasi Formula Distributed Query dalam Basis Data Relasional adalah merupakan hasil karya saya sendiri dan belum pernah dipublikasikan. Sumber informasi berasal atau dikutip dari karya yang diterbitkan maupun tidak diterbitkan dari penulis lain telah disebutkan dalam teks dan dicantumkan dalam daftar pustaka di bagian akhir tesis ini.
Bogor, Juli 2007
Sudrajat, R. NRP: G651024024
vii
PRAKATA Puji Syukur ke Hadirat Allah SWT Yang Maha Pengasih dan Maha Penyayang atas Rahmat serta KaruniaNya, penulis diberi kemampuan dan kekuatan untuk dapat menyelesaikan tesis ini dengan judul:
“ Analisis
Optimisasi Formula Distributed Query dalam Basis Data Relasional “ Pada kesempatan ini penulis menyampaikan rasa hormat dan rasa terima kasih kepada Bapak Prof. Dr. Ir. Kudang Boro Seminar M.Sc. dan Bapak Ir. Fahren Bukhari, M.Sc yang telah meluangkan waktunya untuk membimbimg dan mengarahkan penulis hingga terselesaikannya tesis ini. Ucapan terima kasih juga penulis sampaikan kepada Bapak Drs. Edi Maryanto selaku Data Administrator Manager pada PT. Taspen yang telah memberikan penulis berupa data peserta Asuransi, dan terima kasih kepada Bapak Agus Muhtarom SSi. sebagai kepala Sistem Informasi FMIPA-UNPAD yang telah memberikan fasilitas penggunaan Lab.Penelitian Fakultas MIPA. Akhirnya penulis menyampaikan terima kasih pula untuk Istri tercinta dan putra-putri atas segala do’a dan dukungannya. Semoga segala bantuan dan dorongan yang telah diberikan kepada penulis mendapatkan balasan dari Allah SWT, dan semoga karya ilmiah ini bermanfaat.
Bogor, Juli 2007
Sudrajat, R.
viii
DAFTAR RIWAYAT HIDUP Penulis dilahirkan di Sumedang Jawa Barat pada tanggal 12 Pebruari 1960 sebagai anak ke tiga dari pasangan R. Kusdinar dan Ibu Epon Suhaenah (Alm). Pendidikan Sarjana ditempuh di Jurusan Matematika FMIPA Universitas Padjadjaran Bandung , lulus tahun 1986. Kesempatan untuk melanjutkan program Pascasarjana pada program studi Ilmu Komputer FMIPA IPB, diperoleh pada tahun 2002. Penulis bekerja sebagai tenaga pengajar di Universitas Padjadjaran Bandung sejak tahun 1987 di bidang algoritma pemrograman dan struktur data.
ix
DAFTAR ISI Halaman DAFTAR TABEL ................................................................................................... xi DAFTAR GAMBAR ................................................................................................ xii DAFTAR LAMPIRAN.............................................................................................xiii BAB I PENDAHULUAN ........................................................................................ 1.1. Latar Belakang ....................................................................................... 1.2. Formulasi Permasalahan ........................................................................ 1.3. Tujuan Penelitian ................................................................................... 1.4. Manfaat Penelitian ................................................................................. 1.5. Ruang Lingkup .......................................................................................
1 1 2 2 2 3
BAB II TINJAUAN PUSTAKA .............................................................................. 4 2.1. Basis Data Terdistribusi ......................................................................... 4 2.1.1. Sistem Basis Data Terdistribusi ................................................... 4 2.1.2. Arsitektur Sistem Basis Data Terdistribusi ................................... 5 2.2. Konsep Aljabar Relasional …………..................................................... 7 2.2.1. Selection ……...…………….......……....………........................ 8 2.2.2. Projection …………...….....…….………………........................ 9 2.2.3. Join …....……….…………………………….............................. 9 2.2.3.1 Cross Join …………........................................................ 11 2.2.3.2. Natural Join ………......................................................... 11 2.2.4. Operasi Himpunan …........ …………………..….…….............. 12 2.2.4.1.Union………………...……………………..................... 12 2.2.4.2.Intersection……………...……………............................ 13 2.2.4.3. Difference ………...…………………............................. 13 2.3. Proses Query ………………………………….………………............ 13 2.4. Optimisasi Query …………………………….…………………......... 16 2.5. Prinsip Optimisasi Query ………………….……………………......... 16 2.6. Metoda Optimisasi Query ……………………………..………........... 17 2.6.1. Optimisasi Query Basis Formula …………………………......... 18 2.6.2. Optimisasi Query Basis Biaya …...........…………………......... 18 2.6.3. Fungsi Biaya dari Statistik Basis Data ........................................ 19 2.6.4. Optimizer DBMS MySQL ............................................................ 21 BAB III METODOLOGI DAN RANCANGAN PENELITIAN ........................... 3.1 Metodologi Penelitian ........................................................................... 3.2 Sistematika Penelitian dan Pembahasan ................................................ 3.3 Tahapan Proses Penelitian ....................................................................
22 22 23 24
x Halaman BAB IV HASIL DAN PEMBAHASAN ............................................................... 27 4.1 Formulasi Masalah dan Penentuan Tujuan ............................................. 27 4.2 Formulasi Optimisasi Query ................................................................. 32 4.2.1. Analisis Selectivity Factor dari Karakteristik Basis Data ........... 35 4.2.2. Analisis Optimisasi Secara Spesifik ........................................... 36 4.2.3.1. Nested -Loops-Join ......................................................... 38 4.2.3.2. Block-Nested-Loops-Join ................................................. 39 4.2.3.3. Sort-Merge-Join .............................................................. 42 4.2.3.4. Biaya Sort-Merge-Join ................................................... 46 4.2.3.5. Hash-Join........................................................................ 46 4.2.3. Analisis Signifikansi Optimisasi Query ...................................... 50 4.2.4. Analisis Optimisasi Query Optimizer DBMS MySQL................. 54 4.3 Percobaan .............................................................................................. 59 BAB V KESIMPULAN DAN SARAN ................................................................. 71 5.1. Kesimpulan.. ........................................................................................ 71 5.2. Saran ..................................................................................................... 71 DAFTAR PUSTAKA .............................................................................................. 73
xi
DAFTAR TABEL Halaman
1. Fragmentasi Horizontal, Vertical dan Mixed Fragmentasi.................................. 7 2. Segmen Tabel peserta S1 .................................................................................... 8 3. Segmen Tabel peserta S2 .................................................................................... 8 4. Segmen Tabel pmk_ke1 R1 .................................................................................. .8 5. Segmen Tabel pstpens B1 ................................................................................... 8 6. Hasil Join dari S1 dan R1................................................................................... 10 7. Tahapan Proses Penelitian ................................................................................. 24 8. Tabel informasi data tabel relasi ........................................................................ 29 9. Contoh Segmen tabel pst_ke1 ......................................................................... 45 10. Contoh Segmen tabel pstaktif ........................................................................... 45 11. Running time query tabel satu relasi tanpa join, Q1 tanpa optimisasi, Q2 dengan optimisasi satu kriteria ................................. 62 12. Perbadingan join query tidak dioptimisasi dan dioptimisasi............................. 64 13. Running time query , Q6 mendahulukan operasi join sebelum seleksi , Q7 mendahulukan operasi seleksi sebelum operasi join .................................. 66 14. Perbandingan Running time fragmentasi setelah proses join query dan fragmentasi sebelum proses join query.............................................................. 67 15. Perbandingan Running time client berbeda spesifikasi ................................... 69
xii
DAFTAR GAMBAR Halaman 1. Lingkungan Basis Data Terdistribusi.................................................................. 5 2. Arsitektur Sistem Basis Data Terdistribusi......................................................... 6 3. Tahapan proses sebuah Query ............................................................................ 14 4. Bagan alir proses penelitian ............................................................................... 26 5. Diagram E-R keseluruhan tabel peserta ............................................................ 29 6. Diagram E-R tabel peserta spesialisasi menjadi tabel pst_ke1 dan pstaktif ...... 30 7. Diagram E-R tabel pensiun spesialisasi menjadi pmk_ke1 dan pmk_fd1 ......... 31 8. Rencana evaluasi query dari join tree ................................................................. 33 9. Rencana evaluasi Query mendahulukan operasi seleksi ..................................
34
10. Contoh perintah Join......................................................................................... 37 11. Algoritma Simple Nested Loops Join .............................................................. 38 12. Algoritma Block Nested Lopps Join ................................................................ 40 13. Penggunaan buffer Block Nested Lopps Join .................................................... 41 14. Algoritma Sort Merge Join ............................................................................... 44 15. Tahap Partisi Proyeksi Hash Based ................................................................. 47 16. Tahap Equality Join menggunakan Hash Join ................................................. 49 17. Algoritma Hash Join ......................................................................................... 50 18. Running time query satu relasi tanpa join, Q1 tanpa optimisasi, Q2 dengan optimisasi satu kriteria ..................................................................... 63 19. Perbandingan join query tidak dioptimisasi dan dioptimisasi .......................... 65 20. Running time query, Q6 mendahulukan operasi join sebelum seleksi, dan Q2 mendahulukan operasi seleksi sebelum operasi join. .......................... 66 21. Perbandingan Running time Q8 : fragmentasi setelah proses query dan Q9 :fragmentasi sebelum proses query ............................................................. 68 22. Perbandingan Runtime client yang berbeda spesifikasi ................................... 69 23. Konfigurasi bagian peta MIPA - NETWORK ( FMIPA-UNPAD 2007) ............ 70
xiii
DAFTAR LAMPIRAN Halaman
1. Contoh kamus data tabel relasi pst_ke1 4 buah atribut 3.873.324 record........ 75 2. Contoh kamus data tabel relasi pstaktif dengan 8 buah attribut 3.619.423 record ................................................................................................ 76 3. Contoh kamus data tabel relasi pmk_ke1 dengan 6 buah attribut 1.401.040 record................................................................................................. 77 4. Contoh kamus data tabel relasi pmk_fd1 dengan 13 buah attribut 1.261.239 record ................................................................................................ 78 5. Contoh kamus data tabel relasi pstpens dengan 11 buah attribut 1.264.037 record................................................................................................. 79 6. Contoh isi data dari tabel relasi pst_ke1 ..........................................................
80
7. Contoh isi data dari tabel relasi pstaktif...........................................................
81
8. Contoh isi data dari tabel relasi pmk_ke1 ......................................................... 82 9. Contoh isi data dari tabel relasi pmk_ke1 ......................................................... 83 10. Contoh isi data dari tabel relasi pmk_fd1 ........................................................ 84
BAB I PENDAHULUAN 1.1. Latar Belakang Sebuah perusahaan yang cukup besar biasanya mempunyai banyak cabang, misalnya sebuah bisnis supermarket yang cukup besar memiliki ratusan cabang dan tersebar di beberapa kota besar, sistem stok barangnya setiap hari harus dihitung yang terdiri dari merek, produk, jenis dan transaksi berisi saldo penjualan harian dan saldo barang. Demikian juga perusahaan-perusahaan yang bergerak dibidang jasa, misalnya perusahaan asuransi jasa pensiun yang cukup besar mempunyai banyak cabang tersebar di beberapa kota, setiap minggu atau setiap bulan harus melaporkan hasil transaksi-transaksi dari semua cabang yang tersebar tersebut. Sedangkan dalam menggabungkan tabel-tabel transaksi yang terpisah-pisah menjadi satu tabel secara berkala, sistem harus memprosesnya melalui join query. Masalah akan timbul bilamana prosesnya sangat lambat dan tidak sesuai dengan yang diharapkan. Keterlambatan proses akan menghambat pembuatan laporan dan pengambilan keputusan. Operasi join query adalah merupakan operasi yang cukup mahal dan sangat membutuhkan teknik dan metode tertentu untuk dapat menghasilkan keluaran sesuai dengan yang diharapkan (Chen Li. 2003). Proses join query dalam sistem basis data terdistribusi adalah salah satu masalah penting dan cukup rumit, prosesnya banyak menggunakan metodemetode optimisasi yang melibatkan formula-formula dan biaya-biaya query. Para ahli melakukan penelitian mencoba menggunakan teknik-teknik terdistribusi yang dilandasi oleh perkembangan lokal. Sistem harus melindungi users dari kompleksitas basis data, agar supaya proses query yang didistribusikan dapat mencapai hasil optimal dan mudah dikontrol (Richard 2000). Para programmer melakukan proses optimisasi query dapat menggunakan fasilitas optimizer dari DBMS, karena dalam kasus tertentu dapat memberikan hasil sesuai dengan yang diharapkan, misalnya : Oracle 9i’s selalu menemukan yang ideal untuk mengeksekusi query, karena bahasa SQL Oracle melakukan query dari berbagai jalur secara cepat, dan menemukan baris (row) dengan cara full-table scan, via b-tree index , menggabungkan dua tabel dengan beberapa
2 teknik Sort / Merge, tetapi Oracle 9i’s sangat membutuhkan unjuk kerja CPU dan memory yang cukup memadai (Ken 2002). Pada perkembangan penelitian terdapat sebuah tantangan lain, yaitu signifikansi mungkin akan tercapai bilamana komputasi dilakukan secara spesifik dan parsial disesuaikan dengan hardware dan software DBMS yang digunakan.
1.2. Formulasi Permasalahan Pada dasarnya permasalahan dalam optimisasi query belum tentu layak di optimisasi, dan belum tentu signifikan optimisasi query akan dicapai bila tidak disesuaikan antara DBMS, hardware sumber, lokasi dan karakteristik dari statistik basis datanya. Untuk basis data yang cukup besar apakah signifikansi dapat tercapai apabila proses optimisasinya dilakukan secara spesifik dan parsial, serta bagaimana pengaruh nilai selectivity factor dari statistik basis data yang cukup besar terhadap proses optimisasi dalam operasi join query.
1.3. Tujuan Penelitian Tujuan
penelitian ini adalah menganalisis pengaruh optimisasi query
dalam basis data terdistribusi secara spesifik dan parsial dilihat dari karakteristik basis datanya secara teoritis yang didukung secara empiris oleh percobaan. Menganalisis teknik formulasi relasi aljabar relasional untuk proses optimisasi query dan mencari signifikansi query berdasarkan biaya yang disetarakan dengan waktu berupa runtime hasil eksekusi query disesuaikan dengan DBMS, hardware dan karakteristik dari statistik basis data yang digunakan. 1.4. Manfaat Penelitian Manfaat penelitian ini untuk memberi wawasan tentang analisis optimisasi query secara parsial disesuaikan dengan karakteristik statistik basis data, hardware dan software yang digunakan. Dan diharapkan dapat membantu users atau programmer dalam menganalisis dan menentukan formula-formula optimisasi query.
3 1.5. Ruang Lingkup Ruang Lingkup dalam penelitian ini yaitu menguraikan proses optimisasi query menggunakan fasilitas DBMS Optimizer menggunakan algoritma NestedLoops-Join,
Block-Nested-Loops-Join,
Sort-Merge-Join
dan
Hash-Join.
Melakukan percobaan proses optimisasi query menggunakan tabel data peserta asuransi PT. Taspen, jumlah record terkecil 1,2 juta dan terbesar 3,8 juta, proses eksekusi dilakukan menggunakan software DBMS MYSQL pada jaringan komputer client-server FMIPA-UNPAD Jatinangor.
BAB II TINJAUAN PUSTAKA 2.1.
Basis Data Terdistribusi
2.1.1. Sistem Basis Data Terdistribusi Dalam pengelolaan basis data terdapat dua sistem basis data, yaitu Basis Data Terpusat ( Centralized ) dan Basis Data Terdistribusi ( Distributed ). Perbedaan utama antara sistem basis data terpusat dan terdistribusi adalah jika pada sistem basis data terpusat, data ditempatkan di satu lokasi saja dan semua lokasi lain dapat mengakses data di lokasi tersebut, sedangkan pada system basis data terdistribusi, data di tempatkan di banyak ( lebih dari satu ) lokasi, tetapi menerapkan suatu mekanisme tertentu untuk membuatnya menjadi satu kesatuan basis data, dan hal ini berbeda dengan system basis data terpisah (Isolated) yang mana dalam sistem basis data terpisah, basis data ditempatkan di banyak lokasi, tetapi tidak saling berhubungan sama sekali. Menurut
Özsu MT, Valduriez P. (1999) Basis Data Terdistribusi
didefinisikan sebagai berikut : Suatu Basis Data Terdistribusi ( DDBS ) adalah suatu koleksi beberapa basis data yang secara logika saling berhubungan dan terdistribusi dalam suatu jaringan komputer, sedangkan Sistem Basis Data Manajemen Terdistribusi ( D-DBMS ) adalah Perangkat Lunak yang mengatur Basis Data Terdistribusi (DDB) dan menyediakan suatu mekanisme akses yang membuat distribusi ini dapat diketahui oleh pemakai. Jadi
Sistem Basis Data Terdistribusi ( DDBS )= DDB+ D-DBMS
Lokasi-lokasi penempatan basis data dapat terlihat dalam Gambar 1.
5
Site 2 Site 1 Site 3
Site 4
Communication Network
Site 4
Gambar 1. Lingkungan Basis Data Terdistribusi ( Valduriez P. 1999) 2.1.2. Arsitektur Sistem Basis Data Terdistribusi Dalam arsitektur basis data terdistribusi konsep basis data relasional lebih banyak digunakan, karena dalam operasionalnya dapat disesuaikan dengan sistem basis data terpusat, secara formal relasional basis data terdistribusi mencakup : Global Level, Fragmentation Level dan Allocation Level ( Kuijk 2000 ) dan hal ini dapat terlihat dalam Gambar 2 berikut.
6
Distributed Database Systems Global Schema
Site Independent
Fragmentation Schema
Allocation Schema
Site dependent
Site 1
Site 2
Site n
Gambar 2 : Arsitektur Sistem Basis Data Terdistribusi (Kuijk 2000)
- Global Level : suatu skema basis data secara global yang menggambarkan basis data terdistribusi yang seolah-olah tidak seluruhnya terdistribusi. - Fragmentation level : suatu skema fragmentasi yang menggambarkan suatu pemetaan antara relasi individu dengan fragmentasinya - Allocation Level : suatu skema alokasi yang menggambarkan pemetaan antara fragmen individu dimana basis data disimpan Dalam melakukan fragmentasi terdapat kriteria-kriteria yang harus dipenuhi, yaitu : Reconstruction Condition, Completeness Condition dan Disjointness Condition (Kuijk 2000)
7 Jika R adalah tabel relasi, Ai adalah atribut dari R, r adalah record dari R dan Fi kondisi dari operasi seleksi, maka hasil fragmentasi dapat direkonstruksi terlihat dalam Tabel 1. Tabel 1: Fragmentasi Horizontal, Vertical dan Mixed Fragmentasi (Kuijk 2000). Type
Partitioning
Horizontal
Reconstruction
r(Ri ) = σ Fi (r (R))
Vertical
( )
n r (Ri ) = U r Ri i =1
n r ( Ri ) = ⋈ πAi (r (R ))
r(Ri ) = π Ai (r (R))
i=1
Mixed
2.2
(
)
r(Ri ) = π Ai σ Fi (r ( R))
n 1 r (Ri ) = U r Ri1 ⋈…⋈ … i =1 1
( )
n k U r Rik i =1 k
( )
Konsep Aljabar Relasional. Relasi aljabar adalah bahasa prosedural, dan salah satu cara untuk
membangun relasi satu atau lebih relasi berdasarkan konsep aljabar. Dalam basis data relasional relasi aljabar mempelajari bagaimana struktur properti dan kendala-kendala akan menjadi dasar dalam operasi basis data, formulasi query dipetakan pada relasi aljabar dan sejauh mana pendekatan teori set digunakan. Bahasa query memiliki sejumlah operasi yang memanfaatkan satu atau beberapa tabel/relasi basis data sebagai masukkan dan menghasilkan sebuah tabel/relasi basis data yang baru sebagai keluarannya. Operasi dasar dalam Aljabar Relasional antara lain mencakup : Select, Project, Cartesian-Product, Union, Set-Difference (Kuijk 2000). Konsep optimisasi query dalam Aljabar Relasional yang banyak digunakan adalah operasi-operasi yang berhubungan dengan operasi join. Dalam tesis ini ditampilkan sejumlah contoh dengan menggunakan skema tabel relasi berikut :
peserta (notsp : integer, tgl_lhr : date, tmt_pst : date, gapok : integer) pensiun(nopen : integer, nama : string, tgl_kej : date) pmk_k1(notsp : integer, nopen : integer , tgl_kej : date)
8 Skema dari tabel-tabel relasi di atas ditunjukkan pada segmen Tabel 2, Tabel 3, Tabel 4 dan Tabel 5. Tabel 2. : Segmen Tabel peserta S1
notsp
tgl_lhr
tmt_pst
gapok
010013098
12/31/1955
1/1/1975
832000
010018391
12/18/1952
3/1/1973
932000
Tabel 3 : Segmen Tabel peserta S2
notsp
tgl_lhr
tmt_pst
gapok
010018391
12/18/1952
3/1/1983
932000
010018826
3/30/1966
3/1/1971
732000
010022921
8/29/1955
10/1/1975
632000
Tabel 4 : Segmen Tabel pmk_ke1 R1
notsp
Nopen
tgl_kej
010013098
0000007700
12/31/1999
010022921
0000008880
12/23/1989
010018391
0000009990
13/21/1990
Tabel 5 : Segmen Tabel pensiun B1
nopen
Nama
tgl_kej
0000007700
Nangkuh
12/31/1999
0000008880
Abdul Hadi
12/23/1989
0000009990
Siddik
13/21/1990
2.2.1. Selection Operasi Selection digunakan untuk memilih subset record-record dari tabel sebuah relasi yang memenuhi pilihan. Kondisi harus berupa formula yang proporsional. Tata cara penulisan yang digunakan pada operasi ini adalah :
σp (R)
atau
σ<selection condition> (R)
9 p adalah <selection condition> berupa predikat pada atribut-atribut di R, dan R adalah tabel/relasi yang akan diakses oleh operasi selection. Jika merujuk Tabel 2 pada tabel peserta, perintah mengambil baris data (record) peserta yang tanggal lahirnya ’9/9/1969’, maka operasi ini dapat dituliskan
σ tgl_lhr = ‘9/9/1969’ (peserta) 2.2.2. Projection Operasi
Projection
dilakukan
untuk
memilih
atribut-atribut
dari
tabel/relasi. dan dapat mengambil atribut satu atau lebih. Tata cara penulisan pada operasi ini adalah :
Π
(R) Atribut list adalah daftar atribut yang akan ditampilkan yang ada di R. Misalkan pada Tabel 2 yaitu dalam tabel peserta akan ditampilkan notsp dan tgl_lhr, untuk semua baris data yang ada pada tabel tersebut, maka perintahnya adalah :
Πnotsp,tgl_lhr(peserta) Dapat pula menampilkan berupa hasil operasi/query. Misalkan akan ditampilkan notsp dan tgl_lhr dngan tmt_pst pada tanggal ’1/1/1975’ saja, maka operasi seleksi dan projeksi harus digunakan secara bersamaan, seperti berikut :
Πnotsp,tgl_lhr (σ tmt_pst= ’1/1/1975’ (peserta)) 2.2.3. Join. Operasi Join adalah untuk menggabungkan lebih dari satu tabel/relasi. Operasi Join dilambangkan dengan “⋈”
dan digunakan untuk
mengkombinasikan hubungan record-record dari dua relasi
kedalam record
tunggal. Pada umumnya operasi PROJECT pada dua relasi R(A1,A2,…An) dan S(B1,B2,…Bm) ditunjukkan oleh :
R⋈
(S)
10 Hasil dari Join adalah sebuah relasi Q dengan n + m atribut Q(A1,A2,…An, B1,B2,…Bm). Q mempunyai satu record untuk masing-masing kombinasi dari record, satu dari R dan satu dari S. Dalam join, hanya kombinasi-kombinasi dari record-record yang memenuhi kondisi join yang akan tampak pada hasil. Kondisi Join ditentukan oleh atribut-atribut dari relasi R dan S dan evaluasi untuk tiap kombinasi dari record-record Bentuk dari kondisi Join secara umum adalah : AND AND … AND dimana tiap kondisi adalah bentuk dari Ai θ Bj. Ai adalah sebuah atribut dari R dan Bj adalah sebuah atribut dari S. Ai dan Bj mempunyai domain yang sama, dan θ (theta) adalah salah satu dari operator-operator pembanding {<, ≤, ≠, ≥, >,}. Operasi Join dengan sebuah kondisi join yang umum disebut dengan theta join. Contoh :
(R ⋈c S) = σc (R x S)
Jadi, ⋈ ditentukan untuk menjadi sebuah cross product diikuti dengan satu selection, Jika diperhatikan c condition dapat merujuk ke atribut baik R maupun S. Referensi ke sebuah atribut dari sebuah relasi, misalnya R , dapat berdasarkan posisi (dari bentuk Ri) atau berdasarkan nama dan bentuk Rname, merujuk pada Tabel 2 dan Tabel 4, maka hasil dari S1 ⋈S1.notsp
notsp
tgl_lhr
tmt_pst
gapok
notsp
nopen
tgl_kej
010018391 12/31/1955 1/1/1975 832000 010022921 0000008880 12/23/1989 010018826 12/18/1952 3/1/1973 932000 010022921 0000008880 12/23/1989
11
2.2.3.1. Cross Join Operasi Cross Join yang juga biasa disebut dengan Cross Product atau Cartesian Product dilambangkan dengan “ X “ yang juga merupakan sebuah kumpulan operasi biner. Contoh (R1 X S1) operasinya memungkinkan untuk menggabungkan data dari dua buah tabel atau hasil query yang berakibat semua record di R1 dipasangkan dengan semua record di S1 dan hasil operasi akan memuat semua atribut yang ada di R1 dan di S1 dan operasi ini bersifat komutatif. Operasi Cross Join umumnya tidak berdiri sendiri, tetapi digunakan bersama operasi lainnya, seperti operasi seleksi dan proyeksi dengan berbagai bentuk sesuai kebutuhan, sebagaimana dapat dilihat dalam contoh berikut : Akan diambil data dari penggabungan tabel S1 dan R1 untuk tmt_pst=‘1/11975’
dan tgl_kej = ‘12/23/1989’
operasinya dapat dituliskan
sebagai berikut :
σ tmt_pst= ’1/1/1975’ ∧ tg_kej = ’ 2/23/1989’ ∧ S1.notsp =R1.notsp ( S1 X R1) 2.2.3.2. Natural Join Sebuah query yang melibatkan operasi Cartesian Product umumnya menggunakan operasi seleksi untuk memberikan hasil query yang diinginkan. Contoh : cari dari semua peserta yang telah pensiun dan tampilkan nama dan tanggal kejadian, notsp diambil dari gabungan Tabel 4 (pmk_ke1) dan Tabel 5 (pensiun). Mula-mula akan menggunakan operasi Cartesian Product tabel
pensiun yang menyimpan data nama dan nopen kemudian dari tabel pmk_ke1 yang menyimpan data notsp, kemudian menyeleksi yang sesuai dengan kriteria yang diminta yaitu no_tsp dari Tabel 4 yaitu tabel pmk_ke1 dan Tabel 5 yaitu tabel pensiun
Πnama,notsp,tgl_kej (σ PMK.nopen=Pensiun.nopen (pmk_ke1 X pensiun)) Bentuk di atas dapat disederhanakan dengan operasi natural join yang menggabungkan operasi cartesian product dan operasi seleksi dengan menggunakan simbol ⋈ , operasi natural join membentuk sebuah cartesian product dari kedua argumennya, lalu menetapkan sebuah seleksi untuk baris-baris data yang memiliki kesamaan nilai untuk atribut-atribut yang muncul di kedua
12 argumennya dan akhirnya mengabaikan data-data duplikat dan perintahnya sebagai beikut :
Πnama,notsp,tgl_kej (pmk_ke1 ⋈ pensiun)) Secara formal, jika S1 memiliki himpunan atribut s dan R1 memiliki himpunan atribut r, maka dapat didefinisikan :
S1 ⋈ R1 =Πs Dimana
r(
σs1.a1=r1.a2 ∧ s1.a1=r1.a2∧...∧ s1.an=r1.an(S1 X R1)
s = domain atribut dari S1 r = domain atribut dari R1 s
r = { a1, a2, a3, …, an }
Jika tidak ada atribut yang sama di kedua ekspresi S1 dan R1 atau s
r =0, maka :
S1 ⋈ R1 = S1 X R1 2.2.4 Operasi Himpunan Operasi Himpunan yang digunakan adalah Union, Intersection dan Difference.
2.2.4.1. Union (R S) Operasi ini untuk menggabungkan data dari dua kelompok baris data (row) yang sejenis (memiliki hasil proyeksi yang sama) Simbol dari operasi ini adalah : R
S
Atribut notsp terdapat pada Tabel 5 (pensiun) dan Tabel 4 (pmk_ke1), sehingga notsp pada kedua tabel tersebut dapat diproyeksikan dengan operasi Union :
Πtglkej (pensiun)
Πtglkej (pmk_ke1)
Pada operasi Union R S terdapat dua syarat yang dipenuhi yaitu : 1) S dan R harus memiliki jumlah atribut yang sama. 2) Domain dari atribut ke i dari S dan atribut ke i dari R haruslah sama, dan harus berlaku untuk semua atribut di S dan R
13
2.2.4.2. Intersection (R
S)
Operasi Intersection digunakan untuk menyatakan atau mendapatkan irisan (kesamaan anggota) dari dua buah kelompok data dari suatu tabel atau hasil query. Tata penulisannya adalah (R
S) yang ekivalen dengan penggunaan operasi dasar
Set-Difference S – ( S – R ). Contoh untuk mendapatkan notsp mana saja yang sama-sama dipunyai, baik dari Tabel 2 (peserta) maupun Tabel 4 (pmk_ke1), query tersebut dapat dipenuhi dengan operasi
Πnotsp (Peserta) Πnotsp (pmk_ke1) 2.2.4.3. Difference (R - S) Operasi difference merupakan pengurangan data di tabel/hasil proyeksi pertama R oleh data/hasil proyeksi yang kedua S Simbolnya adalah : R – S Ketentuannya sama dengan operasi Union yaitu harus mempunyai jumlah atribut yang sama baik di S maupun di R, contoh :
Πtglkej (pensiun) – Πtglkej (pmk_ke1) 2.3. Proses Query Dalam Database Manajemen System (DBMS) akses data dapat dilakukan dengan berbagai macam cara. Ada banyak plan (rencana) yang dapat diikuti oleh DBMS dalam memproses dan menghasilkan jawaban sebuah query. Semua rencana pada akhirnya akan menghasilkan jawaban (output) yang sama tetapi pasti mempunyai biaya yang berbeda-beda. Kebanyakan aplikasi secara nyata adalah permintaan-permintaan secara langsung dari user yang memerlukan informasi tentang bentuk maupun isi dari basis data. Apabila permintaan user terbatas pada sekumpulan query-query standar, maka query-query tersebut dapat dioptimisasi secara manual oleh pemrograman. Tetapi bagaimanapun juga, sebuah sistem optimisasi query otomatis menjadi penting apabila query-query khusus dinyatakan dengan
14 menggunakan bahasa query yang digunakan secara umum seperti Structure Query Language (SQL). Optimisasi query memberikan suatu pemecahan untuk menangani masalah dengan cara menggabungkan sejumlah besar teknik-teknik dan strategi, yang meliputi transformasi-transformasi logika dari query-query pada sistem file penyimpanan data. Setelah ditransformasikan, sebuah query dipetakan ke dalam sebuah langkah-langkah operasi untuk menghasilkan data-data yang diminta.
Query Language (SQL)
SCANNER ( Mengecek sintaks SQL keyword )
PARSER ( Mengecek sintaks SQL keyword )
Menghasilkan parse tree QUERY OPTIMIZER ( Mengecek sintaks SQL keyword )
Menghasilkan Query plan CODE GENERATOR / INTERPRETER
Menghasilkan kode Query QUERY PROCESSOR (Eksekusi Query)
Hasil Query Gambar 3. Tahapan proses sebuah Query (Swamy 2001)
15 Sebuah query yang diekspresikan dalam sebuah bahasa query tingkat tinggi seperti SQL mula-mula harus dibaca, diuraikan dan disahkan (scanning, parsing, validating). Query tersebut kemudian dibentuk menjadi sebuah struktur data yang biasa disebut dengan query tree. Kemudian
DBMS merencanakan
sebuah
strategi eksekusi
untuk
mendapatkan kembali hasil dari query dari file-file basis data. Tahapan-tahapan proses dari sebuah query didalam sebuah sistem basis data ditunjukkan pada Gambar 3 dan berikut penjelasan dari masing-masing tahapan :
Scanner melakukan identifikasi (pengenalan) perintah-perintah seperti SQL keywords, atribut, dan relation name. Proses ini disebut dengan scanning.
Query
Parser
mengecek
validitas
query
dan
kemudian
menterjemahkannya dalam bentuk internal yaitu ekspresi relasi aljabar atau parse tree proses ini disebut dengan parsing.
Query Optimizer memeriksa semua ekspresi-ekspresi aljabar yang sama untuk query yang diberikan dan memilih salah satu dari ekspresi tersebut yang terbaik yang memiliki perkiraan paling murah. Dengan kata lain, tugas dari query optimizer adalah menghasilkan sebuah rencana eksekusi dan proses ini disebut optimisasi query.
Code Generator atau Interpreter mentransformasikan rencana akses yang dihasilkan oleh optimizer ke dalam kode-kode. Setelah itu, kode-kode tersebut dikirimkan ke dalam query processor untuk dijalankan.
Query Processor melakukan eksekusi query untuk mendapatkan hasil query yang diinginkan. Bagian yang diarsir pada Gambar 3 adalah optimizer yang sudah
disediakan oleh DBMS. Tahapan proses query pada Gambar 3 tersebut adalah untuk memberikan gambaran yang jelas tentang bagaimana pada umumnya sebuah query diproses di dalam sebuah Data Base Manajemen Sistem .
16 2.4. Optimisasi Query Optimisasi Query adalah suatu proses untuk menganalisis query untuk menentukan sumber-sumber apa saja yang digunakan oleh query tersebut dan apakah penggunaan dari sumber tersebut dapat dikurangi tanpa merubah keluaran. Atau dengan kata lain bahwa optimisasi query adalah sebuah prosedur untuk meningkatkan strategi evaluasi dari suatu query untuk membuat evaluasi tersebut menjadi lebih efektif (Richard 2000). 2.5. Prinsip Optimisasi Query Prinsip Optimisasi Query terdapat dalam pemilihan strategi query, dan terletak pada penentuan strategi operasi Join. Bahasa query salah satu yang biasa digunakan, misalnya SQL, tetapi untuk beberapa kasus khusus, suatu query dapat mempunyai hubungan dengan pemetaan aljabar. Bentuk yang lebih sederhana sangat diperlukan dari pada bentuk-bentuk aljabar tersebut, dan diasumsikan bahwa operasi gabungan adalah salah satu operasi relasi aljabar ( Ken 2000). Menurut Richard Vlach (2000),
optimisasi query dalam basis data
terdistribusi, ada dua aspek yang sangat penting, yaitu : 1.
Tranmisi data dan kontrol data ke tempat tujuan sangat dipengaruhi oleh bentuk komunikasi, dan dapat memperlambat keseluruhan proses.
2.
Pengolahan data secara paralel transmisi data dapat mempercepat respone
Optimisasi Query adalah proses untuk menunjukkan bahwa baik total biaya maupun total waktu suatu query diminimalkan. Total biaya diukur oleh penggunaan sumber daya sistem seperti CPU atau bentuk komunikasi data. Respone time optimizers yaitu untuk meminimalkan respone time dalam sebuah query bersama-sama secara paralel.
17 Menurut Özsu MT, Valduriez P. (1999 ) formulasi untuk meminimalkan biaya (cost function) adalah :
Total Cost = I/O cost + CPU cost + communication cost ........................... (2.1) Dimana
I/O cost = unit disk I/O cost + no. of disk I/Os CPU cost = unit instruction cost + no. of instruction Communicatin cost = message initiation + transmition
Formula (2.1) masing-masing bagiannya dapat mempunyai bobot yang berbeda tergantung dari terdistribusinya data, antara lain : - Apabila proses query menggunakan Wide Area Networks (WAN), maka biaya komunikasi sangat dipengaruhi low bandwidth, low speed dan high protocol overhead.
Sedangkan
algoritma-algoritma
yang
ada
pada
umumnya
mengabaikan komponen biaya. - Apabila menggunakan Local Area Networks (LAN), biaya komunikasi dan pengiriman data tidak mempengaruhi, tetapi total biaya dari fungsi-fungsi yang digunakan harus dipertimbangkan.
2.6. Metoda Optimisasi Query Biaya query sangat dipengaruhi oleh dua hal, yaitu proses secara lokal dan transmisi data antar lokasi, karena berkaitan dengan fungsi biaya. Proses perhitungan diperlukan untuk
menghasilkan biaya query yang akurat secara
parsial. Karakteristik relasi secara lokal harus diketahui dalam optimisasi waktu. Beberapa diantaranya adalah kardinalitas dari relasi secara lokal, banyaknya byte dalam nilai atribut, dan nilai selectivity factor
yang terdapat dalam relasi
diperlukan. Optimisasi
proses
pengolahan
data
secara
global
dengan
cara
menggunakan metoda secara lokal, dalam pelaksanaannya adalah mengoperasikan atas kedua proses, yaitu memproses data lokal dan memproses data secara lokal yang datang dari lokasi lain. Besar biaya untuk optimisasi lokal pada umumnya didasarkan pada banyaknya akses dari memori sekunder, ukuran buffers dan ukuran operand. Data yang akan dioperasikan secara lokal dan tambahan struktur data lokal seperti indek, hash tabel akan dapat mempercepat proses secara lokal.
18 Operasi join adalah operasi yang sangat mahal. Dan diketahui bahwa metoda operasi join secara lokal adalah : nested-loops, sort-merge dan hash join. Walaupun ada metoda optimisasi query global yang mempertimbangkan proses lokal, ongkos proses secara lokal pada umumnya dapat diabaikan jika dibandingkan dengan ongkos transmisi data. Selama transmisi data dioptimisasi, jelas asumsinya bahwa nilai waktu selama transmisi bergantung pada jumlah data yang dialirkan. Perhitungkan
respone
time
yang
minimal,
optimisasi
global
memanfaatkannya secara paralel dan mencoba untuk memperkecil transmisi pada alur yang ”paling buruk”. Operasi secara lokal yang membatasi relasi lokal harus dieksekusi secepat mungkin. Kemudian, utamakan pada optimisasi pada berbagai operasi join. Metoda optimisasi secara dinamis dapat memilah perencanaan ekseskusi query pada tahapan eksekusi. Pada awalnya rencana eksekusi didasarkan pada penilaian hasil secara parsial. Perubahan selama tahap eksekusi didasarkan pada ukuran secara parsial dan perubahan mengarahkan pada sisa query yang akan diproses. (Richard 2000)
2.6.1. Optimisasi Query Basis Formula Optimisasi basis formula (Rule Based) biasa juga disebut heuristic optimization adalah optimisasi query dengan menggunakan aturan-aturan heuristic dan dijalankan pada rencana query secara logika yang terdiri dari urutan operasioperasi relasional yang biasanya digambarkan sebagai query tree
2.6.2. Optimisasi Query Basis Biaya Dalam optimisasi basis biaya dapat digunakan solution space dan cost function yaitu dengan total time atau total cost. Hal ini dapat mereduksi setiap biaya ( dalam setiap termin waktu ) semua komponen satu persatu kemudian melakukan proses optimisasi untuk setiap utilitas dari setiap sumber-sumber daya sehingga meningkatkan kinerja sistem. Faktor-faktor yang terdapat dalam total cost yang ditunjukkan oleh persamaan (2.1) menghasilkan total cost factor dan tergantung dari arsitektur jaringan yang digunakan. Untuk penggunaan Wide Area Network dipengaruhi
19 oleh inisiasi pesan dan transmisi cost sangat tinggi, dan biaya pemrosesan secara lokal lambat (kecuali untuk mainframe dan mini komputer). Demikian juga rasio dari komunikasi ke I/O costs adalah = 20 : 1, tetapi untuk penggunaan Local Area
Network komunikasi dan proses secara lokal biayanya lebih sedikit dengan rasio dari komunikasi ke I/O costs = 1 : 1,6 ( Valduriez P. 1999). Dalam menghitung Respone time dapat mengerjakan hal-hal yang mungkin secara paralel sehingga dapat meningkatkan total time karena meningkatnya total aktifitas, dan berdasarkan rumus (2.1)
Respone time = CPU time + I/O time + communication time ...................... (2.2) Dimana CPU time = unit instruction time * no. of sequential instruction I/O time = Unit I/O time * no.of sequential I/Os Communication time = unit msg initiation time + no.of sequential msg + unit transmition time * no.of sequential bytes
2.6.3. Fungsi Biaya dari Statistik Basis data Untuk melihat cost factor yang utama dalam statistik basis data menurut (Valduriez P. 1999), ukuran relasi dari basis data memiliki nilai selectivity factor untuk setiap relasi dalam setiap operasi, yaitu :
1. Operasi joins card(R⋈ S) SF (R,S) = -------------------------
.............................................
(2.3)
size(R) = card(R)*length
............................................
(2.4)
card(σ F (R)) = SF σ (F) *card(R)
............................................
(2.5)
...............................
(2.6)
card(R)*card(S)
2. Operasi Selection
dimana 1 S F σ (A = value) = --------------------card(∏A (R))
20 max(A) – value S F σ (A > value) = --------------------------
...............................
(2.7)
...............................
(2.8)
max(A) – min(A) value – max(A) S F σ (A < value) = --------------------------max(A) – min(A) SF σ (p(A i ) ∧ p(A j )) = SF σ (p(A i )) *SF σ (p(A j )
.......
(2.9)
SF σ (p(A i ) ∨ (p(A j )) = SF σ (p(A i )) + SF σ (p(A j )) – (SF σ (p(A i )) *SF σ (p(A j )))
...............................
SF σ (A ∈ value) = SF σ (A= value) * card(value)
(2.10)
...................
(2.11)
.......................................................
(2.12)
3. Projection card(Π A (R))=card(R)
4. Cartesian Product card(R × S) = card(R) .card(S)
............................................
(2.13)
Batas atas: card(R ∗S) = card(R) + card(S) ................................
(2.14)
Batas Bawah: card(R ∗S) = max{card(R), card(S)} ....................
(2.15)
5. Union
6. Set Difference Batas atas: card(R–S) = card(R)
............................................
(2.16)
Batas bawah: 0
............................................
(2.17)
7. Join Dalam kasus khusus: A adalah primary key dari R dan B adalah foreign key dari S; card(R⋈ A=B S) = card(S)
.........................................................
(2.18)
Lebih umum: card(R⋈ S) = SF⋈ .card(R) *card(S)
.................................
(2.19)
21
2.6.4. Optimizer DBMS MySQL MySQL melakukan optimisasi melalui fasilitas query optimizer. Query optimizer secara rutin memeriksa dan melakukan transformasi semua ekspresiekspresi aljabar yang sama dan memilih salah satu dari ekspresi yang terbaik dan memiliki perkiraan paling murah dengan menggunakan fungsi optimize() dari optimizer MySQL dan secara rutin diaplikasikan pada semua tipe query ([email protected]. 1998-2007 MySQL AB ). MySQL Optimizer melakukan proses optimisasi menggunakan 5 langkah, yaitu : 1.
Menentukan tipe join. Sistem menetapkan tabel yang akan dibaca dalam join, kemudian menetapkan primary index secara berurutan dalam equality relation dengan nilai indek tidak null, menetapkan jangkauan dari indek dan membaca seluruh tabel menurut indek secara berurutan.
2.
Menentukan metode akses dan join Metode akses dan join dilakukan dengan Query Execution Plan (QEP) dan mencari rencana yang terbaik dengan menggunakan prosedur find_best() dari MySQL Optimizer.
3.
Menentukan rentang indek dari tipe join Tipe join dalam tabel diberi rentang indek agar optimizer dengan mudah mengambil data dari tabel yang berada dalan rentang indek.
4.
Menentukan indek dari tipe join Tipe join dalam tabel diberi indek, agar optimizer dengan mudah mengambil data berdasarkan indek.
5.
Menentukan indek dari tipe merge join Indek merge join digunakan bilamana kondisi atribut join dalam tabel dapat dibentuk kedalam beberapa kondisi indek yang terdiri dari cond_1 OR cond_2 ... OR cond_N. Jika cond_1 OR cond_j , dan dapat digabung menjadi satu rentang yang sama, maka diberikan satu rentang indek, hal ini dilakukan untuk menghindari dan mengeliminasi duplikasi data.
BAB III METODOLOGI DAN RANCANGAN PENELITIAN
3.1. Metodologi Penelitian Sejak tahun 1960 an penelitian-penelitian tentang basis data sudah dimulai dan dikembangkan sesuai kebutuhan, terutama dengan menggunakan metode kuantitatif, namun perkembangan software dan hardware terus-menerus berkembang ke arah otonomi komputasi sehingga metode penelitian-penelitian dikembangkan kepada metode kualitatif atau gabungan dari metode tersebut yang diarahkan kepada komputasi tersdistribusi. Materi dan bahan penelitian dikumpulkan dari internet dan buku-buku teks pustaka. Informasi dari internet yang digunakan adalah jurnal atau paper penelitian-penelitian sejenis yang membahas permasalahan basis data terdistribusi atau permasalahan-permasalahan yang berhubungan dengan optimisasi query. Sumber utama data penelitian yang akan diolah adalah tabel-tabel relasi dari peserta asuransi PT. Taspen berlandaskan pada jumlah record dengan jumlah data terkecil 1,2 juta record dan terbesar 3,8 juta record. Diasumsikan jumlah data cukup besar memenuhi syarat untuk diteliti, karena penelitian-penelitian yang banyak dilakukan masih dalam kapasitas puluhan ribu record. Penelitian tidak melihat bentuk dan isi tabel, sehingga update tabel kepada isi tabel yang mutakhir tidak dilakukan. Pada saat bersamaan, dikumpulkan berbagai informasi mengenai data yang dapat diakses oleh user dari tabel-tabel tersebut. Kemudian dianalisa proses penggunaan tabel-tabel tersebut yang terkait dengan proses optimisasi. Data-data dan informasi yang telah dikumpulkan kemudian dikompilasi untuk melakukan percobaan. Perintah-perintah query yang diuji coba adalah perintahperintah query untuk melakukan join sesuai kebutuhan. Penelitian juga dilakukan untuk mencari solusi yang terbaik atau mencari signifikansi optimisasi query dengan sumber-sumber hardware dan software yang digunakan. Penelitian fokus kepada karaktersitik basis data secara spesifik dengan jumlah record disesuaikan pada sumber hardware dan software yang digunakan dalam percobaan, dengan harapan dapat menghasilkan rancangan optimisasi query yang optimal.
23 3.2. Sistematika Penelitian dan Pembahasan Pada dasarnya tesis ini membahas empat bagian yaitu : Bagian pertama menggambarkan tentang perkembangan basis data terdistribusi, yang mungkin saat ini terdapat pada perusahaan-perusahaan besar dan mempunyai banyak cabang di beberapa tempat dan menjelaskan kemungkinan permasalahan yang akan timbul dalam proses transaksi-transaksi antar perusahaan yang melibatkan join query. Bagian kedua mencoba memberikan gambaran tentang konsep basis data terdistribusi dengan segala sumber-sumbernya, membahas teori-teori aljabar relasional yang digunakan dalam analisis teori optimisasi query mencakup : Select, Project, Cartesian-Product, Union, Set-Difference. Bagian ketiga menjelaskan langkah-langkah yang dilakukan dalam penelitian awal dan kajian teoritis, kemudian menjelaskan langkah-langkah penelitian
dalam
mengkaji
perkembangan
optimisasi
query,
berikutnya
menjelaskan langkah-langkah menganalisis dengan implementasi menggunakan formula-formula untuk mengevaluasi optimisasi query. Bagian keempat membahas tentang formulasi masalah dan penentuan tujuan, kemudian bagaimana menganalisis algoritma dari metode-metode NestedLoops-Join, Block–Nested-Loops-Join, Sort-Merge-Join dan Hash Join yang merupakan fasilitas dari DBMS, berikutnya menjelaskan perhitungan biaya query dari algoritma tersebut secara teoritis yang didukung percobaan. Bagian kelima membahas percobaan yang dilakukan dalam mengeksekusi perintah-perintah query, menggambarkan hasilnya berupa tabel-tabel
yang
diilustrasikan pada grafik-grafik hasil eksekusi dan dijadikan bahan kajian untuk menganalisis optimisasi query hasil implementasi.
24 3.3. Tahapan Proses Penelitian Tahapan penelitian untuk proses optimisasi query adalah urutan langkah yang harus dikerjakan dalam melakukan optimisasi sebuah proses query. Tahapan proses penelitian tersebut secara umum dijelaskan dalam Tabel 7.
Tabel 7 : Tahapan proses penelitian PROSES
BAHASAN MATERI
PENELITIAN Persiapan
Pelaksanaan
SUMBER REFERENSI
- Pengumpulan materi dan bahan - Penyusunan proposal - Pengumpulan data penelitian Penelitian awal dan kajian teoritis * formulasi masalah dan penentuan tujuan * penentuan kebutuhan penelitian * kajian-kajian perintah query yang dapat dilaksanakan dalam kasus yang dibahas * pendefinisian model dalam representasi query dalam bentuk aljabar relasional Studi intensif * me-review perkembangan penelitian-penelitian tentang optimisasi query * studi tentang optimisasi query terdistribusi Studi implementatif * mengkonversi perintah query, dengan menggunakan cartesian product dari klausa FROM, menggabungkan dan memilih kondisi-kondisi dari klausa WHERE dari proyeksi-proyeksi klausa SELECT * membagi nilai-nilai penyimpanan data dari record-record untuk memilih satu atau lebih caloncalon prosedur untuk diimplementasikan dalam query. * menghasilkan rencana-rencana query
Studi kepustakaan dan akses internet Studi kepustakaan dan akses internet
Akses internet
Studi kepustakaan
25 PROSES
BAHASAN MATERI
PENELITIAN Pelaksanaan
Penyelesaian
SUMBER REFERENSI
* mencari signifikansi optimisasi query berdasarkan biaya yang disetarakan dengan waktu runtime dilihat dari karakteristik basis data Pengembangan formulasi otpimisasi * penentuan optimisasi secara spesifik * penentuan formulasi biaya * penentuan karakteristik statistik basis data yang dikaji * penentuan signifikansi optimisasi query yang dilakukan Pengujian dan evaluasi * analisis kajian signifikansi optimisasi query berdasarkan biaya, dilihat dari karakteristik basis data secara spesifik - Penyusunan laporan - Dokumentasi
Studi kepustakaan
Studi kepustakaan
Studi kepustakaan dan Percobaan
Tahapan-tahapan proses penelitian tersebut diuraikan pada bagan alir Gambar 4 berikut.
26
Mulai
PERSIAPAN
- Pengumpulan materi dan bahan - Pengumpulan data awal penelitian - Penyusunan proposal
Tidak
Studi implementatif * mengkonversikan perintah query dengan menggunakan cartesian product dari klausa FROM, menggabungkan dan memilih kondisi-kondisi dari klausa WHERE dari proyeksi- proyeksi klausa SELECT * membagi nilai-nilai penyimpanan data dari record- record untuk memilih satu atau lebih calon-calon prosedur untuk diimplementasikan dalam query. * menghasilkan rencana-rencana query * mencari signifikansi optimisasi query berdasarkan biaya, dilihat dari karakteristik basis data secara spesifik
Pengembangan formulasi otpimisasi * penentuan optimisasi secara parsial * penentuan formulasi biaya * penentuan karakteristik statistik basis data yang dikaji * penentuan signifikansi optimisasi query yang dilakukan
Proposal disetujui ?
Ya PELAKSANAAN Tidak Penelitian awal dan kajian teoritis * formulasi masalah dan penentuan tujuan * penentuan kebutuhan penelitian * kajian-kajian perintah query yang dilaksanakan dalam kasus yang dibahas * pendefinisian model dalam representasi query dalam bentuk aljabar relasional
Hasil query Signifikan ?
Ya Pengujian dan evaluasi * analisis kajian signifikansi optimisasi query berdasarkan biaya, dilihat dari karakteristik basis data spesifik
PENYELESAIAN Studi intensif * me-review perkembangan penelitian-penelitian tentang optimisasi query * studi tentang optimisasi query terdistribusi * studi tentang signifikansi optimisasi query
Penyelesaian - Penyusunan laporan - Dokumentasi
Selesai
Gambar 4 : Bagan alir proses penelitian.
BAB IV HASIL DAN PEMBAHASAN 4.1.
Formulasi Masalah dan Penentuan Tujuan. Dalam bagian ini dibahas tentang formulasi masalah dan penentuan tujuan
yang akan dicapai, diperlukan tahapan-tahapan analisis yang akan timbul selama proses optimisasi query dijalankan. Aspek utama pemilihan strategi query untuk sistem basis data terdistribusi terletak dalam penentuan strategi operasi join. Strategi operasi join dapat menggunakan fasilitas optimizer yang terdapat dalam DBMS, antara lain : Metode Nested-Loops-Join, Block–Nested-Loops-Join, Sort-Merge-Join dan Hash Join. Tetapi tidak semua DBMS dapat melakukan strategi dengan metode-metode tersebut. Dalam penelitian ini penulis mencoba membahas secara spesifik optimisasi join query sesuai dengan karakteristik basis data dan spesifikasi komputer yang digunakan. Untuk memformulasi masalah terdapat beberapa faktor yang harus dipertimbangkan dalam sistem terdistribusi, antara lain : •
Biaya / waktu untuk transmisi data dan biaya operasi join.
•
Potensi peningkatan unjuk kerja karena adanya sejumlah simpul yang dapat melaksanakan query secara paralel.
•
Karakteristik basis data.
Biaya / waktu transfer data dalam jaringan dan transfer data ke dan dari disk, sangat berbeda-beda tergantung pada tipe jaringan yang dipilih dan kecepatan akses dari disk yang digunakan. Sementara unjuk kerjanya akan sangat tergantung pada desain basis data terdistribusi yang kita terapkan serta strategi DBMS dalam melakukan transformasi setiap perintah query. Ambil sebuah contoh perintah query sederhana, “ tampilkan semua baris data dalam tabel pst_ke1 “. Pemrosesan query tersebut menjadi tidak sederhana, jika tabel tersebut telah direplikasi atau difragmentasi atau sekaligus direplikasi dan difragmentasi. Jika tabel pst_ke1 tersebut ternyata telah direplikasi, maka dapat dengan mudah untuk memenuhi query tersebut dengan memilih salah satu simpul tempat tabel pst_ke1 berada, dan kemudian mengeksekusi query. Jika
28 tabel tersebut tidak difragmentasi, pemilihan simpul didasarkan pada simpul yang memberikan ongkos transmisi data paling rendah. Akan tetapi jika tabel pst_ke1 tersebut difragmentasi dan ditempatkan di berbagai simpul yang berbeda, maka harus melakukan operasi join atau union untuk merekontruksi isi seluruh tabel pst_ke1. Penerapan operasi di atas disamping tergantung pada bentuk perintah query, tergantung pada jenis fragmentasi yang diterapkan pada tabel terlibat. Jika tabel pst_ke1 telah difragmentasi horizontal, perlu rekonstruksi dengan menggunakan operasi union, tetapi jika fragmentasi dilakukan vertikal , maka rekonstruksi operasi natural join yang harus digunakan. Dalam berbagai kasus dan berbagai keadaan banyak pilihan strategi dan metode
yang harus
dipetimbangkan, tetapi besar kemungkinan akan memperberat upaya optimisasi query yang kadang-kadang menjadi tidak praktis untuk diterapkan. Percobaan dilakukan untuk menganalisis permasalahan menggunakan tabel peserta asuransi, dengan tabel hasil fragmentasi dari peserta didekomposisi (spesialisasi) menjadi tabel pst_ke1 dan tabel pstaktif, tabel peserta pensiun (pstpens) didekomposisi menjadi tabel pmk_ke1 dan tabel pmk_fd1. Tabel-tabel yang digunakan dalam percobaan hanya menggunakan 5 buah tabel yang terdiri dari tabel pstaktif, pst_ke1, pstpens, pmk_ke1 dan pmk_fd1. Hal ini dilakukan dengan pertimbangan efisiensi ruang penyimpanan. Untuk lebih jelasnya situasi tabel secara keseluruhan dapat dilihat pada kamus data di bawah ini dan Diagram E-R ditunjukkan pada Gambar 5. Kamus data dari 5 buah tabel yang dianalisis antara lain : a. pst_ke1 ( no_tsp, tgl_lhr, tmt_pst, kd_bup) b. pstaktif ( nippa, tgl_lhr, tmt_pst, sex, gaji_pokok, blth_gapok, suskel, pangkat) c. pmk_ke1 ( no_tsp, tmt_pst, tglhr_ymk, tgl_kej, kd_kej,) d. pmk_fd1 ( nippa, tmt_pst, kd_kej, tgl_klim, tgl_trans, pangkat, gaji_pokok, thp, suskel, nama_ymk, tglhr_ymk, rp_hak) e. pstpens ( nopen, jenis, kp030, kp040, kp080, kp180, kp380, kp570, kp550, kp710).
29 Tabel 8 : Tabel informasi data tabel relasi Nama Tabel
Jumlah
Jumlah
(Alias)
Atribut
Record
Kapasitas memory (MB)
Panjang
Key
Record (Byte)
pst_ke1 ( P )
4
3.873.324
132
30
no_tsp
pstaktif ( F )
8
3.619.423
165
50
nippa
pmk_ke1 ( E )
5
1.401.040
58
44
no_tsp
pmk_fd1 ( D )
13
1.261.239
107
117
nippa
pstpens ( N )
10
1.264.037
70
61
nopen
peserta
d
o
pst_ke1
pstaktif
peserta pensiun (pstpens)
Keterangan : d
: disjoint
o
: non disjoint
o
Pmk_ke1
Pmk_fd1
: subset Gambar 5 : Diagram E-R dari keseluruhan tabel peserta
30 Tanda ‘d’ dalam konektor lingkaran menunjukkan dekomposisi (spesialisasi) disjoint dan tidak terdapat relasi spesialisasi antar tabel, menunjukkan non disjoint dan
dan tanda ‘o’
terdapat relasi spesialisasi antar tabel dan
menunjukkan perbedaan tiap entitas, tanda ‘ С ‘ menunjukkan subset
(Begg C.
1996). 5 buah tabel yang digunakan dalam percobaan lebih dijelaskan pada Diagram E-R Gambar 6 dan Gambar 7.
no_tsp
nama_peserta
alamat_peserta
peserta no_tsp
tgl_lhr
sex
gapok
o pst_ke1
tmt_pst
kd_bup
pstaktif
blth_gapok
suskel
pangkat
Gambar 6 : Diagram E-R tabel peserta spesialisasi menjadi tabel pst_ke1 dan tabel pstaktif.
31
kp040
kp080
kp180
kp570
pstpens
jenis
kp550
nopen
no_tsp
kp710
tmt_pst
tgl_klim
o
pmk_ke1
tglhr_ymk
tgl_kej
tgl_trans
pmk_fd1
kd_kej
rp_hak
tglhr_ymk pangkat nama_ymk gapok suskel thp
Gambar 7 : Diagram E-R tabel pensiun (pstpens) spesialisasi menjadi tabel pmk_ke1 dan tabel pmk_fd1.
4.2.
Formulasi Optimisasi Query.
32 Pada bagian ini bagaimana proses query diformulasi, dianalisis dan dievaluasi. Data deskriptif atau metadata disimpan dalam tabel khusus yang disebut katalog sistem yang digunakan untuk menemukan cara terbaik dalam mengevaluasi query. Secara umum query tersusun dari beberapa operator, algoritma pada operator relasi dapat dikombinasikan dengan berbagai cara untuk mengevaluasi query. Setiap perintah query sebaiknya dievaluasi dengan melalui formulasi tree aljabar relasional. Keterangan pada masing-masing node menggambarkan metode akses untuk masing-masing tabel dan metode implementasi untuk tiap operator relasional. Penulis mencoba mempertimbangkan contoh dengan menggunakan skema berikut : a. pst_ke1 (no_tsp, tgl_lhr, tmt_pst, kd_bup) b. pstaktif (nippa, tgl_lhr, tmt_pst, sex, gaji_pokok, blth_gapok, suskel, pangkat) Tabel di atas masing-masing record dari pst_ke1 panjangnya 30 byte, dengan asumsi sebuah halaman yang akan masuk dalam buffer dapat menangani 100 record pst_ke1, maka dalam pst_ke1 terdapat 3.873.324 record akan mempunyai 38.730 halaman dalam buffer, demikian juga bahwa masing-masing record dari pstaktif panjangnya 50 byte, mempunyai 3.619.423 record, sebuah halaman dapat menangani 80 record pstaktif, sehingga mempunyai 45.242 halaman. Perhatikan query SQL berikut ini : SELECT
F. tmt_pst
FROM
pst_ke1 P, pstaktif F
WHERE
P.no_tsp = F.nippa AND P. kd_bup= ‘100’ AND F. pangkat >= ‘3A’
Query di atas dapat dinyatakan dalam aljabar relasional seperti berikut : Πtmt_pst (σ kd_bup = ’100’ ∧ pangkat >=’3A’ (pst_ke1 ⋈ no_tsp= nippa pstaktif)
33 Pernyataan di atas dapat dinyatakan dalam bentuk join tree pada Gambar 8. Sebagian pernyataan aljabar dapat menentukan bagaimana mengevaluasi query pertama, join dihitung secara alami dari pst_ke1 dan pstaktif, kemudian melakukan seleksi dan akhirnya memproyeksikan atribut tmt_pst. Untuk proses evaluasi harus dijelaskan implementasi untuk masing-masing operasi aljabar yang terlibat. Sebagai contoh dapat digunakan page-oriented dari nested-loop-join yang sederhana
dengan
pst_ke1
sebagai
tabel
pertama
yang
dibaca,
dan
mengaplikasikan seleksi dan proyeksi untuk masing-masing record pada hasil join, hasil dari join tersebut sebelum seleksi dan proyeksi tidak disimpan seluruhnya.
Πtmt_pst
(proyeksi)
σ kd_bup = ’100’∧ pangkat >=’3A’
(proses seleksi)
⋈ no_tsp = nippa
(baca file)
pst_ke1
(proses join)
pstaktif
(baca file)
Gambar 8 : Rencana evaluasi query dari join tree Pada Gambar 8 ditunjukkan bahwa pst_ke1 adalah tabel pertama dibaca, terletak disebelah kiri dari join tree atau disebut tabel luar dari operator join.
34 Mendahulukan operasi seleksi sebelum operasi join Untuk melakukan operasi Join secara heuristik sebaiknya tabel dibuat dengan ukuran sekecil mungkin, dan operasi seleksi dilakukan lebih awal. Sebagai contoh seleksi kd_bup =”100” hanya melibatkan atribut dari pst_ke1 dan dapat diaplikasikan pada pst_ke1 sebelum join. Sama halnya dengan seleksi pangkat >= ”3A” hanya melibatkan atribut dari pstaktif, dapat diaplikasikan pada pstaktif sebelum join. Andaikan bahwa seleksi didahulukan dengan menggunakan scan file, hasil dari masing-masing seleksi ditulis ke tabel temporer pada disk, selanjutnya tabel temporer digabung menggunakan metode sort-merge-join seperti ditunjukkan pada Gambar 9. Hasil eksekusi menunjukkan perbedaan waktu yang cukup signifikan, untuk jumlah record masing-masing 10.000 record eksekusi medahulukan seleksi lebih cepat dari pada eksekusi mendahulukan join. Penurunan waktu eksekusi mencapai 37,45 %
Πtmt_pst
(proyeksi akhir)
⋈
(lakukan Sort-Merge-Join)
no_tsp = nippa
kd_bup = ”100” (baca : tulis ke tabel temp T1)
(baca file) pst_ke1
pangkat >=”3A” (baca : tulis ke tabel Temp T2)
pstaktif
(baca file)
Gambar 9: Rencana evaluasi query mendahulukan operasi seleksi
35 4.2.1. Analisis Selectivity Factor dari Karakteristik Basis Data. Dalam hal ini penulis mengemukakan statistik basis data sesuai dengan karateristiknya, yaitu relasi yang digunakan berupa tabel basis data dengan nilai kardinalitas cukup besar. Statistik basis data dengan operasi Join untuk tabel relasi difragmentasi dengan jumlah record 10.000 per tabel pada tabel (pst_ke1 dan pstaktif, serta pmk_ke1 dan pmk_fd1), berdasarkan persamaan (2.3) adalah:
card( P⋈ F ) a.
card(P⋈ no_tsp=nippa F) = card(F)
SF1 (P, F) = ------------------------- = --------------------------------------card( P ) * card( F )
card( P ) * card( F )
283 =-------------------------- ---
= 0,00000283
10,000 * 10,000 card( E⋈ D ) b.
SF1 (E, D)
= ------------------------card( E ) * card( D ) card(E⋈ no_tsp=nippa D) = ------------------------------------card( E ) * card( D ) 240 = --------------------------10.000*10.000 =
0,0000024
Untuk Selectivity Factor operasi Selection berdasarkan persamaan (2.4) adalah : card(σ F (R)) = SF σ (F) *card(R) dimana
36 1 S F σ (A = value) = --------------------card(∏A (R)) 1 1 S F σ (kodebup = “100”=1) = --------------------- = ------------= 0,000102 card(∏kodebup (P))
9776
Dari hasil perhitungan Selectivity Factor menghasilkan angka 0,00000283 dan 0,0000024 dan 0,000102,
menunjukkan bahwa operasi join dan operasi
seleksi di atas cukup baik, karena nilai selectivity-nya mendekati 0, dan jumlah tabel-tabel di atas secara spesifik tidak berpengaruh terhadap nilai
record
selectivity factor 4.2.2. Analisis Optimisasi Secara Spesifik. Perintah query menggunakan operator relasional sebenarnya mempunyai banyak persamaan (ekivalen). Beberapa teknik yang sederhana dapat digunakan untuk mengembangkan algoritma dari masing-masing operator yaitu : •
Indektasi : Jika syarat seleksi atau join telah ditentukan, maka gunakan indek untuk memeriksa record yang memenuhi syarat saja.
•
Iterasi : Proses secara iterasi yaitu memeriksa semua record dalam tabel input satu per satu, jika kita hanya memerlukan beberapa field dari masing-masing record dan terdapat indek yang key-nya berisi semua field tersebut akan diambil.
•
Partisi : Mempartisi record pada sort key, memungkinkan dekomposisi sebuah operasi menjadi serangkaian operasi partisi yang lebih tidak mahal. Sorting dan hashing merupakan dua teknik yang umum digunakan.
Dalam menganalisis proses optimisasi secara spesifik operasi query dijalankan menggunakan algoritma dengan partisi relasi-relasi menggunakan metode-metode Nested-Loops-Join, Block-nested-loops-join, Sort-Merge-Join, dan Hash Join.
37 Penulis mencoba membahas tentang operasi join dari sebuah contoh kasus sederhana di bawah ini: SELECT
*
FROM
pst_ke1 P, pstaktif F
WHERE
P. no_tsp = F. nippa Gambar 10 : Contoh Perintah Join
Query ini dapat dinyatakan sebagai operasi ( P ⋈ F ) dan perintahnya sangat sederhana, meskipun join dapat didefinisikan sebagai cross product yang diikuti oleh seleksi dan proyeksi, join lebih sering muncul dalam praktek dibandingkan dengan cross product murni. Cross product biasanya lebih besar daripada hasil join. Dalam hal ini sangat penting untuk mengimplementasikan join tanpa menampilkan cross product. Untuk mengimplementasikan join dapat digunakan algoritma simple-nested-loops-join dan block-nested-loops-join, yang pada dasarnya menghitung semua record dalam cross product dan membuang record yang tidak memenuhi syarat join. Selanjutnya menghindari perhitungan cross product dengan menggunakan partisi. Secara intuitif jika syarat join terdiri dari equality, maka record dalam dua relasi dapat dianggap tercakup dalam partisi, sehingga hanya record yang berada dalam partisi yang sama yang dapat join satu sama lain atau record dalam partisi tersebut berisi nilai yang sama dalam kolom join. Indeks nested-loops-join men-scan salah satu relasi, untuk masingmasing record didalamnya, dengan menggunakan indeks pada kolom join dari relasi kedua untuk menemukan record yang berada dalam partisi yang sama. Jadi hanya subset relasi kedua yang dibandingkan dengan record tertentu dari relasi pertama, seluruh cross-product tidak dihitung. Penulis mencoba membahas join dari dua relasi P dan F, dengan syarat join Pi = Fj, menggunakan tanda posisional. Diasumsikan M halaman dalam P dengan PP ( page P) record per halaman M, dan N halaman dalam F dengan PF (page F) record per halaman dalam N, dimana P adalah tabel relasi pst_ke1 dan F adalah tabel relasi pstaktif.
38 4.2.3.1 Nested-Loops-Join Algoritma yang paling sederhana adalah record pada saat dievaluasi nested loops. Algoritma men-scan relasi P tabel relasi pertama, untuk tiap record p ∈ P, kemudian men-scan semua relasi kedua dalam F . Biaya men-scan P adalah M I/O, dimana M adalah jumlah halaman dalam P, kemudian men-scan F sebanyak
PP
M kali, dan tiap scanning biayanya N I/O, dimana N adalah jumlah
halaman dalam F (Raghu 2003), jadi biaya totalnya adalah : M + PP.M.N .......................................(4.1). Dimana :
pP
: adalah jumlah record per halaman dari M
M: jumlah halaman dari relasi P N : jumlah halaman dari relasi F Algoritmanya dapat dinyatakan sebagai berikut : For each record p ∈ P do For each record f ∈ F do if pi == fj then add (p,f) to result
Gambar 11 : Algoritma Simple-Nested-Loops-Join (Raghu 2003) Algoritma Simple-Nested-Loops-Join tidak memanfaatkan fasilitas buffer. Andaikan memilih P menjadi pst_ke1 dan F menjadi pstaktif , maka nilai M adalah 38.730 halaman dan pP adalah 100, kemudian nilai N adalah 45.242 PF adalah 80. Menurut Ramakrishna Raghu & Gehrke Johanes (2003) merujuk ke rumus (4.1.), biaya simple-nested-loops-join adalah : 38.730 + 100 * 38.730 * 45.242 halaman I/O ditambah biaya penulisan hasil yang dalam hal ini diabaikan, maka besarnya biaya paling sedikit : 38.730 + 100 * 38.730 * 45.242 = 175.222.304.730 = 175.222.340.730 halaman I/O Biaya tersebut sangat mengejutkan, apabila biaya I/O 10 ms ( setara dengan 0,001666667 detik atau 1/360000 jam = 0,0000028 jam ) per halaman pada perangkat keras terbaru, maka join ini akan memerlukan waktu :
39 175.222.340.730 * 0,001666667 = 292.037.293 detik 292.037.293 / 60
=
4.867.288,216 menit
4.867.288,216 / 60
=
81121,470 jam
81.121,470 / 24
=
3380,061 hari
3.380,061261 / 365
=
9,260 tahun
Biaya tersebut sangat tidak realistik, mungkin dapat diperbaiki dengan menggunakan join-page-at-a-time. Untuk tiap halaman P, kita dapat mengambil halaman F dan mengisi record (p,f) untuk semua record yang memenuhi syarat p
∈ P halaman dan f ∈ F halaman. Atas dasar tersebut biaya M untuk men-scan P, seperti sebelumnya, akan tetapi F hanya di-scan M kali. Jadi biaya total adalah : M + M * N, maka perbaikan page-at-a-time memberikan perkembangan faktor PF. Dalam contoh join dari relasi pst_ke1 dan pstaktif, biaya dapat dikurangi, yaitu : 38.733 + 38.733 * 45.242 = 1.752.397.119 halaman I/O 1.752.397.119 * 0,0000028 = 4867,769775 jam 4867,769775 / 24
= 202,9 hari
Perkembangan ini menekankan pentingnya partisi yang ditunjukkan pada operasi page-at-a-time dan dapat meminimalkan disk I/O, sehingga terjadi perubahan yang signifikan.
4.2.3.2 Block-Nested-Loops-Join Algoritma simple-nested-loops-join tidak memanfaatkan halaman buffer B secara efektif. Andaikan CPU mempunyai memory yang cukup untuk mempertahankan relasi P, diasumsikan paling sedikit terdapat dua halaman buffer ( B-2) ekstra yang tersisa. Kemudian menggunakan salah satu dari halaman buffer ekstra untuk men-scan relasi F. Untuk tiap record
f
∈ F, memeriksa P dan
menghasilkan record ( p, f ) untuk record f yang memenuhi syarat (misalnya, pi=fj ). Halaman buffer ekstra kedua digunakan sebagai buffer output. Tiap relasi hanya di scan sekali, sehingga biaya total : I/O M + N . Berikutnya mempartisi relasi P menjadi blok yang dapat masuk ke halaman buffer, kemudian men-scan semua F untuk tiap blok P. P adalah relasi
40 pertama, cukup di-scan sekali, dan F adalah relasi kedua dan di-scan banyak kali. Jika memori tersedia sebanyak B halaman buffer, maka P dapat masuk kedalam B-2, dan men-scan relasi dalam F dengan menggunakan satu dari dua halaman yang masih ada. Kita dapat menulis record (p, f), dimana p ∈ P blok,
f
∈ F
halaman, dan pi = fj dengan menggunakan halaman buffer terakhir untuk menulis output. Cara yang efisien untuk menemukan pasangan record yang cocok (misalnya record yang memenuhi syarat join pi = fj ) adalah membentuk main memory hash tabel ( yaitu tabel sementara hasil join tersimpan dalam memori utama) untuk blok P. Karena hash tabel melibatkan pertukaran ukuran blok P yang efektif, dalam hal ini jumlah record per blok dikurangi. Algoritma block-nested-loops dideskripsikan pada Gambar 12 dan penggunaan buffer dalam algoritma diilustrasikan pada Gambar 13. foreach block of B-2 pages of P do foreach page of F do { for all maching in-memory record p ∈ P block dan
f
∈ F –page,
add (p,f) to result }
Gambar 12. : Algoritma Block-nested-loops-Join (Raghu 2003) Biaya strategi ini adalah M I/O untuk membaca P (di-scan sekali), F di-
⎡ M ⎤ scan sebanyak ⎢ kali, ini diperlukan berkenaan dengan in-memory hash ⎢ B − 2 ⎥⎥ tabel (yaitu tabel yang akan dibuat sementara dalam memori utama berisi tabel hasil join), dan biaya tiap scan N I/O. ⎡ M ⎤ Jadi biaya totalnya adalah = M + N * ⎢ ⎢ B − 2 ⎥⎥ dimana :
..................................... (4.2).
M
: Jumlah halaman pada tabel relasi pertama P
N
: Jumlah halaman pada tabel relasi kedua F
B
: Blok halaman buffer
41 Relasi P dan F
Hasil join
Fungsi hash h
* * * Hash tabel untuk blok P1 { k < B -1 halaman}
***
*** Buffer Input Untuk men-scan F
Buffer output
Gambar 13: Penggunaan buffer Block-nested-loops-Join (Raghu 2003 ) Relasi pst_ke1 adalah relasi pertama P dan pstaktif adalah relasi kedua F. Asumsikan bahwa kita mempunyai buffer yang cukup untuk menahan in-memory hash tabel untuk 100 halaman pst_ke1, sehingga harus men-scan pst_ke1 dengan biaya 38.730 I/O. Untuk tiap 100 halaman blok pst_ke1, harus di-scan pstaktif. Oleh karena itu akan menampilkan 10 halaman scan dari pstaktif, yang masingmasing biayanya adalah 45.242 I/O, maka biaya totalnya adalah : 38.730 + 10 * 45.242 = 491.150 halaman I/O jika tersedia buffer yang cukup untuk menahan 90 halaman pst_ke1, maka harus men-scan pstaktif 38.730 / 90 = 430 kali, dan biaya total akan menjadi : 38.730 + 430 * 45.242 = 19.509.380 halaman I/O Jika kemampuan perangkat keras I/O mempunyai kecepatan 10ms, maka total biaya di atas adalah : 19.509.380 * 0,0000028 = 54,2 jam 542 / 24 = 2,26 hari. Hasilnya menunjukkan lebih baik dari metode nested-loops-join yang tidak memanfaatkan blok buffer.
42
4.2.3.3 Sort- Merge-Join Dasar pemikiran dari Sort-Merge-Join adalah mengurutkan kedua relasi pada atribut yang akan melakukan join, lalu mencari record yang memenuhi syarat p ∈ P dan
f
∈ F , dengan menggabungkan dua relasi. Langkah pengurutan
mengelompokkan semua record yang mempunyai nilai sama dalam kolom join, untuk memudahkan dalam mengidentifikasi partisi, atau grup record dengan nilai sama dalam kolom join. Sort-Merge-Join memanfaatkan partisi dengan membandingkan record P dalam partisi hanya dengan record F dalam partisi yang sama (dengan semua record F), dengan demikian dapat menghindari perhitungan cross-product P dan F. (Pendekatan secara spesifik hanya bekerja untuk syarat equality join). Jika relasi telah diurutkan berdasarkan atribut join, selanjutnya memproses penggabungan secara terperinci. Pertama scanning relasi P dan F untuk mencari record yang memenuhi syarat (misalnya, record Tp dalam P dan Tf , dalam F sehingga Tpi=Tfj). Kedua, scanning dimulai pada record pertama dalam tiap relasi dan scan P selama record P terbaru kurang dari record F terbaru (mengacu pada nilai atribut join ). Ketiga, scan F selama record F terbaru kurang dari record P terbaru, dan memilih sampai menemukan P record Tp dan F record Tf dengan syarat Tp i = Tf j. Pada saat menemukan record Tp dan Tf yaitu Tp i = Tf j, hasilnya perlu dikeluarkan. Tetapi pada kenyataannya dapat terjadi beberapa record P dan beberapa record F mempunyai nilai yang sama. Disini mengacu pada record tersebut sebagai partisi P terbaru dan partisi F terbaru. Untuk tiap record p dalam partisi P terbaru, scan semua record
f
dalam partisi F terbaru yang akan
menghasilkan record hasil join ( p, f ), kemudian dilanjutkan scan P dan F, mulai dengan record pertama dan mengikuti partisi yang baru diproses. Algoritma Sort-Merge-Join ditunjukkan pada Gambar 14 menetapkan nilai record pada variable Tp, Tf dan Gf, menggunakan nilai eof untuk menandai bahwa tidak ada record lagi dalam relasi yang sedang di-scan. Subscripts mengidentifikasi field, Tpi menyatakan atribut ke i dari record Tp. jika Tp mempunyai nilai eof, maka setiap perbandingan yang melibatkan TPi didefinisikan
43 untuk mengevaluasi kondisi false, dengan syarat join yang menjadi equality pada atribut no_tsp. Relasi pst_ke1 diurutkan pada no_tsp, relasi pstaktif diurutkan pada atribut nippa. Tahap penggabungan pada algoritma sort-merge-join mulai dengan scan pada record pertama pada masing-masing relasi. Dahulukan scan pst_ke1, karena nilai no_tsp = ‘131909235’ pada pst_ke1, pada contoh segmen tabel
pst_ke1 (lihat Tabel 9), kurang dari nilai nippa = ‘131909236’ pada pstaktif. Record kedua pst_ke1 mempunyai nilai ‘131909236’, sama dengan nilai nippa record pstaktif terbaru, pada pstaktif (lihat Tabel 10). Hasil join mendapatkan sepasang record, satu dari pst_ke1 dan satu dari pstaktif, dalam partisi terbaru (berisi nippa = no_tsp =’131909236’). Karena hanya mempunyai satu record
pst_ke1 dengan nilai no_tsp=’131909236’ dan satu record dari pstaktif, maka selanjutnya menuliskan satu record hasil pada partisi keluaran. Tahap selanjutnya pemposisikan scan pstaktif pada record pertama dengan nippa = ‘131909237’. Sama halnya dalam memposisikan scan sebelumnya, karena record kedua tersebut mempunyai nilai yang sama dengan no_tsp record ketiga yaitu '131909237' dari pst_ke1, maka jika telah ditemukan partisi yang cocok, tulis lagi record yang dihasilkan oleh partisi ini pada partisi keluaran. Atribut no_tsp dan nippa sama-sama key sehingga paling banyak hanya satu record yang cocok dalam
partisi.
Selanjutnya
no_tsp=’131909238’,
scanning
scanning
pada
pstaktif
pst_ke1
diposisikan
diposisikan
pada
pada record
nippa=’131909238’, tahap penggabungan selanjutnya dilakukan dengan cara yang sama.
44 Proc smjoin( P, F, ‘Pi = Fj ) if P not sorted on atribut i, sort it; if F not sorted on atribut j, sort it; Tp = first record in P;
// range over P
Tf = first record in F;
// range over F
Gf = first record in F;
// start of current F-partition
while Tp ≠ eof and Gf ≠ eof do { while Tpi < Gfj do Tp = next record in P after Tp; while
// continue scan of P
Tpi > Gfj do Gf = next record in F after Gf;
Tf = Gf ;
// continue scan of F // needed in case Tpi ≠ Gfj
while Tpi = = Gfj do {
// process current P partition
Tf = Gf ;
// reset F partition scan
while Tfj = Tpi do {
// process current P record
add (Tp, Tf) to result;
// output joined records
Tf = next record in F after Tf ; } Tp =next record in P after Tp; } Gf = Tf ;
// advance F partition scan // advanced scan of P // done with current P partition
// initialize search for next F partition
}
Gambar 14 : Algoritma Sort-Merge-Join (Raghun 2003)
45 Tabel 9 : Contoh Segmen Tabel pst_ke1
NO_TSP
TGL_LHR TMT_PST KD_BUP
131909235 10/11/1964 01/03/1990 310 131909236 12/02/1966 01/03/1990 312 131909237 05/04/1964 01/03/1990 310 131909238 12/02/1964 01/03/1990 312 131909986 13/04/1955 01/03/1990 100 131909987 10/01/1963 01/03/1990 100 131909988 29/10/1965 01/03/1990 100 131909989 25/07/1968 01/03/1990 100 131909990 12/07/1970 01/03/1990 100 131909991 10/08/1967 01/04/1990 401
Tabel 10 : Contoh segmen Tabel pstaktif NIPPA
TGL_LHR TMT_PST SEX GAJI_POKOK BLTH_GAPOK SUSKEL PANGKAT
131909236 13/02/1966 01/03/1990
L
901500
012001
100
3C
131909237 05/04/1964 01/03/1990
L
828200
082001
101
3B
131909238 12/02/1964 01/03/1990
L
870100
012001
103
3B
131909239 07/05/1966 01/03/1990
P
891900
072002
000
3B
131909240 08/02/1967 01/03/1990
P
870100
082001
101
3B
131909241 28/12/1967 01/03/1990
L
839800
082001
102
3A
131909243 03/08/1962 01/03/1990
P
914200
082001
101
3B
131909244 31/03/1964 01/03/1990
L
870100
082001
102
3B
131909245 05/04/1964 01/03/1990
L
848900
082001
101
3B
131909246 12/10/1965 01/03/1990
L
901500
082001
102
3C
Secara umum, algoritma harus men-scan partisi record dalam relasi kedua dalam F sesering jumlah record dalam partisi yang sesuai dengan relasi pertama P
46
4.2.3.4 Biaya Sort-Merge-Join Biaya sorting P adalah O(M log M) dan biaya sorting F adalah O(N logN). Biaya dari tahap penggabungan adalah M + N jika tidak terdapat partisi F di-scan beberapa kali (atau halaman yang diperlukan ditemukan dalam buffer setelah tahap pertama). Pendekatan ini sangat menarik jika setidaknya terdapat satu relasi yang telah disortir pada atribut join atau mempunyai clustered indek pada atribut join. Perhatikan join dari relasi pst_ke1 dan pstaktif, asumsikan bahwa kita mempunyai 100 halaman buffer, kemudian dapat mengurutkan pstaktif dalam dua tahap. Tahap pertama menghasilkan 10 run tiap 100 halaman yang diurutkan secara internal. Tahap kedua menggabungkan 10 run tersebut untuk menghasilkan relasi yang disortir. Karena membaca dan menulis dalam tiap tahap biaya sortingnya adalah : 2 * 2 * 38.730 = 154..920 halaman I/O Sama halnya kita dapat menyortir pstaktif dalam dua tahap dengan biaya 2 * 2 * 45.242 = 180.968 halaman I/O Selain itu tahap kedua algoritma sort-merge-join meminta scan tambahan kedua relasi , jadi total biaya adalah : 154.920 + 180.968 + 38.730 + 45.242 = 419.860 halaman I/O. Apabila kecepatan perangkat keras 10 ms, maka : 419.860 * 0,0000028 = 1,166277778 jam
4.2.3.5 Hash Join Algoritma
Hash
join,
seperti
algoritma
sort-merge-join,
yaitu
mengidentifikasi partisi dalam P dan F dalam tiap partisi dan dalam tahap equality berikutnya membandingkan record dalam partisi P hanya dengan record dalam F yang sesuai untuk menguji syarat equality join. Berbeda dengan sort-merge-join, hash join menggunakan hashing untuk mengidentifikasi partisi dalam pengurutan. Tahap partisi ini dapat disebut juga sebagai building dari hasil hash join serupa dengan partisi dalam proyeksi hash based dan diilustrasikan dalam Gambar 15, dan tahap equality atau disebut matching diilustrasikan dalam Gambar 16.
47 Partisi
Partisi Orisinil
1 Input
1
2
Fungsi hash h
2
*** ***
*** B-1
B-1
Buffer memory utama B
disk
disk
Gambar 15: Tahap Partisi Proyeksi Hash-Based. (Raghu 2003) Gambar di atas menandakan bahwa jika terdapat sejumlah besar (misalkan
B halaman buffer relatif) dengan jumlah halaman P, maka pendekatan hash-based sangat perlu, karena terdapat dua tahap pekerjaan yaitu : partisi dan eliminasi duplikat. Dalam tahap partisi dipunyai satu halaman buffer input dari B-1 halaman buffer output. Relasi P dibaca
ke dalam halaman buffer input, setiap satu
halaman. Halaman input diproses sebagai berikut : Untuk tiap record, diproyeksikan sesuai atribut yang diinginkan, dan kemudian mengaplikasikan fungsi hash h pada kombinasi dari semua atribut yang ada. Fungsi h dipilih sehingga record didistribusikan secara seragam pada satu B-1 partisi; dan terdapat satu halaman output per partisi. Setelah proyeksi record diisi ke halaman buffer output yang di hash menurut h. Pada akhir tahap partisi, mempunyai B-1 partisi, masing-masing berisi kumpulan
record
menggunakan
nilai
hash
umum
(dihitung
dengan
mengaplikasikan h pada semua field, dan hanya mempunyai field yang diinginkan. Dua record yang tercakup dalam partisi yang berbeda dijamin tidak menjadi duplikat karena mereka mempunyai nilai hash yang berbeda. Jadi jika
48 dua record merupakan duplikat, maka mereka berada dalam partisi yang sama. Dalam tahap eliminasi duplikat dibaca B-1 partisi satu per satu untuk menghilangkan duplikat, dasar pemikirannya adalah membentuk in-memory hash tabel seperti memproses record untuk mendeteksi duplikat. Untuk tiap partisi dihasilkan dalam tahap pertama : 1. Baca partisi satu halaman per satu waktu. Hash tiap record dengan mengaplikasikan fungsi hash h2 ( ≠ h ) pada kombinasi dari semua field dan kemudian menyisipkannya ke dalam in-memory hash tabel. Jika record baru meng-hash nilai yang sama seperti beberapa record yang ada, maka bandingkan keduanya untuk memeriksa apakah record baru tersebut merupakan duplikat, buang duplikat saat ditemukan. 2. Setelah semua partisi telah dibaca, tulis record dalam hash tabel (dimana tidak terdapat duplikat) ke file hasil, kemudian bersihkan in-memory hash tabel untuk mempersiapkan partisi berikutnya. Untuk persoalan join idenya adalah meng-hash kedua relasi pada atribut join, menggunakan fungsi hash h yang sama. Jika meng-hash tiap relasi (idealnya secara seragam) ke dalam k partisi, maka yakin bahwa record P dalam partisi i hanya dapat join dengan record F dalam partisi j yang sama. Pengamatan ini dapat digunakan untuk pengaruh yang baik, yaitu dapat membaca dalam partisi secara lengkap dari relasi P yang lebih kecil dan hanya men-scan partisi sesuai dengan F untuk kesesuaian. Dan selanjutnya tidak perlu memperhatikan record P dan F lagi. Jadi setelah P dan F di partisi, maka dapat dilakukan join dengan hanya membaca P dan F sebanyak satu kali saja. Dan menyediakan memory yang cukup diperkenankan untuk menyimpan semua record dalam partisi P tertentu. Dalam praktek sistem membentuk in-memory hash tabel untuk partisi P, menggunakan fungsi hash h2 yang berbeda dari h ( karena h2 dimaksudkan untuk mendistribusi record dalam partisi yang berdasarkan h ), untuk mengurangi biaya CPU. Hal ini sangat memerlukan memory yang cukup untuk memegang hash tabel, yang sedikit lebih besar daripada partisi P itu sendiri.
49 Partisi P dan F
Hasil join
Fungsi hash h2
* * * h2
Hash tabel untuk partisi P1 { k < B -1 halaman}
***
*** Buffer Input Untuk men-scan Fi
disk
Buffer output
Buffer memory utama B
disk
Gambar 16: Tahap equality join menggunakan Hash-Join.(Raghu 2003) Algoritma hash join dipresentasikan pada Gambar 17, perhatikan biaya algoritma hash join. Dalam tahap partisi harus men-scan P dan F sekali dan menulisnya sekali. Oleh karena itu biaya tahap ini adalah 2 ( M + N ). Pada tahap kedua men-scan tiap partisi sekali, dengan asumsi bahwa tidak terdapat partisi overflow, dengan besar biayanya adalah : ( M + N ) I/O sehingga dengan demikian biaya total adalah : 3 ( M + N ) dengan asumsi bahwa tiap partisi dapat dimasukkan dalam memory pada tahap kedua. Pada contoh join dari pst_ke1 dan pstaktif biaya total adalah : 3 * ( 38.733 + 45.242) = 251.925 halaman I/O. Apabila unjuk kerja komputer diasumsikan 10 ms per I/O, hash join memerlukan waktu sebesar: 251.925 * 0,0000028 = 0,699791667 jam hal tersebut dikarenakan algoritma hash join memanfaatkan buffer ekstra (inmemory) dan menggunakan variabel dinamis dimana memory yang sudah tidak digunakan dapat dibersihkan.
50 Dari hasil analisis di atas jelas terlihat bahwa algoritma mem-partisi tabeltabel relasi dengan menggunakan metode hash join secara parsial dapat menunjukkan unjuk kerja query secara signifikan. Tetapi prinsip Hash Based harus dirancang sebelum aplikasi digunakan, karena tabel-tabel relasi harus berupa “hash tabel” yang mana terdapat fungsi hash berupa variabel pointer yang dapat menunjuk langsung pada alamat tertentu sesuai keperluan yang dilakukan dalam hash join,
// partition P into k partitions foreach record p ∈ P do read p and it to buffer page h(pi);
// flushed as page fills
// Partition F into k partitions foreach record f ∈ F do read f and it to buffer page h(fj);
// flushed as page fills
// Probing phase for l=1,... , k do { // build in memory hash tabel for Pi, using h2 foreach tuple p ∈ Partition Pi do read p and insert into hash table using h2(pi); // Scan Fl and Probe for matching Pi record foreach record f ∈ Partition Fj do { read f and probe tabel using h2 ( fj ); for matching P record p, output (p,f) } clear hash tabel to prepare for next partition; } Gambar 17. Algoritma Hash-Join (Raghu 2003)
4.2.3. Analisis Signifikansi Optimisasi Query. Proses scanning relasi yang berulang kali dari sebuah partisi akan memerlukan biaya yang mahal. Untuk meningkatkan kesempatan suatu partisi dapat masuk kedalam memory yang tersedia dalam tahap equality, besaran partisi harus diminimalkan dengan memaksimalkan jumlah partisi. Dalam tahap partisi,
51 untuk mem-partisi P (sama halnya dengan F) ke dalam k partisi memerlukan k buffer output dan satu buffer input. Misalkan terdapat B halaman buffer, jumlah maksimum partisi k = B-1, dengan asumsi bahwa ukuran partisi sama, maka ukuran tiap partisi P adalah
M (M adalah jumlah halaman P ). Jumlah halaman B −1
dalam (in-memory hash tabel) partisi terbentuk selama tahap equality adalah cM , dimana c adalah nilai konstanta yang digunakan untuk meningkatkan B −1 ukuran antara partisi dan hash tabel. Dalam tahap equality selain hash tabel untuk partisi P diperlukan halaman buffer untuk scanning partisi F dan halaman buffer untuk keluaran. Maka buffer yang diperlukan sebanyak
B>
c.M + 2 , dan buffer B > c.M , agar algoritma B −1
hash join dapat dilakukan dengan baik. Partisi P diharapkan sesuai dengan tersedianya buffer, sehingga buffer B>
M , maka jumlah halaman buffer yang diperlukan lebih kecil daripada B −1
B > c.M . Resiko akan timbul jika fungsi hash h tidak mempartisi P secara seragam, maka hash tabel untuk satu partisi P atau lebih mungkin tidak dapat masuk ke dalam memory selama tahap equality. Situasi ini secara signifikan dapat menurunkan unjuk kerja. Proyeksi Hash-based adalah salah satu cara untuk menangani masalah overflow partisi, yaitu mengaplikasikan teknik hash join secara berulang pada join partisi P yang overflow dengan partisi F yang bersangkutan. Pertama membagi partisi P dan F ke dalam subpartisi, berikutnya melakukan join subpartisi secara berpasangan.
Semua
subpartisi
P
masuk
ke
dalam
memory
dengan
mengaplikasikan teknik hash join secara berulang, seperti tertulis dalam algoritma pada Gambar 17. Memori ekstra adalah memori yang tersedia dalam memori utama berupa RAM atau chace memori dan metode hybrid hash join adalah salah satu metode yang memanfaatkan memori ekstra. Jika tersedia lebih banyak memory, maka hybrid hash join dapat digunakan.
52 Andaikan bahwa
⎛M ⎞ B > c.⎜ ⎟ , k adalah jumlah partisi yang dapat ⎝ k ⎠
⎛M ⎞ dibentuk. Jika P dibagi menjadi k partisi ukuran ⎜ ⎟ , in-memory hash tabel ⎝ k ⎠ dapat dibentuk untuk tiap partisi. Untuk partisi P ( sama halnya dengan F) menjadi k partisi dibutuhkan k buffer output dan satu buffer input, yaitu k+1 halaman, dan akan menyisakan sebanyak B-(k+1) halaman ekstra selama tahap ⎛M ⎞ partisi. Jika B − (k + 1) > c.⎜ ⎟ , berarti mempunyai cukup memory ekstra selama ⎝ k ⎠ tahap partisi. Metode hybrid hash join adalah membentuk in-memory hash tabel untuk partisi pertama P selama tahap partisi, yang berarti bahwa dapat menulis partisi ke disk. Sama halnya saat mempartisi F, dapat langsung melakukan equality dalam in-memory hash tabel dengan partisi P pertama. Pada akhir tahap partisi telah menyelesaikan equality join, selanjutnya algoritma bekerja seperti dalam hash join. Penghematan melalui hybrid hash join yaitu menghindari untuk menulis partisi pertama P dan F ke disk selama tahap partisi, dan membacanya kembali selama tahap equality. Apabila dilihat contoh pada pst_ke1 yang terdapat 38.730 halaman dalam relasi P lebih kecil dari 45.242 dari relasi F. Jika buffer tersedia B=300 halaman, maka dapat dengan mudah membentuk in-memory hash tabel untuk partisi P pertama saat mempartisi P menjadi dua partisi. Selama tahap partisi P algoritma dapat membaca P dan menulis satu partisi, biayanya adalah: 38.730 + 19.366 = 58.096 halaman I/O Jika diasumsikan bahwa partisi mempunyai ukuran yang sama, kemudian selanjutnya membaca F dan menulis satu partisi, biayanya adalah : 45.242 + 38.730 = 83.972 halaman I/O Pada tahap equality membaca partisi kedua P dan F, biayanya adalah : 19.366 + 38.730 = 58.096 halaman I/O Biaya totalnya adalah : 58.096 + 83.972 + 58.096 = 200.164 halaman I/O. Jika kecepatan 1 halaman I/O memakan waktu 10 ms, maka kecepatan totalnya adalah :
53 200.164 * 0,0000028 = 0,556 jam Dilihat dari hasil perhitungan, terdapat penurunan waktu runtime yang signifikan antara algoritma hash join dengan nilai 0,69 jam dan algoritma hybrid hash join sebesar 0,56 jam , yaitu sebesar ( 0, 69 jam – 0,56 jam = 0,13 jam). Jika mempunyai cukup memori untuk menyimpan in-memory hash tabel untuk semua P, maka penghematannya akan lebih besar. Misalkan jika B> c.N+2, yaitu k = 1, maka dapat membentuk hash tabel ini dan membaca F sekali untuk menyelidiki hash tabel P sehingga biayanya menjadi : 38730 + 45242 = 83.972 I/O. Apabila unjuk kerja komputer mempunyai kecepatan I/O 10 ms, yaitu : 83.972 * 0,0000028 = 0,233 jam Metode hybrid hash join, saat ini untuk DBMS komersial terdapat dalam Oracle, IBM DB2, dan Informix. Analisis perhitungan optimisasi query dengan metode hybrid-hash-join, hasilnya menunjukkan bahwa proses optimisasi query dapat dicapai secara signifikan apabila memory CPU dapat menampung sejumlah buffer dan bucketbucket (in-memory hash tabel dengan sejumlah halaman) yang sedang diproses. Apabila hash tabel tidak dapat dibentuk, maka selama tahap partisi dan tahap equality, hasil query akan selalu ditulis ke disk yang tentunya akan memakan waktu yang cukup lama. Untuk mengatasi proses query yang cukup lama dan menghindari partisi overflow dapat dilakukan fragmentasi horizontal sesuai dengan rentang atau kriteria tertentu, hasil fragmentasi disebar dibeberapa server dan diasumsikan penyebaran data seragam.
54 4.2.4. Analisis Optimisasi query optimizer DBMS MySQL
DBMS MySQL Oprimizer dapat memberikan perkiraan unjuk kerja pecarian dari disk. Untuk tabel-tabel yang kecil dapat mencari baris dalam satu disk secara berurutan. Jika tabel-tabel cukup besar, dapat diperkirakan dengan menggunakan B++ tree index, akan diperlukan langkah pencarian sebanyak i : log(row_count) / log(index_block_length / 3 * 2 / (index_length + data_pointer_length)) + 1 seeks to find a row .............................................. (4.3) dan memerlukan buffer sebanyak : row_count * (index_length + data_pointer_length)*3/2 ............................... (4.4) Dalam MySQL banyak indek dalam block adalah 1024 bytes dan panjang data pointer 4 bytes dan panjang indek 3 bytes. Jika diaplikasikan pada tabel pst_ke1 yang mempunyai record sebanyak 3.873.324, maka dalam tabel pst_ke1
dengan mempunyai panjang data pointer 4 bytes dan panjang indek 3 bytes, berdasarkan persamaan (4.3) akan didapat nilai pencarian sebesar : log(3.873.324 )/log(1024/3*2/(3+4)) + 1 = (6.58880 / 0.07167 ) + 1 = 93 kali pencarian. dan berdasarkan persamaan (4.4), memerlukan buffer sebanyak 3.873.324 * 7 * 3/2 = 40,6 MB Untuk tabel pstaktif mempunyai jumlah record sebesar 3.619.423, akan mempunyai nilai pencarian sebesar : log(3.619.423 )/log(1024/3*2/(3+4)) + 1 = (6.55863 / 0.07167 ) + 1 = 92 kali pencarian dan memerlukan buffer sebanyak 3.619.423 * 7 * 3/2 = 38 MB Proses pencarian satu indek dalam tabel pst_ke1 diperlukan 93 langkah dan memerlukan memori sebanyak 40,6 MB, sedangkan untuk tabel pstaktif pencarian indek diperlukan 92 langkah dengan memerlukan memori sebanyak 38MB. Diasumsikan buffer index digunakan sebanyak 2/3, normalnya proses pencarian dilakukan 2 kali, yaitu untuk update indek dan menulis baris.
i
(http://www.mysql.com/documentation/)
55 Proses selanjutnya melakukan join setelah record mempunyai indek yang sesuai, dan kemudian dilakukan equality join. Untuk menghitung biaya join diperlukan ii : a.
Jumlah blok sebesar : bP = r / bfr
.......................................................................... (4.5)
dimana : r = jumlah record bfr = blocking factor (jumlah record per blok) b.
Selection cardinality, yaitu : Satribut = rP / datribut
.............................................................. (4.6)
dimana : rP = jumlah record dalam tabel pertama datribut = distinct value tabel kedua c.
Biaya algoritma nested loop : Cost = bP + ( bP * bF ) + [ ( js * rP * rF) / bfrF ] ............................. (4.7)
dimana : bp = jumlah blok dalam tabel pertama bF = jumlah blok tabel kedua js = join selectivity sebesar (1/jumlah record tabel kedua) rP = jumlah record dalam tabel pertama rF = jumlah record dalam tabel kedua bfrF = blocking factor dari tabel kedua d.
Biaya algoritma B++ tree indek structure : Cost = bP + (rP * ( XatributF + SatributP ))+[ (js*rP * rF) / bfrF ] ......... (4.8)
dimana : bp = jumlah blok dalam tabel pertama rP = jumlah record dalam tabel pertama XatributF = primary index tabel kedua SatributP = Selection cardinality tabel pertama js = join selectivity sebesar (1/jumlah record tabel kedua) rF = jumlah record dalam tabel kedua bfrF = blocking factor dari tabel kedua
ii
(http://ivpr.cs.uml.edu/theses/jplee-ch2.pdf
56 Contoh kasus sebelumnya perintah join query yaitu: SELECT
*
FROM
pst_ke1 P, pstaktif F
WHERP
P. no_tsp = F. no_tsp
Tabel pst_ke1 P mempunyai 3.873.324 record. Jadi rp = 3.873.324 ( rP adalah record dalam P ). Diasumsikan jumlah record pst_ke1 per-halaman dalam satu disk blok adalah 100. Jadi bfrP = 100. Jika b adalah jumlah blok yang diperlukan untuk menyimpan tabel, maka jumlah blok dalam tabel P adalah bP, berdasarkan persamaan (4.5) blocking factor dari tabel P adalah : bP = rP / bfrP = 3.873.324 / 100 = 38.733 Untuk membedakan nilai indek diperlukan sebuah secondary index pada no_tsp dengan Xno_tsp = 2. Jangkauan atribut no_tsp terhadap nippa dari tabel pstaktif diperlukan 3.619.423 distinct value untuk no_tsp. Jadi dno_tsp = 3.619.423 Berdasarkan persamaan (4.6), nilai selection cardinality tabel P dari no_tsp adalah: Sno_tsp = rP / dno_tsp = 3.873.324 / 3.619.423 = 1,07 Tabel pstaktif mempunyai 3.619.423
record. Jadi rF = 3.619.423 dengan
Blocking factor dari pstaktif adalah bfrF= 80, maka nilai blok untuk pstaktif F adalah bF = 45242. Primary index pada nippa adalah tunggal, maka Xnippa = 1 Berdasarkan asumsi-asumsi di atas, Join Selectivity (js) adalah 1 / 3.619.423. dan untuk mendapatkan harga yang minimum, dapat dilakukan perhitungan berdasarkan persamaan (4.7) untuk nested loop, dan persamaan (4.8) untuk index structure yaitu :
57
1. Menggunakan nested loop dengan pst_ke1 pada bagian luar : Cost = bP + ( bP * bF ) + [ ( js * rP * rF) / bfrF ] = 38733 + ( 38733 * 45242 ) + [ (1 / 3.619.423 * 3.873.324 * 3.619.423 ) / 80 ] = 38733 + 1752358386 + 48416,55 = 1752445536 blok Apabila kecepatan I/O komputer mencapai 10ms, maka biaya di atas menjadi : = 1752445536 * 0,0000028, hasilnya setara dengan = 4906,85 jam = 204,5 hari 2. Menggunakan nested loop dengan pstaktif pada bagian luar : Cost = bF + ( bF * bP ) + [ ( js * rP * rF) / bfrF ] = 45242 + (45242 * 38733 ) + [ ( 1 / 3.619.423 * 3.873.324 * 3.619.423 ) / 80 ] = 45242 + 1752358386 + 48416,55 = 1752452027,55 blok , jika kecepatan I/O komputer mencapai 10ms, maka, = 1752452027,55 * 0,0000028, hasilnya setara dengan = 4906,86 jam = 204 hari 3. Menggunakan index structure pada nippa dengan pst_ke1 pada bagian luar. Cost = bP + ( rP * ( Xnippa + Sno_tsp ) ) + [ ( js * rP * rF) / bfrF ] = 38733 + ( 3.873.324*(1 + 1)) + [(1/3.619.423 * 3.873.324 * 3.619.423) / 80 ] = 38733 + 7746648 + 48416,55 = 7833797,55 blok, jika kecepatan I/O komputer mencapai 10ms, maka, = 7833797,55 * 0,0000028, hasilnya setara dengan = 21,935 jam = 0,91395 hari 4. Menggunakan index structure pada nippa dengan pstaktif pada bagian luar. Cost = bF + ( rF * ( Xno_tsp + Sno_tsp ) ) + [ ( js * rP * rF) / bfrF ]
58 = 45242+ (3.619.423*(2+1,07 ))+ [(1/3.619.423 * 3.873.324 * 3.619.423) /80] = 45242 + 11111628,61 + 48416,55 = 11205287,16 blok , jika kecepatan I/O komputer mencapai 10ms, maka, = 11205287,16 * 0,0000028, hasilnya setara dengan = 31,3748 jam = 1,37 hari Dari hasil perhitungan menunjukkan bahwa persamaan ketiga mempunyai biaya 21,935 jam adalah nilai yang paling rendah, sehingga optimizer akan memilih eksekusi menggunakan persamaan yang ketiga. Biaya keempat proses di atas tidak termasuk proses pencarian yang dilakukan sebelum operasi join, untuk proses pencarian biaya dapat diabaikan karena proses pencarian dilakukan didalam buffer. Fasilitas optimizer dari DBMS MySQL, menggunakan index structure biaya query lebih rendah dibandingkan dengan biaya menggunakan nested loops, MySQL optimizer akan memilih dan menggunakan index structure, dengan persyaratan spesifikasi minimum untuk tabel yang besar harus dipenuhi , sebagai berikut iii : Processor Intel Pentium IV Set Up Buffer : Key_buffer = 384 M max_allowed_packet = 1 M table_cache = 512 M Sort_buffer_size = 2 M read_buffer_size = 2 M MyISAM_sort_buffer_size = 64 M thread_cache_size = 32 M
iii
(htttp://www.golod.com/2007/01/optimizing_mysql_for_speed/)
59 4.3.
Percobaan
Penulis melaksanakan percobaan menggunakan fasilitas jaringan komputer yang berada di Kampus FMIPA UNPAD Jatinangor (” sebagian peta network dapat dilihat pada Gambar 23 ”), fasilitas tersebut menggunakan arsitektur clientserver dengan spesifikasi antara lain : - Client :
Processor Intel Pentium IV Core Duo 2,66 GHZ Memory 512 MB, Harddisk 60 GB Processor Intel Pentium IV 1,7 GHZ Memory 256 MB, Harddisk 40 GB Sistem Operasi Windows XP
- Server :
Processor Intel Pentium IV Core Duo 2,66 GHZ Memory 2 GB, Harddisk 80 GB Sistem Operasi Linux Redhat
- Software DBMS:
Mysql 4.0.3 win My ODBC 3.51.06 My SQL-Front_2.5 My-SQL Administrator 1.0.5
Dalam melakukan perintah-perintah query terdapat karakteristik dari DBMS dan arsitektur client server antara lain : 1.
Client dan server dapat melakukan komputasi, client dapat menerima bagian dari jawaban query.
2.
Server melakukan replikasi kepada client secara real time dimana server sebagai server master dan client sebagai server slave.
3.
Client akan merubah data transaksi pada server sebelum koneksi ke server di tutup. Dalam skenario yang memiliki 3 karakteristik ini minimasi waktu akses
dan transfer data menjadi sangat penting, sehingga masalah minimasi ongkos yang dikeluarkan dalam transfer hasil query dapat menjadi lebih murah. Ada beberapa cara yang mungkin untuk mendekomposisi query kedalam hasil views, rencana terbaik yaitu mempunyai ukuran minimum dan pada basis data di server.
60 Sebuah keuntungan dari pendekatan ini adalah bahwa menggunakan metoda formal, untuk memilih optimisasi secara global yang terdapat dalam DBMS dapat diperhitungkan dan dapat dibuktikan pada saat yang sama efisiensi metoda-metoda yang men-dekomposisi query kedalam views, dengan kata lain untuk sebuah query yang diberikan dari sebuah client ke server. Dalam percobaan dengan ketiga skenario di atas ongkos komunikasi tidak dapat diabaikan dan akan berpengaruh pada total perhitungan waktu, kemudian hasilnya dapat dievaluasi dalam berbagai kasus query tersebut. Dalam percobaan ini data relasi disimpan pada client (server slave) dan server (server master), situasinya dapat dilihat pada Gambar 23, masing-masing pst_ke1 dan pstaktif disimpan dalam client (server slave), sedangkan, pmk_ke1, pmk_fd1 dan pstpens disimpan dalam server (server master).
Dalam DBMS yang penulis gunakan client terkoneksi dengan database server, dan server melakukan replikasi pada client. Replikasi yang dijalankan yaitu dari server master ke server slave, transfer data (selama replikasi) antar server apabila query menggunakan MySQL kecepatannya mencapai 0,0002 detik dalam keadaan kondisi jaringan normal. Untuk percobaan yang dilakukan tabel-tabel yang diuji masih berupa tabel dengan tipe file masih ber-ekstensi .dbf, tabel tersebut dikonversi kedalam tabel Microsoft Access, setelah menjadi file Microsoft Access kemudian dikonversi lagi kedalam database MySQL, hal ini dilakukan karena karakteristik database tersebut banyak mengandung duplikasi dan banyak kesalahan dari tipe data yang tidak sesuai dengan isi data, begitu pula untuk field yang tidak null banyak yang tidak dipenuhi, sehingga apabila data berupa file .dbf tersebut langsung di konversi kedalam database MySQL sulit dapat diterima. Dari hasil pengamatan dalam proses query yang dilakukan terdapat hasil analisis dari beberapa output runtime antara lain : 1.
Perintah-perintah query yang tidak melakukan join tidak terdapat masalah walaupun jumlah record cukup besar dengan rata-rata lebih dari satu juta record dengan kapasitas memori tabel di atas 100 MB.
2.
Perintah-perintah
query
dengan
menggunakan
proses
optimisasi
menggunakan kriteria tertentu baik dalam satu relasi atau lebih dari satu
61 relasi, perbedaan kecepatan join query sangat signifikan, walaupun dalam DBMS sendiri sudah mempunyai fasilitas optimizer. 3.
Proses optimisasi dengan
mendahulukan
proses seleksi sebelum
melakukan join, proses eksekusi waktunya lebih cepat dari pada melakukan join lebih dahulu kemudian melakukan seleksi. 4.
Perubahan-perubahan hasil proses optimisasi sangat terlihat dalam jumlah record diatas 100.000, demikian juga untuk spesifikasi komputer yang berbeda, perbedaan runtime terlihat pada record diatas 100.000.
5.
Fragmentasi sangat diperlukan dalam jumlah record lebih dari satu juta, karena proses join tersebut dapat memakan waktu lebih dari satu hari. Perintah-perintah query yang dilaksanakan dalam kasus ini pertama kali
adalah perintah query yang dilakukan untuk menguji bahwa tabel betul-betul layak uji dan tidak terdapat error data dalam field sehingga tidak perlu melakukan join terlebih dahulu, kemudian perintah query selanjutnya dilakukan seleksi dan join, perintah-perintah query tersebut adalah : Q 1.
Perintah-perintah query tanpa optimisasi pada satu tabel relasi, hal ini untuk melihat seluruh isi tabel layak uji dan melihat unjuk kerja I/O komputer, yaitu : 1
2 3 4 5
Q2
SELECT
*
FROM
pst_ke1;
SELECT
*
FROM
pstaktif;
SELECT
*
FROM
pmk_ke1;
SELECT
*
FROM
pmk_fd1;
SELECT
*
FROM
pstpens;
Perintah-perintah query dengan optimisasi seleksi satu kriteria dari atribut
tertentu pada tabel satu relasi, yaitu :
62 1
2
3
4
5
SELECT
*
FROM
pst_ke1
WHERE
no_tsp = 131653793;
SELECT
*
FROM
pstaktif
WHERE
nippa = 131653793;
SELECT
*
FROM
pmk_ke1
WHERE
tmt_pst = “1970/01/01”;
SELECT
*
FROM
pmk_fd1
WHERE
tmt_pst = “1970/01/01”;
SELECT
*
FROM
pstpens
WHERE
kp180=”1997/11/01”;
Tabel 11 . Running time query tabel satu relasi tanpa join, Q1 tanpa optimisasi Q2 dengan optimisasi satu kriteria. TABEL/QUERY
pmk_ke1 pstpens pmk_fd1
pst_ke1
pstaktif
58 MB
70 MB
107 MB
132 MB
165 MB
1,4 juta
1,26 juta
1,26 juta
3,87 juta
3,62 juta
record
record
record
record
record
Q1
10,84
14,69
19,26
22,75
29,66
Q2
0,8
2,81
3,05
7,49
7,73
P IV Core Duo 512 MB
63
Query Tanpa Join
R u n ti m e (d e ti k )
35 30 25 20 15 10 5 0
Q1
Q2
1,4 juta record 1,26 juta record 1,26 juta record 3,87 juta record 3,62 juta record 58 MB
70 MB
107 MB
132 MB
165 MB
Jumlah Record Q1: Query Tanpa Optimisasi
Q2: Query dengan Optimisasi
Gambar 18. Running time query satu relasi tanpa join, Q1 tanpa optimisasi, Q2 dengan optimisasi satu kriteria. Perintah-perintah join query Q3, Q4 dan Q5 di bawah ini digunakan untuk membandingkan perintah tanpa optimisasi dan perintah dengan optimisasi, perintah query tersebut yaitu : Q3
Q4
: SELECT
*
FROM
pst_ke1 P, pstaktif F
WHERE
P. no_tsp = F. nippa;
: SELECT
P.no_tsp, P.tgl_lhr, P.tmt_pst, F.pangkat
FROM
pst_ke1 P, pstaktif F
WHERE
P.no_tsp = F. nippa;
64 Q5
: SELECT
P.no_tsp, P.tgl_lhr, P.tmt_pst, F.pangkat
FROM
pst_ke1 P, pstaktif F
WHERE
P.no_tsp = F. nippa AND F.gaji_pokok >= 500000 AND F.pangkat >='3A';
Hasil eksekusi perintah-perintah query tersebut ditunjukkan dalam Tabel 12 dan Gambar 19. Tabel 12. :Perbandingan join query tidak dioptimisasi dan dioptimisasi Query /Kardinalitas Q3: Join Query
1000
10000
20000
30000
40000
50000
record
record
record
record
record
record
0,72
45,59
192,02
426,67
776,41
1213,43
0,44
41,88
166
372,13
659,58
1028,84
0,22
32,25
135,55
275,95
466,08
689,17
tidak dioptimisasi Q4: Join Query dioptimisasi satu kriteria Q5: Join Query dioptimisasi tiga kriteria
65
Optimisasi Join Query 1400,00
Q3
Runtime (detik)
1200,00 1000,00
Q4
800,00 600,00
Q5
400,00 200,00 0,00 1000
10000
20000
30000
40000
50000
Jumlah Record Q3:Join Query tidak dioptimisasi Q4:Join Query dioptimisasi 1 kriteria Q5:Join Query dioptimisasi 3 kriteria
Gambar 19 . Perbandingan join query Q3 tidak dioptimisasi dan Q4 , Q5 dioptimisasi Salah
satu
teknik
perintah
optimisasi
dapat
dilakukan
dengan
mendahulukan operasi seleksi sebelum melakukan operasi join, hasil eksekusi secara signifikan lebih cepat dari pada mendahulukan operasi join sebelum melaksanakan operasi seleksi, hal ini ditunjukkan pada perintah query Q6 dan Q7, dan hasil eksekusi ditunjukkan pada Tabel 13 dan Gambar 20. Q6
: SELECT
P.no_tsp, P.tgl_lhr, P.tmt_pst, F.gaji_pokok, F.pangkat
FROM
pst_ke1 P, pstaktif F
WHERE
F.gaji_pokok >= 500000 AND F.pangkat >='3A' AND P.no_tsp = F. nippa;
Q7
: SELECT
P.no_tsp, P.tgl_lhr, P.tmt_pst, F.gaji_pokok, F.pangkat
FROM
pst_ke1 P, pstaktif F
WHERE
P.no_tsp = F. nippa AND gaji_pokok >= 500000 AND F.pangkat >='3A' ;
66 Tabel 13 : Running time query, Q6 mendahukan operasi join sebelum seleksi dan Q7 mendahulukan operasi seleksi sebelum operasi join Query/Kardinalitas
1000
10000
20000
30000
40000
50000
record
record
record
record
record
record
Q6 : mendahulukan join
0,38
51,56
202,75
468,2
742,39
1044,31
0,22
32,25
135,55
275,95
466,08
689,17
Q7 : mendahulukan seleksi
Mendahulukan Join atau Seleksi
R u n tim e (d e tik )
1200,00
Q6
1000,00 800,00 600,00
Q7
400,00 200,00 0,00 1000
10000
20000
30000
40000
50000
Jumlah Record Q6: Mendulukan Join
Q7: Mendahulukan Seleksi
Gambar 20 . Running time query, Q6 mendahulukan operasi join sebelum seleksi dan Q7 mendahulukan operasi seleksi sebelum operasi join. Perintah-perintah query untuk melakukan join dan seleksi satu atau beberapa kriteria lebih dari satu tabel dengan atribut yang sama dari tabel yang telah difragmentasi ditunjukkan pada Tabel 14 dan Gambar 21.
67
Perintah join query Q8 dan Q9 di bawah ini untuk melakukan join dan seleksi dengan tiga kriteria dari tabel pst_ke1 (3.873.333 record) dan pstaktif (3.619.4230 record ), untuk Tabel 14 dan Gambar 21 jumlah record pst_ke1 dan pstaktif difragmentasi antara 1000 s/d 100.000 record. Q8 fragmentasi dilakukan
setelah proses join query berjalan, dan Q9 fragmentasi dilakukan sebelum proses join query dilakukan dari 1000 s/d 100.000 record. Q8
: SELECT
*
FROM
pst_ke1 P, pstaktif F
WHERE
P.no_tsp = F. nippa AND P. kd_bup=’100’ AND F.pangkat >='3A' LIMIT 1000;
Q9
: SELECT
*
FROM
pst_ke1 P, pstaktif F
WHERE
P.no_tsp = F. nippa AND P. kd_bup=’100’ AND F.pangkat >='3A';
Tabel 14 : Perbandingan Runtime fragmentasi setelah proses join query dan fragmentasi sebelum proses join query. Join / Kardinalitas
1000
10.000
50.000
100.000
P IV 256 MB
(record)
(record)
(record)
(record)
85,3
1.246,09
31.250
155.556,5
0,42
31,98
325,2
1.245,48
Q8 : fragmentasi setelah proses query Q9 : fragmentasi sebelum proses query
68
Fragmentasi Join Query
Runtime (detik)
200000 150000
Q8
100000 50000 Q9
0 1000
10000
50.000
100000
Jumlah Record Q8
Q9
Gambar 21 : Perbandingan Runtime Q8 : fragmentasi setelah proses query Q9 : fragmentasi sebelum proses query Perintah-perintah query untuk melakukan join dan seleksi satu atau beberapa kriteria lebih dari satu tabel dengan atribut yang sama dengan spesifikasi client yang berbeda, ditunjukkan pada Tabel 15 dan Gambar 22. Q10
SELECT
P.no_tsp, P.tgl_lhr, F.tmt_pst, F.gaji_pokok, F.pangkat
FROM
pst_ke1 P, pstaktif F
WHERE
P.no_tsp = F.nippa AND P.tgl_lhr = F.tgl_lhr AND P.kd_bup ="100" AND F.pangkat >="3A" AND P.gaji_pokok >=700000;
69 Tabel 15. Perbadingan Running time client berbeda spesifikasi Join / Kardinalitas
P1 : Query pada P IV
1000
10.000
50.000
100.000
200.000
(record)
(record)
(record)
(record)
(record)
0,42
31,98
325,20
1245,48
12110,03
0,02
17,11
169,33
699,31
6177,05
256 MB P2 : Query pada P IV Core Duo 512 MB
Runtime (detik)
Perbedaan Runtime Query Berbeda Client 15000 P1
10000 5000 P2
0 1000
10000
50000
100000
200000
Jumlah Record P1 : Query pada P IV 256 MB P2: Query pada P IV Core Duo 512 MB
Gambar 22: Perbandingan Runtime client yang berbeda, P1 Pentium IV 256 MB P2 Pentium IV Core Duo 512 MB,
70
ROUTER OMNI FMIPA
switch management server
ROUTER FMIPA-PTBS
router hotspot
Proxy server
DNS server
mail server
switch
point to point FMIPA 192.168.203.2
router Dekanat 192.168.0.1
web server
point to point FMIPA-Jalawave
DataBase server 192.168.0.2 (master)
hub
hub
switch
Perpustakaan
SBP & Akademik
hub
client Lab. Penelitian (slave)
Dekanat
hub
Gambar 23: Konfigurasi sebagian peta MIPA-NETWORK ( FMIPA-UNPAD 2007 )
71 BAB V KESIMPULAN DAN SARAN 5.1.
Kesimpulan
Dari analisis dan percobaan yang dilakukan, penulis mengambil kesimpulan bahwa untuk melakukan perintah-perintah join query untuk jumlah record melebihi seratus ribu dan banyak mengandung atribut non teks, dilakukan secara parsial dengan fragmentasi relasi menurut kriteria tertentu, dan hasil proses secara signifikan menunjukkan yang optimal. menggunakan fasilitas optimizer dari DBMS
Proses
join
query
dapat
komersil maupun open source.
Untuk fasilitas optimizer dalam DBMS komersil unjuk kerja metode Hash Join menunjukkan hasil yang signifikan dengan biaya terendah. Dalam MySQL optimizer proses join query menggunakan index struture , hasilnya lebih baik dibandingkan dengan metode nested loops, tetapi harus dipenuhi persyaratan minimum spesifikasi komputer, yaitu processor Pentium 4 dengan memori minimal 1 GB. Unjuk kerja processor dari spesifikasi komputer yang lebih tinggi secara signifikan hanya menunjukkan relatif waktu running time lebih cepat dan grafik kecepatan menunjukkan kenaikkan sangat tinggi untuk record diatas 100 ribu. Biaya transfer jaringan tidak signifikan, apabila server melakukan replikasi secara real time sebelum query dijalankan. Proses optimisasi sangat diperlukan baik untuk query satu relasi maupun join query dua relasi. Untuk join query menggunakan proses optimisasi satu kriteria menghasilkan penurunan waktu rata-rata sebesar 17 %, dan proses optimisasi tiga kriteria menghasilkan penurunan waktu rata-rata sebesar 41 %. Demikian
juga
proses
optimisasi
mendahulukan
seleksi
sebelum
join
menghasilkan penurunan waktu rata-rata sebesar 37,50 % 5.2.
Saran
Dari hasil penelitian yang penulis lakukan, terdapat beberapa saran yang disampaikan, yaitu apabila akan melaksanakan join query, lalu-lintas jaringan harus sedang tidak padat. Melakukan join query sebaiknya dengan jalur tersendiri, dapat pula menggunakan DBMS yang dapat melakukan replikasi sebelum query
72 dijalankan, sehingga proses query dapat dijalankan secara lokal. Untuk penelitian lanjutan jika tabel relasi belum dibuat dan akan mencapai jumlah record yang besar, sebaiknya menggunakan Hash Based, Hash Table dan Hash Function sebagai sarana tabel dinamis menggunakan variabel pointer, dan dapat diuji coba dengan memanfaatkan memori ekstra menggunakan metode Hybrid Hash Join.
73
DAFTAR PUSTAKA Connolly T, Begg. C 1996. Database System A Practical Approach to Design, Implementation and Management. New York : Addison Wesley Publishing Company. hlm. 163-191 Erik va Kuijk. 2000. Semantic Query Optimization in Distributed Database Systems. Netherlands: Universiteit Twente. hlm. 13-28 Fathansyah. 2004 .Sistem Basis Data , Informatika Bandung. hlm. 21-50 Fuad Harahap, 2004 Optimisasi Query. http://www.geociteis.com/visiweb. hlm. 64-65 [ 22 Desember 2004] Jacobs Ken. 2002. Perspective DR.DBA Query Optimization . Documentation Discussion Forums Articles Sample Code Training RSS Resources As Published. hlm 1-4 http://www./oracle.com/ken.jacobs/drdba [6 Juli 2005] Jia li, Rada Chirkova, Chen Li. 2003. Minimizing Data-Communication Costs by Decomposing Query Results in Client-Server Environments. Deparment of Computers Science UCI ICS Technical Report. hlm 10-18. http://www.cse.iitk.ac.in/researc/mtech_1997 [25 September 2004] Özsu MT, Valduriez P. 1999. Principles of Distributed Database Systems. Ed ke-2 New Jersey : Prentice Hall. hlm. 75-233 Ramakrishna Raghu & Gehrke Johanes. 2003. Database Management Systems. Third Edition The McGraw-Hill Companies, Inc. Ed. ke 3 hlm. 299-317, 336-354, 559-564 Vadali V R L Swamy. 2001. Applying Parametric Query Optimization to NonParametric Query Metrics. Departement of Computer Science & Engineering Indian Instititute of Technologi, Kanpur. hlm 2-5.
74
Vlach Richard. 2000. Query Processing in Distributed Database Systems. Departement of Software Engineering, Charles University. hlm. 1-3 http://www.cs.umd.edu/~keleher/818s97/ryan/paper.html. [6 September 2004]
75 Lampiran 1 : Contoh kamus data tabel relasi pst_ke1 4 buah atribut 3.873.324 record
Nama Attribut
Type
NO_TSP
VarChar
Ukuran 10
Key
Keterangan
Primary
No Taspen dari
Key
NIP Pegawai
TGL_LHR
DateTime
-
-
Tanggal Lahir
TMT_PST
DateTime
-
-
Terhitung
Mulai
Tanggal Peserta KD_BUP
VarChar
3
-
Kode
76
Lampiran 2 : Contoh kamus data tabel relasi pstaktif dengan 8 buah attribut 3.619.423 record.
Nama Attribut
Type
NIPPA
VarChar
Ukuran 10
Key
Keterangan
Primary
No. Taspen dari
Key
NIP Pegawai
TGL_LHR
DateTime
-
-
Tanggal Lahir
TMT_PST
DateTime
-
-
Terhitung Mulai Tanggal
SEX
Char
1
-
Jenis Kelamin
GAJI_POKOK
Float
-
-
Gaji Pokok
BLTH_GAPOK Varchar
6
-
Gaji Pokok Terakhir
SUSKEL
Varchar
3
-
Status Keluarga
PANGKAT
Char
2
-
Pangkat
77 Lampiran 3 : Contoh kamus data tabel relasi pmk_ke1 dengan 6 buah attribut 1.401.040 record. Nama Attribut NO_TSP
Type VarChar
Ukuran 10
Key
Keterangan
Primary No Taspen dari NIP Pegawai Key
TMT_PST
DateTime
-
-
Terhitung
Mulai
Tanggal
Peserta TGL_KEJ
DateTime
-
-
Tanggal Kejadian
TGLHR_YMK
DateTime
-
-
Tanggal
lahir
yang
mengajukan klaim KD_KEJ
VarChar
4
-
Kode Kejadian B(pensiun), C(meninggal pensiun, setelah pensiun)
sebelum E(meninggal
78
Lampiran 4 : Contoh kamus data tabel relasi pmk_fd1 dengan 13 buah attribut 1.261.239 record
Nama Attribut
Type
NIPPA
VarChar
TMT_PST
DateTime
Ukuran Key 10
-
Keterangan
Primary No Taspen dari Key
NIP Pegawai
-
Terhitung
Mulai
Tanggal
Peserta KD_KEJ
VarChar
4
-
Kode Kejadian B(pensiun),
C(meninggal
sebelum
pensiun,
E(meninggal
setelah
pensiun) TGL_KEJ
DateTime
-
-
Tanggal Kejadian
TGL_KLIM
DateTime
-
-
Tanggal Klaim
TGL_TRANS
DateTime
-
-
Tanggal Transaksi
PANGKAT
Char
2
-
Pangkat
GAJI_POKOK
Float
-
-
Gaji Pokok
THP
Float
-
-
Tunjangan Hari Pensiun
SUSKEL
Char
3
-
Status Keluarga
NAMA_YMK
VarChar
30
-
Nama
yang
mengajukan
klaim TGLLHR_YMK DateTime
-
-
Tanggal
lahir
yang
mengajukan klaim RP_HAK
Float
-
Jumlah uang hak terima uang
79 Lampiran 5 : Kamus data tabel relasi pstpens dengan 11 buah attribut 1.264.037 record
Nama Attribut
Type
NOPEN
VarChar
Ukuran 10
Key
Keterangan
Primary
No Identitas Pensiun
Key JENIS
Char
1
-
Jenis
KP030
DateTime
-
-
Tanggal Lahir
KP040
Char
2
-
Golongan
KP080
Float
-
-
Tunjangan Kel
KP180
DateTime
-
-
Tanggal Pensiun
KP380
Float
-
-
Gaji Pokok
KP570
VarChar
4
-
Jenis Pensiun
KP550
Float
-
-
Jumlah uang hak diterima
KP710
VarChar
6
-
Status Keluarga
TMT_KERJA
DateTime
-
-
Terhitung Mulai Tanggal Kerja
80 Lampiran 6 : Contoh isi data tabel relasi pst_ke1 NO_TSP 000130985 010018391 010018826 010022921 010027958 010028654 010031869 010033046 010033069 010033707 010037805 010037812 010037815 010037828 010037869 010038434 010038436 010038437 010042845 010042859 010042860 010042884 010042889 010042900 010042910 010042920 010042939 010042955 010042971 010042977 010042989 010043669 010047214 010047216 010047219 010047225 010047231 010047237 010047248 010047257 010047258
TGL_LHR 31/12/1955 18/12/1952 30/03/1966 29/08/1955 19/10/1943 07/07/1942 02/09/1959 17/08/1943 31/12/1943 03/06/1943 29/08/1942 05/05/1942 11/11/1941 16/07/1943 25/07/1942 16/06/1943 15/12/1941 13/07/1941 08/05/1944 02/08/1943 08/09/1948 09/08/1946 10/10/1946 12/12/1942 31/12/1940 16/08/1943 13/06/1943 31/12/1947 01/10/1942 20/06/1942 06/06/1943 29/09/1943 29/04/1946 02/02/1948 16/05/1943 11/11/1943 02/08/1943 26/07/1943 23/05/1945 16/02/1948 22/05/1944
TMT_PST KD_BUP 01/01/1975 100 01/03/1983 100 01/03/1991 100 01/10/1975 100 01/12/1961 100 01/11/1961 100 01/03/1976 100 01/01/1962 100 01/01/1962 100 01/02/1962 100 01/04/1966 100 01/10/1963 100 01/04/1963 100 01/07/1963 100 01/10/1963 100 01/01/1963 100 01/07/1961 100 01/06/1962 100 01/09/1964 100 01/12/1964 100 01/12/1964 100 01/12/1964 100 01/12/1964 100 01/07/1964 100 01/07/1964 100 01/12/1964 100 01/07/1964 100 01/03/1964 100 01/07/1964 603 01/07/1964 100 01/04/1964 100 01/05/1964 100 01/02/1965 100 01/11/1965 100 01/11/1965 100 01/11/1965 100 01/09/1965 100 01/12/1965 100 01/11/1965 100 01/09/1969 100 01/10/1965 100
81 Lampiran 7 : Contoh isi tabel relasi pstaktif
NIPPA 010035956 010035980 010035987 010036013 010036019 010036084 010036094 010036095 010036115 010036148 010036150 010036152 010036153 010036188 010036197 010036256 010036276 010036278 010036282 010036410 010036428 010036430 010036447 010036469 010036471 010036491 010036505 010036530 010036541 010036578 010036580 010036590 010036598 010036624 010036630 010036651 010036652 010036670 010036671
TGL_LHR 15/11/1943 25/09/1943 26/01/1944 26/11/1943 01/01/1977 26/07/1943 01/12/1943 01/12/1943 26/08/1943 12/08/1944 01/12/1943 31/12/1943 01/12/1943 08/08/1943 17/09/1943 06/06/1944 08/09/1943 28/04/1943 06/07/1943 31/12/1946 01/12/1944 14/02/1943 20/06/1946 11/09/1943 03/04/1947 03/04/1943 20/03/1944 01/01/1977 31/12/1946 10/06/1943 16/03/1943 31/12/1943 27/03/1943 04/05/1943 02/02/1943 21/06/1943 15/04/1947 01/01/1944 25/08/1943
TMT_PST SEX GAJI_POKOK BLTH_GAPOK SUSKEL 01/10/1963 L 897500 082001 000 01/08/1963 L 866200 082001 100 01/01/1963 L 498000 012000 100 01/07/1963 L 973900 082001 100 01/01/1997 L 929900 082001 101 01/12/1963 L 875600 082001 103 01/08/1963 L 887900 082001 100 01/12/1963 L 940000 082001 101 01/03/1963 L 513000 021998 101 01/07/1963 L 1138100 082001 102 01/03/1963 L 887900 082001 102 01/03/1963 L 963500 082001 102 01/03/1963 L 885100 082001 103 02/12/1963 L 1060200 082001 000 01/10/1963 L 367700 091999 102 01/11/1963 L 973900 082001 101 01/04/1963 L 1125900 082001 100 01/06/1964 L 953100 082001 101 01/02/1963 L 987600 082001 100 01/01/1963 L 1098400 082001 102 01/08/1963 L 1060200 082001 102 01/12/1963 L 1060200 082001 103 01/08/1963 L 1034300 082001 103 01/07/1963 L 1363200 092002 100 01/10/1963 L 845100 082001 103 01/07/1963 L 1166500 082001 100 01/01/1963 L 1166500 082001 102 01/01/1997 L 947200 082001 103 01/08/1963 L 940000 012001 103 01/02/1963 L 216800 121990 102 01/11/1963 L 963500 082001 103 01/09/1963 L 804400 082001 102 01/12/1963 L 963500 082001 102 01/06/1963 L 897500 082001 102 01/06/1963 L 998300 082001 101 01/06/1963 L 367700 061999 000 01/12/1963 L 887900 012001 103 01/12/1963 L 180600 121990 102 01/06/1963 L 998300 082001 103
PANGKAT 2B 2A 3B 3A 2C 2B 2A 2D 3D 3D 2A 2D 2C 3B 2B 3A 3C 2C 2D 3C 3B 3B 3B 4C 2A 3D 3D 3C 2D 1D 2D 2A 2D 2B 3A 2B 2A 1B 3A
82 Lampiran 8 : Contoh isi tabel relasi pmk_ke1 NO_TSP 010037875 010037876 010037877 010037877 010037878 010037878 010037881 010037881 010038341 010038410 010038420 010038421 010038422 010038423 010038423 010038423 010038426 010038426 010038427 010038427 010038428 010038429 010038431 010038432 010038435 010038443 010038446 010038447 010038450 010038451 010038452 010038453 010038454 010038455
TMT_PST 01/09/1963 01/04/1963 01/07/1963 01/07/1963 01/11/1963 01/11/1963 01/09/1963 01/09/1963 01/04/1963 01/12/1963 01/09/1963 01/06/1963 01/01/1963 01/01/1963 01/01/1963 01/01/1963 01/08/1963 01/08/1963 01/06/1963 01/06/1963 01/06/1963 01/08/1963 01/01/1963 01/01/1963 01/01/1963 01/12/1963 01/04/1963 01/06/1963 01/07/1963 01/07/1963 01/08/1963 01/06/1963 01/01/1963 01/01/1963
TGLHR_YMK 30/07/1938 09/06/1943 31/12/1929 31/12/1929 16/04/1927 18/10/1929 09/07/1945 09/07/1945 21/07/1932 07/12/1941 17/08/1940 21/08/1936 01/04/1942 18/03/1930 18/03/1930 18/03/1930 01/07/1932 01/07/1932 18/08/1935 18/08/1935 10/05/1936 23/02/1934 09/03/1942 03/12/1941 30/12/1942 18/12/1937 10/10/1936 01/08/1937 27/09/1937 25/04/1943 03/02/1942 12/08/1945 01/07/1942 21/05/1941
TGL_KEJ KD_KEJ 31/07/1994 B110 30/06/1999 B110 31/12/1985 B111 16/06/1991 E110 31/12/1983 B110 18/10/1996 B210 30/12/1991 C110 30/12/1991 C111 27/01/1985 C110 31/12/1997 B110 31/08/1996 B110 31/08/1992 B110 30/04/1998 B110 31/03/1986 B110 31/03/1986 B111 07/11/1993 E110 31/07/1988 B110 13/05/1990 E110 31/08/1991 B110 31/08/1991 B111 31/05/1992 B110 24/06/1987 C110 31/03/1998 B110 31/12/1997 B110 31/12/1998 B110 31/12/1993 B110 31/10/1992 B110 03/07/1984 C110 30/09/1993 B110 30/04/1999 B110 28/02/1998 B110 31/08/1998 B110 30/11/1995 B110 31/05/1997 B110
83 Lampiran 9 : Contoh isi tabel relasi pstpens
NOPEN 0003819710 0003819720 0003819760 0003819780 0003819820 0003819950 0003819960 0003819970 0003819990 0003820040 0003820050 0003820060 0003820210 0003820240 0003820250 0003820280 0003820500 0003820510 0003820580 0003820610 0003820950 0003821000 0003821020 0003821080 0003821170 0003821400 0003821420 0003821430 0003821440 0003821450 0003821460 0003821470
JENIS KP030 KP040 KP080 1 12/09/1928 1C 257 2 11/11/1919 1B 239 2 01/12/1919 1B 290 1 27/09/1922 1B 205 1 31/12/1926 1B 205 1 31/12/1924 1B 222 1 23/02/1923 1B 205 2 12/12/1922 1B 308 1 31/12/1923 1C 311 1 11/05/1926 1B 222 1 01/12/1922 1B 205 2 31/12/1926 1C 265 1 31/12/1924 1C 857 1 22/11/1928 1D 778 2 09/01/1926 1B 569 1 31/12/1927 1B 569 1 01/01/1926 1B 569 2 01/06/1925 1A 33200 1 27/08/1919 1C 680 2 01/12/1925 1B 764 2 31/12/1929 1B 569 1 01/12/1930 1B 569 2 31/12/1919 1D 29700 2 10/07/1917 1B 29100 2 31/12/1921 1C 739 2 27/12/1927 1B 621 2 15/07/1923 1B 673 2 20/12/1928 1B 29100 2 01/12/1913 1C 503 2 30/06/1924 2D 1608 2 05/03/1923 1B 29500 2 31/12/1908 1B 30300
KP180 KP380 KP570 01/10/1978 500000 1100 01/05/1998 187500 1000 01/11/1990 375000 1000 01/10/1972 500000 1100 01/01/1967 500000 1101 01/04/1985 500000 1100 01/03/1993 500000 1000 01/04/1999 375000 1000 01/04/1985 500000 1000 01/04/1979 500000 1101 01/01/1973 500000 1000 01/03/2001 375000 1000 01/04/1979 500000 1100 30/10/1990 500000 1100 01/08/1997 187500 1000 01/04/1979 500000 1100 01/04/1979 500000 1100 01/07/1975 375000 1000 01/09/1969 500000 1100 01/08/1987 375000 1000 01/11/1993 375000 1001 01/01/1981 500000 1100 01/12/1986 375000 1000 01/07/1987 375000 1000 01/05/1998 375000 1000 01/06/1989 375000 1000 01/04/1974 375000 1000 01/06/1985 375000 1000 01/08/1998 375000 1000 01/08/2000 375000 1000 01/08/1985 375000 1000 01/06/1981 375000 1000
KP550 KP710 589500 102002 225000 102002 424800 102002 589500 102002 624600 102002 589500 102002 515300 102002 424800 102002 515300 102002 624600 102002 515300 102002 424800 102002 589500 102002 589500 102002 225000 102002 589500 102002 589500 102002 424800 102002 589500 102002 424800 102002 425400 102002 589500 102002 424800 102002 424800 102002 424800 102002 424800 102002 424800 102002 424800 102002 424800 102002 392800 102002 424800 102002 424800 102002
84
Lampiran 10 : Contoh isi data dari tabel relasi pmk_fd1 NIPPA
PANG GAJI_POKOK THP SUSKEL NAMA_YMK KAT 09/05/1988 2A 58200 0 000 TOGA NAPITUPULU 24/08/1989 1A 12000 52392 000 BACHTIAR EFFENDY 07/10/1998 2C 330400 376656 102 WILMAR SIMORANGKIR 13/06/1992 1C 91000 105560 103 MUHAMMAD NASIR LUBIS 24/02/1997 2C 192700 219678 102 AKMALUDDIN NASUTION 08/02/1992 2C 83000 83000 000 SYAHRIAL SIHITE 18/02/1993 2D 188900 211568 101 SYAIFUL MASRUL,BSC 21/12/1988 2B 72800 80808 103 LEGIMIN SUKARDI 22/01/1999 2D 327200 379552 103 MASA SEMBIRING 08/02/1996 2D 215700 241584 101 JAMALEM SITEPU 28/07/1995 2D 215700 250212 103 MUHAMMAD MUNIR 29/12/1993 1C 142700 165532 103 AMIR HUSIN 22/03/1999 2D 296800 326480 100 HERRY TH. PANGARIBUAN 07/12/1988 2A 69100 69100 000 M IRWAN 20/07/1995 3A 220200 242220 100 ERNAWATY BR SURBAKTI
TMT_PST KD_KEJ TGL_KEJ TGL_KLIM TGL_TRANS
010158936 01/03/1983 D110
29/02/1988 09/05/1988
010159184 01/03/1983 C110
30/05/1989 24/08/1989
010159312 01/01/1993 C110
31/08/1998 07/10/1998
010159318 01/03/1983 C110
11/05/1992 13/06/1992
010159363 01/01/1993 C110
14/01/1997 24/02/1997
010159371 01/03/1983 C110
14/01/1992 08/02/1992
010160176 01/03/1983 C110
11/01/1993 17/02/1993
010160189 01/03/1983 C110
17/11/1988 21/12/1988
010160980 01/01/1993 C110
10/11/1998 22/01/1999
010161545 01/01/1993 B110
31/01/1996 08/02/1996
010161547 01/01/1993 B110
31/05/1995 28/07/1995
010161548 01/01/1981 C110 010162569 01/03/1983 C110
07/12/1993 29/12/1993 21/01/1999 19/03/1999
010162981 01/03/1983 C110 010 01/03/1983 C110
30/06/1988 07/12/1988 20/04/1995 20/07/1995
TGLHR_YMK RP_HAK 02/07/1960
162700
20/08/1948
616600
26/05/1950 5567800 21/07/1946 1337400 30/08/1960 4484900 10/04/1957 1307200 23/04/1954 3583300 15/07/1946
873800
16/08/1948 5245300 14/01/1940 2002100 05/11/1935 1984000 09/08/1947 2387100 12/05/1958 6247400 01/12/1959 1145100 08/07/1960 4925100
