ullman121 (2)

4. U/.IAI ANIA W MUUfcU/ RELACYJNYM

4.4.2. Obliczanie najmniejszego punktu stałego

Wcale nie musi być oczywiste to, że najmniejsze rozwiązanie równania z przykładu 4.34, czyli zdefiniowana tam relacja Nast epny, jest właśnie tym zbiorem, o który nam chodzi, tzn. zbiorem tych par filmów, które należą do jednej serii filmów, i gdzie pierwszy odcinek w parze jest wcześniejszy niż drugi element w parze. Sens operatora punktu stałego będzie najlepiej zrozumieć, gdy przeanalizuje się obliczenie punktu stałego. Opisany poniżej sposób obliczania punktu stałego jest poprawny w przypadku, gdy w wyrażeniu nie występuje operator różnicy, natomiast w p. 4.4.4 przedstawimy inny sposób, poprawny dla zadań, w których wy stępuje operator różnicy.

1.    Na początku zakładamy, że występująca z lewej strony równania relacja R jest pusta.

2.    Powtarzamy obliczanie kolejnej nowej wartości relacji R przez przetworzenie prawej strony równania, gdzie w miejsce R wstawia się wartość obliczony w poprzednim kroku.

3.    Kończymy obliczenie w tej iteracji, w której uzyskana wartość jest identyczna z poprzednią.

PRZYKŁAD I 35

Prześledzimy obliczenie relacji Nar.: «. iny przy założeniu, że relacja Ko >-ny składa się z następujących krotek:

film	kolejny
Rocky	Rocky U
Rocky II	Rocky 111
Rocky Tli	Rocky IV

Na początku zakładamy, że relacja Następny jest pusta. Złączenie relacji Kolejny i Następny w równaniu z punktem stałym jest wobec tego też puste, a więc jedyne krotki rozwiązania będą pochodzić z pierwszego termu w sumie, czyli z relacji Kolejny. A więc po pierwszym kroku iteracji wartości relacji Następny i Kolejny są takie same. Tę sytuację przedstawiono na rys. 4.16.

W drugim kroku jako relacji Następny użyjemy relacji z rys. 4.16 i policzymy przy tym założeniu prawą stronę naszego równania / punktem sta łym. Z pierwszego termu otrzymuje się ponownie te same trzy krotki, które

X	y
Rocky	Rocky II
Rocky IT	Rocky III
Rocky III	Rocky IV

RYSUNEK 4 16

Relacja Następny po pierwszej iteracji

już są. Aby obliczyć relację zapisaną w drugim termie, trzeba utworzyć złączenie relacji Kolejny z bieżącą relacją Następny, która, jak uprzednio napisaliśmy, jest z nią identyczna. Aby otrzymać wynik złączenia, wybieram) takie krotki, których drugi element pary w relacji Kolejny jest taki sam jak pierwszy element w parze relacji Nast ępny.

A więc na przykład otrzymujemy krotkę (Rocky, Rocky III) z połączenia pary (Rocky, Rocky II) z relacji Koleiny z parą (Rocky II, Rocky 111) z relacji Następny. Postępując analogicznie z krotką

(Rocky II, Rocky III)

z relacji Kolę jny oraz krotką (Rocky III, Rocky IV) z relacji Następny, otrzymujemy nową krotkę relacji Następny: (Rocky II, Rocky :v). Żadnych innych par z relacji Kolejny i Następny nic można połączyć.

A zatem po dwóch krokach \s relacji Następny jest pięć krotek przedstawionych na rys. 4.17. Porównując rys. 4.16 z rys. 4.17 możemy intuicyjnie określić, że pierwszy z nich zawiera odcinki następujące bezpośrednio po sobie, a na drugim są jeszcze dodatkowo pary odległe od siebie o dwa odcinki.

W kroku trzecim jako relację Następny traktujemy krotki uwidocznione na rys. 4.17 i ponownie obliczamy prawą stronę równania z punktem stałym. Poza powstałymi dotąd krotkami otrzymujemy jeszcze jedną parę. Bowiem z połączenia pary (Rocky, Rocky II) z relacji Kolejny z parą (Rocky II, Rocky IV) z bieżącej relacji Następny otrzymuje się nową parę (Rocky, Rocky IV). Po trzecim kroku iteracji powstaje zatem nowy stan relacji Następny przedstawiony na rys. 4.18.

X	_ y
Rocky	Rocky 11
Rocky TI	Rocky III
Rocky III	Rocky IV
Rocky	Rocky III
Rocky II	Rocky IV

RYSUNEK 4 17

Relacja Następny po drogiej iteracji

X	y
Rocky	Rocky II
Rocky 11	Rocky III
Rocky III	Rocky IV
Rocky	Rocky III
Rocky II	Rocky IV
Rocky	Rocky IV

RYSUNEK 4 18

Relacja Następny po trzeciej iteracji