Aljabar Relasional untuk Optimasi Kueri

Ketika kueri ditempatkan, kueri itu pertama kali dipindai, diurai, dan divalidasi. Representasi internal dari kueri kemudian dibuat seperti pohon kueri atau grafik kueri. Kemudian strategi eksekusi alternatif dirancang untuk mengambil hasil dari tabel database. Proses memilih strategi eksekusi yang paling tepat untuk pemrosesan kueri disebut optimasi kueri.

Masalah Optimasi Kueri di DDBMS

Di DDBMS, pengoptimalan kueri adalah tugas penting. Kompleksitasnya tinggi karena jumlah strategi alternatif dapat meningkat secara eksponensial karena faktor-faktor berikut -

• Kehadiran sejumlah fragmen.
• Distribusi fragmen atau tabel di berbagai situs.
• Kecepatan tautan komunikasi.
• Perbedaan dalam kemampuan pemrosesan lokal.

Oleh karena itu, dalam sistem terdistribusi, target sering kali menemukan strategi eksekusi yang baik untuk pemrosesan kueri daripada yang terbaik. Waktu untuk mengeksekusi kueri adalah jumlah dari berikut ini -

• Waktu untuk mengkomunikasikan pertanyaan ke database.
• Waktu untuk mengeksekusi fragmen kueri lokal.
• Saatnya mengumpulkan data dari situs yang berbeda.
• Saatnya menampilkan hasil ke aplikasi.

Pemrosesan Kueri

Pemrosesan kueri adalah sekumpulan semua aktivitas mulai dari penempatan kueri hingga menampilkan hasil kueri. Langkah-langkahnya seperti yang ditunjukkan pada diagram berikut -

Aljabar Relasional

Aljabar relasional mendefinisikan himpunan operasi dasar model database relasional. Urutan operasi aljabar relasional membentuk ekspresi aljabar relasional. Hasil ekspresi ini mewakili hasil query database.

Operasi dasarnya adalah -

• Projection
• Selection
• Union
• Intersection
• Minus
• Join

Proyeksi

Operasi proyeksi menampilkan subset bidang tabel. Ini memberikan partisi vertikal pada tabel.

Syntax in Relational Algebra

$$ \ pi _ {<{AttributeList}>} {(<{Table Name}>)} $$

Sebagai contoh, mari kita pertimbangkan database siswa berikut -

STUDENT
Roll_No	Name	Course	Semester	Gender
2	Amit Prasad	BCA	1	Pria
4	Varsha Tiwari	BCA	1	Perempuan
5	Asif Ali	MCA	2	Pria
6	Joe Wallace	MCA	1	Pria
8	Shivani Iyengar	BCA	1	Perempuan

Jika kami ingin menampilkan nama dan mata kuliah semua siswa, kami akan menggunakan ekspresi aljabar relasional berikut -

$$ \ pi_ {Nama, Kursus} {(SISWA)} $$

Pilihan

Operasi pemilihan menampilkan subset tupel tabel yang memenuhi kondisi tertentu. Ini memberikan partisi horizontal pada tabel.

Syntax in Relational Algebra

$$ \ sigma _ {<{Kondisi}>} {(<{Nama Tabel}>)} $$

Misalnya, dalam tabel Siswa, jika kami ingin menampilkan detail semua siswa yang telah memilih kursus MCA, kami akan menggunakan ekspresi aljabar relasional berikut -

$$ \ sigma_ {Kursus} = {\ small "BCA"} ^ {(SISWA)} $$

Kombinasi Operasi Proyeksi dan Seleksi

Untuk sebagian besar kueri, kami memerlukan kombinasi operasi proyeksi dan pemilihan. Ada dua cara untuk menulis ekspresi ini -

• Menggunakan urutan operasi proyeksi dan pemilihan.
• Menggunakan operasi ganti nama untuk menghasilkan hasil antara.

Misalnya untuk menampilkan nama semua siswi mata kuliah BCA -

• Ekspresi aljabar relasional menggunakan urutan operasi proyeksi dan seleksi

$$ \ pi_ {Nama} (\ sigma_ {Gender = \ small "Female" AND \: Course = \ small "BCA"} {(STUDENT)}) $$

• Ekspresi aljabar relasional menggunakan operasi ganti nama untuk menghasilkan hasil antara

$$ FemaleBCAStudent \ leftarrow \ sigma_ {Jenis kelamin = \ small "Female" AND \: Course = \ small "BCA"} {(STUDENT)} $$

$$ Hasil \ leftarrow \ pi_ {Nama} {(FemaleBCAStudent)} $$

Persatuan

Jika P adalah hasil dari operasi dan Q adalah hasil dari operasi lain, penyatuan P dan Q ($ p \ cup Q $) adalah himpunan semua tupel yang ada di P atau di Q atau di keduanya tanpa duplikat .

Misalnya untuk menampilkan semua mahasiswa baik yang sedang semester 1 maupun yang sedang kuliah di BCA -

$$ Sem1Siswa \ leftarrow \ sigma_ {Semester = 1} {(SISWA)} $$

$$ BCAStudent \ leftarrow \ sigma_ {Course = \ small "BCA"} {(STUDENT)} $$

$$ Hasil \ leftarrow Sem1Siswa \ cup BCAStudent $$

Persimpangan

Jika P adalah hasil dari operasi dan Q adalah hasil dari operasi lain, perpotongan P dan Q ($ p \ cap Q $) adalah himpunan semua tupel yang ada di P dan Q keduanya.

Misalnya, diberikan dua skema berikut -

EMPLOYEE

EmpID

Nama

Kota

Departemen

Gaji

PROJECT

PId

Kota

Departemen

Status

Untuk menampilkan nama semua kota tempat proyek berada dan juga karyawan tinggal -

$$ CityEmp \ leftarrow \ pi_ {City} {(EMPLOYEE)} $$

$$ CityProject \ leftarrow \ pi_ {City} {(PROJECT)} $$

$$ Hasil \ leftarrow CityEmp \ cap CityProject $$

Minus

Jika P adalah hasil dari operasi dan Q adalah hasil dari operasi lain, P - Q adalah himpunan semua tupel yang ada di P dan bukan di Q.

Misalnya, untuk membuat daftar semua departemen yang tidak memiliki proyek yang sedang berjalan (proyek dengan status = sedang berlangsung) -

$$ AllDept \ leftarrow \ pi_ {Departemen} {(EMPLOYEE)} $$

$$ ProjectDept \ leftarrow \ pi_ {Departemen} (\ sigma_ {Status = \ small "berkelanjutan"} {(PROJECT)}) $$

$$ Hasil \ leftarrow AllDept - ProjectDept $$

Ikuti

Operasi gabungan menggabungkan tupel terkait dari dua tabel berbeda (hasil kueri) ke dalam satu tabel.

Misalnya, pertimbangkan dua skema, Pelanggan dan Cabang dalam database Bank sebagai berikut -

CUSTOMER

CustID

AccNo

TypeOfAc

BranchID

DateOfOpening

BRANCH

BranchID

Nama cabang

IFSCcode

Alamat

Untuk membuat daftar detail karyawan bersama dengan detail cabang -

$$ Hasil \ leftarrow CUSTOMER \ bowtie_ {Customer.BranchID = Branch.BranchID} {BRANCH} $$

Menerjemahkan Kueri SQL ke dalam Aljabar Relasional

Kueri SQL diterjemahkan ke dalam ekspresi aljabar relasional yang setara sebelum pengoptimalan. Kueri pada awalnya diuraikan menjadi blok kueri yang lebih kecil. Blok-blok ini diterjemahkan ke ekspresi aljabar relasional yang setara. Pengoptimalan mencakup pengoptimalan setiap blok dan kemudian pengoptimalan kueri secara keseluruhan.

Contoh

Mari kita pertimbangkan skema berikut -

KARYAWAN

EmpID

Nama

Kota

Departemen

Gaji

PROYEK

PId

Kota

Departemen

Status

KARYA

EmpID

PID

Jam

Contoh 1

Untuk menampilkan detail semua karyawan yang mendapatkan gaji KURANG dari gaji rata-rata, kami menulis kueri SQL -

SELECT * FROM EMPLOYEE 
WHERE SALARY < ( SELECT AVERAGE(SALARY) FROM EMPLOYEE ) ;

Kueri ini berisi satu sub-kueri bertingkat. Jadi, ini bisa dipecah menjadi dua blok.

Blok bagian dalam adalah -

SELECT AVERAGE(SALARY)FROM EMPLOYEE ;

Jika hasil dari query ini adalah AvgSal, maka blok luar adalah -

SELECT * FROM EMPLOYEE WHERE SALARY < AvgSal;

Ekspresi aljabar relasional untuk blok dalam -

$$ AvgSal \ leftarrow \ Im_ {AVERAGE (Gaji)} {EMPLOYEE} $$

Ekspresi aljabar relasional untuk blok luar -

$$ \ sigma_ {Gaji <{AvgSal}>} {EMPLOYEE} $$

Contoh 2

Untuk menampilkan ID proyek dan status semua proyek karyawan 'Arun Kumar', kami menulis kueri SQL -

SELECT PID, STATUS FROM PROJECT 
WHERE PID = ( SELECT FROM WORKS  WHERE EMPID = ( SELECT EMPID FROM EMPLOYEE 
            WHERE NAME = 'ARUN KUMAR'));

Kueri ini berisi dua sub-kueri bertingkat. Dengan demikian, dapat dipecah menjadi tiga blok, sebagai berikut -

SELECT EMPID FROM EMPLOYEE WHERE NAME = 'ARUN KUMAR'; 
SELECT PID FROM WORKS WHERE EMPID = ArunEmpID; 
SELECT PID, STATUS FROM PROJECT WHERE PID = ArunPID;

(Di sini ArunEmpID dan ArunPID adalah hasil dari kueri dalam)

Ekspresi aljabar relasional untuk ketiga blok tersebut adalah -

$$ ArunEmpID \ leftarrow \ pi_ {EmpID} (\ sigma_ {Name = \ small "Arun Kumar"} {(EMPLOYEE)}) $$

$$ ArunPID \ leftarrow \ pi_ {PID} (\ sigma_ {EmpID = \ small "ArunEmpID"} {(WORKS)}) $$

$$ Hasil \ leftarrow \ pi_ {PID, Status} (\ sigma_ {PID = \ small "ArunPID"} {(PROJECT)}) $$

Perhitungan Operator Aljabar Relasional

Perhitungan operator aljabar relasional dapat dilakukan dengan berbagai cara, dan setiap alternatif disebut an access path.

Alternatif komputasi bergantung pada tiga faktor utama -

• Jenis operator
• Memori yang tersedia
• Struktur disk

Waktu untuk melaksanakan operasi aljabar relasional adalah jumlah dari -

• Saatnya memproses tupel.
• Saatnya mengambil tupel tabel dari disk ke memori.

Karena waktu untuk memproses tupel jauh lebih kecil daripada waktu untuk mengambil tupel dari penyimpanan, terutama dalam sistem terdistribusi, akses disk sering kali dianggap sebagai metrik untuk menghitung biaya ekspresi relasional.

Perhitungan Seleksi

Perhitungan operasi pemilihan bergantung pada kompleksitas kondisi pemilihan dan ketersediaan indeks pada atribut tabel.

Berikut ini adalah alternatif komputasi tergantung pada indeks -

• No Index- Jika tabel tidak diurutkan dan tidak memiliki indeks, maka proses pemilihan melibatkan pemindaian semua blok disk tabel. Setiap blok dibawa ke dalam memori dan setiap tupel di blok tersebut diperiksa untuk melihat apakah memenuhi kondisi pemilihan. Jika kondisi terpenuhi, maka akan ditampilkan sebagai keluaran. Ini adalah pendekatan yang paling mahal karena setiap tupel dibawa ke dalam memori dan setiap tupel diproses.

• B+ Tree Index- Kebanyakan sistem database dibangun di atas indeks B + Tree. Jika kondisi pemilihan didasarkan pada bidang, yang merupakan kunci dari indeks Pohon B + ini, maka indeks ini digunakan untuk mengambil hasil. Namun, memproses pernyataan pemilihan dengan kondisi kompleks mungkin melibatkan lebih banyak akses blok disk dan dalam beberapa kasus pemindaian lengkap atas tabel.

• Hash Index- Jika indeks hash digunakan dan bidang kuncinya digunakan dalam kondisi pemilihan, maka mengambil tupel menggunakan indeks hash menjadi proses yang sederhana. Indeks hash menggunakan fungsi hash untuk menemukan alamat bucket tempat penyimpanan nilai kunci yang sesuai dengan nilai hash. Untuk menemukan nilai kunci dalam indeks, fungsi hash dijalankan dan alamat keranjang ditemukan. Nilai kunci di keranjang dicari. Jika kecocokan ditemukan, tupel sebenarnya diambil dari blok disk ke dalam memori.

Perhitungan Gabungan

Ketika kita ingin menggabungkan dua tabel, katakanlah P dan Q, setiap tupel di P harus dibandingkan dengan setiap tupel di Q untuk menguji apakah kondisi penggabungan terpenuhi. Jika kondisinya terpenuhi, tupel terkait digabungkan, menghilangkan bidang duplikat dan ditambahkan ke relasi hasil. Akibatnya, ini adalah operasi yang paling mahal.

Pendekatan umum untuk menghitung gabungan adalah -

Pendekatan Nested-loop

Ini adalah pendekatan gabungan konvensional. Ini dapat diilustrasikan melalui pseudocode berikut (Tabel P dan Q, dengan tuple tuple_p dan tuple_q dan bergabung dengan atribut a) -

For each tuple_p in P 
For each tuple_q in Q
If tuple_p.a = tuple_q.a Then 
   Concatenate tuple_p and tuple_q and append to Result 
End If 
Next tuple_q 
Next tuple-p

Pendekatan Sort-merge

Dalam pendekatan ini, dua tabel diurutkan secara individual berdasarkan atribut penggabung dan kemudian tabel yang diurutkan digabungkan. Teknik penyortiran eksternal diadopsi karena jumlah record sangat tinggi dan tidak dapat diakomodasi dalam memori. Setelah masing-masing tabel diurutkan, satu halaman setiap tabel yang diurutkan dibawa ke memori, digabungkan berdasarkan atribut join dan tuple yang digabungkan ditulis.

Pendekatan Hash-join

Pendekatan ini terdiri dari dua fase: fase partisi dan fase probing. Dalam fase pemartisian, tabel P dan Q dipecah menjadi dua set partisi yang saling terpisah. Fungsi hash umum diputuskan. Fungsi hash ini digunakan untuk menetapkan tupel ke partisi. Dalam fase probing, tupel dalam partisi P dibandingkan dengan tupel dari partisi terkait Q. Jika cocok, maka tupel tersebut akan ditulis.