JPS - Języki i Środowiska Programowania Baz Danych

Języki i Środowiska Programowania Baz Danych

I.	Wprowadzenie do języków zapytań (1)
II.	Wprowadzenie do języków zapytań (2)
III.	Pojęcia obiektowości w bazach danych (1)
IV.	Pojęcia obiektowości w bazach danych (2)
V.	Podstawy semantyczne języków zapytań
VI.	Modele składu obiektów
VII.	Stos środowisk, rezultaty zapytań, funkcja nested
VIII.	Język SBQL (Stack-Based Query Language) (1)
IX.	*Język SBQL (Stack-Based Query Language)* (2)**
X.	Dalsze własności SBQL
XI.	Operatory order by i group by
XII.	Przetwarzanie struktur nieregularnych
XIII.	Rozszerzenie języków zapytań o konstrukcje imperatywne
XIV.	Procedury, procedury funkcyjne, metody, reguły zakresu
XV.	Parametry procedur i metod, procedury rekurencyjne, optymalizacja poprzez modyfikację zapytań
	Wstęp
	1. Parametry procedur, funkcji i metod
	2. Procedury rekurencyjne
	3. Optymalizacja poprzez modyfikację zapytań
	Podsumowanie
	Zadania

3. Optymalizacja poprzez modyfikację zapytań

Modyfikacja zapytań jest podstawową metodą optymalizacji zapytań używających perspektyw. Jest stosowana we wszystkich systemach relacyjnych. Jak ustaliliśmy wcześniej, ponieważ pojęcie perspektywy, tak jak jest wprowadzone w systemach relacyjnych, jest równoważne procedurze funkcyjnej, w istocie metoda modyfikacji zapytań dotyczy tych ostatnich.

Metoda została sformułowana przez M.Stonebrakera w 1975 roku [Ston75], ale wskutek braku ortogonalności ówczesnych języków zapytań (w szczególności QUEL i SQL) sformułowanie jest bardzo złożone i niejasne. Wydawało się wówczas, że metoda jest całkowicie oryginalnym wynalazkiem.

Okazało się, że przy założeniu pełnej ortogonalności języka (cecha SBQL) i przy przyjęciu tezy, że perspektywa jest procedurą funkcyjną, metoda ta jest wariantem metody, która była znana już w latach 60-tych i powszechnie stosowana w optymalizacji języków programowania. Sprowadza się do następującego stwierdzenia:

Metoda modyfikacji zapytań polega na tym, że definicję funkcji traktuje się jako makrodefinicję.

Wszędzie tam, gdzie w zapytaniach występuje nazwa funkcji, zastępuje się tę nazwę poprzez tekst będący definicją tej nazwy (pomijając nieistotne elementy leksykalne). Po tym zabiegu uzyskuje się zapytanie bez odwołań do perspektyw. Poddaje się go następnie standardowym metodom optymalizacyjnych, np. przesuwaniem operatorów, usunięciu martwych podzapytań, wykorzystaniu indeksów itd.

Aby metoda ta prowadziła do semantycznie poprawnych konstrukcji i nie zmieniała znaczenia zapytania, jej zastosowanie wymaga wprowadzenia ograniczeń na postać deklaracji funkcji:

Funkcja nie może mieć lokalnego środowiska, w szczególności, nie może mieć parametrów.
Funkcja nie może być także rekurencyjna, pośrednio lub bezpośrednio, gdyż prowadziłoby to do nieskończonej pętli stosowania makrodefinicji.
Środowisko, w którym wywoływana jest funkcja, jest takie samo jak środowisko, w którym ewaluowane jest zapytanie wewnątrz tej funkcji.
Funkcja powinna mieć postać

procedure NazwaFunkcji { return zapytanie} równoważną pojedynczemu zapytaniu.

Dla większości zastosowań perspektyw te ograniczenia są spełnione. Niespełnienie któregoś z tych ograniczeń oznacza, że metoda prowadzi do błędów syntaktycznych, zapętlenia się lub braku równoważności semantycznej zapytania przed modyfikacją i po modyfikacji.

Jedną z przyczyn skomplikowania metody modyfikacji zapytań w systemach relacyjnych jest brak formalnej semantyki pomocniczych nazw. Jest ona niewyrażalna w algebrze relacji, rachunku relacyjnym i stosowanych w tym celu logikach, zatem oparcie semantyki języka zapytań na tych formalizmach powoduje poważne ograniczenia. Definicje perspektyw w SQL określają w nagłówku nazwy wirtualnych atrybutów, zatem wstawienie ciała definicji jako fragmentu zapytania wymaga odpowiednich operacji na tych nazwach.

P15.11.
SQL:

Patrz Rys.55. Definicja perspektywy w SQL ma postać:

create view PracSzef( Naz, NazD, NazSzefa) as
     select p.Nazwisko, d.Nazwa, s.Nazwisko
     from Prac p, Dział d, Prac s
    where p.PracujeW = d.NrD and d.Szef = s.NrP

Nowe nazwy Naz, NazD, NazSzefa są nazwami kolumn wirtualnej tabeli, których można używać w zapytaniach, np.:

Podaj nazwiska i nazwy działów pracowników nazywających się tak samo jak ich szef):

select p.Naz, p.NazD from PracSzef p where p.Naz = p.NazSzefa

Jeżeli w powyższym zapytaniu podstawilibyśmy na PracSzef tekst z definicji perspektywy znajdujący się po as, to otrzymalibyśmy niepoprawne zapytanie. Należałoby jeszcze dokonać odpowiedniej transformacji nazw Naz, NazD, NazSzefa występujących w tak przekształconym zapytaniu na nazwy atrybutów z zapamiętanych tabel, a to prowadzi do złożonych i niejasnych semantycznie algorytmów.

Ustalenie, że powstałe w ten sposób zmodyfikowane zapytanie w SQL nie zmienia zwracanego wyniku, jest dla tych algorytmów bardzo trudne i opiera się na inżynierskich spekulacjach raczej niż na poprawnie sformalizowanej semantyce. Jest dość prawdopodobne, że w niektórych systemach nie opanowano tego problemu dla złożonych zapytań, w związku z czym zastosowanie tej metody może prowadzić do błędów lub może być ograniczone. Ten problem całkowicie znika w SBQL, gdyż pomocnicze nazwy są tam objęte semantyką języka.

P15.12.

Patrz Rys.55, schemat relacyjny. Przenosząc dokładnie przykład P15.11 na grunt SBQL otrzymamy następującą definicję:

procedure PracSzef {
     return (Prac as p, Dział as d, Prac as s)
          where (p.PracujeW = d.NrD and d.Szef = s.NrP).
        (p.Nazwisko as Naz,
         d.Nazwa as NazD,
         s.Nazwisko as NazSzefa )}

Jak widać, nazwy "wirtualnych kolumn" tej perspektywy są standardowymi nazwami powoływanymi przez operator as. Dzięki temu nie ma problemów koncepcyjnych z modyfikacją zapytań. Sprowadza się ona do prostej operacji zastąpienia nazwy PracSzef występującej w zapytaniu przez tekst zapytania znajdującego się po słowie return. Zapytanie równoważne podanemu w przykładzie P15.11 zapytaniu SQL ma w SBQL następującą postać:

(PracSzef as p where p.Naz = p.NazSzefa). (p.Naz, p.NazD)

Jeżeli zamiast PracSzef podstawimy tekst zapytania z ciała definicji funkcji PracSzef, to otrzymamy następujące poprawne zapytanie w SBQL:

(((Prac as p, Dział as d, Prac as s)
where (p.PracujeW = d.NrD and d.Szef = s.NrP).
(p.Nazwisko as Naz, d.Nazwa as NazD, s.Nazwisko as NazSzefa )) as p
where p.Naz = p.NazSzefa). (p.Naz, p.NazD)

Zapytanie to nie ma już odwołań do funkcji PracSzef. Wynik tego zapytania będzie identyczny z wynikiem oryginalnego zapytania. Zapytanie to może być następnie optymalizowane.

Funkcje w SBQL nie ograniczają oczywiście modyfikacji zapytań do struktur relacyjnych. W ten sposób mogą być modyfikowane zapytania odwołujące się do dowolnych obiektowych struktur danych.

P15.13.

Patrz Rys.55, schemat obiektowy.

procedure MałoZarabiający {
return (Prac where Zar < 0.5 * avg( Prac.Zar ) ) .
( Nazwisko as N, Zar as Z, (PracujeW.Dział.Nazwa) as D) };

Funkcja MałoZarabiający zwraca bag struktur:

struct{ N(iNazwisko), Z(iZar), D(iNazwa)}

dla każdego pracownika zarabiającego mniej niż połowa średniej zarobków; iatr jest referencją do atrybutu atr. Funkcja ta może być użyta w następującym zapytaniu:

(MałoZarabiający where N = "Bilski").Z

Załóżmy, że w bazie danych dostęp poprzez atrybut Nazwisko jest wspomagany indeksem IndeksPracNazwisko( nazw ), który zwraca referencję do obiektów Prac dla stringowego parametru nazw będącego nazwiskiem. Zauważmy następujące okoliczności:

Zmaterializowanie wyniku procedury będzie czasochłonne.
Indeks IndeksPracNazwisko, zapewniający szybki dostęp do obiektów według nazwisk, w powyższym zapytaniu nie może być wykorzystany.
Zwracanie przez funkcję nazwy działu jest niepotrzebne, bo tej danej zapytanie nie wykorzystuje.

Modyfikacja zapytań usuwa te problemy. Dzięki niej nie trzeba będzie liczyć wszystkich elementów tej perspektywy, w szczególności jej niepotrzebnych członów. Można będzie również wykorzystać indeks. Prześledźmy to na kolejnych krokach. Po makrosubstytucji otrzymamy następujące zapytanie:

(( (Prac where Zar < 0.5 * avg( Prac.Zar )).
(Nazwisko as N, Zar as Z, (PracujeW.Dział.Nazwa) as D) )
where N = "Bilski") . Z

Szarym tłem zaznaczyliśmy podstawione zapytanie. Możemy teraz dokonać optymalizacji. Podzapytanie (PracujeW.Dział.Nazwa) as D nie jest używane (jest "martwe"); może być więc usunięte. Otrzymamy w ten sposób następującą formę tego zapytania:

(( (Prac where Zar < 0.5 * avg( Prac.Zar ) ).
(Nazwisko as N, Zar as Z) )
where N = "Bilski") . Z

Rezultat podzapytania 0.5 * avg( Prac.Zar ) jest identyczny dla wszystkich pracowników; podzapytanie to może być zatem wyciągnięte przed pętlę implikowaną przez pierwszy operator where:

(((0.5 * avg(Prac.Zar )) as x).(Prac where Zar < x ).
(Nazwisko as N, Zar as Z)
where N = "Bilski") . Z

Definicje pomocniczych nazw N i Z stają się zbędne; można je usunąć, zastępując oryginalnymi nazwami Nazwisko i Zar:

(((0.5 * avg(Prac.Zar )) as x).(Prac where Zar < x )
where Nazwisko = "Bilski") . Zar

Warunki w dwóch następujące po sobie operatorach where łączymy w jeden warunek połączony operatorem and:

((0.5 * avg(Prac.Zar )) as x).(Prac where Zar < x
and Nazwisko = "Bilski") . Zar

W tej chwili można wykorzystać indeks IndeksPracNazwisko, którego wywołanie zastępuje zapytanie Prac where Nazwisko = "Bilski":

((0.5 * avg(Prac.Zar )) as x).
(IndeksPracNazwisko( "Bilski" ) where Zar < x ). Zar

Zapytanie jest ostatecznie zoptymalizowane. Optymalizacja odbywała się na podstawie reguł, które można sformalizować i zaimplementować.

Jeżeli procedura funkcyjna ma parametry, wówczas makrosubstytucja wymaga potraktowania każdego parametru również jako makro. To sugeruje metodę transmisji parametrów znaną jako wołanie przez nazwę (call-by-name). Powstaje pytanie, kiedy ta metoda transmisji parametrów jest semantycznie równoważna przyjętej w SBQL metodzie ścisłego wołania przez wartość. Dla prostych przykładów, w których nie występuje zmiana środowiska obliczania parametru po zastosowaniu metody wołania przez nazwę, semantyczna równoważność wydaje się oczywista. Ogólny przypadek wymaga jednak dalszych badań.

W niektórych sytuacjach makrosubstutucję można odwrócić w taki sposób, aby zmodyfikować definicję funkcji (perspektywy), a nie zapytanie. Jeżeli zapytanie ma postać:

f where q

gdzie f jest wywołaniem funkcji, to klauzuję where q można przesunąć do wnętrza deklaracji f. Ma to sens w tych sytuacjach, gdy deklaracja f nie składa się z pojedynczego zdania return p, lecz ma bardziej skomplikowaną strukturę, wobec czego zastosowanie metody modyfikacji zapytań jest niemożliwe. Jeżeli ta deklaracja kończy się zdaniem return p, wówczas można zmodyfikować ją do postaci return p where q, zaś nasze początkowe zapytanie zredukować do wywołania f. Dzięki temu może pojawić się nowa szansa na optymalizację zapytania p where q, np. poprzez zastosowanie indeksu. Zgodnie z wiedzą autora, metoda ta nie ma precedensu w historii baz danych, wymaga więc dalszych badań.