ullman113 (2)

to, by reguły / podzadaniami arytmetycznymi lub zaprzeczonymi (tzn. ze* spójnikiem NOT na początku) miały znaczenie zgodne z intuicją Ograniczenie, nazywane warunkiem bezpieczeństwa, brzmi następująco:

• Każda zmienna, która występuje w regule, musi występować w pewnym niezaprzeczonym podzadaniu relacyjnym.

A zatem, jeśli zmienna występuje w nagłówku, w podzadaniu zaprzeczonym lub podzadaniu arytmetycznym, to musi również w tej regule występować gdzieś w podzadaniu relacyjnym, niezaprzeczonym.

PRZYKŁAD 4.17

Rozważmy regułę z przykładu 4.16:

DługiFilm (t, y) <- Film (t, y, 1,    _)

AND 1 i. 100

Pierwsze podzadanie jest niezaprzeczone i relacyjne oraz zawiera wszystkie zmienne występujące w regule. A obie zmienne z nagłówka: t oraz y występują również w pierwszym podzadaniu w treści reguły. Z kolei zmienna /, która występuje w podzadaniu arytmetycznym, pojawia się również w pierwszym podzadaniu.

□

PR/.YKLAD4 18

W regule, którą przedstawiono poniżej, są trzy odstępstwa od zasady bezpieczeństwa:

P(x, y) 4- Q(x, z) AND NOT (R(w, x, z) AND c < y

1.    Zmienna y występuje w nagłówku, ale nie występuje w żadnym podzadaniu, które jest zarówno relacyjne, jak i niezaprzeczone. Zauważmy, że zapis x <y nic ogranicza zakresu wartości zmiennej y do zbioru skończonego. W związku z tym, jeśli znajdziemy takie wartości a, b. c, odpowiadające kolejnym zmiennym w, x, z, dla których pierwsze dwa podzadania są prawdziwe, to w relacji nagłówka P pojawi się nieskończona liczba krotek (a, d), gdzie d> a.

2.    Zmienna w występuje wyłącznic w podzadaniu. które co prawda jest relacyjne, ale nic jest niezaprzeczone.

3.    Zmienna y występuje w podzadaniu arytmetycznym, a nic występuje w żadnym podzadaniu niezaprzeczonym i relacyjnym.

A zatem reguła nic spełnia warunku bezpieczeństwa i nie można jej użyć jako reguły Datalogu.

Bezpieczeństwo reguł można również określać w inny sposób. Zamias rozważać wszystkie możliwe przy pisania wartości do zmiennych, rozważam zbiory krotek tych wszy stkich pod/adań, które są relacyjne i niezaprzeczone Jeśli pewne przypisanie krotek do wszystkich pod/adań niezaprzeczonycl i relacyjnych jest niesprzeczne, tzn. każdemu wystąpieniu zmiennej odpowia da taka sama wartość, to należy zbadać wynikowe przypisanie wartości d» wszystkich zmiennych występujących w regule. Jeśli reguła spełnia warunel bezpieczeństwa, to każdej zmiennej jest przypisana pewna wartość.

Dla każdego przypisania niesprzecznego rozważmy teraz podzadania rela cyjne, niezaprzeczone oraz podzadania ary tmetyczne i sprawdźmy, czy przypi sanie tych wartości zmiennym sprawiło, że są one prawdziwe Należy przy ty n pamiętać, że podzadanie zaprzeczone jest prawdziwe wówczas, gdy atom jes fałszywy. Jeśli wszystkie podzadania są prawdziwe, to wiadomo jakie krotk występują w nagłów ku w wyniku tego przypisania wartości do zmiennych. Dc relacji, występującej w nagłów ku, dołącza się wówczas daną krotkę.

PRZYKŁAD 4.19

Rozważmy następującą regułę / Datalogu:

P(x, y) «— 0( x, z) AND R( z, y) AND NOT Q(x, y)

Załóżmy, że w relacji Q występują dwie krotki; (1, 2) ora/ (1, 3). Niech w relacji R występują / kolei krotki (2, 3) oraz (3, 1). W regule są dwa podzadania niezaprzeczone, relacyjne: Q(x, r) ora/ R(z, y). Trzeba zbadać wszystkie możliwe kombinacje przypisań krotek z relacji Q i R do pod/adań im odpowiadających. Na rysunku 4.13 zamieszczono tabelę z zapisem wszystkich czterech kombinacji.

	Krotka dla Q(x, z)	Krotka dla RU, y)	Przypisanie niesprzeczne?	NOT Q(x, y) Prawda?	Nagłówek wynikowy
1)	(1,2)	(2,3)	Tak	Nie	—
2)	(1,2)	(3, 1)	Nic; z = 2,3	Niewłaściwe	—
3)	(1,3)	(2,3)	Nic; z = 3,2	Niewłaściwe	—
4)	0.3)	(3,1)	Tak	Tak	P(l, 1)

RYSUNTK t 13

Wszystkie możliwe przypisania krotek do z) i R(z,y)

Drugi i trzeci wariant z rys. 4 13 są sprzeczne. W każdym / nich występują dwie różne wartości przypisane do tej samej zmiennej z. A zatem te warianty przypisań zostaną odrzucone, nie będą już dłużej brane pod uwagę.

W wariancie pierwszym jest niesprzeczne przypisanie krotki (1.2) do podzadania Q(x, z) oraz krotki (2. 5) do podzadania R(z. y), skąd wynika przypisanie dla zmiennych x, y, z kolejno wartości 1. 3. 2. Następnie sprawdzamy wynikające / tego przypisania wartości pozostałych pod wyrażeń, które