Jurnal Teknik Informatika, Vol 1 September 2012

1

Jurnal Teknik Informatika, Vol 1 September 2012 PEMBUATAN APLIKASI UNTUK MENDETEKSI KEBENARAN PERINTAH SQL QUERY MENGGUNAKAN METODE KNUTH-MORRIS PRATT (KMP) Thio Wibowo1), Ardianto Wibowo2), Rika Perdana Sari3) Program Studi Teknik Informatika, Politeknik Caltex Riau Jalan Umban Sari no 1, Rumbai, Pekanbaru, Riau 28265 (E-mail: 1thio,[email protected], [email protected], [email protected])

Abstrak Basis data lanjut (BDL) adalah salah satu mata kuliah yang ada pada jurusan komputer di Politeknik Caltex Riau. Mata kuliah ini mempelajari tentang perintah-perintah query. Perintah query ini dibuat dengan menggunakan database oracle. Permasalahan yang terjadi pada mata kuliah ini adalah kesulitan saat dosen mendeteksi kebenaran query mahasiswa dalam pelatihan perintah-perintah query, karena perintah tersebut masih dikerjakan dengan tulis tangan dan di periksa secara manual. Hal ini akan menghabiskan banyak waktu. Salah satu solusinya adalah membangun sebuah aplikasi yang mampu mendeteksi kebenaran dari suatu query secara otomatis. Aplikasi yang di bangun menggunakan metode KMP, yaitu sebuah metode yang di gunakan dalam pencocokan string. Aplikasi ini dapat memberikan bobot penilaian dari perintah query yang di masukkan berdasarkan prioritas dari kata query. Hasilnya adalah berupa nilai pembobotan masing-masing query yang dimasukkan mahasiwa pada sistem. Dibangun menggunakan bahasa pemograman web PHP dan database MySQL. Berdasarkan hasil pengujian kuisioner yang diberikan terhadap mahasiswa dan dosen pengampu pada mata kuliah ini serta pengujian terhadap metode KMP, didapatkan hasil bahwa aplikasi ini dapat membantu dosen/ staff pengajar pada mata kuliah praktikum basis data lanjut serta membantu mahasiswa dalam pembelajaran mata kuliah praktikum basis data lanjut. Kata Kunci: Query, KMP, String, PHP, MySQL

Abstract Basis data lanjut (BDL) is one of the existing courses in computer science at the Polytechnic Caltex Riau. This course learn about the query commands. Query command is built using oracle database. The problems that occurred on this subject is difficult to detect when a lecturer in the training of student queries righteousness the commandments of the query, because the order was still done by hand and write on the check manually. This is going to spend a lot of time. One solution is to build an application that is able to detect the correctness of a query automatically. Applications built using the KMP method, a method that is used in the matching string. This application can provide an assessment of the weight of query commands entered by the priority of the query words. The result is a weighting value of each query is entered students in the system. Built using web programming language PHP and the MySQL database. Based on the results of testing the questionnaire given to students and faculty pengampu on this course and the testing of KMP method, showed that these applications can help faculty / staff teaching on the course and lab work-up database to help students in the learning lab course basis data lanjut. Keywords: Query, KMP, String, PHP, MySQL 1

PENDAHULUAN

1.1 Latar Belakang Basis data lanjut (BDL) adalah sebuah mata kuliah yang ada di Politeknik Caltex Riau. Mata kuliah ini merupakan lanjutan dari mata kuliah basis data dasar. Mata kuliah basis data lanjut membahas tentang query, yaitu perintah-perintah untuk membuat, memanipulasi, dan mengontrol database yang dipakai sebagai Relational Database Management System (RDBMS). Tetapi, pengujian soal masih dilakukan secara manual dengan menggunakan tulis tangan sehingga menyulitkan staff pengajar maupun mahasiswa sebagai pihak-pihak yang terlibat

2

Thio Wibowo1, Ardianto Wibowo2 & Rika Perdana Sari3

dalam mata kuliah tersebut. Seiring teknologi yang makin berkembang saat ini, mencocokkanquery yang dibuat oleh mahasiswa dengan jawaban query yang ada pada dosen tidak perlu dilakukan secara manual, tetapi dapat dilakukan melalui sebuah aplikasi berbasis web PHP yang mampu mencocokkan query yang dibuat oleh mahasiswa dengan jawaban query yang ada pada database, dimana jawaban tersebut telah dimasukkan oleh admin terlebih dahulu ke dalam database. Hal ini yang mendasari pembuatan aplikasi pendeteksi kebenaran perintah query, karena dengan adanya aplikasi ini, suatu query tidak perlu di cek satu persatu. Selain itu, aplikasi ini juga dapat memberikan pembobotan nilai kebenaran dari query tersebut, sehingga membantu mahasiswa dalam pembelajaran mata kuliah BDL. 1.2 Perumusan Masalah Perumusan masalah dalam proyek akhir ini adalah: 1. Bagaimana membuat sebuah aplikasi berbasis web yang dapat mencocokkan query yang diinputkan oleh mahasiswa dengan query yang tersimpan dalam database. 2. Bagaimana menerapkan metode Knuth-Morris Pratt (KMP) dalam aplikasi sebagai algoritma dalam pencocokan string. 2 Dasar Teori 2.1 Penelitian Sebelumnya Dalam proyek akhir mahasiswa Universitas Maryland, atas nama Jimmy Lin, telah melakukan penelitian dengan judul “Brute Force and Indexed Approaches to Pairwise Document Similarity Comparisons with MapReduce”. Rumusan masalah dari aplikasi ini adalah mengimplementasikan metode Brute force pada aplikasi search document pada perangkat java desktop. Aplikasi ini di gunakan untuk mencari file document dimana inputan berupa potongan nama file. Berikut adalah tabel yang membandingkan antara aplikasi sebelumnya dengan aplikasi sekarang: Tabel 2. 1 Perbandingan aplikasi sebelumnya dengan aplikasi sekarang Parameter Inputan ke system

Sebelumnya potongan karakter nama

Sekarang String yang berisi query

document Dasar pencarian

Teks nama document yang

String query yang ada di

tersimpan dalam database

database

Berbasis

Java Application

Output

File document

Web PHP Persentase kebenaran query dan pencocokan query

2.2. Metode/ Algoritma Knuth-Morris Pratt (KMP) 2.2.1. Pengertian dan Cara kerja algoritma KMP Algoritma pencocokan string (pattern) yang mempunyai kinerja bagus adalah KnuthMorris-Pratt (KMP) danAlgoritma Boyer-Moore. Kedua algoritma ini popular digunakan pada editor teks (menu find), search engine, analisis citra, dan sebagainya. Search engine atau mesin pencari adalah program komputer yang dirancang untuk membantu seseorang menemukan filefile yang disimpan dalam komputer, misalnya dalam sebuah server umum di web (WWW) atau dalam komputer sendiri. Mesin pencari memungkinkan kita untuk meminta content media dengan kriteria yang spesifik (biasanya yang berisi kata atau frasa yang kita tentukan) dan memperoleh daftar file yang memenuhi kriteria tersebut. Mesin pencari biasanya menggunakan

3

indeks (yang sudah dibuat sebelumnya dan dimutakhirkan secara teratur) untuk mencari file setelah pengguna memasukkan kriteria pencarian. Algoritma Knuth Morris Pratt (KMP) dikembangkan oleh D. E. Knuth, bersama dengan J. H. Morris dan V. R. Pratt. Untuk pencarian string dengan menggunakan algoritma Brute Force, setiap kali ditemukan ketidakcocokan pattern dengan teks, maka pattern akan digeser satu karakter ke kanan. Sedangkan pada algoritma KMP, kita memelihara inFormasi yang digunakan untuk melakukan jumlah pergeseran. Algoritma menggunakan inFormasi tersebut untuk membuat pergeseran yang lebih jauh, tidak hanya satu karakter seperti halnya pada Makalah IF3051 Strategi Algoritma – Sem. I Tahun 2010/2011 algoritma brute force. Secara sistematis, langkah-langkah yang dilakukan algoritma Knuth-Morris-Pratt pada saat mencocokkan string: a. Algoritma Knuth-Morris-Pratt mulai mencocokkan pattern pada awal teks.Dari kiri ke kanan, algoritma ini akan mencocokkan karakter per karakter pattern dengan karakter di teks yang bersesuaian, sampai salah satu kondisi berikut dipenuhi: i. Karakter di pattern dan di teks yang dibandingkan tidak cocok (mismatch). ii. Semua karakter di pattern cocok. Kemudian algoritma akan memberitahukan penemuan di posisi ini. b. Algoritma kemudian menggeser pattern berdasarkan tabel, lalu mengulangi langkah 2 sampai pattern berada di ujung teks. Algoritma ini menemukan semua kemunculan dari pattern dengan panjang n di dalam teks dengan panjang m dengan kompleksitas waktu O(m+n). Algoritma ini hanya membutuhkan O(n) ruang dari memory internal jika teks dibaca dari file eksternal. Semua besaran O tersebut tidak tergantung pada besarnya ruang alphabet. Berikut contoh pencocokan pattern dengan menggunakan algoritma KMP. 2.2.2.

Kelebihan Algoritma Knuth-Morris Pratt (KMP) Pada algoritma KMP, kita memelihara inFormasi yang digunakan untuk melakukan jumlah pergeseran. Algoritma menggunakan inFormasi tersebut untuk membuat pergeseran yang lebih jauh, tidak hanya satu karakter (Sunni, 2010). 2.2.3.

Fungsi Pinggiran (Border Function) Pada Metode KMP Fungsi pinggiran b(j) didefinisikan sebagai ukuran awalan terpanjang dari P yang merupakan akhiran dari P[1..j]. Sebagai contoh, tinjau pattern P = ababaa. Nilai F untuk setiap karakter di dalam P adalah sebagai berikut: Tabel 2. 2 Fungsi Pinggiran J P[j] B[j]

1 A 0

2 B 0

3 a 1

4 b 2

2.3.Algoritma KMP masukan: sebuah array karakter, S (teks yang akan dicari) sebuah array karakter, W (kata yang dicari) output: integer (yang berbasis-nol posisi di S di mana W adalah ditemukan)

5 A 3

6 a 1

Thio Wibowo1, Ardianto Wibowo2 & Rika Perdana Sari3

4

mendefinisikan variabel: integer, m ← 0 (awal pertandingan saat ini dalam S) integer, i ← 0 (posisi dari karakter saat ini di W) sebuah array bilangan bulat, T (meja, dihitung di tempat lain) selama m + i adalah kurang dari panjang dari S, lakukan: jika W [i] = S [m + i], jika saya sama dengan (panjang dari W) -1, kembali m i←i+1 jika tidak, m ← m + i - T [i], jika T [i] adalah lebih besar dari -1, i ← T [i] lain i←0 (Jika kita mencapai di sini, kita telah mencari semua S tidak berhasil) mengembalikan panjang dari S.

Contoh 7: Teks : abcabcabd Pattern : abcabd Mula-mula kita hitung fungsi pinggiran untuk pattern tersebut: Tabel 2. 3. Fungsi Pinggiran 2 J P[j] B[j]

Teks : Pattern :

1 a 0

2 b 0

3 c 0

4 a 1

5 b 2

6 d 0

abcabcabd abcabd  j = 3, j merupakan output berupa posisi karakter yang cocok

3. Perancangan dan Pembahasan 3.1 Proses Pembobotan Query dan Penilaian Aplikasi ini lebih membantu mahasiswa memahami perintah query dan cara penanganan kesalahan yang lebih mudah dipahami serta mahasiswa juga dapat melihat bobot penilaian yang di berikan aplikasi untuk setiap perintah query yang di masukkan. Pembobotan kata pada sebuah query berdasarkan prioritas dari kata yang di masukkan, sehingga didapat nilai akhir atau penjumlahan dari semua pembobotan kata. Tabel 3. 1 Prioritas Kata Query Prioritas 1

Kata Select, from, where, insert, into, value, update, delete

Keterangan Apabila salah pada satu karakter, maka pembobotan pada kata tersebut=0

2

*,Nama attribut tabel,nama tabel

Pembobotan berdasarkan jumlah karakter yang cocok dengan karakter query pada database

5

Terlihat seperti contoh berikut : Tabel 3. 2. Contoh kasus pencocokkan query Tampilkan semua nama barang pada tabel barang?

Soal

select nama_barang from barang

Jawaban query di database Jawaban query user

selec nama_baran from barang 74.01

Nilai user

Proses Pembobotan: Keterangan nilai mahasiswa : penjumlahan bobot penilaian semua kata pada query Query di atas mempunyai 4 kata  x[4]-Double Linked List Circular Bobot nilai per-karakter = 100 / jumlah karakter pada jawaban query database Bobot nilai per-karakter= 100/ 27 = 3.70 Pembobotan query: prioritas untuk kata select, from =1 prioritas untuk kata nama_barang, barang =2 Tabel 3. 3. Proses pembobotan dan penilaian kecocokkan query Parameter

X[0]

X[1]

X[2]

X[3]

Kata

Selec

nama_baran

From

Barang

Nilai

5 * 0 =0

10 * 3.7 = 37

4 * 3.7 =14.81

6 * 3.7=22.2

6

Thio Wibowo1, Ardianto Wibowo2 & Rika Perdana Sari3

3.2. Flowchart Algoritma KMP

Gambar 3. 1 Flowchart algoritma KMP

Gambar 3.1 merupakan penjelasan dari algoritma KMP, flowchart ini menjelaskan bagaimana metode KMP mendapatkan output yang berupa posisi karakter yang cocok. Terlihat pada gambar, metode KMP menyimpan nilai pergeseran dalam variable (i), pergeseran dilakukan sebanyak nilai (i) itu sendiri.

7

3.3. Flowchart Pmbobotan nilai

Gambar 3. 2 Flowchart pembobotan nilai

Pada gambar 3.2 merupakan penjelasan bagaimana aplikasi mendapatkan bobot nilai dalam pencocokkan karakter query menggunakan KMP-String Array. Pada metode ini pembobotan nilai dilakukan dengan mudah. Terlihat pada flowchart, metode ini mengumpulkan kata dalam array kemudian memeriksa kata tersebut pada tabel prioritas. Jika kata sama dengan tabel prioritas, maka kesalahan pada satu karakter dianggap salah pada kata. Jika tidak, kata tersebut akan diberi nilai sesuai dengan banyak karakter yang cocok pada kata.

8

Thio Wibowo1, Ardianto Wibowo2 & Rika Perdana Sari3

4. Hasil dan Diskusi 4.1 Hasil

Gambar 4. 1 Pengujian Aplikasi bagian user

4.2 Analisa Perbandingan Metode Antara Metode KMP-String Array dan Metode KMPDouble Linked List Circular Berdasarkan pengujian dan analisa metode KMP, dapat ditarik kesimpulan bahwa kedua metode KMP memiliki kelebihan dan kekurangan baik dalam pembobotan nilai dan pencocokkan karakter. Terlihat pada pengujian, metode KMP-LinkedList memiliki tingkat pencocokkan karakter yang lebih baik dari pada metode KMP-String array. Hal ini dikarenakan metode KMP-LinkedList melakukan pencocokkan dengan mencocokkan karakter perkarakter, sementara pada metode KMP String Array pencocokkan karakter dilakukan setelah membagi query menjadi String array, sehingga pada metode ini karakter spasi (‘ ‘) sangat diutamakan kebenarannya. Pengujian KMP juga memperlihatkan metode KMP String array memiliki tingkat pembobotan nilai yang lebih baik dari metode KMP-LinkedList. Hal ini disebabkan metode KMP-String array merupakan kumpulan kata sehingga memiliki kemudahan dalam menentukan prioritas suatu kata. Berbeda dengan metode KMP-LinkedList yang menggabungkan kembali query dalam bentuk susunan kata, sehingga karakter yang seharusnya karakter biasa dapat dianggap sebagai karakter yang terdapat pada kata prioritas. Tabel berikut merupakan penjelasan secara rinci dari perbandingan metode KMP: Tabel 4. 1 Perbandingan Metode KMP Parameter Inputan query

Pencocokkan query

KMP – array char to string

KMP – double Linked List Circular

Inputan jawaban query tidak ada batas

Inputan jawaban dibatasi pada akhir

akhir query

query dengan karakter (;)

Query dicocokan berdasarkan karakter,

Query dicocokkan berdasarkan

kemudian disatukan menjadi kata

karakter, apabila karakter cocok, kemudian melakukan pencocokkan

9 terhadap next atau previous dari karakter tersebut dengan jawaban query Pembobotan

Pembobotan dilakukan setiap karakter

Pembobotan dilakukan setiap

pada kata query. Kata yang memiliki

karakter, kemudian mengumpulkan

query dengan prioritas nomor satu

karakter yang memiliki kecocokkan

bernilai penuh jika kata tersebut cocok

dengan kata pada prioritas query.

dengan prioritas query, jika tidak maka

Penilaian berdasarkan bobot perhuruf,

kata tersebut bernilai 0

terkecuali karakter yang memiliki kecocokkan dengan kata pada prioritas query.

Akurasi penilaian

Proses penilaian query memiliki

Proses penilaian query hampir

akurasi yang bagus bahkan untuk kata

memiliki akurasi yang bagus,

query yang merupakan prioritas utama.

terkecuali untuk kata pada prioritas query.

Batas masalah

Penggunaan karakter spasi sangat

Penilaian pada karakter yang bukan

diperhitungkan sehingga apabila

termasuk prioritas query tidak

terjadi kesalahan dalam spasi, sistem

memiliki akurasi yang bagus .

tidak bisa menangani.

5.

KESIMPULAN Kesimpulan yang dapat diambil dari pengujian dan analisa yang telah dilakukan pada perangkat lunak adalah sebagai berikut: 1. Berdasarkan pengujian dan analisa kuisioner yang diberikan kepada user dan dosen pengampu mata kuliah basis data lanjut dapat ditarik kesimpulan bahwa pencocokan ataupun pendeteksian kebenaran perintah SQL Query pada mata kuliah praktikum basis data lanjut dapat dilakukan. 2. Berdasarkan pengujian dan analisa metode KMP dapat ditarik kesimpulan bahwa penerapan metode KMP pada pencocokan string dapat diimplementasikan.

10

Thio Wibowo1, Ardianto Wibowo2 & Rika Perdana Sari3

DAFTAR PUSTAKA [1]

Cahyono, Setyo. (2006). Panduan Praktis Pemograman Database menggunakan MySQL dan Java. Bandung: InFormatika. [2] Daniweb. (2007). Doubly Linked List Circular. Diambil 14 Agustus 2012 dari http://www.daniweb.com/software-development/c/threads/67953/doubly-linked-circularlist [3] Fathansyah. (2002). Basis Data. Bandung: Informatika. [4] Haryanto, S: (t.t). Scripting World. Diambil 01 Desember 2011 dari http://www.master.web.id/scriptingworld/02-8_hal_mysql/02-8_hal_mysql.html. [5] Heryanto, I., Raharjo, B., 2002, Memahami Konsep SQL dan PL/SQL di Oracle, Informatika, Bandung [6] Kochhar, N., Gravina, E., Nathan, P., 1999, Introduction to Oracle 8i, Oracle Corporation [7] PHI-Integration. (t.t). MySQL Tutorial. Di ambil 01 Desember 2011 dari http://mysql.phi-integration.com/sql/apa-itu-dml-ddl [8] Pusdatin www admin. (t.t). Diambil 01 Desember 2011 dari http://www.deptan.go.id/pusdatin/admin/RB/Programming/Materi%20PHP.pdf [9] Sidik, Betha (2005). MySQL. Bandung: InFormatika . [10] Sunni, I. (8 Desember 2010). Music Finder Menggunakan Algoritma KMP Extension. Diambil 01 Desember 2012 dari http://www.inFormatika.org/~rinaldi/Stmik/20102011/Makalah2010/MakalahStima201 0-096.pdf [11] Tarigan, Edi Prima (2003). Menguasai Oracle SQL . Jakarta: PT Elex Media Komputindo kelompok Gramedia. [12] Taufik. (2009). Skala Linkert. Diambil 14 Agustus 2012 dari http://daps.bps.go.id/index.php?page=website.ViewArtikel&id=100