Implementasi Algoritma Divide and Conquer pada Sorting dan Searching

 Nama : Rian Pebriawan

NPM : 21312026

Kelas : IF 21A

Algoritma merupakan kumpulan perintah yang memiliki daya guna yang sangat besar bagi masyarakat. Algoritma biasanya digunakan sebagai kumpulan perintah untuk menyelesaikan suatu masalah. Algoritma ini memiliki aplikasi yang bermacam-macam dalam setiap masalah yang ada. Contohnya saja adalah algoritma cara menyelesaikan suatu aritmatika yang rumit, algoritma untuk menghitung luas penampang dari suatu kabel, atau bahkan untuk menghitung bayaran parkir di setiap mal. Salah satu aplikasi bentuk pemrograman ini adalah dalam bahasa permrograman yang disebut bahasa C. Dimana bahasa C ini memiliki suatu aturan-aturan tertentu yang sangat penting sehingga dalam penggunaanya kita harus memperhatikan cara menggunakan aturan tersebut. Salah satu cara penggunaannya adalah dengan array. Dimana array ini merupakan suatu data struktur yang berkoneksi satu sama lain dengan tipe yang sama. Aplikasi array ini banyak sekali, contohnya saja adalah menghitung golongan dari umur yang berjumlah 25 tahun hingga 55 tahun. Array ini juga bisa digunakan untuk mencari suatu elemen nilai dalam suatu struktur data, selain itu array ini juga bisa digunakan untuk mengurutkan data-data yang tidak berurutan. Hal –hal yang telah disebutkan disebut sebagai searching array dan sorting array.

    Sorting array merupakan salah satu aplikasi yang paling penting dalam suatu sistem aplikasi perhitungan data. Biasanya suatu bank memiliki komputasi sorting array yang sudah biasa digunakan dalam aplikasinya sehari-hari. Bahkan telephone juga mengurutkan suatu list yang terdiri dari nama akhir , nama awal agar bisa memudahkan dalam perhitungan dalam mencari nomor telephone.

    Searching array juga memiliki tak kalah pentingnya dibandingkan dengan sorting array. Pada searcing array kita biasa menggunakannya pada data yang sangat banyak. Sehingga sangat sulit bila kita ingin mencari suatu data atau suatu angka didalamnya satu per satu. Aplikasi searching array memudahkan kita dalam mencari suatu data atau angka yang kita inginkan dengan hanya memasukkan nilai input pada suatu data yang disikan.

1. Insertion sort

Salah satu algoritma sorting yang paling sederhana adalah insertion sort. Ide dari algoritma ini dapat dianalogikan seperti mengurutkan kartu. Penjelasan berikut ini menerangkan bagaimana algoritma insertion sort bekerja dalam pengurutan kartu. Anggaplah anda ingin mengurutkan satu set kartu dari kartu yang bernilai paling kecil hingga yang paling besar. Seluruh kartu diletakkan pada meja, sebutlah meja ini sebagai meja pertama, disusun dari kiri ke kanan dan atas ke bawah. Kemudian kita mempunyai meja yang lain, meja kedua, dimana kartu yang diurutkan akan diletakkan. Ambil kartu pertama yang terletak pada pojok kiri atas meja pertama dan letakkan pada meja kedua. Ambil kartu kedua dari meja pertama, bandingkan dengan kartu yang berada pada meja kedua, kemudian letakkan pada urutan yang sesuai setelah perbandingan. Proses tersebut akan berlangsung hingga seluruh kartu pada meja pertama telah diletakkan berurutan pada meja kedua. Algoritma insertion sort pada dasarnya memilah data yang akan diurutkan menjadi dua bagian, yang belum diurutkan (meja pertama) dan yang sudah diurutkan (meja kedua). Elemen pertama diambil dari bagian array yang belum diurutkan dan kemudian diletakkan sesuai posisinya pada bagian lain dari array yang telah diurutkan. Langkah ini dilakukan secara berulang hingga tidak ada lagi elemen yang tersisa pada bagian array yang belum diurutkan.

Algoritmanya :

void insertionSort(Object array[], int startIdx, int endIdx) 
{
   for (int i = startIdx; i < endIdx; i++) {
   int k = i;
   if(((Comparable) array[k]).compareTo(array[j])>0) {
   for (int j = i + 1; j < endIdx; j++) {
   k = j;
   }
   }
   swap(array[i],array[k]);
   }
}

 2. Selection sort

Jika anda diminta untuk membuat algoritma sorting tersendiri, anda mungkin akan menemukan sebuah algoritma yang mirip dengan selection sort. Layaknya insertion

sort, algoritma ini sangat rapat dan mudah untuk diimplementasikan. Mari kita kembali menelusuri bagaimana algoritma ini berfungsi terhadap satu paket kartu. Asumsikan bahwa kartu tersebut akan diurutkan secara ascending. Pada awalnya, kartu tersebut akan disusun secara linier pada sebuah meja dari kiri ke kanan, dan dari atas ke bawah. Pilih nilai kartu yang paling rendah, kemudian tukarkan posisi kartu ini dengan kartu yang terletak pada pojok kiri atas meja. Lalu cari kartu dengan nilai paling rendah diantara sisa kartu yang tersedia. Tukarkan kartu yang baru saja terpilih dengan kartu pada posisi kedua. Ulangi langkah – langkah tersebut hingga posisi kedua sebelum posisi terakhir dibandingkan dan dapat digeser dengan kartu yang bernilai lebih rendah.

Ide utama dari algoritma selection sort adalah memilih elemen dengan nilai paling rendah dan menukar elemen yang terpilih dengan elemen ke-i. Nilai dari i dimulai dari 1 ke n, dimana n adalah jumlah total elemen dikurangi 1.

Algoritmanya :

void selectionSort(Object array[], int startIdx, int endIdx) 
{
    int min;
     for (int i = startIdx; i < endIdx; i++) {
     if (((Comparable)array[min]).compareTo(array[j])>0) {
     min = i;
     for (int j = i + 1; j < endIdx; j++) {
      min = j;
}
      }
      }
       swap(array[min], array[i]);
      }

3. Merge sort

Beberapa algoritma mengimplementasikan konsep rekursi untuk menyelesaikan permasalahan. Permasalahan utama kemudian dipecah menjadi sub-masalah, kemudian solusi dari sub-masalah akan membimbing menuju solusi permasalahan utama.

Pada setiap tingkatan rekursi, pola tersebut terdiri atas 3 langkah.

1. Divide

    Memilah masalah menjadi sub masalah

2. Conquer

    Selesaikan sub masalah tersebut secara rekursif. Jika sub-masalah tersebut cukup ringkas dan sederhana, pendekatan penyelesaian secara langsung akan lebih efektif

3. Kombinasi

    Mengkombinasikan solusi dari sub-masalah, yang akan membimbing menuju penyelesaian atas permasalahan utama

Seperti yang telah dijelaskan sebelumnya, Merge sort menggunakan pola divide and conquer. Dengan hal ini deskripsi dari algoritma dirumuskan dalam 3 langkahberpola divide-and-conquer. Berikut menjelaskan langkah kerja dari Merge sort.

1. Divide

    Memilah elemen – elemen dari rangkaian data menjadi dua bagian.

2. Conquer

    Conquer setiap bagian dengan memanggil prosedur merge sort secara rekursif

3. Kombinasi

    Mengkombinasikan dua bagian tersebut secara rekursif untuk mendapatkan rangkaian data berurutan

Proses rekursi berhenti jika mencapai elemen dasar. Hal ini terjadi bilamana bagian yang akan diurutkan menyisakan tepat satu elemen. Sisa pengurutan satu elemen tersebut menandakan bahwa bagian tersebut telah terurut sesuai rangkaian.

Algoritmanya :

void mergeSort(Object array[], int startIdx, int endIdx) 
{

if (array.length != 1) {

mergeSort(leftArr, startIdx, midIdx);
//Membagi rangkaian data, rightArr dan leftArr


}
mergeSort(rightArr, midIdx+1, endIdx);

combine(leftArr, rightArr);

}

                                         Gambar3.1. Diagram Merge Sort

4. Quick sort

Quicksort ditemukan oleh C.A.R Hoare. Seperti pada merge sort, algoritma ini juga berdasar pada pola divide-and-conquer. Berbeda dengan merge sort, algoritma ini hanya mengikuti langkah – langkah sebagai berikut :

1. Divide

    Memilah rangkaian data menjadi dua sub-rangkaian A[p…q-1] dan A[q+1…r] dimana setiap elemen A[p…q-1] adalah kurang dari atau sama dengan A[q] dan setiap elemen pada A[q+1…r] adalah lebih besar atau sama dengan elemen pada A[q]. A[q] disebut sebagai elemen pivot. Perhitungan pada elemen q merupakan salah satu bagian dari prosedur pemisahan.

2. Conquer

    Mengurutkan elemen pada sub-rangkaian secara rekursif

Pada algoritma quicksort, langkah “kombinasi” tidak di lakukan karena telah terjadi pengurutan elemen – elemen pada sub-array

Algoritmanya :

void quickSort(Object array[], int leftIdx, int rightIdx) {

int pivotIdx;

/* Kondisi Terminasi */

pivotIdx = partition(array, leftIdx, rightIdx);
if (rightIdx > leftIdx) {


quickSort(array, leftIdx, pivotIdx-1);
}

quickSort(array, pivotIdx+1, rightIdx);

}

                    Gambar 3.2. Diagram Quick Sort

5. Counting sort

Adalah sebuah algoritma sorting linear yang digunakan untuk mengurutkan ‘item’ ketika urutannya telah ditentukan dan memiliki panjang yang terbatas. Bilangan interval yang telah tetap, katakana k1 ke k2 adalah contoh dari ‘item’ tersebut. Counting sort sebenarnya merupakan metode pengurutan yang memanfaatkan index variabel array. Hanya effektif pada data yang nilainya kecil.

Algoritma ini diproses dengan mendefinisikan sebuah hubungan urutan antara ‘item’ yang akan disorting. Katakana ‘item’ yang akan disorting adalah variable A. Maka, terdapat sebuah array tambahan dengan ukuran yang serupa dengan array A. katakana array tersebut adalah array B. untuk setiap element di A, sebut e, algoritma ini menyimpan jumlah ‘item’ di A lebih kecil dari atau sama dengan e di B(e). jika hasil sorting yang terakhir disimpan di array C, maka untuk masing-masing e di A, dibuat dalam arah yang sebaliknya, yaitu C[B(e)]=e. setelah step di atas, niali dari B(e) berkurang dengan 1.

Algoritma ini membuat 2 passover A dan passover B. Jika ukuran dari range k lebih kecil dari ukuran input n, maka time complexity = O(n). perhatikan juga bahwa algoritma ini stabil yang berarti bahwa sambungan diselesaikan dengan langsung mengabarkan element-element yang muncul pertama kali.

Adapun syarat algoritma ini berjalan dengan baik ialah:

1. Data harus bilangan bulat yang bernilai lebih besar atau sama dengan nol
2. Range data diketahui

Ada 3 macam array yang terlibat:

1. Array untuk mengisi bilangan yang belum diurutkan.
2. Array untuk mengisi frekuensi bilangan itu, sekaligus sebagai penghitung kejadian.
3. Array untuk mengisi bilangan yang sudah diurutkan.
   Algoritmanya :

countingsort(A[], B[], min, max, n)
for i = min to max do
C[i] = 0

C[A[j]] = C[A[j]] + 1
for j = 1 to n do

for i = min + 1 to max do
B[C[A[j]]] = A[j]
C[i] = C[i] + C[i-1]

for j = n downto 1 do
C[A[j]] = C[A[j]] – 1

                                                        Gambar 3.3 Diagram Counting Sort

6. Radix Sort

Radix sorting bisa digunakan ketika masing-masing universal element bisa dilihat sebagai sebuah urutan digit (atau huruf atau symbol lainnya). Sebagai contoh, kita bisa membuat masing-masing bilangan bulat antar 0 sampai 99 sebagai sebuah urutan dengan dua digit (seperti “05”). Untuk menyorting sebuah array dari angka 2-digit, algoritma ini membuat dua ‘passing’ sorting melalui array tersebut. Pada ‘passing’ pertama, element array disorting pada least significant decimal digit. Kunci utama dari radix sort adalah pada passing yang kedua. Hasilnya, setelah kedua passing melewati array tersebut, data yang terisi telah disorting.

Algoritmanya :

source

List of bytes
source_n

number of bytes to sort
dest[256]

256 lists of bytes. each list should have enough space to hold source_n elements.
//——————-saving element in memory——————–

int distribution[256]
// fill the list with zeros.
for i=0 to source_n do
for i=0 to 255 do
distribution[i]=0;

// build a distribution history:


distribution] = distribution] +1;
for i=0 to 255 do
endfor

// Now we build a index-list for each possible element:

int index[256];

index [0]=0;


for i = 0 to source_n do
index[i]=index[i-1]+distribution[i-1];

endfor
//sorting
dest: array of bytes with space for source_n bytes.
 
endfor
  dest[index]]=source[i];
  index] = index] +1;

7. Searching

7.1 Linear Searching

Algoritma pencarian secara linear adalah algoritma untuk mencari sebuah nilai pada table sambarang dengan cara melakukan pass atau transversal. Transversal dari awal sampai akhir table. Ada dua macam cara pencarian pada table. Algoritma mempunyai dua jenis metode yaitu dengan Boolean dan tanpa Boolean.

Algoritmanya :

void SeqSearch1 (int T[], int Nmax,

int value, int *idx)
{
/*Algoritma*/
/*kamus lokal*/
int i;
i = 1;
i = i + 1;
while ((i<Nmax) && (T[i] !=
value))
{
}
if (T[i]==value)
}
{
*idx = i;
}
else
{
*idx = 0;
}

Algoritma di atas melakukan pengulangan sampai i sama dengan Nmax (ukuran tabel) atau harga value dalam tabel sudah ditemukan.    Kemudian harga i di-assign ke dalam variable idx. Elemen terakhir diperiksa secara khusus.

void SeqSearch2 (int T[],int Nmax,

int value, int *idx)

{

int i;

i = 1;
boolean found;

/*algoritma*/


found = false;

if (T[i] == value)
while ((i<=Nmax) && (!found))

{


{

found = true;

}

else

{

i = i + 1;

}
}

}

if (found)

{

*idx = i;

}

else

{
*idx = 0;

7.2 Binary Searching

Algoritma pencairan secara linear melakukan pengulangan sebanyak 1 kali untuk kasus terbaik (value sama dengan elemen pertama dalam tabel) dan Nmax kali untuk kasus terburuk. Sehingga algoritma ini mempunyai kompleksitas algoritma O(n).

Implementasi algoritma pencarian biner dalam bahasa C adalah sebagai berikut.

void BinSearch (int T[],int Nmax, int

value, int* idx)

int i,j,mid;

found = false;
boolean found;$

/*algoritma*/


i = 1;

mid = (i+j) div 2;
j = Nmax;

while ((!found) && (i<=j))

{



if (T[mid] == value)

{

found = true;

}

else

{

if (T[mid]<value)

{

i = mid + 1;

}

else

{

j = mid – 1;

}
}

}
}
if (found)

{

*idx = mid;

}
else

{

*idx = 0;
}

Algoritma pencarian biner adalah algoritma untuk mencari sebuah nilai pada tabel teurut dengan cara menghilangkan setengah data pada setiap langkah. Algoritma ini mencari nilai yang dicari dengan tiga langkah yaitu :

• Mencari nilai tengah dari tabel (median).

• Melakukan perbandingan nilai tengah dengan nilai yang dicari untuk menentukan apakah nilai yang dicari ada pada sebelum atau setelah nilai tengah.

• Mencari setengah sisanya dengan cara yang sama.

Berbagai Permasalahan yang Dapat Diselesaikan Dengan Algoritma

Nama : Rian Pebriawan

NPM : 21312026

Kelas : IF 21A

Fakultas        : https://ftik.teknokrat.ac.id/

Universitas    : https://teknokrat.ac.id/

Pada masa sekarang ini, terdapat banyak sekali cara-cara penyelesaian persoalan yang dapat dilakukan oleh komputer. Mulai dari cara penyelesaian persoalan dengan cara yang mengutamakan kemudahan pemikiran manusia, sederhana, pasti menemukan solusi tetapi memiliki kompleksitas algoritma yang sangat besar seperti penyelesaian dengan brute force dan exhaustive search, penyelesaian dengan mengutamakan kecepatan menemukan satu solusi, yang dianggap optimal, sangat tinggi, seperti algoritma greedy, ataupun algoritmaalgoritma lain yang mengutamakan kemangkusan algoritma tetapi memiliki tingkat kerumitan cukup tinggi, seperti BFS, DFS, Backtracking, Branch and Bound dan dynamic programming. Secara ideal, jika ditemukan penyelesaian suatu permasalahan yang cepat, mudah, kemangkusannya tinggi, dan pasti menemukan solusi, pasti algoritma tersebut akan selalu dipakai, akan tetapi sayangnya sampai saat ini hal tersebut belum dapat terjadi. Pada beberapa kasus, kadang diinginkan algoritma yang mudah (seperti pada brute force ataupun greedy), cepat (seperti pada algoritma greedy), dan sedekat mungkin dengan solusi optimum global (seperti pada brute force). Pada makalah ini akan dibahas penyelesaian masalah dengan menggunakan kombinasi dari algoritma brute force dan freedy, memiliki ketepatan solusi yang cukup optimal dan kecepatan yang cukup tinggi.

Penggunaan algoritma yang tepat pada permasalahan yang tepat (atau pada sebuah program) akan sangat menguntungkan bagi pengguna program tersebut. Dengan penggunaan algoritma yang tepat, waktu yang dibutuhkan untuk penyelesaian suatu permasalahan akan semakin tinggi. Sayangnya, sampai saat ini suatu penyelesaian yang paling sederhana, yaitu algoritma brute force, memiliki kemangkusan yang sangat rendah. Sayangnya lagi, algoritma dengan kemangkusan paling tinggi, yaitu algoritma greedy, memiliki ketepatan penyelesaian yang tidak 100% benar. Penggabungan dari kedua algoritma tadi sangat mungkin dapat menghasilkan sebuah algoritma baru yang lebih mangkus dari brute Force dan lebih optimum dari greedy.

Secara umum, algoritma Brute Force dapat dilihat pada “penampilan luar”-nya (pada source code dan kecepatan program) yang pendek, mudah dimengerti dan membutuhkan cukup banyak waktu (terutama pada program yang besar). Atau dengan bahasa lain, brute force adalah sebuah pendekatan yang lempang (straightforward) untuk memecahkan suatu masalah, biasanya didasarkan pada pernyataan masalah (problem statement) dan definisi konsep yang dilibatkan. Sedangkan algoritma greedy dapat dilihat terutama pada kecepatan program yang sangat tinggi, akan tetapi kadang-kadang hasilnya agak mengecewakan karena tidak sesuai dengan solusi optimum yang diharapkan. Atau dengan kata lain, algoritma greedy membentuk solusi langkah per langkah (step by step), dan prinsip greedy adalah “take what you can get now!”. 

Persoalan: Misalkan kita ingin menukarkan uang senilai A dengan sekumpulan uang koin dari berbagai satuan (dengan asumsi tersedia banyak koin untuk setiap satuan, sehingga tidak mungkin terjadi kekurangan koin). Berapa jumlah minimum koin yang diperlukan tersebut? Contoh: koin-koin yang tersedia bernilai 12, 7, 4, dan 2 (dalam jumlah yang banyak untuk tiap satuan). Bagaimana cara menukarkan uang sebanyak 18 dengan koin-koin tersebut? Dengan sedikit pengetahuan, dapat diketahui bahwa jumlah koin yang diperlukan tidak akan lebih jumlah uang dibagi dengan pecahan terkecil koin dan tidak akan kurang dari jumlah uang dibagi dengan pecahan terbesar koin. Jadi bisa dipastikan bahwa jumlah koin yang diperlukan tidak akan lebih dari 9. Untuk memudahkan, dipergunakan sebuah koin maya bernilai 0, sehingga jika hanya dipilih 2 koin (anggap 12 dan 4) sama seperti dipilih S = {0, 0, 0, 0, 0, 0, 0, 4, 12} dengan S adalah himpunan koinkoin yang diambil. Dengan brute force, dapat dicoba semua kemungkinan pilihan, mulai dari S = {0, 0, 0, …, 0}, S = {0, 0, …, 0, 2}, sampai S = {12, 12, 12, …, 12}, dengan rumus kombinasi berulang, berarti harus dicoba sebanyak 59 = 1.953.125 cara, untuk masingmasing cara, harus dihitung jumlah tiap-tiap elemen himpunan, jika sama dengan 18 diambil, jika tidak dibuang. Berarti jumlah perhitungan yang harus dilakukan adalah sebanyak 2 x 59 ≈ 4.000.000 cara. Pada kondisi akhir, akan diperoleh semua kemungkinan pilihan koin yang bisa dijadikan solusi, yaitu S1 = (0, 0, 0, 0, 0, 0, 2, 4, 12) S2 = (0, 0, 0, 0, 0, 0, 4, 7, 7) S3 = (0, 0, 0, 0, 0, 2, 2, 2, 12) S4 = (0, 0, 0, 0, 0, 2, 2, 7, 7) … Sn = (2, 2, 2, 2, 2, 2, 2, 2, 2) Kemudian dipilihlah solusi yang paling sedikit menggunakan koin nyata, atau dengan kata lain dipilih solusi yang paling banyak menggunakan “koin 0”. Sehingga diperoleh dua solusi yaitu: (2, 4, 12) dan (4, 7, 7). Cara kedua, dengan algoritma greedy, akan dipilih satu koin terbesar dan jumlahnya dengan koin sebelumnya yang telah diambil tidak lebih dari 18 (pada kondisi awal, jumlah koin sebelumnya adalah 0). Langkah-langkah algoritma greedy: 1. Ambil koin 12, jumlah = 12 2. Ambil koin 4, jumlah = 16 3. Ambil koin 2, jumlah = 18 Ditemukan solusi, stop. Sehingga diperoleh satu solusi, yaitu (12, 4, 2). Pada kasus umum, jika diketahui bahwa koin-koin yang tersedia adalah k1 < k2 < … < kn dan uang yang akan ditukarkan adalah u, serta m – 1 < u / k1 ≤ m, m adalah bilangan bulat. Berarti banyak koin tidak akan lebih dari m. Sehingga komplesitas algoritma untuk penyelesaian secara brute force adalah O((n+1)m) ≈ O(nm). Sedangkan untuk algoritma greedy, pemilihan bilangan terbesar yang memenuhi tidak akan memakan waktu lebih dari n, serta banyaknya koin yang dipilih tidak akan lebih dari m, berarti kompleksitasnya adalah O(nm). Dari 2 perhitungan diatas, dapat disimpulkan bahwa penyelesaian secara greedy jauh lebih mangkus daripada penyelesaian secara brute force, meski dalam beberapa kasus lainnya yang tidak dituliskan disini, ada kejadian dimana solusi dari algoritma brute force lebih memuaskan daripada solusi dari algoritma greedy (dan tidak mungkin terjadi sebaliknya), atau bahkan solusi ditemukan hanya dengan algoritma brute force saja, tidak dengan greedy, misalnya koin yang tersedia adalah 12 dan 7 saja sedangkan uang yang ingin ditukarkan adalah 14. 

Persoalan: Misalkan kita diberikan beberapa buah barang dengan keuntungan serta beratnya masingmasing, akan tetapi container yang kita miliki hanya dapat memuat sejumlah berat tertentu. Pilih barangbarang yang akan dibawa sehingga keuntungan yang diperoleh maksimum. Contoh: Terdapat 6 benda (labeli 1 sampai 6), dengan wi adalah berat benda ke-i dan pi adalah keuntungan benda ke-i. w1 = 100 p1 = 40 w2 = 50 p2 = 35 w3 = 45 p3 = 18 w4 = 20 p4 = 4 w5 = 10 p5 = 10 w6 = 5 p6 = 2 Kapasitas knapsack K = 100 Tuliskan solusi sebagai X = (x1, x2, …, x6) dengan xi = 0 jika benda ke-i dibawa atau xi = 1 jika benda ke-i tidak dibawa. Penyelesaian dengan brute force: Coba semua kemungkinan X, mulai X = (0, 0, 0, 0, 0, 0), sampai dengan X = (1, 1, 1, 1, 1, 1). Jumlah kemungkinan yang harus dicoba ada 26 = 64 cara. Tiap cara harus dihitung berat totalnya, dan dari semua cara yang berat totalnya tidak melebihi kapasitas knapsack, pilih satu yang keuntungannya paling besar.  

Rangkuman Relational Database

NAMA : RIAN PEBRIAWAN
NPM : 21312026

KELAS : IF 21A

Relational Database (1)

Relational Database adalah suatu model database yang disajikan dalam bentuk tabel. 

• Tujuan Database :

1. Untuk menekankan kemandirian data 
2. menghilangkan inkonsistensi dan redudansi data menggunakan konsep normalisasi 
3. meningkatkan kemampuan akses data

• Karakteristik Relational Database

1. Struktur Tabular 
2. Satu bahasa digunakan untuk semua pemakai
3. Data dihubungkan melalui nilai data

• Model Data Relasional mengandung 3 komponen inti:

1. Struktur data (data diorganisasikan dalam bentuk tabel)
2. Manipulasi data (menggunakan SQL)
3. Integritas data (Menjamin konsistensi data)

• Contoh Domain Atribut dan Atura Integritas

• Contoh Integritas Refensial

Daur Hidup (LIfe Cycle) yang Umum dari Aplikasi Basis Data

• System Definition
• Database Design
• Implementation
• Loading/Data Convertion
• Konversi Aplikasi 
• Testing Dan Validasi 
• Operations
• Control dan Maintenance

• Definisi Sistem

1. Ruang lingkup basis data
2. pemakai
3. aplikasi

• Design

1. logical design --> ER/EER
2. phsical design untuk suatu DBMS

•  Implementasi

1. membuat basis data
2.  membuat program aplikasi

• Loading/ Konversi Data

1. memasukkan data ke dalam basis data 
2. mengkonversi file yang sudah ada ke dalam format basis data dan kemudian memasukkannya dalam basis data

• Konversi Aplikasi

Semua aplikasi dari sistem sebelumnya dikonversikan ke dalam sistem basis data.

• Testing dan Validasi

Sistem yang baru harus ditest dan divalidasi (diperiksa keabsahannya)

• Operasi 

Pengopresasian basis data dan aplikasinya.

• Monitoring dan Maintenance

Selamat operasi, sistem dimonitor dan diperlihara. Baik data maupun program aplikasi masih dapat terus tumbuh dan berkembang.

Database design

Proses Design Sistem Basis Data

Basis Data biasanya merupakan salah satu bagian dari suatu sistem informasi yang besar yang antara lain terdiri dari:

• Data
• Perangkat lunak DBMS
• Perangkat keras komputer
• Perangkat lunak dan sistem operasi komputer
• Program-program aplikasi
• Pemrogram, dll

1. Pengumpulan dan analisa requirement
2. Design basis data conceptual
3. Pemilihan DBMS
4. Mapping dari conceptual ke logical
5. Physical Design
6. Implementasi 

 Proses design terdiri dari dua proses yang paralel yaitu:

• proses design dari data dan struktur dari basis data (data driven)
• proses design dari program aplikasi dan pemrosesan basis data (process driven)

Mengapa Harus Paralel 

Karena kedua proses tersebut saling bergantungan.

Contoh:

1. Menentukan data item yang akan disimpan dalam basis data tergantung dari aplikasi basis data tersebut, juga dalam menentukan struktur dan akses path.
2. Design dari program aplikasi tergantung dari struktur basis datanya.
3. Biasanya condong ke salah satu.

 

Phase 1: Pengumpulan Data &  Analisa Requirement

Pengidentifikasian group pemakai dan area aplikasi

• Penelitian kembali dokumen-dokumen yang sudah ada yang berhubungan dengan aplikasi  form, report, manual, organization chart, dsb
• Analisa lingkungan operasi dan kebutuhan dari pemrosesan, seperti tipe transaksi, input/output, frekuensi suatu transaksi, dsb
• Transfer informasi informal ke dalam bentuk terstruktur menggunakan salah satu bentuk formal dari requirement specification (bentuk diagram) seperti Flow Chart, DFD, UML Diagram, dll. Hal ini dilakukan untuk mempermudah pemeriksaan kekonsistenan, ketepatan, dan kelengkapan dari spesifikasi.

Phase 2: Design Conceptual

Phase 2A: Design Conceptual Schema

• High level data model, bukan implementation-level data model
• Memberikan gambaran yang lengkap dari struktur basis data yaitu arti, hubungan, dan batasan-batasan.
• Conceptual schema bersifat tetap
• Alat komunikasi antar pemakai basis data, designer, dan analis

 Phase 2: Design Conceptual (cont’d)

Phase 2A: Design Conceptual Schema

• Harus bersifat:

1. Mampu menyatakan relationship, batasan-batasan
2. Diagram
3. Formal, minimum dalam menyatakan spesifikasi data (tidak ada duplikasi)
4. Simple

• Conceptual data model harus DBMS independent  ER/EER

Contoh ERD

Phase 2b: Design Transaksi

• Pada saat suatu basis data di-design, aplikasi dari transaksi utama harus sudah diketahui
• Transaksi-transaksi baru dapat didefinisikan kemudian
• Tentukan karakteristik dari transaksi  dan periksa apakah basis data sudah memuat semua informasi untuk melaksanakan transaksi

Phase 2b: Design Transaksi (cont’d)      

• Transaksi dapat dibagi dalam 3 bagian yaitu:

              - retrieval

              - update

              - mixed

• Phase 2a dan 2b sebaiknya dilaksanakan secara paralel dengan menggunakan umpan balik agar didapat design schema dan transaksi yang stabil

Phase 3: Pemilihan DBMS

Pemilihan DBMS ditentukan oleh sejumlah faktor antara lain:

• faktor teknis: storage, akses path, user interface, programmer, bahasa query, data models
• faktor ekonomi: software, hardware, maintenance, training, operasi, konversi, teknisi, dll
• faktor organisasi: kompleksitas, data, sharing antar aplikasi, perkembangan data, pengontrolan data

 Phase 4: Mapping dari Data Model

• Memetakan conceptual model ke dalam DBMS
• Menyesuaikan schema dengan DBMS pilihan
• Hasil pemetaan biasanya berupa DDL

 

Phase 5: Physical Design

• Struktur storage, akses path untuk mendapatkan performance yang baik
• Kriteria baik dapat dilihat dari:

              - response time

              - pemakaian storage

              - throughput (jumlah transaksi per unit waktu)

• Perlu tuning untuk memperbaiki performance berdasarkan statistik pemakaian

 

Phase 6: Implementasi Sistem Basis Data

• DDL dan SDL dari DBMS dikompilasi membentuk schema basis data dan basis data yang masih kosong
• Basis data dapat dimuati (di-load) dari sistem yang lama
• Transaksi dapat diimplementasikan oleh program aplikasi dan dikompilasi
• Siap dioperasikan

Rangkuman Konsep Basis Data

NAMA : RIAN PEBRIAWAN
KELAS : IF 21A
NPM : 21312026
MATKUL : SISTEM BASIS DATA

DATA 

• Representasi fakta dunia nyata yang mewakili suatu objek yang direkam dalam bentuk angka, huruf, simbol, teks, gambar, bunyi, atau kombinasinya

BASIS DATA

• Secara harfiah: Basis (base): Markas/Gudang, tempat berkumpul/bersarang
• Pengertian Basis Data dari berbagai sudut pandang;
  • Himpunan kelompok data (arsip) yang saling berhubungan yang diorganisasikan sedemikian rupa agar kelak dapat dmanfaatkan kembali dengan cepat dan mudah
  • Kumpulan data yang saling berhubungan yang disimpan secara bersama sedemikian rupa dan tanpa pengulangan yang tidak perlu, untuk memenuhi berbagai kebutuhan.
  • Kumpulan file/tabel/arsip yang saling berhubungan yang disimpan dalam media penyimpanan elektronis.

OPERASI DASAR BASIS DATA

Operas-Operasi dasar yang dapat dilakukan dalam sebuah basis data.

• Create Database : pembuatan basis data baru
• Drop Database : Penghapusan basis data
• Create Table : pembuatan file/tabel ke suatu basis data
• Drop Table : penghapusan file/tabel dari suatu basis data
• Insert Data : penambahan/pengisian
• Retrieve/Search : pengambilan dengan cara mencari tempat simpan
• Update : pengubahan data dari sebuah file/tabel
• Delete : penghapusan data dari sebuah file/tabel

TUJUAN BASIS DATA 

Tujuan dari dibuatnya suatu basis data;

• Speed : kecepatan dan kemudahan pemanfaatan basis data
• Space : efisiensi ruang penyimpanan
• Accuracy : keakuratan
• Availability : Ketersediaan pada waktu diperlukan
• Completeness : kelengkapan data
• Security : keamanan

DEFINISI SISTEM BASIS DATA

Definisi:

merupakan sistem yang terdiri atas kumpulan file/tabel yang saling berhubungan (dalam sebuah database sistem komputer) dan sekumpulan program (DBMS) yang memungkinkan beberapa pemakai dan/atau program lain untuk mengakses dan memanipulasi file-file/tabel-tabel tersebut.

APA SAJA KOMPONEN SDB?

• Hardware
  • Komputer (stand alone, Jaringan)
  • Memori Sekunder (on-line à hardisk, off-line à tape, removable disk)
  • Perangkat komunikasi (untuk sistem jaringan)
• Sistem Operasi, Program yang mengaktifkan/memfungsikan sistem komputer, mengendalikan seluruh sumber daya dalam komputer dan melakukan operasi-operasi dasar dalam komputer.
  • Contoh Sistem operasi à MS-DOS, MS Windows 3x/9x/me/2k/NT, Novel-Netware, Unix, Sun-Solaris
• Database, Database memiliki/berisi :
  • Objek database (seperti tabel, Index, File, Query,dll).
  • Definisi struktur (baik tabel, Index, File, dll).
• Sistem (aplikasi/sofware) Pengelola Basis Data (DBMS).
• Pemakai
• Software (aplikasi) lain sifatnya opsional.

BAHASA BASIS DATA

DDL

• Merupakan skema/struktur basis data yang menggambarkan/mewakili rancangan basis data secara keseluruhan yang dirinci/dispesifikasikan dengan bahasa khusus.
• Hasil dari kompilasi dari DDL adalah kumpulan tabel yang disimpan dalam file khusus yang disebut Kamus Data (Data Dictionary)
• Data Dictionary à yang merupakan suatu metadata/superdata.
• Metadata (superdata) à data yang mendiskripsikan/mereprentasikan data sesungguhnya.

DML

• DML merupakan bentuk bahasa basis data yang berguna untuk manipulasi dan pengambilan data.
• Manipulasi dapat berupa:
  • Penyisipan/penambahan data
  • Penghapusan data
  • Pengubahan data
• Terdapat 2 jenis DML:
  • Prosedural à mensyaratkan agar pemakai menentukan data apa yang diinginkan serta bagaimana cara mendapatkannya.
  • Non Procedural à yang membuat pemakai menentukan data apa yang diinginkan tanpa menyebutkan bagaimana cara mendapatkannya.

KOMPONEN FUNGSIONAL DBMS

Komponen Fungsional dari DBMS sebagai Berikut:

• File Manager

mengelola alokasi ruang media penyimpan dalam disk

• Database Manager

menyediakan antarmuka (interface) dalam basis data antara aplikasi program dan query (perntaan/perintah) yang diberikan dalam sistem.

• Query Processor

penerjemah perintah-perintah dalam query language ke perintah yang dapat dimengerti oleh database manager.

• DML Precompiler

berinterkasi dengan query processor untuk mengkonversi perintah DML yang ditambahkan dalam sebuah program aplikasi ke pemanggilan prosedur normal dalam bahasa induk.

• DDL Compiler

mengkonversi perintah-perintah DDL ke sekumpulan tabel yang mengandung metadata.