60375 ullman120 (2)

nowa c/^ść ma powodzenie, to powstaje kolejny odcinek itd. A zatem każdy tilm może potencjalnie stanowić początek długiego ciągu innych filmów. Załóżmy, że relacja Kolcjny(tilm, odcinek) zawiera pary złożone z filmu i jego bezpośrednio następnej części. Przykładowe krotki w tej relacji mogą wyglądać następująco:

film	odcinek
Rewo1 wer	Rewolwer 21/2
Rewolwer 2 1/2	Rewolwer 33 1/3

Można zastosować ogólniejszy zapis następnego filmu, w znaczeniu kolejnego do kolejnego itd. W przedstawionej relacji Rewolwer 33 1/3 nastę pujc po filmie Rewolwer, ale nic jest kolejnym w znaczeniu użytego tu termi nu ,.kolejny". Przechowywanie w relacji tylko bezpośrednio kolejnych części służ} oszczędności przestrzeni na dysku, a jednocześnie umożliwia określenie właściwego następstwa poszczególnych części, jeśli zajdzie taka potrzeba W powyższym przykładzie oszczędność jest niewielka, ale już w przypadku pięciu odcinków filmu Roch pamiętamy o sześć par mniej, a w przypadku IX odcinków „Piątek trzynastego” już jest o 136 par mniej.

Jednakże sposób tworzenia relacji następstwa z relacji Kole jny nie jest już taki oczywisty. Można tworzyć kolejny do kolejnego przez złączenie relacji Kol-- jny zc sobą. Poniżej przedstawiamy przykład wyrażenia opisującego złączenie naturalne, w którym przemianowano zmienne:

Kpurwuy, irztc/j^Ripitrwin. .^(Kolejny) X />**,*,. ,rrw)(^{Ko 1} ° 3 ⁿy))

Przemianowanie zastosowano w tym wyrażeniu dwukrotnie: najpierw argumenty relacji Kolejny nazywają się pierwszy i drugi, a potem drugi i trzeci. W naturalnym złączeniu otrzymujemy zatem te krotki (/»|, ///:) i (/«-,, //;₄) relacji Kolejny, w których m₂ = /Wj. Z tego złączenia powstają pary (ifii, Mą). Zauważmy, że ///^ jest kolejnym od kolejnego od ni\.

Ażeby otrzymać kolejny od kolejnego od kolejnego (np. Rocky i Rocky IV), możemy złączyć ze sobą trzy kopie relacji Kole ny. Ogólniej rzecz ujmując, można otrzymać My kolejny odcinek, gdzie i jest pewną ustaloną wartością przez wykonanie złączenia /-I razy. Polem można wykonać operację sumy algebraicznej i w ten sposób otrzymać relacje z zapisem wszystkich następstw (nie tylko bezpośrednich).

Zauważmy jednak, żc można tak postępować, tylko gdy wartość / jest z góry ustalona. W algebrze relacji nie można otrzymać „sumy nieskończonej”, w której dla dowolnie długiego ciągu następstwa można by otrzymać krotkę zawierającą /-ty kolejny odcinek, dla dowolnego, nieograniczonego /'. Suma w algebrze relacji jest bowiem zdefiniowana dla dwóch relacji, a nie dla ich nieskończonej liczby. Stosując zatem operator sumowania, skończoną liczbę razy można uzyskać skoń-czonc wyrażenie algebraiczne sumę skończonej liczby relacji, nie można nato miast uzyskać wyrażenia o nieskończonej długości.

c

4.4.1. Operator punktu stałego

Na szczęście nie ma konieczności dołączenia do algebry relacji bałaga marskiej konwencji, która umożliwiałaby zapisywanie nieskończonej sum; „podobnych” wyrażeń. Istnieje inny popularny sposób opisania relacji takie] jak Następny (x, y) (tzn. film y jest odcinkiem następnym po .r w sensi' wynikającym z przykładu 4.33), które są tworzone w potencjalnie nieskoń czonym. ale uporządkowanym procesie z innych relacji, takich jak Kolejny Utworzymy równanie, w którym relacja Następny jest opisywana przez sa mą siebie i relację Kolejny, a potem stwierdzimy, że relacja Następny jes najmniejszą relacją (najmniejszym punktem stałym), która spełnia to równanie Dla oznaczenia faktu, że należy wybrać najmniejszy punkt stały równania użyjemy symbolu <f>.

PRZYKŁAD 4.34

Poniżej przedstaw iamy zastosowanie operatora punktu stałego w równaniu które opisuje relację Następny (x, y):

</>(Następny A'«*y»><».yj(Kolo Jny) u

.(Kolejny tx *,*•,«>• . .Następny)))

Intuicyjnie to równanie można przeczytać następująco: „Film y następuje p« filmie x, jeśli jest kolejnym odcinkiem filmu v, albo następuje po kolejnyn odcinku filmu x'\

Aby zrozumieć zapisane rów nanie, najpierw trzeba sobie uśw iadomić, ż atrybutami relacji Następny są v i y. Relacja Następny stanowi lewą stron równania, a jego prawą stroną jest suma dwóch termów. Pierwszy z nich ^(Kolejny) jest kopią relacji Kolejny z przemianowaniem alrybu tów po to, by ich nazwy pasowały do relacji Następny. Drugi term stanów złączenie teta Kolejny    , Następny, które służy połączeniu wszyst

kich par (a, b) z relacji Kole ny / parami (ó, t ) relacji Następny. W wyniki powstają krotki (a, h, />, c), których atrybutami są odpowiednio fi im, ko 1< jny, v orazy. To złączenie jest następnie rzutowane na pierwszą i czwart składową: f i ln oraz y, a polem zostają przemianowane atrybuty x i y.

W równaniu ze stałym punktem relacja Następny jest przyrównana do su my relacji Kolejny oraz wyniku przetworzenia drugiego termu, który podaj ciąg następstw. A zatem relacja Następny składa się z takich par (x, y), któr albo są elementami relacji kolejny, albo w' któiychyjest następnym odcinkier

po kolejnym odcinku filmu ,v. Inaczej mówiący jest kolejnym.....po kolejnyr

odcinku filmu x. gdzie słowo „kolejny" powtarza się dowolnie dużo razv.

C