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
  Wstęp
  1. Rozszerzenie SBQL w modelu M1
  2. Rozszerzenie SBQL w modelu M2
  Podsumowanie
  Zadania
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ń

 

1. Rozszerzenie SBQL w modelu M1

Dotychczasowe definicje operatorów języka SBQL nie uwzględniają pojęć klasy i dziedziczenia. Pokażemy, w jaki sposób można je łatwo rozszerzyć na powyższe własności. W następnych podrozdziałach omówimy SBQL dla modeli składu M1 i M2. Konsekwencje pojęcia hermetyzacji dla SBQL (określonego modelem M3) musimy odłożyć na nieco później, kiedy będziemy omawiać zanurzenie zapytań w zdania imperatywne i abstrakcje programistyczne, takie jak procedury i metody, ponieważ pojęcie hermetyzacji daje się wykorzystać dopiero wtedy, gdy definiowany język obejmuje metody.

Model składu M1 wprowadza pojęcie klasy jako specjalnej struktury danych przechowywanej w ramach składu obiektów. Klasy przechowują inwarianty obiektów. Istotnym inwariantem przechowywanym w ramach klasy jest nazwa obiektów tej klasy. Klasy i obiekty są połączone związkami dziedziczenia.

Model M1 powoduje większą złożoność wprowadzanych przez nas definicji. Jak zobaczymy, z tego punktu widzenia model M2 jest bardziej korzystny, ale też mniej popularny niż M1. Powodem zwiększonej złożoności definicji dla modelu M1 jest to, że jest on przede wszystkim podstawą języków i systemów obiektowych zakładających wczesne (statyczne) wiązanie, tj. wiązanie w czasie analizy składniowej i kompilacji. Często w takiej sytuacji klasa jest bytem drugiej kategorii programistycznej, tj. nie jest istotna w czasie wykonania programu; jest własnością źródłowego tekstu programu, a nie jego wykonywalnego kodu. Ta własność zwykle komplikuje rozważania semantyczne. W naszym podejściu model M1 został przystosowany do koncepcji, w której wiązanie jest późne (dynamiczne). Dodatkowo, w klasycznych modelach języków programowania nazwy obiektów nie są inwariantami klas; np. w C++ i Java dla danej klasy można powołać obiekt o dowolnej nazwie. Te okoliczności powodują, że semantyka języków opartych na modelu M1 wykazuje anomalie; dotyczy to nie tylko języków zapytań, ale również języków programowania (np. anomalie związane z wielokrotnym dziedziczeniem).

Aby przystosować model M1 dla potrzeb rozwijanej przez nas semantyki języków zapytań, należy zmodyfikować regułę wiązania nazw. Chodzi o zachowanie zasady zamienialności (substitutability), która mówi, że obiekt klasy podrzędnej jest jednocześnie obiektem klasy nadrzędnej. Przykładowo, obiekt Prac jest jednocześnie obiektem Osoba. Informacja o tej zależności jest przechowywana w modelu M1 w dwóch miejscach, Rys.28 i Rys.29. Pierwszym z nich są klasy, które przechowują nazwy należących do nich obiektów. Drugim miejscem przechowywania tej informacji są związki dziedziczenia zaznaczone na Rys.28 jako relacje KKOK.

W terminach operacji na stosie zmieniona reguła wiązania oznacza, że o ile w pewnej sekcji stosu znajduje się binder o nazwie Prac, zaś wiązana jest nazwa Osoba, to binder ten uczestniczy w procesie wiązania tak samo, jakby był to binder o nazwie Osoba. Alternatywnie możemy uważać, że w danej sekcji stosu środowiskowego wraz z binderem Prac(v) pojawia się w tej samej sekcji binder Osoba(v). Ta zasada powinna być uogólniona na dowolną liczbę poziomów hierarchii dziedziczenia oraz na wielokrotne dziedziczenie.

Klasy wprowadzają nowe zasady otwierania i usuwania sekcji na stosie środowisk. Jeżeli operator niealgebraiczny przetwarza obiekt posiadający identyfikator i, to na wierzchołek stosu środowisk wkładane są, jak poprzednio, bindery określone przez nested(i). Oprócz tego, dla umożliwienia wiązania własności przechowywanych w ramach klas, poniżej wierzchołka stosu są ulokowane sekcje z binderami do własności klas tego obiektu w odpowiedniej kolejności, Rys.57. Po zakończeniu przetwarzania wszystkie te sekcje są usuwane ze stosu.

Zwróćmy uwagę, że podana koncepcja automatycznie uwzględnia własność przesłaniania (overriding). Jeżeli np. klasa K1 zawiera pewną metodę m, która przesłania metodę m zawartą w klasie K2, to zgodnie z przedstawioną kolejnością przeszukiwania stosu przy wiązaniu nazwy m związana zostanie metoda m z klasy K1; metoda m z klasy K2 będzie niewidoczna.

57
Rys.57. ENVS przy przetwarzaniu obiektu O, członka klas K1, K2, K3,...

Rys.57 przedstawia wizję stanu stosu od strony koncepcji semantyki języka zapytań. Wizja ta może być bezpośrednio zaimplementowana, ale jest ona dość rozrzutna, w związku z czym w staranniejszej implementacji i po zabiegach optymalizacyjnych organizacja tego stosu oraz operacje na tym stosie mogą wyglądać zupełnie inaczej. W tym wykładzie nie będziemy jednak zajmować się zbyt szczegółowo zagadnieniami implementacyjnymi.

Rys.58 ilustruje tę sytuację dla przypadku, gdy operator niealgebraiczny, np. where w zapytaniu:

P10.1.

Prac where Wiek > avg(Prac.Wiek)

przetwarza obiekt Nowaka dla bazy danych przedstawionej na Rys.28 i Rys.29.

Sekcja binderów do obiektów bazy danych zawiera bindery do obiektów i4 oraz i9 opatrzone zarówno nazwą Prac, jak i nazwą Osoba. Jest to jeden z wariantów uwzględnienia omawianej wcześniej zasady zamienialności. Dodatkowe bindery Osoba pojawiają się na podstawie nazw obiektów będących inwariantami klas oraz związku KK (patrz Rys.28).

58
Rys.58. Przykładowy stan stosu środowisk w modelu M1

Zwykle w różnych językach obiektowych zakłada się, że jeżeli wiązana jest nazwa Osoba, to kontrola typologiczna ograniczy możliwość użycia własności obiektu Prac nie będących własnościami obiektów Osoba. Dla języków pozbawionych mocnej kontroli typów nazwy OsobaPrac w takim podejściu są traktowane de facto jako synonimy, co zdaniem niektórych autorów może prowadzić do anomalii, np. wiążąc nazwę Osoba mamy jednocześnie dostęp do takich własności, jak ZarZarNetto. Powstaje pytanie, czy jest to sprzeczne z jakimiś wypracowanymi zasadami obiektowości. Jak się okazuje z przykładów, pozbawienie możliwości dostępu do niektórych atrybutów obiektu Prac z tego powodu, że dostaliśmy się do niego poprzez nazwę Osoba, jest niewygodne i powoduje znaczne skomplikowanie niektórych zapytań. Jakkolwiek systemy bez kontroli typów są z kilku punktów widzenia niekorzystne i przez to niezbyt dla nas interesujące, przyjmiemy jednak, że muszą istnieć środki językowe pozwalające programiście na stwierdzenie, z jakim obiektem ma do czynienia (Osoba czy Prac) oraz odwołanie się do atrybutów, które zostały sztucznie "ukryte" ze względu na kontrolę typologiczną. Można to rozwiązać na kilka sposobów. Najprostszy polega na tym, że funkcja nested zwraca bindery do wszystkich własności obiektu, niezależnie od tego, w jaki sposób referencja do tego obiektu została odzyskana, zaś programista ma środki, aby ustalić w programie typ, klasę lub nazwę obiektu. Np. można wprowadzić funkcję objectName(i), która dla zadanego identyfikatora obiektu i (ustalonego poprzez zapytanie) zwróci nazwę tego obiektu w postaci stringu.

Podaną wyżej dyskusję można też potraktować jako zarzut pod adresem modelu M1 i anomalii semantycznych, które on powoduje. Anomalie te radykalnie usuwa model M2.


1.1. Wiązanie i wywoływanie metod w modelu M1

Dotychczas przyjmowaliśmy, że wiązanie polega wyłącznie na tym, że nazwę występującą w zapytaniu zamienia się np. na referencję obiektu na podstawie bindera wyszukanego na stosie ENVS. Dla metod ta zasada musi być rozszerzona. Jeżeli wiązana nazwa jest nazwą metody, to:

  • Następuje wiązanie jej nazwy jak zwykle na stosie ENVS;

  • Po związaniu metoda jest wywoływana;

  • Wywołanie metody powoduje utworzenie nowej sekcji na stosie ENVS, tzw. zapisu aktywacji, zawierającego bindery do lokalnego środowiska metody, tj. jej parametrów i lokalnych obiektów, następnie wejście sterowania w kod metody.

  • Zapis aktywacji zawiera także ślad (adres) powrotu z metody, który jest wykorzystywany w momencie, gdy metoda zakończy działanie.

  • Aktualne parametry metody są pobierane ze stosu rezultatów QRES i następnie wstawiane do lokalnego środowiska.


Niech w klasie K będzie umieszczona metoda met posiadająca parametry p1 typu T1p2 typu T2. Metoda met posiada lokalne środowisko w postaci dwóch obiektów x1 typu T11x2 typu T12. Metoda met zwraca wynik typu T:

P10.2.

procedure met(p1: T1, p2: T2 ): T  {
      x1: T11, x2: T12;
      ....
};

Niech ta metoda będzie wywoływana w zapytaniu:

P10.3.

q q ...met(q1, q2) ...

w kontekście operatora niealgebraicznego q; q, q1, q2 są podzapytaniami.

59
Rys.59. Stany stosów ENVS i QRES podczas przetwarzania metody

Niech eval(q) zwróci bag{ r1, r2, ....}, gdzie r1, r2, .... są referencjami do obiektów będących członkami klasy K. Rys.59 przedstawia kroki przetwarzania dla r1. Górna część rysunku przedstawia stany ENVS, dolna - stany QRES. Najpierw ewaluowane jest q; w wyniku powstaje nowa sekcja na QRES. Mechanizm następnie wchodzi w pętlę iteracjyjną po r1, r2, .... W każdym obrocie tej pętli następuje włożenie na ENVS binderów do publicznych własności klasy K oraz binderów do wnętrza aktualnie przetwarzanego obiektu (rysunek przedstawia przetwarzanie dla obiektu r1). W tym środowisku następuje wiązanie nazwy met (wśród publicznych własności klasy K), ewaluacja parametrów metody oraz wywołanie metody. W wyniku wywołania na stos ENVS wkłada się sekcję z binderami do prywatnych własności klasy K oraz rekord aktywacyjny metody met, składający się z binderów zawierających obliczone parametry oraz binderów do lokalnych obiektów x1x2. Podczas ewaluacji sekcje inne niż wymienione oraz inne niż sekcje globalne powinny być przesłonięte (czarny prostokąt na ENVS) ze względu na reguły zakresu (będą omówione później). Po zakończeniu działania metody sterowanie wraca do przetwarzania zapytania; sekcje lokalne metody zostają usunięte ze stosu ENVS, rezultat metody jest ulokowany na wierzchołku QRES. Zwrócimy uwagę, że ciało metody ma dostęp do aktualnie przetwarzanego obiektu poprzez sekcję zawierającą nested(ri). Wynika stąd, że wewnątrz tego ciała programista może bezpośrednio używać nazw podobiektów tego obiektu. W niektórych językach identyfikacja aktualnie przetwarzanego obiektu odbywa się poprzez specjalne słowo kluczowe, np. self lub this. Przyjęcie tego założenia ma minimalne konsekwencje dla objaśnionego wyżej mechanizmu. Oznacza wyłącznie to, że powyżej sekcji zawierającej bindery obliczone poprzez nested(ri) będzie także sekcja (skojarzona z wywołaniem metody met) zawierająca pojedynczy binder o postaci self(ri). Traktujemy w tym przypadku self jako pomocniczą nazwę identyfikującą dany obiekt, podobnie jak w zapytaniu q as self.

Niekiedy może nam zależeć na pobraniu identyfikatora metody, a nie na jej wywołaniu, np. w celu przekazania metody jako parametru. W tym celu potrzebna jest specjalna składnia, np. ref Wiek. Podsumowując:

Zmiany semantyczne przetwarzania zapytań w modelu M1 są następujące:

Zmiany w globalnych sekcjach binderów (m.in. do bazy danych): dowolny binder n(i) wynikający ze zbioru R identyfikatorów startowych jest uzupełniany poprzez bindery n1(i), n2(i), ... , gdzie n1, n2,... są nazwami ustalonymi jako inwarianty klas nadrzędnych w stosunku do klasy, do której należy obiekt i.

Jeżeli operator niealgebraiczny przetwarza obiekt z identyfikatorem i należący do klasy K1, która ma kolejne nadklasy K2, K3, ..., wówczas na wierzchołek stosu środowiskowego wkłada się po kolei, poczynając od wierzchołka: nested(i), bindery do własności K1, bindery do własności K2, bindery do własności K3 itd.

Jeżeli wiązana jest metoda, wówczas jest ona automatycznie wywoływana. Wywoływana metoda widzi swoje lokalne środowisko, środowisko klasy, do której należy, oraz środowisko wnętrza obiektu, na którym działa.


1.2. Wielokrotne dziedziczenie

Jeżeli pewna klasa dziedziczy z większej liczby klas, to na stosie pojawią się sekcje klas nadrzędnych w pewnej (niekiedy dowolnej) kolejności. Możliwe są dwa przypadki:

  • Nie występuje konflikt nazw pomiędzy własnościami dziedziczonymi z poszczególnych klas. W tym przypadku kolejność klas na stosie powinna uwzględniać hierarchię klas, ale kolejność klas na tym samym poziomie hierarchii nie ma znaczenia. 

  • Jeżeli występuje konflikt pomiędzy własnościami dziedziczonymi z poszczególnych klas, to nie istnieje dobry porządek ustawienia klas na stosie. Każdy porządek łamie zasadę zamienialności (powodując znane anomalie wielodziedziczenia). Przykładowo, na Rys.60 metoda m z klasy K3 będzie przesłaniać metodę m z klasy K4, mimo, że programista piszący K3 nie miał takiej intencji. Oznacza to, że obiekt O klasy K1 nie może być użyty jako obiekt klas K2 i K4, co łamie zasadę zamienialności. Jest to sytuacja kwalifikowana jako konflikt. Tego rodzaju konflikty są inherentną wadą modelu M1 (która jest wyeliminowana w modelu M2). Niektórzy autorzy proponują w takiej sytuacji "chwilową" zmianę nazwy metody m z klasy K4 na inną, nie powodującą konfliktów. W ten sposób ta sama metoda w tym samym programie wystąpi pod różnymi nazwami, co jest błędogenne i będzie utrudniać pielęgnację programu.

60
Rys.60. Konflikt nazw przy wielodziedziczeniu

Podane wady wielokrotnego dziedziczenia są nieuchronne dla modelu M1 i nie dadzą się usunąć w jakikolwiek sposób. Wynikają one z faktu zmieszania w jednym środowisku własności różnych klas, często niekompatybilnych. Jest to przyczyna tego, że w niektórych językach i systemach zrezygnowano z wielokrotnego dziedziczenia. Jednakże nie usuwa to problemu, ponieważ w ten sposób zwiększa się dystans pomiędzy modelowaniem pojęciowym (dla którego wielokrotne dziedziczenie jest naturalne) a modelem implementacyjnym. Jest to niekorzystne zarówno z punktu widzenia efektywności programowania, czytelności programu, jak i jego pielęgnacyjności. Brak wielokrotnego dziedziczenia ogranicza zasadę obiektowości znaną jako "zasada otwarte-zamknięte" (open-close principle). Zasada ta mówi, że klasy na pewnym etapie powinny być zamknięte dla modyfikacji, ale otwarte dla rozszerzeń poprzez możliwość utworzenia ich specjalizacji. Zasadę tę również łamie zakaz umieszczania w klasach nadrzędnych własności o tych samych nazwach. Brak wielokrotnego dziedziczenia ogranicza możliwość tworzenia specjalizacji klas. Zasada otwarte-zamknięte jest uważana za podstawową z powodu możliwości ponownego użycia (reuse).

Model M1 jest stosowany w większości języków i systemów obiektowych (z różnymi mutacjami i pod różnymi nazwami). Niezależnie od tego, czy zezwala on na wielodziedziczenie (C++, OMG CORBA, standard ODMG, standard SQL-99) czy też nie (Smalltalk, Java), zawsze pojawią się w nim pewne wady bądź w zakresie modelowania pojęciowego, bądź też w postaci anomalii technicznych tworzących rafy dla programistów. Radykalnym sposobem usunięcia tych wad jest przyjęcie modelu M2 (i modeli pochodnych), zakładających koncepcję dynamicznych ról obiektów.


1.3. Przykłady zapytań w modelu M1

61
Rys.61. Schemat obiektowej bazy danych

Rys.61 przedstawia schemat obiektowej bazy danych zapisany w modyfikowanym UML, w którym liczności są podane nie tylko dla asocjacji, lecz dla dowolnych obiektów. Asocjacje PracujeW/Zatrudnia oraz Kieruje/Szef są zrealizowane jako bliźniacze obiekty pointerowe przechowywane wewnątrz odpowiednich obiektów. Atrybut Zar może nie wystąpić, atrybuty Stan i Lokacja mogą wystąpić dowolną liczbę razy, poczynając od 1.

P10.4.

Podaj nazwę działu i średni wiek jego pracowników (dziedziczenie metody Wiek przez klasę Prac):

Dział . ( Nazwa, avg(Zatrudnia.Prac.Wiek()) as Średnia)


P10.5.

Podaj nazwiska, zarobek netto i nazwisko szefa dla programistów pracujących w Radomiu (dziedziczenie atrybutu Nazwisko przez klasę Prac):

(Dział where $Lokacja as x (x = "Radom" )) join
(Zatrudnia.Prac where "programista" Î Stan ).
(Nazwisko, ZarNetto() as netto, (Szef.Prac.Nazwisko) as boss)


P10.6.

Dla każdego pracownika podaj nazwisko oraz procent budżetu przeznaczony na jego uposażenie.


a) nie uwzględniamy informacji, że Zar jest opcyjne:

Prac
. (Nazwisko as NazwiskoPrac,
(Zar * 12 * 100 / (PracujeW.Dział.BudżetRoczny())) as PrcBudż)


b) uwzględniamy informację że Zar jest opcyjne; obiekty Prac nie posiadające atrybutu Zar są pomijane:

Prac. (Nazwisko as NazwiskoPrac, (Zar as z).
((z * 12 * 100 / (PracujeW.Dział.BudżetRoczny())) as PrcBudż))


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