37648 ullman116 (2)

4 DZIAŁANIA W MODELU RELACYJNYM

4.3.5. Selekcja

Operacja selekcji jest w przypadku ogólnym trudniejsza do wyrażenia w notacji Datalogu niż operacje poprzednie. Zaczniemy od przypadku prostego. gdy warunek wyboru jest koniunkcją dwóch lub większej liczby porównań arytmetycznych. Wówczas tworzymy regułę w następujący sposób:

1. Jedno podzadanic odpowiada relacji, z której dokonujemy selekcji. W tym atomie występują oddzielne zmienne dla poszczególnych składowych. odpowiadające atrybutom relacji.

2. Dla każdego warunku operacji selekcji tworzymy odpowiadające tym operacjom podzadania arytmetyczne. Nazwom atrybutów z warunków wyboru muszą odpowiadać w podzadaniach arytmetycznych nazwy zmiennych, które zostały powiązane z atrybutami w podzadaniu relacyjnym.

PRZYKŁAD 4.24

Operacje selekcji z przykładu 4.4

Ojh.K“*‘ i 100 AND - Yo*<Film)

w Datalogu zapiszemy w postaci następującej reguły:

S(t, y, 1, c, s, p) — Film(t, y, 1, c, s, p) AND 1 £ 100 AND s - 'Fox'

Wynikiem jest tutaj relacja S. Zmienne / oraz s odpowiadają atrybutom długość i nazwaStud-ia w porządku, który został określony w relacji Film.

□

Teraz zajmiemy się operacją selekcji dla przypadku warunku zc spójnikiem OK. Instrukcji selekcji nie musimy zastępować dokładnie jedną regułą Selekcja w przypadku alternatywy dwóch warunków jest równoważna wykonaniu selekcji dla poszczególnych warunków osobno, a potem utworzeniu sumy wyników. Zatem selekcja przy warunku zadanym jako alternatywa // warunków może zostać wyrażona przez n selekcji, a nagłówek każdej z nich zawiera ten sam predykat; /-ta reguła służy do określenia wyniku Mego /. kolei spośród // warunków.

PRZYKŁAD 4.25

Operację selekcji z przykładu 4.24 zmodyfikowano w ten sposób, żc zamiast spójnika AND wstawiono OR, w wyniku powstało następujące wyrażenie wyboru:

Nas7.c zadanie polega na podaniu wszystkich filmów, które albo są długie, albo produkcji studia Fox. Dla każdego / tych warunków określamy osobną regułę:

Sit, y, 1, c, a, p) ♦- FilmU, y, 1, c, s, p) AND 1 i 100

S (t, y, 1, c, s, p) — y, 1, c, s, p) AND s - 'Fox'

Wynikiem reguły pierwszej są wszystkie filmy, które trwają co najmniej 100 minut, a reguły drugiej filmy wyprodukowane w studiu Fox.

□

Używając kombinacji spójników logicznych AND, OR i NO", można tworzyć bardzo złożone warunki wyboru. Każde takie wyrażenie /łożone możni z kolei przekształcić, korzystając ze znanej, aczkolwiek pominiętej w naszyn opisie, techniki, do tak zwanej ..postaci normalnej koniunkcji’- czyli ko niunkcji połączonych spójnikiem or. Z kolei koniwikcja jest zbiorem litera łów połączonych spójnikami AND, gdzie literał jest albo porównaniem, albę negacją porównania¹.

Literały możemy traktować jako podzadania, czasem poprzedzone spój nikiem NOT. Jeśli podzadanie jest arytmetyczne, to spójnik NOT możni wkomponować w- znak porównania. Na przykład wyrażenie NOT x £ 10C można zapisać jako x < 100. Każdą koniunkcję można przedstawić w postać pojedynczej reguły Datalogu, w której każde podzadanie jest jednym porów naniem. W końcu każde wyrażenie w postaci normalnej koniunkcyjncj możni przedstawić jako ciąg reguł Datalogu, po jednej regule dla każdej koniunkcji Wynikiem jest suma (inaczej alternatywa OR) wyników poszczególnych reguł

PRZYKŁAD 4.26

Już w' przykładzie 4.15 było przedstawione proste użycie tego algorytmu Bardziej skomplikowany przykład otrzymamy, zaprzeczając warunków z tamtego przy kładu. Wówczas powstaje następujące wyrażenie:

tżjłoT (Ulugnić ? 100 ok nazwa$tmcbo - Tox'»( film)

Polecenie to należy odczytać jako: wyszukać te wszystkie filmy, które trwaj krótko (nic są długie) i nie były wy produkowane w studio Fox.

Spójnik NOT poprzedza tu wyrażenie złożone. Trzeba go wprowadzić d wewnętrznej części wyrażenia, co w takich przypadkach jest możliwe prze zastosowanie prawa De Morgana, które stanowi, ż.c negacja alternatywy jeł równoważna koniunkcji negacji. Dzięki temu nasze wyrażenie selekcji mc żerny przepisać do następującej postaci:

0(_;;y_T (długołe > I00» AMD (NOT( - 'fox'))( ^ i 1 ^m)

Zobacz także np. A. V. Aho i J t). Ullman: Foundation of Computer Science. Computi Science Press, New York. 1992.