MEDIA KULIAH SISTEM BERKAS BASISDATA: Maret 2019

Kamis, 07 Maret 2019

BAB I ALGORITMA, METRIK, DAN MEDIA PENYIMPANAN BERKAS BASISDATA

A. Algoritma Basisdata

Tema sentral dari ilmu komputer adalah algoritma (Brookshear, 2009). Pada dasarnya, para peneliti meyakini bahwa semua aktivitas pemikiran manusia, termasuk di dalamnya imajinasi, kreatifitas, maupun pengambilan keputusan, adalah hasil eksekusi sebuah algoritma. Contoh sederhana adalah saat berada di sebuah persimpangan yang dilengkapi dengan lampu pengatur lalu lintas. Sudah diperkenalkan kepada masyarakat bahwa bila lampu menyala hijau berarti para pengendara boleh terus melaju, kalau lampu kuning berarti pengendara perlu waspada karena dalam beberapa detik lagi lampu merah akan menyala. Dan, bila lampu merah menyala, maka semua pengendara harus berhenti sebelum garis batas. Bila algoritma tersebut dilaksanakan dengan sempuma maka terbangunlah ketertiban berkendara yang aman dan nyaman.

Sebelum komputer dapat melaksanakan sebuah tugas, komputer tersebut harus diberi tahu algoritma yang memunjukkan secara persis apa saja yang harus dilakukan dan bagaimana melakukannya. Itulah sebabnya studi tentang algoritma menjadi salah satu bagian yang penting dalam ilmu komputer.

Algoritma juga selalu dikaitkan dengan struktur organisasi data dan untuk pengolahan data tersebut. Algoritma dapat mengambil salah satu bentuk dari dua pilihan, pertama dalam bentuk kalimat-kalimat sederhana seperti resep masakan dalam buku-buku tataboga, atau dalam bentuk pseudo-code (kode palsu). Buku teks dalam bahasa Inggris menampilkan algoritma pseudo-code dalam bahasa Inggris sederhana, sementara dalam buku ini hanya kata-kata kerja saja yang akan ditulis dalam bahasa Inggris.

Berikut adalah contoh algoritma dalam pseudo-code untuk menggambarkan €strategi mempelajari struktur berkas (dalam bentuk kalimat sederhana).

Gambar 1.1 Algoritma Mempelajari Sistem Berkas

B. Metrik Basisdata

Pada awal bab pendahuluan ini, sudah diingatkan pentingnya mengorganisasi dan mengolah berkas secara efektif dan efisien. Akan tetapi ,bagaimana cara untuk mengetahui bahwa kondisi tersebut sudah atau belum tercapai? Jelas diperlukan suatu alat ukur (metrik) yang mampu memberikan indikasi tentang hal tersebut. Berikut adalah sebagian dari karakteristik alat ukur tersebut:

Kesederhanaan (simplicity). Jika ada beberapa alternatif, maka pilih altematif yang paling sederhana.
Keandalan (reliability). Memilih struktur berkas untuk sebuah sistem harus pula memikirkan apakah sistem tersebut akan tetap berfungsi dalam segala kondisi.
Dapat diprogram (programmability). Dapatkah dibangun program untuk mengolah algoritma dalam waktu yang disediakan? Kalau tidak , pilih alternatif lain.
Dapat dipelihara (maintainability). Sekali teknik yang dipilih tersebut diprogram, dapatkah
program-tersebut dimodifikasi atau diperbarui dengan mudah? Jika terlalu rumit sehingga
sulit untuk dimodifikasi, maka sebaiknya pilih prosedur yang lain.
Kebutuhan penyimpanan (storage requirement). Dalam menentukan media penyimpan data sebaiknya dipertimbangkan tentang keterbatasan media tersebut.
Kompleksitas komputasi atau kompleksitas waktu (complexity). Waktu proses suatu algoritma merupakan syaarat yang sangat utama. Kompleksitas komputasional suatu algoritma memberikan estimasi tentang waktu yang diperlukan saat algoritma diaplikasikan terhadap sejumlah besar data.

C. Media Penyimpanan Berkas-Basisdata

Pertimbangan yang sangat penting yang berkaitan dengan perancangan suatu sistem informasi ataupun pembelian sistem komputer adalah cara bagaimana data dan berkas diakses. Pita magnetis hanya dapat digunakan secara sekuensial, sementara disk magnetis memiliki kemampuan akses baik secara sekuensial, random, maupun langsung. Karena kemampuan tersebut, penyimpa disk magnetis merupakan pilihan yang paling diminati oleh banyak pemakai komputer, baik untuk komputer mikro, workstation, ataupun komputer-super. Sejumlah varietas penggerak disk (perangkat keras) serta disk magnetis (media) diproduksi untuk berbagai kebutuhan bisnis.

Media penyimpanan memerlukan perhatian karena mempengaruhi pengambilan keputusan tentang bagaimana sebaiknya menentukan struktur dan memproses informasi, atau dengan kata lain mempengaruhi bagaimana informasi ditangani oleh sistem perangkat 1unak. Pada sebuah sistem perangkat lunak, waktu akses yang diartikan sebagai lamanya waktu yang dibutuhkan untuk mengakses informasi dalam media penyimpan merupakan aspek yang sangat penting. Jika informasi disimpan pada perangkat dengan kecepatan akses tinggi, maka waktu dibutuhkan untuk pengaksesan informasi tersebut relatif singkat.

Teknologi media penyimpan, sampai dengan saat sekarang, dapat dikelompokkan ke dalam dua tipe yaitu;

Penyimpan primer (Primary memory storage)
Penyimpan pendukung (auxiliary memory/storage) atau penyimpan sekunder (secondary storage).

Di dalam sistem komputer, program dan informasi dalam berbagai bentuk (teks, citra, audio, video) disimpan dalam penyimpan primer maupun penyimpan sekunder. Program dan informasi diambil dari penyimpan sekunder dan disimpan untuk sementara di penyimpan primer untuk pemrosesan. Ada beberapa faktor yang berkaitan dengan keberadaan tipe-tipe media penyimpan ini:

Tidak semua informasi dapat ditampung dalam penyimpan primer berkecepatan tinggi walaupun pada saat ini penyimpan primer memiliki kapasitas yang semakin bertambah dan dengan hargayang semakin murah.
Keterbatasan secara pisik dan ekonomis. Secara fisik besarnya kapasitas penyimpan primer ditentukan oleh skema pengalamatan oleh sistem komputer dan secara ekonomis walapun harganya semakin murah namun masih belum menyamai penyimpan sekunder. Penyimpan primer mempunyai karakteristik akses yang sangat cepat, tetapi harga per bit jauh lebih mahal dibanding penyirnpan sekunder dan mempunyai kapasitas yang lebih kecil. Penyimpan sekunder merupakan kebalikannya yaitu memunyai kecepatan akses yang lebih lambat, kapasitasnya lebih besar tetapi lebih murah.

Rangkuman Bab I Algoritma, Metrik, dan Media Penyimpanan Basisdata

Evaluasi Bab I Algoritma, Metrik dan Media Penyimpanan Basisdata

BAB II STRUKTUR ORGANISASI BERKAS-BASISDATA PRIMER

A. Pengertian Struktur Organisasi Berkas Primer

B. Medan (Field) Data

C. Rekaman (Record) Data

D. Berkas (File) Data

Rangkuman Bab 2 Struktur Organisasi Berkas-Basisdata Primer

Evaluasi Bab 2 Struktur Organisasi Berkas-Basisdata Primer

Bab III STRUKTUR ORGANISASI BERKAS-BASISDATA SEKUENSIAL

A. Pengertian Struktur Organisasi Berkas-Basisdata Sekuensial

Sebagaimana diuraikan pada Bab II, berkas dapat diorganisasi secara sekuensial, langsung, maupun sekuensial berindeks, dan masing-masing memiliki (peluang) metoda pengaksesan yang berbeda. Bab ini akan membahas tentang berkas sekuensial, sebuah tipe struktur organisasi berkas basisdata yang paling sederhana, dan yang sudah sangat akrab di kalangan para mahasiswa.

Dalam berkas sekuensial, rekaman ke 1+1 akan diletakkan tepat sesudah rekaman ke-i, sebagai contoh adalah:

ke-n

RRRRRRRR

Subskrip

Gambar 3.1 Susunan berkas sekuensial

Pada Gambar 3.1 tersebut rekaman R, diikuti oleh rekaman R, kemudian R, dan seterusnya sampai dengan rekaman terakhir yaitu R., Pada keadaan sehari-hari, berkas ini terjadi sesuai dengan kronologi kedatangan rekaman. Misalkan saja sebuah kantor kecamatan melakukan pendataan terhadap semua keluarga yang memiliki anak usia balita, maka susunan berkas keluarga tersebut akan memiliki urutan yang sama dengan urutan keluarga yang mencatatkan diri. Dalam hal ini tidak ada manipulasi urutan berdasarkan medan data tertentu.

B. Metode Pengaksesan Berkas-Basisdata Sekuensial

Sesuai dengan namanya, berkas sekuensial sangat cocok untuk akses yang sekuensial. Misal dalam sebuah aplikasi diperlukan proses terhadap sebagian besar atau semua rekaman yang ada (mencetak daftar semua mahasiswa dalam sebuah Jurusan), maka akses sekuensial cukup memadai. Melakukan akses secara sekuensial berarti proses akan berpindah dari satu rekaman ke rekaman yang berikutnya secara langsung

Berkas sekuensial juga dapat diproses secara individual dan langsung jika diketahui subskrip-nya. Akan tetapi, bagaimana kalau subskrip yang dimiliki bukan identitas utama rekaman, misal "Nama Mahasiswa dalam contoh Gambar 2.3? Pembacaan harus dilakukan secara sekuensial atau linear, rekaman demi rekaman, sampai "Nama Mahasiswa" yang sesuai ditemukan. Untuk membaca rekaman dengan "Nama Mahasiswa" = "Dewi Sartika", diperlukan probe sejumlah 5 kali (beruntung direkam pada rekaman ke 5). Permasalahan akan muncul bila rekaman berada pada urutan belakang, karena waktu pembacaan akan lama. Demikian pula kalau kebetulan nama yang dicari memang tidak berada dalam rekaman, aplikasi harus membaca semua rekaman dan berakhir dengan pesan bahwa rekaman tidak diketemukan.

Pencarian secara sekuensial memproses rekaman-rekaman dalam berkas sesuai urutan keberadaan rekaman-rekaman tersebut sampai ditemukan rekaman yang diinginkan atau semua rekaman terbaca.

Apakah yang harus dilakukan agar kinerja pembacaan rekaman lebih baik? Salah satu alternatif adalah melakukan satu pekerjaan ekstra terhadap berkas sebelum proses pembacaan dimulai. Sebagai contoh rekaman-rekaman dalam berkas mahasiswa diurutkan untuk mendapatkan pengurutan yang linear berdasar pada nilai kunci rekaman (bisa secara alfabetis ataupun numeris). Hasil pengurutan (menurut nama mahasiswa) adalah sebagai berikut:

Kolom "Nama Mahasiswa" menunjukkan nilai yang urut dari kecil ke besar, atau

Kuncil kunci2 <kunci3 <... kunci i < Kunci n

Pada Gambar 3.2, Akmad Nurhadi lebih kecil dari Budiani, yang lebih kecil dari Dewi Sartika, yang lebih kecil dari Ida Arini dan seterusnya. Dengan metoda pengurutan, maka pencarian dan pembacaan rekaman bisa berlangsung normal seperti bila rekaman-rekaman dalam berkas tidak diurutkan. Namun dalam hal mencari rekaman yang tidak ada dalam berkas. metoda ini lebih baik karena tidak harus membaca semua rekaman untuk mengetahuinya. Bila hasil pembacaan secara sekuensial menghasilkan nama mahasiswa yang nilainya lebih besar dari yang diinginkan maka proses langsung dihentikan dan pesan kegagalan menemukan rekaman yang diinginkan disampaikan.

Dengan demikian, hanya n/2 rekaman yang perlu diperiksa rekaman-demi-rekaman untuk menemukan rekaman yang diinginkan, karena kalau pembacaan diteruskan melewati posisi di mana rekaman seharusnya berlokasi (mengingat berkas sudah diurutkan), proses pencarian dihentikan. Untuk membaca "Dewi Sartika" hanya diperlukan 3 probe (Gambar 3.2), lebih kecil dibanding sebelum berkas diurutkan (Gambar 2.3). Namun teknik tersebut masih kurang memuaskan untuk berkas dengan jumlah rekaman yang sangat besar. Masih diperlukan teknik untuk mengorganisasi rekaman yang lebih baik. Algoritma

C. Algoritma Pencarian Biner (Binary Search)

Untuk sebuah berkas dengan rekaman yang sudah diurutkan, jumlah probe yang diperlukan untuk membaca sebuah rekaman dapat diusahakan untuk diperkecil dengan menggunakan teknik pencarian biner. Jika Kunci Kunci maka bagian berkas mulai dari Kunci sampai akhir berkas dieliminasi. Sebaliknya jika Kunci Kunci maka bagian berkas mulai dari depan sampai dengan Kunci-tengah dieliminasi. Dengan mengulang proses pembandingan terhadap rekaman tengah, maka lokasi rekaman yang diinginkan akan ditemukan atau diketahui bahwa rekaman yang diinginkan tersebut tidak berada dalam berkas.

Program Pascal untuk Binary Search (pencarian biner) bekerja dengan membagi dua array terurut secara berulang untuk menemukan nilai target. Metode ini efisien dengan kompleksitas waktu, di mana posisi tengah dibandingkan dengan target, dan ruang pencarian dipersempit ke kiri atau kanan hingga ditemukan.

Berikut adalah contoh kode program Pascal untuk algoritma pencarian biner:

Pascal (Iteratif)

program BinarySearch;

uses crt;

{ Mendefinisikan tipe data array }

type

IntArray = array[1..100] of integer;

{ Fungsi Binary Search }

function BSearch(var arr: IntArray; n, target: integer): integer;

var

low, high, mid: integer;

begin

low := 1;

high := n;

BSearch := 0; { Default 0 jika tidak ditemukan }

while (low <= high) do

begin

mid := (low + high) div 2;

if (arr[mid] = target) then

begin

BSearch := mid; { Target ditemukan }

exit;

end

else if (arr[mid] < target) then

low := mid + 1 { Cari di kanan }

else

high := mid - 1; { Cari di kiri }

end;

{ Program Utama }

var

data: IntArray;

n, i, target, hasil: integer;

begin

clrscr;

write('Masukkan jumlah elemen: ');

readln(n);

{ Input data (harus terurut) }

writeln('Masukkan ', n, ' elemen terurut (ascending):');

for i := 1 to n do

begin

write('Elemen ', i, ': ');

readln(data[i]);

end;

write('Masukkan nilai yang dicari: ');

readln(target);

{ Panggil fungsi }

hasil := BSearch(data, n, target);

{ Output hasil }

if (hasil <> 0) then

writeln('Nilai ', target, ' ditemukan pada indeks: ', hasil)

else

writeln('Nilai ', target, ' tidak ditemukan.');

readkey;

end.

Algoritma Pencarian Biner yang lengkap diperlihatkan pada Algoritma 3.1 berikut ini.

Proc pencarian_biner

/* n buah rekaman dalam berkas diurutkan menaik menurut kunci rekaman */

1 AWAL:= 1

2 Akhir:= n

3 while AWAL ≤ AKHIR do

13 end

tengah:L(AWAL+AKHIR) / 2」

if kunci (cari) kunci (tengah) pencarian berakhir.

else if kunci (cari) > kunci (tengah)

AWAL TENGAH + 1

else

AKHIR: TENGAH-1

11 rekaman tidak ditemukan

end pencarian biner

Algoritma 3.1 Pencarian biner

Keterangan X menunjukkan integer X atau pembulatan terhadap X.

Python (Iteratif)

def binary_search(arr, target):

left = 0

right = len(arr) - 1

while left <= right:

mid = (left + right) // 2

# Cek jika target ada di tengah

if arr[mid] == target:

return mid

# Jika target lebih besar, abaikan separuh kiri

elif arr[mid] < target:

left = mid + 1

# Jika target lebih kecil, abaikan separuh kanan

else:

right = mid - 1

# Target tidak ditemukan

return -1

# Contoh Penggunaan

data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]

target = 23

result = binary_search(data, target)

print(f"Elemen ditemukan pada indeks: {result}") # Output: 5

C++

#include <iostream>

using namespace std;

int binarySearch(int arr[], int left, int right, int target) {

while (left <= right) {

int mid = left + (right - left) / 2;

if (arr[mid] == target)

return mid;

if (arr[mid] < target)

left = mid + 1;

else

right = mid - 1;

}

return -1;

}

int main() {

int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};

int n = sizeof(arr) / sizeof(arr[0]);

int target = 23;

int result = binarySearch(arr, 0, n - 1, target);

cout << "Elemen ditemukan pada indeks: " << result << endl; // Output: 5

return 0;

}

Algoritma Pencarian Biner membandingkan Key rekaman yang dicari dengan kunci rekaman pada posisi tengah dari berkas. Bila sama (kasus 1) berarti rekaman yang diinginkan sudah ditemukan, atau kalau tidak sama (kasus 2) berarti separuh dari rekaman-rekaman dalam berkas akan dieliminasi dari perbandingan yang selanjutnya. Bila yang terjadi adalah kasus 2 maka proses pembandingan terhadap rekaman pada posisi di tengah dilanjutkan menggunakan rekaman rekaman yang tersisa.