Sorgu Optimizasyonu için İlişkisel Cebir
Bir sorgu yerleştirildiğinde, önce taranır, çözümlenir ve doğrulanır. Daha sonra sorgu ağacı veya sorgu grafiği gibi sorgunun dahili bir temsili oluşturulur. Daha sonra veritabanı tablolarından sonuçların alınması için alternatif yürütme stratejileri tasarlanır. Sorgu işleme için en uygun yürütme stratejisini seçme sürecine sorgu optimizasyonu denir.
DDBMS'de Sorgu Optimizasyonu Sorunları
DDBMS'de sorgu optimizasyonu çok önemli bir görevdir. Aşağıdaki faktörlerden dolayı alternatif stratejilerin sayısı katlanarak artabileceğinden karmaşıklık yüksektir -
- Bir dizi parçanın varlığı.
- Parçaların veya tabloların çeşitli sitelere dağılımı.
- İletişim bağlantılarının hızı.
- Yerel işleme yeteneklerinde eşitsizlik.
Bu nedenle, dağıtılmış bir sistemde hedef genellikle en iyisinden ziyade sorgu işleme için iyi bir yürütme stratejisi bulmaktır. Bir sorguyu yürütme süresi aşağıdakilerin toplamıdır -
- Veritabanlarına sorgu iletme zamanı.
- Yerel sorgu parçalarını yürütme zamanı.
- Farklı sitelerden veri toplama zamanı.
- Sonuçları uygulamaya görüntüleme zamanı.
Sorgu İşleme
Sorgu işleme, sorgu yerleştirmeden başlayarak sorgunun sonuçlarını görüntülemeye kadar tüm etkinlikler kümesidir. Adımlar, aşağıdaki şemada gösterildiği gibidir -
İlişkisel Cebir
İlişkisel cebir, ilişkisel veritabanı modelinin temel işlemlerini tanımlar. Bir dizi ilişkisel cebir işlemleri, ilişkisel bir cebir ifadesi oluşturur. Bu ifadenin sonucu, bir veritabanı sorgusunun sonucunu temsil eder.
Temel işlemler -
- Projection
- Selection
- Union
- Intersection
- Minus
- Join
Projeksiyon
Projeksiyon işlemi, bir tablonun alanlarının bir alt kümesini görüntüler. Bu, tablonun dikey bir bölümünü verir.
Syntax in Relational Algebra
$$ \ pi _ {<{AttributeList}>} {(<{Tablo Adı}>)} $$
Örneğin, aşağıdaki Öğrenci veritabanını ele alalım -
|
||||
Roll_No | Name | Course | Semester | Gender |
2 | Amit Prasad | BCA | 1 | Erkek |
4 | Varsha Tiwari | BCA | 1 | Kadın |
5 | Asıf Ali | MCA | 2 | Erkek |
6 | Joe Wallace | MCA | 1 | Erkek |
8 | Shivani Iyengar | BCA | 1 | Kadın |
Tüm öğrencilerin isimlerini ve derslerini göstermek istiyorsak, aşağıdaki ilişkisel cebir ifadesini kullanacağız -
$$ \ pi_ {İsim, Kurs} {(ÖĞRENCİ)} $$
Seçimi
Seçim işlemi, belirli koşulları sağlayan bir tablonun tuple alt kümesini görüntüler. Bu, tablonun yatay bir bölümünü verir.
Syntax in Relational Algebra
$$ \ sigma _ {<{Koşullar}>} {(<{Tablo Adı}>)} $$
Örneğin, Öğrenci tablosunda, MCA kursunu seçen tüm öğrencilerin ayrıntılarını görüntülemek istiyorsak, aşağıdaki ilişkisel cebir ifadesini kullanacağız -
$$ \ sigma_ {Kurs} = {\ küçük "BCA"} ^ {(ÖĞRENCİ)} $$
Projeksiyon ve Seçim İşlemlerinin Kombinasyonu
Çoğu sorgu için, projeksiyon ve seçim işlemlerinin bir kombinasyonuna ihtiyacımız var. Bu ifadeleri yazmanın iki yolu vardır -
- Projeksiyon dizisini ve seçim işlemlerini kullanma.
- Ara sonuçlar oluşturmak için yeniden adlandırma işlemini kullanma.
Örneğin, BCA kursundaki tüm kız öğrencilerin adlarını görüntülemek için -
- Projeksiyon dizisi ve seçim işlemleri kullanarak ilişkisel cebir ifadesi
$$ \ pi_ {İsim} (\ sigma_ {Cinsiyet = \ küçük "Kadın" VE \: Kurs = \ küçük "BCA"} {(ÖĞRENCİ)}) $$
- Ara sonuçlar oluşturmak için yeniden adlandırma işlemini kullanan ilişkisel cebir ifadesi
$$ FemaleBCAStudent \ leftarrow \ sigma_ {Cinsiyet = \ küçük "Kadın" VE \: Kurs = \ küçük "BCA"} {(ÖĞRENCİ)} $$
$$ Result \ leftarrow \ pi_ {İsim} {(FemaleBCAStudent)} $$
Birlik
P bir işlemin sonucuysa ve Q başka bir işlemin sonucuysa, P ve Q'nun birleşimi ($ p \ cup Q $), P veya Q veya her ikisinde de yinelenmeyen tüm tuplelar kümesidir .
Örneğin, 1. Dönemde veya BCA kursunda olan tüm öğrencileri görüntülemek için -
$$ Sem1Öğrenci \ leftarrow \ sigma_ {Sömestr = 1} {(ÖĞRENCİ)} $$
$$ BCAStudent \ leftarrow \ sigma_ {Kurs = \ küçük "BCA"} {(ÖĞRENCİ)} $$
$$ Result \ leftarrow Sem1Öğrenci \ cup BCAStudent $$
Kavşak
P bir işlemin sonucuysa ve Q başka bir işlemin sonucuysa, P ve Q'nun kesişimi ($ p \ cap Q $) her ikisi de P ve Q'da olan tüm tuplelar kümesidir.
Örneğin, aşağıdaki iki şema verildiğinde -
EMPLOYEE
EmpID | İsim | Kent | Bölüm | Maaş |
PROJECT
PId | Kent | Bölüm | Durum |
Bir projenin bulunduğu ve aynı zamanda bir çalışanın ikamet ettiği tüm şehirlerin adlarını görüntülemek için -
$$ CityEmp \ leftarrow \ pi_ {Şehir} {(EMPLOYEE)} $$
$$ CityProject \ leftarrow \ pi_ {Şehir} {(PROJE)} $$
$$ Result \ leftarrow CityEmp \ cap CityProject $$
Eksi
P bir işlemin sonucuysa ve Q başka bir işlemin sonucuysa, P - Q, Q'da değil P'de olan tüm tuplelar kümesidir.
Örneğin devam eden bir projesi olmayan tüm departmanları listelemek için (durumu = devam eden projeler) -
$$ AllDept \ leftarrow \ pi_ {Department} {(EMPLOYEE)} $$
$$ ProjectDept \ leftarrow \ pi_ {Departman} (\ sigma_ {Durum = \ küçük "devam eden"} {(PROJE)}) $$
$$ Result \ leftarrow AllDept - ProjectDept $$
Katılmak
Birleştirme işlemi, iki farklı tablonun ilgili tupl'larını (sorguların sonuçları) tek bir tabloda birleştirir.
Örneğin, aşağıdaki gibi bir Banka veritabanındaki Müşteri ve Şube olmak üzere iki şema düşünün -
CUSTOMER
Müşteri Kimliği | AccNo | TypeOfAc | BranchID | DateOfOpening |
BRANCH
BranchID | BranchName | IFSC kodu | Adres |
Çalışan ayrıntılarını şube ayrıntılarıyla birlikte listelemek için -
$$ Result \ leftarrow CUSTOMER \ bowtie_ {Customer.BranchID = Branch.BranchID} {BRANCH} $$
SQL Sorgularını İlişkisel Cebire Çevirme
SQL sorguları, optimizasyondan önce eşdeğer ilişkisel cebir ifadelerine çevrilir. Bir sorgu ilk olarak daha küçük sorgu bloklarına ayrıştırılır. Bu bloklar eşdeğer ilişkisel cebir ifadelerine çevrilir. Optimizasyon, her bloğun optimizasyonunu ve ardından sorgunun bir bütün olarak optimizasyonunu içerir.
Örnekler
Aşağıdaki şemaları ele alalım -
ÇALIŞAN
EmpID | İsim | Kent | Bölüm | Maaş |
PROJE
PId | Kent | Bölüm | Durum |
İŞLER
EmpID | PID | Saatler |
örnek 1
Ortalama maaştan DAHA AZ maaş kazanan tüm çalışanların ayrıntılarını görüntülemek için SQL sorgusunu yazıyoruz -
SELECT * FROM EMPLOYEE
WHERE SALARY < ( SELECT AVERAGE(SALARY) FROM EMPLOYEE ) ;
Bu sorgu, iç içe geçmiş bir alt sorgu içerir. Yani, bu iki bloğa bölünebilir.
İç blok -
SELECT AVERAGE(SALARY)FROM EMPLOYEE ;
Bu sorgunun sonucu AvgSal ise, dış blok -
SELECT * FROM EMPLOYEE WHERE SALARY < AvgSal;
İç blok için ilişkisel cebir ifadesi -
$$ AvgSal \ leftarrow \ Im_ {AVERAGE (Maaş)} {EMPLOYEE} $$
Dış blok için ilişkisel cebir ifadesi -
$$ \ sigma_ {Salary <{AvgSal}>} {EMPLOYEE} $$
Örnek 2
Çalışan 'Arun Kumar' ın tüm projelerinin proje kimliğini ve durumunu görüntülemek için SQL sorgusunu yazıyoruz -
SELECT PID, STATUS FROM PROJECT
WHERE PID = ( SELECT FROM WORKS WHERE EMPID = ( SELECT EMPID FROM EMPLOYEE
WHERE NAME = 'ARUN KUMAR'));
Bu sorgu, iç içe geçmiş iki alt sorgu içerir. Böylece, aşağıdaki gibi üç bloğa ayrılabilir -
SELECT EMPID FROM EMPLOYEE WHERE NAME = 'ARUN KUMAR';
SELECT PID FROM WORKS WHERE EMPID = ArunEmpID;
SELECT PID, STATUS FROM PROJECT WHERE PID = ArunPID;
(Burada ArunEmpID ve ArunPID, iç sorguların sonuçlarıdır)
Üç blok için ilişkisel cebir ifadeleri:
$$ ArunEmpID \ leftarrow \ pi_ {EmpID} (\ sigma_ {Ad = \ small "Arun Kumar"} {(EMPLOYEE)}) $$
$$ ArunPID \ leftarrow \ pi_ {PID} (\ sigma_ {EmpID = \ small "ArunEmpID"} {(İŞLER)}) $$
$$ Result \ leftarrow \ pi_ {PID, Status} (\ sigma_ {PID = \ small "ArunPID"} {(PROJE)}) $$
İlişkisel Cebir Operatörlerinin Hesaplanması
İlişkisel cebir operatörlerinin hesaplanması birçok farklı şekilde yapılabilir ve her alternatife bir access path.
Hesaplama alternatifi üç ana faktöre bağlıdır -
- Operatör tipi
- Kullanılabilir hafıza
- Disk yapıları
İlişkisel bir cebir işleminin yürütülmesi için gereken süre -
- Kayıtları işleme zamanı.
- Tablonun demetlerini diskten belleğe alma zamanı.
Bir demeti işleme süresi, özellikle dağıtılmış bir sistemde, kaydı depodan getirme süresinden çok daha kısa olduğundan, disk erişimi genellikle ilişkisel ifadenin maliyetini hesaplamak için bir ölçü olarak kabul edilir.
Seçimin Hesaplanması
Seçim işleminin hesaplanması, seçim koşulunun karmaşıklığına ve tablonun öznitelikleri üzerindeki dizinlerin mevcudiyetine bağlıdır.
Aşağıda indekslere bağlı olarak hesaplama alternatifleri verilmiştir -
No Index- Tablo sıralanmamışsa ve dizini yoksa, seçim işlemi tablonun tüm disk bloklarının taranmasını içerir. Her blok belleğe getirilir ve bloktaki her bir tuple, seçim koşulunu karşılayıp karşılamadığını görmek için incelenir. Koşul yerine getirilirse, çıktı olarak görüntülenir. Bu, her demet hafızaya getirildiği ve her bir demet işlendiği için en maliyetli yaklaşımdır.
B+ Tree Index- Çoğu veritabanı sistemi B + Ağaç indeksi üzerine inşa edilmiştir. Seçim koşulu, bu B + Ağaç indeksinin anahtarı olan alana dayanıyorsa, bu indeks sonuçları almak için kullanılır. Ancak, karmaşık koşullara sahip seçim ifadelerinin işlenmesi, daha fazla sayıda disk bloğu erişimini ve bazı durumlarda tablonun tam olarak taranmasını içerebilir.
Hash Index- Karma dizinler kullanılıyorsa ve anahtar alanı seçim koşulunda kullanılıyorsa, karma dizini kullanarak tupleları almak basit bir işlem haline gelir. Bir karma dizini, karma değerine karşılık gelen anahtar değerinin depolandığı bir paketin adresini bulmak için bir karma işlevi kullanır. Dizinde bir anahtar değeri bulmak için, karma işlevi çalıştırılır ve paket adresi bulunur. Paket içindeki anahtar değerleri aranır. Bir eşleşme bulunursa, gerçek kayıt disk bloğundan belleğe alınır.
Birleşmelerin Hesaplanması
İki tabloyu birleştirmek istediğimizde, örneğin P ve Q, P'deki her bir demet, birleştirme koşulunun karşılanıp karşılanmadığını test etmek için Q'daki her bir demet ile karşılaştırılmalıdır. Koşul yerine getirilirse, karşılık gelen kayıtlar birleştirilerek yinelenen alanlar ortadan kaldırılır ve sonuç ilişkisine eklenir. Sonuç olarak, bu en pahalı işlemdir.
Bilgi işlem birleştirmeleri için yaygın yaklaşımlar şunlardır:
İç içe döngü Yaklaşımı
Bu, geleneksel birleştirme yaklaşımıdır. Aşağıdaki sözde kodla gösterilebilir (tuple_p ve tuple_q tuple'ları ve a birleştirme niteliği ile Tablo P ve Q) -
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
Sırala-birleştirme Yaklaşımı
Bu yaklaşımda, iki tablo birleştirme özniteliğine göre ayrı ayrı sıralanır ve ardından sıralanan tablolar birleştirilir. Kayıtların sayısı çok yüksek olduğundan ve hafızaya alınamadığından harici sıralama teknikleri benimsenmiştir. Ayrı tablolar sıralandıktan sonra, sıralanan tabloların her biri bir sayfa belleğe getirilir, birleştirici niteliğe göre birleştirilir ve birleştirilen tuplelar yazılır.
Hash-Join Yaklaşımı
Bu yaklaşım iki aşamadan oluşur: bölümleme aşaması ve araştırma aşaması. Bölümleme aşamasında, P ve Q tabloları iki ayrık bölüm grubuna ayrılır. Ortak bir hash fonksiyonuna karar verilir. Bu hash işlevi, tuple'ları bölümlere atamak için kullanılır. Araştırma aşamasında, P'nin bir bölümündeki tuplelar, karşılık gelen Q bölümünün tuplelarıyla karşılaştırılır. Eğer eşleşirlerse, yazılırlar.