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.
X.
Dalsze własności SBQL
XI.
Operatory order by i group by
  Wstęp
  1. Operator sortowania order by
  2. Operator group by - czy potrzebny?
  Podsumowanie
  Zadania
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ń

 

1. Operator sortowania order by


1.1. Definicja operatora order by w SBQL

Operator order by został zaimplementowany w SBQL systemu Loqis. Niżej objaśnimy (nieco uogólnioną) ideę tego operatora. Operator ten będzie należał do kategorii niealgebraicznych. Przyjmijmy następującą składnię (rozszerzającą podane wcześniej reguły składniowe SBQL):

zapytanie ::= zapytanie order by zapytanie

Semantyka zapytania q1 order by q2 jest następująca. Przedmiotem sortowania jest bag lub sekwencja zwrócona przez q1. Podzapytanie q2 wyznacza klucz sortowania. Wynikiem całego zapytania jest sekwencja powstająca z bagu lub sekwencji zwróconej przez q1, która jest uporządkowana zgodnie z kluczem  q2. Zapytanie q2 wyznacza strukturę (ogólnie: bag struktur) struct{v1, v2, ..., vk}, gdzie vi Î Di, zaś Di Í V. Zbiory Di są dziedzinami, w których istnieje naturalny porządek liniowy, np. taką dziedziną może być zbiór liczb całkowitych, zbiór liczb rzeczywistych, zbiór stringów, zbiór wszystkich dat (zapisanych w takiej reprezentacji, która umożliwia ustalenie, która z nich jest wcześniejsza/późniejsza) itd.

Przetwarzanie zapytania q1 order by q2 odbywa się w sposób następujący:

  • Oblicza się zależne złączenie q1 join q2. Jeżeli zapytanie q1 zwróci bag bag{ r1, r2, ... }, to w wyniku całego zapytania otrzymujemy bag o budowie
         bag{ struct{ r1, v11, v21, ..., vk1 },
                   struct{ r2, v12, v22, ..., vk2 },   ....  }

    (Analogicznie, jeżeli q1 zwróci sekwencję.)

  • Jeżeli któreś z vij jest referencją, to dokonuje się automatycznie dereferencji, zamieniając ją na wartość. Jeżeli dereferencja nie jest zdefiniowana lub wartość vij (po ewentualnej dereferencji) nie należy do dziedziny Di Í V, w której obowiązuje naturalny porządek liniowy, wówczas sytuacja ta jest uważana za błędną.

  • Dokonuje się sortowania powstałego bagu, które zamienia go na sekwencję. Sortowanie następuje według pierwszego klucza, w ramach identycznych wartości pierwszego klucza - według drugiego klucza itd.

  • Po sortowaniu otrzymamy sekwencję:
         sequence{ struct{ s1, vs11, vs21, ..., vsk1 },
                              struct{ s2, vs12, vs22, ..., vsk2 },   ....  }

    która powstała z poprzedniego bagu poprzez jego posortowanie;  si są rezultatami ri, po zamianie ich kolejności.

    Końcowy rezultat uzyskujemy po rzutowaniu powstałej sekwencji na rezultaty q1; usuwamy rezultaty zwrócone przez  q2. Powstaje więc sekwencja: sequence{ s1, s2,   ....  }, która jest ostatecznym rezultatem zapytania q1 order by q2.


Przykłady
(patrz Rys.61):

P11.1.

Podaj identyfikatory wszystkich pracowników posortowane według ich nazwisk:

Prac order by Nazwisko


Wynikiem będzie sequence{iPrac1, iPrac2, iPrac3...} identyfikatorów obiektów Prac, posortowanych według nazwisk. Zwrócimy uwagę, że wykorzystaliśmy dziedziczenie.

P11.2.

Podaj identyfikatory wszystkich pracowników posortowane według ich wieku, zaś w ramach tego samego wieku - według nazwisk:

Prac order by (Wiek, Nazwisko)

P11.3.

Podaj działy posortowane według liczby pracowników w działach oraz według nazwisk ich szefów; zwróć nazwę działu oraz jego lokacje posortowane alfabetycznie.

(Dział order by (count(Zatrudnia), (Szef.Prac.Nazwisko))) .
(Nazwa, (((Lokacja as x) order by x).x) group as lokacje)

Przy porządkowaniu lokacji posłużyliśmy się pomocniczą zmienną x, której następnie użyliśmy jako klucza sortowania. Aby pozbyć się tej zmiennej z wyniku, dokonaliśmy projekcji na x. Wszystkie lokacje danego działu zostały zgrupowane w postaci jednego bindera o nazwie lokacje.


1.2. Puste i wielowartościowe klucze

Przedstawiona semantyka operatora order by posiada kilka niuansów, które niżej omówimy. Pierwszy z nich dotyczy sytuacji, kiedy w zapytaniu q1 order by q2 podzapytanie q2 zwraca pusty wynik. Np. przyjmijmy schemat z Rys.61, gdzie w obiektach Prac podobiekt Zar może nie wystąpić. Wówczas zgodnie z przedstawiona semantyką opartą na zależnym złączeniu zapytanie: 

P11.4.

Prac order by Zar

pominie tych pracowników, dla których Zar nie występuje. Jeżeli programiście zależałoby na tym, aby jednak uwzględnić tych pracowników w dostarczonym wyniku, wówczas musi ustalić dla nich klucz sortowania, np. przyjmując, że dla pracowników nie posiadających informacji o zarobku ten klucz wynosi zero. Odpowiednie zapytanie (jedno z wielu) może mieć następującą postać:

P11.5.

Prac order by max( bag(0, Zar) )

Dla pracowników nie posiadających zarobku bag(0, Zar) będzie zawierał pojedynczy element 0, zaś dla posiadających zarobek - dwa elementy: 0 oraz referencję do zarobku. Funkcja max zwróci więc 0 dla pracowników nie posiadających zarobku i aktualny zarobek dla pozostałych.

Podobna sytuacja następuje wtedy, gdy w zapytaniu q1 order by q2 podzapytanie q2 zwraca wiele wartości, np. zapytanie:

P11.6.

Prac order by Stan

Zgodnie z przedstawioną semantyką opartą na zależnym złączeniu, identyfikatory pracowników posiadających więcej niż jedno stanowisko będą w wyniku powielone tyle razy, ile dany pracownik ma stanowisk; następnie te identyfikatory zostaną posortowane według poszczególnych stanowisk. Taka interpretacja jest logiczna i konsekwentna, ale programista powinien być jej świadomy. Oczywiście, może on użyć innych środków, aby dla uniknięcia wspomnianych powtórzeń, ustalić takie q2, które zwróci dla pracownika dokładnie jedno stanowisko, np.:

P11.7.

Prac order by ((((Stan as z) order by z).z) [1])

W tym przypadku programista uporządkował stanowiska pracownika alfabetycznie i wybrał pierwsze stanowisko jako klucz sortowania.


1.3. Sortowanie w kolejności rosnącej i malejącej

W SQL i OQL do tego celu służą specjalne słowa kluczowe ASC (ascending) i DESC (descending) umieszczone za danym kluczem sortowania (pierwsze z nich jest domyślne). Można bez trudu rozpoznać, że obydwie opcje oznaczają funkcje działające na kluczach sortowania. ASC jest funkcją identyczności (zwraca swój argument), zaś DESC jest funkcją zwracającą element będący dopełnieniem swojego argumentu zgodnym z określonym porządkiem liniowym. Przykładowo, dla liczby całkowitej X dopełnieniem jest -X, lub (przyjmując, że liczby ujemne nie mogą być kluczem sortowania) 1000000000 - X, gdzie jest 1000000000 jest (przykładowym) maksymalnym kluczem. Podobnie, dopełnieniem stringu może być string, w którym każdy znak w ASCII o kodzie k zostaje zastąpiony przez znak o kodzie 256 - k. Funkcję DESC należy zdefiniować dla każdej dziedziny D, której element może być użyty jako klucz. Funkcja ta może odwoływać się do własności fizycznych reprezentacji, zatem powinna być napisana w języku niskiego poziomu jako "wszyta" w interpreter. Jest rzeczą syntaktycznie drugorzędną, czy nazwy tych funkcji wystąpią jako prefiksy argumentów (jak zwykle) czy też jako postfixy argumentów (jak w SQL i OQL).

P11.8.

Podaj identyfikatory wszystkich pracowników posortowane malejąco według wieku i rosnąco według ich nazwisk:

Prac order by (DESC(Wiek), ASC(Nazwisko))


1.4. Uwzględnienie porządku alfabetycznego w językach narodowych

Operator order by języka SQL wzbudził w swoim czasie kontrowersje dotyczące sposobu sortowania stringów. Twórcy tego operatora oparli się na kodzie ASCII, w którym porządek liter odpowiada alfabetowi angielskiemu. Reguły porządku alfabetycznego są jednak inne np. dla niemieckiego, francuskiego lub polskiego, a ponadto alfabety różnią się zestawem znaków, co w początkowym okresie wdrażania systemów relacyjnych na rynkach poza angielsko-języcznych wzbudziło protesty użytkowników. W efekcie, dostawcy systemów relacyjnych poprawili tę klauzulę w taki sposób, aby uwzględnić narodowe reguły porządku alfabetycznego.

Powyższą własność można rozwiązać dwojako. Pierwsza opcja polega na tym, że podczas instalacji systemu ustala się, z jakim językiem narodowym ma on pracować, i dla tego języka wewnętrznie ustala się procedurę porównania dwóch stringów będącą podstawą procedury sortowania. Wariant ten (zastosowany w większości systemów relacyjnych) jest niestety mało elastyczny, gdyż uniemożliwia pracę systemu z kilkoma językami jednocześnie. Druga opcja polega na tym, aby zdefiniować i zaimplementować rodzinę funkcji, takich jak francuski, niemiecki, polski, węgierski (podobnych do funkcji DESC), która dla danego stringu zwróci wartość kompatybilną z porządkiem tego stringu w danym języku narodowym. Rozwiązanie to jest oczywiście możliwe tylko wtedy, gdy system kodowania znaków nie jest zależny od narodowego języka (np. jest to Unicode). Ponieważ to, co zwróci taka funkcja, jest sprawą wewnętrzną (implementacyjną), nie jest istotna dziedzina, do której taka wartość należy, w szczególności może to być dziedzina liczbowa. Następny przykład ilustruje tę opcję.

P11.9.

Podaj identyfikatory wszystkich pracowników posortowane rosnąco według nazw działów w języku angielskim i  malejąco według nazwisk w języku węgierskim:

Prac order by (angielski(PracujeW.Dział.Nazwa), DESC( węgierski(Nazwisko)))


1.5. Zapytania zakresowe

Tego rodzaju zapytania są konsekwencją tego, że zapytania mogą zwrócić sekwencje. Oznacza to, że powinna istnieć możliwość wyboru i-tego elementu sekwencji, ostatniego elementu sekwencji itd. W najprostszym przypadku można zastosować następującą składnię:

zapytanie ::= zapytanie [liczba naturalna]
zapytanie ::= zapytanie [liczba naturalna .. liczba naturalna]
P11.9.

Podaj 50-ciu najmniej zarabiających pracowników:
(Prac order by Zar)[1..50]

Zwrócimy uwagę, że w powyższym zapytaniu pierwszy element otrzymuje numer 1. Język C i jego pochodne (C++, Java), a także CORBA, OQL itd. wprowadzają inną metodę numeracji, w której pierwszy element oznacza się numerem 0, drugi - numerem 1 itd. W C było to umotywowane zgodnością indeksów tablic z arytmetyką pointerową. Ten komputerowy atawizm jest kontynuowany w języku ODMG OQL, mimo że uzasadnienie dla niego znikło. Programiści do tej numeracji się przyzwyczaili, niemniej odstępstwo od powszechnie przyjętego sposobu numeracji elementów nie wydaje się właściwe dla języków zapytań, dla których arytmetyka pointerowa nie ma znaczenia. Jesteśmy zdania, że numerowanie elementów poczynając od 0 jest także błędogenne.

Może być potrzebna jest bardziej uniwersalna opcja umożliwiająca określenie zakresu poprzez zapytanie. Można w związku z tym przyjąć bardziej uniwersalną składnię (zapytania w nawiasach kwadratowych muszą zwrócić liczbę naturalną):

zapytanie ::= zapytanie [zapytanie]
zapytanie ::= zapytanie [zapytanie .. zapytanie]
P11.9.

(Prac order by Zar)[x..y]

Jeszcze inną opcją jest rozwiązanie przyjęte w systemie Loqis, gdzie założono specjalny tryb powoływania pomocniczej nazwy:

zapytanie ::= zapytanie number as nazwa

Niech zapytanie ma postać q number as n. Semantyka tej opcji przypomina operator as. Oznacza, że jeżeli q zwraca sequence{r1, r2, r3, ...}, to q number as n zwraca

sequence{ struct{r1, n(1)}, struct{r2, n(2)}, struct{r3, n(3)}, ...}

Jak widać, wynik jest dodatkowo wyposażony w binder o nazwie n przechowujący kolejną liczbę naturalną, To umożliwia dowolne warunki na tej liczbie, np.:

P11.10.

Podaj pracowników, którzy w rankingu zarobków zajmują miejsca od 25 do 50:

((Prac order by Zar) number by r) where r > 25 and r < 50

Jest oczywiście możliwa dowolna kombinacja tej opcji z innymi opcjami języka zapytań, np. wyliczenie podanych wyżej liczb 25 i 50 przez podzapytania. Podane rozwiązanie, wraz z innymi własnościami SBQL, wydaje się najbardziej uniwersalne.

Należy zwrócić uwagę, że obecność sekwencji w strukturach danych i operacje na sekwencjach w języku zapytań znacznie obniżają potencjał dla optymalizacji zapytań. W większości metod optymalizacyjnych, w tym w metodach opartych na przepisywaniu (rewriting) i metodach opartych na indeksach, zakłada się dowolny porządek elementów zwracanych przez zapytanie. Jeżeli ten porządek jest wymuszony, to praktycznie nie pozostaje nic innego prócz sekwencyjnego przetwarzania element po elemencie.

Pewnym problemem semantycznym jest zachowywanie porządku określonego przez sekwencję przez inne operatory. Dla niektórych operatorów zachowywanie porządku jest naturalne. Np. operator where działający na sekwencji nie musi zmieniać kolejności wynikowych elementów, ale w takim przypadku nie może on być objęty optymalizacją np. poprzez indeksy. Dla innych operatorów porządek ten nie musi być ustalony. Np. dla operatora kropki w zapytaniu:

P11.11.

(Prac order by Wiek) . (Nazwisko, Zarobek)

wynikowa lista struktur powinna pozostawić porządek ustalony przez order by w poprzednim podzapytaniu; programista byłby prawdopodobnie zaskoczony, gdyby ten porządek nie był utrzymany przez ten operator. Ta własność nie jest jednak oczywista w przypadku zapytania:

P11.12.

(Prac order by Wiek) . Stan

gdyż Stan jest atrybutem wielowartościowym, w którym porządek nie obowiązuje. W tej sytuacji należałoby przyjąć, że wynikowa lista identyfikatorów stanowisk pozostaje nieuporządkowana (operator order by jest ignorowany). Generalnie, dla dowolnego operatora (algebraicznego lub niealgebraicznego) działającego na sekwencjach i bagach należałoby przyjąć jednoznaczną regułę dotyczącą typu kolekcji zwracanego wyniku oraz porządku elementów, o ile zwracana jest sekwencja.

Copyrights © 2006 PJWSTK
Materiały zostały opracowane w PJWSTK w projekcie współfinansowanym ze środków EFS.