Kazimierz Subieta. Teoria i konstrukcja obiektowych języków zapytań. Wydawnictwo PJWSTK, Warszawa 2004, ISBN 83-89244-29-2 (522 stron)

 

Wprowadzenie

 

 

Języki zapytań (query languages) są przyjaznymi dla użytkowników interfejsami do bazy danych, umożliwiającymi jej przeszukiwanie według dowolnie wybranych kryteriów i dowolnie określanego wyniku wyszukiwania. Najbardziej popularnym językiem zapytań jest SQL. Jest on uważany za istotny czynnik komercyjnego sukcesu relacyjnych baz danych. SQL jest przedmiotem kilku standardów, w szczególności SQL-86, SQL-89, SQL-92 (znany również jako SQL2) [Melt93] i SQL-99 [Melt99, Melt01] (znany również jako SQL3). Stał się on podstawą wielu interfejsów służących do programowania aplikacji, takich jak ODBC i JDBC. SQL podlegał licznym rozszerzeniom, m.in. poprzez konstrukcje zmieniające bazę danych (update, insert, delete), w kierunku języków programowania, perspektyw (views), procedur zapamiętanych w bazie danych (stored procedures) oraz wyzwalaczy (triggers).

Wraz z językami zapytań pojawiły się różnorodne teorie, takie jak algebra relacji, rachunek relacyjny i odmiany logiki matematycznej. Teorie języków zapytań są istotne z kilku względów, w szczególności ustalają ich bazę koncepcyjną, semantyczną i dydaktyczną, oraz zasadniczo wspomagają opracowanie metod optymalizacyjnych. Pojawiło się także wiele metod empirycznych, w szczególności dotyczących optymalizacji zapytań. Istnieją jednak kontrowersje co do roli i przydatności teorii i metod związanych z modelem relacyjnym. W szczególności, algebra relacji i rachunek relacyjny przykrywają co najwyżej kilka procent konstrukcji SQL i nie są z nim do końca spójne, zaś metody optymalizacyjne są zbytnio przywiązane do relacyjnego modelu danych (którego czas minął) i do fizycznych własności systemów, mają ograniczony zakres stosowalności oraz mają luki i niejasności koncepcyjne.

Pojawienie się obiektowych  [Atki89, ODMG00, Clue98] (object-oriented) i obiektowo-relacyjnych (object-relational) baz danych [Kim95a, Ston90b]  stworzyło w tej dziedzinie nową jakość. Dotyczy to także technologii internetowych opartych na standardzie XML [XML04, XQue04, Cham01, Abit97c]. Nowe modele danych, standardy, rozwiązania praktyczne, metody i teorie spowodowały stan, który można określić jako totalny chaos: brak spójnych, jednorodnych podstaw teoretycznych i przypadkowość rozwiązań praktycznych. Dominują w tym względzie rozliczne rozszerzania operatorów obecnych w SQL oraz rozszerzania i modyfikacje teorii, takich jak algebra relacji, rachunek relacyjny i innych. Świadectwem tego chaosu są wypracowane przez ogromne konsorcja i instytucje przemysłowe standardy SQL-99 i ODMG OQL, które wielu specjalistów uważa za nieimplementowalne w obecnym kształcie z powodu zasadniczych wad ich specyfikacji.

Książka prezentuje spójne podejście do teorii i konstrukcji języków zapytań. Jest ona próbą uporządkowania chaosu na gruncie jednolitej teorii określanej jako podejście stosowe (stack-based approach, SBA). Podstawą tego podejścia jest założenie, że języki zapytań są odmianą języków programowania, zatem powinno się do nich stosować pojęcia, koncepcje i metody znane i skuteczne w tych językach. Głównym pojęciem semantyki i implementacji większości języków programowania jest stos środowisk (environment stack, environmental stack). Jest on podstawą mechanizmu określania zakresu nazw, wiązania nazw, wywoływania procedur (włączając wołania rekurencyjne), komunikowania parametrów oraz realizacji pojęć obiektowości, takich jak hermetyzacja, dziedziczenie i polimorfizm. Istotą podejścia stosowego do języków zapytań jest wykorzystanie mechanizmu stosu środowiskowego do definiowania i implementacji operatorów charakterystycznych dla języków zapytań, takich jak operatory selekcji, projekcji, nawigacji i złączenia.

Podejście stosowe umożliwiło stworzenie spójnej teorii niezależnej od specyficznego modelu danych. Można ją stosować dla relacyjnych, hierarchicznych, obiektowych i obiektowo-relacyjnych baz danych oraz dla repozytoriów XML. Dla dowolnego z tych modeli podejście stosowe umożliwia stworzenie
i szybkie zaimplementowanie bardzo mocnego języka zapytań dla praktycznie dowolnie wybranego celu. Dzięki temu podejście to ucina dość jałowe dyskusje odnośnie do tego, który model danych sprzyja lub nie sprzyja realizacji języka zapytań i który ma „zdrowe podstawy matematyczne”, a który ich „nie ma”. Podejście stosowe do pewnego stopnia unifikuje i klasyfikuje modele danych, redukując w ten sposób niesławny syndrom „jeszcze jednego modelu obiektowego”. Syndrom ten polega na uporczywym proponowaniu kolejnych obiektowych modeli danych, których celem jest zredukowanie drobnych wad i braków poprzednich modeli. W istocie ten ciąg poprawek i mutacji nie ma końca.

Podejście stosowe jest konkurencją dla teorii znanych z modelu relacyjnego, takich jak algebra relacyjna, rachunek relacyjny i logika matematyczna. Popularne podejścia do obiektowych języków zapytań są oparte na rozszerzeniach i modyfikacjach tych teorii w postaci tzw. „algebr obiektowych” oraz specjalnych logik i rachunków. Podejście stosowe eksponuje braki i wady tych teorii, pokazując ich ograniczenia i nieadekwatność do problemu. Zdaniem autora, brak spójnej, całościowej i uniwersalnej teorii języków zapytań podczas tworzenia standardów ODMG i SQL-99 jest podstawową przyczyną wad ich koncepcji i konstrukcji. W efekcie standardy te - produkty najbardziej renomowanych firm i ciał informatyki przemysłowej - są intelektualnymi i technicznymi bublami nie nadającymi się do dydaktyki i do efektywnej całościowej implementacji.  Jak się okazało, dwóch zdolnych studentów znających podejście stosowe potrafi zaprojektować i zaimplementować w ciągu roku lepszy i mocniejszy język zapytań niż konsorcja specjalistów z renomowanych firm zachodnich.

Oparcie semantyki języków zapytań na mechanizmie stosu środowisk umożliwia precyzyjne wyjaśnienie ich własności i związków z pojęciami obiektowości, takimi jak klasy, dziedziczenie, hermetyzacja itd. W odróżnieniu od wcześniejszych „algebr” i „rachunków” podejście stosowe przyjmuje punkt widzenia imperatywnych języków programowania, zatem nie prowadzi do jakichkolwiek ograniczeń koncepcyjnych w zakresie operacji aktualizacyjnych działających na bazie danych. Nie ogranicza się zresztą do bazy danych: zapytania mogą jednocześnie działać na trwałych obiektach bazy danych oraz na nietrwałych obiektach danej aplikacji. Zapytania są podstawą definicji konstrukcji imperatywnych, takich jak operator podstawienia (update w SQL), wstawiania (insert), usuwania (delete) i innych.

Zapytania są także podstawą abstrakcji programistycznych takich jak procedury, metody i funkcje (procedury funkcyjne). Te ostatnie są tradycyjnie nazywane w dziedzinie baz danych „perspektywami” lub „widokami” (views). Znane z SQL perspektywy są procedurami funkcyjnymi, których ciało składa się z pojedynczego zapytania, w związku z czym ich uniwersalność jest ograniczona. Podejście stosowe nie zmusza do tego rodzaju ograniczeń: dowolne procedury, w tym perspektywy, mogą mieć pełną moc algorytmiczną. Dzięki mechanizmowi stosu środowiskowego wszystkie procedury, metody i funkcje/perspektywy mogą być rekurencyjne oraz mogą mieć parametry będące zapytaniami. W podejściu stosowym można bez trudu wyjaśnić mechanizmy komunikacji parametrów, znane jako call-by-value, call-by-reference i inne, w odniesieniu do parametrów będących zapytaniami.

Perspektywy[1] w bazach danych są odrębnym, bardzo ważnym tematem. Perspektywy są definiowane poprzez język zapytań i mogą być używane (wywoływane) w zapytaniach. Umożliwiają przystosowanie schematu bazy danych do konkretnych wymagań użytkownika, ograniczają dostęp do danych oraz mogą stanowić podstawę integracji rozproszonych, heterogenicznych baz danych. Istnieją trzy poważne problemy związane z perspektywami:

Podejście stosowe wprowadza całkowicie nową jakość w kontekście trzech wymienionych problemów, umożliwiając nowe podejście do ich efektywnego rozwiązania dla ogólnego przypadku.

Niemniej ważnym tematem związanym z językami zapytań jest doprowadzenie do sytuacji, gdy czas wykonania zapytań jest akceptowalny dla użytkowników. Bezpośrednia implementacja interpretera zapytań w sytuacji, gdy bazy danych zawierają miliony danych, prowadzi często do nieakceptowalnego czasu wykonania. Radykalne skrócenie tego czasu, zwane optymalizacją, staje się więc koniecznością, zaś język zapytań, który nie jest wspomagany przez optymalizację, nie ma szans na akceptację ze strony klientów baz danych. Metodom optymalizacji zapytań poświęcono wiele uwagi w systemach relacyjnych. Niestety, większość z nich z trudem przenosi się na inne modele, w szczególności obiektowe, ze względu na przywiązanie tych metod do cech modelu relacyjnego oraz do fizycznej reprezentacji danych wewnątrz tych systemów.

Optymalizacja zapytań jest zasadniczym katalizatorem rozwoju teorii języków zapytań. Optymalizacja najczęściej polega na tym, że zapytanie q1 jest automatycznie zamieniane na semantycznie równoważne zapytanie q2, które rokuje znacznie lepszy czas wykonania[2]. Teoria jest niezbędna do tego, aby odpowiedzieć na pytanie: co to znaczy „semantycznie równoważne”? W tym względzie inżynierska intuicja nie wspomagana teorią jest zbyt zawodna i nie jest
w stanie opanować zależności semantycznych powstających dla złożonych zapytań. Konieczna staje się uniwersalna, prosta i konsekwentna teoria, wyjaśniająca najdrobniejsze detale semantyczne języka zapytań. W zakresie teorii języków zapytań obowiązuje zasada, którą sformułujemy za pomocą oksymoronu:

Każdy, nawet najdrobniejszy problem semantyczny, jest ogromnym problemem.

Niespełnienie tej zasady oznacza luki lub nieścisłości semantyczne, które mogą uniemożliwić udzielenie jednoznacznej odpowiedzi, że zapytanie q1 jest semantycznie równoważne zapytaniu q2; zatem kwestia optymalizacji zapytań staje się problematyczna. Większość znanych teoretycznych podejść do języków zapytań zaniedbuje powyższą zasadę. Przykładowo, w klasycznej algebrze relacji nie da się wyjaśnić operatora naturalnego złączenia (natural join), semantyki pomocniczych nazw występujących w SQL, semantyki banalnego operatora +, semantyki operatorów grupowania, sortowania i eliminowania duplikatów itd. Nie przeszkadza to umieszczaniu algebry relacji jako podstawowego formalizmu służącego do opisu semantyki języków zapytań w licznych podręcznikach i mocno naciąganym tezom, że stanowi ona podstawę optymalizacji zapytań. Istotnie, niektóre zabiegi optymalizacyjne można zilustrować w tej algebrze, ale jest to tylko ilustracja, która musi być efektywnie zrealizowana dla konkretnego języka, np. SQL. Znakomita większość optymalizacji znanych z SQL jest w tej algebrze niewyrażalna.

W podejściu stosowym staramy się spełnić powyższą zasadę w 100%. W tym względzie podejście stosowe odcina się od algebry relacji i tzw. „obiektowych algebr”[3], pozwalając na opracowanie nowych, bardzo mocnych metod optymalizacyjnych, z których część jest uogólnieniem metod znanych z systemów relacyjnych, zaś część nie ma precedensów w historii baz danych.

W książce zostaną wyjaśnione założenia i semantyka języka zapytań SBQL (Stack Based Query Language) opartego na podejściu stosowym. SBQL jest pewną idealizacją opartą na abstrakcyjnej składni, pokazującą istotę semantyki operatorów wprowadzonych w większości języków zapytań. W tym sensie pełni tę samą rolę, którą w relacyjnych językach zapytań pełni algebra relacji i rachunek relacyjny. Zasadniczą nowością wprowadzoną w SBQL są operatory niealgebraiczne, takie jak operatory selekcji, projekcji/nawigacji, złączenia, kwantyfikatory, operator tranzytywnego domknięcia i operator porządkowania. W ogólnym przypadku, semantyka tych operatorów nie może być wyrażona w terminach algebry podobnej do algebry relacji. Jak się okazało, ich semantykę można w prosty sposób wyrazić poprzez operacje na stosie środowiskowym, przy czym pewnym zaskoczeniem jest to, że semantyka tych, wydawałoby się, bardzo różnych operatorów jest oparta na tym samym prostym mechanizmie.

Czytelnik może być nieco zaskoczony kwalifikowaniem wymienionych operatorów jako „niealgebraicznych”, ponieważ twórcy i kontynuatorzy koncepcji modelu relacyjnego przez lata przyzwyczaili nas, że operatory selekcji, projekcji i złączenia są zwyczajnymi „operatorami algebraicznymi” w algebrze relacji. Nie potrzeba wielkiej wnikliwości matematycznej, aby pokazać, że ich „algebraizacja” odbyła się kosztem niezbyt rzetelnej sztuczki formalnej, w której część semantyki została przesunięta do nieformalnego metajęzyka tej algebry. Dotyczy to nazw atrybutów, operacji, funkcji i innych elementów występujących w indeksach operatorów algebry relacji. W istocie operator, taki jak selekcja, nie jest pojedynczym operatorem: jest to nieskończona rodzina operatorów, gdzie konkretny egzemplarz jest wyznaczony poprzez indeks tego operatora należący do metajęzyka tej algebry. Przykładowo, w wyrażeniu algebry relacyjnej

σZar>1000( Prac )

występuje operator selekcji σ kwalifikowany wyrażeniem Zar > 1000. To wyrażenie nie należy do języka tej algebry; jest to wyrażenie metajęzykowe, które w istocie jest wyłącznie nieformalnym tekstowym komentarzem wstawionym na użytek danego wykładu lub objaśnienia; jest fragmentem tego tekstu, a nie opisywanego modelu formalnego. Jest to zasadnicze nieporozumienie co do charakteru tych algebr. Czasami ten indeks jest na tyle prosty, że jego semantyka jest oczywista (niemniej matematycy podkreślają, że w matematyce nic nie jest oczywiste). Często jednak indeks bywa złożonym wyrażeniem, które posiada swoją semantykę. Ta semantyka jest nieformalna i niewyrażalna w tej algebrze; indeks będący fragmentem danego tekstu może być co najwyżej nieformalnie opisany w tymże tekście.

W ten sposób uniwersum semantycznych rozważań zostało podzielone na dwa światy: świat formalny pojęć „pierwszej kategorii”, włączający nazwy relacji i operatory, takie jak selekcja, projekcja i złączenie oraz świat nieformalny pojęć „drugiej kategorii”, występujący w nieformalnych komentarzach, w tym w indeksach. Świat nieformalny włącza nazwy atrybutów, operatory takie jak =, <, >, + i inne elementy występujące w indeksach.

Ten podział semantyki na dwa światy – semantyki formalnej i semantyki nieformalnej - uznaliśmy za frustrujący, nieakceptowalny i kompletnie niepotrzebny. Twórcy formalnych podejść do semantyki języków programowania poradzili sobie z dużo bardziej złożonymi zagadnieniami. Podejście stosowe nie korzysta więc z tworów formalnych wypracowanych przez społeczność baz danych. Nie istnieje jakikolwiek temat w zakresie języków zapytań, włączając optymalizację zapytań, który wymagałby odwołania się do tych tworów. Odwrotnie, podejście stosowe znacznie precyzyjniej formułuje te właśnie pojęcia, które dotąd są przypisywane algebrze relacji, rachunkowi relacyjnemu lub logice matematycznej. Odwołania do tych tworów formalnych występują więc w tej książce wyłącznie w kontekście negatywnym: pokazujemy ich koncepcyjne słabości i braki, które są wyeliminowane przez podejście stosowe.

Podejście stosowe jest w dużym stopniu powrotem do pojęć języków programowania dobrze znanych i opracowanych ponad 30 lat temu. Wprowadzane tu pojęcia były opisane w podręcznikach kompilatorów oraz podstaw formalnych języków programowania z lat 60-tych i 70-tych, takich jak notacja i rachunek lambda, semantyka denotacyjna, maszyny abstrakcyjne i inne (prawie zapomnianych, szczególnie w społeczności baz danych). Te koncepcje przystosowaliśmy dla potrzeb nowoczesnego wykładu dotyczącego języka zapytań, wprowadzając przy tym nowe ich sformułowania oraz szereg nowych pomysłów w zakresie specyfikacji semantyki.

W naszym podejściu nie ma potrzeby wprowadzania metajęzykowych indeksów operatorów, zaś każda nazwa (obiektu, atrybutu itd.) oraz każdy operator (włączając selekcję, złączenie, <, + itd.) podlega takiemu samemu traktowaniu od strony semantyki. Dzięki temu uzyskaliśmy unikalną precyzję specyfikacji semantyki języków zapytań, która jest w stanie wyjaśnić na gruncie formalnym semantykę wszystkich konstrukcji językowych definiowanych języków zapytań. Taka precyzja i uniwersalność jest nieosiągalna w przypadku algebry relacji, rachunku relacyjnego, specjalnych logik matematycznych oraz innych podobnych tworów formalnych.

Specyfikacja semantyki SBQL jest jednocześnie abstrakcyjną implementacją. Po próbach zastosowania semantyki denotacyjnej [Subi85, Subi87a, Subi87b], w wersji maksymalnie „zhumanizowanej”, uznaliśmy, że ten sposób specyfikacji (jakkolwiek nagłośniony w literaturze teoretycznej) jest całkowicie nieczytelny dla potencjalnych implementatorów języków opartych na tym podejściu. Zdecydowaliśmy się więc na specyfikację semantyki w „zhumanizowanej” wersji semantyki operacyjnej, tj. poprzez podanie czynności, które musi wykonać pewna abstrakcyjna maszyna, aby dokonać ewaluacji zapytania. Ten sposób, po raz pierwszy opisany w [Subi95a], okazał się o tyle lepszy, że bezpośrednia implementacja języka (bez optymalizacji) stała się oczywista dla wszystkich zainteresowanych studentów i doktorantów.

W naszym podejściu zapytania będą pełnić rolę wyrażeń znanych z języków programowania. Przyjęta przez nas zasada ortogonalnej trwałości nie różnicuje sposobów dostępu do trwałych i nietrwałych danych. Wobec tego nasze zapytania będą również stosowane do nietrwałych danych. Inaczej mówiąc, przyjęliśmy, że w naszym hipotetycznym języku programowania nie będzie innych wyrażeń niż zapytania. Zapytaniami będą więc także klasyczne wyrażenia, takie jak 2+2, sin(x), A[i+1] itd. To założenie jest pewną rewolucją w odniesieniu do języków zapytań. Tradycyjnie, np. w języku SQL zapytania (zagnieżdżone w język programowania) mogły odwoływać się do zmiennych języka programowania poprzez specjalną składnię. Z powodu różnej przestrzeni nazw, nazwy zmiennych były w zapytaniach SQL poprzedzane dwukropkiem i specyficznie wiązane, tak aby zatrzeć różnicę pomiędzy wczesnym wiązaniem zmiennych a późnym wiązaniem charakterystycznym dla języka SQL.

Niemniej już w SQL pojawiły się elementy imperatywnych języków programowania w postaci klauzul update, insert, delete i innych. Znacznie dalej poszła firma Oracle wprowadzając język PL/SQL, który jest językiem programowania opartym na SQL. W tym samym kierunku poszły liczne języki określane jako języki czwartej generacji (4GL) oraz ostatni standard SQL znany jako SQL-99, który jest już specyfikacją kompletnego (jakkolwiek eklektycznego, chaotycznego i monstrualnego) języka programowania.

Podejście stosowe nie stwarza jakiejkolwiek granicy pomiędzy językiem zapytań a językiem programowania. Co więcej, jeżeli zaimplementowane są mechanizmy języka zapytań, wówczas przystosowanie ich do konstrukcji imperatywnych i abstrakcji takich jak moduły, klasy, procedury, funkcje, metody i perspektywy jest zadaniem dość oczywistym. Podejście stosowe prowadzi  również do prostych mechanizmów przekazywania parametrów do procedur (funkcji, metod), w szczególności mechanizmów znanych jako wołanie przez wartość (call-by-value) i wołanie przez referencję (call-by-reference). Z natury rzeczy, definiowane w podejściu stosowym mechanizmy umożliwiają dowolne wołania rekurencyjne procedur (funkcji, metod, perspektyw).

Przy rozpatrywaniu języków zapytań, szczególnie języków zintegrowanych z językami programowania, nie sposób pominąć kwestie mocnej kontroli typologicznej. Ostatni rozdział tej książki jest poświęcony temu zagadnieniu. Mechanizm mocnej kontroli typów chroni programistów przed ich własnymi błędami i w związku z tym jest kluczowym czynnikiem podwyższenia niezawodności oprogramowania. Istnieją szacunki pokazujące, że system kontroli typologicznej jest w stanie wykryć 80% błędów semantycznych i koncepcyjnych. Dało to podstawę do ukucia pojęcia bezpieczeństwo typologiczne (typing safety) jako podstawowej zasady języków programowania. System typów ma również ogromne znaczenie dla modelowania pojęciowego, gdyż odpowiednio dobrane nazwy typów pełnią rolę semantycznych kwalifikatorów bytów programistycznych w dziedzinie przedmiotowej. Np. typ Student przypisany do obiektu, zdradza nam jego intencję i biznesową semantykę. Języki bez typów i bez mocnej kontroli typów są uważane za niebezpieczne, prowadzące do niskiej jakości oprogramowania.

Teoria i praktyka typów jest w dużej mierze niezależna w stosunku do języków zapytań. Istnieją jednak cechy języka zapytań, które wprowadzają nowe problemy i konieczność nowych rozwiązań. Klasyczne systemy typologiczne, znane z popularnych języków programowania, nie uwzględniają wielu własności języków zapytań, takich jak kolekcje, automatyczne koercje, nieregularności w danych, specyficzne własności obiektowe i inne. Co więcej, uważamy, że popularne teorie typów (szczególnie te, które powstały w kontekście języków funkcjonalnych) są nieadekwatne do problemu praktycznego. Z tego względu zaproponowaliśmy tu oryginalne podejście do problemu mocnej kontroli typologicznej, które bezpośrednio nawiązuje do pojęć podejścia stosowego.


Last modified: December 30, 2005


[1] Będziemy zajmować się perspektywami wirtualnymi, czyli takimi, które istnieją wyłącznie w postaci definicji. Zmaterializowane perspektywy (materialized views) stanowią odrębny temat, który nie będzie tutaj poruszany.

[2] Ta zamiana q1 na q2 odbywa się zwykle na wewnętrznej reprezentacji zapytań.

[3] Motywem powstania obiektowych algebr była optymalizacja zapytań. Niestety,  wszystkie znane nam algebry obiektowe są w istocie nieformalnymi tworami (udającymi matematykę). Wykazują także zasadnicze wady koncepcyjne, co przekreśla ich znaczenie; patrz [Subi95b].