Języki i Środowiska Programowania Baz Danych
4. Procedura ewaluacji zapytań eval
Będziemy definiować semantykę operacyjną naszego języka zapytań poprzez procedurę rekurencyjną, którą nazwaliśmy eval. Argumentem procedury eval jest dowolne zapytanie, zaś wynikiem procedury jest rezultat tego zapytania włożony na wierzchołek stosu rezultatów QRES. Procedura eval będzie korzystać ze składu obiektów, ENVS oraz QRES. Dla zapytań bez efektów ubocznych (nie wywołujących metod lub funkcji, które mogą zmienić stan), zachowane będą następujące założenia:
- Procedura eval nie zmienia stanu składu obiektów;
- Procedura eval w trakcie ewaluacji zapytania q może zmieniać stan ENVS, ale po zakończeniu ewaluacji q stan ten będzie dokładnie taki sam, jak przed rozpoczęciem ewaluacji;
- Procedura eval w trakcie ewaluacji zapytania q nigdy nie zmienia tej części stosu rezultatów, którą zastała w momencie rozpoczęcia ewaluacji. Może wkładać na ten stos i zdejmować wiele różnych elementów, ale po zakończeniu ewaluacji stos ten będzie posiadać dokładnie jeden element więcej niż przed ewaluacją; tym elementem będzie rezultat zapytania q; jest to zilustrowane na Rys.45.
Definicja semantyki będzie sterowana abstrakcyjną składnią. Oznacza to, że procedura eval jest wspomagana przez analizator gramatyczny (parser), który dokona hierarchicznego rozbioru gramatycznego zapytania na podzapytania oraz operatory łączące podzapytania. Następnie, każde podzapytanie zwróci swój rezultat, zaś rezultat całego zapytania jest obliczany na podstawie rezultatów zwróconych przez jego składowe podzapytania. Ta własność składni i semantyki nosi nazwę modularności lub kompozycyjności.
Rys.45. Rezultat działania procedury eval na stosie rezultatów QRES
Rezultaty zapytań zapisane na stosie rezultatów są "konsumowane" przez operatory danego języka lub interfejsu, dla których zapytania były parametrami. Takim operatorem może być znany z SQL operator delete oznaczający usunięcie danych, np.:
| P8.2. | delete Osoba where Nazwisko = "Nowak"; |
Wykonanie tego polecenia oznacza ewaluację przez procedurę eval zapytania Osoba where Nazwisko = "Nowak", w wyniku czego na wierzchołku stosu rezultatów pojawi się wynik tej ewaluacji w postaci referencji do obiektu Nowaka (tj. jego identyfikatora). Następnie ten rezultat zostanie "skonsumowany" przez operator delete, który później usunie go ze stosu. Zakładamy, że w poprawnie zbudowanym języku i jego mechanizmie nie może wystąpić zapytanie, którego wynik nie będzie "skonsumowany" przez pewien operator. Dzięki temu wzrost stosu QRES będzie kontrolowany i na zakończenie pewnej spójnej porcji czynności jego wysokość i zawartość będzie taka sama, jak przed rozpoczęciem tych czynności.
Elementarnym zapytaniem w definiowanym przez nas języku SBQL może być leksykalny reprezentant wartości l Î L lub zewnętrzna nazwa n Î N. Definicja procedury eval (w pseudokodzie) dla takich zapytań jest bardzo prosta:
procedure eval( q : zapytanie )
begin
parse( q ); // rozbiór gramatyczny zapytania na składowe podzapytania
case q jest rozpoznane jako l Î L :
push( QRES, l );
case q jest rozpoznane jako n Î N :
push( QRES, bind( n ) );
case .....
.....
end;
Jeżeli zapytanie jest literałem l Î L, to procedura eval wkłada odpowiadającą mu wartość atomową l Î V na wierzchołek stosu QRES. Jeżeli zapytanie jest zewnętrzną nazwą n Î N, to procedura eval dokonuje wiązania tej nazwy na ENVS (funkcja bind), a następnie wynik tego wiązania wkłada na wierzchołek stosu QRES.
Dla innych przypadków procedura eval dokonuje rozbioru gramatycznego w celu wyodrębnienia z każdego zapytania jednego lub dwóch podzapytań oraz operatora, który jest zastosowany do tych podzapytań. Następnie wyznacza rezultaty tych podzapytań (w kolejności określonej operatorem, dla niektórych operatorów - wielokrotnie) i łączy je w rezultat całego zapytania zgodnie z łączącym je operatorem. Ten proces jest rekurencyjny, tj. podzapytania są rozkładane na podpodzapytania itd. aż do podanych wyżej przypadków zapytań elementarnych. Rys.46 przedstawia rozbiór prostego zapytania w postaci tzw. drzewa syntaktycznego.
Operatory łączące zapytania będziemy dzielić na algebraiczne i niealgebraiczne, przy czym istotą podejścia stosowego są operatory niealgebraiczne. Fundamentalna różnica pomiędzy operatorami niealgebraicznymi i algebraicznymi polega na ich stosunku do stosu środowisk. Operatory algebraiczne nie używają ENVS: działanie takiego operatora dotyczy wyłącznie stosu QRES (zwykle jego jednego lub dwóch wierzchołkowych elementów). Natomiast operatory niealgebraiczne, oprócz działań na QRES, bezpośrednio odwołują się do konstrukcji i operacji zachodzących na ENVS.
Rys.46. Drzewo syntaktyczne zapytania Osoba where Nazwisko = "Nowak"
Materiały zostały opracowane w PJWSTK w projekcie współfinansowanym ze środków EFS.