2. Stos rezultatów (QRES)

Jak w większości języków, wszelkie pośrednie i końcowe rezultaty zapytań (wyrażeń) będą odkładane na stosie rezultatów, który będziemy oznaczać QRES (Query REsult Stack). Stos rezultatów jest prostym uogólnieniem stosu arytmetycznego spotykanego w implementacji języków programowania. Rys.41 ilustruje działanie stosu rezultatów dla prostego wyrażenia arytmetycznego.

Rys.41. Stany stosu rezultatów dla prostego wyrażenia

Po tych operacjach wierzchołek stosu rezultatów zawiera obliczony rezultat wyrażenia. Operacje na stosie arytmetycznym odpowiadają nawiasowaniu wyrażenia; w innym ujęciu są one realizacją tzw. odwrotnej notacji polskiej.

Stos rezultatów dla języka zapytań będzie opierał się na identycznej zasadzie jak zilustrowana powyżej, z następującymi różnicami:

• Elementami stosu będą rezultaty zapytań (elementy zbioru Rezultat) zdefiniowane poprzednio;
  
  
• Stos będzie przechowywał także wszelkie pomocnicze elementy niezbędne do obliczania zapytań; w szczególności, liczniki pętli iteracyjnych implikowanych przez operatory działające na kolekcjach. Elementy te nie będą uwzględniane w opisie formalnej semantyki.
  

Dla sformułowania semantyki języków, w tym języków zapytań, stos rezultatów ma znaczenie drugorzędne i w niektórych sformułowaniach tej semantyki (np. przy zastosowaniu semantyki matematycznej zwanej denotacyjną) jest zbędny. Jest on również zbędny w sytuacji, gdy naszą semantykę zaimplementujemy poprzez zestaw rekurencyjnych procedur. Mamy jednak kilka powodów, aby wprowadzić to pojęcie:

• Stos ten jest wygodny przy podejściu operacyjnym do semantyki. Nasze doświadczenie wskazuje, że inne podejścia (np. denotacyjne) są trudne do zrozumienia przez Czytelnika mało wprawionego w abstrakcyjnej matematyce. Ponadto, zwiększają znacznie dystans pomiędzy opisem semantyki a implementacją języka.
  
  
• Stos ten uzupełnia koncepcję abstrakcyjnej implementacji, która jest cechą i zaletą podejścia stosowego. Dzięki wprowadzeniu tego stosu nasze rozważania można bez trudu odwzorować na zaimplementowane struktury danych i programy;
  
  
• Stos rezultatów jest skojarzony z jego statycznym odpowiednikiem funkcjonującym podczas statycznej analizy zapytania. Statyczny stos rezultatów jest niezbędnym elementem optymalizatora zapytań.
  

Stos QRES jest abstrakcyjną strukturą danych obsługiwaną przez cztery operatory:

• push (włóż nowy element na wierzchołek stosu),
  
• pop (zdejmij jeden element z wierzchołka stosu),
  
• top (odczytaj wierzchołek stosu),
  
• empty (sprawdź, czy stos jest pusty).

Operacje na stosie odbywają się zawsze na jego wierzchołku (uwzględniają jeden lub dwa wierzchołkowe elementy). Pozostałe elementy stosu staną się widoczne dopiero wtedy, gdy zdejmiemy pewną liczbę elementów z jego wierzchołka. Rys.42 przedstawia przykładowy stan stosu rezultatów w podejściu stosowym.

Rys.42. Przykładowy stan stosu rezultatów QRES