57382 ullman124 (2)

I U/.IAI-ANIA w Mlłl>1.1.v¹ Kr. i. AC- VJNVM

i szóstej, ponieważ pr/ylot do Dallas następuje o 14:30 i jest to tylko na pół godziny przed odlotem / Dallas o 15:00. Krotki powstałe w wyniku tego kroku iteracyjnego zostały przedstawione na rys. 4.22. Nad linią znajdują się krotki powstałe w pierwszym kroku, a pod nią umieszczono sześć nowych krotek, które pow stały w kroku 2. Sama linia nie jest oczywiście elementem relacji.

V	y	d	r
SF	DEN	930	1230
SF	DAL	900	1430
DEN	CHI	1500	1800
DEN	DAL	1400	1700
DAL	CHI	1530	1730
DAL	NY	1500	1930
CHI	NY	1900	2200
CHI	NY	1830	2130

RYSUNEK 4.21

Podstawowe krolki relacji Połączenia

X	V	d	r
SF	DEN	930	1230
SF	DAT,	900	1430
DEN	CHT	1500	1800
DEN	DAL	1400	1700
DAL	CHT	1530	1730
DAL	NY	1500	1930
CHI	MY	1900	2200
CHI	NY	1830	2130
SF	CHT	900	1730
SF	CHT	930	1800
SF	DAT,	930	1700
DEN	NY	1500	2200
DAL	NY	1530	2130
DAL	NY	1530	2200

RYSUNEK 4.22

Relacja poU< /.onia po drugiej iteracji

W trzecim kroku iteracji trzeba rozważyć wszystkie krotki z rys. 4.22 jako kandydatów do utworzenia nowych Połączeń przy- zastosowaniu reguły (2). Jednak nie ma sensu rozpatrywać ponownie par krotek, z których obie są umieszczone nad linią, były już. bowiem analizowane w drugim kroku iteracji, i jeśli spełniały warunki, to zostały zapisane poniżej linii. Jedyne nowe krotki mogą powstać z par. w których przynajmniej jeden element został wygenerowany w drugim kroku, a zatem z krolki zapisanej poniżej linii na rys. 4.22.

X	V	d	r
SF	DEN	930	1230
SF	DAL	900	1430
DEN	CHI	1500	1800
DEN	DAL	1400	1700
DAL	CHI	1530	1730
DAL	NY	1500	1930
CHT	NY	1900	2200
CHI	NY	IB 30	2130
SF	CHI	900	1730
SF	CHI	930	1800
SF	DAL	930	1700
DEN	NY	1500	2200
DAL	NY	1530	2130
DAL	NY	1530	2200
SF	NY	900	2130
SF	NY	900	2200
SF	NY	930	2200

RYSUNEK 4.23

Relacjo Połączenia po trzeciej iteracji

W trzecim kroku iteracji otrzymujemy tylko trzy nowe krotki, /osi one umieszczone na samym dole tabeli na rys. 4.23. Linie na tym rysui oddzielają grupy krotek powstałe w poszczególnych krokach iteracji, powy linii pierwszej jest osiem krotek powstałych w pierwszym kroku, w sro* jest sześć krotek z drugiego kroku, a poniżej drugiej linii ostatnie trzy kro W kroku 4 iteracji nie powstają już żadne nowe krotki, a zatem jest to koniec przetwarzania algorytmu. Na ry sunku 4.23 została zatem przedstav na kompletna relacja Połaćr

4.4.4. Negacja w regułach rekurencyjnych

Czasami trzeba użyć w jednej regule zarówno rckurencji, jak i neg; Połączenie tych dwóch elementów można przeprowadzić na dwa spos< bezpieczny i ryzykowny. Ogólna zasada polega na tym, żeby używać neg jedynie w takich przy padkach, kiedy nie znajduje się ona wewnątrz opet z punktem stałym. Żeby uchwycić właściwy sens tej zasady przedstaw dwa przy kłady połączenia rckurencji i negacji, jeden / nich daje poprą’ wynik, a drugi jest paradoksalny. Przekonamy sic, że jedynie ..warstwo negacja dobrze łączy' się z rekurencją. a termin „warstwowa" precyzy zdefiniujemy po przedstawieniu przykładów