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 -

STUDENT
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.