Organisasi file
Element pokok perancangan system akses adalah cara
record-record diorganisasikan atau distrukturkan.
Beberapa criteria umum untuk pemilihan organisasi
file adalah [WIE-87]
•
Redudansi yang kecil
•
Pengaksesan yang cepat
•
Kemudahan dalam memperbaharui
•
Pemeliharaan yang sederhana
•
Kehandalan yang tinggi
Terdapat
enam organisasi dasar, kebanyakan organisasi file system termasuk salah satu
atau kombinasi kategori-kategori ini. Enam organisasi pengaksesan file secara
dasar adalah sebagai berikut :
1. File
pile (pile file)
2. File sekuen (sequential file)
3. File sekuen berindeks (indexed-sequenstial file)
4. File berindek majemuk (multiple-indexed file)
5. File ber-hash (hashed file)
6. File cincin (multiring file)
Keenam organisasi dasar ini dirinci dibukua Gio Wiederhold [WIE-87].
2. File sekuen (sequential file)
3. File sekuen berindeks (indexed-sequenstial file)
4. File berindek majemuk (multiple-indexed file)
5. File ber-hash (hashed file)
6. File cincin (multiring file)
Keenam organisasi dasar ini dirinci dibukua Gio Wiederhold [WIE-87].
A. PILE FILE
Pembahasan struktur file diketahui bahwa struktur
dasar paling dasar sebuah file adalah pile dan file sekuensial. File pile atau
file tumpukan merupakan struktur paling sederhana. Struktur ini jarang
digunakan secara praktis tapi merupakan basis evaluasi struktur-struktur lain.
Properti struktur pile
- Data
tidak dianalisis, dikategorikan, atau harus memenuhi definisi atau ukuran
field tertentu
- Panjang
rekord dapat bervariasi dan elemen-elemen data tidak perlu serupa.
Karakteristik struktur pile
- Biasanya
data ditumpuk secara kronologis
- Tak
ada keterkaitan antara ukuran file, record, dan blok
- Elemen
data dapat beragam, dapat berbeda untuk tiap record ( berisi attribut lain
).
- Data
harus disimpan secara lengkap beserta nama attributnya, tidak Cuma nilai
atributnya.
‘Komponen file pile hanya berisi
data’
Struktur dan pengaksesan
Rekord berelasi dengan suatu objek atau kejadian di
dunia nyata. Rekord berisi elemen-elemen ( field-field) data dan tiap elemen
data perlu mempunyai identifikasi. Identifikasi pada pile adalah berupa nama
atribut secara ekplisit. Misalnya: Tinggi = 163, Dimana, nilai elemen data
adalah 163 dan nama deskripsi adalah tinggi. Tiap elemen data di pile berbentuk
tuple dua komponen disebut pasanagn nama atribut – nilai atribut ( atribute
name – value atribute ).
Format record
Sejumlah
pasangan untuk mendefinisikan objek dan mengasosiasikan data dengan objek. Contoh :
|nama=Nurman,jurusan=IF,alamat=Sadang
Serang 64, umur=24, tinggi=163.
ketika
informasi akan diambil, pemilihan record dengan menspesifikasikan di argumen
pencarian.
Penggunaan
file pile
File pile merupakan struktur dasar dan tak
berstruktur. Struktur ini memberikan fleksibilitas penuh. Struktur ini
menggunakan ruang penyimpanan dengan baik saat data berukuran dan berstruktur
beragam. Struktur ini sangat jelek untuk pencarian record tertentu. Berbagai
penggunaan dari file pile, diantaranya :
- File-file
sistem
- File
log ( mencatat kegiatan )
- File-file
penelitian / medis
- Config.sys
B. SEQUENTIAL FILE
Sequential
File adalah
file dengan organisasi urut. Data yang disimpan diurutkan berdasarkan urutan
pemasukan data (urut berdasarkan nomor record). Data yang ditambahkan selalu
menempati urutan berikutnya. Sequential
file adalah record yang disimpan dalam media penyimpanan sekunder
komputer, yang dapat diakses secara berurutan mulai dari record pertama sampai
dengan record terakhir. Record per record searah. Record terakhir adalah
rekaman fiktif yang menandai akhir dari arsip. Sequential adalah sekumpulan record yang disimpan dalam
media penyimpanan sekunder computer, yang dapat diakses secara berurutan mulai
dari record pertama sampai record terakhir. Sequential file merupakan suatu
cara ataupun suatu metode penyimpanan dan pembacaan data yang dilakukan secara
berurutan. Dalam hal ini, data yang ada akan disimpan sesuai dengan urutan
masuknya. Data pertama dengan nomor berapapun, akan disimpan ditempat pertama,
demikian pula dengan data berikutnya yang juga akan disimpan ditempat
berikutnya. Dalam melakukan pembacaan data, juga akan dilakukan secara
berurutan, artinya, pembacaan akan dimulai dari data paling awal dan
dilanjutkan dengan data berikutnya sehingga data yang dimaksud bisa
diketemukan.
Keuntungan dari Sequential file
Keuntungan
utama dari organisasi Sequential file adalah:
1.
Mengarsipkan desain adalah sederhana.
2.
Lokasi dari rekaman memerlukan hanyalah kunci rekaman.
3. Ketika
laju ke aktifan adalah tinggi,kesederhanaan dari mengakses cara membuat proses
efisien.
4. Media
file murah seperti pita magnet dapat dipergunakan untuk menyimpan data.
Kelemahan
dari Sequential file
Kelemahan
utama dari organisasi Sequential file adalah:
1. Memperbaharui memerlukan bahwa
semua transaksi rekaman diurutkan pada urutan kunci rekaman.
2. Satu berkas menguasai baru,secara
fisik pisahkan dan eksklusif, selalu diciptakan sebagai hasil pembaharuan
percontohan.
3. Tambahan dan penghapusan dari
rekaman tidak sederhana.
PENGOLAHAN
SEQUENTIAL FILE
File merupakan fasilitas
penyimpanan data pada external storage yang bersifat permanen, jika
dibandingkan dengan penyimpanan ke RAM yang sifatnya sementara. Dengan
pemakaian file kita dapat menghemat pemakaian RAM komputer yang memiliki jumlah
yang terbatas serta dapat melakukan dokumentasi untuk jangka waktu yang
panjang.
Pada QBasic pengolahan file dapat
dibagi atas tiga jenis, yaitu :
1. SEQUENTIAL FILE
2. RANDOM FILE
3. BINARY FILE
2. RANDOM FILE
3. BINARY FILE
Pada Sequential file (file urut) proses
pengolahannya dilakukan secara linier dari awal sampai akhir, tanpa bisa
kembali kebagian sebelumnya, kecuali proses dimulai lagi dari awal. Jadi dalam
pengolahan datanya bersifat first in first out, artinya pembacaan data dari
file ini harus dimulai dari data yang paling awal. Pada umumnya pengolahan data
yang menggunakan file sebagai media INPUT maupun OUTPUT memiliki tiga tahap,
yaitu :
1. Tahap
membuka file (OPEN)
2. Tahap memproses (INPUT/OUTPUT)
3. Dan yang terakhir adalah tahap menutup file (CLOSE)
2. Tahap memproses (INPUT/OUTPUT)
3. Dan yang terakhir adalah tahap menutup file (CLOSE)
Membuka File SEQUENTIAL
Untuk
membuka file sequential yang akan diproses dapat digunakan penulisan sebagai
berikut :
Syntax :
Open filename [FOR mode] AS [#]filenum
Open filename [FOR mode] AS [#]filenum
dimana mode terdiri dari :
INPUT, membuka file untuk proses INPUT
OUTPUT, membuka file baru untuk proses OUTPUT
APPEND, membuka file untuk untuk proses OUTPUT dimana data baru ditambahkan pada bagian akhir.
INPUT, membuka file untuk proses INPUT
OUTPUT, membuka file baru untuk proses OUTPUT
APPEND, membuka file untuk untuk proses OUTPUT dimana data baru ditambahkan pada bagian akhir.
Contoh :
Open “Siswa.Dat” For Append AS #1
Akan membuka Siswa.Dat sebagai OUPUT dimana data
baru ditambahkan pada bagian akhir. Jika file Siswa.Dat belum ada, maka akan
dibuat yang baru.
Proses INPUT/OUTPUT
Perintah proses INPUT/OUTPUT pada sequential file
sangat tergantung kepada bentuk perlakuan terhadap data. Untuk penulisan yang
berorientasi pada baris, anda dapat menggunakan perintah PRINT, dan pembacaanya
dapat menggunakan LINEINPUT. Penulisan yang berorientasi kepada data, anda
dapat menggunakan perintah WRITE dan INPUT untuk proses pembacaannya.
Syntax :
PRINT #filenumber,[USING stringexpressin;]expression list
WRITE #filenumber[,expressionlist]
INPUT #filenumber, variablelist
LINEINPUT #filenumber, variable-string
PRINT #filenumber,[USING stringexpressin;]expression list
WRITE #filenumber[,expressionlist]
INPUT #filenumber, variablelist
LINEINPUT #filenumber, variable-string
Contoh :
Write #1,
“920403024″,”Hendra”,80,90
menulis
ke file nomor 1, dan data dapat dibaca kembali dengan perintah :
Input #1,Nim$,Nama$,Teori,Praktek
Catatan :
Anda
dapat menggunakan fungsi bantu EOF(filenumber) untuk memeriksa apakah berada
diposisi akhir file.
Proses
CLOSE
Untuk
menutup file dapat digunakan perintah CLOSE.
Syntax
CLOSE #filenumber
CLOSE #filenumber
Contoh:
CLOSE #1
CLOSE #1
menutup
file nomor 1.
C. INDEX SEQUENTIAL FILE
Index Sequential File merupakan perpaduan terbaik
dari teknik sequential dan random file. Teknik penyimpanan yang dilakukan,
menggunakan suatu index yang isinya berupa bagian dari data yang sudah
tersortir. Index ini diakhiri denga adanya suatu pointer (penunjuk) yang bisa
menunjukkan secara jelas posisi data yang selengkapnya. Index yang ada juga
merupakan record-key (kunci record), sehingga kalau record key ini dipanggil,
maka seluruh data juga akan ikut terpanggil. Untuk membayangkan penyimpanan dan
pembacaan data secara sequential, kita bisa melihat rekaman lagu yang tersimpan
pada kaset. Untuk mendengarkan lagu kelima, kita harus melalui lagu kesatu,
dua, tiga dan empat terlebih dahulu.Pembacaan seperti inilah yang disebut
sebagai sequential atau berurutan. Apabila lagu-lagu yang ada kemudian disimpan
didalam compack-disk, maka untuk mendengar kan lagu yang kelima bisa langsung
dilakukan (dibaca secara random). Disamping itu, dengan compack-disk juga bias
dilakukan pembacaan secara berurutan atau sequential. Compack disk menyimpan
lagu secara random. Untuk membayangkan penyimpanan data dengan menggunakan
teknik index sequential ini, kita bisa melihat daftar isi pada sebuah buku.
Pada bagian atas disebut sebagai index data yang berisi bagian dari data yang
ada. Index data kemudian diakhiri dengan pointer yang menunjukkan posisi
keseluruhan isi data.
Keuntungan dari Index Sequential
file
Sangat cocok untuk digunakan menyimpan batch data
ataupun individual data. Dibanding sequential file, pemanggilan data menjadi
lebih cepat.
Kelemahan dari Sequential file
Access (pemanggilan) data tidak bisa disamakan
dengan random (direct access file). Memerlukan adanya ruangan extra didalam
memory untuk menyimpan index data. Memerlukan adanya hardware dan software yang
lebih kompleks.
D. MULTIPLE INDEX FILE
- Terdiri
dari main file dan file-file index (file berindex majemuk).
- Tidak
ada rantai overflow.
- Tidak
dikenal konsep atribut kunci (tidak ada keterurutan berdasarkan atribut
kunci).
- Pengubahan
data langsung dilakukan terhadap main file.
- Format
record dapat berupa name-value pair atau dapat berupa structured record.
- Index
bersifat multiple index, dinamis, record anchored.
- Entri
index terdiri dari atribut dan TID.
- Entri
index terurut berdasarkan nilai atributnya.
- Next
record diakses berdasarkan keterurutan entri pada index-nya.
- Tiap
index dapat bersifat multilevel.
- TID
pada index berisi alamat block dan posisi record.
- Exhaustive
vs partial index.
Pada Multiple Index File (file berindex majemuk),
pembaharuan dilakukan terhadap file utama bukan file overflow, karena record
dicari lewat indeks, maka indeks harus dinamis. Begitu terjadi pembaharuan (
insert, update, delete) mka indeks-indeks diperbaharui mengikuti perubahan di
file utama. Contoh : Indeks Dinamis adalah Indeks B-tree.
B-Tree
- BTree
= Balanced Tree
- Perubahan
pada main file berimplikasi terhadap index-nya.
- Struktur
index menggunakan BTree.
- Blok
– blok BTree harus dijaga agar memuat setengah dari fan out ratio-nya
(effective fan out antara y/2 – y).
- Order
Capacity = d
- Kapasitas
minimum = d, dan maximum = 2d
- Khusus
untuk root, kapasitas minimum = 1
Algoritma
Penyisipan Btree
- Cari
posisi yang sesuai bagi record baru, mulai dari root BTree.
- Jika
tersedia space, sisipkan record baru sesuai urutan, jika tidak terjadi,
overflow.
- Jika
terjadi overflow :
1.
Split
menjadi 2 node
2.
Pilih
node tengah untuk naik ke level berikutnya
3.
Set
pointer dari parent node ke child node
Algoritma
Penghapusan Btree
- Menghapus
node pada leaf dan tidak melanggar kapasitas minimum, maka record langsung
dihapus tanpa mengubah struktur BTree.
- Menghapus
node pada root dan tidak melanggar kapasitas minimum, maka ganti dengan 1
record dari leaf node kanan terkecil.
- Menghapus
node (leaf dan root), dan melanggar kapasitas minimum, maka perbaiki
dengan redistribusi record. Apabila redistribusi record mengakibatkan
pelanggaran kapasitas minimum pada node lain, maka lakukan coalescing
node.
- Contoh
BTree dengan order capacity d = 2
E. HASHED FILE
Metode penempatan dan pencarian yang memanfaatkan
metode Hash disebut hashing atau ‘Hash addressing’ dan fungsi yang digunakan
disebut fungsi hashing / fungsi Hash. Fungsi hashing atau fungsi Hash inilah
yang dapat menjadi salah satu alternatif dalam menyimpan atau mengorganisasi
File dengan metode akses langsung. Fungsi Hash berupaya menciptakan
“fingerprint” dari berbagai data masukan. Fungsi Hash akan mengganti atau
mentransposekan data tersebut untuk menciptakan fingerprint, yang biasa disebut
Hashvalue (nilai Hash). Hash value biasanya akan digambarkan sebagai suatu
string pendek yang terdiri atas huruf dan angka yang terlihat random (data
biner yang ditulis dalam notasiheksadesimal). Berkaitan dengan upayanya untuk
menciptakan “fingerprint”, fungsi Hash digunakan juga pada algoritma enkripsi
untuk menjaga integritas sebuah data.
Dalam konsepnya modern ini –selain digunakan pada
penyimpanan data-, fungsi Hash adalah sebuah fungsi matematika, yang menerima
masukan string yangpanjangnya sebarang, mengambil sebuah panjang variable dari
string masukantersebut –yang disebut pre-image, lalu mekonversinkannya ke
sebuah stringkeluaran dengan ukuran tetap (fixed), dan umumnya lebih pendek
dari ukuran string semula, yang disebut message digest.
Pada penggunaan fungsi Hash, saat keadaan tertentu
dapat terjadi tabrakan (coallision) pada home address yang dihasilkan. Yaitu
saat munculnya nilai Hash yang sama dari beberapa data yang berbeda. Untuk
mengantisipasi keadaan ini ada beberapa metode yang dapat digunakan, seperti
perubahan fungsi Hash atau mengurangi perbandingan antara jumlah data yang
tersimpan denganslot address yang tersedia. Hal-hal tersebut dapat
meminimalisir tabrakan, tetapi tidak menghilangkannya. Kita tetap memerlukan
collision resolution –sebuah prosedur untuk menempatkan data yang memiliki
address yang sama.
1. Konsep-Konsep File Hashed
1. Organisasi file dengan metode
akses langsung (direct acsess ), yang menggunakan suatu fungsi untuk memetakan
key menjadi address
2. fungsi yang digunakan disebut
fungsi hash/KAT (key to address transformation)
3. Address yang dihasilkan dari
hasil perhitungan fungsi hash disebut dengan istilah home address
4. Jadi, terdapat dua komponen file
hash :
a. Ruang rekord, yang terdiri
atas m slot address
b. Fungsi hash, yang
mentransformasi key menjadi address
5. Transfomasi key akan mudah jika
key telah berupa nilai integer, untuk key berupa karakter alphanumerik terdapat
proses prakondisi untuk mengubahnya menjadi suatu nilai integer.
2. Macam- Macam Fungsi Hashed
Fungsi Hash diimplementasi untuk mengkonversi
himpunan kunci rekaman (K) menjadi himpunan alamat memori (L). Bisa dinotasikan
dengan H : K -> L
Aspek
yang perlu dipertimbangkan dalam pemilihan fungsi Hash adalah :
• fungsi
Hash harus mudah dan cepat dihitung
• fungsi
Hash sebisa mungkin mendistribusikan
posisi
yang dimaksud secara uniform sepanjang himpunan L sehingga collision yang
mungkin terjadi dapat diminimalkan.
3. Tabrakan
Dengan menggunakan hashing, maka hubungan
korespondensi satu-satu antara record key dengan alamat record akan hilang.
Selalu timbul kemungkinan dimana terdapat dua buah record dengan kunci yang
berbeda namun memiliki home address yang sama, dan terjadi tabrakan (collision).
Tabrakan dapat diminimalisir dengan melakukan penggantian pada fungsi Hash yang
digunakan, atau mengurangi packing factor.
a. Packing Factor
Packing factor, bisa disebut juga dengan packing
density ataupun load factor adalah perbandingan antara jumlah data yang
tersimpan terhadap jumlah slot address yang tersedia. Location Storage of
Number Total Stored cord of Number Factor. Penggantian fungsi Hash dan
pengurangan packing factor hanya meminimasisasi tabrakan, tetap dibutuhkan
collision resolution.
b. Collision Resolution
Pada hashing untuk penempatan data, output dari
fungsi Hash tidak selalu unik, namun hanya berupa kemungkinan suaru alamat yang
dapat ditempati. Jika suatu home address sudah ditempati oleh record lain, maka
harus dicarikan alamat lain. Proses pencarian Packing Re = alamat lain
inilah yang disebut sebagai prosedur collision resolution.
1. Metode
Collision Resolution
a. Open
addressing
Metode
dengan pencarian alamat alternative di alamat-alamat selanjutnya yang masih
kosong.
Cara :
• Linear
probing Pencarian dilakukan dengan jarak pencarian tetap
•
Quardratic probing Pencarian dilakukan dengan jarak pencarian berubah dengan
perubahan tetap.
• Double
hashing
Pencarian
dilakukan menggunakan dua fungsi Hash, yaitu fungsi H1 untuk menentukan home
address dan fungsi H2 untuk menentukan increment jika terjadi tabrakan. Syarat
metode ini adalah ukuran table merupakan bilangan prima sehingga kemungkinan
terjadinya siklus pencarian pada slot yang sama dapat dihindari.
Algoritma
: Tentukan home address dari key dengan fungsi H1.
IF home address kosong THEN
Sisip record pada home address.
ELSE
Hitung increment dengan fungsi H2 misalnya
H2 (key) = x
Temukan slot kosong dengan cara increment sejauh x dari home address.
IF slot kosong ditemukan THEN
Sisip record pada slot kosong.
ELSE
Tabel telah penuh.
b.
Computed chaining
Menggunakan
“pseudolink” untuk menemukan next address jika terjadi collision. Tidak
menyimpan actual address pada pseudolink, tapi address ditemukan dengan
menghitung apa yang tersimpan pada pseudolink. Kinerja pseudolink lebih baik
dibandingkan non-link karena menghilangkan penebakan lokasi (address).
Algoritma
: Temukan home address dari key.
IF home address kosong THEN
Sisip record baru ke home
address.
ELSE
Set 3
prioritas increment untuk mencari new address :
1 :
Tentukan increment (new key).
2 :
Tentukan increment (key pada current address).
3 :
Penjumlahan hasil prioritas 1 dan 2.
WHILE new
address belum kosong dan tabel belum penuh DO
Cek posisi mulai dari home address untuk ke – 3
prioritas untuk mencari new address yang kosong.
IF new address belum kosong THEN
Set ke – 3 nilai prioritas dengan
kelipatannya.
END
WHILE
IF tabel penuh THEN
Proses sisip tidak dilakukan,
keluarkan pesan “Tabel Penuh”.
ELSE
Sisip record baru pada new
address.
Set field
pseudolink pada home address dengan kode urut prioritas yang digunakan.
c.
Coalesced hashing
Algoritma
: Tentukan home address dari key.
IF home
address kosong THEN
Sisip
record pada home address.
ELSE
Temukan
record terakhir dari data yang telah menempati home address, dengan mengikuti
link. Temukan slot kosong mulai dari yang terletak pada address paling bawah.
IF slot
kosong tidak ditemukan THEN
File
telah penuh.
ELSE
Sisip
record pada slot kosong.
Set link
field dari record terakhir yang ber-home address sama ke alamat dari record
yang baru disisip.
d.
Chained progressive overflow
Algoritma
: Tentukan home address dari key.
IF home address kosong THEN
Sisip record pada home address.
ELSE
Temukan slot kosong yang terletak
setelah home address.
IF slot kosong ditemukan
THEN
Sisip record pada slot kosong.
ELSE
Tabel telah penuh.
e. Binary
tree
Metode
yang menggunakan struktur binary tree untuk pencarian address ketika erjadi
tabrakan dengan memberikan dua pilihan langkah :
•Continue
: melanjutkan pencarian address berikutnya yang mungkin ditempati oleh record
yang akan disisipkan.
•Move :
memindahkan record yang menempati address ke address berikutnya yang
memungkinkan untuk ditempati record lama.
Algoritma
: Tentukan home address dari key yang akan di-sisipkan (new key).
IF home address kosong THEN
Sisip record pada home address.
ELSE
WHILE new address tidak kosong
dan tabel belum penuh DO Generate binary tree untuk mendapatkan new address :
4. Fungsi
Hashed Satu Arah
Fungsi
Hashed satu arah adalah fungsi Hash yang bekerja dalam satu arah. Maksud dari
satu arah disini adalah bahwa pesan yang sudah diubah menjadi message digest
tidak dapat dikembalikan lagi menjadi pesan semula (irreversible).
Sifat-sifat fungsi Hash satu-arah adalah sebagai
berikut:
1. Fungsi H dapat diterapkan
pada blok data berukuran berapa saja.
2. H menghasilkan nilai (h)
dengan panjang tetap (fixed-length output).
3. H(x) mudah dihitung untuk
setiap nilai x yang diberikan.
4. Untuk setiap h yang
dihasilkan, tidak mungkin dikembalikan nilai x sedemikian sehingga H(x)
=h. Itulah sebabnya fungsi H dikatakan fungsi Hash satu-arah
(one-way Hash function).
5. Untuk setiap x yang
diberikan, tidak mungkin mencari y ≠ x sedemikian sehingga H(y)
= H(x).
6. Tidak mungkin mencari pasangan x
dan y sedemikian sehingga H(x) = H(y).
Beberapa
fungsi Hash satu-arah yang sudah dibuat, antara lain:
- MD2, MD4, MD5,
- Secure Hash Function (SHA),
- Snefru,
- N-Hash,
- RIPE-MD
F.
MULTIRING FILE
I. Pengertian Multiring File
Multiring File merupakan metode pengorganisasian
file yang berorientasi pada pemrosesan subset dari record secara efisien.
Subset tersebut digambarkan sebagai grup dari beberapa record yang terdiri dari
nilai atribut yang biasa. Contohnya “Semua pekerja yang berbicara bahasa
Perancis”.
Subset dari record dihubungkan bersama secara
eksplisit menggunakan pointer. Rantai penghubung ini menentukan urutan anggota
dari subset. Setiap subset mempunyai record kepala yang merupakan record
awal dari suatu rantai. Sebuah record kepala berisi informasi yang berhubungan
dengan seluruh record anggota di bawahnya. Record-record kepala ini juga dapat
dihubungkan menjadi sebuah rantai.
Tipe rantai tertentu yang digunakan untuk
menggambarkan hal ini dinamakan ring, yang merupakan rantai di mana
pointer anggota terakhir digunakan untuk menunkuk record kepala dari rantai.
Ring-ring dapat disarangkan dalam banyak level kedalaman. Dalam hal ini record
anggota dari ring level ke-i record kepala ring bawahan pada level i-1. Ring level
terbawah, yang berisi data terakhir, selalu dianggap berada pada level 1.
Pencarian dalam Multiring File adalah dengan
menelusuri rantai sampai atribut nilai yang dicari ditemukan. Kemudian rantai
baru dimasuki untuk menemukan atribut recod bawahan. Proses ini diulang terus
sampai record yang diinginkan ditemukan.
II. Interlinked Rings
Untuk pertanyaan (query) yang lebih spesifik, yaitu
pertanyaan anggota rantai bawahan seperti “Daftar semua tukang patri di suatu
perusahaan”, dara sebelumnya kurang efisien karena memerlukan pencarian yang
melelahkan. Untuk keperluan ini digunakan struktur ring sebagai berikut.
Panah Bachman digunakan untuk menunjukkan bahwa
pada kotak yang ditunjuk memiliki banyak record.
Bila kita ekspansikan contoh di atas dengan memisahkan
pekerja dalam berbagai lokasi ke dalam departemen-departemen yang lebih
spesifik, memungkinkan akses dengan urutan senioritas, dan tambahkan warehouse
pada setiap lokasi dan biarkan informasi stock tersedia. Struktur diagramnya
tampak sebagai berikut.
Hubungan di antara ring-ring tidak harus hirarkis.
Hubungan dapat diimplementasi dengan merelasikan anggota dalam ring-ring yang
sama, yang menyediakan banyak lintasan di antara record-record, atau
menghubungkan ring-ring pada level yang lebih rendah kembali ke ring-ring
dengan level lebih tinggi.
Efektivitas dari sebuah proses dalam melokasikan
sebuah record sangat bergantung pada kecocokan pasangan atribut yang membentuk
argument pertanyaan dengan struktur dari file. Bila file tidak diorganisasikan
secara benar, maka proses tidak dapat berjalan secara efisien, dan dibutuhkan
intervensi dari pengguna.
III. Struktur dari Multiring File
Semua record mempunyai struktur yang sama dalam
Multiring File, tetapi isi dan ukuran merupakan fungsi dari ring-ring di mana
mereka berada. Sebuah Multiring File dapat mempunyai sejumlah kategori record
yang berbeda. Di sini definisi file telah menyimpang dari definisi awal. Di
sini record-record tidak sama formatnya, dan keanggotaan ring serta keanggotaan
file harus diketahui sebelum pemrosesan.
Format record yang sebenarnya bergantung pada
kombinasi dari tipe-tipe ring di mana record tersebut menjadi anggota. Pasangan
nilai atrinbut mengidentifikasi dirinya seperti pada pile. Tetapi biasanya
tidak seperti itu, dan tiap record akan mempunyai pengidentifikasi tipe record.
Pada contoh berikut, field t mengidentifikasi
record ini sebagai record pekerja. Tiap record dengan tipe t akan mempunyai
field data yang sama dan 7 field pointer. Pengidentifikasi ini akan
memungkinkan referensi ke sebuah deskripsi format recod yang tepat, disimpan
dengan deskripsi umum dari file.
Untuk menghubungkan record-record ke dalam
ring-ring mereka, pointer-pointer akan muncul dalam sebuah record yang umum.
Sebuah record dapat dimiliki oleh ring-ring sebanyak jumlah pointer yang
dimilikinya.
Dapat juga terdapat field-field data NULL, tetapi
karena terdapat bayak tipe record dengan tujuan spesifik, file secara
keseluruhan relative padat.
Setiap ring pasti memiliki kepala. Kepala ini dapat
berupa poin masukan, anggota dari ring lain, atau keduanya. Ketika sebuah ring
dimasuki dalam sebuah pencarian, poin masukan dicatat sehingga ring ini tidak
dimasuki 2 kali.
IV. Manipulasi Ring
Umumnya organisasi Multiring File menghindari
penggandaan data dengan menempatkan data biasa kepada semua anggota ring ke
dalam record kepala dari ring. Efek negatifnya adalah dalam desain dasar ring,
ketika sebuah record diambil berdasarkan kombinasi kata kunci pencarian,
hasilnya yang dapat diaplikasikan dengan record tidak selalu dapat dilakukan
dengan hanya atribut yang disimpan dalam anggota atau record kepala yang
diakses selama pencarian sepanjang 1 lintasan. 2 alternatif yang
digunakan, yaitu:
- Pencarian
Paralel
melalui semua ring yang diidentifikasi dalam kata kunci pencarian dapat
dilakukan, dengan menghilangkan pada record-record pada persimpangan
ring-ring tersebut.
- Pencarian
Inisial
dapat dilakukan berdasarkan atribut dengan efektivitas mempartisi terbaik.
Record-record yang dikumpulkan kemudian dicek untuk ketepatan dengan
menempatkan record kepala untuk tipe atribut lain yang diperlukan dan
menolak record dengan nilai data yang tidak tepat.
Proses
yang kedua di atas diaplikasikan dengan langkah-langkah sebagai berikut.
Query:
Find an Employee with Location
=”Thule” and Profession=”Welder”.
Enter Location chain;
For each member record determine
if key = Thule;
When found followEmplo yee chain;
For every Employee record the
profession must be determined
Follow the profession chain;
When its header record is
reached,
then inspect profession header
for key = Welder
If the field matches the search
key
then Employee member record
becomes output;
Continue with the next Employee
record;
When its header record, the
Location = Thule is reached,
then the result is complete.
V. Keputusan Desain Ring File
Lama penelusuran rantai berbanding lurus dengan
ukuran rantai. Ukuran rantai-rantai individu dapat dikurangi dengan menambah
jumlah rantai-rantai dan jumlah level dalam struktur file.
Hal ini digambarkan dengan rumus sebagai berikut.
y = x√n dengan x = level
y = panjang rantai
n = record count
Waktu
pencarian untuk record dengan level terendah berkurang secara proporsional
sampai akar ke-x dari record count, n, dan bertambah secara proporsional sampai
level x. Sebuah atribut yang tidak mempartisi file ke dalam banyak level tidak
sangat berguna seperti elemen ring.
Peng-Cluster-an Ring
Record yang sering diakses bersama paling baik
disimpan dengan derajat lokalitas yang tinggi. Satu ring umumnya dapat
diletakkan seluruhnya dalam 1 silinder, seingga semua pencarian dihindari saat
penelusuran cluster ring ini. Ketika referensi berulang-ulang kepada record
kepala ring dibutuhkan, kepala record itu dapat berpartisipasi dalam cluster.
Ring berikutnya dengan level lebih tinggi akan sulit untuk berpartisipasi,
kecuali jika ruangan total yang dibutuhkan semua anggota record dan
pendahulunya cukup kecil untuk disimpan dalam satu atau beberapa silinder.
Dalam perubahan database yang dinamis, peng-cluster-an yang optimal sulit untu
dijaga dan keuntungannya sedikit. Sebuah reorganisasi diperlukan untuk
mengembalikan cluster-cluster.
Pengkategorian Atribut Real
Atribut yang merepresentasikan data real atau
kontinyu tidak menyediakan partisi yang efektif kecuali jika dikategorikan
secara artificial.
VI. Penggunaan Multiring File
Struktur Multiring merupakan dasar untuk beberapa
database terbesar yang digunakan saat ini. Sistem informasi manajemen di mana
banyak melibatkan tabulasi, penjumlahan, dan laporan pengecualian telah
diimplementasikan menggunakan daftar Multiring ini.
Beberapa masalah dalam representasi ruang geografis
dan arsitektur juga telah diselesaikan dengan pendekatan Multiring.
Perkembangan saat ini dalam system multifile terintegrasi bergantung pada
kapabilitas yang disediakan oleh struktur ring. Masalahnya adalah desain yang
cermat berdasarkan pengetahuan tentang data dan pola penggunaan diperlukan
sebelum Multiring File dapat diimplementasikan.
VII. Kinerja Multiring
Kinerja system Multiring sangat bergantung pada
kecocokan dari penandaan atribut ke ring-ring tertentu.
Ukuran record dalam Multiring File
Karena banyak tipe record yang berbeda dalam
Multiring File, estimasi akurat didapatkan hanya dengan mendaftar semua tipe,
dengan frekuensi dan ukuran masing-masing.
Pengambilan record dalam Multiring File
Waktu untuk mengambil sebuah record adalah fungsi
dari jumlah dan panjang rantai yang dicari. Panjang daripada ring bergantung
pada ukuran file, jumlah level, dan seberapa baik file dipartisi ke dalam
ring-ring.
Pengambilan record berikutnya dari Multiring File
Record berikutnya untuk urutan yang berhubungan
dapat ditemukan dengan menelusuri rantai tersebut.
Pemasukan ke dalam Multiring File
Penambahan record ke dalam Multiring File dilakukan
dengan menentukan spasi kosong yang cocok untuk record, menempatkan semua pendahulu
untuk record baru, mengambil nilai dari link yang tepat dari pendahulu,
menetapkannya ke dalam record baru, dan menempatkan nilai dari posisi record
baru ke dalam area-area link pendahulu.
Meng-Update record dalam Multiring File
Jika hanya field data yang akan dirubah, update
hanya memerlukan penemuan record dan penulisan ulang.
Membaca seluruh Multiring File
Pembacaan menurut rantai memerlukan bahwa sebuah
record kepala diakses untuk setiap ring tambahan. Baik record kepala baru
maupun lama diperlukan untuk bergerak di antara 2 ring.
Reorganisasi Mutiring File
Reorganisasi sebenarnya tidak diperukan sebagau
bagian dari prosedur operasi normal. Hanya saat pemformatan ulang tipe record
diperlukan, record-record seperti itu harus ditulis ulang, Ini hanya memerlukan
reorganisasi parsial dari file, karena perubahan terbatas pada ring-ring pada
level-level yang menggunakan tipe-tipe record itu.