4

Dziabania w modelu relacyjnym

W bieżącym rozdziale przedstawimy bazy danych z punktu widzenia użyt­kownika. Najczęściej główne działanie użytkownika polega na przeszukiwaniu bazy danych, to znaczy na pisaniu programów, których wyniki są odpowie­dziami na pytania związane z bieżącą instancją bazy danych. W rozdziale czwartym nauczymy się definiowania zapytań do bazy danych w sposób ode­rwany od konkretnych zastosowań, przez użycie pewnych operatorów zapytań.

W metodach stosowanych w modelu ODL korzysta się z dowolnych ope­ratorów przetwarzania danych, w modelach związków encji także nie okre­ślono żadnej specyfiki dla operowania na danych, natomiast w modelu rela­cyjnym istnieje ograniczony zestaw „standardowych" operacji na danych. A zatem skoncentrujemy uwagę na nauczeniu się operowania na danych w modelu relacyjnym, bez względu na to, jakie dane te modele opisują. Ope­racje na danych są definiowane w sposób algebraiczny i tworzą tzw. „algebrę relacji". Stosuje się w tym celu formalizm logiki, i ten rodzaj opisu nazwano „Datalog". Obie te notacje poznamy w bieżącym rozdziale.

W następnych rozdziałach opiszemy współczesne komercyjne systemy baz danych w zakresie języków i możliwości oferowanych uźytkownikowi. W rozdziałach od 5 do 7 opisano operatory zapytań występujące w języku zapytań SQL. Podobne operatory występują również w języku OQL, który opisano w rozdziale 8.

4.1. Algebra dzialań na relacj ach

Jako pierwsze działania na relacjach poznamy te operacje algebYy relacji, które obejmują metody tworzenia nowych, bardziej skomplikowanych relacji na podstawie innego zbioru relacji. Pojęcie wyrażenia w algebrze relacji po­czątkowo sprowadza się do operandu, relację można przedstawić albo prrzez jej nazwę (np. R lub Film), albo przez podanie jej knotek. Następnie, stosując

4.1. ALGEBRA DZIAŁAŃ NA RELACJACH ZO7

różne, opisane poniżej operatory algebry albo do relacji, albo do prostszych wyrażeń algebry relacji, można tworzyć nowe, coraz bardziej skomplikowane wyrażenia. Zapytanie jest wyrażeniem algebry relacji. Dlatego też algebra relacji jest pierwszym podstawowym przykładem języka zapytań.

Operacje w algebrze relacji można podzielić na cztery szerokie kategorie:

1. Zwyczajne działania algebry zbiorów: suma, przecięcie i różnica za­stosowane do relacji.

2. Operacje zawężania relacji: selekcja eliminuje pewne wiersze, a rzu­towanie niektóre kolumny.

3. Operacje komponowania krotek z innych krotek pochodzących z róż­nych relacji, na przykład „iloczyn kartezjański", który tworzy wszyst­kie możliwe kombinacje par krotek pochodzących z dwóch różnych relacji lub różne warianty operacji złączenia, która w sposób selek­tywny łączy w pary krotki z dwóch różnych relacji.

4. Operacje „przemianowania", które nie zmieniają krotek relacji, ale jej schemat, tzn. nazwy atrybutów lub/ i nazwę samej relacji.

Zakres tych działań jest dość ograniczony, nie wystarczą one do wyko­nania wszystkich możliwych obliczeń dla relacji. Mimo to jednak, posługując się nimi, można wykonać prawie wszystko, co jest potrzebne w bazach da­nych i stanowią one, jak przekonamy się w rozdziale 5, dużą część standar­dowego języka zapytań baz danych SQL. Natomiast w podrozdziałach 4.6 i 4.7 przedstawimy pokrótce pewne możliwości tkwiące w języku SQL, ale które nie występująca algebrze relacji.

4.1.1. Działania teoriomnogościowe w zastosowaniu do relacji

Trzy najpopularniejsze operacje teoriomnogościowe stanowią suma, przecięcie i różnica zbiorów. Czytelnicy powinni znać te operacje z podsta­wowego kursu matematyki, tutaj przytoczymy tylko definicje, przy założeniu, że dane są dwa zbiory R i S:

• R u .S'- suma zbiorów R i S jest zbiorem elementów, z których każdy należy do zbioru R lub do zbioru S, lub do obu naraz. Jeżeli jakiś ele­ment należy do obu zbiorów R i S, to w sumie tych zbiorów występuje tylko jeden raz.

• R n S- przecięcie zbiorów R i S jest takim zbiorem, do którego nale­żą tylko te elementy, które występują zarówno w zbiorze S, jak i w zbiorze R.

• R - S - różnica zbiorów R i S to zbiór, do którego należą tylko te ele­menty ze zbioru R, które nie należą do zbioru S. Zwróćmy uwagę na

~OÓ 4. DZIALANIA W MODELU RELACYJNYM

to, że zbiór R - S jest różny od zbioru S - R. Ten drugi zawiera tylko te elementy zbioru S, które nie należą do zbioru R.

Relacje R i S, do których można zastosować operacje teoriomnogościo­we, muszą spekniać następujące warunki:

1. Schematy relacji R i S muszą mieć identyczne zbiory atrybutów.

2. Zanim zostanie obliczona teoriomnogościowa suma, przecięcie lub róż­nica zbiorów krotek, należy uporządkować atrybuty relacji R i S w ten sposób, aby w obu relacjach kolejność atrybutów była taka sama.

Może się zdarzyć czasem, że trzeba utworzyć sumę, przecięcie lub różni­cę relacji, które mają taką samą liczbę atrybutów, ale różniących się ich na­zwami. Jeśli tak się zdarzy, to można skorzystać z operatora przemianowania, który omówiono w p. 4.1.8, i dzięki temu zmienić schemat jednej lub obu relacj i w taki sposób, aby ich zbiór atrybutów był taki sam.

PRZI'KŁAD 4.1

Niech będądane dwie relacje R i S, które są instancjami relacji GwiazdaFil­mowa z podrozdziału 3.9. Te instancje R i S przedstawiono na rys. 4.1.

nazwisko I adres

Carrie Fisher 123 Maple St., Hollywood F Mark Hamill 456 Oak Rd., Brentwood M Relacja R

nazwisko

Carrie Fisher Harrison Ford

adres 123 Maple St., Hollywood F 789 Palm. Dr., M Beverly Hills

Relacja S

RYSUNEK 4.1 Dwie relacje

Sumątych dwóch relacji jest poniższa nowa relacja:

nazwisko I adres

Carrie Fisher 123 Maple St., Hollywood K Mark Hami11 456 Oak Rd., Brentwood M Harrison Ford 789 Palm Dr., M Beverly Hills

eć dataUrodzenia 9/9/99 818/88

dataUrodzehia

919199 7/7177

dataUrodzenia 919/99 8/8/88 7/7/77

Zauważmy, że krotka dotycząca Carrie Fisher, która występuje w obu rela­cjach wejściowych, w wyniku pojawia się tylko jeden raz.

4.1. ALGEBRA DZIAŁAŃ NA RELACJACH

Przecięciem R i S jest poniższa relacja:

209

nazwisko adres łeć dataUrodzenia Carrie Fisher 123 Maple St., Hollywood K 9/9/99

Tutaj występuje tylko krotka z Carrie Fisher, ponieważ tylko ta krotka wystę­puje w obu relacjach: R i S.

Różnica R - S jest następująca:

nazwisko adres leć dataUrodzenia Mark Hamill 456 Oak Rd., Brentwood M 8/8/88

Krotki z opisem gwiazd Fisher i Hamill występują w R, a zatem są potencjal­nymi kandydatami dla R - S. Jednakże, ponieważ krotka Fisher występuje również w S, więc nie ma jej w różnicy R - S.

0

4.1.2. Rzutowanie

Z operatora rzutowania korzysta się przy tworzeniu nowej relacji, która po­wstaje z relacji R przez usunięcie z niej pewnych kolumn. Wartością wyrażenia ~al,az,..., a~,(R) jest relacja, która powstaje z R przez przepisanie wszystkich atry­butów AI, Az, ..., An. W wyniku powstaje schemat obejmujący zadany zbiór atry­butów {AI, Az, ..., An}, występujących w takim porządku, w jakim je zadano.

tul rok dłu ość cz Kolor nazwaStudia roducentC#

Gwiezdne Wojny 1977 124 kolor Fox 12345

Potężne Kaczory 1991 104 kolor Disney 67890

Świat Wayne'a 1992 95 kolor Paramount 99999

RYSUNEK 4.2 Relacja Filml

PRZYKŁAD 4.2

Rozważmy relację Film, której schemat został opisany w podrozdziale 3.9. Instancję tej relacji pokazano na rys. 4.2. Wyrażenie:

~(ylul, rnk, d/ugo.ść(Film~

opisuje operację rzutowania relacji Film na pierwsze trzy atrybuty. W wyniku tej operacji powstaje następująca relacja:

tytul rok dlugość

Gwiezdne wojny 1977 124

Potężne Kaczory 1991 104

Świat Wayne'a 1992 95

2 I O 4. DZIAŁANIA W MODELU RELACYJNYM

Inny przykład zastosowania rzutowania polega na obliczeniu wyrażenia ~~. yK„,„r(Film). Otrzymujemy wówczas relację o jednej kolumnie:

czyKolor

prawda

W wynikowej relacji występuje tylko jedna krotka, ponieważ na rys. 4.2 wszyst­kie trzy krotki majątaką samą wartość składowej dla atrybutu czyKolor.

0

4.1.3. Selekcja

W wyniku zastosowania operatora selekcji do relacji R powstaje nowa relacja, do której należy pewien podzbiór knotek relacji R. Knotki w relacji wynikowej są wybierane według kryterium określonego przez pewien waru­nek C narzucony na atrybuty relacji R. Tę operację oznaczamy symbolem ~~-(R). Schemat relacji wynikowej nie różni się niczym od schematu relacji R, a porządek atrybutów zostaje też zachowany.

C stanowi wyrażenie warunkowe tworzone podobnie do wyrażeń warun­kowych w językach programowania, na przykład tych, które występują po słowie If w konwencjonalnych językach programowania, takich jak Pascal lub C. Jedyna różnica polega na tym, że w wyrażeniu algebraicznym operan­dami mogą być tylko albo stałe, albo atrybuty relacji R. Wartość wyrażenia C jest obliczana po kolei dla każdej knotki t z R w ten sposób, że w miejsce atrybutu w C podstawia się wartość składowej knotki t dla tego atrybutu. Jeśli po zastąpieniu wszystkich atrybutów odpowiednimi wartościami z knotki wy­rażenie przyjmuje wartość prawda, to wówczas knotka t jest dołączana do wynikowego zbioru operacji o-~.(R), w przeciwnym przypadku knotka t nie będzie należała do relacji wynikowej.

PRZYKŁAD 4.3

Załóżmy, że relacja Film wygląda tak jak na rys. 4.2. Wówczas wartością wyrażenia 6~~u~~.5<<.> Ioo(Fi1m) jest następująca relacja:

tul Yok dlu ość cz Kolor nazwaStudia roducentC#

Gwiezdne Wojny 1977 124 ( prawda I Fox 1 12345

Potężne Kaczory 1991 104 `( prawda Disney 67890

Warunek dlugość >_ 100 jest spełniony przez pierwszą krotkę, ponieważ gdy zamiast nazwy dlugość wstawimy 124, co jest wartością składowej atry­butu długość z pierwszej knotki, otrzymamy nierówność 124 >_ 100, co jest prawdą. Możemy zatem umieścić pierwszą krotkę w zbiorze wynikowym. W ten sam sposób należy tłumaczyć, dlaczego druga knotka z rys. 4.2 także została tam umieszczona.

4.1. ALGEBRA DZIAŁAŃ NA RELACJACH 21 1

W trzeciej krotce wartość składowej dla atrybutu długość wynosi 95. Jeśli podstawimy tę wartość zamiast nazwy dlugość do warunku, to otrzyma­my wyrażenie 95 >_ 100, które jest nieprawdziwe. Dlatego ostatnia krotka z rys. 4.2 nie jest wynikiem.

0

PRZYKŁAD 4.4

Chcemy teraz wyszukać te krotki relacji:

Film (tytuł, rok, długość, czyKolor, nazwaStudia, produ­centC#)

w których producentem jest wytwórnia Fox i które trwają co najmniej .100 minut. Wówczas trzeba utworzyć warunek bardziej złożony, do którego nale­żą dwa warunki połączone spójnikiem logicznym AND. Wyrażenie to przyjmie następującą postać:

~dlugośC >_ 100 AND nazwaStndia = Fox( F ~- l m)

Jedynie krotka:

tut rok dlu Gwiezdne Wojny 1977 124

cz Kolor nazwaStudia roduc prawda Fox 12345

występuje w relacji wynikowej.

0

4.1.4. Iloczyn kartezjański

' Iloczynem kartezjańskim (lub produktem) zbiorów R i S nazywa się zbiór wszystkich par uporządkowanych, z których pierwszy element pary należy do zbioru R, a drugi do zbioru S. Taki iloczyn oznacza się symbolem R x S. De­finicja nie zmienia się, gdy zbiorami są relacje. Jednak ponieważ elementami R i S są w takim przypadku krotki, w których może występować wiele skła­dowych, więc w wyniku utworzenia pary krotek z jednej krotki S i jednej R

' otrzymuje się nową, dłuższą krotkę, która zawiera wszystkie składowe z kro­tek, które wchodzą w skład pary. W wynikowej krotce wszystkie składowe z krotki R występują przed składowymi krotki z S.

Schemat relacji wynikowej jest sumą schematów relacji R i S. Ale jeśli zdarzy się tak, że pewne atrybuty powtarzają się w obu schematach, to co naj­mniej dla jednego z powtarzających się atrybutów trzeba wprowadzić nową nazwę. Aby odróżniać identyczne atrybuty A z relacji R i S, wprowadza się oznaczenie S.A dla atrybutu A w relacji S oraz R.A dla atrybutu A w relacj i R.

212

A B

1 2 3 4

Relacja R

B C D

2 5 6

4 7 I 8

9 10 11

Relacja S

A R.B S.B C D

1 2 2 5 6

1 2 4 7 8

1 2 9 10 11

3 4 2 5 6

3 4 4 7 8

3 4 9 10 11

Wynik R x S

RYSUNEK 4.3

Dwie relacje i ich iloczyn kartezjański

PRZYKŁAD 4.5

4. DZIAŁANIA W MODELU RELACYJNYM

Aby uczynić nasz przykład zwięźlejszym, zilustrujemy pojęcie iloczynu kar­tezjańskiego w sposób oderwany od konkretnych danych. Niech schematy i krotki relacji R i S będą takie, jak przedstawiono na rys. 4.3. Wówczas do iloczynu kartezjańskiego należy sześć krotek, które również przedstawiono na tym rysunku. Zwróćmy uwagę na to, jak powstały pary utworzone z każdej z dwóch krotek relacji R z każdą z trzech krotek relacji S. Ponieważ atrybut B występuje w obu relacjach, zatem w schemacie R x S trzeba było użyć ozna­czeń R.B oraz S.B. Nazwy pozostałych atrybutów są jednoznaczne, więc w schemacie wynikowym pozostają bez zmian.

0

4.1.5. Zlączenie naturalne

Znacznie częściej niż iloczyny kartezjańskie trzeba realizować połącze­nia relacji przez tworzenie par krotek, które w jakiś sposób odpowiadają so­bie. Najprostszy sposób polega na wykonaniu, oznaczanej symbolem R ~a S, operacji naturalnego zlc~czenia dwóch relacji R i S, która polega na połączeniu w pary tych krotek z relacji R oraz S, które mają identyczne wartości dla okre­ślonych atrybutów. Aby omówić to dokładniej, załóżmy, że atrybuty AI, Az,

OG ~O

v~ ~d? d~ O

G,

4.1. ALGEBRA DZIAŁAŃ NA RELACJACH 213

..., A„ występują w obu schematach relacji: w schemacie R oraz w schema­cie S. Wówczas krotka r z relacji R zostanie połączona w parę z krotką s z relacji S, jeśli wartości składowych r i s są takie same dla atrybutów A1 ~ Az~ ..., A„.

Jeśli w złączeniu R ~a S występują krotki r oraz s, to wynikowa krotka nazywa się krotkc~ z~c~czonc~; składa się ona ze składowych dla atrybutów po­wstałych w wyniku sumowania schematów relacji R i S. Krotka złączona ma takie same wartości składowych co krotka r dla atrybutów ze schematu R oraz takie same jak krotka s dla atrybutów ze schematu S. Ponieważ ta nowa krotka została utworzona w wyniku złączenia, więc dla atrybutów, które występują w obu schematach R i S, wartości krotek r i s muszą być takie same. A zatem krotka wynikowa musi mieć również wartości takie same w składowych dla atrybutów wspólnych w obu schematach R i S. Sposób tworzenia krotki złą­czonej pokazano na rys. 4.4.

R

S

Zwróćmy tutaj uwagę na fakt, że opisana powyżej operacja złączenia jest tą samą operacją, którą wykonywaliśmy przy odtwarzaniu relacji rzutowanej na dwa podzbiory atrybutów i którą opisaliśmy w p. 3.7.6. Wówczas służyła ona do uzasadnienia sensowności metody dekompozycji do postaci BCNF. W punkcie 4.1.7 zostanie przedstawiony jeszcze inny sposób użycia operacji złączenia naturalnego, tj. takie połączenie dwóch relacji, aby można było napisać zapytanie o dowolną kombinację atrybutów.

PRZYKŁAD 4.6

Poniżej zamieszczono wynik operacji złączenia naturalnego relacji R i S, przedstawionych na rysunku 43

A B C D

1 2 I 5 I 6

3 4 7 8

RYSUNEK 4.4 Złączenie krotek

214 4. DZIAŁANIA W MODELU RELACYJNYM

Jedynym wspólnym atrybutem obu relacji S i R jest atrybut B. Aby zatem utworzyć właściwe pary krotek, krotki muszą mieć takie same wartości w składowych odpowiadających atrybutowi B. A jeśli tak, to krotki wyniku zawierają składowe dla następujących atrybutów: A (z R), B (albo z R, albo z S), C (z S) oraz D (z S).

W naszym przykładzie pierwszą krotkę z R można połączyć wyłącznie z pierwszą krotką z S, ponieważ mają obie wartość 2 dla wspólnego atrybutu B. Stąd otrzymuje się pierwszą krotkę wyniku: (l, 2, 5, 6). Drugą krotkę z R można z kolei połączyć wyłącznie z drugą krotką z S i w wyniku powstaje krotka (3, 4, 7, 8). Natomiast trzecia krotka z S już nie może być połączona w parę z żadną krotką z relacji R, a więc nie wpływa ona na wynik złączenia R ~ S. Taka krotka, której nie można połączyć z żadną krotką z drugiej rela­cji,jest czasami określana mianem knotki wiszącej.

0 PRZYKŁAD 4.7

W poprzednim przykładzie nie dało się przedstawić pełnego spektrum możli­wości ukrytych w operacji złączenia naturalnego. Na przykład nie było tam knotek, które dało się łączyć z wieloma knotkami z drugiej relacji, a poza tym wspólny dla obu relacji był tylko jeden atrybut. Na rysunku 4.5 przedstawiono inne relacje: U oraz V, w których występują dwa wspólne atrybuty B i C. Do­brano także takie wartości atrybutów w instancjach, aby jedna knotka łączyła się z kilkoma innymi.

A B C 1 2 3 6 7 8 9 7 8

Relacja U

B C D 2 3 4 2 3 5 7 8 10

Relacja V

A B C D

1 2 3 4

1 2 3 5

6 7 8 10

9 7 8 10

Wynik U ~a V

RYSUNEK 4.5

Złączenie naturalne relacji

4. 1. ALGEBRA DZIAŁAŃ NA RELACJACH 21 S

Aby utworzyć połączenie krotek, muszą one mieć takie same wartości dla obu atrybutów: B oraz C. A zatem pierwsza krotka U łączy się z dwiema pierwszymi krotkami z V, a druga i trzecia krotka z U łączy się z trzecią krot­ką z V. Wynik tego złączenia przedstawiono na rys. 4.5.

0

4.1.6. Złączenie teta

W operacji złączenia naturalnego korzysta się zawsze z tego samego kryterium wyboru krotek. Mimo że ten sposób, gdy wybiera się krotki o rów­nych wartościach dla wspólnych atrybutów, jest najpowszechniejszy przy łączeniu relacji, to jednak czasami jest konieczne połączenie krotek przy za­daniu innego kryterium łączenia. Dlatego powstała operacja złc~czenia teta, gdzie teta określa zadany warunek łączenia krotek, który my jednak będzie­my oznaczać raczej literą C, a nie literą B.

Połączenie typu teta relacji R i S oznaczamy symbolem R ~a~~ S. Wynik takiego złączenia definiuje się następująco:

1. Utworzyć iloczyn kartezjański relacji R i S.

2. Z iloczynu kartezjańskiego wybrać tylko te krotki, dla których waru­nek C jest spełniony.

Tak samo jak to było w przypadku operacji iloczynu, schemat utworzo­nej w ten sposób relacji jest sumą schematów relacji R oraz S, przy czym atrybuty o takiej samej nazwie poprzedza się odpowiednio R. lub S., aby w ten sposób oznaczyć, z której relacji pochodząwartości tych atrybutów.

PRZYKŁAD 4.8

Rozważmy operację U ~aA<o V, gdzie relacje U i V są przedstawione na rys. 4.5. Trzeba rozważyć wszystkie dziewięć ~aAw par krotek, czyli wszyst­kie możliwości tworzenia par dla tych relacji, a następnie sprawdzić, czy składowa A krotki U jest mniejsza od składowej D z krotki V. Pierwsza krotka z U, której składowa dla A wynosi 1, łączy się z wszystkimi krotkami z V. Natomiast krotki z U: druga i trzecia, których składowe dla atrybutu A wyno­szą odpowiednio 6 i 9, mogą zostać połączone tylko z ostatnią krotką relacji V. Dlatego w wynikowej relacji jest tylko S krotek, które powstają z pięciu połączeń. Wynik złączenia przedstawiono na rys. 4.6.

0

Zauważmy, że w schemacie umieszczonym na rys. 4.6 występuje wszystkie 6 atrybutów, przy czym oznaczono atrybuty B i C prefiksami, które wskazują, z której relacji U czy V pochodzą ich wartości. To właśnie różni złączenie teta od złączenia naturalnego, w którego wyniku występuje tylko

216

4. DZIALANIA W MODELU RELACY.fNYM

A U.B U.C V.B V.C D

1 2 3 2 3 4

1 2 3 2 3 5

1 2 3 7 8 10

6 7 8 7 8 10

9 7 8 7 8 10

RYSUNEK 4.6 Wynik U ~aA~,~ V

jedna kopia atrybutów łączących. Oczywiście powielenie atrybutów nie ma sensu w przypadku złączenia naturalnego, bo tam wartości wspólnych atry­butów są równe. W przypadku złączenia teta nie ma gwarancji, że porówny­wane atrybuty mają takie same wartości, ponieważ operator porównania może być inny niż =.

PRZYKŁAD 4.9

Poniżej przedstawiamy bardziej złożony warunek złączenia teta relacji U i V:

U D4,q~p złtvD t>.B zVB

A zatem w każdej krotce złączenia składowa dla atrybutu A krotki U musi być mniejsza od składowej atrybutu D krotki V, a ponadto w obu krotkach warto­ści atrybutu B muszą być różne. Jedynie krotka

A ~ U.B ~ U.C , V.B f V.C ~ D 1 2 3 7 8 10

spełnia jednocześnie te oba warunki, a więc powyższa relacja stanowi wynik złączenia teta, które zostało zdefiniowane powyżej.

0

4.1.7. Tworzenie zapytań z po~ączonych operacji

Algebra relacji nie byłaby tak użyteczna, gdyby były dopuszczalne tylko pojedyncze operacje na relacji lub na dwóch relacjach. Ale algebra relacji, tak jak wszystkie inne algebry, umożliwia tworzenie dowolnie złożonych wyrażeń przez zastosowanie operatorów albo do danych relacji, albo do wyników otrzymanych z zastosowania jednego lub wielu operatorów do jednej lub wielu relacji.

W wyrażeniach algebry relacji można grupować operacje przez umiesz­czanie nawiasów, które oddzielają podwyrażenia oraz umożliwiają bardziej precyzyjne określenie kolejności wykonywania poszczegółnych operacji. Można także przedstawiać wyrażenia w postaci drzew podwyrażeń, czasami nawet jest w ten sposób łatwiej odczytać kolejność wykonywania działań, a poza tym jest to notacja stosowana do reprezentowania wyrażeń algebry w zapisie maszynowym.

4.1. ALGEBRA DZIAŁAŃ NA RELACJACH 217

PRZYKŁAD 4.10

Rozważmy ponownie dekomponowaną relację Film z przykładu 3.32. Chce­my otrzymać odpowiedź na pytanie: „Jakie są wszystkie tytuły i lata produk­cji filmów wyprodukowanych przez wytwórnię Fox, które trwają co najmniej 100 minut?" Kolejność wykonywania operacji, prowadzących do uzyskania odpowiedzi, może być następująca:

1. Wybrać te krotki relacji Film, w których d~ugość >_ 100.

2. Wybrać te krotki relacji Film, w których nazwaStudia = `Fox'. 3. Policzyć przecięcie wyników z (1) i (2).

4. Zrzutować wynik z (3) na atrybuty tytuł i rok.

Na rysunku 4.7 przedstawiono powyższe punkty w postaci drzewa. Dwa wierzchołki wyboru odpowiadają punktom (1) i (2). Wierzchołek przecięcia odpowiada punktowi (3), a wierzchołek rzutowania punktowi (4).

tytuł, rok

n

6długość >_ 100 ónazwaStudia = ~FOX~

Film Film

RYSUNEK 4.7

Drzewo wyrażenia utworzone dla wyrażenia algebry relacji

Można także zapisać to wyrażenie w sposób konwencjonalny, liniowy, sto­sując w tym celu nawiasy. Wówczas przyjmie ono postać następującej formuły:

~ytul, rok(ódlugość>_100 (F11m) n 6nazwaStudW -'FOx'(F11m))

Może się zdarzyć, ze ten sam proces obliczeniowy można zapisać w po­staci różnych wyrażeń algebry relacji. Na przykład powyższe wyrażenie moż­na zapisać jako inne wyrażenie, w którym zamiast przecięcia występuje spój­nik AND w warunku wyboru. A zatem alternatywna postać wyrażenia wygląda następująco:

~ylul, rnk\6d/ugośL2100 ANDnazwaStudia='Fox'(Fllm))

CJ

218 4. DZIALANIA W MODELU RELACYJNYM

Wyrażenia równoważne i optymalizacja zapytań

W wielu systemach baz danych korzysta się z systemów zapytań, które zawierają języki zapytań zbliżone, w zakresie mocy obliczeniowej, do al­gebry relacji. A zatem zapytanie utworzone przez użytkownika można przeksztalcać w sposób równoważny i otrzymać w ten sposób wiele rów­noważnych wyrażeń (tzn. wyrażeń, które dają ten sam wynik, jeśli operują na tych samych relacjach), różniących się czasem przetwarzania. W punk­cie 1.2.3 omawialiśmy pokrótce „optymalizator zapytań", którego glówne zadanie polega na zastąpieniu wyrażenia algebry relacji wyrażeniem rów­noważnym, które można przetworzyć w sposób bardziej efektywny.

PRZYKŁAD 4.11

Ważnym zastosowaniem operacji zlączenia naturalnego jest rekonstrukcja oryginalnej relacji z relacji otrzymanych w wyniku jej dekompozycji do po­staci BCNF. Przypomnijmy sobie, jak wyglądały relacje otrzymane w wyniku przekształceń w przykładzie 3.32:

Filml o Schenlacle {tytuł, rok, długość, typFilmu, nazwaStu­dia}

Film2 o schemacie {tytuł, rok, nawiskoGwiazdy}

Spróbujmy teraz zapisać zapytanie „Wyszukać gwiazdy tych filmów, które trwają dlużej niż 100 minut". W tym zapytaniu powiązano atrybut nazwi­skoGwiazdy z relacji Filml z atrybutem długość z relacji Film2. Można polączyć te atrybuty przez wykonanie złączenia tych dwóch relacji. W złą­czeniu naturalnym zostaną powiązane ze sobą te krotki, które dotyczą tego samego filmu, a zatem w których wartości atrybutów tytuł i rok majątakie same wartości w obu relacjach. Czyli wyrażenie z algebry relacji Filml >~ Film2 daje w wyniku relację, którą w przykładzie 3.32 nazywaliśmy Film. Nie ma ona postaci BCNF, ponieważ zawiera wszystkie sześć atrybutów oraz występują w niej krotki opisujące ten sam film, jeśli wystąpiło w tym filmie kilka gwiazd.

Teraz do złączenia relacji Filml i Film2 zastosujemy operator wyboru, który wymusza wybór tylko tych filmów, które trwają nie krócej niż 100 mi­nut. Potem trzeba wykonać rzutowanie na określony w zapytaniu zbiór atry­butów: tytuł i rok. Poniżej przedstawiamy wyrażenie algebry relacyjnej, opisujące zadane zapytanie:

~tytul, rok(6dlugaść?100 (F11m1 D4 Fllm2~~

O

" Relacja Film w tamtym przykładzie różniła się od relacji Film, opisanej w podroz­dziale 3.9 i z której korzystaliśmy w przykładach 4.2, 4.3 i 4.4.

4.1. ALGEBRA DZIAŁAŃ NA RELACJACH 219

4.1.8. Przemianowanie

Aby nazwy atrybutów wchodzących w skład relacji nie doprowadzały do nieporozumień w przypadku tworzenia zlożonych wyrażeń algebry relacji, w których występuje wiele relacji i wiele operatorów, często bywa wygodnie utworzyć nowe nazwy dla pewnych atrybutów lub dla relacji. Symbolem pS~AI, A2, __., Ani (R) oznaczymy przemianowanie relacji R., W wyniku otrzymuje się relację, do której należą te same krotki co do relacji R, ale nazwą nowej relacji jest S. Atrybuty otrzymują nazwy: A1, A2,, ..., A„, a ich porządek jest zachowany z relacji oryginalnej. Jeśli zmiana ma dotyczyć tylko nazwy rela­cji, a nazwy atrybutów mają pozostać bez zmian, to stosujemy zapis ps{R).

PRZYKŁAD 4.12

Przy tworzeniu iloczynu kartezjańskiego relacji R i S w przykładzie 4.5 sto­sowaliśmy konwencję pozwalającą odróżniać tak samo nazywane atrybuty z różnych relacji przez dopisywanie przed nimi nazw relacji, z których te atrybuty pochodzą. Na rysunku 4.8 przedstawiono ponownie relacje R i S.

A B 1 2 3 4

Relacja R

B C D 2 5 6 4 7 8 9 10 11

Relacja S

A B X C D 1 2 2 5 6 1 2 4 7 8 1 2 9 10 11 3 4 2 5 6 3 4 4 7 8 3 4 9 10 11 Wynik R x prix c, n~(~

RYSUNEK 4.8

Dwie relacje i ich iloczyn kartezjański

Może się jednak okazać, że oznaczanie atrybutu B odpowiednio przez R.B i S.B jest niewygodne, a lepiej w dalszym ciągu nazywać atrybut B z rela­cji R jako B, natomiast atrybut B z relacji S nazwać inaczej, np. X. Możemy

22O 4. DZIAŁANIA W MODELU RELACYJNYM

tak wykonać przemianowanie relacji S, aby jej pierwszy atrybut nazywał się X W wyniku przetworzenia wyrażenia ps~X, ~~,,~~(S) powstaje relacja S, która wygląda dokładnie jak relacja S z rys. 4.3, a jedynie różni się od oryginału nazwą pierwszej kolumny, którą jest atrybut X.

Jeśli tworzymy teraz iloczyn kartezjański S i R, to nie występuje już kon­flikt między nazwami atrybutów tych relacji, a więc nie potrzeba już stosować przemianowania. Wynikiem przetworzenia wyrażenia R x p5~x c., o~(,Ś) jest pra­wie taka sama relacja jak R x S z rys. 4.3 poza tym, że kolumny mają teraz nazwy: A, B, X, C oraz D. Tę nową relacje przedstawiono na rys. 4.8.

Inny sposób otrzymania tego samego wyniku polega na utworzeniu ilo­czymu kartezjańskiego przed przemianowaniem jak w przykładzie 4.5, a na­stępnie przemianowanie wyniku. Wyrażenie pzS~A,,3,x, ~,,~~(R x S) opisuje także relację przedstawioną na rys. 4.8, z takim samym zbiorem atrybutów, wyłącz­nie jej nazwa RS jest inna niż na rys. 4.8.

0

4.1.9. Operacje zależne i niezależne

Niektóre operacje, opisane w podrozdziale 4.1, można przedstawić za pomocą innych operacji algebry relacji. Na przykład przecięcie można przed­stawić jako zfiożenie różnic:

RnS=R-(R-,S~

A zatem, jeśli relacje R i S mają ten sam schemat, to ich iloczyn można obli­czyć, tworząc nową relację T, która jest różnicą między R i S, a więc zawiera krotki R nie należące do S. Jeśli teraz od R odejmiemy T, to pozostaną tylko krotki, które są zarówno w R, jak i w S.

Oba złączenia także można przedstawić w postaci złożenia innych operacji. Złączenie teta można przedstawić jako kombinację iloczynu kartezjań­skiego i selekcji:

R ~~~ S = ~~~(R x S)

Z kolei złączenie naturalne relacji R oraz S można otrzymać również, zaczy­nając od utworzenia iloczynu kartezjańskiego R x S. Potem należy wykonać operacje selekcji z warunkiem C, który ma postać:

R.A~ = S.A, AND R.A~ = S.AZ AND ... AND R.A„ = S.A„

a atrybuty A~, AZ, ..., A„ są wszystkimi atrybutami występującymi jednocze­śnie w obu relacjach R i S. W końcu trzeba odrzucić po jednej kopii powielo­nych atrybutów. Niech L oznacza zbiór atrybutów z relacji R oraz zbiór tych atrybutów relacji S, które nie występują w R. Wówczas:

R da S = ~l ( o-c (R x ,S~)

4.1. ALGEBRA DZIAŁAŃ NA RELACJACH ZZ I

PRZYKŁAD 4.13

Złączenie naturalne relacji U i V z rys. 4.5 można zapisać za pomocą operato­rów iloczynu kartezjańskiego selekcji oraz projekcji jako:

~A, U.B, (LC,D~ 6UB = V.B 1aND U.C = V.C ~ U X • l)

Najpierw tworzy się iloczyn kartezjański Ux V. Potem wybieramy te krotki, w których wartości par atrybutów o takich samych nazwach, tutaj B i C, pokry­wają się. W końcu wykonujemy rzutowanie na wszystkie atrybuty poza poje­dynczymi kopiami B oraz C, w tym przypadku wyeliminowaliśmy parę atry­butów B i C z relacji V, których nazwy występująrównież w schemacie U.

Aby podać jeszcze inny przykład, zapiszemy złączenie teta z przykła­du 4.9 jako:

6A<nAt~pU.BxVB~UX

Tutaj tworzymy iloczyn kartezjański relacji U i V, a następnie stosujemy se­lekcję określoną warunkiem zlączenia teta.

D

Nadmiarowość operatorów, którą opisaliśmy powyżej, jest jedynym ro­dzajem nadmiarowości, jaki występuje wśród zdefiniowanych operatorów. Pozostałe sześć operacji: suma, różnica, selekcja, rzutowanie, iloczyn karte­zjański i przemianowanie jest wzajemnie niezależne, żadnej z nich nie można przedstawić jako kombinacji pięciu pozostałych.

4.1.10. Ćwiczenia do podrozdziaku 4.1

Ćwiczenie 4.1.1. W tym ćwiczeniu przedstawimy nowy przykład schematu relacyjnej bazy danych i pewne przykkadowe dane. Schemat tej bazy skkada się z następujących schematów relacji:

Produkt (producent, model, typ)

PC (model, szybkość, ram, hd, cd, cena)

Laptop (model, szybkość, ram, hd, ekran, cena) Drukarka (model, kolor, typ, cena)

Relacja Produkt opisuje produkty, określając ich producenta, numer modelu oraz typ (PC, laptop lub drukarka). Dla ukatwienia przyjmujemy, że numery modeli są jednoznaczne i niezależne od producentów i typów. Takie zakożenie daleko odbiega od realiów i w bazach danych, z których korzysta się w rzeczywistości, trzeba w podobnych przypadkach podawać kod producenta, jako część identyfikacji pro­duktu. W relacji Pc dla każdego modelu jest określona szybkość procesora w mega­hercach, wielkość pamięci operacyjnej w megabajtach (RAM), pojemność dysku

22Z 4. DZIAŁANIA W MODELU RELACYJNYM

twardego (hd) w gigabajtach oraz szybkość napędu cD (np. 4x), a także cena. Podob­ne parametry są określone w relacji Laptop, a dodatkowo można tam odnaleźć wiel­kość ekranu w calach, zamiast występującej w poprzedniej relacji szybkości napędu cD. W relacji drukarka model drukarki jest opisany przez atrybut kolor, określający, czy można otrzymać kolorowy wydruk (jeśli tak, to wartością tego atrybutu jest prawda), atrybut typ, którego wartość opisuje technikę drukowania (laser, atramento­wa lub mozaikowa), a także atrybut cena.

producent ~ model ~ typ

A A A B B B B C C D D

D D D D D D E E F G G H I

1001 1002 1003 1004 1006 3002 3004 1005 1007 1008 1009 1010 2001 2002 2003 3001 3003 2004 2008 2005 2006 2007 3005 3 0 0'6

RYSUNEK 4.9

Przykładowe dane relacji Produkt

PC PC PC PC PC drukarka

drukarka PC

PC PC PC i PC laptop

laptop laptop drukarka drukarka laptop laptop laptop laptop laptop drukarka drukarka

Na rysunku 4.9 przedstawiono pewne przykładowe dane relacji produkt. Przy­kłady danych pozostałych trzech relacji przedstawiono na rys. 4.10. Dane dotyczące producenta i numery modeli zostały mocno uproszczone, ale dane techniczne pro­duktów są typowe dla tego, co można było znaleźć na rynku przy końcu 1996 r.

Należy napisać wyrażenia algebry relacji, które służą do określenia zapytań, opi­sanych poniżej. Należy również podać wyniki tych zapytań dla przykładowych da­nych z rys. 4.9 i 4.10. Ale wyrażenia powinny być zapisane dla dowolnych danych, niezależnie od tych przykładów. Wskazówka: W przypadkach bardziej skomplikowa­nych zapytań może się okazać pomocne utworzenie dodatkowych relacji pośrednich,

R

4.1. ALGEBRA DZIAŁAŃ NA RELACJACH

model sz bkość ram hd cd cena

1001 133 16 1.6 6x 1595

1002 120 16 1.6 6x 1399

1003 166 24 2.5 6x 1899

1004 166 32 2.5 8x 1999

1005 166 16 2.0 8x 1999

1006 200 32 3.1 8x 2099

1007 200 32 3.2 8x 2349

1008 180 32 2.0 8x 3699

1009 200 32 2.5 8x 2599

1010 160 16 1.2 8x 1495

a) Przykładowe dane relacji PC

model sz bkość ram hd ekran cena

2001 100 20 1.10 9.5 1999

2002 117 1~2 0.75 11.3 2499

2003 117 32 1.00 10.4 3599

2004 133 16 1.10 11.2 3499

2005 133 16 1.00 11.3 2599

2006 120 8 0.81 12.1 1999

2007 150 16 1.35 12.1 4799

2008 120 16 1.10 12.1 2099

b) Przykładowe dane relacji Laptop

model kolor cena

3001 prawda atrament 275

3002 prawda atrament 269

3003 fałsz laser 829

3004 fałsz laser 879

3005 fałsz atrament 180

3006 prawda mozaikowa X470

c) Przykladowe dane relacji Drukarka

RYSUNEK 4.10

Przykładowe dane relacji z ćwiczenia 4.1.1

223

określonych w terminach relacji oryginalnych, a następnie zapisanie wyrażenia za pomocą relacji pośredniej. Potem w tak zapisanym wyrażeniu należy zastąpić tę relację pośrednią jej definicją i w ten sposób przedstawić ostateczną postać wyra­żenia.

*a) Podać modele PC, których szybkość zegara wynosi co najmniej 150 MHz. b) Podać tych producentów, którzy wytwarzają laptopy z dyskami twardymi o pojemności co najmniej 1 gigabajta.

224 4. DZIAŁANIA W MODELU RELACYJNYM

c) Podać numery modeli i ceny wszystkich produktów (dowolnych typów) wytwarzanych przez producenta B.

d) Podać numery modeli wszystkich kolorowych drukarek.

e) Wybrać wszystkich producentów, którzy sprzedają laptopy, a nie sprzedają PC.

*!~ Wskazać te twarde dyski, które występują w co najmniej dwóch typach PC.

!g) Wybrać pary modeli PC, które mają te same szybkości zegara oraz wielkość RAM. Każdą parę należy wymienić tylko jeden raz, tzn. jeśli wystąpi para (i, j), to para (j, i) nie powinna być wybierana.

*!!h) Wybrać producentów, którzy wytwarzają co najmniej dwa różne modele (PC lub laptopy) z szybkościami zegara co najmniej 133 MHz.

!!i) Wybrać producentów, którzy wytwarzają komputery (PC lub laptopy) o największych częstotliwościach zegara.

!!j) Wybrać producentów, którzy wytwarzają PC z co najmniej trzema różnymi zegarami.

!!k) Wybrać producentów, którzy wytwarzają dokładnie trzy różne modele PC.

Ćwiczenie 4.1.2. Dla każdego wyrażenia utworzonego w ćwiczeniu 4.1.1 należy narysować jego drzewo.

Ćwiczenie 4.1.3. W tym ćwiczeniu przedstawimy nowy przykład, dotyczący okrętów z czasów drugiej wojny światowej. Obejmuje on następujące relacje:

Klasy (klasa, typ, kraj, liczbaDział, działo, wyporność) Okręt (nazwa, klasa, wodowanie)

Bitwa (nazwa, data)

Rezultat (okręt, bitwa, wynik)

Okręty, które budowano z tych samych projektów, tworzą klasę okrętów, której nazwa pokrywa się z nazwą pierwszego okrętu powstałego dla danej klasy. W rela­cji Klasy zapisuje się nazwę klasy, typ (bb dla określenia okrętu liniowego lub bc dla określenia krążownika liniowego), kraj, w którym powstał dany typ okrętów, liczbę największych dział, kaliber ich największych dział (określany w calach) oraz wyporność (jako wagę w tonach). W relacji okręt zapisuje się nazwy poszczegól­nych egzemplarzy okrętów, nazwę klasy oraz rok wodowania. W relacji Bitwa określa się, w których bitwach uczestniczyły określone okręty, a w relacji Rezu1­tat jest zapisywane, co stało się z określonym okrętem w danej bitwie (zatopiony, uszkodzony lub ok).

Przykładowe dane tych czterech relacji zostały umieszczone na rys. 4.11 i 4.12. W tym przykładzie występują pewne krotki wiszące, jakich nie było w poprzednim schemacie, tzn. występują pewne okręty w relacji Rezultat, których nie zdefinio­wano w relacji okręt.

i " Żródlo: J.N. Westwood: l=ighting Ships of YVorld War Il. Follett Publishing, Chicago, 197 oraz R.C. Steru: US Battleships in action. Squadron/Signal Publications, Carrollton, TX, 1980.

4.1. ALGEBRA DZIAŁAŃ NA RELACJACH

225

klasa ty kra' liczbaDział średnica w orność

Bismarck bb Niemcy 8 15 42000

Iowa bb USA 9 16 46000

Kongo bc Japonia 8 14 32000

North Carolina bb USA 9 16 37000

Renown bc Wielka 6 15 32000

Brytania

Revenge bb Wielka 8 15 29000

Brytania

Tennessee bb USA 12 14 32000

Yamato bb Japonia 9 18 65000

a) Przykładowe dane relacji Kl a s y

nazwa data North Atlantic 5/24-27/41 Guadalcanal 11/15/42 North Cape 12/26/43 Surigao Strait 10/25/44

b) Przykładowe dane relacji Bitwa

okręt bitwa w ny ik

Bismarck North Atlantic zatopiony

California Surigao Strait ok

Dulce of York North Cape ok

Fuso Surigao~Strait zatopiony

Hood North Atlantic zatopiony

King George V North Atlantic ok

Kirishima Guadalcanal zatopiony

Prince of Wales North Atlantic uszkodzony

Rodney North Atlantic ok

Scharnhorst North Cape zatopiony

South Dakota Guadalcanal uszkodzony

Tennessee Surigao Strait ok

Washington Guadalcanal ok

West Virginia Surigao Strait ok

Yamashiro Surigao Strait zatopiony

c) Przykładowe dane relacji Rezultat

RYSUNEK 4.11

Dane do ćwiczenia 4.1.3

226 4. DZIAŁANIA W MODELU RELACYJNYM

nazwa klasa wodowanie

California Tennessee 1921

Haruna Kongo 1915

Hiei Kongo 1914

Iowa Iowa 1943

Kirishima Kongo 1915

Kongo Kongo 1913

Missouri Iowa 1944

Musashi Yamato 1942

New Jersey Iowa 1943

North Carolina North Carolina 1941

Ramillies Revenge 1917

Renown Renown 1916

Repulse Renown 1916

Resolution Revenge 1916

Revenge Revenge 1916

F.oyal Oak Revenge 1916

Royal Sovereign Revenge 1916

Tennessee Tennessee 1920

Washington North Carolina 1941

Wisconsin Iowa 1944

Yamato Yamato 1941

RYSUNEK 4.12

Przykładowe dane relacji okręt

Należy napisać wyrażenia albebry relacj i, które służą do określenia zapytań opi­sanych poniżej. Należy również podać wyniki tych zapytań dla przykładowych da­nych z rys. 4.1 1 i 4.12. Ale wyrażenia powinny być zapisane dla dowolnych danych, niezależnie od przykładów:

a) Podać nazwy klas oraz kraje klas, których działa były co najmniej 16 calo­we.

b) Wymienić okręty zwodowane przed 1921 r.

c) Wymienić wszystkie okręty zatopione w bitwie o północny Atlantyk.

d) W 1921 r. w Traktacie Waszyngtońskim zabroniono produkcji okrętów o wyporności większej niż 35 000 ton. Wyszukać okręty, których parametry naruszają Traktat Waszyngtoński.

e) Podać nazwę, wyporność oraz liczbę dział okrętów, które brały udział w bitwie o Guadalcanal.

Podać wszystkie okręty umieszczone w bazie (należy przy tym pamiętać, że nie wszystkie występują w relacji Okręt).

!g) Wymienić wszystkie klasy, w których występuje tylko jeden okręt.

!h) Wymienić te kraje, które produkowały zarówno okręty liniowe, jak i krą­żowniki liniowe.

!i) Wyszukać te statki, które „dożyły innej bitwy", tzn. zostały uszkodzone w pewnej bitwie, ale potem uczestniczyły jeszcze winnej bitwie.

42. LOGIKA RELACJI ZZ%

Cwiczenie 4.1.4. Dla każdego wyrażenia utworzonego w ćwiczeniu 4.1.3 należy narysować jego drzewo.

*Ćwiczenie 4.1.5. Określić, jaka jest różnica między naturalnym złączeniem relacji R ~a S oraz złączeniem teta tych relacji R ~a~. S, gdy warunkiem C jest R.A -S.A dla wszystkich atrybutów A, występujących w obu schematach zarówno R, jak i S.

!Ćwiczenie 4.1.6. Mówimy, ze operator określony dla relacji jest monotoniczny wów­czas, gdy dołączenie do pewnego argumentu (pewnej relacji) tego operatora powo­duje, że w relacji wynikowej są wszystkie te same krotki co poprzednio oraz być może jeszcze inne krotki. Które z operatorów zdefiniowanych w bieżącym rozdziale są monotoniczne? Dla operatorów, które nie są monotoniczne, pokazać przykłady, które uzasadniają dlaczego te operatory nie są monotoniczne?

!Ćwiczenie 4.1.7. Niech w relacji R będzie n krotek, a w relacji S m krotek. Należy określić maksymalną i minimalną liczbę krotek, które powstają jako wynik poniż­szych operacji:

*a) RAS. b) R~aS

c) a-~(R) x S, gdzie C jest dowolnym warunkiem.

d) ~~,(R) - S, gdzie L jest listą dowolnych atrybutów.

!Ćwiczenie 4.1.8. Podzłączeniem relacji R i S, które oznacza się jako R ~a S, jest zbiór tych krotek z relacji R, dla których istnieje co najmniej jedna krotka w relacji s, mająca takie same wartości dla atrybutów wspólnych obu relacji R i S. Należy podać przykłady co najmniej trzech wyrażeń algebry relacji, które są równoważne operacji R ~a S.

!!Cwiczenie 4.1.9. Niech (A,, Az, ..., A„, B,, BZ, .., B„,) określa schemat relacji R, a (B,, BZ, ..., B„,) określa schemat relacji S, tzn. atrybuty relacji S są podzbiorem zbio­ru atrybutów relacji R. Ilorazem relacji R i S, który oznaczamy symbolem R = S, jest zbiór krotek t, mających składowe tylko dla atrybutów A,, AZ, ..., A„ (tzn. tych atry­butów relacji R, które nie są atrybutami relacji S) oraz które mają taką właściwość, że dla każdej krotki s z relacji S krotka ts, złożona ze składowych krotki t dla atrybutów A,, A2, ..., A„, oraz ze składowych krotki s dla atrybutów B,, Bz, ..., B„,, stanowi zaw­sze pewną krotkę relacji R. Należy podać jakieś wyrażenie z algebry relacji, złożone z opisanych poprzednio operatorów, które jest równoważne R = S.

4.2. Logika relacji

Zapytania do baz danych można opisywać obok formalizmu algebraicz­nego także za pomocą formalizmu logiki. W obu tych notacjach można wyra­żać zapytania z tej samej klasy. Język zapytań w formalizmie logiki, który zamierzamy omówić w bieżącym rozdziale, nazywany Datalogie~n (database logic - logika baz danych), składa się z reguł typu jeśli - to. W takich regu­

ZZÓ 4. DZIAŁANIA W MODELU RELACY.INYM

łach zapisuje się na przykład, że jeśli w pewnej relacji występuje jakaś okre­ślona kombinacja krotek, to można wnioskować, że w innej określonej relacji na pewno występuje pewna określona krotka.

4.2.1. Predykaty i atomy

W Datalogu relacje zapisuje się w postaci symboli zwanych predykatami. Każdemu predykatowi przypisuje się charakterystyczną dla niego liczbę ar­gumentów, a zapis, w którym występuje nazwa predykatu oraz jego argu­menty, nazywa się atomem. Syntaktyka atomu jest taka jak syntaktyka wy­wołania funkcji w konwencjonalnych językach programowania, na przykład P(xl, xz, ..., x„) oznacza atom złożony z predykatu P oraz jego argumentów xl, xz, ..., xn.

Mówiąc krótko: predykat jest nazwą funkcji logicznej. Jeśli w relacji R jest n atrybutów i został ustalony ich porządek, to nazwy R można używać również do oznaczenia predykatu odpowiadającego tej relacji. Wówczas atom R(al, az, ..., an) przyjmuje wartość PRAWDA, jeśli (a,, a2, ..., a„) jest krotką, która należy do R, w przeciwnym przypadku wartością tego atomu jest FAŁSZ.

PR'Z.YKŁAD 4.14

Niech będzie dana następująca relacja R z rys. 4.3.

A B 1 2 3 4

Wówczas R(1, 2) ma wartość PRAWDA, taką samą wartość ma R(3, 4). Na­tomiast dla wszystkich innych wartości par (x, y), R(x, y) ma wartość FAŁSZ.

0

Argumentami predykatu mogą być zarówno stałe, jak i zmienne. Jeśli ar­gumentami predykatu są zmienne, to wartość takiej funkcji logicznej jest wy­liczana dla kombinacji wartości wszystkich tych zmiennych.

PKZYKŁAD 4. I S

Jeśli R jest predykatem z przykładu 4.14, to funkcja R(x, y) przyjmuje war­tość, która określa, czy dla danych wartości x oraz y krotka R(x, y) należy do relacji R. W konkretnej instancji relacji R z przykładu 4.14 wartością relacji R jest PRAWDA wówczas, gdy:

l.x= 1 iy=21ub 2.x=3 iy=4

4.2. LOGIKA RELACJI 229

a we wszystkich pozostałych przypadkach wartością tej funkcji jest FAŁSZ. Natomiast atom postaci R(1, z) zwraca wartość PRAWDA, jeśli z = 2, a dla wszystkich innych wartości zmiennej z przyjmuje wartość FAŁSZ.

0

4.2.2. Atomy arytmetyczne

W Datalogu występuje jeszcze inny ważny rodzaj atomów, są to atomy arytmetyczne. W takich atomach występuje porównanie dwóch wyrażeń arytmetycznych, na przyklad: x < y lub x + I >_ y + 4 x z. Dla odróżnienia dwóch rodzajów atomów te, które omawialiśmy poprzednio, będziemy nazy­wać atomami relacyjhymi, niemniej oba wymienione rodzaje są atomami.

Zauważmy, że wszystkie atomy zarówno arytmetyczne, jak i relacyjne, podstawiają wartości zmiennych w miejsce argumentów i zwracają w wyniku pewnąwartość logiczną. A zatem porównanie arytmetyczne, takie jak „<" lub „>_", daje taki wynik jak relacja, która zawiera wszystkie pary spełniające daną zależność arytmetyczną. Stąd też relację „<" można przedstawiać jako taką, która zawiera wszystkie te krotki, w których pierwsza składowa jest mniejsza od drugiej, np. (1, 2) lub (-1.5, 65.4). Pamiętajmy jednak, że w ba­zach danych relacje są zawsze skończone, a poza tym zazwyczaj od czasu do czasu zmieniają się. Natomiast relacje arytmetyczne porównywania argu­mentów sązarówno nieskończone, jak i niezmienne.

4.2.3. Reginy i zapytania w Datalogu

Operacje w Datalogu, których wynik jest taki sam jak wynik odpowied­niej operacji w algebrze relacji, są przedstawiane w postaci regul. Reginy składają się z:

1. atomu relacji, który nazywa się nagłówkiem, a po którym występuje

2. symbol •-, który często czytamy jako ,jeżeli", a po którym z kolei występuje

3. treść, złożona z jednego lub większej liczby atomów, które nazywa się podzadaniami. Podzadania mogą być zarówno atomami aryt­metycznymi, jak i relacyjnymi. Podzadania łączy spójnik logiczny AND (I), a każde z podzadań można poprzedzić symbolem negacji NoT (NIE).

PRZYKŁAD 4.16

Reguły z Datalogu

DługiFilm(t, y) E- Film(t, y, 1, c, s, p) AND 1 >_ 100

23O 4. DZIAŁANIA W MODELU RELACYJNYM

można użyć po to, by wyszukać wszystkie „długie filmy", tzn. takie, które trwają co najmniej 100 minut. Jako źródło danych występuje tu znana już z podrozdziału 3.9 relacja Film, której schemat wygląda następująco:

Film (tytuł, rok, długość, czyKolor, nazwaStudia, pro­ducentC#)

W nagłówku tej reguły występuje atom DlugiFilm(t, y). Jej treść stano­wią dwa podzadania:

i 1. Pierwsze z nich składa się z predykatu Film oraz sześciu argumen­tów, które odpowiadają sześciu atrybutom relacji Film. Poszczególne argumenty występują w postaci następujących zmiennych: t dla ozna­czenia składowej atrybutu tytuł, y- atrybutu rok, l - atrybutu dłu­

g gość itd. To podzadanie można sformułować następująco: „ Układ (t, y, 1, c, s, p) jest krotką z bieżącej instancji relacji Film". A jeszcze dokładniej: Film (t, y, 1, c, s, p) jest prawdą wówczas, gdy wartości wszystkich sześciu zmiennych są składowymi pewnej krotki relacji Fi lm.

2. Wartością drugiego podzadania ( l >- 100 ) jest natomiast prawda wówczas, gdy składowa długość w relacji Film wynosi co najmniej I 100.

Regułę tę można sformułować następująco: DlugiFilm (t, y) jest prawdą wtedy i tylko wtedy, gdy w relacji Film występuje taka krotka, że:

a) jej pierwsze dwie składowe (dla atrybutów tytuł i rok) są równe odpowiednio t orazy,

b) trzecia składowa l (dla atrybutu dlugość) ma co najmniej wartość 100 oraz

c) składowe od czwartej do szóstej mają dowolne wartości.

Ta reguła jest dokładnym odpowiednikiem następującej „instrukcji przy­pisania" z algebry relacji:

D ł u g i F i 1 m = 7~,ylut, ,.~,k( ó~tru~;o.,ćzt oo( F i 1 m))

Prawą stroną jest w tej instrukcji wyrażenie algebry relacji.

0

W formalizmie Datalogu zapytanie jest zbiorem złożonym z jednej lub wielu reguł. Jeśli w nagłówku reguły występuje tylko jedna relacja, to wów­czas jej wartość jest wynikiem zapytania. W przykładzie 4.16 wynikiem za­pytania jest relacja DługiFilm. Jeśli w nagłówku reguły występuje więcej

4.2. LOGIKA RELACJI 23 I

niż jedna relacja, to jedna z nich jest wynikiem zapytania, a reszta uczestniczy w obliczeniu tego wyniku. Zawsze trzeba określić, która z tych relacji ma być wynikiem zapytania, np. przez opisanie jej nazwy słowem wynik.

Zmienne anonimowe

W regułach Datalogu często pewne zmienne występują tylko jeden raz. Nazwy tych zmiennych nie mają wówczas żadnego wpływu na wynik. Na­zwa zmiennej istnieje tylko po to, by można było stwierdzić, że to właśnie o tę zmienną chodzi w jej drugim i ewentualnie dalszych wystąpieniach. Dlatego umożliwimy stosowanie konwencji, w której zamiast argumentu można wpisywać znak podkreślenia , -", co będzie oznaczać, że ta zmien­na występuje w regule tylko jeden raz. Wielokrotne wystąpienie podkre­ślenia w formule oznacza wiele zmiennych, a nie tę samą zmienną. Na przykład reguła z przykładu 4.16 wygląda w tej konwencji następująco:

DługiFilm(t, y) ~ Film (t, y, 1, _, _, _) AND 1 >_ 100

Zmienne c, s i p zostały zastąpione znakami , -", ponieważ w tej regule występują tylko jeden raz. Żadnej innej zmiennej nie można zastąpić w tej regule znakiem podkreślenia, ponieważ wszystkie pozostałe występują tu­taj dwa razy.

4.2.4. Znaczenie regul Datalogu

W przykładzie 4.16 uzyskaliśmy już wskazówkę, w jaki sposób inter­pretować reguły Datalogu. Teraz spróbujemy opisać to dokładniej. Wyobraź­my sobie, że zmienne, które występują w regule, przybierają wszystkie moż­liwe wartości. Jeśli wartości tych zmiennych tworzą taki układ, przy którym wszystkie podzadania mają wartość PRAWDA, to wartości przypisane dla zmiennych z nagłówka tworzą krotkę, którą trzeba dołączyć do relacji wyni­kowej.

Wyobraźmy sobie na przykład, że sześć zmiennych z przykładu 4.16 przebiega zbiory wszystkich możliwych wartości. Jedynie kombinacje warto­ści, które spełniają podzadania (podzadania dla tych wartości mają wartość PRAWDA) tworzą, gdy zapisać je w porządku (t, y, 1, c, s, p), krotki relacji Film. Ponadto, ponieważ podzadanie l _> 100 musi być również prawdziwe, więc w tej krotce wartość dla atrybutu długość, oznaczana przez 1, musi być równa co najmniej 100. Jeśli uda się znaleźć taką kombinację wartości, to wówczas dołączamy krotkę (t, y) do nagłówkowej relacji DługiFilm.

Jednakże na sposób korzystania ze zmiennych w regułach musimy nało­żyć pewne ograniczenia po to, by wynik reguły był relacją skończoną, oraz po

232 4 DZIAŁANIA W MODELU RELACYJNYM

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

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

A zatem, jeśli zmienna występuje w nagłówku, w podzadaniu zaprzeczo­nym lub podzadaniu arytmetycznym, to musi również w tej regule występo­wać 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 >_ 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ę­i pują również w pierwszym podzadaniu w treści reguły. Z kolei zmienna 1, ', która występuje w podzadaniu arytmetycznym, pojawia się również w pierw­szym podzadaniu.

0 PRZYKŁAD 4.18

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

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

l . Zmienna y występuje w nagłówku, ale nie występuje w żadnym po­dzadaniu, które jest zarówno relacyjne, jak i niezaprzeczone. Za­uważmy, że zapis x < y nie ogranicza zakresu wartości zmiennej y do

i 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 po­jawi się nieskończona liczba krotek (a, d), gdzie d > a.

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

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

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

o

4.2. LOGIKA RELACJI 233

Bezpieczeństwo reguł można również określać w inny sposób. Zamiast rozważać wszystkie możliwe przypisania wartości do zmiennych, rozważamy zbiory krotek tych wszystkich podzadań, które są relacyjne i niezaprzeczone. Jeśli pewne przypisanie krotek do wszystkich podzadań niezaprzeczonych i relacyjnych jest niesprzeczne, tzn. każdemu wystąpieniu zmiennej odpowia­da taka sama wartość, to należy zbadać wynikowe przypisanie wartości do wszystkich zmiennych występujących w regule. Jeśli reguła spełnia warunek bezpieczenstwa, to każdej zmiennej jest przypisana pewna wartość.

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

PRZYKŁAD 4.19

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

P (x, y) ~ Q ( x, z) AND R ( z, y) AND NOT Q (x, y) a~ ~Ilj~~

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

Krotka dla Krotka dla Przypisanie NOT Q (x, y) Nagłówek

Q (x, z ) R ( z, y) nies rzeczne? Prawda? piko

1) (1, 2) (2, 3) Tak Nie -

2) (1, 2) (3, 1) Nie; z=2,3 Niewłaściwe -

3) (1, 3) (2, 3) Nie; z = 3,2 Niewłaściwe -

4) (l, 3) (3, 1) Tak Tak P(1, 1)

RYSUNEK 4.13

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

Drugi i trzeci wariant z rys. 4.13 są sprzeczne. W każdym z nich wystę­pują dwie różne wartości przypisane do tej samej zmiennej z. A zatem te wa­rianty 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, 3) do podzadania R(z, y), skąd wynika przypisanie dla zmiennych x, y, z kolejno wartości 1, 3, 2. Następnie spraw­dzamy wynikające z tego przypisania wartości pozostałych podwyrażeń, które

I

234 4. DZIALANIA W MODELU RELACYJNYM

mogą być zaprzeczone lub arytmetyczne. W rozważanej regule występuje tylko jedno takie podzadanie: NoT Q (x, y) . Przy tym przypisaniu otrzymuje ono postać NoT Q (1, 3 ) . Krotka (I, 3) występuje w relacji Q, zatem to pod­zadanie jest fałszywe, a krotka, powstająca z przypisania (1), nie zostaje dołą czopa do nagłówka.

Jako ostatni pozostał wariant (4). Przypisanie jest niesprzeczne: zmien­nym x, y, z odpowiadają kolejno wartości: I, 1 i 3. Podzadanie NOT Q (x, y) przybiera postać NOT Q (1, 1) . Ponieważ krotka (l, 1) nie należy do relacji Q, więc to podzadanie jest prawdziwe. Dla tego przypisania wartości otrzy­mujemy P(1, I) jako wartość nagłówka P(x, y). Krotka (I, I) należy więc do relacji P. Ponieważ zostały zbadane już wszystkie przypisania wartości do zmiennych, więc jest to jedyna krotka wyniku.

0

4.2.5. Predykaty ekstensjonalne i intensjonalne

Często okazuje się, że jest warto odróżniać:

• Predykaty ekstensjonalne, czyli te, których relacje są przechowywane w bazie danych, od

• Predykatów intensjonalnych, których relacje są wyliczane przez sto­sowanie jednej lub wielu reguł Datalogu.

Różnica polega na tym samym co różnica między operandami w wyraże­niach algebry relacji, które są ekstensjonalne (tzn. zdefiniowane przez ich ekstensje, inne określenie dla bieżącej instancji relacji), a relacjami wyliczo­nymi jako wynik pośredni lub końcowy pewnych podwyrażeń; te ostatnie nazywa się intensjonalnymi (tzn. zdefiniowanymi przez programistę).

Mówiąc o regułach Datalogu, będziemy określać relacje jako intensjo­palne lub ekstensjonalne w zależności od tego, czy odpowiadający im predy­kat jest odpowiednio intensjonalny lub ekstensjonalny. Będziemy także uży­wać skrótu IDB od „intensjonalna baza danych", przy wskazywaniu intensjo­nalnych predykatów albo odpowiadających im relacji. W analogiczny sposób oznaczymy skrótowo EDB od „ekstensjonalna baza danych" przy predykatach ! lub relacjach ekstensjonalnych.

y W przykładzie 4.16 Film jest relacją EDB, zdefiniowaną przez swoją ekstensję. Podobnie predykat Filnz jest predykatem EDB. Predykat i relacja ~ługieFilmy są intensjonalne. Predykat EDB nie może występować w na­główku reguły, chyba że występuje również w jej treści. Z kolei predykat IDB może wystąpić w nagłówku reguły i w jej treści oraz w obu miejscach jedno­

, cześnie. Często tworzy się jedną relację przez szereg reguł, z tym samym predykatem w nagłówku każdej z nich. To postępowanie zostało zilustrowane w przykładzie 4.21, przy opisywaniu sumy relacji.

4.3. OD ALGEBRY RELACJI DO DATALOGU 23 5

Zastosowanie ciągu predykatów intensjonalnych umożliwia tworzenie coraz to bardziej skomplikowanych funkcji dla relacji EDB. Ten proces jest podobny do tworzenia wyrażeń algebry relacji za pomocą różnych operato­rów. W następnych rozdziałach poznamy również kilka przykładów stosowa­nia predykatów intensjonalnych.

4.2.6. Ćwiczenia do podrozdziaku 4.2

Ćwiczenie 4.2.1. Każde zapytanie z ćwiczenia 4.1.1 należy zapisać w Datalogu. Na­leży korzystać wyłącznie z reguł bezpiecznych, ale można także korzystać z predy­katów IDB, które są odpowiednikami podwyrażeń w bardziej skomplikowanych wy­rażeniach algebry relacji.

Ćwiczenie 4.2.2. Wszystkie zapytania z ćwiczenia 4.1.3 należy zapisać w Datalogu. Tak samo jak poprzednio należy stosować tylko reguły bezpieczne, ale można także stosować predykaty IDB.

!!Ćwiczenie 4.2.3. Warunek, za pomocą którego definiuje się bezpieczeństwo reguły, wystarcza do tego, aby predykatowi nagłówka odpowiadała relacja skończona, jeśli tylko predykatom podzadań odpowiadąją relacje skończone. Ale sam warunek bez­pieczeństwa jest mocniejszy. Należy podać taki przykład reguły z Datalogu, która nie spełnia warunku bezpieczeństwa, ale jeśli relacje podzadań tej reguły są skończone, to i relacja utworzona dla wynikowego predykatu tej reguły też jest skończona.

4.3. Od algebry relacji do Datalogu

Dzialanie wszystkich operatorów algebry relacji można przedstawić równoważnie w postaci jednej lub kilku reguł Datalogu. W bieżącym roz­dziale po kolei omówimy pod tym kątem wszystkie operatory. Potem opisze­my sposób takiego połączenia regul Datalogu, które pełni te same funkcje co wyrażenie algebraiczne.

4.3.1. Przecięcie

Przecięcie dwóch relacji można przedstawić jako regułę, w której wystę­pują podzadania odpowiadające relacjom z tymi samymi zmiennymi jako argumentami.

PRZYKŁAD 4.20

Skorzystamy tu z relacji R i S, przedstawionych na rys. 4.1. Ich schematy składają się z czterech atrybutów: nazwisko, adres, płeć oraz datauro­dzenia. Przecięcie R i S opisuje następująca reguła Datalogu.

23C) 4. DZIAŁANIA W MODELU RELACYJNYM

I (n, a, g, b) E-- R (n, a, g, b) AND S (n, a, g, b)

Iwystępujące w tej regule jest predykatem typu IDB; odpowiadająca mu relacja po zastosowaniu tej reguły przyjmuje wartość R n S, bowiem, aby krotka dała wartościowanie, przy którym oba podzadania są prawdziwe, ta krotka musi wystąpić jednocześnie w obu relacjach: R i S.

0

4.3.2. Suma

Suma dwóch relacji jest opisywana przez dwie reguły. W każdej z nich atom odpowiadający jednej z relacji występuje jako jedyne podzadanie, a w obu regułach ich nagłówki są takie same i stanowi je predykat IDB. Ar­gumenty w predykacie nagłówka są takie same jak w podzadaniach reguły.

Zmienne mają charakter lokalny dla reguł

Zauważmy, że nazwy zmiennych w regułach są ustalone arbitralnie i nie mają związku z nazwami zmiennych w innych regułach. Każda bowiem regula jest przetwarzana niezależenie od innych i określenie zakresu krotek nagłówka nie zależy od innych reguł. Dlatego możemy na przykład zastą­pić drugą regułę z przykładu 4.21 następującym zapisem:

U (w, x, y, z) f-- S (w, x, y, z)

Pierwszą regułę pozostawimy bez zmian, ale obie reguły w dalszym ciągu opisują sumę relacji R i S. Trzeba natomiast pamiętać o tym, że jeśli zmie­nimy nazwę pewnej zmiennej w jakiejś regule, to musimy zastąpić w ten sam sposób wszystkie wystąpienia tej zmiennej w obrębie tejże reguły. Poza tym wybrana nowa nazwa nie może kolidować z nazwami innych zmiennych w tej regule.

PRZYKŁAD 4.21

Do określenia sumy dwóch relacji R i S, opisanych w przykładzie 4.20, korzy­stamy z dwóch następujących reguł:

1. U(n, a, g, b) E- R(n, a, g, b) 2. U (n, a, g, b) <-- S (n, a, g, b)

Z zapisu (1) wynika, że każda krotka relacji R należy również do relacji Utypu IDB. Z zapisu (2) wynika, że każda krotka relacji S również należy do U. Z obu tych zapisów wynika więc, że każda krotka sumy R u S należy do U. Ponieważ w nagłówku poza relacją U nie ma żadnego innego predykatu, a więc nie moż­na w wyniku stosowania tych reguł uzyskać już żadnych innych krotek, stąd też

4.3. OD ALGEBRY RELACJI DO DATALOGU 23 %

możemy wysnuć wniosek, że relacja U jest dokładnie tym samym co suma R u S `. Ponieważ relacje są zbiorami, więc każda krotka w U występuje tylko jeden raz, nawet jeśli występuje w relacji S oraz relacji R.

4.3.3. Różnica

Różnicę relacji R i S w Datalogu zapisujemy w postaci jednej reguły z jednym negowanym podzadaniem. Znaczy to, że w podzadaniu niezanegowa­nym występuje predykat R, a w negowanym predykat S. W obu podzadaniach oraz w nagkówku występująca charakterze argumentów te same zmienne.

PRZYKŁAD 4.22

Jeśli R i S są relacjami z przykładu 4.20, to wówczas reguła

D (n, a, g, b) <- R (n, a, g, b) AND NOT S (n, a, g, b)

definiuje relację D jako różnicę R - S.

a

4.3.4. Rzutowanie

Do obliczania rzutowania relacji R korzysta się z jednej reguły, w której występuje tylko jedno podzadanie z predykatem R. Argumentami tego podza­dania są różne zmienne, po jednej dla każdego atrybutu relacji. Natomiast w nagłówku występuje atom, którego argumenty odpowiadają elementom z listy rzutowania, a występujątam w zgodnym z niąporządku.

PRZYKŁAD 4.23

Załóżmy, że chcemy wykonać rzutowanie następującej relacji:

Film(tytuł, rok, długość, czyKolor, nazwaStudia, produ­centC#)

na pierwsze trzy atrybuty: tytuł, rok, długość, podobnie jak to było w przykładzie 4.2. W wyniku tego działania powstaje relacja P, zdefiniowana przez następująca regułę:

P(t, y, 1) ~ Film (t, y, 1, c, s, p)

O

" Przy każdym z przykładów w bieżącym rozdziale powinniśmy założy`,, że oprócz zapi­sanych explicite, nie obowiązują w nich żadne inne reguły dla predykatów IDB. .leśli bowiem istniałyby takie, to nie moglibyśmy nic stwierdzić na temat zawartości relacji.

i~'~' I

'~II~,;

238

4.3.5. Selekcja

4. DZIAŁANIA W MODELU RELACYJNYM

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

1. Jedno podzadanie odpowiada relacji, z której dokonujemy selekcji. W tym atomie występują oddzielne zmienne dla poszczególnych skła­dowych, 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 rela­cyjnym.

PRZYKŁAD 4.24

' Operacje selekcji z przykładu 4.4

Sdlugo.lć>_ 100?~NDnazwaSludia='EOx'~F11ITl'

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 l oraz s odpowiadają atrybutom dłu­gość i nazwastudia w porządku, który został określony w relacji Film.

0

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

PRZYKŁAD 4.25

Operację selekcji z przykładu 4.24 zmodyfikowano w ten sposób, że zamiast spójnika At~D wstawiono OR, w wyniku powstało następujące wyrażenie wyboru: ~flngo.Cć ? 100 oR nazwaSludia='FOx'~F11Ii1~

4.3. OD ALGEBRY RELACJI DO DATAL.OGU 239 '

Nasze zadanie polega na podaniu wszystkich filmów, które albo są dłu­

gie, albo produkcji studia Fox. Dla każdego z tych warunków określamy i!! osobną regułę:

S (t, y, 1, c, s, p) <- Film(t, y, 1, c, s, p) AND 1 >_ 100

S (t, y, 1, c, s, p) ~ Film(t, 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.

0

Używając kombinacji spójników logicznych AI~1D, oR i IVOT, można two­rzyć bardzo złożone warunki wyboru. Każde takie wyrażenie złożone można z kolei przekształcić, korzystając ze znanej, aczkolwiek pominiętej w naszym opisie, techniki, do tak zwanej „postaci normalnej koniunkcji"- czyli ko­niunkcji połączonych spójnikiem oR. Z kolei koniunkcja jest zbiorem litera­łów połączonych spójnikami AND, gdzie literał jest albo porównaniem, albo .*

negacją porównania .

Literały możemy traktować jako podzadania, czasem poprzedzone spój­nikiem 1~1oT. Jeśli podzadanie jest arytmetyczne, to spójnik NoT można wkomponować w znak porównania. Na przykład wyrażenie NoT x >- 100 można zapisać jako x < 100. Każdą koniunkcję można przedstawić w postaci 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 koniunkcyjnej można 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 warunkowi z tamtego przykładu. Wówczas powstaje następujące wyrażenie:

6NOT (dlugn.ćL~ ~ 100 OR na_wnS'IUdia='I'ox')(F11m)

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

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

~(NOT(długośś?100))AND (NOT(na_°H~a.S'/urlia='Fox'))(F11m1

` Zobacz także np. A. V. Aho i .l. D. Ullman: hozrndation ojCornputer Sciezace. Cotnputer Science Press, New York, 1992.

Z4O 4. D7IAŁANIA W MODELU RELACYJNYM

A teraz można wprowadzić spójnik NoT do porównania, czego wynikiem jest następujące wyrażenie:

ódlu~n,ćc` < 1001~.NF nazwaStudia x'Fox'~F1lm~

To wyrażenie można już przedstawić jako następującąregułę Datalogu:

S (t, y, 1, c, s, p) ~- Film. (t, y, 1, c, s, p) AND 1 < 100 j AND s ~ `Fox'

,~ o

PRZYKŁAD 4.27 I

Teraz rozważmy podobne wyrażenie, w którym występuje warunek wyboru w postaci negacji koniunkcji. Zastosujemy z kolei drugie prawo De Morgana, - z którego wynika, że negacja koniunkcji jest równoważna alternatywie nega­', cji. Zaczniemy od następującego wyrażenia algebraicznego:

6NOT (dlugo,ćć >100 AND nazwaStudxa='F'ox')~F11m~ i

Oznacza to, że trzeba wybrać te filmy, które ani nie są długie, ani nie wypro­dukowane w studio `Fox'.

Po zastosowaniu prawa De Morgana otrzymujemy równoważną postać:

(NOT (dluKośG >_ 100)) OR (NOT(nazwaStuclia='Fox'))~F11m~

Po wkomponowaniu spójnika 1~1oT do warunku powstaje kolejne wyrażenie równoważne:

ódluKośC < 100 OR nazwa.57uclia x'FOx'~F11m~

W końcu można już utworzyć reguły, które są składnikami sumy logicznej. Przyjmują one następującą postać:

1. S(t, y, 1, c, s, p) <- Film (t, y, 1, c, s, p) AND 1 < 100 2. S(t, y, 1, c, s, p) ~ Film (t, y, 1, c, s, p) AND

s ~ ' Fox'

O 4.3.6. Iloczyn kartezjański

Iloczyn kartezjański dwóch relacji R x S można wyrazić przez jedną re­gułę w notacji Datalogu. Obejmuje ona dwa podzadania, jedno dla S, drugie dla R. W każdym podzadaniu występują różne zmienne, odpowiadające po­

4.3. OD ALGEBRY RELACJI DO DATALOGU Z4I

szczególnym atrybutom relacji R oraz S. W predykacie, występującym w na­główku (jest on typu IDB), znajdują się wszystkie zmienne z obu podzadań, przy czym zmienne z podzadania R są umieszczone przed zmiennymi z po­dzadania S.

PRZYKŁAD 4.28

Rozważmy dwie relacje R i S z przykładu 4.20. Każda ma cztery atrybuty. Poniżej przedstawiamy regułę wyznaczającą relację P, która jest iloczynem kartezjańskim relacji R i S:

P(a, b, c, d, w, x, y, z) E- R(a, b, c, d) AND S(w, x, y, z)

Nazwy zmiennych w podzadaniach wybrano arbitralnie z początku alfabetu do podzadania R i z końca alfabetu do podzadania S. Wszystkie te zmienne występująca nagłówku reguły.

0

4.3.7. Zsączenia

Reguła, która w Datalogu opisuje złączenie naturalne dwóch relacji R i S, bardzo przypomina regułę wyznaczającą iloczyn kartezjański tych relacji. Różnica między nimi polega na tym, że w regule wyznaczającej złączenie R da S trzeba konsekwentnie używać tych samych nazw zmiennych oznacza­jących atrybuty, które powtarzają się w R i w S. Możemy zatem stosować nazwy atrybutów jako nazwy zmiennych. W predykacie nagkówka, który jest typu IDB, każda ze zmiennych występuje tylko jeden raz.

PRZYKŁAD 4.29

Rozważmy dwie relacje R i S o schematach R(A, B) oraz S(B, C, D). Złączenie naturalne można opisać następującąregułą:

J(a, b, c, d) f-- R(a, b) AND S(b, c, d)

Nazwy zmiennych użyte w podzadaniach w naturalny sposób odpowiadają nazwom poszczególnych atrybutów relacji R oraz S.

0

W naturalny sposób można także przedstawić w Datalogu opis złączenia teta. Przyponuujmy tu, że złączenie teta można przedstawić jako iloczyn kar­tezjański połączony z selekcją; opisano to już w p. 4.1.9. Jeśli warunek wybo­ru jest koniunkcją, tzn. są to porównania połączone spójnikiem AND, to można rozpocząć tworzenie reguły od zapisu iloczynu kartezjańskiego, a potem dla każdego porównania dołączyć odpowiadające mu podzadanie arytmetyczne.

242 4. DZIAŁANIA W MODELU RELACYJNYM

PRZYKŁAD 4.30

Rozważmy dwie relacje U(A, B, C) i V(B, C, D) z przykładu 4.9 oraz nastę­pujące złączenie teta:

U ~A<U AtvD (lB ~l~B v

Tę samą operację w Datalogu opisuje następująca reguła: ! J(a, ub, uc, vb, vc, d) ~- U(a, ub, uc) AND V(vb, vc, d)

AND a < d AND ub ~ vb

Nazwa ub odpowiada atrybutowi B z relacji U, podobne znaczenie mają na­zwy vb, uc i vc, a zatem tych sześć atrybutów z obu relacji znalazło swoje odpowiedniki w zmiennych. Dwa pierwsze podzadania służą do opisu relacji, a następne dwa zapewniają spełnienie warunku wyboru, który występuje w złączeniu teta.

0 Jednakże, jeśli warunek złączenia teta nie jest koniunkcją, to trzeba go przekształcić do postaci normalnej koniunkcyjnej, którą opisano już w p. 4.3.5. Następnie dla każdego elementu koniunkcji tworzy się osobną regułę. Z kolei w regule zapisuje się podzadania dla iloczynu kartezjańskiego, a następnie dołącza podzadania dla poszczególnych literałów koniunkcji. Nagłówki wszystkich reguł są takie same, umieszcza się w nich po jednym argumencie, odpowiadającym poszczególnym atrybutom relacji tworzącym złączenie teta.

D .,

PRZYKŁAD 4.31

Teraz tylko nieznacznie zmodyfikujemy wyrażenia algebraiczne z poprzed­niego przykładu. Zastąpimy spójnik AND spójnikiem oR. Ponieważ w tym przykładzie nie występuje negacja, więc wyrażenie jest w postaci normalnej koniunkcyjnej. Są w nim dwie koniunkcje z pojedynczymi literałami. Ma ono następującą postać:

U ~A<D oR C B ~V.B

Korzystając z tej samej konwencji nazywania zmiennych, którą stosowano w przykładzie 4.30, można zapisać następujące reguły:

1. J (a, ub, uc, vb, vc, d) AND a < d

2. J(a, ub, uc, vb, vc, d) AND ub ~ vb

f- U (a, ub, uc) AND V (vb, vc, d)

E- U (a, ub, uc) AND V (vb, vc, d)

4.3. OD ALGEBRY RELACJI DO DATALOGU 243

W każdej regule występują podzadania opisujące obie relacje U oraz V, a także jedno z podzadań warunku złączenia A < Dalbo U.B ~ V.B.

0

4.3.8. Symulowanie operacji złożonych w Datalogu

Regułami Datalogu można opisywać nie tylko proste operacje algebry relacji, ale także dowolnie złożone wyrażenia algebraiczne. Polega to na sprowadzeniu wyrażenia do postaci drzewa, a następnie na tworzeniu po jed­nym predykacie typu IDB dla poszczególnych wierzchołków wewnętrznych drzewa. Te operandy w drzewie, które są ekstensjonalne (tzn. są relacjami w bazie danych), zostają w regule przedstawione jako predykaty. Operandy, które są wierzchołkami wewnętrznymi drzewa, zostają w regule zapisane jako predykaty typu IDB.

PRZYKŁAD 4.32

Rozważmy następujące wyrażenie algebraiczne z przykładu 4.10:

~ty(uJ, rak(ódlugo~f_>100 (F11m~ n ónazwaS(udia='FOx'(F11m)~

Drzewo tego wyrażenia zilustrowano na rys. 4.7. Powtarzamy to na rys. 4.14. Występują tu cztery wierzchołki wewnętrzne, trzeba zatem utworzyć cztery predykaty typu IDB. Każdemu z nich odpowiada jedna reguła Datalogu, wszystkie powstałe reguły przedstawiono na rys. 4.15.

Najniższe dwa wierzchołki wewnętrzne reprezentują pojedyncze opera­cje selekcji z relacji Film typu EDB; do ich odwzorowania tworzymy predy­katy W i X typu IDB. Te operacje selekcji na rys. 4.15 są reprezentowane regułami (1) i (2). Na przykład z reguły (1) wynika, że do relacji W należą te wszystkie filmy relacji Film, które trwająco najmniej 100 minut.

tytuł, rok

n

6długość >_ 100 ónazwaStudia ='FOX~

Film Film

RYSUNEK 4.14 Drzewo wyrażenia

I

244 4. DZIAŁANIA W MODELU RELACYJNYM i

1. W (t, y, 1, c, s, p) ~ Film (t, y, 1, c, s, p) AND 1 >_ 100 I

2. X (t, y, 1, c, s, p) .- Film (t, y, 1, c, s, p) AND s = `Fox' ' 3.Y(t, y, 1, c, s, p) ,- W(t, y, 1, c, s, p)

I AND X (t, y, 1, c, s, p)

4. Z (t. Y) ~- Y (t. Y. 1. C, s, p) RYSUNEK 4.15

Reguły Datalogu

Następna reguła (3) definiuje relację Y jako przecię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 Film, relacja, którą opisuje ten predykat, jest taka sama jak relacja, która powstaje w wyniku przetworze­nia 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 za­stąpić podzadanie Y treścią reguły (3). Potem można zastąpić podzadania W '' iX treścią reguł odpowiednio numer (1) i (2). Ponieważ podzadanie Film

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.

0

4.3.9. Ćwiczenia do podrozdzia~u 4.3

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

a) R u S

b) RnS

c) R-S

*d) (R~~-T

!e) (RW~(R-T)

esu. h(R)

*!g) esu, h(R) n Pu~~. h~~~r~. a(~~

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

4.4. PROGRAMOWANIE REKURENCYJNE W DATALOGU Z4S

a) x =y

*b) x<yANDy<z c) x<yORy<z

d) NOT (x<yORx>y)

*!e) NOT ((x <y 0Rx >y) ANDy <z) !f)NOT((x<yORx<z)ANDy<z)

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

a) R ~a S b) S ~a T

!c) (R ~a S) ~a T. (Uwaga: kolejność wykonywania tych złączeń nie ma zna­czenia, 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(x, y, z). Należy utworzyć regułę lub reguły Datalogu, które definiują operację złączenia teta R ~a~~ S. Ćwiczenie należy wykonać kolejno dla warunków sformułowanych w ćwi­czeniu 3.3.2. Porównania arytmetyczne należy interpretować w ten sposób, że argu­ment z lewej strony wyrażenia odpowiada 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.

!Ćwiczenie 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) E-- Q(x, z) AND R(z, y) b) P(x, y) f- Q(x, z) AND Q(z, y)

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

4.4. Programowanie rekurencyjne w Datalogu

Pomimo że w algebrze relacji można wyrazić wiele różnych użytecznych operacji na relacjach, to istnieją takie zadania, których nie można opisać wy­rażeniami tej algebry. Taki rodzaj popularnych zadań, których nie da się zapi­sać w algebrze relacji, stanowią zadania rekurencyjne, które powodują po­wstawanie nieskończonego ciągu coraz bardziej złożonych wyrażeń.

PRZYKŁAD 4.33

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

246 4. DZIAŁANIA W MODELU RELACYJNYM

nowa część ma powodzenie, to powstaje kolejny odcinek itd. A zatem każdy flm może potencjalnie stanowić początek długiego ciągu innych filmów. Załóżmy, że relacja Kolejny(film, odcinek) zawiera pary złożone z filmu i jego bezpośrednio następnej części. Przykładowe krotki w tej relacji mogą wyglądać następująco:

alm odcinek Rewolwer Rewolwer 2 1/2 Rewolwer 2 1/2 Rewolwer 33 1/3

Można zastosować ogólniejszy zapis następnego filmu, w znaczeniu ko­i lejnego do kolejnego itd. W przedstawionej relacji Rewolwer 33 1/3 nastę­

puje po filmie Rewolwer, ale nie jest kolejnym w znaczeniu użytego tu termi­!' nu „kolejny". Przechowywanie w relacji tylko bezpośrednio kolejnych części służy oszczędności przestrzeni na dysku, a jednocześnie umożliwia określenie właściwego następstwa poszczególnych części, jeśli zajdzie taka potrzeba. W powyższym przykładzie oszczędność jest niewielka, ale już w przypadku pięciu odcieków filmu Rocky pamiętamy o sześć par mniej, a w przypadku 18 odcinków „Piątek trzynastego" już jest o 136 par mniej.

Jednakże sposób tworzenia relacji następstwa z relacji Kolejny nie jest już taki oczywisty. Można tworzyć kolejny do kolejnego przez złączenie rela­cji Kolejny ze sobą. Poniżej przedstawiamy przykład wyrażenia opisującego złączenie naturalne, w którym przemianowano zmienne:

~pierw.rzy, trzeci(PR(pierw.szy, drugi)(KOl e ~ ny) ~4 ~7,5(drugi, trzeci)(KOl e ~ ny))

Przemianowanie zastosowano w tym wyrażeniu dwukrotnie: najpierw argu­menty relacji Kolejny nazywają się pierwszy i drugi, a potem drugi i trzeci. W naturalnym złączeniu otrzymujemy zatem te krotki (m,, m2) i (m3, m4) relacji Kolej ny, w których mz = m3. Z tego złączenia powstają pary (m,, na4). Zauważmy, że m4 jest kolejnym od kolejnego od m,.

Ażeby otrzymać kolejny od kolejnego od kolejnego (np. Rocky i Rocky IV), możemy złączyć ze sobą trzy kopie relacji Kolejny. Ogólniej rzecz uj­mując, można otrzymać i-ty kolejny odcinek, gdzie i jest pewną ustaloną wartością przez wykonanie złączenia i-1 razy. Potem można wykonać opera­cję sumy algebraicznej i w ten sposób otrzymać relacje z zapisem wszystkich 'i następstw (nie tylko bezpośrednich).

Zauważmy jednak, że można tak postępować, tylko gdy wartość i jest z góry ustalona. W algebrze relacji nie można otrzymać „sumy nieskończonej", w której dla dowolnie dhigiego ciągu następstwa można by otrzymać krotkę zawierającą i-ty kolejny odcinek, dla dowolnego, nieograniczonego i. Suma w algebrze relacji jest bowiem zdefiniowana dla dwóch relacji, a nie dla ich nieskończonej liczby. Stosując zatem operator sumowania, skończoną liczbę razy można uzyskać skoń­

4.4. PROGRAMOWANIEREKURENCYJNE W DATALOGU 247

czone wyrażenie algebraiczne - sumę skończonej liczby relacji, nie można nato­miast uzyskać wyrażenia o nieskończonej długości.

0

4.4.1. Operator punktu stałego

Na szczęście nie ma konieczności dołączenia do algebry relacji bałaga­niarskiej konwencji, która umożliwiałaby zapisywanie nieskończonej sumy „podobnych" wyrażeń. Istnieje inny popularny sposób opisania relacji takich jak Następny (x, y) (tzn. film y jest odcinkiem następnym po x w sensie wynikającym z przykładu 4.33), które są tworzone w potencjalnie nieskoń­czonym, ale uporządkowanym procesie z innych relacji, takich jak Kolejny. Utworzymy równanie, w którym relacja Następny jest opisywana przez sa­mą siebie i relację Kolejny, a potem stwierdzimy, że relacja Następny jest najmniejszą relacją (najmniejszym punktem stalym), która spełnia to równanie. Dla oznaczenia faktu, że należy wybrać najmniejszy punkt stały równania, użyjemy symbolu

PRZYKŁAD 4.34

Poniżej przedstawiamy zastosowanie operatora punktu stałego w równaniu, które opisuje relację Następny (x, y)

Następny = pK„r~~„y~X,y~(Kolej ny) V pa~.x,y>(~tvm,y(Kolejny D<l k~l~~ny=xNastępnY)~~

Intuicyjnie to równanie można przeczytać następująco: „Film y następuje po filmie x, jeśli jest kolejnym odcinkiem filmu x, albo następuje po kolejnym odcinku filmu x".

Aby zrozumieć zapisane równanie, najpierw trzeba sobie uświadomić, że atrybutami relacji Następny sąx i y. Relacja Następny stanowi lewą stronę równania, a jego prawą stroną jest suma dwóch termów. Pierwszy z nich: pK„,~;„y~a,y~(Kolejny) jest kopią relacji Kolejny z przemianowaniem atrybu­tów po to, by ich nazwy pasowały do relacji Następny. Drugi term stanowi złączenie teta Kolejny flak„,~~ny-xNastępny, które służy połączeniu wszyst­kich par (a, b) z relacji Kolejny z parami (b, c) relacji Następny. W wyniku powstają krotki (a, b, b, c), których atrybutami są odpowiednio film, ko­lejny, x orazy. To złączenie jest następnie rzutowane na pierwszą i czwartą składową: film oraz y, a potem zostają przemianowane atrybuty x i y.

W równaniu ze stałym punktem relacja Następny jest przyrównana do su­my relacji Kolejny oraz wyniku przetworzenia drugiego terenu, który podaje ciąg następstw. A zatem relacja Następny składa się z takich par (x, y), które albo są elementami relacji kolej ny, albo w których y jest następnym odcinkiem po kolejnym odcinku filmu x. Inaczej mówiąc y jest kolejnym, ..., po kolejnym odcinku filmu x, gdzie słowo „kolejny" powtarza się dowolnie dużo razy.

0

i

24Ó 4. DZIAŁANIA W MODELU RELACYJNYM

4.4.2. Obliczanie najmniejszego punktu stałego

',I Wcale nie musi być oczywiste to, że najmniejsze rozwiązanie równania z przykładu 4.34, czyli zdefiniowana tam relacja Następny, jest właśnie tym zbiorem, o który nam chodzi, tzn. zbiorem tych par filmów, które należą do jednej serii filmów, i gdzie pierwszy odcinek w parze jest wcześniejszy niż drugi element w parze. Sens operatora punktu stałego będzie najlepiej zrozu­mieć, gdy przeanalizuje się obliczenie punktu stałego. Opisany poniżej sposób obliczania punktu stałego jest poprawny w przypadku, gdy w wyrażeniu nie występuje operator różnicy, natomiast w p. 4.4.4 przedstawimy inny sposób, poprawny dla zadań, w których występuje operator różnicy.

i 1. Na początku zakładamy, że występująca z lewej strony równania rela­cja R jest pusta.

2. Powtarzamy obliczanie kolejnej nowej wartości relacji R przez pr,~e­tworzenie prawej strony równania, gdzie w miejsce R wstawia się i wartość obliczoną w poprzednim kroku.

,6 ' 3. Kończymy obliczenie w tej iteracji, w której uzyskana wartość jest identyczna z poprzednią.

P~YKŁAD 4.35

Prześledzimy Obliczenie relacje Następny przy załOżerilU, Że relacja Kolej­j ny składa się z następujących krotek:

alm kole'h Rocky Rocky II Rocky II Rocky III Rocky III Rocky IV

Na początku zakładamy, że relacja Nastypny jest pusta. Złączenie relacji Ko­lejny i Następny w równaniu z punktem stałym jest wobec tego też puste, a więc jedyne krotki rozwiązania będą pochodzić z pierwszego termu w sumie, czyli z relacji Kolejny. A więc po pierwszym kroku iteracji wartości relacji Następny i Kolej ny sątakie same. Tę sytuację przedstawiono na rys. 4.16.

W drugim kroku jako relacji Następny użyjemy relacji z rys. 4.16 i po­liczymy przy tym założeniu prawą stronę naszego równania z punktem sta­łym. Z pierwszego termu otrzymuje się ponownie te same trzy krotki, które

x Rocky Rocky II Rocky II Rocky III Rocky III Rocky IV

RYSUNEK 4.16

Relacja Następny po pierwszej iteracji

4.4. PROGRAMOWANIE REKURENCYJNE W DATALOGU Z49

już są. Aby obliczyć relację zapisaną w drugim termie, trzeba utworzyć złą czenie relacji Kolejny z bieżącą relacją Następny, która, jak uprzednio napisaliśmy, jest z nią identyczna. Aby otrzymać wynik złączenia, wybieramy takie krotki, których drugi element pary w relacji Kolejny jest taki sam jak pierwszy element w parze relacji Następny.

A więc na przykład otrzymujemy krotkę (Rocky, Rocky III) z połą­czenia pary (Rocky, Rocky II) z relacji Kolejny z parą (Rocky II, Rocky III) z relacji Następny. Postępując analogicznie z krotką

(Rocky II, Rocky III)

z relacji Kolej ny oraz krotką (Rocky I I I, Rocky IV) z relacji Następny, otrzymujemy nową krotkę relacji Następny: (Rocky II, Rocky IV). Żadnych innych par z relacji Kolejny i Następny nie można połączyć.

A zatem po dwóch krokach w relacji Następny jest pięć krotek przedsta­wionych na rys. 4.17. Porównując rys. 4.16 z rys. 4.17 możemy intuicyjnie określić, że pierwszy z nich zawiera odcinki następujące bezpośrednio po sobie, a na drugim są jeszcze dodatkowo pary odległe od siebie o dwa odcinki.

W kroku trzecim jako relację Następny traktujemy krotki uwidocznione na rys. 4.17 i ponownie obliczamy prawą stronę równania z punktem stałym. Poza powstałymi dotąd krotkami otrzymujemy jeszcze jedną parę. Bowiem z pokączenia pary (Rocky, Rocky I I) z relacji Kolej ny z parą (Roc­ky W , Rocky IV) z bieżącej relacji Następny otrzymuje się nową parę (Rocky, Rocky IV). Po trzecim kroku iteracji powstaje zatem nowy stan relacji Nastypny przedstawiony na rys. 4.18.

x

Rocky Rocky II

Rocky II Rocky III

Rocky III Rocky IV

Rocky Rocky III

Rocky II ~Rocky IV

KYSUNEK 4.17

Relacja Następny po drugięj iteracji

x

Rocky Rocky II

Rocky II Rocky III

Rocky III Rocky IV

Rocky Rocky III

Rocky II Rocky IV

Rocky Rocky IV

RYSUNEK 4.18

Relacja Następny po trzecięj iteracji

---