~. JFZYK 13AZ DANYChI SQL,

myParamount i na nich operuje zapytanie. Dlatego wykonując dwa razy to samo zapytanie na jednej perspektywie, można uzyskać inne wyniki, mimo że sama relacja FilmyParamount nie uległa zmianie - mogła jednak w mię­dzyczasie zmienić się tabela bazowa.

PRZYKŁAD x.38

Dla perspektywy FilmyParamount można określić zapytanie tak, jakby była ona zwykłą tabelą:

SELECT tytuł

EROM FilmyParamount WHERE rok = 1979;

Definicja perspektywy FilmyParamount jest wówczas użyta po to, by prze­kształcić powyższe zapytanie do nowej postaci, w której przeszukiwane są bezpośrednio krotki tabeli bazowej Film. Sposób przekształcania zapytań określonych dla perspektyw w zapytania określone na tabelach bazowych zostanie przedstawiony dopiero w p. 5.8.5. Jednakże w prezentowanym przy­kładzie nie jest trudno określić, co oznacza zapytanie zdefiniowane dla per­spektywy. FilmyParamount różnią się od relacji Filmy w dwóch punktach:

1. Do relacji FilmyParamount dołącza się tylko atrybuty tytuł oraz rok.

2. Warunek nazwastudia = `Paramount' może być klauzulą do­wolnego warunku wHERE odnoszącego się do relacji FilmyParamo­unt.

Ponieważ w wyniku zapytania powinien zostać umieszczony wyłącznie atry­but tytuł, więc warunek 1) nie jest istotny. A zatem ze względu na punkt 2) trzeba tylko do klauzuli wHERE dołączyć warunek nazwastudia = `Para­mount' . Wówczas można już, bez zmiany znaczenia zapytania, w klauzuli EROM w zapytaniu zastąpić nazwę filmyParamount nazwą relacji Film. Czyli zapytanie:

SELECT tytuł EROM Film

WHERE nazwaStudia = `Paramount' AND rok = 1979;

dotyczy tabeli bazowej Film, ale daje ten sam wynik co początkowe zapyta­nie określone na perspektywie FilmyParamount. Wykonanie tego typu przekształceń należy do zadań systemu SQL. Przedstawiliśmy ten proces tyl­ko po to, aby zobrazować, na czym polega wykonanie zapytania określonego na perspektywie.

0

~.8. DEFINIOWANIE PERSPEKTYW 343

PRZYKŁAD 5.39

Pisanie zapytań określonych zarówno na perspektywach, jak i tabelach, jest także dopuszczalne. A oto przykład:

SELECT DISTINCT nazwiskoGwiazdy EROM FilmyParamount, GwiazdyW

WHERE tytuł = tytułFilmu AND rok = rokFilmu;

W wyniku przedstawionego zapytania mają zostać określone nazwiska gwiazd, które wystąpiły w filmach wyprodukowanych przez wytwórnię Pa­ramount. Zastosowanie klauzuli DISTINCT gwarantuje, że każda gwiazda zostanie dołączona tylko jeden raz, nawet jeśli wystąpiła w kilku filmach wytwórni Paramount.

O

PRZYKŁAD 5.40

Teraz rozważymy trochę bardziej złożone zapytanie definiujące perspektywę. Zadanie polega na określeniu relacji ProdFilm, która ma zawierać tytuły filmów oraz nazwiska ich producentów. Zapytanie definiujące tę perspektywę jest określone na dwóch relacjach:

Film (tytuł, rok, długość, czyKolor, nzawaStudia, producentC#)

z której wybiera się numery certyfikatów producentów, oraz z relacji:

FilmDyr(nazwisko, adres, cert#, cenaSieci)

która służy do odtworzenia nazwiska producenta na podstawie numeru jego certyfikatu. Zapytanie zapiszemy w następujący sposób:

1) CREATE VIEW FilmProd AS 2) SELECT tytuł, nazwisko 3) EROM Film, FilmDyr

4) WHERE producentC# = cert#;

Dla tak określonej perspektywy możemy tworzyć zapytania tak samo, jakby była ona przechowywaną relacją. Na przykład, aby wyszukać producenta Przeminęło z wiatrem, można utworzyć następujące zapytanie:

SELECT nazwisko EROM FilmProd

WHERE tytuł = 'Przeminęło z wiatrem';

344 5. JĘZYK BAZ DANYCH SQL

Jak w przypadku innych perspektyw, tak samo i tu zapytanie jest traktowane jakby było równoważnym zapytaniem określonym na tabelach bazowych, czyli jako zapytanie:

SELECT nazwisko EROM Film, FilmDyr

WHERE producentC# = cert# AND tytuł = 'Przeminęło z wiatrem';

0

5.8.3. Przemianowanie atrybutów

Czasami zamiast korzystać z nazw atrybutów występujących w definicji perspektywy, może się okazać wygodne, żeby w perspektywie wybrać inne nazwy dla atrybutów. Możemy to zrobić, umieszczając w instrukcji cREATE vlEw wybrane nowe nazwy w postaci listy ujętej w nawiasy, po nazwie per­spektywy, a przed zapytaniem definiującym. Definicję z przykładu 5.40 mo­żemy zapisać w następujący sposób:

CREATE VIEW FilmProd(tytułFilmu, nazwiskoProd) AS SELECT tytuł, nazwisko

EROM Film, FilmDyr

WHERE producentC# = cert#;

Perspektywa jest taka sama jak poprzednio, ale w nagłówkach kolumn za­miast nazw tytuł, nazwisko wystąpią teraz atrybuty o nazwach tytuł­Filmu,nazwiskoProd.

5.8.4. Modyfikowanie perspektyw

W pewnych okolicznościach można wykonywać działania wstawiania, usuwania oraz zmian perspektyw. Po pierwsze jednak trzeba określić znacze­nie takich działań w przypadku perspektyw, które przecież nie istnieją w sen­sie fizycznym, tak jak to występuje przy tabelach bazowych (czyli relacji przechowywanych). Co zatem oznacza wstawienie krotki do perspektywy? Gdzie ta krotka zostanie umieszczona i w jaki sposób system baz danych roz­pozna, że ma ona być dołączona do danej perspektywy?

W wielu przypadkach odpowiedź jest prosta: „nie można tak robić". Jed­nakże przy bardzo prostych perspektywach, tak zwanych „modyfikowal­nych", można przekładać modyfikowanie perspektywy na równoważne dzia­łanie na tabeli bazowej, które zostanie dokonane na niej zamiast na perspek­tywie. W języku SQL2 w sposób formalny określa się, kiedy jest dopuszczal­na modyfikacja perspektywy. Zasady zapisane w języku SQL są skompliko­

5.8. DEFINIOWANIE PERSPEKTYW 315

wane, krótko można je streścić w następujących słowach: modyfikacje per­spektyw są dopuszczalne tylko wtedy, kiedy perspektywy są zdefiniowane przez selekcję (czyli SELECT lub SELECT DISTINCT) pewnych atrybutów z jednej relacji R (która sama także może być perspektywą modyfkowalną). Muszą jednak być speknione następujące warunki techniczne:

• Klauzula wHERE nie może zawierać zapytania dotyczącego relacji R.

• W klauzuli sELECT musi być dostatecznie dużo atrybutów po to, by dla każdej krotki, którą wstawia się do perspektywy, można było wprowadzić pozostałe atrybuty z wartościami NULL lub domyślnymi, i aby w relacji bazowej istniała krotka, która stanowi podstawę dla krotki umieszczanej w perspektywie.

PRZYKŁAD 5.41

Załóżmy, ze do perspektywy FilmyParamount z przykładu 5.37 będzie wstawiana następująca krotka:

INSERT INTO FilmyParamount VALUES (`Star Trek', 1979);

Perspektywa FilmyParamount nieomal spełnia warunki modyfikowalności z SQL2, ponieważ wchodzą do niej dane tylko z jednej relacji

Film (tytuł, rok, długość, czyKolor, nazwaStudia, producentC#)

której krotki ograniczono do wybranych składowych. Problem pojawia się przy określaniu wartości nazwastudia, ponieważ ten atrybut nie należy do perspektywy. Zatem jego wartością w krotce perspektywy nie jest ' Paramo­unt' , lecz NULL.

Można jednak doprowadzić perspektywę FilmyParamount do postaci, która umożliwi wykonanie modyfikowania. Wystarczy do klauzuli sELECT dołączyć atrybut nazwastudia, mimo iż wiemy, że to będzie nazwa Para­mount. Tak zmieniona definicja będzie miala następującą postać:

1) CREATE VIEW FilmyParamount AS

2) SELECT nazwaStudia, tytuł, rok 3) EROM Film

4) WHERE nazwaStudia = 'Paramount';

Wówczas instrukcja wstawiania krotki do perspektywy przyjmie następującą postać:

INSERT INTO FilmyParamount

VALUES (`Paramount', 'Star Trek', 1979);

346 5 JĘZYK BAZ DANYCH SQL

W jej wyniku musi powstać nowa krotka relacji Film, która będzie sta­nowić podstawę do otrzymania krotki o wartościach z instrukcji wstawiania przy przeglądaniu perspektywy FilmyParamount. W rozpatrywanym przy­kładzie w krotce składowa atrybutu nazwastudia przyjmie wartość ' Para­mount' , składowa tytuł - wartość ' star Trek' , a składowa rok będzie określona jako 1979.

Należy także określić wartości pozostałych trzech atrybutów relacji Film, które nie występują w perspektywie: długość, czyKolor i produ­centC#. Jednak ich wartości nie da się zgadnąć. A zatem we wstawianej krotce do relacji Film jako wartości składowych muszą być wstawione od­powiednie wartości donmiemane: albo NULL, albo inna wartość domniemana, którą zdefiniowano dla atrybutu lub jego dziedziny. Na przykład, jeśli dla atrybutu długość określono wartość 0, a dla pozostałych dwóch wartość NULL, to krotka wstawiana do relacji Film wygląda następująco:

tytul I rok I dlugość I czyKolor I nazwaStudia I prodz `Star Trek' 1079 0 NULL `Paramount' NULL

O

Z perspektyw modyfikowalnych można także usuwać krotki. Usuwanie, podobnie jak wstawianie, jest przetwarzane w relacji bazowej R, a w jego wyniku zostająz relacji R usunięte te krotki, które nie powinny już generować żadnych danych do perspektywy.

PRZYKŁAD 5.42

Tym razem zadanie polega na usunięciu z perspektywy modyfikowalnej Fil­myParamount wszystkich filmów, w których tytułach występuje „Trek". Instrukcja usuwania ma postać następującą:

DELETE EROM FilmyParamount WHERE tytuł LIKE `~Trek%';

Powyższe usuwanie zostanie przekształcone do postaci równoważnego usu­wania, określonego dla bazowej relacji Film. Drobna zmiana polega na dołą czemu do klauzuli WHERE warunku określającego perspektywę FilmyPara­mount.

Poniższy zapis

DELETE EROM Film

WHERE tytuł LIKE `oTrek%' AND nazwastudia = `Paramo­unt';

określa instrukcję faktycznie wykonywaną.

0

5,8. DEFINIOWANIE PERSPEKTYW 347

Również instrukcja modyfikowania jest przetwarzana w relacji bazowej. Modyfikowanie perspektywy powoduje zmodyfikowanie tych wszystkich krotek w relacji bazowej, których dane sąwidoczne poprzez perspektywę.

PRZYKŁAD 5.43

Modyfikowanie perspektywy polegające na wykonaniu następującej instrukcji:

UPDATE FilmyParamount SET rok = 1979

WHERE tytuł - 'Film Star Trek';

zostaje przekształcone w następujący sposób:

UPDATE Film SET rok =1979

WHERE tytuł = 'Film Star Trek' AND nazwaStudia = 'Pa­ramount';

0

Dlaczego niektórych perspektyw nie można modyfikować? Rozważmy perspektywę FilmProd, którą określono w przykładzie 5.40, a która łączy tytuł filmu z nazwiskiem producenta. Według zasad SQL2 ta perspektywa nie jest modyfikowalna, ponieważ w klauzuli FROM znajdują się dwie relacje: Film oraz FilmDyr. Załóżmy, że należy wstawić nastę­pującą krotkę:

(`Największy spektakl na świecie', `Cech B. DeMille')

Należy wstawić wówczas krotki do obu relacji i Film i FilmDyr. Dla atrybutów, takich jak długość czy adres, można wstawić wartości do­mniemane, ale jakie wartości przyjąć dla atrybutów cert# lub produ­centc#, które mają określać numer certyfikatu pana DeMille? Możemy w obu przypadkach użyć wartości NULL. Jednakże przy wyliczaniu złączeń wartości NULL nie traktuje się jako równych (zob. p. 5.9.1). A więc nie można filmu 'Największy spektakl na świecie' połączyć z pro­ducentem Cecil B. DeMille, w perspektywie FilmProd, tak by zo­stała spełniona intencja zamierzonej modyfikacji.

Ostatnia z modyfikacji perspektyw polega na ich usuwaniu. Można ją wykonywać bez względu na to, czy perspektywa jest, czy też nie jest modyfi­kowalna. Stosuje się wówczas standardową instrukcję DROP:

DROP VIEW FilmyParamount;

348 5. JĘZYK BAZ DANYCH SQL

Taka instrukcja likwiduje definicję perspektywy, a zatem nie można już dłu­żej określać zapytań ani wydawać poleceń modyfikowania tej perspektywy. Jednakże polecenie DROP w odniesieniu do perspektywy nie ma wpływu na dane, które są z nią stowarzyszone, podczas gdy polecenie:

DROP TABLE Film

nie tylko usuwa tabelę Film. Uniemożliwi ono również korzystanie z per­spektywy FilmyParamount, ponieważ każde zapytanie dotyczące tej per­spektywy faktycznie odnosi się do danych nieistniejącej już w tej chwili rela­cji Film.

5.8.5. Interpretowanie zapytań, które dzialają na perspektywach

Mimo że dokładny opis semantyki zapytań z perspektywami wychodzi poza zakres naszej książki, to jednak możemy dowiedzieć się czegoś na ten temat, gdy prześledzimy przebieg interpretowania takich zapytań. Ograni­czymy się tutaj tylko do zapytań i perspektyw, które dają się wyrazić w alge­brze relacji, podczas gdy w SQL można dodatkowo interpretować jeszcze operatory odpowiadające działaniom grupowania i agregacji.

Podstawowy sposób interpretowania zapytań przedstawiono na rys. 5.14. Zapytanie Q zostało zapisane w postaci drzewa algebry relacji. W liściach tego drzewa występują pewne relacje, które są perspektywami. Wyróżniono dwa takie liście, oznaczone literami V oraz W. Aby zinterpretować Q w tabe­lach bazowych, trzeba posłużyć się definicjami perspektyw V i W. Także te definicje zostały wyrażone w notacji algebry relacji.

Q

V W

RYSUNEK 5.14

Podstawienie definicji perspektywy zamiast referencji perspektywy

Aby otrzymać zapytanie określone na tabelach bazowych równoważne Q, każdy liść odpowiadający perspektywie zastępujemy drzewem jej definicji. Na rysunku 5.14 pokazano, że liście o etykietach V i W zostały zastąpione drzewami, które definiują odpowiednio V i W. Drzewo wynikowe jest zapyta­niem równoważnym z Q, ale działającym wyłącznie na tabelach bazowych.

5.8. DEFINIOWANIE PERSPEKTYW

PRZYKŁAD 5.44

349

Rozważmy teraz definicję perspektywy oraz zapytanie z przykładu 5.38. De­finicja perspektywy FilmyParamount jest następująca:

1) CREATE VIEW FilmyParamount AS 2) SELECT tytuł, rok

3) FROM Film

4) WHERE nazwaStudia = `Paramount';

Na rysunku 5.15 przedstawiono drzewo wyrażenia zapytania definiującego tę perspektywę.

tytuł, rok

ónazwaStudia = `Paramount'

Film

RYSUNEK 5.15

Drzewo wyrażenia dla perspektywy FilmyParamount

tytuł

Grok = 19'79

FilmyParamount RYSUNEK 5.16

Drzewo wyrażenia zapytania

Zapytanie z przykładu 5.38 dotyczy filmów wyprodukowanych w 1979 r. w wytwórni Paramount.

SELECT tytuł

EROM FilmyParamount WHERE rok = 1979;

Drzewo wyrażenia tego zapytania zostało przedstawione na rys. 5.16. Jeden z liści tego drzewa oznacza perspektywę FilmyParamount.

Zapytanie zinterpretujemy, wstawiając drzewo z rys. 5.15 zamiast liścia FilmyParamount w drzewie z rys. 5.16. Drzewo wynikowe przedstawiono na rys. 5.17.

350

tytuł Grok = 1979 ~tytui, rok

ónazwaStudia = `Paramount'

Film RYSUNEK 5.17

Wyrażenie zapytania w terminach tabel bazowych

5. JĘZYK BAZ DANYCH SQL

Drzewo przedstawione na rys. 5.17 stanowi akceptowalną interpretację zapytania, która jest jednak niepotrzebnie zbyt skomplikowana. System SQL przekształci je do postaci, która przypomina drzewo wyrażenia zapytania z przykład u 5 .3 8:

SELECT tytuł EROM Film

WHERE nazwaStudia = 'Paramount' AND rok = 1979

W tym celu można na przykład przesunąć rzutowanie ~tYt„ł, rok powyżej selekcji 6rox = 19,9. Opóźnienie wykonania selekcji nie ma bowiem wpływu na znaczenie wyrażenia. Teraz następują bezpośrednio jedno po drugim dwa rzutowania, jedno na atrybuty tytuł i rok, a drugie na sam tytuł. Wyraź­nie widać, że pierwsze z nich jest nadmiarowe. A więc można je wyelimino­wać. Czyli dwa rzutowania można zastąpić w tym przypadku jednym rzuto­waniem na atrybut tytuł.

tytuł

Grok = 1979 AND nazwaStudia = `Paramount'

Film

RYSUNEK 5.18

Uproszczone zapytanie o tabele bazowe

5.8. DEFINIOWANIE PERSPEKTYW

351

Można także polączyć dwie selekcje. Zawsze bowiem można dwie następu­jące po sobie selekcje połączyć w jedną przez połączenie warunków wyboru spójnikiem AND. Na rysunku 5.18 zostało przedstawione drzewo wyrażenia wy­nikowego. Wyrażenie wynikowe można zapisać również w sposób następujący:

SELECT tytuł EROM Film

WHERE nazwaStudia = 'Paramount' AND rok = 1979;

5.8.6. Ćwiczenia do podrozdziału 5.8

Ćwiczenie 5.8.1. Na podstawie następujących tabel bazowych:

GwiazdaFilmowa(nazwisko, adres, płeć, dataUrodzenia) FilmDyr(nazwisko, adres, cert#, cenaSieci)

Studio (nazwisko, adres, prezC#)

należy utworzyć następujące perspektywy.

O

*a) Perspektywę BogatyDyr, do której dołącza się atrybuty: nazwisko, adres, numer certyfikatu i wartość sieci wszystkich dyrektorów, których sieci są warte co najmniej 10 000 000 $.

b) Perspektywę Prezesstudia, która zawiera nazwiska, adresy i numery certyfikatów tych wszystkich dyrektorów, którzy są prezesami studia.

c) Perspektywę GwiazdaDyr, zawierającą nazwiska, adresy, płeć, daty uro­dzenia, numery certyfikatów i wartość sieci wszystkich osób, które są za­równo gwiazdami filmowymi, jak i dyrektorami produkcji.

Ćwiczenie 5.8.2. Które z perspektyw utworzonych w poprzednim ćwiczeniu są mo­dyfikowalne?

Ćwiczenie 5.8.3. Należy zapisać poniższe zapytania tak, by dotyczyły tylko perspek­tyw z ćwiczenia 5.8.1, a nie odwoływały się do tabel.

a) Wyszukać nazwiska wszystkich kobiet, które są jednocześnie aktorkami i dyrektorami produkcji.

*b) Podać nazwiska tych dyrektorów produkcji, którzy są prezesami studiów i których sieci są warte nie mniej niż 10 000 000 $.

!c) Podać nazwiska wszystkich prezesów, którzy są gwiazdami filmowymi i których sieci sąwarte nie mniej niż 50 000 000 $.

*!Ćwiczenie 5.8.4. Na podstawie perspektyw oraz zapytań z przykładu 5.40 należy:

a) Utworzyć drzewo wyrażenia perspektywy FilmProd.

b) Utworzyć drzewo wyrażenia dla zapytania z tego przykładu.

c) Z odpowiedzi a) i b) utworzyć nowe wyrażenie zapytania, które odwołuje się do tabel bazowych.

3 SZ 5. .TĘZYK BAZ DANYCH SQL

d) Wyjaśnić, w jaki sposób zmienić wyrażenie utworzone w punkcie c) tak, aby było ono równoważne wyrażeniu, które pasuje do rozwiązania z przykładu 5.40.

!Ćwiczenie 5.8.5. Każde z zapytań z ćwiczenia 5.8.3 należy wyrazić jako zapytanie lub perspektywę w terminach algebry relacji, zastąpić w zapytaniach perspektywy ich definicjami algebraicznymi, a następnie jak najbardziej uprościć wyrażenia wyniko­we. W końcu należy zapisać zapytania w SQL, które są równoważne otrzymanym wyrażeniom, a które odnoszą się tylko do tabel bazowych.

Ćwiczenie 5.8.6. Za pomocątabel bazowych:

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

z ćwiczenia 4.1.3 nalewy:

a) Zdefiniować perspektywę okrętyBrytyjskie, która dla wszystkich okrętów brytyjskich zawiera ich klasy, typy, liczby dział, kaliber dział, wy­porność oraz rok wodowania.

b) Korzystając z perspektywy zdefiniowanej w a), należy utworzyć zapytanie o liczbę dział i wyporność wszystkich brytyjskich okrętów bojowych, które zwodowano przed 1919 r.

!c) Należy przedstawić zapytanie z punktu b) i perspektywę z a) jako wyraże­nia algebry relacji, następnie zastąpić w wyrażeniu zapytania perspektywę jej wyrażeniem, a potem uprościć powstałe wyrażenie.

!d) Zapisać wyrażenie z punktu c) jako zapytanie SQL, które dotyczy tabel ba­zowych Klasy I Okręty.

5.9. Wartości NULL oraz zsączenia zewnętrzne

W bieżącym podrozdziale omówimy sposób korzystania w języku SQL z wartości NULL. Bardzo ważne zastosowanie t~ULL zachodzi przy wyliczaniu złączenie wówczas, gdy należy chronić dane, a krotka z jednej relacji nie daje się połączyć z żadną krotką pewnej innej relacji. Taka wersja złączenia nazy­wa się złc~czenien2 zew~aętrznym. Omówimy kilka wariantów implementacji złączenia zewnętrznego. Operator złączenia zewnętrznego jest dostępny w standardzie SQL2, ale wcześniejsze wersje SQL przeważnie już dopusz­czają stosowanie wartości NULL.

5.9.1. Dzialania na wartości NULL

W naszej książce już kilka razy omówiono zastosowanie wartości NULL w języku SQL. W punkcie 4.7.4 omówiono na przykład zastosowanie NULL przy reprezentowaniu wartości nieznanych lub nieistniejących. Wartości NULL są stosowane w krotkach wstawianych do relacji wówczas, gdy w pole­

5.9. WARTOŚCI NULL ORAZ ZŁĄCZENIA ZEWNĘTRZNE 3 S 3

Geniu nie określono wszystkich składowych wstawianej krotki. Wartość NULL jest wstawiana zamiast brakujących wartości, chyba że określono inne warto­ści domniemane. Przekonamy się, że źródlem pojawienia się w bazie danych wartości NULL sątakże złączenia zewnętrzne.

Pułapki związane z NULL

Istnieje pokusa, aby w SQL2 stosować wartość NULL wówczas, gdy nie można określić wartości, która „nie jest znana, ale na pewno istnieje". Jed­nakże ta intuicja w niektórych sytuacjach okazuje się zawodna. Załóżmy na przykład, że x stanowi pewną składową, której dziedziną są liczby cał­kowite. A zatem należy sądzić, że bez względu na wartość x wyrażenie 0 * x będzie miako wartość 0, ponieważ dowolna wartość calkowita prze­mnożona przez 0 daje w wyniku 0. Ale gdy x ma wartość NULL, to stosuje się zasadę (1) z p. 5.9.1, czyli iloczyn 0 i NULL ma wartość NULL. Można by też sądzić, że x - x przyjmuje wartość 0, ponieważ bez względu na wartość x różnica z wartością x daje w wyniku 0. Jednakże i w tym przy­padku stosuje się zasadę (1) i w wyniku powstaje wartość NULL.

Przy działaniach z wartością NULL należy pamiętać dwie reguły:

1. Jeśli jako argument działania arytmetycznego takiego jak x lub + wy­stępuje NULL i pewna inna wartość, być może też NULL, to wynikiem jest wartość NULL.

2. Przy porównywaniu wartości NULL z pewną inną wartością, być może także NULL, za pomocą operatorów algebraicznych takich jak =lub > w wyniku powstaje wartość UNKNOWN (nieznana). Wartość UNKNOWN jest trzecią, obok TRUE i FALSE, wartością logiczną; będzie o niej mowa w dalszym ciągu.

Trzeba jednak pamiętać również o tym, iż wartość NULL, mimo że korzy­sta się z niej w krotkach, nie jest stałą. Nie można więc jej traktować przy wyli­czaniu wartości wyrażeń tak samo, jak traktuje się argumenty innego rodzaju.

PRZYKŁAD 5.45

Załóżmy, że wartością x jest NULL. Zatem wartością x + 3 jest także NULL. Jednakże NULL + 3 nie jest poprawnym wyrażeniem w SQL. Z podobnego powodu wartością x = 3 jest UNKNOWN, ponieważ nie można stwierdzić czy wartościąx, która jest zapisana jako NULL, jest 3, czy też nie, a z kolei wyra­żenie NULL = 3 nie jest poprawnym wyrażeniem w SQL.

0

Czasami można sprawdzić, czy wartościąx jest NULL, stosując wyrażenie x IS NULL. Przyjmuje ono wartość TRUE, gdy wartościąx jest NULL, a war­

354 5. JĘZYK BAZ DANYCH SQL

tość FALSE, gdy wartościąx jest FALSE. Przeciwne wartości przyjmuje wyra­żenie x IS NOT NULL, jest ono prawdziwe, gdy wartość x jest różna od NULL.

5.9.2. Wartość logiczna LJNKNOWN

W punkcie 5.1.2 omawiano wyrażenia zawierające operatory porówna­nia, ich wartością były stałe logiczne FALSE lub TRUE. Takie wyrażenia moż­na było łączyć spójnikami logicznymi AND, oR oraz NoT. Przed chwilą po­wstała inna sytuacja, gdy z powodu wystąpienia wartości NULL nie można byto stwierdzić, czy wyrażenie jest prawdziwe, czy falszywe i w związku z tym trzeba się posługiwać inną wartością logiczną: UNKNOWN. Należy zatem określić reguly otrzymywania wartości wyrażeń ze spójnikami logicznymi w przypadku kombinowania trzech różnych stałych logicznych.

Regina jest łatwa do zapamiętania, jeśli przypiszemy stałym logicznym wartości liczbowe: potraktujemy TRUE jako 1 (czyli zupełna prawda), FALSE jako 0 (czyli zupelnie nieprawda), a UNKNOWN jako 1/2 (czyli coś pomiędzy prawdą i fałszem). A zatem:

1. Koniunkcja AND dwóch wyrażeń logicznych przyjmuje wartość sta­nowiącą minimum wartości polączonych wyrażeń. To znaczy x AND y ma wartość FALSE, jeśli x lub y ma wartość EALSE; ma natomiast wartość UNKNOWN, jeśli żaden z argumentów nie ma wartości FALSE i co najmniej jeden z nich przyjmuje wartość UNKNOwN, oraz ma war­tość TRUE jedynie wówczas, gdy oba argumenty x i y przyjmują war­tośĆ TRUE.

2. Wartość alternatywy x oR y jest określona jako minimum wartości x i y. To znaczy x OR y ma wartość TRUE, jeśli x lub y ma wartość TRUE; wartość UNKNOWN występuje, jeśli żaden z argumentów nie ma warto­ści TRUE i co najmniej jeden ma wartość UNKNOWN, z kolei x OR y ma wartość FALSE jedynie wówczas, gdy oba argumenty mają wartość FALSE.

3. Negację wyrażenia logicznego obliczamy, odejmując od 1 wartość wyrażenia negowanego. To znaczy NoT x przyjmuje wartość TRUE, je­śli x ma wartość FALSE, wartość FALSE, gdy x ma wartość TRUE i wartość UNKNOWN, gdy x jest równe UNKNOWN.

Na rysunku 5.19 przedstawiono tabelę opisującą wyniki trzech dzialań logicznych w dziewięciu kombinacjach trzech wartości logicznych, które można przyporządkować argumentom. Wartość ostatniego operatora NoT zależy tylko od argumentu x.

Warunki SQL są zapisywane w klauzuli wHERE instrukcji select-from­-where lub DELETE i dla każdej krotki z przeszukiwanej relacji jest określana

5.9. WARTOŚCI NULL ORAZ ZLĄCZENIA ZEWNĘTRZNE 3 S S

jedna z trzech wartości FALSE, TRUE lub UNKNOWN. Do wyniku dołącza się tylko te krotki, dla których jest określona wartość TRUE, natomiast pozostałe krotki, które powodują wyliczenie wartości FALSE lub UNKNOwN, są odrzuca­ne. Powoduje to czasem nieoczekiwane sytuacje, o których pisano w ramce zatytułowanej Pułapki związane z NULL.

x y x AND y x OR y NOT x

TRUE TRUE TRUE TRUE FALSE

TRUE UNKNOWN UNKNOWN TRUE FALSE

TRUE FALSE FALSE TRUE FALSE

UNKNOWN TRUE UNKNOWN TRUE UNKNOWN

UNKNOWN UNKNOWN UNKNOWN UNKNOWN UNKNOWN

UNKNOWN FALSE FALSE UNKNOWN UNKNOWN

FALSE TRUE FALSE TRUE TRLJE

FALSE UNKNOWN FALSE UNKNOWN TRUE

FALSE FALSE FALSE FALSE TRUE

RYSUNEK 5.19

Tabela wartościowania działań dla logiki trójwartościowej

PRZYKŁAD 5.46

Załóżmy, że zapytanie będzie dotyczyć relacji:

Film (tytuł, rok, długość, czyKolor, nazwaStudia, producentC#)

i ma ono następującą postać:

SELECT EROM Film

WHERE długość <= 120 OR długość > 120;

Wygląda na to, że do wyniku powinny zostać dołączone wszystkie krotki relacji Film, ponieważ każdy flm trwa albo co najmniej 120 minut, albo mniej niż 120 minut.

Jednakże zastanówmy się, co się stanie, jeśli w pewnych krotkach war­tość NULL występuje jako składowa długości. Wówczas oba porównania długość <= 120 i długość > 120 przyjmą wartość UNKNOWN. Z tabeli na rys. 5.19 odczytujemy, że wynik alternatywy dwóch UNKNOWN daje wartość UNKNOWN. Czyli dla każdej krotki, której składową długości jest NULL, wy­rażenie z wHERE przyjmuje wartość UNKNOWN. Czyli ta krotka nie zostanie dołączona do wyniku zapytania. W tym przypadku zapytanie oznacza zatem: „wyszukaj wszystkie krotki relacji Film, których składowa długość jest różna od NULL".

3 S G 5. JĘZYK BAZ DANYCH SQL

5.9.3. Wyrażanie złączeń w języku SQL2

Zanim wprowadzimy operatory złączenia zewnętrznego, rozważymy prostszy przypadek złączenia konwencjonalnego. W języku SQL2 istnieje kilka różnych operatorów złączenia; w poprzednich standardach nie występowały one w sposób jawny, jednakże można było uzyskać wynik złączenia przez za­stosowanie zapytania select-from-where. W języku SQL2 operatory zlączeń są alternatywą instrukcji select-from-where i można z nich korzystać wymiennie. Ponadto, ponieważ w wyniku złączenia powstaje relacja, więc złączenie może być argumentem w klauzuli ;SROM w wyrażeniu select-from-where.

Najprostsza postać złączenia nazywa się złc~czeniem krzyżowym (lub skrośnym) i jest to po prostu synonim iloczynu kartezjańskiego, który był omawiany w p. 4.1.4. Jeśli chcemy na przykład uzyskać iloczyn kartezjański dwóch relacji:

Film (tytuł, rok, długość, czyKolor, nazwaStudia, producentC#)

GwiazdyW(tytułFilmu, rokFilmu, nazwiskoGwiazdy)

to możemy w tym celu napisać:

Film CROSS JOIN GwiazdyW;

W wyniku powstanie relacja z dziewięcioma atrybutami z obu relacji Film i Gwiazdyw. Będą do niej należeć krotki złożone z par, w których pierwszy element pary jest krotkąz relacji Film, a drugi - z relacji GwiazdyW.

Atrybuty w relacji wynikowej będą identyfikowane wyrażeniem R.A, gdzie R oznacza nazwę którejś relacji wejściowej, natomiastA nazwę pewnego atrybutu relacji R. Jeśli nazwa A występuje tylko w jednej z relacji wejściowych, to jak zwykle można w tym wyrażeniu pominąć R i kropkę. Ponieważ w omawianym przykładzie w relacjach Film i Gwiazdyw nie występują jednakowo nazwane atrybuty, więc w relacji wynikowej wystarczają same ich nazwy.

Jednakże rzadko korzysta się z występującego osobno tego operatora złączenia. Częściej występuje on w polączeniu ze spójnikiem ON, co oznacza złączenie teta. Operator JoW umieszcza się między nazwami łączonych rela­cji, a potem umieszcza się skowo oN oraz warunek złączenia. Do iloczynu kartezjańskiego R x S należy zatem zastosować selekcję z warunkiem wyboru określonym przez warunek oN.

PRZYKŁAD 5.47

Załóżmy, że złączenie odnosi się do relacji:

Film(tytuł, rok, długość, czyKolor, nazwaStudia, producentC#)

GwiazdyW(tytułFilmu, rokFilmu, nazwiskoGwiazdy)

p.9. WARTOŚCI NULL ORAZ ZŁĄCZENIA ZEWNĘTRZNE 3 S %

z warunkiem wyboru dotyczącym pary krotek, które opisują ten sam film. Tytuky i lata produkcji w obu relacjach muszą więc być takie same. To złą czepie można zapisać w następujący sposób:

Film JOIN GwiazdyW ON

tytuł = tytułFilmu AND rok = rokFilmu;

W wyniku powyższego zlączenia powstaje relacja o dziewięciu atrybutach pochodzących z lączonych relacji. Jednakże teraz krotka jest dolączana do wyniku tylko wówczas, gdy krotki wejściowe mają takie same wartości skła­dowych tytulu filmu i roku jego produkcji w obu relacjach wejściowych. W wyniku dwie kolumny są nadmiarowe, ponieważ w każdej krotce wyniku atrybuty tytuł i tytułFilmu sątakie same; rok i rokFilmu też majątakie same wartości.

0

Jak już wspomnieliśmy, wyrażenie zlączenia może wystąpić w klauzuli EROM W wyrażeniu typu select-from-where. W takim przypadku relacja wyni­kowa złączenia jest traktowana tak samo jak tabela bazowa lub perspektywa w klauzuli EROM. Ilustracją tego sposobu korzystania ze zlączenia jest przy­klad 5.48.

PRZYKŁAD 5.48

W wyniku złączenia z przykładu 5.47 powstają dwie nadmiarowe kolumny. Usuniemy ten defekt, wstawiając wyrażenie z tamtego przykładu do klauzuli EROM i usuniemy zbędne atrybuty, używając klauzuli sELECT. Instrukcja:

SELECT tytuł, rok, długość, czyKolor, nazwaStudia, producentC#~ nazwiskoGwiazdy

EROM Film JOIN GwiazdyW ON

tytuł = tytułFilmu AND rok = rokFilmu;

powoduje powstanie relacji z siedmioma atrybutami, do której należąwszyst­kie krotki relacji Film poszerzone o nazwiska wszystkich gwiazd, które biorą udzial w poszczególnych filmach.

0

5.9.4. Złączenie naturalne

Pamiętamy z p. 4.1.5, że zlączenie naturalne rożni się od złączenia teta:

1. Warunek złączenia polega na równości wartości atrybutów, które w krotkach lączonych w parę mają takie same nazwy. Innych warun­ków nie ma.

2. Tylko jeden z identycznych atrybutów jest dołączany do wyniku.

3 S S 5. JĘZYK BAZ DANYCH SQL

Złączenie naturalne w języku SQL2 ma dokładnie takie same właściwości. Słowa kluczowe NATURAL JoIN występują między nazwami łączonych rela­cji i określają operator złączenia ~a.

PRZYKŁAD 5.49

Nasze zadanie polega na policzeniu złączenia naturalnego następujących relacj i:

GwiazdaFilmowa(nazwisko, adres, płeć, dataUrodzenia) FilmDyr(nazwisko, adres, cert#, cenaSieci)

W wyniku złączenia powstanie relacja, do schematu której należą atrybuty nazwisko i adres oraz wszystkie te atrybuty, które należą tylko do jednej z relacji wejściowych. Krotka wynikowa opisuje osobę, która jest zarówno gwiazdą, jak i dyrektorem produkcji, a opis zawiera nazwisko, adres, płeć, datę urodzenia, numer certyfikatu i cenę sieci. Poniżej przedstawiono wyraże­nie opisujące tę nową relację:

GwiazdaFilmowa NATURAL JOIN FilmDyr;

5.9.5. Zsączenia zewnętrzne

O

W celu uniknięcia pewnych niedogodności związanych ze stosowaniem złączeń w języku SQL2 wprowadzono wariant złączenia nazywany z~c~cze­niem zewnętrznym. Przypuśćmy, że zadanie polega na obliczeniu złączenia R r~a S. Jeśli pewna krotka t relacji R nie pasuje do żadnej krotki relacji S, to w złączeniu R ~a S nie będzie po niej żadnego śladu. Może to się okazać nie­wygodne w wielu sytuacjach. Jeśli na przykład wynik złączenia definiuje perspektywę, a zapytanie dotyczy tych atrybutów perspektywy, które należą tylko do schematu relacji R, to intuicyjnie można by się spodziewać, że krotka t wystąpi w wyniku zapytania. Jednakże ta krotka nie jest wcale widoczna w perspektywie R ~a S, a więc takie samo zapytanie przetworzone dla relacji R da inny wynik, niż gdy przetwarza się krotki złączenia R ~a S.

Złączenie zewnętrzne różni się od zwykłego złączenia (tj. wewnętrzne­go) tym, że do wyniku są dołączane również te krotki, które nie „pasują" do żadnej krotki z drugiej relacji. Takie krotki, których nie można dopasować, występowały już w przykładzie 4.6 i nazywaliśmy je krotkami wiszc~cymi. Ponieważ jednak w relacji wynikowej muszą występować wartości atrybutów z obu relacji, zatem w dołączanej krotce trzeba brakujące elementy uzupełnić i w konsekwencji składowe brakujących atrybutów otrzymują w takich przy­padkach wartość NULL.

5.9. WARTOŚCI NULL ORAZ ZŁĄCZENIA ZEWNĘTRZNE

PRZYKŁAD 5.50

Trzeba utworzyć zlączenie dwóch relacji:

359

GwiazdaFilmowa(nazwisko, adres, płeć, dataUrodzenia) FilmDyr(nazwisko, adres, cert#, cenaSieci)

ale należy tym razem dołączyć do wyniku również tych aktorów, którzy nie są dyrektorami produkcji, oraz tych dyrektorów, którzy nie są gwiazdami filmo­wymi. W SQL2 korzysta się w tym celu z operatora pełnego naturalnego zlą czenia zewnętrznego (natural full outerjoin), które ma następującą postać:

GwiazdaFilmowa NATURAL FULL OUTER JOIN FilmDyr;

Do relacji wynikowej dołącza się te same sześć atrybutów, które występowały w schemacie z przykładu 5.49. W wynikowej relacji występują krotki trzech rodzajów. Krotki dotyczące tych osób, które są zarówno dyrektorami, jak i aktorami mają wartości wszystkich sześciu atrybutów różne od NULL. Są to te same krotki, które występują w wyniku złączenia w przykładzie 5.49.

Drugi rodzaj obejmuje te krotki, które opisują gwiazdy, które nie są dy­rektorami. Zawierają one wartości atrybutów: nazwisko, adres, płeć i dataUrodzenia, które pochodzą z relacji GwiazdaFilmowa, natomiast wartością atrybutów z relacji FilmDyr, tj. cert# i cenaSieci jest NULL.

Trzeci rodzaj stanowią krotki opisujące dyrektorów, którzy nie są akto­rami. Atrybuty pochodzące z relacji FilmDyr mają w tych krotkach takie same wartości jak w oryginalnej relacji, natomiast wartości atrybutów płeć i dataUrodzenia, które należą do schematu relacji GwiazdaFilmowa, są równe NULL. Na rysunku 5.20 przedstawiono wszystkie trzy rodzaje krotek.

nazwisko ~ adres ~ płeć ~ dataUrodzenia ~ cert# ~ cenaSieci

Mary Tyler Maple St. `F' 9/9/99 12345 $ 100... Moore

Tom Hanks Cherry Ln. `M' 8/8/88 NULL

George Oak Rd. NULL NULL 23456 $200... Lucas

RYSUNEK 5.20

Trzy krotki złączenia zewnętrznego relacji GwiazdaFilmowa i FilmDyr

W języku SQL2 istnieje wiele wariantów złączeń zewnętrznych. Obok pelnego zlączenia zewnętrznego występuje na przykkad zewnętrzne zlączenie lewostronne, które polega na tym, że do wyniku dolącza się tylko krotki „wi­szące" z pierwszej relacji, uzupełnione wartościami NULL w skladowych dru­giej relacji. Na przykład złączenie

GwiazdaFilmowa NATURAL LEFT OUTER JOIN FilmDyr;

mogłoby zawierać pierwsze dwie krotki z rys. 5.20, ale trzeciej już nie.

3 E)O 5. JĘZYK BAZ DANYCH SQL

W podobny sposób tworzy się złączenie zewnętrzne prawostronne, do któ­rego dołącza się krotki „wiszące" drugiej (prawej) relacji. A zatem złączenie:

GwiazdaFilmowa NATURAL RIGHT OUTER JOIN FilmDyr;

mogłoby zawierać pierwszą i trzecią krotkę z rys. 5.20, ale nie drugą.

Inne warianty złączenia zewnętrznego powstają, gdy określa się warunek złączenia. Zamiast słowa kluczowego NATU1zAL zamieszcza się wówczas sło­wo kluczowe oN oraz warunek, który muszą spełniać krotki wynikowe. Jeżeli poza tym w instrukcji umieścimy FULL oUTER JOIN, to poza uzgodnionymi krotkami tworzącymi pary do wyniku zostaną dołączone krotki, do których nie można dobrać pary, a które zostają uzupełnione wartościami NULL.

PRZYKŁAD 5.51

Rozważmy ponownie przykład 5.47, w którym definiowano złączenie relacji Film i Gwiazdyw z warunkiem złączenia dopuszczającym pary, które mają równe wartości atrybutów tytuł i tytułFilmu oraz rok i rokFilmu. Sto­sując operator złączenia zewnętrznego, otrzymamy następujące wyrażenie:

Film FULL OUTER JOIN GwiazdyW ON

tytuł = tytułFilmu AND rok = rokFilmu;

Wówczas do wyniku zostaną dołączone krotki nie tylko tych filmów, które mają jedną gwiazdę umieszczoną w relacji Gwiazdyw, ale również filmy, o których gwiazdach nie ma danych, a nieznane wartości atrybutów: tytuł­Filmu, rokFilmu 1 nazwiskoGwiazdy zostaną Określone jako NULL. W analogiczny sposób zostaną potraktowane te krotki relacji Gwiazdyw, które nie mają odpowiedników w relacji Film.

0

Słowo kluczowe FULL w złączeniu zewnętrznym, opisanym w przykła­dzie 5.51, można zastąpić słowami LEFT lub RIGHT. Na przykład w wyniku złączenia:

Film LEFT OUTER JOIN GwiazdyW ON

tytuł = tytułFilmu AND rok = rokFilmu;

powstają krotki z relacji Film, które mają odpowiedniki w relacji Gwiazdyw, a także te, dla których nie można dobrać pary, a które uzupełnia się warto­ściami NULL.

Z kolei w wyniku złączenia

Film RIGHT OUTER JOIN GwiazdyW ON

tytuł = tytułFilmu AND rok = rokFilmu;

~.9. WARTOŚCI NULL ORAZ ZŁĄCZENIA ZEWNĘTRZNE 361

nie umieszcza się krotek tych filmów, których gwiazdy nie występują w rela­cji GwiazdyW, ale dołącza się również te krotki z relacji GwiazdyW, które nie mająpary w relacji Film.

5.9.6. Ćwiczenia do podrozdzia~u 5.9

Ćwiczenie 5.9.1. Bazując na „filmowej" bazie danych"

GwiazdyW( tytułFilmu, rokFilmu, nazwiskoGwiazdy) GwiazdaFilmowa(nazwisko, adres, płeć, dataUrodzenia) FilmDyr(nazwisko, adres, cert#, cenaSieci)

Studio (nazwa, adres, prezC#)

należy opisać te krotki, które będą należeć do wyników następujących wyrażeń SQL:

a) studio CROSS JOIN FilmDyr;

b) GwiazdyW FULL NATURAL OUTER JOIN GwiazdaFilmowa; c) GwiazdyW FULL OUTER JOIN gwiazda ON nazwisko

= nazwiskoGwiazdy;

*!Ćwiczenie 5.9.2. Posługując się schematem

Produkt (producent, model PC(model, szybkość, ram, Laptop(model, szybkość, Drukarka(model, kolor, t

typ) hd, cd, cena)

am, hd, ekran, cena) p, cena)

należy napisać zapytanie SQL, które będzie zawierać dane o wszystkich produktach: PC, laptopach i drukarkach, obejmujące producenta oraz wszelkie inne stosowne dane dla danego produktu (tzn. występujące w odpowiedniej relacji).

!Ćwiczenie 5.9.3. Posługując się dwiema relacjami

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

zdefiniowanymi w schemacie bazy danych w przykładzie 4.1.3, należy napisać zapy­tanie SQL, które dostarczy wszystkie dostępne dane o okrętach, a także te dane, które są w relacji Klasy. Nie trzeba dołączać tych danych, które nie mają odpowiedników w klasie okręty.

!Ćwiczenie 5.9.4. Należy powtórzyć ćwiczenie 5.9.3, ale do wyniku należy dołączyć także dane o statku, którego klasa C nie występuje w relacji Okręty, a który ma taką samą nazwę C, jak klasa.

3 C)Z 5. JĘZYK BAZ DANYCH SQL

!Ćwiczenie 5.9.5. W przykładzie 5.46 rozważaliśmy zapytanie

SELECT FROM Film

WHERE długość <= 120 OR długość > 120;

Jego wynik nie jest intuicyjny, gdy w jakiejś krotce długość przyjmuje wartość NULL. Należy podać prostsze zapytanie równoważne z pojedynczym warunkiem w klauzuli wHERE (a nie koniunkcję ani alternatywę).

!Ćwiczenie 5.9.6. Operatory złączeń, o których była mowa w bieżącym rozdziale, są nadmiarowe w tym sensie, że można je zastąpić wyrażeniem typu select-from-where. Należy omówić wyrażenia select-from-where, którymi można zastąpić wyrażenia zapisane poniżej:

*a) R CROSS JOIN S; b) R NATURAL JOIN S;

c) R JOIN S ON C; (gdzie C jest pewnym warunkiem zapisanym w SQL)

!!Ćwiczenie 5.9.7. Operatory złączenia zewnętrznego zawsze można zastąpić zapyta­niami SQL, które zawierają inne operatory z SQL. Należy określić, w jaki sposób utworzyć wyrażenia w SQL, które nie korzystają w sposób jawny z operatorów złą­czenia ani złączenia zewnętrznego

a) R NATURAL LEFT OUTER JOIN S; b) R NATURAL FULL OUTER JOIN S;

C) R FULL OUTER JOIN S ON C; (gdzie C jest pewnym warunkiem Zap1Sa­nym w SQL).

5 .10. Rekurencj a w j ęzyku SQL

W bieżącym podrozdziale skupimy uwagę na pewnym charakterystycz­nym aspekcie SQL3 - na zapytaniach rekurencyjnych - które zaczynają już się pojawiać w systemach komercyjnych. W poprzednich rozdziałach opisy­waliśmy te cechy SQL, które obowiązują w prawie wszystkich implementa­cjach komercyjnych. Standard SQL2 został formalnie zatwierdzony, ale za­pytania rekurencyjne nie są tam dołączone i ich opis opiera się na pewnych roboczych wersjach opisu standardu SQL3, a więc może odbiegać od wersji zaimplementowanych.

Koncepcja rekurencji w SQL3 jest zbliżona do regul rekurencyjnych Da­talogu, które opisano w podrozdziale 4.4. Istnieje jednak między nimi kilka różnic. Po pierwsze w standardzie SQL dopuszcza się tylko rekurencję liniową, czyli taką, która opisuje się jednym podzadaniem rekurencyjnym. Poza tym

5.10. REKURENCJA W JĘZYKU SQL 3 63

wymaganie dotyczące stratyfikacji było omawiane dla operatora negacji w p. 4.4.4, w SQL3 rozciąga się na inne operatory, mogące w przypadku reku­rencji prowadzić do niejednoznaczności wyniku, np. do agregacji.

5.10.1. Definiowanie relacji typu IDB w języku SQL3

W podrozdziale 4.4 rozróżniliśmy relacje typu EDB (ekstensjonal­ne bazy danych), które zapisuje się w postaci tabel, od relacji typu IDB (in­tensjonalne bazy danych), które definiuje się za pomocą reguł Datalogu. W języku SQL występuje instrukcja identyfikowana słowem kluczowym wITH, która umożliwia definiowanie relacji typu IDB. Ich definicji można od razu używać w tej samej instrukcji. Prosta postać instrukcji wITH jest następująca:

WITH R AS <definicja R> <zapytanie określone na R>

A więc definiuje się roboczą relację R, a następnie korzysta się z niej w zapytaniu. W bardziej ogólnej postaci po wITH może wystąpić kilka de­finicji relacji, oddzielonych przecinkami. Każda z definiowanych relacji może być rekurencyjna. Część z nich może być wzajemnie rekurencyjna, tzn. każdą z nich można zdefiniować za pomocą innej, także samej siebie. Definicja każdej relacji, która jest objęta rekurencją, musi być poprzedzona słowem kluczowym RECURSIVE. Ogólna postać instrukcji wITH jest nastę­pująca:

1. Słowo kluczowe mTH.

2. Jedna lub kilka definicji. Definicje oddziela się przecinkami, a każda z nich składa się z następujących elementów:

a) opcjonalne słowo kluczowe RECURSIVE, jeśli definiowana relacja jest rekurencyjna;

b) nazwa definiowanej relacji; c) słowo kluczowe As;

d) zapytanie, które określa relację.

3. Zapytanie, które może dotyczyć dowolnej z definiowanych rela­cji, a którego wynik jest jednocześnie wynikiem dziakania instrukcji wITH.

Trzeba zauważyć, że inaczej niż w przypadku innych definicji relacje zdefiniowane w instrukcji wITH są dostępne tylko w obrębie tej instrukcji, a nie można korzystać z nich gdzie indziej. Jeśli relacja ma być trwała, to trzeba jązdefiniować w schemacie bazy danych poza instrukcjąwITH.

364

5. JĘZYK BAL DANYCH SQL

PRZYKŁAD 5.52

Rozważmy ponownie informację lotniczą, która slużyla już jako przykład w podrozdziale 4.4. Dane na temat rejsów są zawarte w następującej rela­...

c~ ~

Rejsy (linia, z, do, odlot, przylot)

Dane aktualne zostaly przedstawione na rys. 4.19, który powtórzono na rys. 5.21.

AA 1900-2200 UA 1500-1800 UA 1830-2130 CHI

UA 930-1230 DEN

UA 1530-1730 SF 1400-1700 /

AA 900-1430

DAL

RYSUNEK 5.21

Rejsy linii lotniczych (powtórzenie rys. 4.19)

AA 1500-1930

NY

W przykladzie 4.37 szukaliśmy zbioru par miast takich, że można dostać się z pierwszego z nich do drugiego, korzystając z rejsów uwzględnionych na rys. 5.21. W bieżącym przykładzie przedstawimy definicję relacji IDB Rej sy określonej następującymi dwiema regułami:

1. Dostępne (x, y) E- Rejsy(a, x, y, d, r)

2. Dostępne (x, y) E- Dostępne (x, z) AND Dostępne (z, y)

Z powyższych reguł tworzymy definicję relacji Dostępne, zapisaną w SQL, której znaczenie jest takie same jak w definicji IDB. Zapytanie SQL definiujące tę relację ma postać instrukcji typu WzTH, która zostaje uzupełnio­na stosownym zapytaniem. W przykladzie 4.37 chodzilo o wszystkie możliwe polączenia, ale można formułować także zapytania o wybrane połączenia, na przyklad miasta docelowe dostępne z Denver.

ł Słowo z oznacza mięjsce odlotu, a odlot - czas odlotu. Odpowiednio do oznacza miej­sce przylotu, a przylot - czas przylotu.

5.10. REKURENCJA W JĘZYKU SQL 36S

1) WITH RECURSIVE Dostępne (z, do) AS 2) (SELECT z, do EROM Rejsy)

3) UNION

4) (SELECT Rl.z, R2.do

5) EROM Dostępne AS R1, Dostępne AS R2 6) WHERE Rl.do = R2.z)

7) SELECT * EROM Dostępne; RYSUNEK 5.22

Zapytanie SQL3 o pary miast połączonych

Na rysunku 5.22 przedstawiono relację Dostępne w postaci zapytania SQL". Wiersz 1) rozpoczyna definicję Dostępne, a jej treść jest zapisana w wierszach od 2) do 6).

Według definicji tworzona relacja powstaje w wyniku sumowania dwóch zapytań, z których każde odpowiada jednej z reguł opisujących relacje Do­stępne z przykładu 4.37. Wiersz 2) jest odpowiednikiem pierwszej, zasadni­czej reguly. Stanowi ona, że drugie i trzecie skladowe każdej krotki relacji Rejsy (wartości atrybutów z i do) tworząkrotki relacji Dostępne.

Rekurencja wzajemna

Można sprawdzić, czy dwie relacje lub dwa predykaty są wzajemnie reku­rencyjne, stosując metodę teorii grafów. Polega ona na tym, ze konstruuje się graf zależności, którego wierzchotki reprezentują relacje (lub predyka­ty, gdy używamy regul Datalogu). Między wierzchołkami A i B rysujemy łuk, jeśli definicja B bezpośrednio zależy od definicji A. Gdy korzysta się z reguł Datalogu, znaczy to, że A występuje w treści reguły, w której na­glówku jest B. W SQL z kolei A wystąpiłoby gdzieś w definicji B, zazwy­czaj w klauzuli EROM, ale również w argumentach sumy, przecięcia lub różnicy.

Jeśli wierzchołki R i S są polączone cyklem, to R i S są wzajemnie re­kurencyjne. Najczęstszy przypadek polega na pętli od R do R, która ozna­cza, że relacja R zależy rekurencyjnie od siebie samej.

Zauważmy, że graf zależności przypomina ten graf, który został wprowadzony w p. 4.4.4 przy definiowaniu negacji warstwowej. Jednakże tam trzeba byto różnicować zależności pozytywne i negatywne, a tutaj nie trzeba tego robić.

W standardzie SQL3 w przypadku rekurencji liniowej w klauzuli EROM zapytania defi­niującego relacje jest dopuszczalne tylko jedno wystąpienie relacji rekurencyjnej. Ten postulat może być zrealizowany w DBMS albo nie. W wierszu 5) na rys. 5.22 są desa wystąpienia rela­cji rekurencyjnęj Dostępne, więc jest to odstępstwo od standardu. Jednak?e rozważamy ten przykład, ponieważ bardzo dobrze wiąże się on z przykładem 4.37. A w systemie komercyjnym taka postać może być dopuszczalna, mimo że nie maj~j w standardzie.

3 G6 5. JĘZYK BAZ DANYCH SQL

Wiersze od 4) do 6) są odpowiednikiem drugiej, indukcyjnej reguły. Dwa podzadania są przedstawione w klauzuli FROM przez synonimy R1 i R2 relacji Dostępne. Pierwsza składowa R1 odpowiada x z reguły 2), a druga składowa R2 jest odpowiednikiem y. Zmiennej z odpowiadają druga składowa R1 oraz pierwsza składowa R2; w wierszu 6) zapisano, że ich wartości mają być równe.

W wierszu 7) jest podany w końcu opis zapytania. Jest ono kopią relacji Dostępne. Możemy je zastąpić zapytaniem bardziej skomplikowanym, na przykład:

7) SELECT do EROM Dostępne WHERE z = `DEN'

W jego wyniku zostaną umieszczone te miasta, do których można dostać się z Denver.

5 .10.2. Rekurencj a liniowa

W związku z przykładem 5.52 wspomnieliśmy, że istnieją pewne tech­niczne uwarunkowania przedstawianych rozwiązań, ponieważ standard SQL3 dopuszcza tylko rekurencję liniową. Od strony formalnej rekurencja jest li­niowa, jeśli w definicji relacji w klauzuli EROM relacja rekurencyjna wystę­puje tylko jednokrotnie. Najczęściej w klauzuli FROM występuje definiowana relacja, ale może się również zdarzyć, że będzie to inna relacja, która jest wzajemnie rekurencyjna z relacją definiowaną.

PRZYKŁAD 5.53

Można by poprawić kod z rys. 5.22, wstawiając po prostu w wierszu 5) Rej­sy zamiast jednego z wystąpień Dostępne. Wówczas wyrażenie przyjęłoby postać rekurencji lewo- lub prawostronnej, które opisywaliśmy w p. 4.4.3. Można by równie dobrze, korzystając z instrukcji WITH, zdefiniować dodat­kową relację Pary, która jest rzutem relacji Rej sy na atrybuty z i do, a na­stępnie użyć tej relacji w obu składnikach sumy.

Przekształcony kod z rys. 5.22 przedstawiono na rys. 5.23. Wybraliśmy rekurencję prawostronną: gdybyśmy wybrali rekurencję lewostronną, wów­czas w wierszu 7) trzeba by zamienić kolejność występowania relacji Pary i Dostępne.

Zauważmy, że iteracyjne obliczenia z punktem stalym, które omówiono w p. 4.4.2, można także zastosować w zapytaniach SQL, podobnie jak, stosuje się je w regułach Datalogu. Ze względu na liniowość rekurencji może się okazać, że elementy relacji Dost~pne wystąpią w innym porządku niż w przykładzie z Datalogu, ale wszystkie pary (x, y), które oznaczają, że można przelecieć z x do y, zostaną w końcu wygenerowane.

5.10. REKURENCJA W JĘZYKU SQL 3G%

1) WITH

2) Pary AS SELECT z, do EROM Rejsy,

3) RECURSIVE Dostępne( z, do) AS 4) Pary

5) UNIOM

6) (SELECT Pary. z, Dostępne.do 7) FROM Pary, Dostępne

8) WHERE Pary. do = Dostępne. z) 9) SELECT * EROM Dostępne;

RYSUNEK 5.23

Zapytanie liniowo-rekurencyjne par miast połączonych

Rozważmy pierwszy krok iteracji. Relacja Dostępne na początku jest pusta, a zatem w wyniku obliczeń powstanie tylko pierwszy składnik sumy: Pary z wiersza 4) i będą to pary miast połączone w relacji Rej sy. W drugim kroku iteracji w wyniku znajdą się pary miast odległych o jeden rejs oraz te, które można połączyć dwoma rejsami, na przykkad (sF, CHI). W następnym kroku do relacji Dostępne nie dołącza się już żadnych nowych krotek. Na­tomiast w przypadku ogólnym do relacji Dostępne w i-tym kroku iteracji dołącza się te pary miast (x, y), między którymi najkrótsza droga ma długość i rejsów.

0

5.10.3. Instrukcja WITH i perspektywy

Instrukcja WITH służy do definiowania tabel, ale można z niej korzystać także przy określaniu perspektyw. Różnica syntaktyczna sprowadza się do konieczności użycia słowa kluczowego vlEw w przypadku określania per­spektyw.

PRZYKł,AD 5.54

Relację Pary z wiersza 2) na rys. 5.23 można traktować jako perspektywę. Jej definicja wygląda wówczas w sposób następujący:

2) VIEW Pary AS SELECT z, do EROM Rejsy

W łatwy sposób można uzasadnić traktowanie relacji Pary jako perspektywy. Gdy traktuje się ją jako relację w ścisłym znaczeniu, to jest ona tworzona w trakcie przetwarzania instrukcji WITH, zupełnie niezależnie od jej użycia w wierszu 4) przy konstruowaniu relacji Dostępne. Jeśli jest to perspektywa, to tworzenie par przy konstruowaniu relacji Dostępne można zastąpić uży­ciem składowych krotek relacji Rej sy.

0

368

5.10.4. Negacja warstwowa

5. JĘZYK BAZ DANYCH SQL

Zapytania, które stanowią definicje relacji rekurencyjnych, nie mogą być dowolnymi zapytaniami SQL. Podlegają one pewnym ograniczeniom, z któ­rych najważniejsze polega na tym, że negacja relacji wzajemnie rekurencyj­nych musi być warstwowa, zgodnie z definicjami z p. 4.4.4. W punkcie 5.10.5 omówimy zasady rozszerzenia uwarstwienia na inne struktury, które wystę­pują w języku SQL, ale których nie ma w Datalogu, takie jak na przykład agregaty.

PRZYKŁAD 5.55

Rozważmy ponownie zadanie z przykładu 4.39, polegające na odszukaniu tych par miast (x, y), które można połączyć ciągiem rejsów linii lotniczych UA, ale których nie można połączyć rejsami linii AA. Aby wyrazić koncepcję podróżowania potencjalnie nieskończonym ciągiem rejsów jednych linii lot­niczych, trzeba skorzystać z rekurencji. Jednak w tym zadaniu trzeba użyć także operatora negacji, po wyliczeniu bowiem relacji UAłaczy i AAłączy trzeba policzyć ich różnicę, a więc pojawia się problem uwarstwienia.

1) WITH

2) Trójki AS SELECT linia, z, do EROM Rejsy,

3) RECURSIVE Dostępne (linia, z, do) AS 4 ) Trój ki

5) UNION

6) (SELECT Trójki.linia, Trójki.z, Dostępne.do 7) EROM Trójki, Dostępne

8) WHERE Trójki.do = Dostępne z AND Trójki.linia = Dostępne.linia 9) )

10) (SELECT z, do EROM Dostępne WHERE linia = `UA' 11) EXCEPT

12) (SELECT z, do EROM Dostępne WHERE

linia = `AA');

RYSUNEK 5.24

Zapytanie uwarstwione miast połączonych rejsami jednej lub dwóch linii

W SQL3 można postępować w takich sytuacjach podobnie jak w Datalo­gu, trzeba tylko uprzednio zastąpić postać nieliniową rekurencji postacią le­wo- lub prawostronnie liniową, tak jak to zrobiono w przykładzie 5.53. Jed­nakże, aby opisać różnice w sposobie wykonywania, zdefiniujemy rekuren­cyjnie nie tylko pojedyncząrelację Dostępne (linia, z, do), której krot­

5.10. REKURENCJA W JĘZYKU SQL 369

ki (l, z, d) oznaczają, że można dolecieć z miasta z do miasta d rejsami linii lotniczych 1. Określimy także relację Trój ki ( linia, z, do ) , która jest rzutem relacji Rej sy na trzy odpowiednie skladowe. Zapytanie zostało przed­stawione na rys. 5.24.

Definicja relacji Dostępne, zapisana w wierszach od 3) do 9), jest sumą dwóch termów. Podstawowym termem jest relacja Trój ki, określona w wierszu 4). Term indukcyjny zostal przedstawiony jako zapytanie w wier­szach od 6) do 9) i stanowi on złączenie relacji Trój ki z relacją Dostępne. W wyniku przetworzenia tych termów do relacji Dostępne zostaną dołączo­ne krotki (l, z, d), które znaczą, że z miasta z do miasta d można dolecieć jed­nym lub kilkoma, ale rejsami tylko linii lotniczych 1.

Samo zapytanie zostało zapisane w wierszach od 10) do 12). Po przetwo­rzeniu instrukcji w wierszu 10) otrzymuje się wszystkie połączenia liniami UA, a w 12) te, które są możliwe poprzez rejsy linii lotniczych AA. Wyni­kiem jest różnica tych dwóch zbiorów połączeń.

0

PRZYKŁAD 5.56

Na rysunku 5.24 negacja została zapisana za pomocą ExCEPT w wierszu 11) i jest ona uwarstwiona, ponieważ jest wykonywana dopiero po zakończeniu rekurencji występującej w wierszach od 3) do 9). Natomiast w przykla­dzie 4.40 negacja nie była uwarstwiona, jej bezpośrednie tłumaczenie na SQL3 zostało przedstawione na rys. 5.25. Tutaj EXCEPT występuje wewnątrz definicji rekurencyjnej. Tak zapisane zapytanie dotyczy tylko wartości P, mimo że trzeba pytać także o wartość Q oraz pewne przeksztalcone wartości zPiQ.

1) WITH

2) RECURSIVE P(x) AS

3) (SELECT * EROM R)

4) EXCEPT

5) (SELECT * EROM Q),

6) RECURSIVE Q(x) AS

7) (SELECT * EROM R)

8) EXCEPT

9) (SELECT * EROM P)

10) SELECT * EROM P;

RYSUNEK 5.25

Zapytanie niewarstwowe, niedozwolone w SQL3

Sposób korzystania z EXCEPT, który został przedstawiony na rys. 5.25 w wierszach od 4) do 8), nie jest dopuszczalny w SQL3, ponieważ w obu przypadkach drugi argument jest relacją wzajemnie rekurencyjną z relacją definiowaną. A więc stosuje się tu negację, która nie jest uwarstwiona, a za­

37O 5. JĘZYK BAZ DANYCiI SQL

tem nie jest dopuszczalna. Niestety nad tym zagadnieniem nie pracuje się obecnie w SQL3, i być może nie trzeba, ponieważ rekurencja z rys. 5.25 nie jest odpowiednią definicją relacji P i Q.

0

5.10.5. Wyrażenia wątpliwe w języku SQL3

W przykładzie 5.56 można było zauważyć, że użycie EXCEPT wewnątrz definicji rekurencyjnej narusza wymagania SQL3 dotyczące uwarstwienia ne­gacji. Istnieją jeszcze inne postacie zapytań, w których co prawda nie korzysta się z ExCEPT, ale które też nie są dopuszczalne w SQL3". Na przykład negacje można wyrazić również, korzystając z operatora NOT IN. W takim przypadku wiersze od 2) do 5) z rys. 5.25 można zapisać w następujący sposób:

RECURSIVE P(x) AS

SELECT x EROM R WHERE x NOT IN Q

Taki zapis nie zmienia jednak warstwowości rekurencji i jest ona tutaj w dal­szym ciągu niewarstwowa, a zatem niedozwolona w SQL3.

Jednakże, jeśli w klauzuli WHERE użyjemy po prostu operatora NOT, na przykład NOT x = y (co można jeszcze inaczej przedstawić jako x < > y), to warunek uwarstwienia negacji nie zostanie naruszony wprost. A zatem jaka zasada stanowi, które zapytania z SQL można dopuścić do definiowania rela­cji rekurencyjnych w SQL3?

W zasadzie, żeby rekurencja była dopuszczalna w SQL3, należy tak określać relację rekurencyjną R, aby jej definicja zawierała tylko takie użycie funkcji wzajemnie rekurencyjnej S (S może być po prostu relacją R), której użycie w S jest monotoniczne. Użycie S nazywa się monotonicznym wówczas, gdy dołączenie nowej krotki do S może spowodować dołączenie nowych krotek do R lub pozostawienie R bez zmian, ale nie spowoduje usunięcia ja­kiejkolwiek krotki z relacji R.

Zasada ta nabiera znaczenia, gdy rozważa się najmniejsze obliczenie stałopunktowe opisane w p. 4.4.2. Definiowanie relacji rekurencyjnych IDB rozpoczynamy od relacji pustej, a potem iteracyjnie dołączamy do niej nowe krotki, które spełniają podane warunki. Jeśli algorytm dopuszcza taką możli­wość, że krotka dodana w pewnym kroku iteracji zostanie w którymś kolej­nym kroku usunięta, to trzeba się liczyć z ryzykiem wystąpienia oscylacji i z tym, że proces obliczeniowy nie będzie zbieżny. W następnych przykła­dach pokażemy zapytania, które zawierają struktury niemonotoniczne, a za­tem takie, które są niedozwolone w SQL3.

Mimo że rekurencja nieliniowa nie jest dopuszczalna w standardzie SQL3, to w doku­mentacji SQL3 zawarto obietnicę dołączenia rekurencji nieliniowej w SQL4. Jednakże w tym miejscu staramy się pr: edstawić pewne niejednoznaczności i paradoksy związane z rekurencją, a nie postacie, których nie akceptuje standard SQL3.

5.10. REKURENCJA W JĘZYKU SQL 3 % I

PRZYKŁAD 5.57

Na rysunku 5.25 przedstawiono implementację reguł Datalogu z przykla­du 4.40, który służył do objaśnienia negacji niewarstwowej. Reguły te umożliwiały wyliczenie dwóch minimalnych punktów stałych. Jak można się spodziewać deEnicje P i Q z rys. 5.25 nie są monotoniczne. Zobaczmy na przyklad definicję P w wierszach od 2) do 5). Relacja P zależy od relacji Q, jest z nią wzajemnie rekurencyjna, ale dolączenie krotki do Q może spo­wodować, że zostanie usunięta jakaś krotka z P. Dlaczego tak się może stać? Otóż załóżmy, że R sklada się z dwóch krotek: (a) i (b), a do Q należą krotki (a) oraz (c). Wówczas P = {(b)}. Jednakże, jeśli do Q dołączymy krotkę (b), to relacja P stanie się pusta. Dodanie krotki powoduje zatem usunięcie krotki, czyli mamy do czynienia z niemonotoniczną, a więc nie­dozwoloną strukturą.

Brak monotoniczności prowadzi wprost do zachowań oscylacyjnych wy­stępujących podczas próby wyliczenia relacji P i Q przez algorytm minimal­nego punktu stalego". Zalóżmy na przyklad, że do relacji R należą dwie krot­ki: {(a), (b)}. Początkowo obie relacje P i Q są puste. Po pierwszej iteracji, zgodnie z zapisem w wierszach od 3) do 5) na rys. 5.25, relacja P osiąga wartość {(a), (b)}. W wierszach od 7) do 9) jest wyliczana wartość Q, która będzie taka sama jak wartość P, ponieważ korzysta się w obliczeniach z war­tości powstałych w poprzedniej iteracji, a więc tutaj z wartości pustej.

Po tej iteracji wszystkie trzy relacje: P, Q i R mają taką samą wartość {(a), (b)}. Obliczenia w kolejnej iteracji spowodują, że na skutek wykonania instrukcji od 3) do 5) dla wyliczenia P oraz od 7) do 9) dla wyliczenia Q, obie te relacje staną się puste. A potem z kolei ponownie obie przyjmą wartość {(a), (b)}. Ten proces będzie trwał nieprzerwanie, generując relacje puste w iteracjach parzystych, a relacje równe {(a), (b)} w iteracjach o numerach nieparzystych. A więc nigdy nie dojdzie do wyliczenia wartości P i Q na pod­stawie „definicji" przedstawionej na rys. 5.25.

PRZYKŁAD 5.58

Także agregacja może prowadzić do niemonotoniczności, chociaż na pierw­szy rzut oka nie jest to wcale oczywiste. Zalóżmy, że zdefiniowano dwie unarne (jednoargumentowe) relacje P i Q, podając następujące warunki:

P jest sumą relacji Q oraz relacji R typu EDB.

Q zawiera tylko jedną krotkę, która stanowi sumę elementów rela­cji P.

" Gdy rekurencja nie jest monotoniczna, to porządek, w jakim są wyliczane wartości w instrukcji WITH, ma wpływ na wynik końcowy, natomiast gdy rekureneja jest monotonicz­na, to wynik nie zależy od porządku przetwarzania. W prz_ykladzie bieżącym i następnych zakładamy, że relacje P i Q są obliczane „ równolegle". To znaczy, że wartości wyliczone są używane w kolejnych iteracjach w obu relacjach.

3 72 5 JĘZYK BAZ DANYCH SQL

Warunki te zapiszemy za pomocą instrukcji WITH, mimo że narusza ona w tym przypadku wymagania monotoniczności nakładane przez SQL3. Za­pytanie przedstawione na rys. 5.26 służy do wyliczenia wartości relacji P.

1) WITH

2) RECURSIVE P(x) AS

3) (SELECT * EROM R) 4) UNION

5) (SELECT * EROM Q), 6) RECURSIVE Q(x) AS

7) SELECT SUM(*) EROM P 8) SELECT * FROM P;

RYSUNEK 5.26

Niedozwolone zapytanie niewarstwowe obejmujące agregację w SQL3

Załóżmy teraz, że relacja R składa się z knotek 12) i 34), a relacje P i Q na początku obliczeń są puste, ponieważ tak musi być zawsze na początku obli­czeń punktu stałego. Na rysunku 5.27 zestawiono w tabeli wartości obliczone w pierwszych sześciu iteracjach. Przypomnijmy tu, że stosujemy zasadę, że w danej iteracji korzysta się z wartości wyliczonych w iteracji poprzedniej. A zatem po pierwszej iteracji P staje się równe relacji R, a Q jest pusta, ponie­waż do wyliczeń w wierszu 7) używa się starej wartości P, która jest pusta.

Iteracja P Q

1) { (12), (34) }

2) {(12), (34)} {(46)}

3) {(12), (34), (46)} {(46)}

4) {(12), (34), (46)} {(92)}

5) {(12), (34), (92)} {(92)}

6) {(12), (34), (92)} {(92)}

RYSUNEK 5.27

Obliczenie iteracyjne punktu stałego agregacji niemonotonicznej

W drugiej iteracji suma określona w wierszach od 3) do 5) jest taka sama jak relacja R = {(12), (34)} i ona stanowi nową wartość relacji P. Stara war­tość P była taka sama, a więc w drugiej iteracji Q = {(46)}, ponieważ 46 jest sumą wartości 12 i 34.

Z kolei w trzeciej iteracji otrzymujemy P = {(12), (34), (46)} z wylicze­nia zgodnego z zapisem w wierszach od 2) do 5). A relacja Q, wyliczana w wierszach 6) i 7) na podstawie poprzedniej wartości P = {(12), (34)}, pozo­staje bez zmian.

W czwrtej iteracji natomiast relacja P nie zmienia wartości, za to relacja Q otrzymuje wartość {(92)}, ponieważ 12 + 34 + 46 = 92. Zauważmy, że

5.10. REKURENCJA W JĘZYKU SQL 373

z relacji Q przy dołączeniu krotki (92) została usunięta poprzednia krotka (46). Można zauważyć również, że dołączenie krotki (46) do relacji P spowo­dowało, że została usunięta krotka (przez przypadek ta sama krotka) z relacji Q. Uzewnętrznia się tutaj zatem brak monotoniczności, zabroniony w reku­rencyjnych definicjach w SQL3, co potwierdza, że zapytanie przedstawione na rysunku 5.26 jest niedozwolone. W tym przypadku w każdej iteracji o nu­merze 2i relacja P składa się z krotek (12), (34) oraz (46i - 46), a relacja Q tylko z jednej krotki (46i).

0

Korzystanie z nowych wartości w trakcie obliczeń punktu stałego Można by się zastanawiać dlaczego w przykładach 5.57 i 5.58 do wylicze­nia wartości Q używa się raczej starych wartości relacji P, a nie nowych. Wynik byłby wówczas zależny od kolejności zapisania definicji w klauzuli mTH. W przykładzie 5.57 P i Q byłyby zbieżne do jednego z dwóch punktów stałych, zależnie od kolejności przetwarzania. A w przykładzie 5.58 P i Q w dalszym ciągu nie byłyby zbieżne, a ich wartości zmieniałyby się w każdej iteracji, a nie w co drugiej.

5.10.6. Ćwiczenia do podrozdziale 5.10

Ćwiczenie 5.10.1. W przykładzie 4.36 była omawiana następująca relacja:

Kolejny (film, odcinek)

przeznaczona do zapisu kolejnych odcinków filmów. Zdefiniowaliśmy także relację Następny typu IDB, zawierającą takie pary (x, y), w których y był albo kolejnym odcinkiem filmu x, albo następował po pewnym innym kolejnym odcinku x.

a) Należy zapisać definicję relacji Następny, używając rekurencji SQL3.

b) Należy utworzyć rekurencyjne zapytanie SQL3, w wyniku którego otrzy­muje się pary (x, y) takie, że y następuje po x, ale nie jest bezpośrednim ko­lejnym odcinkiem po x.

c) Należy utworzyć rekurencyjne zapytanie SQL3, w wyniku którego otrzy­muje się pary (x, y) takie, że y następuje po x, ale ani nie jest bezpośrednim kolejnym odcinkiem po x, ani nie jest bezpośrednio kolejnym po bezpośred­nio kolejnym.

!d) Należy utworzyć rekurencyjne zapytanie SQL3, w wyniku którego otrzy­muje się te filmy x, które mają co najmniej dwa kolejne odcinki. Oba ma­ją być kolejnymi odcinkami bezpośrednio po x, a nie kolejnymi kolej­nych.

!e) Należy utworzyć rekurencyjne zapytanie SQL3, w wyniku którego otrzy­muje się pary (x, y) takie, że y następuje po x, ale po y następuje co najwyżej jeden kolejny odcinek.

374 5 JĘZYK BAZ DANYCH SQL

Ćwiczenie 5.10.2. W ćwiczeniu 4.4.3 została zdefiniowana relacja:

Rel(klasa, pklasa, wiel)

która opisuje sposób powiązania klas w ODL. Krotka (c, d, m) występuje w tej relacji wówczas, gdy między klasami c a d został określony pewien związek. Gdy związek jest wielowartościowy, wówczas wartością m jest ~wiel~, a gdy związek ten jest jednowartościowy, wówczas wartością m jest ~j ed~ . W ćwiczeniu 4.4.3 wspominali­śmy również, że relację Rel można interpretować jako graf, którego wierzchołkami sąklasy, a krawędzie, etykietowane jako m, istnieją między wierzchołkami c a d, jeśli w relacji Ret występuje krotka (c, d, m).

a) Należy utworzyć rekurencyjne zapytanie SQL3, w wyniku którego otrzymuje się pary (c, d) takie, że w grafie opisanym powyżej istnieje ścieżka od c do d.

*b) Należy utworzyć rekurencyjne zapytanie SQL3, w wyniku którego otrzy­muje się pary (c, d) takie, że istnieje ścieżka między c a d, której wszystkie odcinki są etykietowane jako j ed.

*!c) Należy utworzyć rekurencyjne zapytanie SQL3, w wyniku którego otrzy­muje się pary (c, d) takie, że istnieje ścieżka między c a d, na której co naj­mniej jeden łuk ma etykietę wiei.

d) Należy utworzyć rekurencyjne zapytanie SQL3, w wyniku którego otrzy­muje się pary (c, d) takie, że istnieje ścieżka między c a d, ale nie ma takiej ścieżki między nimi, na której wszystkie łuki miałyby etykiety j ed.

!e) Należy utworzyć rekurencyjne zapytanie SQL3, w wyniku którego otrzy­muje się pary (c, d) takie, że istnieje ścieżka między c a d oraz łuki mają etykiety na przemian jed i wiel.

f] Należy utworzyć rekurencyjne zapytanie SQL3, w wyniku którego otrzy­muje się pary (c, d) takie, że istnieją ścieżki między c a d oraz od d do c, i wszystkie łuki na tych ścieżkach mają etykiety j ed.

*!Ćwiczenie 5.10.3. Zmodyfikujmy obliczenie relacji Dost~pne z rys. 5.23, tak aby występowała tam rekurencja nieliniowa. W tym celu zamieniamy wiersze od 6) do 8) na następujące:

6) (SELECT Pierwsza. z, Druga.do

7) FROM Dostępne AS Pierwsza, Dostępne AS Druga 8) WHERE Pierwsza.do = Druga. z)

gdzie występujądwie kopie relacji Dostępne: Pierwsza i Druga, których złączenie generuje nowe pary. Jak długie będą ścieżki dołączane do relacji dostępne w i-tym kroku obliczania punktu stałego?

5 .11. Podsumowanie

~ SQL: Język SQL jest powszechnie stosowanym językiem zapytań w relacyjnych systemach baz danych. Największy wpływ na systemy komercyjne ma standard SQL2 z 1997 r. Oczekuje się wkrótce ukoń­czenia prac nad nowym standardem SQL3.

5.11. PODSUMOWANIE

375

1 Zapytania (queries) Select-From-Where: Najpopularniejsze zapytanie w SQL ma postać select-from-where. Umożliwia ono utworzenie ilo­czynu kartezjańskiego kilku relacji (klauzula FROM), określenie, czy krotki spełniają warunek logiczny (klauzula wHERE) i utworzenie krotek o zadanej postaci (klauzula SELECT).

~ Podzapytania (subqueries): Zapytania typu select-from-where można stosować także jako podzapytania w klauzuli wHERE innego zapytania. Można także sprawdzać, czy wyniki podzapytań spełniają warunki sformułowane za pomocą operatorów EXISTS, IN, ALL lub ANY.

1 Zastosowanie działań teoriomnogościowych do relacji (set operations on relations): Można uzyskiwać wyniki sumy, przecięcia i różnicy teoriomnogościowej, kącząc relacje lub wyniki podzapytań odpowied­nio spójnikami: UNION, INTERSECT lub EXCEPT.

1 Model wielozbioru dla relacji (the bag model of relations): W syste­mach SQL relacje są postrzegane jako wielozbiory krotek, a nie jako zbiory krotek. Można jednak wymuszać usuwanie kopii krotek, korzy­stając ze slowa kluczowego DISTINCT. Natomiast, gdy użyjemy sło­wa kluczowego ALL, wynik będzie wielozbiorem w tych sytuacjach, w których wielozbiór nie jest standardem.

1 Agregacje (aggregations): Wartości występujące w jednej kolumnie relacji można podsumowywać (agregować), korzystając z jednego z następujących slów kluczowych: SUM, AvG (wartość średnia), MIN, MAx lub COUNT. Zanim wykona się agregację, można lączyć krotki w grupy, używając słowa kluczowego GROUP BY. Niektóre grupy można wyeliminować, stosując słowo kluczowe HAVING.

~ Instrukcje modyfikujcice (modification statements): W SQL jest do­puszczalna zmiana krotek w relacjach. Możemy wprowadzać nowe krotki do relacji, korzystając z instrukcji INSEKT, usuwać krotki z re­lacji za pomocą DELETE oraz zmieniać wartości w krotkach, stosując UPDATE.

1 Definicja danych (data definition): W SQL istnieją specjalne polecenia, które służą do deklarowania elementów schematu bazy danych. Instruk­cja CREATE TAELE duży do deklarowania schematu przechowywanej relacji (nazywanej w SQL tabelą), specyfikując atrybuty oraz ich typy. Można także używać polecenia CREATE DoMAIN, które umożliwia de­finiowanie nazw typów danych. Nazwy te potem można stosować w deklaracjach schematów relacji. W tych instrukcjach CREATE można także określać domniemane wartości atrybutów oraz dziedzin.

1 Zmiany schematów (altering schemas): Wlaściwości schematu można zmieniać, korzystając z instrukcji ALTER. Umożliwia ona dodanie lub usunięcie atrybutu ze schematu relacji lub zmianę wartości domnie­manych związanych z atrybutami lub dziedzinami. Można także ko­rzystać z instrukcji DROP, która służy do usuwania elementów sche­matu bazy takich jak relacje lub dziedziny.

376

5. JĘZYK BAZ DANYCH SQL

• Indeksy (indexes): Nie są one co prawda zdefiniowane w standardzie SQL, ale w komercyjnych systemach indeksy można deklarować, przyspieszają bowiem wykonywanie zapytań lub tych modyfikacji, które wymagają odszukania krotek z zadanymi wartościami pewnych atrybutów.

• Perspektywy (views): Perspektywa definiuje relację konstruowa­ną z tabel przechowywanych w bazie. Można na nich przetwarzać zapytania tak samo, jak gdyby były to tabele. SQL przeksztalca te zapytania do postaci zapytań działających na tabelach bazy, a więc w wyniku tych zapytań występują dane z tabel przechowywanych w bazie.

• Wartość NULL (null values): W SQL występuje specjalna wartość NULL, która jest wpisywana w miejsce składowych, o nieokreślonych wartościach. Wartości NULL nie można traktować tak jak zwykłych wartości liczbowych lub logicznych. Porównanie jakiejkolwiek innej wartości z NULL daje w wyniku wartość logiczną UNKNOWN. Z kolei wartość UNKNOWN można traktować jako trzecią wartość logiczną, umiejscowioną między prawdą a fałszem, czyli między stałymi TRUE oraz FAL S E.

• Wyrażanie złc~czeń (join expressions): W SQL występują operatory ta­kie jak NATURAL JOIN, które służą do lączenia relacji zarówno w za­pytaniach,jak i przy definiowaniu relacji w klauzuli FROM.

• Złączenia zewnętrzne (outerjoins): W SQL występuje także operator oUTER JOIN, który powoduje nie tylko złączenie dwóch relacji, ale także dołącza do wyniku „wiszące" krotki z jednej lub drugiej relacji. Nieznane wartości atrybutów w tych krotkach wypełnia się wartością NULL.

• Rekurencja (recursion) w SQL3: W standardzie SQL3 istnieje sposób definiowania roboczych relacji rekurencyjnie, a także korzystania z tych relacji w zapytaniach. W przedstawianej wersji proponowanego zapytania istnieje wymóg, aby negacje i agregacje, które występują w rekurencji, byty warstwowe. Oznacza to, że relacja rekurencyjna nie może być definiowana jako negacja lub agregat siebie samej.

5 .12. Literatura do rozdziaw 5

Standardy SQL2 oraz SQL3 są dostępne bezpośrednio w National Institute of Science and Technology (NIST, poprzednio była to instytucja o nazwie National Bureau of Standards). Można je otrzymać poprzez FTP lub HTTP. Są one umieszczone w komputerze o nazwie speckle.ncsl.nist.gov. Standard SQL2 oraz aktualną wersję standardu SQL3 można znaleźć w katalogu:

isowg3/dbl/BASEdocs

5.12. LITERATURA DO ROZDZIAŁU 5 37%

Warto wiedzieć, że definicja składni SQL2 znajduje się w pliku: isowg3/dbl/BASEdocs/sql-92.bnf

Ktalog isowg3/x3h2 zawiera wiele dokumentów zarówno roboczych, jak i historycz­nych, które objaśniąją standardy SQL2 i SQL3.

Aby dostać się do dokumentacji SQL poprzez HTTP, należy skorzystać z URL

http://speckle.ncsl.nist.gov/~ftp/

Potem trzeba wpisać którąś ze ścieżek wymienionych powyżęj.

Na temat programowania w SQL powstało już wiele książek. Do naszych ulubionych należą na przykład pozycje [2], [3] oraz [6].

Pierwsza definicja SQL została zapisana w artykule [4]. Zaimplementowano ją w syste­mie R [1], jednym z pierwszych prototypów relacyjnych baz danych. Z kolei pozycja [5] sta­nowiła źródło opisu rekurencji w SQL3.

1. Astrahan M.M. i inni: System R: relacyjne podejście do zarządzania danymi. ACM Tran­sactions on Database Systems 1:2, s. 97-137, 1976.

2. Celko J.: SQL for Smarties. Morgan-Kaufman, San Francisco, 1995.

3. Date C.J., Darwen H.: A Guide to the SQL Standard. Addison-Wesley, Reading, MA, 1993. 4. Chamberlin D.D. i inni: SEQUEL 2: a unified approach to data definition, manipulation and control. IBMJournal of Researeh and Development 20:6, s. 560-575, 1976.

5. Finkelstein S.J., Mattos N., Mumick LS., Pirahesh H.: Expressing recursive queries in SQL. ISO WG3 report X3H2-96-075, Marzec 1996.

6. Melton J., Simon A. R.: Llnderstaning the New SQG: A Complete Guide. Morgan­-Kaufmann, San Francisco, 1993.

---