Data Based Management System

Pengertian SISTEM BASIS DATA

Merupakan sistem yang terdiri atas kumpulan file (table) dalam sebuah basis data di sebuah sistem komputer yang saling berhubungan dan sekumpulan program pengelola basis data (DBMS :Database Management System) yang memungkinkan beberapa pemakai dan atau program lain untuk mangakses dan memanipulasi file-file (table-table) tersebut.

Komponen Utama

·         HARDWARE

Hardware merupakan sistem computer actual yang digunakan untuk menyimpan dan mengakses databse. Dalam sebuah organisasi berskala besar, hardware terdiri : jaringan dengan sebuah server pusat dan beberapa program client yang berjalan di komputer desktop.

·         Aplikasi atau perangkat lunak yang bersifat opsional

adalah DBMS yang aktual. DBMS memungkinkan para user untuk berkomunikasi dengan database. Dengan kata lain DBMS merupakan mediator antara database dengan user. Sebuah database harus memuat seluruh data yang diperlukan oleh sebuah organisasi.

·         SISTEM OPERASI

Bagian integral dari setiap sistem adalah sekumpulan prosedur yang mengontrol jalannya sistem, yaitu praktik-praktik nyata yang harus diikuti user untuk mendapatkan, memasukkan, menjaga, dan mengambil data.

·         DATABASE

adalah jantung dari DBMS. Ada dua jenis data. Pertama, adalah kumpulan informasi yang diperlukan oleh suatu organisasi. Jenis data kedua adalah metadata, yaitu informasi mengenai database.

·         USER

Ada sejumlah user yang dapat mengakses atau mengambil data sesuai dengan kebutuhan penggunaan aplikasi-aplikasi dan interface yang disediakan oleh DBMS, antara lain adalah

1.       Pemrogram Aplikasi

2.       Pengguna Mahir (Casual User)

3.       Pengguna Awam (End User/Naïve User)

4.       Pengguna Khusus (Specialized User)

Abstraksi Data

Tingkatan / Level dalam melihat data daam sebuah basis data.

·         Level Fisik (Physical Level)

·         Level Konseptual (Conceptual Level)

·         Level Penampakan (View Level)

Komponen Bahasa BASIS DATA

·         Data Definition Language (DDL)

1.       Digunakan untuk mespesifikasikan struktur/skema basis data yang menggambarkan/mewakili desain basis data secara keseluruhan.

2.       Hasil kompilasi perintah DDL adalah kamus data >>File yang berisi metadata (data yang mendeskripsikan data sesungguhnya)

3.       Struktur penyimpan dan metode akses yang digunakan oleh sistem basis data disebut dengan data storage and definition language

·         Data Manipulation Language (DML)

1.       Digunakan untuk memanipulasi basis data

2.       Bentuk manipulasi

o   Pencarian kembali data lama

o   Penyisipan data baru

o   Penghapusan data

o   Pengubahan data

3.       Jenis DML 

o   Prosedural

user dapat menspesifikasikan data apa yang dibutuhkan data apa yang dibutuhkan  dan bagaimana untuk memperoleh data tersebut.

o   Non Prosedural

user menspesifikasikan data apa yang dibutuhkan tanpa menjelakan bagaimana data tersebut diperoleh.

QUERY PROCESSING

Pada query processing akan dipelajari 3 langkah sebagai berikut :

1.       Parsing dan Translasi yaitu memecah dan menterjemahkan query menjadi aljabar relasional.

2.       Optimisasi yaitu dipilihnya query yang paling minimum harga cost nya.

3.       Evaluasi yaitu mesin query-execution mengambil rencana query-evaluation, mengeksekusi plan tersebut, dan mengembalikan hasilnya.

Transaction Management

Pengertiannya adalah bagian dari aplikasi DataBase yang memastikan bahwa DataBase masih dalam keadaan konsisten.

Fungsi dari Concurrency Control Manager adalah mengontrol concurrency transaction untuk memastikan DataBase masih dalam keadaan konsisten.

Sistem computer yang dipakai DataBase diantaranya : Centralized, Client-Server, Parralel dan Distributed.

DataBase Administrator

Fungsinya antara lain adalah untuk mengatur semua aktifitas system database.

Tujuannya adalah :

1.       Mendefinisikan skema

2.       Menyimpan struktur dan mengakses metode definisi

3.       Membuat skema dan memodifikasi physical organization

Dibutuhkannya minimum cost dalam memilih evaluation plan pada query optimization, faktor besar kecilnya cost adalah :

Ø  Disk Access

Diukur dari :

·         Number of Seeks

·         Number of Block Read

·         Number of Block Write

·         Average-Seek-Cost

·         Average-Block-Read-Cost

·         Average-Block-Write-Cost

Ø  CPU

Ø  Network Communication

Menghitung Query Cost

t_T : time to transfer 1 block

t_{S :} time for 1 seek

 jadi cost untuk  b block dan S seek adalah:

b * t_T +S*t_S

Operasi Selection

A1

br= jumlah blok yang telah dibaca

cost:

- seleksi yang atributnya bukan merupakan key..

cost= br, karena dia harus menelusuri semua tuple dan menseleksinya

- kalau ternyata seleksi itu atributnya berupa key..

cost = br/2, merupakan avg cost maks br, sedangkan min 1

KELEBIHAN:bisa dipakai di segala kondisi, tidak memperedulikan ordering ataupun index,

A2

mulai pencarian dari tengah, dilihat dari  index yang dicari lebih besar atau lebih kecil, kemudian buka yang ditengah di bawah atau di atas

syaratnya atribut sudah terurut

kompleksitasnya log2(br)

A3

intinya A3 memiliki perbandingan di key atribut (equality on key, dan ada index nya)

costnya tinggi pohon + 1

knapa tambah 1: karena ditambah record yang akan diambil, jadi indexnya merupakan primary index (sudah berurutan). Kemudian  cost yg dbutuhkan kalo misal kita pake struktur b+ tree jadinya height si tree nya + record yg diambil.

b+ tree

mirip binary tree cuma leaf nya tidak hanya 2, tepatnya sebuah pohon index yang jumlah anaknya selalu sama

A4

masih primary index, tapi equalitynya bukan di key

jadi costnya harus ditambah  block yang masih punya record yang dicari, tidak hanya + 1 saja, tergantung blok yg terambil.

Jadi, kalau  misal record yg isinya search key ada 5, berarti+ 5.

A5

indexnya secondary akan tidak terurut dan seleksinya masih equality (yg non equality ada  di A6 dst)

index secondary: tidak terurut di fisiknya, misal index nya 1 2 3 tapi bisa saja disimpannya 1 3 2, biar tidak  perlu mencari sampai akhir di indexnya.

A6

Operasi perbandingan dengan primary index. Untuk kasus A>V, telusuri index untuk mencari nilai yang lebih besar daripada V, kemudian fetch table fisik, diikuti dengan fetch block selanjutnya yang memenuhi. Untuk kasus A<V, tanpa menelusuri index, langsung fetch blok pertama dan blok-blok selanjutnya sampai didapat nilai yang lebih besar dari V.

A7

Operasi perbandingan dengan secondary index. Untuk kasus A>V, telusuri index untuk mencari nilai yang lebih besar dari V, kemudian fetch blok pada table fisik. Karena index di table fisik tidak terurut, untuk mencari record selanjutnya, kita harus menelusuri index selanjutnya dan menelusuri pointer yang menunjuk ke record di table fisik lalu blok nya di fetch ke memori, begitu selanjutnya. Untuk kasus A<V, sama dengan A>V tetapi dimul

jadi ambil dari indeks pertama, sampai ketemu A<V pertama kali

a6 sama a7 mirip, bedanya ya a6 based on primary index, yg a7 dari scondary index

we can use a secondary ordered index to guide retrieval for comparison conditions

involving <, <=, >= ato > secondary index ini kan pointer ke records, a7 bisa jadi jelek sekali daripada linear search, kalau menunjuk ke records yang banyak, jadi a7 terbatas pada misalkan recordsnya yang dituju sedikit

A8

selection conjunctive dengan single index ambil salah satu kondisi, kemudian pilih algoritma dari A1 – A7 yang cost nya paling sedikit. Lalu algoritma yang sudah dipilih, diterapkan ke kondisi yang lain.

A9

selection conjunctive dengan multiple index Index yang kita miliki merupakan index yang komposit,

A10

 selection conjunctive dengan mencari intersection dari tiap-tiap kondisi. Tiap-tiap kondisi yang ada indexnya, di proses satu persatu kamudian hasilnya di simpan di memori buffer, kemudian hal yang sama dilakukan terhadap kondisi sisa. Lalu dilakukan intersection dari semua hasil yang ada di memori buffer.

QUERY EXECUTION

Dibutuhkan query execution plan, untuk membuat query ini dibutuhkan logical tree, lalu menerapkannya pada setiap node yang ingin diisi sesuai dengan pilihan yang telah ditentukan.

Langkah selanjutnya adalah :

Scheduling Operation

Leave of the Plan

Table Scan

Index Scan

Sorted Scan

Implementasi Relasi Operasional

Selection

Projection

Join

Set Difference

Union

Agregration

Implementasi Projection

Pada tahap ini terdapat 2 langkah awal yaitu :

1.       Menghapus atribut yang tidak dibutuhkan

2.       Menghapus duplikatnya

Kemudian refinement berfungsi sebagai menduplikat removal

Sorting

Alasan mengapa sorting memiliki peranan penting dalam sistem basis data adalah :

·         Query dapat dispesifikasian dan SQL-nya dapat disorting

·         Beberapa operasi relasional dapat diimplementasikan secara efisien jika input relasinya disorting terlebih dahulu.

Logically : unsufficient Memory

Physically : External Sorting

External Merge Sort

Analisa Cost :

Total number yang dibutuhkan pada merge passes adalah:[log_m-1(Br/M)].

Kita tidak perlu menghitung write costnya untuk final passnya.

Total number of block transfer untuk external sorting Br(2 [log _m-1(br/m)]+1)

Cost of Seek

Saat run generation, 1seek unutk membaca masing-maisng run dan  1seek ntuk menulis masing-masing run.

2[br/M]

Saat   merge pass

Buffer size:b_b(membaca atau menulis bufferblok pada saat itu)

Membutuhkan 2[b_r/b_b]seek untuk stiap merge pass.

Sehingga total number of seek adalah

2[br/M]+ 2[b_r/b_b]x Br(2 [log _m-1(br/m)]+1)

JOIN OPERATION

Terdapat beberapa algoritma berbeda yaitu :

Nested-loop Join

Block Nested-loop Join

Indexed Nested-loop Join

Merge Join

Hash Join

Untuk menentukan algoritma yang dipakai, maka harus didasarkan pada estimasi cost-nya.

Nested-loop Join

adalah join yang  dilakukan antara record per record, record di inner blok dijoin dengan 1 record di outer blok. Join dilakukan record per record. Jadi 1 record di relasi kiri, dijoinkan dengan semua record di relasi kanan, karena pergantian blok akan terjadi (sebanyak record di relasi kiri x blok di relasi kanan)  + jumlah blok relasi kiri. Cara ini paling boros. Cost di atas dapat dituliskan : (nr* bs) + br

misalnya R><S, untuk setiap tuple pada relasi R, makan cocokkan dengan tuple pada S

jika cocok, tuple tersebut di-join

maka costnya = (Nr*Bs)+Br

Nr: jml tuple relasi R

Br: jml block relasi R

Block Nested-loop Join

untuk R><S,

ambil dulu block pertama dari relasi R lalu, ambil block pertama dari relasi S

kemudian, dicocokan dengan masing2 tuplenya

costnya= (Br*Bs)+Br

Indexed Nested-loop Join

Prasyaratannya adalah bisa jalan kalau inner relasionnya berindex

Indexed Nested-loop Join = Nested-loop Join biasa, cuma yang dalam pake index

algoritma hasil akhirnya = Br + Nr * C

C : rata2 dari block read, write, seek

kalau keduanya punya index, yang outer harus lebih sedikit.

Merge join

Sort kedua relasi pada join atribut, kemudian merge relasi yang telah disort untuk menjoinkannya. Merge join ini hanya dapat digunakan pada equi njoin dan natural join. Berikut cost merge join

B_r+b_s block transfer +[ B_r/b_b]+[ B_s/b_b]+seeks+cost of sorting, jika belum terurut

Hibird merge join jika satu relasi disort,dan ynag lainya memiliki secondari B⁺- tree index, pada join attribute.

Hash Join

Sangat cocok untuk equi join dan natural join, fungsi h adalah untuk mempartisi tuple pada kedua relasi. H maps JoinAttrsmemiliki nilai {0, 1, ..., n}, JoinAttrs diartikan sebagai

common attributes pada  r dan s digunakan pada natural join.

r0, r1, . . ., r, n diartikan sebagai partisi pada tuples r.

 r,, r. . .,r diartikan pertisi pada tuple s

cost pada hash join

jika recursive partitioning  tidak diminta

 3( b_r+b_s )+4 *n_h block transfers +2(  b_r / b_b+b_s /b_b) seeks

jika recursive partitioning diminta:

◦ number of passes required for partitioning build relation

S adalah  logM–1( bs) – 1

◦ best to choose the smaller relation as the build relation.

◦ Total cost estimate is:

2 (br+ bs  logM–1( bs) – 1 + br+ bs block transfers +2(br / b + bs / bb) log_M–1( bs) – 1seeks

Hybird hash join

Sangat berguna,jika ukuran memori relatif besar sedangkan ukuran input lebih besar daripada memori. Fitur utama pada hybird hash join adalah jaga partisi pertama pada pembangunan relasi di memori.hybird hash join sangat berguna jika M>>√b_s

Complex join

Terdiri dari 2 macam join yaitu  join dengan  kondisi conjunctive .dan disjunctive.pada kondisi  conjunctive menggunakan nested loop /block nested loop, atau dengan mengkomputasikan hasil dari salah satu join yang sedarhana.sedangkan untuk disjunctive bisa menggunakan nested loop /block nested loop selain itu bisa menggunakan komputasi penggabungan record pada individual join.

 Operasi lainnya

Duplikat elimination: dapat diimplementasikan dengan menggunakan hashing atau sorting.

Agregrasi: dapat diimplementasikan pada manner yang sama untuk menduplikasi eliminasi.

Outer join: Jika terdapat baris yang tidak memenuhi kondisi join, dan akan ditampilkan pada

hasil query, maka digunakan outer join.

Evaluation of exspression

Terdapat dua macam cara untuk mengevaluasi entire expression tree, yaitu materialization dan pipelining.

Materialization mengevaluasi 1 operasi pada satu waktu, dimulai pada level yang paling rendah kemudian dilanjutkan ke atasnya. Cost untuk menulis result pada disk dan membaca kembali cenderung besar.

Pipelining

mengevaluasi banyak operasi secara bersamaan, melewati hasil satu opeasi ke berikutnya.pipelining jauh lebih murah dari pada  materialisasi, karena tidak perlu untuk menyimpan sementara
hubungan ke disk.
Pipelining mungkin tidak selalu bisa digunakan pada sort, hash-join.
pipelining untuk menjadi efektif, menggunakan algoritma evaluasi yang
menghasilkan output tupel bahkan sebagai tupel diterima untuk masukan kepada
operasi.  Pipelines  dapat diekseskusi  dalam dua cara: demand driven dan producer driven.

Pada deman driven

permintaan berulang-ulang sistem tupel berikutnya dari tingkat atas operasi
◦ Setiap permintaan operasi berikutnya operasi tupel dari children diperlukan, untuk output tupel berikutnya
◦ Di antara panggilan, operasi ini untuk mempertahankan "state" sehingga tahu  untuk kembali selanjutnya

pada producer driven

operator memproduksi tuples dengan semangat, dan meneruskanya ke parent.

Buffer dipertahankan antara operator, menempatkan anak tupel dalam  penyangga, orangtua menghapus tupel dari buffer  jika buffer sudah penuh, anak menunggu sampai ada ruang di dalam buffer,  dan kemudian menghasilkan lebih tupel  jadwal Sistem operasi yang memiliki ruang dalam output buffer  dan dapat memproses lebih banyak masukan tupel.

Evaluasi  Algoritma untuk Pipelining

Beberapa algoritma tidak bisa menghasilkan output, yaitu : merge join/ hash join.

Varian algoritma untuk menghasilkan (setidaknya beberapa) hasil on the fly, seperti
input tupel dibaca dalam hibrid  hash  join menghasilkan output gabung tupel bahkan sebagai probe
hubungan tupel dalam memori di-partisi (partisi 0) dibaca
teknik  pipelined join:  Hybrid hash join, dimodifikasi untuk buffer  partisi 0 tupel dari kedua relasi di memori, membaca mereka sebagai  mereka menjadi tersedia, dan output hasil setiap pertandingan
antara partisi 0 tupel  

·                     Ketika tupel r0 baru ditemukan, cocok dengan yang ada tupel s0,
output pertandingan, dan menyimpannya dalam r0

·                     Simetris untuk s0 tupel.