26206 ullman126 (2)

ZDÓ 4 DZ1AI ANIA W MODELU RELACYJNYM

1. Należy narysować graf, którego wierzchołki odpowiadają predykatom

IDB.

2.    Jeśli reguła, w której nagłówku znajduje się predykat A, zawiera zanegowane zadanie / predykatem li, to tworzymy krawędź od A do B. Tę krawędź etykietujemy znakiem co oznacza krawędź z negacją.

3.    Jeśli reguła, w której nagłówku znajduje się predykat A, zawiera nic zanegowane zadanie z predykatem B, to tworzymy krawędź od A do Ii. Tej z kolei krawędzi nie etykietujemy znakiem

Jeśli w tym grafie występuje cykl, który zawiera krawędź z negacją, to reku-rencja nie jest warstwowa. W przeciwnym przypadku w grafie można wyróżnić warstwy, które są wyznaczone dla poszczególnych predykatów IDB. Warstwą predykatu A jest liczba krawędzi z negacją znajdujących się na ścieżce zaczynającej się w wierzchołku A.

W przypadku rekurencji warstwowej można określić kolejność obliczania predykatów IDB w porządku warstw, poczynając od najmniejszej. Dzięki takiej strategii można określić jeden z minimalnych punktów stałych reguły. A co jest jeszcze ważniejsze, to wyliczanie predykatów IDB w kolejności wyznaczonej przez warstwy zawsze ma sens i prowadzi do określenia „prawidłowego” punktu stałego. W przeciwieństwie do przypadku takiego, jak opisano w przykładzie 4.40, kiedy niewarstwowa rckurcncja doprowadziła do określenia wielu możliwych rozwiązań, nic dostarczając przy tym możliwości określenia właściwego.

PR/.YKł.AI) 4 41

Na rysunku 4.24 przedstawiono graf predykatów z przykładu 4.39. Predykaty UAłączy i AAłączy znajdują się w warstwie 0. ponieważ nie prowadzi od nich żadna krawędź z negacją. Z kolei predykat UAr yl -io jest w warstwie 1, ponieważ prowadzą od niego ścieżki z jedną krawędzią z negacją, a nie ma ścieżek z w iększą ich liczbą. A zatem predykat UAtylko zostanie wyznaczony przed predykatami UAł Aczy i AAłączy.

Przypomnijmy sobie teraz przykład 4.40 i skonstruujmy graf z predykatami P i Q z tego przykładu. Przedstawiono go na rys. 4.25. Z P do Q wiedzie krawędź z negacją, ponieważ w regule I w nagłówku znajduje się predykat P,

UAtylko

RYSUNEK 4 21

Graf utw orzony dla rckurcncji warstwowej

RYSUNEK 4 25

Graf utworzony dla rckurcncji mcwarstwowcj

a Q w podjadaniu / negacją. Z kolei od Q do P także wiedzie krawędź z negacją. ponieważ w regule 2 predykat Q jest zapisany w nagłówku, a predykat P w podzadaniu zanegowanym. Czyli w grafie występuje cykl / zanegowaną krawędzią i w takim grafie nie da się określić warstw.

4.4.5. Ćwiczenia do podrozdziału 4.4

Ćwiczenie 4.4.1. Jeżeli do diagramu /. rys. 4.19 dołączymy krawędzie lub jakieś krawędzie usuniemy, to możemy zmienić wartości relacji Dostępne z przykładu 4.37, relacji Połączenia / przykładu 4.38 lub relacji UAiączy i AA łączy z przykładu 4.39. Podaj nowe wartości tych relacji, jeśli:

•a) Zostanie dodana krawędź od Cl II do SF z etykietą AA. 1900 2100.

b)    Zostanie dodana krawędź od N Y do DEN z etykietą U A. 900 1100.

c)    Zostaną dodane obie te krawędzie.

d)    Zostanie usunięta krawędź z DEN do DAL.

Ćwiczenie 4.4.2. Zapisz reguły w Datalogu (stosując negację warstwową, jeśli negacja jest konieczna), któro opisują następujące modyfikacje pojęcia „następny” z przykładu 4.33. Można kor/ysiać przy tym ze zdefiniowanych w przykładzie 4.36 relacji EDB Kolejny oraz relacji IDB Następny.

*a) P(x, y) zachodzi, gdy y jest odcinkiem następującym po odcinku x, ale nie jest bezpośrednio kolejnym odcinkiem po x (w znaczeniu Kole jny zdefiniowanym w relacji EDB)

b) Q(x, y) zachodzi, gdy _mv następuje po x, ale nie w bezpośredniej kolejności. ani nie jako kolejno trzeci po x.

!c) R {x) zachodzi, gdy po x wyprodukowano co najmniej dwa następne odcinki.

Oba mogą być następnymi kolejnymi odcinkami, ale nie tworzą łańcucha.

!d) S(x, y) zachodzi, gdy y następuje po x, ale i po y jest jeszcze jakiś odcinek.

Ćwiczenie 4.4.3. Klasy i związki w ODE można opisać jako relację Re? 1 (klasa, pklaaa, wiol). W Lei określa wiclowartościowość związku, dla wiclowartościo-wych związków ma wartość wie.1, a dla pojedynczych jod. Pierwsze dwa atrybuty określają powiązane ze sobą klasy, związek jest określony w kierunku od klasy do pklasy (klasy powiązanej). Na rysunku 4.26 przedstawiono relację Rei zawierającą trzy klasy ODL z przykładu dotyczącego filmu, których zapis w ODE przedstawiono na rys. 2.6.