58259 ullman125 (2)

PRZYKŁAD 4.39

Niech nasze zadanie polega na wyszukaniu na mapie z rys. 4.19 tych wszystkich par miast (x, y), które są połączone rejsami linii UA w kierunku zx do y (może to być połączenie złożone z kilku rejsów), ale które nie są połączone rejsem linii AA. Zdefiniujemy rekurencyjnie predykat UAłaczy tak samo, jak definiowaliśmy predykat Połączenie w przykładzie 4.37, dołączymy tylko nowe ograniczenie do rejsów linii UA.

1.    UAłączy(x,    y)    *—    Rejsy (UA,    x,    y, d,    r)

2.    UAłączy(x,    y)    •—    UAłączy(x,    z)    AND    UAłączyU,    y)

W analogiczny sposób określamy predykat AAłączy, który zawiera wszystkie połączenia zx doy rejsami linii AA i w ten sposób otrzymujemy następujący zestaw reguł:

1.    AAłaczy{>:,    y)    ♦—    Rejsy (AA,    x,    y, d,    r)

2.    AAłączy(x,    y)    «—    AAłączy(x,    z)    AND    AAłączy(z,    y)

Teraz już. tylko trzeba zdefiniować predykat UAtylko, do którego będą należeć tylko te pary miast (*, y\ które można połączyć rejsami wyłącznie linii UA. a nic można połączyć rejsami linii AA, i dostajemy następującą regułę, nie zawierającą rckurencji:

UAtylko (x, y) — UAłączy(x, y) AND NOT AAłączy(x, y)

Powyższa reguła definiuje różnicę relacji UAłączy i AAłaczy.

Dla danych z rys. 4.19 do relacji UAłączy można utworzyć następujące pary: (SF, DEN), (SF, DAL), (SF, CHI), (SF, NY), (DEN, DAL), (DEN, CHI), (DEN, NY), oraz (CHI, NY). Zbiór ten otrzymuje się jako wynik przetworzenia algory tmu z punktem stały m, który został przedstawiony w p 4.4.2. W analogiczny sposób otrzymuje się krotki relacji AAłączy i są nimi: (SF, DAL), (SF, CHI), (SF, NY), (DAL, CHI), (DAL, NY) oraz (CHI, NY). Po wykonaniu operacji różnicy algebraicznej tych relacji powstaje następujący zbiór par: (SF, DEN), (DAN, DAL), (DEN, CHI) Oraz (DEN, NY). Zbiór tych czterech par jest wartością predykatu UAt yl ko.

□

PRZYKŁAD I 40

A teraz rozważmy abstrakcyjną sytuację, w' której nie da się już lak łatwo utworzyć wyniku. Załóżmy, ze jest dany jeden predykat R typu EDB. Jest on unamy (jednoargumentowy) i zawiera tylko jedną krotkę (0). Tworzymy nowe predykaty unamc P i Q, oba typu 1DB; definiują je następujące reguły:

1. P(X) «— R(x) AND NOT Q(x)

2. Q(x) ♦- R(x) AND NOT P(x)

Te dvv ic reguły mów ią o tym, że element x należący do R należy również albo do P, albo do Q, ale nigdy do obu na raz. P i Q są zdefiniowane wzajemnie rekurencyjnic.

Przy oka/ji określania znaczenia reguł rekurcncyjnych w p. 4.4.1 podkreślono, że rekurencja musi być traktowana jako operacja z najmniejszym stałym punktem, tzn. ze wynikiem ma być najmniejsza relacja, która spełnia regułę w postaci równania algebraicznego. Z reguły I wynika, żc P = R - Q, n z reguły 2 wynika, że {) R P. Ale w relacji R jest tylko jedna krotka (0), a więc może ona należeć albo tylko do /\ albo do Q. Ale gdzie? Nic może być w żadnej z nich. ponieważ nie będzie spełnione równanie; na przykład z tego, że zachodzi P-R-Q wynika 0 = {(0)} - 0. co jest oczywistą nieprawdą.

Jeśli natomiast ustalimy, że P {(0)}, a Q ^Ł 0, to otrzymamy rozwiązania obu równań. Z równania P - R Q wynika, żc {(0)} = {(0)} - 0, co jest prawdą, a z Q - R - P wynika, żc 0    {(0)} - {(0)}. co też jest prawdą.

Ale przecież można także określić P = 0, a Q = {(0)}. W tym przypadku również, oba równania są spełnione. Otrzymaliśmy zatem dwa równoprawne rozwiązania dla P i Q\

a) />={(0)}    Q-0

b) /> = 0    £*{(0)}

Oba z nich są rozwiązaniami minimalnymi w tym znaczeniu, żc jeśli usuniemy jakąś krotkę z którejkolwiek z nich, to reguły przestaną być spełnione. A w jaki sposób wskazać jako właściwsze któreś z dwóch minimalnych rozwiązań z punktem stałym? Nie możemy też odpow iedzieć na proste pytanie, takie jak: „Czy P(0)je$t prawdą?”

□

W przykładzie 4.40 okazało się. żc jeśli rekurencja i negacja są za bardzo ze sobą sprzężone, to nasz algorytm tworzenia rozwiązania rekurencyjnych reguł lub równań z punktem stałym, które jest stałopunktowe i minimalne, przestaje działać. Może się bowiem okazać, że takich rozwiązań jest wiele i są dodatkowo wzajemnie sprzeczne. Pewnie byłoby dobrze, gdyby istniał jakiś algorytm precyzyjnego określania rozwiązania rckurcncji powiązanej z negacją, ale dotychczas nie udało się uzgodnić w tej sprawie wspólnego stanowiska, jest zbyt wiele opinii o tym. co naprawdę oznaczają reguły lub równania z takim zapisem.

Lepiej zatem poprzestać na formułowaniu takich reguł rekurencyjnych, w-których negacje są warstwowe. Takie ograniczenie obowiązuje mi przykład w opisywanym w podrozdziale 5.10 standardzie SQL3. Jak przekonamy się później w przypadkach rckurcncji warstwowej istnieje algorytm umożliwiający wyznaczenie jednego określonego rozwiązania minimalnego z punktem stałym (być może spośród w ielu rozwiązań o takich cechach), które jest zgodne z intuicyjnym rozumieniem reguł. Wyjaśnimy obecnie, co to znaczy „warstw o wość”.