Perpustakaan judul masih dalam tahap pengembangan, admin siap menampung kritik dan saran
Penerapan Algoritma Genetika Untuk Mengurangi Search Space Pada Pencarian Urutan Join Query yang Optimal
Ihsan Fauzi (2017) | Skripsi | Teknik Informatika , Teknik Komputer
Bagikan
Ringkasan
Tugas Akhir ini berkaitan dengan pencarian urutan join yang optimal. Hasil yang diharapkan dari Tugas Akhir ini adalah berkurangnya ruang pencarian pada pencarian urutan join namun tetap menemukan urutan join yang optimal. Urutan join dari suatu join query memiliki pengaruh yang besar terhadap cost pengekesekusian query tersebut. Suatu join query memiliki beberapa kemungkinan urutan join yang memiliki cost berbeda namun menghasilkan output yang sama, oleh karena itu diperlukan suatu pencarian untuk menemukan urutan join yang optimal dari beberapa kemungkinan urutan join tersebut. Pencarian dengan mengenumerasi semua kemungkinan dapat dilakukan untuk menemukan urutan join yang optimal. Namun, seiring bertambahnya jumlah relasi pada suatu join query, maka ruang pencarian pada pencarian tersebut pun semakin bertambah sehingga pencarian tersebut tidak tepat dilakukan pada join query yang melibatkan lebih dari delapan relasi karena besarnya ruang pencarian tersebut. Pendekatan yang dilakukan pada Tugas Akhir ini untuk mengurangi ruang pencarian tersebut adalah dengan menerapkan algoritma genetika. Algoritma tersebut dapat digunakan untuk mencari suatu solusi yang optimal dari suatu permasalahan yang memiliki banyak kemungkinan solusi. Algoritma tersebut kemudian diimplementasikan dalam bentuk suatu program yang berupa simulasi pencarian untuk menemukan urutan join yang optimal dari suatu join query. Uji coba dilakukan sebanyak sepuluh kali percobaan pada join query dengan jenis star join query dan chain join query yang terdiri dari enam sampai sepuluh relasi. Hasil uji coba menunjukkan bahwa algoritma genetika dapat mengurangi ruang pencarian pada pencarian urutan join yang optimal sebesar 80.7%. Selain itu, hasil uji coba tersebut pun menunjukkan bahwa tingkat efektivitas algoritma genetika dalam menemukan urutan join yang memiliki perkiraan cost paling rendah mencapai 97.7%. Kata Kunci: urutan join, ruang pencarian, algoritma genetika.
Ringkasan Alternatif
This final project is associated with finding optimal join order. The expected result of this final project is reduction of search space on finding join order but still found optimal join order. Join order of a join query have a considerable effect on the cost of query execution. A join query has several possible join order which have different cost but produce the same output, therefore we need to find the optimal join order from the several possible join order. Search by enumerating all possible can be performed to find the optimal join order. However, with increasing number of relations in a join query, the search space in the search is increasing too, so the search is not appropriate for a join query that involves more than eight relations because of the magnitude of the search space. The approach taken in this final project in reducing the search space is by applying genetic algorithm. The algorithm can be used to find an optimal solution of a problem that has many possible solutions. The algorithm is implemented in the form of a simulation program of finding the optimal join order of a join query. Experiments were performed ten times using star join query and chain join query consisting of six to ten relations. The experiment showed that the genetic algorithm can reduce the search space on finding optimal join order in the amount of 80.7%. In addition, the experiment also showed that the level of effectiveness of genetic algorithm in finding join order that has reached lowest cost of 97.7%. KeyWords: join order, search space, genetic algorithm.