## Jurnal Widya
Volume 3, Nomor 1, April 2022: halaman 50-58 https://jurnal.amikwidyaloka.ac.id/index.php/awl jurnal@amikwidyaloka.ac.id / editor.jurnalwidya@gmail.com

## PENERAPAN ALGORITMA KNUTH MORRIS PRATT (KMP) PADA PENCARIAN DATA DI SQL LIKE OPERATORS
Fenina Adline Twince Tobing 1 , Alex Chandra 2* , Rena Nainggolan 3
1 Program Studi Informatika, Fakultas Teknik dan Informatika Universitas Multimedia Nusantara, Tangerang, Banten, Indonesia
2 Program Studi Manajemen Informatika, AMIK Widya Loka, Medan, Sumatera Utara, Indonesia
3 Program Studi Komputerisasi Akuntansi, Universitas Methodist Indonesia, Medan, Sumatera Utara, Indonesia
Email : 1 fenina.tobing@umn.ac.id , 2 alexsiburian03@gmail.com
Received: January 30, 2022. Revised: February 28, 2022. Accepted: March 25, 2022. DOI : https://doi.org/10.54593/awl.v3i1.82

## Abstrak
Penelitian ini membahas bagaimana database tracking system dapat menemukan data yang diinginkan berdasarkan  SQL  LIKE  Operator  yang  telah  ditentukan  dengan  menggunakan  Knuth  Morris  Pratt Algorithm  (KMP)  dalam  pencarian  data  pada  SQL.  Structured  Query  Language  (SQL)  adalah sekumpulan perintah khusus yang digunakan untuk mengakses data dalam database relasional. Untuk mencari  data  SQL  pada  query  operator  LIKE  yang  telah  ditentukan  dapat  dilakukan  melalui pencocokan string pada data yang ada untuk mendapatkan hasil. Pencocokan String adalah algoritma untuk  mencari  semua  kemunculan  string  pendek  yang  disebut  pola  dalam  string  yang  lebih  panjang yang disebut teks. Knuth Morris Pratt Algorithm (KMP) adalah pencocokan string dalam teks dari kiri ke  kanan  dengan  mencocokkan  karakter  per  pola  karakter  dengan  karakter  dalam  teks  yang  sesuai. Hasil penelitian menggunakan metode KMP pada query SQL berjalan dengan baik dalam melakukan pencarian data menggunakan Operator LIKE dan kemudahan dalam mengimplementasikan algoritma KMP dalam pencarian data pada SQL harus disesuaikan dengan wildcard pada operator LIKE.
Kata kunci—Pencocokan String, SQL, Knuth Morris Pratt (KMP ) .

## Abstract
Application is  an  action taken,  both  individually  and  in  groups  to  achieve  the  goals  that  have  been formulated. This journal discusses how the database tracking system can find the desired data based on  the  SQL  LIKE  Operator  that  has  been  determined  by  using  the  Knuth  Morris  Pratt  Algorithm (KMP) in searching data on the SQL. Structured Query Language (SQL) is a set of special commands that are used to access data in a relational database. To search for SQL data on the LIKE operator query that has been determined through matching a string on existing data to get the results. String Matching is an algorithm for searching for all occurrences of short strings called patterns in a longer string called text. Knuth Morris Pratt Algorithm (KMP) is matching strings in text from left to right by matching characters per character pattern with characters in the corresponding text. The results of the  study  using  the  KMP  method  on  SQL  queries  went  well  in  conducting  data  searches  using  the LIKE Operator and it was easy to implement the KMP algorithm in searching data in SQL.
Keywords— String Matching, SQL, Knuth Morris Pratt (KMP)

## Jurnal Widya
Volume 3, Nomor 1, April 2022: halaman 50-58 https://jurnal.amikwidyaloka.ac.id/index.php/awl jurnal@amikwidyaloka.ac.id / editor.jurnalwidya@gmail.com

## 1 Pendahuluan (Introduction)
Pada zaman sekarang ini perusahaan-perusahaan besar seperti Google, Microsoft, Apple Inc, dll telah banyak menggunakan database, salah satunya menggunakan SQL sebagai tempat dalam proses pengumpulan  dan  pengolahan  suatu  kumpulan  data.  Dengan  adanya  database,  data  yang  telah terkumpul  dapat  disimpan  sehingga  data  tersebut  akan  tersusun  secara  ringkas  dan  rapi,  serta  dapat mengecek  apakah  ada  data  yang  duplikat,  tidak  valid,  atau  data  yang  tidak  penting.  Basis  data  juga dapat  diakses  kapan  saja  dan  di  mana  saja  oleh  siapa  saja  dengan  syarat  terhubung  ke  basis  data melalui  internet.  Wikimedia  Foundation  menyatakan  “Basis  data  adalah  kumpulan  informasi  yang disimpan dalam komputer secara sismetik” [1].
Basis  data  bisa  dikatakan  mirip  dengan  perpustakaan.  Saat  mencari  buku  di  perpustakaan  akan memakan waktu yang cukup lama untuk menemukannya, apalagi jika perpustakaannya sangat besar. Perbedaan dengan database terletak pada kecepatan pencarian data, dengan database pencarian akan dilakukan oleh proses komputer pada sistem.
Dalam query SQL yang merupakan bahasa untuk mengakses data dalam database relasional [2]. Dalam  SQL  terdapat  query  SQL  yang  menggunakan  operator  LIKE  untuk  menampilkan  tabel berdasarkan  pencarian  karakter  sederhana  dengan  cara  mencocokkan  pola  pada  LIKE  dengan  data yang ingin dibutuhkan oleh kolom tabel.
Karena pencarian karakter harus sesuai dengan pola dengan teks data, maka dibuatlah aplikasi untuk mencari data pada operator SQL LIKE dengan algoritma Knuth Morris Pratt (KMP). Melalui metode ini, data yang ingin dicari dapat ditemukan sesuai dengan pola LIKE yang telah ditentukan.

## 2 Tinjauan Literatur

## A. String Matching
Algoritma  String  Matching  (Pencocokan  String)  adalah  algoritma  untuk  mencari  semua kemunculan  string  pendek  (pola)  yang  muncul  dalam  teks.  Polanya  adalah  string  dengan  panjang karakter 'm' (m <n). Teks berupa string panjang yang panjangnya 'n' karakter [3] .

## B. Query SQL
Ariata.C menyatakan, "Query SQL adalah bahasa pemrograman yang berguna untuk memanipulasi data - menambah, menghapus, dan mengubah data." [4].
Query adalah sejenis kemampuan untuk menampilkan data dari database yang diambil dari tabel di database,  dengan  sintaks  atau  perintah  yang  akan  ditulis  sesuai  dengan  keinginan  engineer  dalam menampilkan data. Ada tiga perintah utama dalam operasi akses database, yaitu:
1) SELECT
Digunakan untuk memilih data dari database [5].
2) FROM
Digunakan untuk menentukan tabel untuk memilih atau menghapus data [6].
3) WHERE
Digunakan untuk mengekstrak hanya record yang memenuhi persyaratan tertentu [7]. Contoh penggunaan query untuk mengakses database di SQL adalah sebagai berikut.
SELECT LAST_NAME, JOB_ID, SALARY FROM EMPLOYEES
WHERE SALARY > 2000 AND JOB_ID = ' ST_CLERK';

## Jurnal Widya
Volume 3, Nomor 1, April 2022: halaman 50-58 https://jurnal.amikwidyaloka.ac.id/index.php/awl jurnal@amikwidyaloka.ac.id / editor.jurnalwidya@gmail.com
Pada query diatas akan diakses beberapa data  EMPLOYEES yang memiliki gaji lebih dari 2000 dan memiliki JOB_ID 'ST_CLERK'.
Dalam  WHERE,  berbagai  perintah  relasional  digunakan,  seperti  LIKE  dan  perintah  operasi lainnya. Dengan perintah LIKE, semua string dalam database akan dicari berdasarkan teks/huruf yang dimasukkan. String yang akan dicari dapat digunakan dapat ditentukan pada dua wildcard yang sering digunakan bersama dengan operator LIKE:
1) ' % ' Tanda persen mewakili nol, satu, atau beberapa karakter.
2) ' _ ' Garis bawah mewakili satu karakter yang biasa disebut sebagai karakter khusus [8].
Sintaks atau perintah sederhana dari query LIKE adalah sebagai berikut.

## SELECT JOB_ID FROM EMPLOYEES
WHERE JOB_ID LIKE '%CLERK%';
Pada query di atas akan diakses data JOB_ID yang namanya memiliki kata 'CLERK' di setiap teks [9].

## C. Algoritma Knuth Morris Pratt
Algoritma  KMP  (Knuth-Morris-Pratt)  merupakan  salah  satu  algoritma  yang  dapat  digunakan untuk  mencari  dimana  suatu  string  (dalam  hal  ini  disebut  pattern)  ditemukan  pada  string  lain  yang berukuran lebih besar [10].
Secara  sistematis,  langkah-langkah  yang  diambil  oleh  algoritma  Knuth-Morris-Pratt  saat mencocokkan string:
1) Algoritma Knuth Morris Pratt (KMP) mulai mencocokkan pola di awal teks.
2) Dari  kiri  ke  kanan,  algoritma  ini  akan  mencocokkan  karakter  per  pola  karakter  dengan karakter dalam teks yang sejajar, hingga salah satu kondisi berikut terpenuhi:
a) Karakter dalam pola dan teks yang dibandingkan tidak cocok (mismatch).
b) Semua karakter dalam pola cocok. Kemudian algoritma akan memberitahukan penemuan pada posisi tersebut.
3) Algoritma  kemudian  menggeser  pola  berdasarkan  tabel  berikutnya,  kemudian  mengulangi langkah 'b' hingga pola berada di akhir teks.

## Jurnal Widya
Volume 3, Nomor 1, April 2022: halaman 50-58 https://jurnal.amikwidyaloka.ac.id/index.php/awl jurnal@amikwidyaloka.ac.id / editor.jurnalwidya@gmail.com
Algoritma Pseudocode KMP dalam tahap pencarian oleh Wikipedia (2019).
Algoritma  ini  hanya  membutuhkan  ruang  O  (n)  memori  internal  jika  teks  dibaca  dari  file eksternal. Semua nilai O tidak bergantung pada ukuran ruang alfabet [11].
Contoh penerapan algoritma KMP dalam pencarian string pada teks sesuai pola sebagai berikut.

## Teks : ACTCTCCATGATTAGTCACTCTCCACTATCCTA

## Pola : TAGTCACTC
Cara  untuk  mengatasi  masalah  tersebut  harus  terlebih  dahulu  mencari  data  awalan  agar pergeseran string yang cocok dapat lebih terorganisir. Dengan membuat tabel yang terdiri dari kolom- kolom  (Indexes,  Patterns,  Prefixes,  Prefixes,  Suffixes)  untuk  mencari  nilai  prefix  dari  pattern, dilakukan dengan cara mencocokkan prefix dan suffix pada kedua data tersebut.
Gambar 1: Pencarian Awalan

## Jurnal Widya
Volume 3, Nomor 1, April 2022: halaman 50-58 https://jurnal.amikwidyaloka.ac.id/index.php/awl jurnal@amikwidyaloka.ac.id / editor.jurnalwidya@gmail.com
Setelah Prefix ditemukan maka dapat langsung dilakukan pencocokan string dimana jika awalan 0  maka  bergeser  ke  kanan  1  kali  dan  jika  nilainya  1  maka  bergeser  1  kali,  di  shift  pertama  dilihat karakter mana tidak cocok dengan teks maka lakukan shift sesuai nilai pada awalan.
Gambar 2: Data Awalan Yang Telah Ditemukan
Gambar 3: Mencari String dalam Teks dengan Pola
Dari  gambar  di  atas  kita  mendapatkan  hasil  yang  diblok  warna  hijau  karena  pola  dan  teksnya cocok setiap karakter sehingga hasilnya ada di indeks 13.

## 3 Metode Penelitian (or Research Method)
Dalam SQL atau database, algoritma yang digunakan dalam pencarian data dengan Knuth Morris Pratt Algorithm (KMP) dapat digunakan dalam proses pencarian data dalam database. Dengan cara ini dilakukan  berulang-ulang  pada  setiap  data  pada  tabel  yang  ingin  digunakan  pada  Query  yang  telah ditulis.
Untuk  penerapan  algoritma  ini,  query  dengan  operator  LIKE  akan  mencari  data  dengan  pola tertulis dan mencari substring pada LIKE yang dibatasi oleh wildcard '%' atau '_'. Contoh penerapan Algoritma satu query untuk mencari data pada tabel 'JOB_ID' sebagai berikut
SELECT JOB_ID

## FROM EMPLOYEES
WHERE JOB_ID LIKE ‘%CLE%’;

## Jurnal Widya
Volume 3, Nomor 1, April 2022: halaman 50-58 https://jurnal.amikwidyaloka.ac.id/index.php/awl jurnal@amikwidyaloka.ac.id / editor.jurnalwidya@gmail.com
JURNAL WIDYA This work is licensed under a Creative Commons Attribution-NonCommercial- ShareAlike 4.0 International License .
Dari query diatas akan didapatkan hasil seperti gambar berikut.

## Gambar 4: Hasil Data dalam Query SQL
Hal pertama yang harus dilakukan adalah melihat substring yang telah ditentukan oleh operator LIKE, pola apa yang harus dicari. Pada Gambar 4 dapat dilihat bahwa pola atau substring memiliki wildcard '%'  yang artinya mewakili beberapa karakter termasuk null dan karakter di antara wildcard ditulis  'CLE'  karena  di  antara  karakter  tersebut  terdapat  '%'  maka  panjang  karakter  antar  'CLE' disesuaikan  dengan  teks  yang  ada.  Contoh  teks  yang  akan  digunakan  adalah  'PU_CLERK'  dan  pola 'CLE'.
Selanjutnya, tentukan awalan dalam pola awalan dan akhiran 'CLE'.
Gambar 5: Pencarian Awalan untuk Pola 'CLE'

## Gambar 6: Nilai Awalan dalam Pola
Setelah  menemukan  awalan,  dapat  mencocokkan  pola  dengan  teks.  Pergeseran  dilakukan sesuai dengan nilai awalan masing-masing karakter yang terdapat pada Gambar 6.
Gambar 7: Mencari Data dalam Pola 'CLE'

## Jurnal Widya
Volume 3, Nomor 1, April 2022: halaman 50-58 https://jurnal.amikwidyaloka.ac.id/index.php/awl jurnal@amikwidyaloka.ac.id / editor.jurnalwidya@gmail.com
Pada  Gambar  7  dilakukan  pencarian  data  dari  kiri  ke  kanan  dalam  proses  pencocokan  pola dengan teks. Terdapat warna merah yang artinya pola karakter tidak sesuai dengan karakter pada teks sehingga  digeser  sesuai  dengan  nilai  awalan  dan  nilai  awalan  yang  semuanya  '0'  kemudian  hanya digeser 1 kali hingga karakter dan teks yang sama pola yang telah diberi warna hijau.
Contoh  penerapan  algoritma  KMP  dengan  query  SQL  pada  operator  LIKE  menggunakan  dua wildcard '%' dan '_' pada substring atau polanya.

## SELECT LAST_NAME FROM EMPLOYEES
WHERE LAST_NAME LIKE ‘%a_’;
Dari query di atas, dapatkan data berikut

## Gambar 8: Hasil Data dalam Query SQL
Pada  Gambar  8  hasil  data  pada  operator  LIKE  memiliki  2  wildcard  yang  berbeda  yaitu  '%' dan '_' yang artinya jika terdapat wildcard, maka ini mewakili 1 karakter atau karakter khusus dalam sistem  SQL.  Oleh  karena  itu  pola  yang  dicari  tidak  hanya  'a'  tetapi  'a  [karakter_  khusus]'  Karakter khusus  dalam  jurnal  ini  direpresentasikan  sebagai  '#'.  Bisa  dilihat  dari  pencarian  awalan  terlebih dahulu.
Gambar 9: Pencarian Awalan untuk Pola yang Memiliki Karakter Khusus
Gambar 10: Nilai Awalan dalam Pola

## Jurnal Widya
Volume 3, Nomor 1, April 2022: halaman 50-58 https://jurnal.amikwidyaloka.ac.id/index.php/awl jurnal@amikwidyaloka.ac.id / editor.jurnalwidya@gmail.com
Setelah mendapatkan nilai prefix, maka dapat dicari setiap string yang memiliki proses yang mirip  dengan  string  sebelumnya,  namun  yang  berbeda  dari  sebelumnya  adalah  salah  satu  karakter dalam  teks  akan  berubah  menjadi  karakter  khusus  sebagai  karakter  representatif.  Teks  yang  harus dicoba adalah 'De Haan' di tabel 'LAST_NAME' di database karyawan

## Gambar 11: Menemukan Data di Pettern 'a [special_characters]'
Pada Gambar 11 proses pencarian datanya sama dari kiri ke kanan sampai ditemukan setiap pola karakter dengan teks yang cocok satu sama lain. Pencarian berisi karakter 'n' yang diubah menjadi '#' karena hanya sebagai perwakilan karakter dan ada karakter lain tetapi tidak selesai karena indeks atau perwakilan karakter tidak sesuai dengan pola yang ada sehingga 1- terjadi pergeseran waktu ke kanan dan hasilnya terlihat pada tabel yang berwarna hijau.

## 4 Hasil dan Pembahasan
Penerapan  metode  algoritma  KMP  telah  terbukti  bahwa  algoritma  KMP  dapat  melakukan pencarian data pada operator SQL LIKE dengan baik. Karena algoritma KMP melakukan proses dari kiri  ke  kanan,  jika  ada  sintaks  seperti  'LIKE'  _a%'  akan  mudah  ditemukan  dan  akan  menghemat perkiraan waktu saat mencari data.

## 5 Kesimpulan
Berdasarkan hasil perbandingan yang telah dilakukan, diperoleh kesimpulan sebagai berikut:
1. Dalam pencarian data pada operator SQL LIKE menggunakan Algoritma KMP untuk setiap pola  yang  ada  harus  disesuaikan  dengan wildcard pada  operator  LIKE  karena  merupakan bagian dari penentu pola yang akan dicocokkan dengan teks atau data pada tabel yang telah dipilih  dan  juga  sebagai  penentu  nilai  awalan  untuk  perpindahan  karakter  pada  saat  proses pencocokan setiap karakter.
2. Dalam hal perbandingan, diharapkan dapat menjadi referensi dan bahan pembelajaran untuk meneliti dengan algoritma pencocokan string lainnya dalam pencarian data di operator SQL LIKE  atau  operator  lain  yang  mendukung  algoritma  pencocokan  string  dalam  pencarian datanya.

## Jurnal Widya
Volume 3, Nomor 1, April 2022: halaman 50-58 https://jurnal.amikwidyaloka.ac.id/index.php/awl jurnal@amikwidyaloka.ac.id / editor.jurnalwidya@gmail.com

## Referensi (Reference)
[1] Wikimedia Foundation. “Pangkalan Data”. Wikipedia.org. https://id.wikipedia.org/wiki/Pangkalan_data (accessed 17 November 2021)
[2] Wikimedia Foundation.  “SQL”. Wikipedia.org. https://id.wikipedia.org/wiki/SQL (accessed 17 November 2021)
[3] Wikimedia Foundation. “Algoritme Pencarian Strting”. Wikipedia.org. https://id.wikipedia.org/wiki/Algoritme_pencarian_string (accessed 17 November 2021)
[4] C. Ariata (Juni 3, 2019). “Apa itu Query”. https://www.hostinger.co.id/tutorial/apa-itu-query/
(accessed 17 November 2021)
[5] W3schools. “SQL SELECT Statement”. W3schools.com. https://www.w3schools.com/sql/sql_select.asp (accessed 17 November 2021)
[6] W3schools. “SQL FROM Keyword”. W3schools.com. https://www.w3schools.com/sql/sql_ref_from.asp (accessed 17 November 2021)
[7] W3schools. “SQL WHERE Clause”. W3schools.com. https://www.w3schools.com/sql/sql_where.asp (accessed 17 November 2021)
[8] W3schools. “SQL LIKE Operator”. W3schools.com. https://www.w3schools.com/sql/sql_like.asp (accessed 17 November 2021)
[9] Singh. Puja, Pottle .Brian (April 2009). “Oracle Database 11g: SQL Fundamentals I”. (hlm 112- 113). (accessed 17 November 2021)
[10] Pip. (19 Mei 2016). “Algoritma KMP”. Piptools.net. https://piptools.net/algoritma-kmp-knuth- morris-pratt/ (accessed 17 November 2021)
[11] Wikimedia Foundation.  “Algoritma Knuth Morris Pratt”. Wikipedia.org. https://id.wikipedia.org/wiki/Algoritme_Knuth-Morris-Pratt (accessed 17 November 2021)