15172 ullman119 (2)

ZHH 4 DZIAŁANIA W MODF.UJ Rl I.ACYJNYM

1. W(t, y, i, c, s, p) - Film(t, y, 1, c, s, p) AND 1 £ 100

2. X(t, y, 1, c, s, p) - Fi Im (t, y, 1, c, s, p) AND s » 'Fox'

3.    Y (t, y, 1, c, s, p) - W(t, y, 1, c, a, p)

AND X(t, y, 1, C/ s, p)

4.    Ztt, y) - Y (t# y, 1, c, 5, p)

RYSUNEK 4.15 Reguły Datalogu

Następna reguła (3) definiuje relację Y jako pr/ccięcie relacji W oraz X i przyjmuje ona postać, którą opisano w p. 4.3.1. Ostatnia reguła (4) definiuje predykat Z. jako rzutowanie relacji y na atrybuty tytuł oraz rok. Do zapisu rzutowania zastosowano tu sposób opisany w p. 4.3.4. Predykat Z jest „odpo-wiedzią”, tzn. że bez względu na zawartość relacji Fi lm, relacja, którą opisuje ten predykat, jest taka sama jak relacja, która powstaje w w yniku przetw orzenia wyrażenia algebraicznego, przekształconego na samym początku.

W rozważanym przykładzie można by było w regule (4) z rys. 4.15 zastąpić podzadanie )' treścią reguły (3). Potem można zastąpić podzadania W \X treścią reguł odpowiednio numer (1) i (2). Ponieważ podzadanie Fi im występuje w obu składnikach, zatem jedną kopię możemy usunąć. W wyniku otrzymamy następującą regułę, która definiuje predykat Z:

Z(t, y) — Film (t, y, 1, c, s, p) AND 1 £ 100

AND s - 'Fox'

Taki przypadek, kiedy złożone wyrażenie algebraiczne opisuje się jedną, równoważną regułą Datalogu, spotyka się jednak rzadko.

□

/

4.3.9. Ćwiczenia do podrozdziału 4.3

Ćwiczenie 4.3.1. Niech dane będą trzy następujące relacje: R(a, h, c), S(a. h_y c) oraz T\a, b, c) Poniższe wyrażenia algebry relacji należy zapisać w postaci równoważnych reguł Datalogu:

a)    RkjS

b)    RnS

c)    R-S

•d) (RvS)-T !c) (R-S)n(R-T)

0 *a.h(R)

*IH)    M r\ a*,. /.)(.(-SD)

Ćw iczenie 4.3.2. Niech dana będzie relacja R(x, y, :). Należy utworzyć regułę lub reguły Datalogu. które definiują operacje n,{R). gdzie C jest następującym warunkiem:

a) x^my

•b) X <>’ANDy <Z

c)    x <yORy<z

d)    NOT (x < y OR x > y)

♦!e) NOT ((x <y OR x >y) AND>‘ < r)

!0 NOT ((x <y OR x < z) ANDy< z)

Ćwiczenie 4.3.3. Niech będą dane trzy następujące relacje: R(u, b, c). S(b, c, d) oraz 7\d, e). Dla każdego z poniższych złączeń naturalnych należy utworzyć po jednej regule Datalogu:

a)    R c*i S

b)    S T

!c) (R ckj S) oc 7*. (Uwaga: kolejność wykonywania łych złączeń nie ma znaczenia, ponieważ złączenie naturalne jest operacją łączną i przemienną).

Ćwiczenie 4.3.4. Niech dane będą dwie następujące relacje: R(x, y z) oraz S(pc, y z). Należy utworzyć regułę lub reguły Datalogu, które definiują operację złączenia teta Rt<cS. Ćwiczenie należy wykonać kolejno dla warunków sformułowanych w ćwiczeniu 3.3.2. Porównania arytmetyczne należy interpretować w ten sposób, że argument z lewej strony wyrażenia odpow iada atrybutowi z relacji R, a argument z prawej strony wyrażenia odpowiada atrybutowi z relacji S. Na przykład wyrażenie x < y należy interpretować jako R.x < S.y.

JĆwłczcnlc 4.3.5. Reguły Datalogu można przekształcać do postaci równoważnych im wyrażeń algebraicznych. Nie omawialiśmy żadnych metod postępowania w tym zakresie, można jednak wykonać kilka prostych przykładów. Dla każdej z następujących reguł należy utworzyć równoważne jej wyrażenie algebraiczne, które definiuje relację odpowiadającą predykatowi z nagłówka reguły.

•a)    P(x,    y)    Q(x,    z)    AND    R(z,    y)

b)    P(x,    y)    4-    Q(x,    z)    AND    Q(z,    y)

c)    P(x,    y)    <-    Q(x,    z)    AND    R{z,    y)    AND x < y

4.4. Programowanie rekurcncyjne w Datalogu

Pomimo ż.c w algebrze relacji można wyrazić wiele różnych użytecznych operacji na relacjach, to istnieją takie zadania, których nic można opisać wyrażeniami tej algebry. Taki rodzaj popularnych zadań, których nic da się zapisać w algebrze relacji, stanowią zadania rekurcncyjne, które powodują powstawanie nieskończonego ciągu coraz bardziej złożonych wyrażeń.

PRZYKŁAD 4.33

Dobrym przykładem rckurencji w przypadku przemysłu filmowego są seriale Jeśli jakiś film odnosi sukces, to produkuje się jego następny odcinek. Jeśli ta