ANTARMUKA BAHASA INDONESIA PENGAKSES BASIS DATA DENGAN PEMBANGKITAN INPUT QUERY ALTERNATIF MENGGUNAKAN KAIDAH SINTAKSIS DAN SEMANTIK
KOMPETENSI KOMPUTASI
SKRIPSI
I WAYAN SAFIRA SRI ARTHA NIM. 1208605040
PROGRAM STUDI TEKNIK INFORMATIKA JURUSAN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS UDAYANA BUKIT JIMBARAN 2016
ii
Judul
Nama NIM Pembimbing I Pembimbing II
: Antarmuka Bahasa Indonesia Pengakses Basis Data dengan Pembangkitan Input Query Alternatif Menggunakan Kaidah Sintaksis dan Semantik : I Wayan Safira Sri Artha : 1208605040 : I Gede Santi Astawa, S.T., M.Cs. : I Dewa Made Bayu Atmaja Darmawan, S.Kom., M.Cs. ABSTRAK
Instansi-instansi
kesekretariatan
menggunakan
basis
data
untuk
menyimpan data-data arsip surat. Untuk mengakses dan mengolah data pada basis data diperlukan pemahaman mengenai bahasa kode terstruktur SQL. Namun, tidak semua orang mampu memahami dan memiliki waktu untuk mempelajarinya. Antarmuka form memudahkan end user seperti sekretaris ataupun pegawai administrasi surat untuk mengakses basis data arsip surat tanpa perlu memahami sintaks kode SQL. Bidang ilmu Natural Language Processing menjadi akar pengembangan antarmuka bahasa alami pengakses basis data/Natural Language Interface to Database (NLIDB) untuk mempermudah pencarian data dengan hanya mengetikkan sebuah kalimat perintah bahasa alami dan tanpa perlu mengisi form satu-persatu seperti pada antarmuka form. Dalam penelitian ini, dikembangkan sebuah NLIDB berbahasa Indonesia untuk domain basis data arsip persuratan. NLIDB Bahasa Indonesia ini bekerja dengan tahapan utama: (1) mengenali bahasa query input; (2) Membentuk logic form; (3) translasi ke SQL; (4) eksekusi untuk mendapatkan data pada database. Tahap pengenalan bahasa dilakukan dengan analisis sintaksis menggunakan kaidah-kaidah gramatikal Bahasa Indonesia. Sedangkan, tahap pembentukan logic form menggunakan kaidah-kaidah semantik kata. Pada proses translasi menjadi SQL, diterapkan pula fitur pembangkitan query alternatif untuk mengurangi risiko kesalahan output. Sejumlah 57 query Bahasa Indonesia diujikan terhadap sistem, mulai dari query dengan hanya SELECT expression, WHERE expression, hingga query beroperator. Hasilnya adalah precision sebesar 89,7 % dan recall 77,2 %. Kata Kunci: Natural Language Processing, Natural Language Interface to Database, Bahasa Indonesia, SQL, basis data, kaidah sintaksis & semantik.
iii
Title
: An Indonesian Language Interface to Database with Alternative Input Query Generation using Syntactic and Semantic Rules Name : I WayanSafira Sri Artha Student Number : 1208605040 Main Supervisor : I GedeSantiAstawa, S.T., M.Cs. Co-Supervisor : I Dewa Made BayuAtmajaDarmawan, S. Kom., M.Cs. ABSTRACT Secretariatal agencies use databases to store data of archival letters. To access and process data in the database requires understanding regarding structured code language called SQL. However, not every people is able to understand the language and has time to learn it. A form interface allows end users such as secretaries or administrative staff to access databases and archives without the need of understanding the syntax of SQL code. Natural Language Processing instantiates an interface that translates the natural language into SQL language so can access the database, known as Natural Language Interface to Database (NLIDB). The aim is to facilitate the data search by simply typing a command/sentence in natural language without the need of filling out the form one by one like on the form interface. This study develops an Indonesian NLIDB for the domain of correspondence archive database. The Indonesian NLIDB works with the following major phases: (1) recognition of the input query language; (2) Establishment of the logic forms; (3) translation to SQL; (4) the execution to obtain data on the database. The introduction stage of language syntactic analysis is done by using the rules of Indonesian grammar. Meanwhile, logic formation stage form uses the rules of semantic words. In the process of translation into SQL, it also applied the features of alternative query generation to reduce the risk of error output. A number of Indonesian 57 queries were tested against the system, starting from only a SELECT query expression, WHERE expression, and query with operators. The result was a precision of 89.7% and recall of 77.2%. Keywords: Natural Language Processing, Natural Language Interface to Database, Indonesian, SQL, databases, syntactic and semantic rules.
iv
KATA PENGANTAR Penelitian yang berjudul “Antarmuka Bahasa Indonesia Pengakses Basis Data dengan Pembangkitan Input Query Alternatif Menggunakan Kaidah Sintaksis dan Semantik” ini disusun dalam rangkaian kegiatan pelaksanaan Tugas Akhir di jurusan Ilmu Komputer FMIPA UNUD. Penulis mengucapkan terimakasih kepada pihak-pihak yang telah membantu dalam terselesaikannya penelitian ini, antara lain: 1.
Bapak I Gede Santi Astawa, S.T., M.Cs. sebagai Pembimbing I yang telah banyak membantu menyempurnakan penelitian ini.
2.
Bapak I Dewa Made Bayu Atmaja Darmawan, S.Kom, M.Cs. sebagai Pembimbing II yang telah banyak membantu penulisan laporan penelitian ini.
3.
Bapak Agus Muliantara, S.Kom, M.Kom., sebagai Ketua Jurusan Ilmu Komputer Universitas Udayana sekaligus pembimbing akademik yang yang selalu membimbing, memberi masukan dan saran.
4.
Bapak/Ibu para dosen di lingkungan Ilmu Komputer Universitas Udayana yang telah memberikan ilmu yang sangat berguna bagi penyusunan proposal ini.
5.
Teman-teman yang telah mendukung secara moral dan material. Tugas akhir ini masih jauh dari sempurna, untuk itu penulis mengharapkan
masukan dan saran demi kesempurnaan tugas akhir ini.
Bukit Jimbaran, Januari 2016 Penyusun
I Wayan Safira Sri Artha
v
DAFTAR ISI
LEMBAR PENGESAHAN TUGAS AKHIR ........................................................ ii ABSTRAK ............................................................................................................. iii ABSTRACT ........................................................................................................... iv KATA PENGANTAR ............................................................................................ v DAFTAR ISI .......................................................................................................... vi DAFTAR TABEL .................................................................................................. ix DAFTAR GAMBAR .............................................................................................. x BAB I PENDAHULUAN ....................................................................................... 1 1.1
Latar Belakang ......................................................................................... 1
1.2
Rumusan Masalah .................................................................................... 3
1.3
Batasan Masalah ....................................................................................... 3
1.4
Tujuan Penelitian ...................................................................................... 4
1.5
Manfaat Penelitian .................................................................................... 4
1.6
Metodologi Penelitian .............................................................................. 5
1.6.1
Desain Penelitian ............................................................................... 5
1.6.2
Pengumpulan Data ............................................................................ 5
1.6.3
Persiapan Query Input ....................................................................... 6
1.6.4
Metode yang Digunakan ................................................................... 6
BAB II TINJAUAN PUSTAKA............................................................................. 7 2.1
Tinjauan Empiris ...................................................................................... 7
2.2
Tinjauan Teoritis ...................................................................................... 9
2.2.1
Basis Data ......................................................................................... 9
2.2.2
Structured Query Language ............................................................ 10
2.2.3
Text Processing ............................................................................... 10
vi
2.2.4
Natural Language Processing ........................................................ 13
2.2.5
Natural Language Interface to Database (NLIDB) ......................... 17
BAB III PERANCANGAN DAN IMPLEMENTASI .......................................... 21 3.1
Konsep Dasar ......................................................................................... 21
3.2
Arsitektur Sistem .................................................................................... 21
3.3
Kebutuhan Fungsional Sistem ................................................................ 22
3.3.1
Filtering .......................................................................................... 23
3.3.2
Membedakan Tipe Kata .................................................................. 23
3.3.3
Pelabelan Kelas Kata....................................................................... 23
3.3.4
Mengenali Bahasa ........................................................................... 24
3.3.5
Membentuk Logic Form ................................................................. 24
3.3.6
Translasi ke Format SQL dan Eksekusi .......................................... 25
3.4
Rancangan Basis Data Arsip Surat ......................................................... 25
3.5
Rancangan Aturan Gramatikal ............................................................... 26
3.6
Rancangan Aturan Semantik .................................................................. 26
3.7
Rancangan Query Input Bahasa Indonesia ............................................. 27
3.8
Rancangan Antarmuka Sistem ............................................................... 27
3.9
Pengolahan Query Bahasa Indonesia ..................................................... 28
3.9.1
Filtering ........................................................................................... 28
3.9.2
Pelabelan Tipe dan Kelas Kata ....................................................... 29
3.9.3
Pengenalan Bahasa .......................................................................... 31
3.9.4
Pembentukan Logic Form ............................................................... 36
3.9.5
Translasi ke Format SQL dan Eksekusi Query ............................... 37
3.10
Pengujian dan Evaluasi ....................................................................... 37
3.10.1
Skenario Pengujian.......................................................................... 37
3.10.2
Evaluasi Sistem ............................................................................... 38
vii
BAB IV HASIL DAN PEMBAHASAN .............................................................. 39 4.1
Pengumpulan Dataset ............................................................................. 39
4.2
Persiapan Awal ....................................................................................... 39
4.3
Implementasi Filtering ........................................................................... 39
4.4
Implementasi Pelabelan Kata ................................................................. 40
4.5
Implementasi Pengenalan Bahasa .......................................................... 41
4.6
Implementasi Parsing............................................................................. 43
4.7
Implementasi Pemetaan Semantik.......................................................... 44
4.8
Implementasi Translasi ke Format SQL dan Eksekusi .......................... 47
4.9
Tampilan Antarmuka Sistem .................................................................. 48
4.10
Hasil dan Pengujian Sistem ................................................................ 50
4.10.1
Analisis Sintaksis ............................................................................ 50
4.10.2
Analisis Semantik ........................................................................... 53
4.10.3
Pembangkitan Query Input Alternatif ............................................. 58
4.10.4
Pengujian Query Bahasa Indonesia ................................................. 59
4.10.5
Analisis Faktor Kesalahan Lain ...................................................... 60
BAB V KESIMPULAN DAN SARAN ................................................................ 62 5.1
Kesimpulan ............................................................................................. 62
5.2
Saran ....................................................................................................... 62
DAFTAR PUSTAKA ........................................................................................... 63 LAMPIRAN .......................................................................................................... 65
viii
DAFTAR TABEL
Tabel 2.1 Pseudocode Levenshtein Edit Distance ................................................ 11 Tabel 2.2 Algoritma Stemming Nazief & Adriani ................................................ 12 Tabel 2.3 Algoritma Cocke-Younger-Kasami (CYK) .......................................... 16 Tabel 3.1 Kelas kata dan frase penyusun pola kalimat inversi ............................. 26 Tabel 3.2 Cuplikan aturan semantik yang digunakan sistem ................................ 27 Tabel 4.1 Sintaks filtering query input .................................................................. 39 Tabel 4.2 Sintaks pelabelan kelas dan tipe kata .................................................... 40 Tabel 4.3 Sintaks stemming (algoritma Nazief-Adriani) ...................................... 41 Tabel 4.4 Sintaks pengenalan bahasa metode CYK.............................................. 41 Tabel 4.5 Sintaks parsing...................................................................................... 43 Tabel 4.6 Sintaks pemetaan semantik-1 ................................................................ 44 Tabel 4.7 Sintaks pemetaan semantik-2 ................................................................ 46 Tabel 4.8 Sintaks translasi logic form ke format SQL .......................................... 47 Tabel 4.9 Grammar bantu ..................................................................................... 51 Tabel 4.10 Aturan semantik untuk SELECT expression ....................................... 53 Tabel 4.11 Aturan semantik untuk WHERE expression ....................................... 55 Tabel 4.12 Aturan semantik pada operator untuk SELECT expression ............... 56 Tabel 4.13 Aturan semantik pada operator untuk WHERE expression ................ 57 Tabel 4.14 Macam-macam format tanggal ........................................................... 58 Tabel 4.15 Perbedaan makna kata konjungsi ........................................................ 59 Tabel 4.16 Hasil pengujian dengan pembangkitan query alternatif ...................... 59 Tabel 4.17 Hasil pengujian tanpa pembangkitan query alternatif ........................ 60
ix
DAFTAR GAMBAR
Gambar 2.1 Alur mendapatkan informasi pada basis data .................................... 10 Gambar 2.2 Dua Fase Utama NLP ........................................................................ 13 Gambar 2.3 Contoh parse tree .............................................................................. 18 Gambar 2.4 Contoh semantic parse tree ............................................................... 19 Gambar 2.5 Arsitektur Intermediate Representation Language System ............... 19 Gambar 3.1 Arsitektur Sistem NLIDB Bahasa Indonesia .................................... 21 Gambar 3.2 Skema basis data arsip surat .............................................................. 25 Gambar 3.3 Struktur tabel view_surat .................................................................. 25 Gambar 3.4 Rancangan antarmuka sistem NLIDB Bahasa Indonesia .................. 28 Gambar 3.5 Flowchart proses filtering.................................................................. 29 Gambar 3.6 Flowchart proses pelabelan kata ....................................................... 30 Gambar 3.7 Proses CYK tahap inisialisasi ........................................................... 31 Gambar 3.8 Proses CYK hingga mencapai root ................................................... 33 Gambar 3.9 Hasil trace dari proses CYK .............................................................. 34 Gambar 3.10 Parse tree ........................................................................................ 34 Gambar 3.11 Flowchart proses CYK .................................................................... 35 Gambar 3.12 State pemrosesan query ................................................................... 38 Gambar 4.1 Ilustrasi parsing ................................................................................. 44 Gambar 4.2 Antarmuka sistem NLIDB Bahasa Indonesia ................................... 48 Gambar 4.3 Contoh tampilan input sistem............................................................ 49 Gambar 4.4 Contoh tampilan informasi proses translasi ...................................... 49 Gambar 4.5 Contoh tampilan query alternatif ...................................................... 49 Gambar 4.6 Contoh tampilan output sistem.......................................................... 50
x
