250
4. DZIAŁANIA W MODELU RELACYJNYM
' Następne przetwarzanie nie powoduje już powstania żadnych nowych i krotek, a zatem przerywamy obliczenia. Właściwy obraz relacji Następny,
powstały w wyniku obliczeń z punktem stałym, jest zawarty na rys. 4.18.
0
4.4.3. Równania z punktem stalym w Datalogu
Wyrażenia algebry relacji zawierające równania z punktem stałym bywają mocno skomplikowane. Często bywa tak, że równania okazują się prostsze po zapisaniu w postaci zestawu reguł Datalogu i właśnie ten temat zostanie opisany w bieżącym punkcie. Natomiast w podrozdziale 5.10 zostanie przedstawiony sposób implementacji tej koncepcji w SQL3, gdzie notacja z punktem stałym bardziej przypomina zapis algebraiczny niż logiczny, co wynika ze stylu zapisu użytego w SQL3.
Zasadniczy pomysł równań punktu stałego w konwencji logiki polega na rozpoczęciu od jednej lub kilku relacji, których wartości są znane. Mogą to być albo relacje ekstensjonalne bazy danych, albo relacje typu EDB. Pozostałe relacje definiuje się w nagłówkach reguł. Sąto albo intensjonalne relacje bazy danych, albo relacje typu 1DB. Podzadania w treści reguł zawierają predykaty, które są albo relacjami EDB lub IDB, albo atomami arytmetycznymi. Jeśli któreś relacje IDB są definiowane w regułach, które w treści też je zawierają, to te
1 reguły są efektywnymi równaniami ze stałym punktem, podobnie jak w przypadku równań algebry relacji w przykładzie 4.34.
' PRZYKŁAD 4.36
Nast u ce dwie re u Datalo u definiu relac u IDB Następny: ęp Ją g łY g Ją Ję tYp
Następny (x, y) <-- Kolejny(x, y)
Następny (x, y) E-- Kolejny (x, z) AND Następny (z, y)
j Pierwsza reguła jest podstawowa: mówi ona, że każdy kolejny odcinek jest następnym. Ta reguła odpowiada pierwszemu termowi równania sumy z przykładu 4.34.
W drugiej regule określono, że każde następstwo kolejnego odcinka x jest również następstwem samego x. Mówiąc ściślej: jeśli z jest kolejnym I:,
odcinkiem x, a wiemy, że z następuje po y, to y następuje również po x.
"i o
i' Reguły występujące w przykładzie 4.36 oraz równanie z punktem stałym w przykładzie 4.35 mają takie same znaczenie, bowiem wartość relacji Następny, jako rozwiązanie równania, jest taka sama jak relacja uzyskana z przetworzenia reguł. W ogólnym przypadku, jeśli żadna z reguł wchodzących w zestaw definiujący pewną relację typu IDB nie zawiera w jakimś po
' dzadaniu operatora negacji, to możemy obliczyć tę relację w sposób iteracyj
I I 4.4. PROGRAMOWANIE REKURENCYJNE VV' DATALOGU 2S I I
I ny, rozpoczynając od przypisania tej relacji wartości pustej, a następnie
w kolejnych krokach dołączając do niej nowe wartości wyliczane przez stosowanie reguł do relacji EDB oraz wartości relacji IDB wyliczonej w poprzednim kroku iteracji. Postępowanie iteracyjne kończymy wówczas, gdy nie powstają już żadne nowe elementy.
I PRZYKŁAD 4.37 I
Bardziej złożony przykład rekurencji powstaje w przypadku analizy drogi I~ I w grafach. Na rysunku 4.19 przedstawiono graf, który reprezentuje pewne ~!, I rejsy samolotów dwóch hipotetycznych linii lotniczych Nieznana Linia (UA) I;( oraz Typowa Linia (AA), rejsy pomiędzy miastami San Francisco, Denver, ~~~~[, Dallas, Chicago i Nowym Jorkiem.
AA 1900-2200
UA 1500-1800 CHI UA 1830-2130 i~~i~ NY '~ I,`: l ~I~~! UA 930-1230 DEN
UA` 1530-1730 ~i~ (,' 1 SF 1400-1700 'l AA 1500-1930
AA 900-1430
DAL
RYSUNEK 4.19
Mapa rejsów niektórych linii lotniczych
Rejsy można zapisywać w następującej relacji typu EDB:
Rejsy(linia, z, do, odlot, przylot) 'il
Przykładowe krotki z zap isem danych, reprezen towanych w grafie na ')
rys. 4.19, umieszczo no w tab eli na rys. 4.20. II ,
linialothicza z do odlot Yz lot
I
UA SF DEN 930 1230 ',
AA SF DAL 900 1430
UA DEN CHI 1500 1800
UA DEN DAL 1400 1700 'I'f
AA DAL CHI 1530 1730 I;,i
AA DAL NY 1500 1930 II~I j
AA CHI NY 1900 2200 II`
UA CHI NY 1830 2130 '!
RYSUNEK 4.20 Krotki relacji Rejsy
srdez Cum z~maruod `nosfa~uz urn m ezsfarrrpo~op ~qao.r;;saf q~;sod es, yofa -ua.rn~a.r arce;sod auul" faunmofn;~~z aaua~.r m ouormoiuo omofo~azazs ~.ro;~ `farnorurlar~u rae;sod m ~faua.~nxar afnd~~s~Cm a~n~ar fa; m az `~Curz~mnez v ~;s -arar op x e;s~rur z zarumo.z ~araalop >;uzour o; `rf e;s>;rur op z >?;ssrru z ~araajop ~uzour z>?.ro z e;sniur op x ~si?rru z ~araa~op uuzou~ ysaf az `;~e~ ounsrdzz a~n~ -a.r far~n.rp M ~aru~nr;iq.re f>?;n~ au>?xqop ~s ~r n~o~~z.zd suza zero p n;ospo seza `z~ ~rur~ ao~f~lsaaxo roso~um `.~olou~ns ~fns.zn~ onrpa.rsodzaq yz~Cao;~ ~Czppur `;s>?rut ~.zzd~a;~za~eu aud~~soQ rfae~aa op az `~~IU~Cm ~n~a.r fazsmrard z
~x n~uiapo ur~Cufalox (~Cze.r oznp am~omop)w `ur~Cufajo~ od u~~Cufa~o~ ;saf rC ~aurapo az `r~ay>?~ (rf `x) .rud qay;s~Czsm .rorqz :~iud~~s~N ~fa~~a.r ~ut~s ~;~fnra~ap fn~aa aron;sod.Cz.r; a; arf;s~CzsM ~x,od o~aa~fnd~;seu nur~~ o~aumad ~marxurapo ur~Cud~;seu ;saf oq~u `x urar~ura -po ru~ufa~ox oq1~ ;saf r~saf `x od afnd~;siu ~f :omozuaqo ~fa~zp.rnq a~rmoy~
(~ 'z) Iud~~saN QNK (z 'x) ~ud~~sa~ --~ (~ 'x) fud~~seN ~Z
(ń 'x) r~uCaTo~ -~ (~ 'x)~iud~~s~N y
:~moruyanr ~faua.rn~a.r ~u~mz fiu; ~rs afnuz -.Czr;o sezamom `,Czna ~n~p ;amuu ~~Czn~ euzou~ rfae~a.r fauf~Caua.rnxa~ .
'x od o~aa~fnda;s>?u nual~ o~aunnad uzayurapo ur~Cufa~ox;saf oqjs `x mary -urapo ur~Cufa~o~ oq~n ;saf rlsaf `x od afnd~;siu rC :omoz~.rqo farzpaeq a~rmo~
(~ 'z) ~uCaTo~ QN~ (z 'x)Aud~~s~N --ł (~ 'x)ńud~~s~~ 'Z
(ń 'x) huCaTo~ --> (f 'x)Aud~~se~ 'I
:oa~fnd~;s ->;u ~rs urn~s;spaz.rd fauuo.r;soman y~;sod m fn~a.r qo~Czseu srdez wzsm~ard oxnf a~n~a.r m euozazsarurn afz;soz uuf~Cauarnxaa >?foe~a.z sezomom `~uuo.z;s -omal ~faaaan~a.r z ~~n~a.r ~uzar~o~~uu ~ńz.rom; euzo~ WuCaTo~ gQg rfanla.z od ~k~mod~;s~Cm ~ud~~ s~N euf~Caua.rn~a.z efae~ar faro;~ m `~auuo~r~s -onrn~cd hfaua~rna~a.~ fau>?mz ~>?; z ~Cursrln;stCz.ro~ 9£y r ~,~y ~lanpnf~~z.rd M ~fauaanxa.~ a~au;sod auuI
(fi 'z) aud~~soQ Q~~ (z 'x) auda~soQ --> (I 'x) aud~~soQ ~Z (z 'p 'A 'x 'e)AsCa~ -a (~ 'x) aud~~so~ 'I
;kn~aa m~;saz ~Ca~fnd~;seu~fafnsrdo u `(~ 'x) au -d~~soQ ~fa>;Ia.r ~~fz.zom; ~p~q ;suru~ ~Ca>?d a~, ~qansfa.r faa~~m ~qy ur~Cupaf m ~C n;s>?rw op x ~;sercu z ~~s ge;sop i?uzom az ~uz; `rugi?;oj auozo~~od ~s (rf `x) ;snrut ~G~d aao;~" :rmz.rq `emns~u ~~s ar~nf `auf~Coua.rn~a~ acan;~Cd azs;so.rdfnN
wmuvov~ra~ m~QOw m dwd~vrza b ZSZ
4.4. PROGRAMOWANIE REKURENCYJNE W DATALOGU 2S3
tej reguły wymagałby użycia trzech dodatkowych zmiennych, potrzebnych do opisu krotek relacji Rej sy.
Obliczenie relacji Dostępne polega na przetworzeniu tego samego algorytmu iteracyjnego, który przedstawiliśmy w p. 4.4.2. Z zastosowania reguły numer 1 do relacji Dostępne należą następujące pary: (SF, DEN), (SF, DAL), (DEN, CHI), (DAL, CHI), (DAL, NY) oraz (CHI, NY).Totesiedem par, które są oznaczone krawędziami na rys. 4.19.
W następnym kroku rekurencji stosujemy rekurencyjną regułę numer 2 i otrzymujemy pary krawędzi, które mają wspólny wierzchołek. Stąd otrzymuje się dodatkowo pary ( S F, CHI ) , ( DEN, NY ) oraz ( S F, NY ) .Kolejny krok polega na połączeniu w pary wierzchołków połączonych drogami o długości do czterech krawędzi. W tym konkretnym przypadku nie wprowadza to już żadnych nowych elementów do relacji Dostępne. A więc relacja Dostępne dla danych opisanych grafem z rys. 4.19 zawiera dziesięć par (x, y), takich że w grafie istnieje pomiędzy nimi jakaś droga. Są to przypadkowo dokładnie takie pary (x, y), że na rys. 4.19 y występuje na prawo od x.
0
PRZYKŁAD 4.38
Sytuacja ustalenia właściwej relacji łączenia dwóch lotów w jedną podróż komplikuje się, gdy zostanie dołączone ograniczenie, że rejs może być łączony z innym rejsem, jeśli odlot drugiego z jakiegoś lotniska następuje nie wcześniej niż godzinę po przylocie pierwszego na to lotnisko. Tak określony predykat IDB nazwiemy Połaczenia (x, y, d, r) i jest on spełniony, gdy podróż zaczyna się w miejscu x w czasie d, a przylot następuje do portu y w czasie r. Jeśli taka krotka istnieje, to na przesiadkę między jednym a drugim rejsem jest co najmniej godzina.
Następujące reguły definiują Połączenia*:
1. Połączenie (x, y, d, r) ~- Rejs (a, x, y, d, r)
2. Połączenie (x, y, d, r) ~- Połączenie (x, z, d, tl) AND Połączenie (z, y, t2, r) AND t1 ~ t2 + 100
W pierwszym kroku iteracji otrzymuje się osiem Połączeń, które przedstawiono na rys. 4.21. Każde z nich jest powiązane z jednym rejsem z rys. 4.19; jest ich więcej niż krawędzi w grafie, ponieważ niektóre krawędzie oznaczają kilka rejsów w różnym czasie między tymi samymi portami.
Teraz tworzymy nowe krotki, korzystając z reguły (2). Na przykład druga i piąta krotka tworzą nowe połączenie o parametrach ( S F, CH I , 9 0 0 , 1730 ) . Natomiast nie można utworzyć nowego połączenia z krotek drugiej
Reguły te działąjąjedynie, gdy żaden ręjs nie odbywa się o północy.
2S4 4. DZIAŁANIA W MODELU RELACYJNYM
i szóstej, ponieważ przylot do Dallas następuje o 14:30 i jest to tylko na pół godziny przed odlotem z Dallas o 15:00. Krotki powstałe w wyniku tego kroku iteracyjnego zostały przedstawione na rys. 4.22. Nad linią znajdują się krotki powstałe w pierwszym kroku, a pod nią umieszczono sześć nowych krotek, które powstały w kroku 2. Sama linia nie jest oczywiście elementem relacji.
x d r
SF DEN 930 1230
SF DAL 900 1430
DEN CHI 1500 1800
DEN DAL 1400 1700
DAL CHI 1530 1730
DAL NY 1500 1930
CHI NY 1900 2200
CHI NY 1830 2130
RYSUNEK 4.21
Podstawowe krotki relacji Połaczenia
x d r j' SF DEN 930 1230
SF DAL 900 1430 DEN CHI 1500 1800 DEN DAL 1400 1700 DAL CHI 1530 1730 DAL NY 1500 1930 CHI NY 1900 2200 CHI NY 1830 2130 SF CHI 900 1730 SF CHI 930 1800 SF DAL 930 1700 DEN NY 1500 2200 DAL NY 1530 2130 DAL NY 1530 2200 RYSUNEK 4.22
Relacja Połaszenia po drugięj iteracji i
f,' W trzecim kroku iteracji trzeba rozważyć wszystkie krotki z rys. 4.22 jako kandydatów do utworzenia nowych Poł~czeń przy zastosowaniu reguły (2), Jednak nie ma sensu rozpatrywać ponownie par krotek, z których obie są umieszczone nad linią, były już bowiem analizowane w drugim kroku iteracji, i jeśli spełniały warunki, to zostały zapisane poniżej linii. Jedyne nowe kratki mogą powstać z par, w których przynajmniej jeden element został wygenerowany w drugim kroku, a zatem z kratki zapisanej poniżej linii na rys. 4.22.
4.4. PROGRAMOWANIE REKURENCYJNE W DATALOGU 2SS
x d r
SF DEN 930 1230
SF DAL 900 1430
DEN CHI 1500 1800
DEN DAL 1400 1700
DAL CHI 1530 1730
DAL NY 1500 1930
CHI NY 1900 2200
CHI NY 1830 2130
SF CHI 900 1730
SF CHI 930 1800
SF DAL 930 1700
DEN NY 1500 2200
DAL NY 1530 2130
DAL NY 1530 2200
SF NY 900 2130
SF NY 900 2200
SF NY 930 2200
RYSUNEK 4.23
Relacja Połączenia po trzeciej iteracji
W trzecim kroku iteracji otrzymujemy tylko trzy nowe krotki. Zostały one umieszczone na samym dole tabeli na rys. 4.23. Linie na tym rysunku oddzielają grupy krotek powstałe w poszczególnych krokach iteracji, powyżej linii pierwszej jest osiem krotek powstałych w pierwszym kroku, w środku jest sześć krotek z drugiego kroku, a poniżej drugiej linii ostatnie trzy krotki. W kroku 4 iteracji nie powstają już żadne nowe krotki, a zatem jest to już koniec przetwarzania algorytmu. Na rysunku 4.23 została zatem przedstawiona kompletna relacja Połaczenia.
0
4.4.4. Negacja w regułach rekurencyjnych
Czasami trzeba użyć w jednej regule zarówno rekurencji, jak i negacji. Połączenie tych dwóch elementów można przeprowadzić na dwa sposoby: bezpieczny i ryzykowny. Ogólna zasada polega na tym, żeby używać negacji jedynie w takich przypadkach, kiedy nie znajduje się ona wewnątrz operacji z punktem stałym. Żeby uchwycić właściwy sens tej zasady przedstawimy dwa przykłady połączenia rekurencji i negacji, jeden z nich daje poprawny wynik, a drugi jest paradoksalny. Przekonamy się, że jedynie „warstwowa" negacja dobrze łączy się z rekurencją, a termin „warstwowa" precyzyjnie zdefiniujemy po przedstawieniu przykładów.
2SG 4. DZIAŁANIA W MODELU RELACYJNYM ;'I' PRZYKŁAD 4.39
Niech nasze zadanie polega na wyszukaniu na mapie z rys. 4.19 tych wszystkich par miast (x, y), które są połączone rejsami linii UA w kierunku z x do y j, (może to być połączenie złożone z kilku rejsów), ale które nie są połączone
rejsem linii AA. Zdefuiujemy rekurencyjnie predykat UAłaczy tak samo, jak definiowaliśmy predykat Połaszenie w przykładzie 4.37, dołączymy tylko i' nowe ograniczenie do rejsów linii UA.
I, 1. UAłączy(x, y) <--- Rejsy (UA, x, y, d, r)
2. UAłączy (x, y) f-- UAłączy (x, z ) AND UAłączy ( z, y)
W analogiczny sposób określamy predykat AAłączy, który zawiera wszystkie połączenia z x ~do y rejsami linii AA i w ten sposób otrzymujemy następujący zestaw reguł:
i I. AAłączy(x, y) f-- Rejsy (AA, x, y, d, r)
2. AAłączy(x, y) E-- AAłączy(x, z) AND AAłączy(z, y) '~ i
Teraz już tylko trzeba zdefiniować predykat UAtylko, do którego będąnależeć tylko te pary miast (x, y), które moźna połączyć rejsami wyłącznie linii I UA, a nie można pokączyć rejsami linii AA, i dostajemy następującą regułę, ` j nie zawierającą rekurencji:
UAtylko (x, y) E- UAłączy(x, y) AND NOT AAłączy(x, y)
Powyższa regula definiuje różnicę relacji UAłaczy i AAłączy.
Dla danych z rys. 4.19 do relacji UAłączy można utworzyć następujące pary: (SF, DEN), (SF, DAL), (5F, CHI), (SF, NY), (DEN, DAL), (DEN, CHI ) , ( DEN, NY ) , oraz ( CHI , NY ) . Zbiór ten otrzymuje się jako wynik przetworzenia algorytmu z punktem stałym, który został przedstawiony w p. 4.4.2. W analogiczny sposób otrzymuje się krotki relacji AAłaczy i są nimi: (SF, DAL), (SF, CHI), (SF, NY), (DAL, CHI), (DAL, NY) oraz (CHI, NY) . Po wykonaniu operacji różnicy algebraicznej tych relacji powstaje następujący zbiór par: ( S F, DEN ) , ( DAN, DAL ) , ( DEN, CHI ) oraz ( DEN, NY ) . Zbiór tych czterech par jest wartością predykatu UAtylko.
0 'i;i PRZYKŁAD 4.40
!I !ll A teraz rozważmy abstrakcyjną sytuację, w której nie da się już tak łatwo utworzyć wyniku. Załóżmy, że jest dany jeden predykat R typu EDB. Jest on
(,I~ unarny (jednoargumentowy) i zawiera tylko jedną krotkę (0), Tworzymy nowe predykaty unarne P i Q, oba typu IDB; definiująje następujące reguky:
1 . P (x) <--- R (x) AND NOT Q (x) v',; 2 . Q (x) E- R (x) AND NOT P (x)
4.4. PROGRAMOWANIE REKURENCYJNE W DATALOGU ZS%
Te dwie reguły mówią o tym, że element x należący do R należy również albo j do P, albo do Q, ale nigdy do obu na raz. P i Q są zdefiniowane wzajemnie
rekurencyjnie. Przy okazji określania znaczenia reguł rekurencyjnych w p. 4.4.1 podkre- I ślono, że rekurencja musi być traktowana jako operacja z najmniejszym sta- ', i łym punktem, tzn. że wynikiem ma być najmniejsza relacja, która spełnia
regułę w postaci równania algebraicznego. Z reguły 1 wynika, że P = R - Q,
a z reguły 2 wynika, że Q = R - P. Ale w relacji R jest tylko jedna krotka (0), ~ i a więc może ona należeć albo tylko do P, albo do Q. Ale gdzie? Nie może być
w żadnej z nich, ponieważ nie będzie spełnione równanie; na przykład z tego, !I'.I że zachodzi P = R - Q wynika Q~ _ {(0)} - Q~, co jest oczywistą nieprawdą. ''I !,. I Jeśli natomiast ustalimy, że P = {(0)}, a Q = Q~, to otrzymamy rozwiąza- ;~ . nia obu równań. Z równania P = R - Q wynika, że {(0)} _ {(0)} - QJ, co jest
prawdą, a z Q - R - P wynika, że Ql = {(0)} - {(0)}, co też jest prawdą.
Ale przecież można także określić P = ~ó, a Q = {(0)}. W tym przypadku ';i'~ również oba równania są spełnione. Otrzymaliśmy zatem dwa równoprawne
rozwiązania dla P i Q: i~(:1
a) P = {(0)} Q = ~
b) P = ~ Q = {(o)}
Oba z nich są rozwiązaniami minimalnymi w tym znaczeniu, że jeśli usuniemy jakąś krotkę z którejkolwiek z nich, to reguły przestaną być spełnione. A w jaki sposób wskazać jako właściwsze któreś z dwóch minimalnych rozwiązań z punktem stałym? Nie możemy też odpowiedzieć na proste pytanie, takie jak: „Czy P(0) jest prawdą?"
0
W przykładzie 4.40 okazało się, że jeśli rekurencja i negacja są za bardzo ze sobą sprzężone, to nasz algorytm tworzenia rozwiązania rekurencyjnych reguł lub równali z punktem stałym, które jest stałopunktowe i minimalne, przestaje działać. Może się bowiem okazać, że takich rozwiązań jest wiele i są dodatkowo wzajemnie sprzeczne. Pewnie byłoby dobrze, gdyby istniał jakiś algorytm precyzyjnego określania rozwiązania rekurencji powiązanej z negacją, ale dotychczas nie udało się uzgodnić w tej sprawie wspólnego stanowiska, jest zbyt wiele opinii o tym, co naprawdę oznaczają reguły lub równania z takim zapisem.
Lepiej zatem poprzestać na formułowaniu takich reguł rekurencyjnych, w których negacje są warstwowe. Takie ograniczenie obowiązuje na przykład w opisywanym w podrozdziale 5.10 standardzie SQL3. Jak przekonamy się później w przypadkach rekurencji warstwowej istnieje algorytm umożliwiający wyznaczenie jednego określonego rozwiązania minimalnego z punktem stałym (być może spośród wielu rozwiązań o takich cechach), które jest zgodne z intuicyjnym rozumieniem reguł. Wyjaśnimy obecnie, co to znaczy „warstwowość".
"' 258
4. DZfAŁANIA W MODELU RELACYJNYM
1. Należy narysować graf, którego wierzchołki odpowiadają predykatom IDB.
2. Jeśli reguła, w której nagłówku znajduje się predykat A, zawiera zanegowane zadanie z predykatem B, to tworzymy krawędź od A do B. Tę krawędź etykietujemy znakiem -, co oznacza krawędź z negacją.
3. Jeśli reguła, w której nagłówku znajduje się predykat A, zawiera nie zanegowane zadanie z predykatem B, to tworzymy krawędź od A do B. Tej z kolei krawędzi nie etykietujemy znakiem -.
Jeśli w tym grafie występuje cykl, który zawiera krawędź z negacją, to rekurencja nie jest warstwowa. W przeciwnym przypadku w grafie można wyróżnić warstwy, które są wyznaczone dla poszczególnych predykatów IDB. Warstwą predykatu A jest liczba krawędzi z negacją znajdujących się na ścieżce zaczynającej się w wierzchołku A.
W przypadku rekurencji warstwowej można określić kolejność obliczania predykatów IDB w porządku warstw, poczynając od najmniejszej. Dzięki takiej strategii można określić jeden z minimalnych punktów stałych reguly. A co jest jeszcze ważniejsze, to wyliczanie predykatów IDB w kolejności wyznaczonej przez warstwy zawsze ma sens i prowadzi do określenia „prawidłowego" punktu stałego. W przeciwieństwie do przypadku takiego, jak opisano w przykładzie 4.40, kiedy niewarstwowa rekurencja doprowadziła do określenia wielu możliwych rozwiązań, nie dostarczając przy tym możliwości określenia właściwego.
PRZYKŁAD 4.41
Na rysunku 4.24 przedstawiono graf predykatów z przykładu 4.39. Predykaty UAłaczy i AAłaczy znajdują się w warstwie 0, ponieważ nie prowadzi od nich żadna krawędź z negacją. Z kolei predykat UAtylko jest w warstwie 1, ponieważ prowadzą od niego ścieżki z jedną krawędzią z negacją, a nie ma ścieżek z większą ich liczbą. A zatem predykat UAtylko zostanie wyznaczony przed predykatami uAłączy i AAłaczy.
Przypomnijmy sobie teraz przykład 4.40 i skonstruujmy graf z predykatami P i Q z tego przykładu. Przedstawiono go na rys. 4.25. Z P do Q wiedzie krawędź z negacją, ponieważ w regule 1 w nagłówku znajduje się predykat P,
UAtylko AAłączy UAłączy
RYSUNEK 4.24
Graf utworzony dla rekurencji warstwowęj
4.4. PROGRAMOWANIE REKURENCYJNE W DATALOGU ZS9 P Q
RYSUNEK 4.25 j Graf utworzony dla rekurencji niewarstwowej '
II a Q w podzadaniu z negacją. Z kolei od Q do P także wiedzie krawędź z ne
gacją, ponieważ w regule 2 predykat Q jest zapisany w nagłówku, a predykat P w odzadaniu zane owan m. C li w rafie st u e c kl z zane owan p g Y zY g wY ęP J Y g ą
krawędzią i w takim grafie nie da się określić warstw. I ~l.ś
° I!i ,. i, ~, 4.4.5. Ćwiczenia do podrozdziału 4.4
'~',;'! Ćwiczenie 4.4.1. Jeżeli do diagramu z rys. 4.19 dołączymy krawędzie lub jakieś kra
wędzie usuniemy, to możemy zmienić wartości relacji Dostępne z przykładu 4.37, '~;'~~i' relacji Połączenia z przykładu 4.38 lub relacji DAlączy i AAłączy z przykładu '~,II,~-E 4.39. Podaj nowe wartości tych relacji, jeśli: 'i łj
*a) Zostanie dodana krawędź od CHI do SF z etykietą AA, 1900 - 2100. b) Zostanie dodana krawędź od NY do DEN z etykietą UA, 900 - 1100. c) Zostaną dodane obie te krawędzie.
d) Zostanie usunięta krawędź z DEN do DAL.
Ćwiczenie 4.4.2. Zapisz reguły w Datalogu (stosując negację warstwową, jeśli negacja jest konieczna), które opisują następujące modyfikacje pojęcia „następny" z przykładu 4.33. Można korzystać przy tym ze zdefiniowanych w przykładzie 4.36 relacji EDB Kolejny oraz relacji IDB Następny.
*a) P (x, y) zachodzi, gdy y jest odcinkiem następującym po odcinku x, ale nie jest bezpośrednio kolejnym odcinkiem po x (w znaczeniu Kolejny zdefiniowanym w relacji EDB)
b) Q ( x, y ) zachodzi, gdy y następuje po x, ale nie w bezpośredniej kolejności, ani nie jako kolejno trzeci po x.
!c) R (x) zachodzi, gdy`pox wyprodukowano co najmniej dwa następne odcinki. Oba mogąbyć następnymi kolejnymi odcinkami, ale nie tworząłańcucha.
!d) S ( x, y) zachodzi, gdyy następuje po x, ale i poy jest jeszcze jakiś odcinek.
Ćwiczenie 4.4.3. Klasy i związki w ODL można opisać jako relację: Rel ( klasa, pklasa, wiel ) . Wiel określa wielowartościowość związku, dla wielowartościowych związków ma wartość wiel., a dla pojedynczych j ed. Pierwsze dwa atrybuty określają powiązane ze sobą klasy, związek jest określony w kierunku od klasy do pklasy (klasy powiązanej). Na rysunku 4.26 przedstawiono relację Rel zawierającą trzy klasy ODL z przykaadu dotyczącego filmu, których zapis w ODL przedstawiono na rys. 2.6.
260
klasa rklasa wiel
Gwiazda Film wiei
Film Gwiazda wiel
Film Gwiazda jed
Studio Film wiel
RYSUNEK 4.26
Reprezentacja związku ODL poprzez dane relacji
wiei jed ~~1 r
Gwiazda Film Studio wiei wiei
RYSUNEK 4.27
Reprezentowanie związków w postaci grafu
4. DZIAŁANIA W MODELU RELACYJNYM
'! Te dane można przedstawić także w postaci grafu, w którym wierzchołki reprezentują klasy, a krawędzie prowadzą od klasy do klasy z nią powiązanej i są opatrzone odpowiednio etykietami wiel lub jed. Na rysunku 4.27 przedstawiono taki graf dla danych z rys. 4.26.
Dla podanych poniżej predykatów należy podać ich opis w Datalogu, przy czym jeśli trzeba użyć negacji, to ma ona być warstwowa. Można korzystać z relacji Rel jako relacji EDB. Należy także przedstawić proces obliczeniowy na przykładzie danych z rys. 4.26.
a) Predykat P ( klasa, eklasa) zachodzi, gdy w grafie klas istnieje ścieżka' od klasy do eklasy. Ta druga klasa jest rozumiana jako klasa „objęta" klasą, w tym sensie, że jest ona częścią części, części... obiektu pierwszej klasy.
*!b) Predykaty S (klasa, eklasa) i M(klasa, eklasa). Szachodzi, gdy istnieje „włączenie jednowartościowe" eklasy do klasy, tzn. że istnieje ścieżka od klasy do eklasy, w której wszystkie krawędzie są pojedyncze. Natomiast predykat Mzachodzi, gdy istnieje „wielowartościowe włączenie eklasy do klasy, tzn. istnieje taka ścieżka prowadząca od klasy do eklasy, na której co najmniej jedna krawędź jest wielokrotnie etykietowana.
c) Predykat Q(klasa, eklasa) zachodzi wówczas, gdy istnieje ścieżka od kl a s y do e kl a s y, ale nie j est to ścieżka pojedyncza. W regułach można korzystać z predykatów IDB, które zostały zdefiniowane w niniejszym ćwiczeniu.
4.5. Więzy relacji
W modelu relacyjnym istnieją mechanizmy, służące do określania znanych powszechnie rodzajów więzów, jakimi są na przykład więzy integralności referencyjnej, które opisywaliśmy w podrozdziale 2.5. Przekonamy się
cieżki puste nie są ścieżkami w tym ćwiczeniu.
4.5. WIĘZY RELACJI ZE) I
teraz, że w algebrze relacji można w bardzo wygodny sposób opisywać także różne inne rodzaje więzów. W algebrze relacji można nawet opisywać zależności funkcyjne, o czym przekonamy się, śledząc przykład 4.44. W programowaniu baz danych więzy odgrywają bardzo ważną rolę i dlatego język SQL zawiera mechanizmy do opisu tak samo złożonych więzów, jak algebra relacji; ten temat zostanie dokładnie omówiony w rozdziale 6.
4.5 .1. Algebra relacj i j ako język więzów
W algebrze relacji istnieją dwa sposoby określania więzów:
1. Jeśli R jest pewnym wyrażeniem algebry relacji, to równanie R = Q~ stanowi więzy, które można interpretować w znaczeniu: „Relacja R jest pusta" albo „W relacji R nie występujążadne krotki".
2. Jeśli R i S są wyrażeniami algebry relacji, to R c S stanowi więzy. Można je przeczytać jako: „Każda krotka R jest także krotką S". W S oczywiście mogą występować poza tym jeszcze inne krotki.
Te dwa sposoby zapisu więzów są równoważne, w obu można zapisać te same więzy, ale czasami któryś z nich bywa wygodniejszy, gdyż jest bardziej wyrazisty. Na przykład więzy R c S można równoważnie zapisać jako R - S = ~d, ponieważ jeśli każda krotka z r należy do S, to z pewnością R - S musi być relacją pustą. I odwrotnie, jeśli w R - S nie ma żadnej krotki, to każda krotka, która należy do R, musi także należeć do S (w przeciwnym razie musiałaby należeć do R - ,5~.
Jednakże więzy pierwszego rodzaju: R = QS można równie dobrze przedstawić w postaci R c ~Ó. Traktując rzecz czysto technicznie, QJ nie jest wyrażeniem algebry relacji, ale ponieważ istnieją takie wyrażenia, których wynikiem jest QS, np. wyrażenie R - R, a zatem możemy traktować Q3 jako wyrażenie algebry.
W następnych rozdziałach przedstawimy zapisy ważnych rodzajów więzów w tych dwu konwencjach. W rozdziale 6 okaże się, że pierwsza konwencja: równy-zbiorowi-pustemu jest stosowana w programowaniu w języku SQL. Ale, jak już pokazaliśmy, możemy zawsze wyrazić najpierw nasze więzy w konwencji zawierania-się zbiorów, a jeśli trzeba, to można taki zapis potem przekształcić do postaci równy-zbiorowi-pustemu.
4.5.2. Więzy integralności referencyjnej
W podrozdziale 2.5 wprowadziliśmy pojęcia więzów integralności referencyjnej, które służyły temu, aby wartości identyfikowane w pewnym kontekście występowały także w innym powiązanym kontekście. Integralność referen
262 4. DZIAŁANIA W MODELU RELACYJNYM
cyjna nadaje sens związkom. Jeśli na przykład obiekt (lub encja) A jest połą czony więzami z innym obiektem (lub encją) B, to B rzeczywiście musi istnieć. Posługując się terminami z języka ODL, jeśli związek w obiekcie A jest wskaźnikiem, to ten wskaźnik w przypadku nałożenia więzów integralności nie może wskazywać wartości pustej, ale realnie isW iejący obiekt.
W modelu relacyjnym więzy integralności referencyjnej działają trochę inaczej. Mogą one na przykład określać, że jeśli w pewnej krotce relacji R występuje określona wartość v, to z założeń projektowych wynika, że taka sama wartość v musi występować również jako określona składowa pewnej krotki innej relacji S. W następnym przykładzie zostanie pokazane, w jaki sposób taki rodzaj więzów z modelu relacyjnego można zapisać w algebrze relacji.
PRZYKŁAD 4.42
Skupimy uwagę na następujących dwóch relacjach „filmowej" bazy danych:
Film( tytuł, rok, długość, czyKolor, nazwaStudia, producentC#)
FilmDyr(nazwisko, adres, cert#, cenaSieci)
Założenie, że wszyscy producenci filmów występują w relacji FilmDyr jest założeniem rozsądnym. Jeśli istnieje taki film, który w relacji FilmDyr nie ma swojego producenta, to oznacza, że coś jest w bazie nie tak, i chcielibyśmy przynajmniej być o tym fakcie informowani przez system.
Powyższe wymaganie można sprecyzować dokładniej w sposób następujący: w każdej krotce relacji Film składowa producentC# musi występować także jako składowa cert# w pewnej krotce relacji FilmDyr. Tak sformułowany warunek gwarantuje, że producent filmu występuje jako jeden z dyrektorów filmu, ponieważ wszyscy dyrektorzy są jednoznacznie identyfi
y kowani przez numery certyfikatów. Tak określone więzy można zapisać 9~,i', w postaci następującego warunku typu zawieranie-zbiorów:
~prnducenK,'L`~F11m) C 7Ccerl#~F11mDyr~
Lewa strona wyrażenia opisuje zbiór wszystkich numerów certyfikatów, które występują jako składowe producentC# w krotkach relacji Film. Z kolei wartością wyrażenia z prawej strony jest zbiór wszystkich numerów certyfikatów, które występują jako składowe krotek relacji FilmDyr. Więzy natomiast zapewniają, że każdy element zbioru, występującego z lewej strony wyrażenia, musi także występować w zbiorze zdefiniowanym po prawej stronie tego wyrażenia.
W konwencji przyrównania do zbioru pustego te więzy można przedstawić następująco:
~producentC#\F11m~ - 7tcert#\FJ-1mDyr) WCl
D
4.5. WIĘZY RELACJI 263
PRZYKŁAD 4.43
Teraz z kolei zapiszemy w postaci wyrażeń algebry relacji więzy integralności referencyjnej nałożone na więcej niż jeden atrybut. Można na przykład wymagać, aby wszystkie filmy, które znajdują się w relacji
GwiazdyW(tytułFilmu, rokProdukcji, nazwiskoGwiazdy)
znalazły się także w relacji:
Film( tytuł, rok, długość, czyKolor, nazwaStudia, producentC#)
W obu relacjach film jest identyfikowany przez parę atrybutów, ustaliliśmy już bowiem wcześniej, że żaden atrybut samodzielnie nie stanowi wystarczającej identyfikacji filmu. Następujące więzy:
~tytułFilmu, rokProdukcji(GwiazdyW) C 7itytuł, rok~Fllm~
zapewniają spełnienie więzów integralności w ten sposób, że porównuje się pary tytuł-rok przez rzutowanie obu relacji na odpowiednie listy atrybutów.
0
4.5.3. Inne przykkady więzów
Ta sama konwencja zapisu umożliwia definiowanie dużo więcej warunków, daleko wykraczających poza więzy integralności referencyjnej. W postaci wyrażeni algebraicznych można zapisywać także dowolne zależności funkcyjne, z tym że notacja przyjęta poprzednio dla zależności funkcyjnych dostarcza dużo więcej mechanizmów opisu warunków ograniczeń niż notacja algebraiczna.
PRZYKŁAD 4.44
Zapiszmy w postaci więzów algebraicznych następującązależność funkcyjną:
nazwisko --~ adres
zachodzącą dla relacji:
Gwiazda (nazwisko, adres, płeć, dataUrodzenia)
Zależność ta oznacza, że jeśli jakiekolwiek dwie krotki (tl,, t2) relacji Gwiazda mają takie same wartości atrybutu nazwisko, to nie mogą w nich występować różne wartości atrybutu adres. W algebrze relacji do określenia zbio
264 4. DZIAŁANIA W MODELU RELACYJNYM
ru par korzystamy z iloczynu kartezjańskiego, a wyboru par naruszających ograniczenie dokonuje się przez operację selekcji. Do opisu zależności stosujemy konwencje przyrównania do zbioru pustego.
Aby utworzyć iloczyn kartezjański zbioru z nim samym, trzeba przemianować jedną z kopii, po to by móc we właściwy sposób korzystać z nazw atrybutów w iloczynie. A zatem kopie relacji Gwiazda będziemy skrótowo nazywać MS1 oraz MS2. Wówczas omawiana zależność funkcyjna przyjmie następującą postać algebraiczną:
~MSl.nazwisko=MS2.nazwisko AND MS1.adres xMS2.adres ~MSl X Ms2~ -XJ
li~ W powyższym wyrażeniu MS1 w iloczynie MS1 x MS2 stanowi skrót dla zapii su przemianowania:
PMSI (nazwisko, adres, pleć, dataurodzenia) ~Gw1a Zda
i MS2 jest podobnym przemianowaniem relacji gwiazda.
0
Czasami trzeba korzystać również z jeszcze innych rodzajów więzów, tak zwanych więzów dziedziny. Ich znaczenie polega na przestrzeganiu na przykład wymagania, aby wartości atrybutu miały pewien określony typ danych, na przykład, żeby były to liczby całkowite albo napisy o długości nie przekraczającej 30 znaków. Tego typu więzów nie da się przedstawić w algebrze relacji, ponieważ nie zawiera ona mechanizmu opisu typów. W niektórych przypadkach jednak więzy domenowe polegają na ograniczeniu zakresu wartości pewnych atrybutów. Jeśli taki zbiór wartości akceptowalnych da się zapisać za pomocą warunków wyboru, to wówczas więzy domenowe można również zapisać w postaci więzów algebraicznych.
"' PRZYKŁAD 4.45
Załóżmy, że wartości atrybutu płeć relacji Gwiazda to `K' lub `M'. Taki warunek można przedstawić za pomocą następującego wyrażenia algebraicznego:
ópłeć * `F' AND płeć x `M.'~Gw1 a Zdd) = 1U
Tak sprecyzowany warunek oznacza, że zbiór tych krotek relacji Gwiazda, w których składowa płeć nie jest równa ani `K', ani `M' jest zbiorem pustym.
0
Istnieją również rodzaje więzów, które nie przypominają żadnego typu więzów opisanych w podrozdziale 2.5. Język algebry relacji umożliwia zapis wielu różnych nowych rodzajów więzów. Poniżej przedstawiamy jeden z przykładów.
4.5. WIĘZY RELACJI 265 PRZYKŁAD 4.46
Załóżmy, że aby zostać prezesem studia filmowego, trzeba być właścicielem sieci, której wartość nie jest mniejsza niż 10 000 000 $. Nie można takiego typu ograniczenia zaklasyfikować ani jako więzy domenowe, ani jako pojedyncząwartość, ani też jako więzy integralności referencyjnej. Można je zapisać w postaci wyrażenia algebraicznego w następujący sposób. Najpierw tworzy się złączenie teta dwócli relacji:
FilmDyr(nazwisko, adres, cert#, cenaSieci) Studio (nazwa, adres, prezC#)
przy warunku ograniczającym, w którym jest wymagana równość między wartościami atrybutu prezC# z relacji studio oraz cert# z relacji FilmDyr. W wyniku tego złączenia powstanie zbiór par krotek zawierających studio i tego dyrektora, który jest prezesem studia. Jeśli teraz wybierzemy te krotki, w których wartość sieci jest niższa niż dziesięć milionów dolarów, to taki zbiór, w myśl naszych więzów, musi być pusty. A zatem nasze więzy
można przedstawić w postaci: .j
~cenaSieci < 10000000~StUdlO D4 prezc#=cert#F11mDyr~ - Ś~
Te więzy można przedstawić w algebrze relacji także w postaci alternatywnej, przez porównanie zbioru certyfikatów, reprezentujących prezesów studia, ze
zbiorem certyfikatów tych prezesów, którzy posiadają sieci warte nie mniej 'j'i~'., niż 10 000 000 dolarów. Ten pierwszy zbiór musi być podzbiorem drugiego
zbioru. Poniżej przedstawiamy wyrażenie, które jest zapisem tego zawierania się zbiorów:
~prezck~stUd10~ C iLcert#l~cenasieci>_10000OOO~F~ 1mDyr~)
0 i 4.5.4. Ćwiczenia do podrozdziału 4.5
Ćwiczenie '4.5.1. Należy zapisać w postaci wyrażeń algebry relacji następujące więzy dotyczące zbioru relacji z ćwiczenia 4.1.1, których opis ponawiamy poniżej:
Produkt (producent, model, typ)
PC (model, szybkość, ram, hd, cd, cena)
Laptop (model, szybkość, ram, hd, ekran, cena)
Drukarka (model, kolor, typ, cena)
Te więzy można przedstawić albo w konwencji przyrównania do zbioru pustego, albo w konwencji zawierania się zbiorów. Należy także wskazać te dane z ćwiczenia 4.1.1, które naruszają opisane więzy.
266 4. DZIAŁANIA W MODELU RELACYINYM
*a) Komputera osobistego z procesorem o częstotliwości zegara niższej niż 150 nie można sprzedać za cenę poniżej 1500 $.
b) Jeśli laptop ma ekran o przekątnej mniejszej niż 11 cali, to albo zawiera twardy dysk o pojemności co najmniej 1 gigabajta, albo jego cena jest niższa niż 2 000 $.
!c) Żaden z producentów PC nie wytwarza laptopów.
*!!d)Jeśli producent PC wytwarza laptopy, to muszą one mieć procesory o tych samych parametrach co PC.
!e) Jeśli w laptopie jest więcej pamięci niż w PC, to jego cena musi być wyższa niż cena PC.
Ćwiczenie 4.5.2. Następujące więzy należy przedstawić w postaci wyrażeń algebraicznych. Więzy są nałożone na relacje z ćwiczenia 4.1.3:
Klasy (klasa, typ, kraj, liczbaDział, działo, wyporność) Okręt (nazwa, klasa, wodowanie)
Bitwa (nazwa, data)
Rezultat (okręt, bitwa, wynik)
Te więzy można przedstawić albo w konwencji przyrównania do zbioru pustego, albo w konwencji zawierania się zbiorów. Należy także wskazać te dane z ćwiczenia 4.1.3, które naruszają opisane więzy.
a) W żadnej klasie okrętów nie mogą wystąpić okręty z działami kalibru większego niż 16 cali.
b) Jeśli w klasie okrętów jest więcej niż 9 dział, to ich kaliber nie może przekraczać 14 cali.
!c) W żadnej klasie nie może być więcej niż 2 okręty.
!d) Zaden kraj nie może posiadać jednocześnie okrętów liniowych i krążownilil ków liniowych.
!!e) W bitwie, w której zatonął okręt z liczbą dział mniejszą niż 9, nie mógł brać udziału okręt z liczbą dział większą niż 9.
Ćwiczenie 4.5.3. Więzy można zapisywać nie tylko w algebrze relacji, ale również w postaci reguł Datalogu. Można na przykład w postaci reguł Datalogu definiować predykaty IDB, których wartości mają być puste. Należy w Datalogu zapisać poniżej wymienione więzy:
* a) b) c) d)
e)
Więzy z przykładu 4.42. Więzy z przykładu 4.43. Więzy z przykładu 4.44. Więzy z przykładu 4.45. Więzy z przykładu 4.46.
!Ćwiczenie 4.5.4. Załóżmy, że dane są dwie relacje R i S. Niech więzy C są zdefiniowane w następujący sposób: jeśli pewna krotka relacji R zawiera wartości v,, v2,, ..., v„ odpowiednio dla atrybutów A,, AZ, ..., A„, to w relacji S istnieje taka knotka, w której wartości v,, v~,, ..., v„ są wartościami atrybutów B,, BZ, ..., B„. Należy zapisać więzy C w algebrze relacji.
4.6. OPERACJE RELACYJNE NA WIELOZBIORACH 26%
!!Ćwiczenie 4.5.5. Niech będzie dana relacja R, a w zależności funkcyjnej A,AZ ... A„ B występują tylko atrybuty z relacji R. Należy zapisać w algebrze relacji więzy, które określają, że ta zależność zachodzi zawsze w relacji R.
4.6. Operacje relacyjne na wielozbiorach
Zbiory krotek (relacje) są prostym i naturalnym modelem dla danych, które mogą występować w bazie danych, natomiast w komercyjnych systemach baz danych zbiory są, rzadko albo wcale, jedynym sposobem reprezen
towania danych. Są bowiem takie sytuacje, kiedy należy w bazie danych do- ~; I puścić występowanie większej liczby takich samych krotek. Taki „zbiór", „, w którym elementy mogą się powtarzać nazywamy wielozbiorem. W bieżą
cym podrozdziale będziemy rozważać takie relacje, które są raczej wielozbio
rami, a nie zbiorami w sensie właściwym, tzn. w omawianych relacjach te ,' same knotki będą mogły występować więcej niż jeden raz. W związku z tym j,;. będziemy mówić o zbiorach, w przypadkach gdy chodzi o takie relacje,
w których knotki nie powtarzają się, i o wielozbiorach w przypadku tych rela
cji, w których występująpowtórzenia knotek. ;'.;,
PRZYKŁAD 4.47
Na rysunku 4.28 przedstawiono relację, która jest wielozbiorem knotek. Knotka (l, 2) występuje tam 3 razy, a knotka (3, 4) tylko jeden raz. Jeśli ta relacja miałaby być typu zbiór, to trzeba by z niej wyeliminować dwa wystąpienia knotki (1, 2). W relacjach o typie wielozbioru dopuszczamy wielokrotne wystąpienie tej samej knotki, ale tak samo, jak w przypadku zbioru, kolejność knotek nie ma znaczenia.
A B 1 2 3 4 1 2 1 2
RYSUNEK 4.28 Wie(ozbiór
D
4.6.1. Dlaczego wielozbiory?
Poszukując najbardziej efektywnego sposobu implementacji relacji, uzyskujemy w efekcie wielozbiory jako struktury, które umożliwiają przyspieszenie wykonywania operacji na relacjach. Na przykład przy wykonywaniu operacji rzutowania zastosowanie wielozbioru umożliwia niezależne trakto
,~
268 4. DZIAŁANIA W MODELU RELACYJNYM
wanie poszczególnych krotek. Jeśli natomiast traktujemy relację jako zbiór, to musimy zawsze porównywać wynik rzutowania składowych poszczególnych krotek z dotychczasowym wynikiem rzutowania, po to by upewnić się, że nowa krotka jeszcze nie jest dołączona do wyniku. Jeśli jednak dopuszcza się wielozbiór jako postać wyniku, to po prostu wykonuje się rzutowanie i poi;
I',,,j, wstałą krotkę dołącza do wyniku, nie potrzeba już porównywać nowej krotki z dotychczas uzyskanymi.
PRZYKŁAD 4.48
Jeśli założymy, że wynikiem rzutowania może być wielozbiór, to można traktować wielozbiór przedstawiony na rys. 4.28 jako wynik rzutowania relacji pokazanej na rys. 4.29 na atrybutyA i B. Jeśli natomiast potraktujemy operator rzutowania tak jak w algebrze relacji i w związku z tym wyeliminujemy powtarzające się krotki, to uzyskamy następujący wynik:
A B 1 2 3 4
Zauważmy, iż mimo tego, że wielozbiór zawiera więcej elementów, wynik można uzyskać szybciej, ponieważ nie trzeba każdej z krotek (ł, 2) i (3, 4) porównywać ze wszystkimi, które zostały dotychczas wygenerowane.
A B C 1 2 5 3 4 6 1 2 7 1 2 8
RYSUNEK 4.29 Wielozbiór z przykładu 4.48
Ponadto, jeśli celem rzutowania jest uzyskanie pewnej zbiorczej wartości (będzie o tym mowa w podrozdziale 5.5), na przykład zadanie polega na: „znaleźć wartość średnią składowych A relacji przedstawionej na rys. 4.29", to nie możemy traktować rzutowanej relacji w terminach zbioru. Jeśli bowiem będziemy stosować tu model zbioru, to wartością średnią A będzie liczba 2,
!. ponieważ na rys. 4.29 występują tylko dwie różne wartości tego atrybutu: ł oraz 3, co daje średnią 2. Jeśli jednak potraktujemy kolumnę A z rys. 4.29 jako wielozbiór { ł, 3, ł, 1 }, to otrzymamy poprawną wartość średniej 1,5.
0
Drugi przypadek, kiedy dopuszczenie wielozbioru w postaci wyniku umożliwia zaoszczędzenie czasu przetwarzania, zachodzi, gdy oblicza się sumę dwóch relacji. Jeśli upieramy się przy traktowaniu relacji R u S jako zbioru, to
4.6. OPERACJE RELACYJNE NA WIELOZBIORACH 269
każdą krotkę z S musimy sprawdzać, czy nie należy ona jednocześnie do R. Jeśli tak się zdarzy i okaże się, że pewna krotka z S należy również do relacji R, to ta krotka nie zostanie dołączona do sumy, w przeciwnym razie zostanie dołą czona do sumy. Jeśli natomiast pozwolimy, aby w wyniku sumowania powstał wielozbiór, to po prostu skopiujemy wszystkie krotki z relacji R i wszystkie krotki z relacji S do wyniku, bez względu na to, czy sątakie same, czy nie.
4.6.2. Suma, przecięcie i różnica wielozbiorów
Przy obliczaniu sumy dwóch wielozbiorów dołącza się wszystkie wystąpienia krotki z poszczególnych składników sumy. Oznacza to, że jeśli w relacji R krotka t powtarza się n razy, a w relacji S m razy, to w sumie relacji R u
S krotka t występuje n + m razy. Oczywiście zarówno n, jak m, a także obie j =i zmienne jednocześnie mogą mieć wartość 0. !"'`' Przy przecięciu wielozbiorów, w których krotka t występuje odpowied
nio n i m razy w wielozbiorach R i S, to wich przecięciu R n S krotka t występuje min(n, m) razy. Z kolei, jeśli obliczamy różnicę R - S, to tam krotka t występuje max(0, n-m) razy. Oznacza to, że jeśli w relacji R jest więcej wystąpień krotki t niż w relacji S, to w różnicy R - S liczba wystąpień krotki t jest równa różnicy jej wystąpień w R i S. Jednakże jeśli w relacji S krotka t występuje tyle samo razy co w krotce R, to w różnicy R - S krotka t wcale nie wystąpi. Mówiąc obrazowo: każde wystąpienie knotki t w wielozbiorze S
i ,,I
kasuje jedno jej wystąpienie w zbiorze R. PR7,YKŁAD 4.49
Załóżmy, że relacja R jest taka, jak na rys. 4.28, tzn. składa się ona z trzech ,,! wystąpień knotki (1, 2) oraz jednego wystąpienia knotki (3, 4). Z kolei S za- ',~~I` wiem następujące dane: !~~~_
I''. A B
1 2
'I!: 3 4 '~~i 3 4 ili 5 6 L~ł,,;
,., W sumie R u S knotka (l, 2) występuje cztery razy (trzy razy z wystąpień
w wielozbiorze R i jedno z wielozbioru S), knotka (3, 4) występuje 3 razy, a knotka (5, 6) tylko jeden raz.
Przecięcie R n S jest z kolei następującym wielozbiorem: A B
1 2 3 4
270
4. DZIAŁANIA W MODELU RELACYJNYM
Krotka (1, 2) występuje tutaj tylko jeden raz i krotka (3, 4) także. Dzieje się tak dlatego, że krotka (1, 2) występuje w R 3 razy, a w S jeden raz, rnin (3, 1) = 1, a więc w R n S krotka (l, 2) występuje 1 raz. Z kolei krotka (3, 4) w iloczynie R n S występuje min(l, 2) = 1 raz. Natomiast krotka (5, 6) w zbiorze R wcale nie występuje, a w zbiorze S jeden raz, więc w iloczynie R n S występuje min (0, 1) razy.
Operacje wielozbiorowe w zastosowaniu do zbiorów Załóżmy, że dane są dwa zbiory R i S. Każdy z nich możemy traktować jako wielozbiór, ale taki, w którym przypadkowo wszystkie elementy występują tylko jednokrotnie. Przy obliczaniu przecięcia R n S korzystamy z właściwości przecięcia wielozbiorów. Ale wynik dostaniemy taki sam jak w przypadku, gdybyśmy traktowali R i S jako zbiory. Krotka t należy do wielozbiorów R i S tyle razy, ile wynosi minimum z liczb wystąpień w R i S. Ponieważ oba wielozbiory R i S są w tym przypadku zbiorami, więc t może w każdym z nich wystąpić albo 0 razy, albo 1 raz. A więc stosując zarówno regułę przecięcia zbiorów, jak regułę przecięcia wielozbiorów, krotka t może w wyniku przecięcia wystąpić co najwyżej jeden raz, a dokładnie raz, jeśli występuje równocześnie w R i S. Podobnie można przeanalizować wyniki obliczania różnicy wielozbiorów, gdy oba argumenty są zbiorami. Zarówno wartość R - S, jak i S - R jest taka sama, jak gdybyśmy stosowali regułę obliczania różnicy zbiorów.
Operacja sumy natomiast ma inne właściwości i stosowanie reguły sumowania wielozbiorów daje inny wynik niż stosowanie reguły sumowania zbiorów. Jeśli bowiem stosujemy regułę sumowania wielozbiorów, to nawet gdy oba argumenty są zbiorami, wynik nie musi być zbiorem. Dzieje się tak dlatego, że jeśli jakakolwiek krotka t występuje jednocześnie w obu zbiorach R i S, to w sumie R u S wystąpi ona dwukrotnie, gdy stosuje się regułę sumowania wielozbiorów, a tylko jeden raz, gdy zastosujemy regułę sumowania zbiorów. A więc przy obliczaniu sumy trzeba ściśle precyzować, czy chodzi o obliczanie sumy wielozbiorów, czy sumy zbiorów.
Różnica wielozbiorów R - S zawiera następujące krotki:
A B 1 2 1 2
Aby przekonać się, dlaczego tak się dzieje, zauważmy, że w relacji R krotka (l, 2) występuje trzy razy i jeden raz w relacji S, a więc w relacji R-S wyst~ pi ona max(0, 3 - 1) = 2 razy. Z kolei krotka (3, 4) występuje w relacji R jeden raz, a w relacji S dwa razy, czyli liczba wystąpień w relacji R - S wynosi max(0, 1 - 2) = 0. W relacji R nie ma innych krotek, więc w różnicy R - S też innych krotek nie ma.
4.6. OPERACJE RELACYJNE NA WIELOZBIORAC1i 2% I
Z kolei różnica S - R jest następującym wielozbiorem:
A B 3 4 5 6
Krotka (3, 4) występuje tu jeden raz, co wynika z różnicy liczby wystąpień tej krotki w relacji S i liczby wystąpień w relacji R. Z tego samego powodu krotka (5, 6) w relacji S-R występuje też jeden raz. W tym przypadku wielozbiór jest zbiorem we właściwym sensie.
0
4.6.3. Rzutowanie wielozbiorów
Pokazaliśmy już rzutowanie wielozbiorów. Jak zobaczyliśmy w przykładzie 4.48, operacja rzutowania jest przeprowadzana niezależnie dla każdej krotki. Jeśli relacja R jest wielozbiorem o wartościach występujących na rys. 4.29 i obliczymy rzutowanie wielozbiorów ~A,~(R), to otrzymamy wielozbiór z rys. 4.28.
Prawa algebry w przypadku wielozbiorów
Prawem algebraicznym nazywamy równoważność dwóch wyrażeń algebraicznych, w których relacje są oznaczane nazwami zmiennych. Taka równoważność oznacza, że relacje opisywane przez wyrażenia są równe, niezależnie od tego, jakie relacje wchodzą w skład wyrażeń. Dobrze znanym przykładem prawa algebraicznego jest prawo przemienności sumowania: R u S=S u R. Zachodzi ono niezależnie od tego, jakie elementy należą do relacji R i S, i niezależnie od tego, czy R i S są zbiorami czy wielozbiorami. Istnieją jednak takie prawa algebry relacji, które są spełnione przez konwencjonalne relacje traktowane jako zbiory, a mogą nie być spełnione, gdy dopuścimy relacje w postaci wielozbiorów. Prostym przykładem jest w takim przypadku prawo rozdzielności różnicy względem sumy, czyli (R u ,S~ - T - (R - T) u (S - T). To prawo jest zawsze spełnione dla zbiorów, ale nie jest w ogólnym przypadku spełnione przez wielozbiory. Dlaczego nie zachodzi ono dla wielozbiorów? Załóżmy, że krotka t występuje jednokrotnie w każdym z wielozbiorów R, S i T. Wówczas w relacji opisanej w wyrażeniu po lewej stronie równoważności krotka t występuje jeden raz, a w wyrażeniu po prawej wcale. Gdybyśmy operacje traktowali jako operacje na zbiorach, to krotka t nie wystąpiłaby w żadnym z tych dwóch wyrażeń. Ćwiczenia 4.6.4 i 4.6.5 dają możliwość uzyskania większej praktyki w korzystaniu z praw algebraicznych dla wielozbiorów.
2%2 4. DZIAŁANIA W MODELU RELACYJNYM
Jeśli jakaś krotka zostanie utworzona w trakcie rzutowania wielozbiorów więcej niż jeden raz, to i w wyniku będzie ona występować więcej niż jeden raz. A więc po zrzutowaniu krotek (1, 2, 5), (1, 2, 7) i (1, 2, 8) z relacji R z rys. 4.29 na atrybutyA i B otrzymamy trzy takie same krotki (1, 2). Jeśli wynik potraktujemy jako wielozbiór, to będzie on zawierał trzy wystąpienia tej samej krotki (l, 2), natomiast gdy rzutowanie będzie wykonane jako rzutowanie zbiorów, wówczas wynik będzie zawierał tylko jedno wystąpienie tej krotki.
j 4.6.4. Operacja selekcji dla wielozbiorów
Operację selekcji w przypadku wielozbioru przeprowadza się niezależnie dla każdej krotki. I jak zawsze w przypadku wielozbiorów nie eliminuje się z wyniku powstających powtórzeń.
PRZYKŁAD 4.50
Niech R będzie następującym wielozbiorem: A B C
1 2 5 3 4 6 1 2 7 1 2 7
W wyniku wykonania operacji selekcji na wielozbiorze ~~->6(R) powstaje następujący wielozbiór:
A B C 3 4 6 1 2 7 1 2 7
W wyniku nie występuje tylko pierwsza krotka z R, ponieważ tylko ona nie spełnia warunku wyboru.
0
4.6.5. Iloczyn kartezjański wielozbiorów
Reguła tworzenia iloczynu kartezjańskiego wielozbiorów jest zgodna z intuicją. Tworzymy pary wszystkich możliwych krotek z pierwszej relacji iloczynu z wszystkimi krotkami drugiej relacji, niezależnie od pojawiających się powtórzeń. Zatem jeśli w relacji R krotka t występuje n razy, a w relacji S m razy, to w iloczynie R x S wystąpi ona hm razy.
i
4.6. OPERACJE RELACYJNE NA WIELOZBIORACH Z%3 p j
A B i 1 2 i 1 2
i Relacja R ' I B C
I 2 3 4 5 4 5
Relacja S
A R.B S.B C 1 2 2 3 j
1 2 2 3 1 2 4 5 1 2 4 5 1 2 4 5 1 2 4 5
Iloczyn kartezjauski R X S RYSUNEK 4.30
Obliczenie iloczynu kartezjańskiego wielozbiorów PRZYKŁAD 4.51
Rozważmy relacje R i S przedstawione na rys. 4.30. Iloczyn kartezjański R x S składa się z sześciu krotek, co zostało przedstawione na rys. 4.30(c). Zauważmy, że konwencja odróżniania atrybutów z poszczególnych relacji, którą stosowaliśmy w przypadku zbiorów, ma tutaj także zastosowania. Dlatego atrybut B, który należy do obu relacji R i S, w iloczynie kartezjańskim występuje dwa razy, a określenie relacji, z której pochodzą jego wartości, jest możliwe dzięki właściwemu prefiksowi oznaczającemu nazwę oryginalnej relacji R lub S.
O
4.6.6. Złączenia wielozbiorów
W przypadku złączeń także nie ma niespodzianek. Porównuje się każdą krotkę jednej relacji złączenia z każdą krotką drugiej relacji, i jeśli ta para spełnia warunek złączenia, to powstaje nowa krotka w wyniku złączenia. Z wynikowej relacji nie usuwa się powtórzonych krotek.
PRZYKŁAD 4.52
Relacje R i S przedstawione na rys. 4.30 tworzą naturalne złączenie R ~ S w postaci następującego wielozbioru:
274 4. DZIAŁANIA W MODELU RELACYJNYM A B C
' 1 2 3 1 2 3
Krotka (1, 2) relacji R spełnia warunek złączenia z krotką (2, 3) z relacji S. Ponieważ w relacji R krotka (l, 2) występuje dwa razy, a krotka (3, 4) wystę
'I~ puje w relacji S jeden raz, więc w rezultacie powstają dwie pary, które spełniają warunek złączenia i otrzymujemy krotkę (l, 2, 3). Żadne inne krotki z R i S nie spełniająwarunku złączenia.
'i'I Z kolei w wyniku złączenia teta relacji R i S
R ~a ,~.,~ < ,.eS
powstaje następujący wielozbiór:
A R.B SB C
1 2 4 5
1 2 4 5
1 2 4 5
1 2 4 5
Obliczenie krotek w wyniku tego złączenia przebiega w następujący sposób: Krotki (I, 2) z relacji R oraz (4, 5) z relacji S spełniają warunek złączenia. Ponieważ każda z nich występuje w swojej relacji dwa razy, więc w wyniku powstaną2 x 2 = 4 krotki. Inna para (l, 2) z relacji R wraz z (2, 3) z relacji S nie spełnia warunku złączenia, a więc nie zostaje dołączona do wyniku złą czenia.
D
4.6.7. Zastosowanie reguł Datalogu do wielozbiorów
Jeśli reguła Datalogu nie zawiera zanegowanych podzadań relacyjnych, to możemy dla niej zastosować podobną technikę obliczania selekcji, rzutowania i złączenia wielozbiorów. Wyrażając to opisowo, można stwierdzić, że tworzymy wynik złączenia relacji reprezentowanych przez podzadania, wybieramy z niego te elementy, które spełniają warunki wyboru określone w podzadaniach arytmetycznych, a następnie wykonujemy rzutowanie zgodnie z definicją nagłówka. W każdym kroku stosujemy operację właściwą dla wi el ozb forów.
Takie podęjście jest prostsze w realizacji obliczenia reguł Datalogu niż sposób podany w p. 4.2.4. Przypomnijmy. że tamta technika polegała na tym, że trzeba było przetwarzać osobno każde podzadanie, nie zanegowane i rela
4.6. OPERACJE RELACYJNE NA WIELOZBIORACH 2%S
cyjne, zastępowanie go krotkami relacji powstałej dla predykatu opisanego w podzadaniu. Jeśli otrzymywaliśmy w ten sposób niesprzeczne wartościowania wszystkich zmiennych we wszystkich podzadaniach i równocześnie wszystkie podzadania arytmetyczne były spełnione", to wówczas zmiennym z nagłówka były przypisywane otrzymane wartościowania. Krotki otrzymywane w ten sposób były dołączane do relacji nagłówka.
W przypadku wielozbiorów z nagłówka nie potrzeba eliminować powtórzeń. Poza tym rozpatrujemy wszystkie kombinacje krotek z podzadań, więc jeśli w pewnym podzadaniu jakaś krotka występuje ~ razy, to jest ona rozpatrywana n-krotnie z wszystkimi kombinacjami wszystkich krotek z pozostałych podzadań.
PR7_YKŁAD 4.53
Niech relacje R i S będą opisane, tak jak na rys. 4.30, i niech będzie dana następująca reguła:
H(x, z) ~- R(x, y) AND S(y, z)
Jedyne niesprzeczne wartościowanie (tzn. wartościowanie, przy którym wartość y jest w każdym podzadaniu taka sama) zachodzi, gdy z R do pierwszego podzadania wchodzi krotka (I, 2), a z S do drugiego krotka (2, 3). Ponieważ krotka (1, 2) występuje dwa razy w relacji R, a krotka (3, 4) występuje w relacji S jeden raz, a więc powstaną dwa takie same wartościowania zmiennych: x = 1, y = 2 oraz z = 3. Dla każdego przypisania powstaje taka sama krotka nagłówka (x, z) o wartościowaniu (l, 3). Zatem w nagłówkowej relacji H występuje ta sama krotka (l, 3) dwa razy i nie występujątam żadne inne krotki. Po określeniu atrybutów nagłówka nazwami HI, H2 otrzymujemy jako wynik reguły następującą relację:
Hl H2 1 3 1 3
Mówiąc ogólniej, gdyby krotka (I, 2) występowała w relacji R rr razy, a krotka (2, 3) występowała w relacji S m razy, to krotka (l, 3) wystąpiłaby w relacj i H nm razy.
a
Jeśli relacja jest zdefiniowana kilkoma regułami, to stanowi ona sumę wielozbiorów powstających jako wyniki przetworzenia poszczególnych reguł.
Zauważmy, że w regule nie było zanegowanych podzadań relacyjnych. W przypadku modelu wielozbioru nie można podać jasnych interpretacji znaczenia reguł Datalogu, które zawierają zanegowane podzadania relacyjne.
276
4. DZIAŁANIA W MODELU RELACYJNYM
PRZYKŁAD 4.54
Załóżmy, że relacja Hzostała określona dwiema regułami: H (x, y) ~ S (x, y) AND x > 1
H (x, y) ~ S (x, y) AND y < 5
II~ W relacji S występująwartości takie same jak na rys. 4.30 (b), tzn.: B C
2 3 4 5 4 5 !I
Po przetworzeniu pierwszej reguły do H zostają włączone wszystkie krotki relacji S, ponieważ w każdej krotce pierwsza składowa jest większa od 1. Z zastosowania drugiej reguły do relacji H zostaje dołączona tylko krotka (2, 3), ponieważ krotka (4, 5) nie spełnia warunku y < 5. A zatem w wynikowej 'i'I relacji Hsądwie kopie krotki (2, 3) oraz dwie kopie krotki (4, 5).
o
4.6.8. Ćwiczenia do podrozdziału 4.6
*Ćwiczenie 4.6.1. Załóżmy, że relacja PC jest określona tak samo jak na rysunku 4.10(a), a trzeba obliczyć wartość rzutowania ~cZ~kaY(PC). Jaki wynik otrzymuje się, gdy wyrażenie jest obliczane w konwencji zbiorów. A jaki w konwencji wielozbiorów? Jaka jest wartość średnia krotek otrzymana w przypadku obliczenia w konwencji zbiorów? A jaka, gdy przyjmujemy konwencję wielozbiorow?
Ćwiczenie 4.6.2. Należy wykonać polecenia z ćwiczenia 4.6.1, gdy operacją rzutowania jest ~h,,(PC).
Ćwiczenie 4.6.3. W tym ćwiczeniu korzystamy z relacji „okręty", zdefiniowanej w ćwiczeniu 4.1.3.
a) Wyrażenie ~~~;pr„(Klasy) określa jednokolumnową relację, w której są zapisane kalibry dział poszczególnych klas okrętów. Określić wartości tej relacji w przypadku traktowania wyrażenia jako zbioru oraz jako wielozbioru. Wartość należy obliczać z danych zawartych w ćwiczeniu 4.1.3.
!b) Należy utworzyć wyrażenie algebry relacji, dzięki któremu można uzyskać wartości kalibru największych dział poszczególnych okrętów (nie klas okrętów). Relacje należy traktować jako wielozbiory, tzn. że liczba wystąpień pewnej wartości b określa, ile okrętów ma dany typ działa.
!Ćwiczenie 4.6.4. Pewne prawa algebry relacji prawdziwe dla zbiorów są spełnione również, gdy relacje traktuje się jako wielozbiory. Należy uzasadnić dlaczego poniższe prawa obowiązują zarówno dla zbiorów, jak i dla wielozbiorów.
4.7. INNE ROZSZERZENIA MODELU RELACYJNEGO
277
*a) Prawo łączności dodawania: (R ~ S) u T- R u (S ~ T). i b) Prawo łączności mnożenia: (R n S) n T - R n (S n T).
c) Prawo łączności dla złączenia naturalnego: (R ~a S) ~a T - R ~a (S ~a T). ' d) Prawo przemienności dodawania: (R v S) _ (S v R).
e) Prawo przemienności mnożenia: (R n S) --- (S n R). [ ł f) Prawo przemienności złączenia naturalnego: (R ~a S --- (S ~a R).
g) ~,,(R ~ S) - ~I(R) u ~1,(S~. L jest listą dowolnych atrybutów.
*h) Rozdzielność dodawania względem mnożenia: R v(S n 7j = (R ~ S) n(R v T).
i) ~c AND o(R) = 6c~R) n ~~(R), gdzie C i D oznaczają dowolne warunki
nałożone na krotki relacji R. ' .
!!Ćwiczenie 4.6.5. Prawa algebraiczne, które zdefiniowano poniżej, zachodzą w przypadku zbiorów, ale nie w przypadku wielozbiorów. Należy uzasadnić, dlaczego zachodzą one dla zbiorów, oraz podać kontrprzykłady, które wykażą, że te prawa nie obowiązują dla wielozbiorów.
*a) (R n ,5) - T - R n (S - T). ' b) Prawo rozdzielności mnożenia względem dodawania: R n (S ~T) --- (R n S)
~(RnT). c) ~~~ oR v(R) --- ~~(R) u ~~(R), gdzie C i D oznaczają dowolne warunki nałożone na krotki relacji R.
4.7. Inne rozszerzenia modelu relacyjnego
Istnieją pojęcia i operacje formalnie nie należące do modelu relacyjnego, ale ze względu na swoją użyteczność zostały wprowadzone do języków zapytań. W bieżącym rozdziale omówimy operacje, które modyfikują relacje, tworzą agregacje danych, takie jak suma danych z kolumn, a także służą do tworzenia „perspektyw" lub nazywanych funkcji działających na relacjach. Każde z tych pojęć i operacji ma swój odpowiednik w języku zapytań do baz danych SQL, będą one omówione w rozdziale 5. Części z nich poświęcimy także uwagę przy okazji omawiania języka OQL w rozdziale 8.
4.7.1. Modyfikacje
Algebrę relacyjną oraz Datalog można traktować jako języki zapytań, ponieważ można w nich określić relację lub uzyskać wartość funkcji zastosowanej do określonej relacji. Zapytania są bardzo ważne, ale taka baza danych, której zawartości nie można by zmieniać, nie bylaby interesująca. Z tego powodu wszystkie języki systemów baz danych zawierają zarówno mechanizmy do zapisu zapytań do bazy danych, jak i do modyfikowania jej zawartości. Minimalny zbiór powinien zawierać następujące rozkazy:
Z%Ó 4. DZIAł.ANIA W MODELU RELACYJNYM
1. Wstawianie krotek do relacji. 2. Usuwanie krotek z relacji.
3. Modyfikowanie zapisanych krotek przez zmianę jednej lub kilku składowych.
4.7.2. Agregacje danych
Działania w algebrze relacji wykonuje się na poszczególnych krotkach niezależnie od innych krotek tej samej relacji. Czasami jednak trzeba przetworzyć wiele krotek relacji, po to by uzyskać jedną wartość zagregowaną, tzn. wartość funkcji działającej na wielu w pewien sposób przemieszanych krotkach. W przykładzie filmowym mogąto być następujące zadania:
• Obliczenie liczby różnych filmów, które występująca relacji Film.
• Utworzenie tabeli zawierającej sumę czasu trwania filmów wyprodukowanych przez poszczególne studia filmowe.
i~ • Odnalezienie dyrektora produkcji, który posiada sieć o największej wartości.
Języki zapytań baz danych umożliwiają zastosowanie operatorów agregują cydr dane, głównie liczby krotek, sumy, wartości średniej, minimum i maksimum wartości do kolumn relacji.
4.7.3. Perspektywy
Wyrażenia algebry relacji można traktować jako „program", który służy do obliczenia pewnej relacji R oraz do wydrukowania lub prezentacji w innej formie jej zawartości. Można jednak jeszcze w inny sposób interpretować wyrażenia algebry relacji. Można rozumieć je jako formuły, które definiują pewną relacje, powstającą dopiero wówczas, gdy formuła zostanie przetworzona dla pewnych danych relacji stanowiących jej argumenty. Tego typu formuły w terminologii baz danych nazywają się perspektywami. Przekonamy się, że perspektywy otrzymują zazwyczaj nazwy i pod tymi nazwami są używane jako argumenty innych wyrażeń relacyjnych, tak jakby same były relacjami.
W regułach Datalogu także jest istotne rozróżnienie między zapytaniem a perspektywą. Przypomnijmy sobie, że predykaty lub relacje definiowane regułami Datalogu były nazywane „intensjonalnymi", tzn. że te relacje nie musiały istnieć w rozwiniętej postaci ekstensjonalnej ani przechowywanej. Perspektywa jest pojęciem, które odpowiada właśnie predykatowi intensjonalnemu. A predykatu intensjonalnego można było używać w treści reguł, z kolei perspektyw można używać jako argumentów wyrażeń algebraicznych.
4.8. PODSUMOWANIE Z%9
Zestaw reguł Datalogu możemy zastosować do bazy danych zawierającej zapamiętane relacje, z kolei perspektywę możemy obliczyć wtedy, kiedy jest to potrzebne.
4.7.4. Wartości NULL ' W wielu przypadkach trzeba składowej krotki przypisać jakąś wartość,
a nie wiadomo jaką konkretnie. Na przykład wiemy, że Kevin Kostner jest gwiazdą filmową, ale nie znamy jego daty urodzenia. A przecież każda krotka relacji gwiazdy zawiera składową dataurodzenia, więc co tam wpiszemy? Przyjmiemy wówczas, że ta składowa ma wartość oznaczaną NULL i jest nazywana wartoście pustci albo pull. Wartość NoLL jest w pewnym sensie taką samą wartością jak każda inna wartość. Jednakże z innego punktu widzenia to nie jest wartość. Na przykład przy tworzeniu złączenia dwóch relacji składowe, w których występuje NULL, nie są traktowane jako równe. A jeszcze bardziej konkretny przykład: jeśli w krotkach dwóch różnych gwiazd filmowych składowa dataurodzenia mają wartość Nt1LL, to wcale nie oznacza, że te dwie daty urodzenia są równe.
Wartości null można interpretować bardzo różnie. Poniżej przedstawia
my najpopularniejsze z nich. ' 1. Wartość nieznana: oznacza to mniej więcej tyle, że: „Wiem, że ist- 'i nieje pewna wartość, którą można by tu wpisać, ale jej nie znam".
Dobrym przykładem jest w tym przypadku omówiona powyżej data urodzenia.
2. Wartość niestosowalna: „żadna wartość nie ma tu sensu". Gdyby na
przykład w relacji Gwiazda istniał atrybut współmałżonek, to 'h: w przypadku gwiazdy stanu wolnego z konieczności wartość tego
atrybutu jest pusta, wcale nie dlatego, że nie jest znana ta wartość, ale I dlatego że wcale jej nie ma. i;' 3. Wartość zastrzeżona: „ Nie mamy prawa znać wartości w danym po
lu". Na przykład może tak się dziać w przypadku zastrzeżonych numerów telefonów, pewne składowe tego atrybutu mogą być warto
ściami NULL właśnie z takiego powodu. ;~. r
4.8. Podsumowanie
~ Algebra relacji: Ta algebra stanowi ważną postać języka zapytań dla modelu relacyjnego. Jej najważniejszymi operatorami są: suma, przecięcie, różnica, selekcja, rzut, iloczyn kartezjański, złączenie naturalne oraz złączenie teta i przemianowanie.
280
4. DZIAŁANIA W MODELU RELACYJNYM
1 Datalog: Jest to inna, tyta razem wywodząca się z logiki, postać języka zapytań dla modelu relacyjnego. W Datalogu definiuje się predykaty i relacje za pomocą reguł, w których występują podzadania two
'I rzące treść reguły. Podzadania i nagłówek są atomami, a atom jest (czasami zanegowanym) predykatem, którego wartość zależy od szeregu argumentów. Wszystkie te zapytania, które można zdefiniować w postaci wyrażeń algebraicznych, można także wyrazić w Data]ogu.
1 Datalog rekurencyjny: W regułach Datalogu można korzystać z rekurencji, tzn. że definicja relacji zawiera jej nazwę. Interpretację rekurenc i w Datalo u stanowi na mnie sz unkt sta cz li na mnie sz
,, j g J J Y p łY~ Y J J Y zbiór krotek definiowanej relacji, który sprawia, że relacja z nagłówka jest równa wynikowi wyliczonemu w treści reguły.
1 Negacja warstwowa. W przypadku gdy reguła zawiera zarówno negację, jak i rekurencję, punkt stały nie musi być jednoznacznym rozwiązaniem (może ich być więcej niż jedno). Zdarza się więc, że taka
I reguła nie może zostać zinterpretowana. Stąd zrodziło się pojecie negacji warstwowej. Dzięki temu można w niektórych regułach zawiei,
ji' rających negację i rekurencję określić, które rozwiązanie stałopunktowe jest właściwą interpretacją reguły.
1 Relacje jako wielozbiory: W komercyjnych systemach baz danych re
'i'I lacje są traktowane jako wielozbiory, ponieważ dopuszczalne jest tam powtarzanie się w relacji tych samych krotek. Funkcje algebry relacji
j'I można rozszerzyć na pojęcie wielozbioru, ale niektóre prawa algebraiczne przestają wówczas obowiązywać.
~ Relacje w komercyjnych systemach baz danych: W komercyjnych ~I' systemach baz danych poza modelem wielozbioru są dostępne polece!I nia, które nie mają odpowiedników ani w algebrze relacji, ani w Dai
` talogu. Te polecenia obejmują: wstawianie, usuwanie oraz modyfiko'I
wanie krotek z relacji, agregacje wartości w relacji, a także krotki z wartościami pustymi.
4.9. Literatura do rozdziału 4
Podstawowy raport dotyczący modelu relacyjnego [4] zawiera także opis algebry relacji. Natomiast język zapytań logiki nie ma już tak jasno sprecyzowanego momentu powstania. We wczesnych pracach dotyczących modelu relacyjnego Codd [5] wprowadził rachunek relacyjny, który był pewną postacią logiki pierwszego rzędu. Rachunek relacyjny jest językiem wyrażeń, przypominąjącym trochę algebrę relacji i, co udowodniono, o mocy ekspresji równoważnej algebrze relacji.
Powstanie Datalogu, którego składnia bazuje na regułach, było inspirowane językiem programowania Prolog. Jest to język mocniejszy niż rachunek relacyjny, ponieważ zawiera rekurencję. Praca [6] jest bardzięj związana z ideą języka logiki jako języka zapytań; w pracy [2] natomiast więcej uwagi przywiązano do rozważania pojęć logiki w kontekście baz danych. A pierwszą pracą, która opisuje zastosowanie zapyrtań do określenia więzów, jest [8].
4.9. LITERATURA DO ROZDZIAŁU 4 2 S I
Pomysł dokonywania właściwego wyboru rozwiązania stałopunktowego za pomocą negacji warstwowej został zaprezentowany w opracowaniu [3], natomiast zastosowanie tego podejścia w Datalogu zostało po raz pierwszy przedstawione niezależnie w pracach [1], [7] oraz [10]. Praca [10] zawiera opis zagadnień dotyczących negacji warstwowej, związków między algebrą relacji, Datalogiem a rachunkiem relacyjnym, a także przetwarzania reguł Datalogu zawierających negacje lub bez negacji.
1. Apt K.R., Blair H., Walker A.: Towards a theory of declarative laiowledge, w Foundations of Deductive databases and Logic Programming (J. Minkler, ed.) s. 89-148, Morgan-Kaufman, San Francisco, 1988.
2. Bancilhon F., Ramakrishnan R.: An amateur's introduction to recursive query-processing strategies: ACM SIGMOD lntl. Conf. On Management of Data, s. 16-52, 1986.
3. Chandra A.K., Harel D.: Structure and complexity of relational queries. J Computer and Svstem Sciences 25:1, s. 99-128.
4. Codd E. F.: A relational model for large shared data banks, Comm. ACM 13:6, s. 377-387, 1970.
5. Codd E. F.: Relational completeness of database sublanguages, w Database Systems (R. Rustin, ed.). Prentice Hall, Englewood Cliffs, NJ, 1972.
6. Gallaire H. Minker J.: Logic ofdatabases. Plenum Press, New York, 1978.
7. Naqvi S.: Negation as failure for first-order queries. Proc. Fifth ACM Symp. On Principles ofDatabase systems, str. 114-122, 1986.
8. Nicolas J. M.: Logic for improving integrity checking in relational databases. Acta infor-matica 18:3, s. 227-253, 1982.
9. Ulhnan J. D.: Pr-inciples of Database and Knowledge-Base Systenas, Volume I. Computer Science Press, New York, 1988.
10. Van Gelder A.: Negation as failure using tight derivations for general logic programs, w Foundations of Deductive databases and Logic Programming (J. Minkler, ed.) s. 149176, Morgan-Kaufman, San Francisco, 1988.