Tranzytywne domknięcia i równania stałopunktowe
- Tranzytywne domknięcie w SBQL
- Równania stałopunktowe w SBQL
- Związek z dedukcyjnymi bazami danych
- Optymalizacja układu równań stałopunktowych
- Podsumowanie
- Rekurencyjne lub sieciowe struktury danych
- Dla niektórych aplikacji przetwarzane struktury danych mają organizację rekurencyjną (hierarchiczną)
lub tworzą sieci z pętlami, np.:
- BOM (Bill-Of-Material), który działa na hierarchii części pewnego wyrobu (np. samochodu lub samolotu);
- Drzewa genealogiczne, zależności rodzinne;
- Zależności giełdowe (udziały spółek w innych spółkach);
- Różne typy sieci (transportowa, kolejowa, telekomunikacyjna, gazowa, wodociągowa, kanalizacyjna, kablowa,
itd.);
- Metadane, np. Interface Repository standardu CORBA
- Repozytoria konfiguracji oprogramowania;
- itd.
- Dla takich aplikacji typowe operatory z języków zapytań (selekcja, projekcja, złączenie,
kwantyfikatory)
są niewystarczające.
- Za słaba jest algebra relacji, za słaby jest standardowy SQL.
- Konieczne są specjalne operatory, m.in. tranzytywne domknięcia.
- Przykłady zapytań z tranzytywnym domknięciem
- Dla hierarchii część-podczęść:
- Jaka jest całkowita masa silnika?
- Ile nakrętek M10 wchodzi w skład jednego samochodu?
- Dla drzewa genealogicznego:
- Podaj wszystkich żyjących obecnie moich kuzynów, dowolnie odległych w drzewie genealogicznym.
- Dla sieci połączeń lotniczych:
- Podaj połączenie pomiędzy Plovdiv (Bulgaria) a Seattle (USA) o minimalnym koszcie (lub minimalnym czasie
lotu);
- Dla pliku XML:
- Podaj ścieżkę tagów prowadzących do danej z wartością "Malcolm McLaren".
- Dla tego rodzaju zapytań niektóre systemy wprowadzają specjalne (niestandardowe) rozszerzenia SQL,
np. klauzula connect by w systemie Oracle lub operator union all w systemie IBM DB2.
- Złożoność i uniwersalność zapytań jest poważnym problemem
- Pojęcie tranzytywnego domknięcia
- Pochodzi z teorii relacji lub teorii grafów. Jeżeli relacja binarna R ma postać
- R = {<a1, b1>, <a2, b2>, <a3, b3>, ...}
to tranzytywne domknięcie relacji R, zapisywane jako R*, zawiera parę <a, b>,
jeżeli istnieje dowolnie długi ciąg c1, c2, c3, ..., cn taki, że
- a = c1, b = cn i dla i = 1,2,3, ... n-1 zachodzi <ci, ci+1> należy do zbioru R.
- Innymi słowy, dwa węzły grafu skierowanego należą do tranzytywnego domknięcia, jeżeli pomiędzy nimi
jest połączenie.
-
- Ortogonalność tranzytywnego domknięcia
- Tranzytywne domknięcie musi być przystosowane do pozostałych operatorów języka zapytań i musi być
ortogonalne do tych operatorów, czyli umożliwiające dowolne kombinacje tego operatora z innymi
konstrukcjami języka.
- Naiwne potraktowanie tego operatora może wprowadzić niepotrzebne ograniczenia, uniemożliwiając
zadawanie istotnych zapytań.
- Jest to przypadek rozwiązań tego operatora znanych z systemów relacyjnych - z reguły
nieortogonalnych, przez co:
- mało uniwersalnych (nie dających możliwości zadawania wielu zapytań);
trudnych do objaśnienia dla nowicjuszy;
- trudnych do użycia;
- trudnych do optymalizacji.
- Zadaniem postawionym przy projektowaniu i realizacji języka SBQL było doprowadzenie
tego operatora do takiej uniwersalności, o ktorej można byłoby powiedzieć "więcej się nie da".
- Jednocześnie chodziło o koncepcyjną prostotę.
- Relacja będąca podstawą tranzytywnego domknięcia
- Są dwie możliwości:
- Relacja taka jest dana explicite jako zapamiętana struktura danych:
- Skończona liczba węzłów grafu,
- Wiele zadań jest nierealizowalna,
- Łatwiej optymalizowalna.
- Relację tę wylicza się "w locie" poprzez zapytanie, w miarę potrzeby, przy wyliczaniu tranzytywnego
domknięcia:
- Potencjalnie nieskończona liczba węzłów grafu,
- Znacznie większa uniwersalność,
- Mogą być trudności z optymalizacją (ale nie na pewno).
- Wiele prac teoretycznych,zakłada, że ta relacja jest zadana wyłącznie w strukturze danych,
czyli godzi się na wymienione wady.
- W drugim przypadku dla już wyliczonego elementu ci wyliczamy poprzez zapytanie kolejny
element ci+1 taki,
że <ci, ci+1> należą do tranzytywnego domknięcia tej relacji; to postępowanie kontynuujemy dla ci+1, itd.
- Istotna jest także prosta składnia i semantyka tego operatora, umożliwiająca łatwe
zrozumienie sytuacji, w których może być użyty, oraz sposobów jego użycia.
- Tranzytywne domknięcie w SBQL
- W tym wykładzie nie będziemy szczegółowo omawiać rozwiązań tranzytywnego
domknięcia w Oracle i DB2.
- Dla większości zapytań są one koszmarne.
- Ich uniwersalność jest bardzo słaba, szczególnie w Oracle.
- Zajmiemy się natomiast sposobem (składnią i semantyką) tego operatora w SBQL.
- Dopasowując je do już wprowadzonego (w poprzednim semestrze) stylu definiowania operatorów SBQL.
- Tranzytywne domknięcie w SBQL jest nowym operatorem niealgebraicznym, na
wzór już wprowadzonych operatorów niealgebraicznych.
- Implementacja (bez optymalizacji) jest przez to dziecinnie łatwa.
- Niżej zdefiniujemy je w najbardziej ogólnej postaci, w której operator ten może
działać nie na zapamiętanym, lecz na wyliczonym grafie, zaś kolejny element domknięcia jest wyliczany w locie.
- Składnia i semantyka dla M0
- Składnia: zapytanie ::= zapytanie close by zapytanie
- Semantyka: Zapytanie q1 close by q2 jest ewaluowane
w sposób następujący:
- Ewaluuje się zapytanie q1, które powinno zwrócić bag; jak zwykle, zapamiętuje się go na wierzchołku QRES.
Nazwijmy ten element stosu T.
- Dla każdego elementu r należącego do T wykonuje się następujące kroki:
- Oblicza się nested(r) i rezultat jest wkładany na wierzchołek ENVS;
- Ewaluuje się q2, które powinno zwrócić bag z elementami zgodnymi typologicznie z elementami
zwróconymi przez q1; wynik q2 jest zapamiętany na wierzchołku QRES;
- Istotny moment: wszystkie elementy bagu zwróconego przez q2 dostawia się (sumuje mnogościowo) z T
(gdzie zapamiętany był rezultat q1);
- Usuwa się wierzchołek QRES;
- Usuwa się wszystkie sekcje ENVS włożone w pierwszym kroku;
- W ten sposób elementy zwrócone przez q2 znajdą się w T, a wobec tego będą po jakimś czasie elementami
r przetwarzanymi przez ww. kroki.
- Początkowy stan T, w którym ulokowany był wynik q1, będzie więc rozrastał się w kolejnych krokach o kolejne
wyniki q2, aż do momentu, kiedy dla ostatniego przetwarzanego elementu bagu T zapytanie q2 zwróci pusty bag.
- W końcu wierzchołek QRES będzie zawierał wynik tranzytywnego domknięcia.
- Semantyka i implementacja
- Inne (denotacyjne) sformułowanie opisanego wyżej procesu ma postać równania
stałopunktowego T = q1 T. q2
- startujemy od T = do najbliższego punktu stałego
- Można go także przedstawić w postaci nieskończonej iteracji:
T = q1 q1.q2 q1.q2.q2
q1.q2.q2.q2 ...
która oczywiście zakończy się, gdy któryś z kolejnych członów zwróci .
- Implementacja: operator close by jest tak samo skomplikowany jak operator kropki.
- Implementacja bez optymalizacji jest banalna.
- Pokażemy na przykładach, że mimo banalnej implementacji jest to operator bardzo uniwersalny,
znacznie poszerzający moc języka zapytań.
- Operator można w sposób naturalny rozszerzyć na modele M1-M3.
- Przy pewnym skomplikowaniu zapytań jest to operator dość trudny - pytanie tylko,
czy jest jakiś łatwiejszy sposób
- Schemat (uproszczony) modelu BOM
-
- Schemat opisuje powiązanie pomiędzy częściami i podczęściami.
- Każda podczęść może wchodzić do wielu nadczęści.
- Każda część jest charakteryzowana przez atrybut nazwa oraz rodzaj, który może przyjąć
dwie wartości: "detal" dla części elementarnych i "agregat" dla części złożonych.
- Atrybuty kosztDet - koszt detalu - i masaDet - masa detalu - występują wtedy,
gdy atrybut rodzaj ma wartość "detal".
- Jeżeli atrybut rodzaj przyjmuje wartość "agregat", to występują atrybuty kosztMont
- koszt montażu oraz masaMont - przyrost masy w wyniku montażu.
- Każda część będąca agregatem składa się z pewnej liczby podczęści, co jest odnotowane w
atrybucie złożonym składnik.
- Składnik zawiera pointer prowadziDo, prowadzący do właściwej części będącej
składnikiem danego agregatu.
- Pragmatyka - Przykład 1
- Podaj wszystkie podczęści składające się na część o nazwie "silnik":
-
distinct((Część where nazwa = "silnik") close by (składnik.prowadziDo.Część))
- Podzapytanie (Część where nazwa = "silnik") zwraca referencję do obiektu Część
o nazwie "silnik".
- Operator close by wstawia na stos bindery do wszystkich atrybutów tego obiektu,
wśród nich wiele binderów o nazwie składnik; tyle, ile silnik zawiera bezpośrednich podczęści.
- Na tym stosie działa podzapytanie (składnik.prowadziDo.Część), zwracając referencje do
bezpośrednich składników silnika.
- Zostaną one następnie ulokowane w tym samym miejscu stosu QRES, gdzie umieszczona była referencja
do obiektu "silnik"; wobec czego po jakimś czasie będą tak samo przetworzone przez to podzapytanie.
- Proces domykania zakończy się, gdy rekurencyjnie przetworzone będą przez to podzapytanie wszystkie
składniki części "silnik", bezpośrednie lub pośrednie.
- Funkcja distinct usuwa zdublowane referencje (pojawiające się wskutek "zrostów"
w drzewie specyfikacji wyrobu).
- Pragmatyka - Przykład 2 i 3
- Podaj wszystkie części elementarne składające się na część o nazwie "silnik":
- distinct((Część where nazwa = "silnik")
close by (składnik.prowadziDo.Część))
where rodzaj = "detal"
- Podaj wszystkie części składające się na część o nazwie "silnik", wraz z ich ilością:
- ((Część where nazwa = "silnik"), (1 as ile))
close by (składnik.(( prowadziDo.Część), (ile * ilość) as ile))
- Zapytanie przed close by zwraca strukturę składającą się z referencji do obiektu silnika oraz
liczby 1 nazwanej ile; jest to rodzaj pseudozmiennej (w istocie jest to utworzenie bindera),
która dla każdej podczęści silnika będzie wyznaczać jej ilość.
- Po close by nawigujemy do obiektu składnik, wyznaczając dalej część wchodzącą w skład silnika
oraz ilość nazwaną ile, będąca iloczynem ilości nadczęści (poprzednie ile)
i ilości bieżącej podczęści.
- Pragmatyka - Przykład 4
- Poprzedni wynik nie sumuje ilości identycznych podczęści. Aby to zrobić, należy rozbudować
to zapytania wprowadzając w odpowiedni sposób funkcję agregowaną sum, np. poprzez wyrażenie:
-
((((Część where nazwa = "silnik") as x, (1 as ile))
close by (składnik.((prowadziDo.Część) as x, (ile*ilość) as ile)))
group as wszystkieCzęściSilnika).
((distinct(wszystkieCzęściSilnika.x) as y).
(y, sum((wszystkieCzęściSilnika where x = y).ile)))
- Pierwsze dwie linie zawierają poprzednie zapytanie używające operatora close by, z tym,
że referencja do obiektu Część została nazwana x. Trzecia linia bierze cały wynik tego zapytania i
nazywa go wszystkieCzęściSilnika. Operator kropki w tej linii powoduje, że cały nazwany w ten sposób wynik
znajdzie się na wierzchołku ENVS. Czwarta linia usuwa zdublowane referencje, wyznaczając w ten sposób wszystkie
różne części silnika, nazywając je y. Operator kropki w tej linii uruchamia pętlę po y (po kolekcji części silnika
bez duplikatów), umieszczając w każdej iteracji binder y(iczęść) na wierzchołku ENVS. Ostatnia linia
ustala wynik: referencje do części i sumę ilości poszczególnych części we wszystkich składowych silnika.
- Pragmatyka - Przykład 5
- Podaj koszt i masę części o nazwie "silnik". Uwzględnij koszty i masy wszystkich części
detalicznych silnika, przyrosty kosztu i masy związane z montażem agregatów oraz atrybut ilość określający,
ile razy dana część wchodzi jako składnik do agregatu.
-
((((Część where nazwa = "silnik") as x, (1 as ile))
close by (składnik.((prowadziDo.Część) as x, (ile*ilość) as ile)))
group as wszystkieCzęściSilnika).
(wszystkieCzęściSilnika.( if x.rodzaj = "detal"
then ((ile * x.koszt) as k, (ile * x.masa) as m)
else ((ile * x.kosztMont) as k, (ile * x.masaMont) as m)))
group as przyrostyKosztuMasy).
(sum(przyrostyKosztuMasy.k) as kosztSilnika, sum(przyrostyKosztuMasy.m) as masaSilnika)
- Pragmatyka - Przykład 6
- W obiekcie a jest przechowywana liczba; sformułować zapytanie w SBQL obliczające
pierwiastek kwadratowy z a.
- Wykorzystamy w tym celu równanie stałopunktowe x = (a/x + x)/2, startując od x = 1 i
wykonując 5 iteracji.
-
((1 as x, 1 as licznik) close by
(((a/x + x)/2 as x, licznik+1 as licznik) where licznik < 6).
(x where licznik = 5)
- Na początku ustawiamy wartości początkowe x oraz licznika na 1. W drugiej linii obliczamy
formułę równania, podstawiając ją na x, i zwiększamy licznik o 1. Jeżeli ten licznik przekroczy 5, to
warunek where powoduje,
że operator close by kończy akcję. Podzapytanie w drugiej linii zwraca więc 5 par struct
{ x(przybliżenie
pierwiastka), licznik(liczba)}.
- Najlepszym przybliżeniem jest oczywiście para, gdzie wartość licznika jest 5, i ta wartość
x jest wybrana przez podzapytanie z trzeciej linii.
- Zalety i wady operatora close by
- Ostatnie trzy zapytania pokazują możliwości tranzytywnego domknięcia: przy jego pomocy
możemy prowadzić złożone obliczenia w grafie, liczyć pierwiastek kwadratowy, itd.
- Powstaje pytanie, gdzie jest granica mocy obliczeniowej tej prostej i banalnej
w implementacji konstrukcji? Odpowiedź na to zapytanie, sformułowana przez matematyków,
być może byłaby nietrywialna, ale dla nas jest mało interesująca.
- Nas interesują granice możliwości pragmatycznej operatora, tj. na ile będzie wygodny
dla programistów.
- Ostatnie zapytania prowadzą do negatywnego wniosku. Zapytania są zbyt złożone dla powszechnego
programisty aplikacyjnego, a wobec tego ten sposób formułowania obliczeń może nie być zaakceptowany.
- Odczytanie znaczenia zapytań po jakimś czasie od ich napisania sprawia trudności, a
należy pamiętać (zgodnie ze starym powiedzeniem), że program pisze się raz, a czyta się 50 razy.
- Stąd operator close by jest akceptowalny w wersji prostej, a może być kontrowersyjny przy
użyciu jego pełnej mocy.
- Inne warianty tranzytywnego domknięcia (1)
- Operator leaves by pozwala na domknięcie tranzytywne podobne do close by,
ale który pozostawia tylko liście domykanego grafu, usuwając w locie węzły pośrednie.
To powoduje, że operator jest szybszy, a poza tym znaczna liczba zapytań ulega skróceniu.
- Podaj wszystkie części elementarne składające się na część o nazwie "silnik":
-
distinct((Część where nazwa = "silnik")
leaves by (składnik.prowadziDo.Część))
- Oblicz pierwiastek kwadratowy z a:
-
((1 as x, 1 as licznik) leaves by
(((a/x + x)/2 as x, licznik+1 as licznik) where licznik < 6). x
- Niestety, nie jest pewne, że ten operator jest akceptowalny dla programisty.
- Inne warianty tranzytywnego domknięcia (2)
- Powodem wprowadzenia dalszych wariantów operatora, nazwanych close distinct by
oraz leaves distinct by, są problemy obliczeniowe.
- Jeżeli domykany graf ma cykle, tj. q2 zwróci w pewnym momencie element, który już
wcześniej
był zwrócony przez q2, to proces nigdy się nie skończy.
- Ustalenie tego faktu podczas wykonywania close by jest trudne, ponieważ wymagałoby
stwierdzania przy każdym elemencie zwracanym przez q2, czy taki element nie był już wcześniej zwrócony,
co obniżyłoby sprawność do stanu nieakceptowalnego.
- Operator close distinct by tym różni się od close by, że w każdym obrocie pętli
iteracyjnej automatycznie usuwa duplikaty.
- Efektywna implementacja tego operatora polega na tym, że wspomniany wyżej
zbiór T trzyma się w postaci posortowanej.
- Elementy zwrócone przez q2 są zawsze wstawiane w odpowiednie miejsca posortowanego zbioru,
dzięki czemu można łatwo i szybko stwierdzić, że element jest duplikatem i pominąć go w dalszym
przetwarzaniu.
- Pragmatyka - Przykład 7
- Oblicz pierwiastek kwadratowy z a; wynik należy podać z dokładnością do piątego
miejsca po przecinku.
-
(1 as x) leaves distinct by ((integerOf(100000 * (a/x + x)/2) / 100000) as x)
- Zrezygnowaliśmy z licznika iteracji; obliczenia zakończą się, gdy kolejne przybliżenia x
nie będą się dalej różnić.
- Równania stałopunktowe w SBQL
- Równania stałopunktowe typu x = f(x) (których rozwiązaniem jest tzw. najmniejszy punkt stały,
least fixed point) oraz układy takich równań są przedmiotem licznych teorii w matematyce między innymi
z tego powodu, że są dobrym środkiem formalnego opisu semantyki mechanizmów rekurencyjnych,
np. semantyki rekurencyjnych procedur.
- W językach zapytań pojawiły się one z powodu ich własności pragmatycznych. Okazało się,
że mogą być efektywnie zastosowane przez użytkownika lub programistę do formułowania tranzytywnych domknięć.
- Jest to niekiedy wygodniejsze i czytelniejsze, a ponadto, równania takie są znacznie bardziej
uniwersalne niż tranzytywne domknięcia.
- W istocie, przedstawione przez nas zapytanie q1 close by q2 sprowadza się do równania
stałopunktowego T = q1 T.q2.
- Możemy formułować zapytania w postaci T = q(T), gdzie q jest dowolnym zapytaniem
odwołującym się do T, co pozwoli na zadawanie zapytań niewyrażalnych przez tranzytywne domknięcia.
- Oczekiwania dotyczące równań stałopunktowych
- Wielu specjalistów uważa, że są one w stanie wyrażać w prosty sposób tzw.
"reguły biznesowe" (business rules).
- Jest to naciągane i wątpliwe
- Takie równania mogą być środkiem rozwiązania pewnych rekurencyjnych problemów.
- Równania te realizują paradygmat bardzo podobny do tego, który nosi nazwę
"dedukcyjnych baz danych" (lub Datalogu).
- Podkreśla się przy tym często związki z logiką matematyczną,
"ukoronowaniem maszynowej inteligencji" (zdaniem pseudo-teoretycznych demagogów).
- Związek "dedukcyjnych baz danych" z logiką matematyczną jest drugorzędny.
- Równania stałopunktowe można budować praktycznie w oparciu o dowolny paradygmat,
włączając algebrę relacji, SQL, OQL i oczywiście SBQL.
- Programowanie pewnych rekurencyjnych zadań poprzez reguły mające postać równań
stałopunktowych może być ważne z powodów pragmatycznych
- Natomiast zastosowanie w tym kontekście logiki matematycznej jest
kompletnie nieważne - nie oferuje ona w istocie nic więcej poza (kontrowersyjną) składnią.
- Składnia równań stałopunktowych
- Składniowo, układ równań stałopunktowych należałoby zamknąć pewnymi nawiasami,
aby je wyróżnić wśród innych elementów języka. Podana niżej składnia jest przykładowa.
-
rule (x1, x2, x3, ...) {
x1 :- q1(x1, x2, x3, ...);
x2 :- q2(x1, x2, x3, ...);
x3 :- q3(x1, x2, x3, ...);
...
}
- Nazwy x1, x2, x3, ... mogą być dowolnie wybrane przez programistę.
- q1, q2, q3, ... są zapytaniami SBQL zależnymi od nazw x1, x2, x3, ..., przy czym w danym
zapytaniu te nazwy nie muszą wystąpić.
- To samo dotyczy nagłówka rule: niektóre nazwy spośród x1, x2, x3, ... mogą nie wystąpić,
ale musi wystąpić co najmniej jedna.
- Kolejność równań xi :- qi(x1, x2, x3, ...) jest dowolna.
- W równaniach wybraliśmy symbol :- inny niż = , ponieważ semantyka tej równości
jest specyficzna, bardziej przypominająca podstawienie.
- Semantyka równań stałopunktowych
- Rezultatem jest struktura struct{ x1(bag1), x2(bag2), x3(bag3), ...}, gdzie bag1, bag2,
bag3, ...
są bagami wyliczonymi przez zapytania q1, q2, q3, ... (odpowiednio).
- Wyliczenie polega na procesie iteracyjnym, w którym na początku wszystkim nazwom
x1, x2, x3, ...
przypisuje się pusty bag .
- Następnie liczy się q1, q2, q3,..., uzyskując w ten sposób następne wartości
x1, x2, x3, ... .
- Proces ten jest powtarzany aż do momentu osiągnięcia punktu stałego, tj. takich wartości
bag1, bag2, bag3, ... podstawionych pod x1, x2, x3, ... , że kolejne wyliczenie q1, q2, q3,...
nie przyniesie ich zmiany.
- Implementacja tego procesu jest bardzo prosta.
- Optymalizacja w ogólnym przypadku może być bardzo trudna, stąd mogą pojawić
się zasadnicze problemy z wydajnością (powód dla którego dedukcyjne bazy danych nie przebiły się do praktyki)
- Przykłady z BOM
- Podaj wszystkie części składające się na silnik (ewentualnie z duplikatami).
-
rule(Elem) { Elem :- (Część where nazwa = "silnik")
(Elem.składnik.prowadziDo.Część);}
- Podaj części detaliczne silnika, z usunięciem duplikatów:
-
distinct( rule(Elem) { Elem :- (Część where nazwa = "silnik")
(Elem.składnik.prowadziDo.Część);}.Elem)
where rodzaj = "detal"
- Przykład z drzewem genealogicznym
- Obiekty Osoba mają atrybuty nazwisko, rokUr (rok urodzenia), żyje (z wartością boolowską) oraz
są powiązane związkami rodzinnymi matka, ojciec, syn, córka, zaimplementowanymi jako obiekty pointerowe
umieszczone wewnątrz obiektów Osoba.
- Podaj nazwisko i rok urodzenia wszystkich żyjących kuzynów Kowalskiego,
którzy są od niego młodsi:
-
rule(młodszyŻyjącyKuzyn){
kto :- Osoba where nazwisko = "Kowalski";
przodek :- kto przodek.(matka
ojciec).Osoba;
kuzyn :- przodek kuzyn.(syn
córka).Osoba;
żyjącyKuzyn :- distinct( kuzyn where żyje );
młodszyŻyjącyKuzyn :-
((żyjącyKuzyn as z) where ∃ kto as k (z.rokUr > k.rokUr)).z;
}.
młodszyŻyjącyKuzyn. (nazwisko, rokUr)
- Optymalizacja
- Przy naiwnej ewaluacji w podanym poprzednio układzie równań zmienne kto, przodek, kuzyn,
żyjącyKuzyn, młodszyŻyjącyKuzyn będą ewaluowane wielokrotnie, tyle razu, ile potrzeba do osiągnięcia
punktu stałego.
- Dla dużych drzew genealogicznych może to być nawet miliony razy.
- Tymczasem jest oczywiste, że np. zmienną kto można wyliczyć tylko raz, gdyż za każdym
następnym razem jej wartość się nie zmieni.
- Istotą metody optymalizacji jest ustalenie kolejności wyliczania zmiennych w taki sposób,
aby każda z nich była liczona minimalną liczbę razy.
- W tym celu buduje się graf zależności pomiędzy zmiennymi ustalający, która zmienna korzysta
z której.
- Mając taki graf można bardzo łatwo wyznaczyć kolejność ewaluacji zmiennych.
- Graf zależności między zmiennymi
-
pokaż animację
- Dla tego grafu wyraźnie widać optymalną kolejność obliczania zmiennych.
- W ogólnym przypadku problem może być nietrywialny.
- Szczęśliwie, tego rodzaju ogólny przypadek istnieje prawie wyłącznie w
urojeniach pseudo-teoretyków.
- Zbieżność układu równań stałopunktowych
- Można bez trudu podać taki układ równań, który nigdy nie osiągnie punktu stałego,
tj. będzie w istocie nieskończoną pętlą.
- Co więcej, niektóre operatory są w tym względzie "niebezpieczne", tj. nie dają
gwarancji, że układ równań się nie zapętli.
- Powszechnie znanym takim operatorem jest operator negacji.
- Umotywował on wielu specjalistów z zakresu programowania w logice do specjalnych badań
(owocujących w dalsze pojęcia, takie jak "stratyfikacja").
- Negacja jest jednak tylko jednym z wielu operatorów powodujących, że układ równań może nie
być zbieżny do punktu stałego.
- Przykładowo, to samo może spowodować funkcja sinus lub operator minus.
- Koncentrowanie się logików na operatorze negacji przypomina pieczołowite łatanie
jednej dziury w przeciekającym dachu, w którym jest tysiąc dziur.
- Jest bardzo wątpliwe, że ten problem nie doczeka się skutecznego środka teoretycznego,
wobec czego pozostaje tylko środek klasyczny, czyli testowanie.
- Podsumowanie
- Rekurencyjne lub sieciowe struktury danych wymagają specjalnych operatorów w
językach zapytań. Klasyczne operatory są niewystarczające.
- Komercyjne systemy oferują rozszerzenia SQL o specjalne klauzule lub operatory.
Mają jednak niewystarczająca moc i są trudne w użyciu.
- Paradygmat "dedukcyjnych baz danych" proponuje środki oparte na programowaniu w logice.
Są one jednak z wielu względów wadliwe.
- W SBQL przewidziano dwa środki: tranzytywne domknięcia (operator niealgebraiczny close by)
oraz równania stałopunktowe. Oba te środki są dość łatwe w implementacji i użyciu.
- SBQL oferuje także procedury, metody, funkcje i perspektywy, które również mogą być
rekurencyjne i użyte do programowania zadań rekurencyjnych.
- Wiele zadań rekurencyjnych może być także rozwiązana poprzez zamianę rekurencji na
iterację. Programy stają się jednak przez to znacznie dłuższe, mniej czytelne i trudniejsze do zmian.