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 -
|
|
||||
| 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-pPodejś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.