Page 194 - E-Modul Simbad_Neat

Meskipun algoritma ini menjadi tidak efisien dalam banyak kasus, ia dapat

diterapkan terhadap file apa pun, tidak peduli apakah tersebut terurut atau tidak dan

memiliki indeks atau tidak.

• Aa (pencarian biner/binary search).

Jika file terurut berdasarkan sebuah atribut, dan kondisi seleksi (dala bentuk

pembandingan) melibatkan atribut tersebut, maka kita dape menggunakan

algoritma pencarian biner untuk menemukan baris data yang memenuhi kondisi

seleksi tersebut. Algoritma ini dibentuk terhadap blok file, dengan estimasi

sebagai berikut:

( , )
= [ ( )] + [ ] −

Bagian pertama, yakni [log2 (br)], merupakan estimasi biaya un mencari

baris data pertama yang memanfaatkan algoritma pencaria biner. Sementara

banyaknya baris data yang akan memenuhi konda seleksi adalah SCA, r), dan akan

menempati [SCIA, r)/f blok file yang anggota pertamanya telah dibaca (sehingga

dikurangi dengan 1).

Jika kondisi seleksi berbentuk persamaan terhadap atribut yang menjadi key

pada tabel r, sehingga SCIA, r) = 1, maka estimasi biaya query menjadi E-flog. (b)

Sebagai ilustrasi untuk melihat perkiraan biaya dalam pengeksekusian

query, berikut ini contoh informasi statistik yang berkaitan dengan tabel

Mahamahasiswa yang memiliki 4 field yaitu npm, nama mhs, alamat mhs dan tgl

lahir:

• Fmahamahasiswa=20

ada 20 baris data dari tabel Mahamahasiswa yang muat dalam satu blok

• V(npm,mahamahasiswa)= 10000

181