Algebra relacyjna dla optymalizacji zapytań

Po umieszczeniu zapytania jest ono najpierw skanowane, analizowane i sprawdzane. Następnie tworzona jest wewnętrzna reprezentacja zapytania, taka jak drzewo zapytań lub wykres zapytań. Następnie opracowywane są alternatywne strategie wykonywania pobierania wyników z tabel bazy danych. Proces wyboru najbardziej odpowiedniej strategii wykonywania zapytań nazywa się optymalizacją zapytań.

Problemy z optymalizacją zapytań w DDBMS

W DDBMS optymalizacja zapytań jest kluczowym zadaniem. Złożoność jest duża, ponieważ liczba alternatywnych strategii może rosnąć wykładniczo z powodu następujących czynników -

  • Obecność wielu fragmentów.
  • Dystrybucja fragmentów lub tabel w różnych witrynach.
  • Szybkość łączy komunikacyjnych.
  • Różnica w lokalnych możliwościach przetwarzania.

Dlatego w systemie rozproszonym często celem jest znalezienie dobrej strategii wykonywania zapytań, a nie najlepszej. Czas wykonania zapytania to suma następujących elementów -

  • Czas na przekazywanie zapytań do baz danych.
  • Czas na wykonanie lokalnych fragmentów zapytania.
  • Czas zebrać dane z różnych witryn.
  • Czas na wyświetlenie wyników aplikacji.

Przetwarzanie zapytań

Przetwarzanie zapytań to zestaw wszystkich czynności, począwszy od umieszczenia zapytania, a skończywszy na wyświetleniu wyników zapytania. Kroki są pokazane na poniższym schemacie -

Algebra relacyjna

Algebra relacyjna definiuje podstawowy zestaw operacji modelu relacyjnej bazy danych. Sekwencja operacji algebry relacyjnej tworzy wyrażenie algebry relacyjnej. Wynik tego wyrażenia reprezentuje wynik zapytania do bazy danych.

Podstawowe operacje to -

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

Występ

Operacja rzutowania wyświetla podzbiór pól tabeli. Daje to pionowy podział tabeli.

Syntax in Relational Algebra

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

Na przykład rozważmy następującą bazę danych Studentów -

STUDENT
Roll_No Name Course Semester Gender
2 Amit Prasad BCA 1 Męski
4 Varsha Tiwari BCA 1 Płeć żeńska
5 Asif Ali MCA 2 Męski
6 Joe Wallace MCA 1 Męski
8 Shivani Iyengar BCA 1 Płeć żeńska

Jeśli chcemy wyświetlić nazwiska i kursy wszystkich uczniów, użyjemy następującego wyrażenia algebry relacyjnej -

$$ \ pi_ {Imię, Kurs} {(STUDENT)} $$

Wybór

Operacja wyboru wyświetla podzbiór krotek tabeli, który spełnia określone warunki. Daje to poziomy podział tabeli.

Syntax in Relational Algebra

$$ \ sigma _ {<{Conditions}>} {(<{Table Name}>)} $$

Na przykład w tabeli Student, jeśli chcemy wyświetlić szczegóły wszystkich studentów, którzy wybrali kurs MCA, użyjemy następującego wyrażenia algebry relacyjnej -

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

Połączenie operacji projekcji i wyboru

W przypadku większości zapytań potrzebujemy kombinacji operacji rzutowania i wyboru. Istnieją dwa sposoby zapisania tych wyrażeń -

  • Korzystanie z sekwencji operacji rzutowania i wyboru.
  • Używanie operacji zmiany nazwy do generowania wyników pośrednich.

Na przykład, aby wyświetlić imiona i nazwiska wszystkich studentek kursu BCA -

  • Wyrażenie algebry relacyjnej przy użyciu sekwencji rzutowania i operacji wyboru

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

  • Wyrażenie algebry relacyjnej używające operacji zmiany nazwy do generowania wyników pośrednich

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

$$ Wynik \ leftarrow \ pi_ {Imię} {(KobietaBCAStudent)} $$

Unia

Jeśli P jest wynikiem operacji, a Q jest wynikiem innej operacji, suma P i Q ($ p \ cup Q $) jest zbiorem wszystkich krotek znajdujących się w P lub w Q lub w obu bez duplikatów .

Na przykład, aby wyświetlić wszystkich studentów, którzy są w semestrze 1 lub na kursie BCA -

$$ Sem1Student \ leftarrow \ sigma_ {Semester = 1} {(STUDENT)} $$

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

$$ Wynik \ leftarrow Sem1Student \ cup BCAStudent $$

Skrzyżowanie

Jeśli P jest wynikiem operacji, a Q jest wynikiem innej operacji, przecięcie P i Q ($ p \ cap Q $) jest zbiorem wszystkich krotek, które znajdują się zarówno w P, jak i Q.

Na przykład, biorąc pod uwagę następujące dwa schematy -

EMPLOYEE

EmpID Nazwa Miasto Departament Wynagrodzenie

PROJECT

PId Miasto Departament Status

Aby wyświetlić nazwy wszystkich miast, w których znajduje się projekt, a także mieszka pracownik -

$$ CityEmp \ leftarrow \ pi_ {Miasto} {(PRACOWNIK)} $$

$$ CityProject \ leftarrow \ pi_ {Miasto} {(PROJEKT)} $$

$$ Wynik \ leftarrow CityEmp \ cap CityProject $$

Minus

Jeśli P jest wynikiem operacji, a Q jest wynikiem innej operacji, P - Q jest zbiorem wszystkich krotek, które są w P, a nie w Q.

Na przykład, aby wyświetlić wszystkie działy, które nie mają trwającego projektu (projekty ze statusem = w toku) -

$$ AllDept \ leftarrow \ pi_ {Dział} {(PRACOWNIK)} $$

$$ ProjectDept \ leftarrow \ pi_ {Dział} (\ sigma_ {Status = \ small "w toku"} {(PROJECT)}) $$

$$ Wynik \ leftarrow AllDept - ProjectDept $$

Przystąp

Operacja łączenia łączy powiązane krotki z dwóch różnych tabel (wyników zapytań) w jedną tabelę.

Na przykład rozważ dwa schematy, klienta i oddział w bazie danych banku w następujący sposób -

CUSTOMER

CustID AccNo TypeOfAc BranchID DateOfOpening

BRANCH

BranchID Nazwa filii Kod IFSC Adres

Aby wyświetlić dane pracownika wraz ze szczegółami oddziału -

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

Tłumaczenie zapytań SQL na algebrę relacyjną

Zapytania SQL są tłumaczone na równoważne wyrażenia algebry relacyjnej przed optymalizacją. Zapytanie jest najpierw rozkładane na mniejsze bloki zapytań. Bloki te są tłumaczone na równoważne wyrażenia algebry relacyjnej. Optymalizacja obejmuje optymalizację każdego bloku, a następnie optymalizację zapytania jako całości.

Przykłady

Rozważmy następujące schematy -

PRACOWNIK

EmpID Nazwa Miasto Departament Wynagrodzenie

PROJEKT

PId Miasto Departament Status

PRACUJE

EmpID PID godziny

Przykład 1

Aby wyświetlić szczegóły wszystkich pracowników, którzy zarabiają NIŻEJ niż średnia pensja, piszemy zapytanie SQL -

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

To zapytanie zawiera jedno zagnieżdżone zapytanie podrzędne. Można to więc podzielić na dwa bloki.

Blok wewnętrzny to -

SELECT AVERAGE(SALARY)FROM EMPLOYEE ;

Jeśli wynikiem tego zapytania jest AvgSal, to blok zewnętrzny to -

SELECT * FROM EMPLOYEE WHERE SALARY < AvgSal;

Wyrażenie algebry relacyjnej dla bloku wewnętrznego -

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

Wyrażenie algebry relacyjnej dla bloku zewnętrznego -

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

Przykład 2

Aby wyświetlić identyfikator projektu i status wszystkich projektów pracownika „Arun Kumar”, piszemy zapytanie SQL -

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

To zapytanie zawiera dwa zagnieżdżone zapytania podrzędne. W ten sposób można podzielić na trzy bloki w następujący sposób -

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

(Tutaj ArunEmpID i ArunPID to wyniki zapytań wewnętrznych)

Wyrażenia algebry relacyjnej dla trzech bloków to -

$$ ArunEmpID \ leftarrow \ pi_ {EmpID} (\ sigma_ {Imię = \ small "Arun Kumar"} {(PRACOWNIK)}) $$

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

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

Obliczanie operatorów algebry relacyjnej

Obliczenia operatorów algebry relacyjnej można wykonać na wiele różnych sposobów, a każda alternatywa nosi nazwę access path.

Alternatywa obliczeniowa zależy od trzech głównych czynników -

  • Typ operatora
  • Dostępna pamięć
  • Struktury dyskowe

Czas do wykonania operacji algebry relacyjnej jest sumą -

  • Czas przetworzyć krotki.
  • Czas pobrać krotki tabeli z dysku do pamięci.

Ponieważ czas przetwarzania krotki jest znacznie krótszy niż czas pobierania krotki z pamięci, szczególnie w systemie rozproszonym, dostęp do dysku jest bardzo często brany pod uwagę jako metryka do obliczania kosztu wyrażenia relacyjnego.

Obliczanie selekcji

Obliczenie operacji selekcji zależy od złożoności warunku selekcji i dostępności indeksów atrybutów tabeli.

Poniżej przedstawiono alternatywy obliczeń w zależności od indeksów -

  • No Index- Jeśli tabela jest nieposortowana i nie ma indeksów, wówczas proces wyboru obejmuje skanowanie wszystkich bloków dyskowych tabeli. Każdy blok jest wprowadzany do pamięci, a każda krotka w bloku jest badana w celu sprawdzenia, czy spełnia warunek wyboru. Jeśli warunek jest spełniony, jest wyświetlany jako dane wyjściowe. Jest to najbardziej kosztowne podejście, ponieważ każda krotka jest wprowadzana do pamięci i każda krotka jest przetwarzana.

  • B+ Tree Index- Większość systemów baz danych jest zbudowana na indeksie B + Tree. Jeśli warunek wyboru jest oparty na polu, które jest kluczem tego indeksu B + Tree, to ten indeks jest używany do pobierania wyników. Jednak przetwarzanie instrukcji wyboru ze złożonymi warunkami może wiązać się z większą liczbą dostępów do bloków dysku, aw niektórych przypadkach z całkowitym skanowaniem tabeli.

  • Hash Index- Jeśli używane są indeksy haszujące, a jego pole klucza jest używane w warunku wyboru, pobieranie krotek przy użyciu indeksu skrótu staje się prostym procesem. Indeks skrótu używa funkcji skrótu, aby znaleźć adres zasobnika, w którym przechowywana jest wartość klucza odpowiadająca wartości skrótu. Aby znaleźć wartość klucza w indeksie, wykonywana jest funkcja skrótu i ​​znajduje się adres zasobnika. Przeszukiwane są wartości kluczowe w zasobniku. Jeśli zostanie znalezione dopasowanie, rzeczywista krotka jest pobierana z bloku dysku do pamięci.

Obliczanie połączeń

Kiedy chcemy połączyć dwie tabele, powiedzmy P i Q, każdą krotkę w P należy porównać z każdą krotką w Q, aby sprawdzić, czy warunek łączenia jest spełniony. Jeśli warunek jest spełniony, odpowiednie krotki są łączone, eliminując zduplikowane pola i dołączane do relacji wyniku. W konsekwencji jest to najdroższa operacja.

Typowe podejścia do obliczania sprzężeń to -

Podejście w pętli zagnieżdżonej

Jest to konwencjonalne podejście do łączenia. Można to zilustrować za pomocą następującego pseudokodu (tabele P i Q, z krotkami tuple_p i tuple_q oraz atrybutem łączenia 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

Podejście sortowania

W tym podejściu dwie tabele są sortowane indywidualnie na podstawie atrybutu łączenia, a następnie sortowane tabele są łączone. Przyjęto zewnętrzne techniki sortowania, ponieważ liczba rekordów jest bardzo duża i nie można ich zmieścić w pamięci. Po posortowaniu poszczególnych tabel do pamięci przenoszona jest jedna strona z każdej posortowanej tabeli, łączona na podstawie atrybutu łączenia, a połączone krotki są zapisywane.

Podejście z łączeniem mieszanym

Podejście to obejmuje dwie fazy: fazę podziału i fazę sondowania. W fazie partycjonowania tabele P i Q są podzielone na dwa zestawy rozłącznych partycji. Podjęto decyzję o wspólnej funkcji skrótu. Ta funkcja skrótu służy do przypisywania krotek do partycji. W fazie sondowania krotki w partycji P są porównywane z krotkami odpowiadającej partycji Q. Jeśli pasują, są zapisywane.