1. Database
Apa itu database?
Database adalah sekumpulan
data yang disimpan dengan tujuan tertentu dan susun sedemikian rupa sehingga
dapat diakses, dikelola dan diperbaharui secara mudah. Walaupun definisi diatas
mengungkapkan abstrak dari sebuah database seperti misalnya perpustakaan, file
cabinet, dan address book, yang dimaksud disini adalah sekumpulan data yang
disimpan dalam sebuah sistem komputer. Ada dua jenis utama database, yaitu
transactional database dan analytical database. Transactional database
digunakan untuk menyimpan data yang dinamis (mudah berubah), sedangkan
analytical database digunakan untuk menyimpan data yang statis.
Sejarah singkat
Konsep penggunaan database
diterapkan pada pertengahan abad 20 yang sebelumnya masih menggunakan konsep
file. Sebuah file database sering dianggap sebagai suatu tabel karena strukturnya yang sama dengan tabel pada sebuah laporan
yang dicetak di kertas. Dengan alasan yang sama, kolom pada dalam suatu tabel
disebut sebagai field dan baris
disebut dengan record.
Model-model database
Model database yang paling
awal adalah berbasis model flat file (file datar), dimana semua record disimpan
dalam betuk sebuah file biasa. Pada model ini, tidak ada hubungan
(relationship) yang bisa didefinisikan atau dibuat diantara record-record
tersebut. Dengan tidak adanya hubungan antar record, maka record-record
tersebut hanya bisa diakses dengan cara berurutan (sekuensial). Sebagai contoh,
jika ingin menemukan suatu record pelanggan ke 50, maka akan dilakukan
pencarian dari record pertama sampai ke record 49 secara berurutan. Model ini sesuai
dengan kondisi dimana semua record akan diproses secara keseluruhan, tapi tidak
sesuai jika hanya ingin mencari record yang sesuai saja dalam suatu database.
Model selanjutnya adalah
hierarchial model (model hirarki), yang secara luas digunakan dalam lingkungan
komputer mainframe. Model ini diturunkan dari Information Management Systems
pada tahun 1950an dan diadopsi oleh perusahaan-perusahaan seperti bank,
asuransi dan masih digunakan hingga sampai hari ini. Model ini dirancang dengan
hubungan yang terstruktur sehingga memungkinkan dan mempermudah akses terhadap
suatu data atau record. Dengan menggunakan skema dari suatu pohon yang dibalik,
hubungan yang terjadi dalam model hirarki ini adalah parent-child dan
one-to-many. Setiap tabel parent bisa mempunyai beberapa child tabel, namun
setiap child tabel hanya mempunyai satu parent tabel. Karena struktur datanya
permanen, dan secara eksplisit terhubung antara satu sama lainnya, maka proses
pengaksesan data akan lebih cepat. Meskipun demikian, model struktur yang
bersifat kaku ini menyebabkan beberapa masalah. Penambahan child tabel tidak
bisa dilakukan jika tidak terhubung dengan parent tabel. Misalnya, jika parent
tabelnya adalah “Dokter” dan child tabelnya adalah “Pasien”, maka penambahan
pasien akan bergantung dengan dokter. Dengan kata lain, penambahan record
seorang pasien harus juga menambahkan record seorang dokter. Begitu juga jika
sebuah parent tabel dihapus, maka child-child tabel dibawahnya juga akan
terhapus.
Berdasarkan model hirarki
pohon terbalik juga, pendekatan desain database selanjutnya dibuat yaitu
network model. Model ini menerapkan hubungan yang lebih rumit dari model
hirarki, sebagai contoh suatu pohon bisa memiliki cabang yang banyak. Pada
model ini, tabel-tabel terhubung dalam sebuah himpunan, dimana sebuah record
dalam tabel owner akan dihubungkan
dengan beberapa record dalam tabel member.
Seperti halnya model hirarki, pengaksesan data pada network model juga
berlangsung sangat cepat. Namun demikian, model ini juga mempunyai beberapa
masalah. Misalnya, seorang user harus
paham betul secara menyeluruh struktur database yang ada untuk memperoleh
sebuah data atau informasi. Jika strukturnya berubah, maka segala informasi
yang berkaitan dengannya akan berubah juga.
Pada tahun 1970-an,
hubungan antar database (database relational) dikembangkan dengan pesat dan begitu rumit, dimana nantinya akan
mendominasi penggunaan konsep ini dalam semua industri.
Apa itu database relational?
Pada model database
relational, data disimpan dalam sebuah relations (relasi), biasanya disebut
dengan tabel. Kumpulan dari tabel, record (atau tuples), dan fields (atau
attributes) adalah komponen-komponen dasar yang membentuk suatu relasi
database. Setiap data individual, disimpan dalam field di suatu tabel dan
setiap record terdiri dari beberapa field yang membentuk suatu tabel.
Model database relational
dikembangkan dari proposal oleh Dr. E.F. Codd yang berjudul “A Relational Model
of Data for Large Shared Databanks” pada tahun 1970. Codd adalah seorang peneliti
ilmiah di IBM, yang menjelaskan cara yang baik untuk mengelola data yang ada
dalam jumlah besar. Model hirarki dan network pada waktu itu cenderung
bermasalah dengan redundansi dan integritas data. Dengan menggabungkan disiplin
ilmu aljabar, kalkulus dan lojik ke suatu data, Codd membangun suatu model yang
lebih komplek.
2. Flat
Database
Apa itu flat database
Sebuah flat-file database
adalah database yang hanya memiliki sebuah tabel. Tabel tersebut terdiri dari
sekumpulan field (kolom) dan record (baris). Sebagai contoh adalah pada tabel
kartu nama berikut ini:
Gambar 1. Tabel kartu nama
Flat database bisa
digunakan secara luas dalam berbagai aplikasi yang berbeda, misalnya tabel
dalam wordprocessor atau dokumen HTML, ataupun worksheet disebuah spreadsheet.
Tabel didalamnya bisa diurutkan berdasarkan nilai yang ada dalam kolom. Dalam
spreadsheet, tabel bisa juga diquery dan dimanipulasi dengan cara tertentu. Hal
ini mencerminkan sifat-sifat sebuah database yang sederhana.
Sebuah field digunakan
sebagai key field (atau index field) yang akan digunakan untuk mengindek
database yang nantinya akan digunakan pada waktu operasi pencarian dan
pengurutan. Nilai dari primary key field haruslah unik untuk setiap record.
Contohnya adalah daftar tabel kartu nama dibawah ini:
Gambar 2. Tabel kartu nama yang
diindex
Semua database bisa di index untuk menambah aksesnya.
Index dalam database merupakan sebuah daftar berurutan yang berisi beberapa
kolom dari sebuah tabel dengan penunjuk (pointer) yang berhubungan dengan
sebuah nilai. Sebuah index memungkinkan sebuah kriteria pencarian akan dicari
secara cepat dan akurat. Berbagai macam metode index yang digunakan adalah
b-tree, hashes, dan linked lists.
Suatu database yang
bersifat relasional (RDBMS) akan lebih menguntungkan jika diiindex, karena
tidak akan mengubah aplikasi yang berhubunga dengannya. Hal ini disebabkan
karena aplikasi tersebut tidak menggunakan data yang terindex secara langsung.
B-Trees
(Balanced Tree Data)
B-tree
adalah suatu metode untuk menyimpan dan menemukan suatu file (disebut juga
records atau keys) dalam suatu database. Algoritma b-tree meminimalkan jumlah
dari media yang harus dilalui untuk mencapai suatu record database yang
diinginkan sehingga akan mempercepat proses.
Gambar 3. Struktur dari sebuah tree
B-tree lebih dianjurkan ketika pengaksesan
ke nodes adalah menggunakan media harddisk bukan RAM (Random Access Memory).
Dibutuhkan waktu seribu kali lebih lambat untuk mengakses elemen data dari
harddisk dibanding RAM, karena struktur harddisk yang memiliki bagian-bagian
mekanik yang bergerak. Metode b-tree sangat menghemat waktu dimana setiap nodes
bisa mempunyai beberapa cabang (disebut dengan children) jika dibanding dengan
binary-tree yang hanya mempunyai dua children. Ketika terdapat beberapa
children dalam suatu nodes, maka suatu record dapat ditemukan dengan hanya
melewati beberapa nodes saja dibandingkan dengan node yang hanya mempunyai dua
children.
Gambar 4. Struktur dari sebuah b-tree
Dalam sebuah tree (pohon),
record disimpan dalam suatu lokasi yang disebut leaves (cabang). Suatu record
dalam b-tree selalu berada pada titik akhir. Jumlah maksimal dari children
setiap node disebut order. Jumlah dari disk access yang dibutuhkan disebut
depth. Pada gambar diatas (kanan) menunjukkan sebuah b-tree dengan 3 buah order
untuk menuju suatu record yang ada dalam 8 leaves. Pada gambar kiri adalah
binary-tree dengan depth 4 dan b-tree dengan depth 3. Jelas terlihat bahwa
metode b-tree memungkinkan pengaksesan record lebih cepat dengan asumsi semua
sistem parameter adalah sama.
Dalam prakteknya b-tree
bisa memiliki ribuan atau jutaan record. Tidak harus semua leaves memiliki
suatu record, namun paling tidak adalah separuhnya harus memiliki. Perbedaan
depth antara skema b-tree dan binary-tree adalah dalam penggunaan di sebuah
sistem database dimana b-tree bisa memiliki order yang lebih tinggi, misalnya
32,64,128 atau lebih. Penambahan sejumlah record dalam database akan menambah
depth, begitu juga sebaliknya. Struktur tree mendukung berbagai operasi dasar
termasuk search, predecessor, successor,
minimu, maximum, insert dan delete dalam
sebuah tree.
Hashing
Hashing adalah perubahan string dari suatu karakter kedalam nilai dengan panjang yang tetap atau key yang merepresentasikan string aslinya. Hashing digunakan untuk mengindex dan mengambil suatu nilai pada sebuah database, dimana akan berlangsung lebih cepat jika dibanding dengan data yang asli (sebelum diindex). Metode ini juga menggunakan beberapa algoritma enkripsi.
Contoh sederhana dari
penggunaan hashing dalam database adalah berikut ini. Sebuah data flat dari
sekumpulan orang adalah sebagai berikut:
Abernathy, Sara
Epperdingle, Roscoe
Moore, Wilfred
Smith, David
(dan seterusnya, diurut berdasarkan
abjad)
Setiap nama depan dari
data diatas akan menjadi key dari data nama lengkap mereka. Maka, dalam sebuah
mekanisme pencarian, akan dicari karakter demi karakter terhadap semua data
sehingga kriteria yang dicari ditemukan. Namun, jika setiap nama diatas dihash,
maka dimungkinkan untuk menghasilkan nomor dengan sejumlah digit (misalnya
empat digit) yang unik untuk setiap nama. Misalnya menjadi:
7864
Abernathy, Sara
9802
Epperdingle, Roscoe
1990
Moore, Wilfred
8822
Smith, David
(dan seterusnya)
Dalam sebuah pencarian,
maka pertama kali nama akan dihash dengan fungsi hash yang sama pada waktu
menyimpan data tersebut (mengindex) sehingga menghasilkan suatu nilai yang akan
dibandingkan pada data terindex dengan nilai tersebut. Maka secara umum
pencarian dengan 10 kemungkinan (digit 0-9) akan lebih cepat dibandingkan
berdasarkan 26 kemungkinan (karakter a-z). Algoritma hashing yang digunakan
disebut hash function. Sebagai tambahan, untuk mempercepat pengambilan suatu
data, hashing juga menggunakan digital signature.
Fungsi hash juga digunakan untuk mengindex
nilai asli atau key dan digunakan kemudian
setiap kali data yang berhubungan dengan nilai atau key tersebut
diambil. Maka, metode hasing selalu merupakan operasi sekali jalan (one way
operation). Tidak perlu melakukan teknik reverse
engineering untuk metode ini dengan menganalisa nilai-nilai yang telah
dihash. Fungsi hash yang baik tidak akan menghasilkan dua nilai yang sama untuk
dua masukan yang berbeda. Jika iya, maka disebut collision.
Fungsi hash yang bekerja
dengan baik untuk menyimpan dan mengambil data dari sebuah database mungkin
tidak maksimal jika digunakan untuk cryptographic atau error-checking. Ada
beberapa fungsi hash terkenal yang digunakan dalam cryptographic, misalnya
fungsi hash message-digest MD2, MD4 dan MD4 yang digunakan untuk melakukan hash
terhadap digital signature kedalam nilai yang lebih sederhana yang disebut
message-digest, SHA (Secure Hash Algorithm), algoritma standar yang menggunakan
sebuah message-digest lebih besar (60-bit) atau mirip dengan MD4.
Linked Lists
Sebuah linked list adalah sekumpulan
data yang berurut yang hanya bisa diakses berdasarkan urutannya (dari depan ke
belakang atau awal ke akhir). Setiap data yang disimpan disebut node dimana
berisi penunjuk (pointer) ke node berikutnya. Bentuk dari linked list bisa
digambarkan seperti dibawah ini. Node digambarkan dengan sebuah kotak sedangkan
pointer digambarkan dengan sebuah anak panah. Pointer NULL digunakan untuk
menandai akhir dari suatu list.
Gambar 5. Linked List
List
diatas merupakan nama yang disusun berdasarkan abjad. Perbedaan antara list
yang berurutan dengan sebuah array adalah dalam pengaksesan datanya. Data dalam
sebuah array bisa diakses secara acak dan langsung menunjuk secara tepat ke
data yang dimaksud yang diwakili oleh sebuah angka index. Sedangkan dalam
linked list, data diakses secara sekuensial (berurutan).
Meskipun pencarian data
dalam bentuk array lebih cepat, namun akan mengalami kesulitan ketika sebuah
data baru dimasukkan kedalamnya. Mungkin saja tidak cukup ruang pada array
untuk dimasuki sebuah item baru, atau dengan menambahkan array yang baru.
Sedangkan dalam linked list, penambahan record baru hanya mengubah sejumlah
pointer saja.
Penghapusan sebuah record
dari ordered list juga hanya dengan mengubah sebuah pointer. Jika dalam array,
maka semua data disebelah kanan harus dipindah kekiri untuk mengisi ruang
kosong pada saat penghapusan. Maka, sekali lagi linked list lebih cepat dan
luwes. Secara umum, mungkin metode linked list lebih baik jika digunakan untuk
operasi penambahan dan penghapusan yang dilakukan berulang-ulang. Jadi, linked
list cenderung digunakan untuk tipe data yang dinamis, sedangkan array untuk
tipe data yang statis.
Perbandingan yang lain
adalah berdasarkan jumlah space yang digunakan. Dengan skema array, penggunaan
space mungkin akan melebihi jumlah yang diperkirakan. Namun demikian, linked
list juga membutuhkan space yang lumayan untuk menyimpan setiap pointer dari
suatu node. Secara umum, agak sulit ditentukan metode mana yang membutuhkan
space yang lebih besar.