Cost Estimates for Selection Operation

1. Algorithm A1 (Linear Search) – membaca setiap blok-blok file dan membaca setiap record untuk menentukan dimana hasil selection yang diminta sesuai kondisi.

Cara menghitung cost estimatenya yaitu,

Cost estimate = br block transfers + 1 seek; dimana br adalah jumlah blok yang terisi oleh record-record relasi r.

Tapi jika selection menurut kata kunci / primary key-nya, rumus cost menjadi,

Cost = (br/2) block transfers + 1 seek

Linear search ini bisa digunakan untuk kondisi seleksi, pengurutan record-record dalam suatu file dan indeks.

2. A2 (Primary Index, equality on key) – hanya mengambil/membaca 1 record yang memenuhi dengan kondisi yang diinginkan. Rumus perhitungan costnya yaitu,

Cost = (h_i + 1) * (t_T + t_S)

3. A3 (Primary Index, equality on nonkey) – mengambil/membaca multiple record yang sesuai dengan kondisi. Rumus perhitungan costnya menjadi,

Cost = h_i * (t_T + t_S) + t_S + t_T * b; dimana b adalah jumlah blok dengan data yang sesuai kondisi

4. A4 (Secondary Index, equality on nonkey) – mengambil/membaca 1 record yang sesuai kondisi, dimana search-keynya merupakan kunci kandidat. Perhitungan costnya menggunakan rumus:

Cost = (h_i + 1) * (t_T + t_S)

Kondisi kedua adalah jika searck-keynya bukan merupakan kunci kandidat, perhitungan costnya, yaitu

each of n matching records may be on a different block

Cost =  (h_i + n) * (t_T + t_S)  ; dimana data n yang sesuai dengan kondisi bisa berada dalam blok yang berbeda

5. A5 (Primary Index, comparison)

s_{A ³ V}(r)  digunakan untuk menemukan tuple pertama ³ v  dan memindai secara berurutan.

s_A£V (r) digunakan untuk memindai tuple pertama > v dan tidak menggunakan indeks.

6. A6 (Secondary Index, comparison).

Untuk s_{A ³ V}(r)  menggunakan indeks untuk mencari entri pertama ³ v dan memindai secara berurutan mencari pointer

Untuk s_A£V (r) hanya memindai pointer indeks hingga entri pertama > v

7. A7 (Conjunctive Selection using One Index).

Pemilihan kombinasi q_i dan algoritma A1 melalui A7 menghasilkan biaya untuk s_qi (r).

8. A8 (Conjunctive Selection using Composite Index).

Menggunakan multiple-key indeks yang tersedia.

9. A9 (Conjunctive Selection by Intersection of Identifiers).

Menggunakan indeks yang sesuai untuk setiap kondisi dan mengambil irisan semua set yang didapat dari pointer.

10. A10 (Disjunctive Selection by Union of Identifiers).

Berlaku jika semua kondisi memiliki indeks yang tersedia, untuk mencari setiap kondisi dan mengambil gabungan dari semua set yang diperoleh dari pointer.