20112 ullman181 (2)

5 JĘZYK RAZ DANYCH SOL

5.10.4. Negacja warstwowa

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 rekurencyjnych 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 lotniczych, trzeba skorzystać z rckurcncji. Jednak w tym zadaniu trzeba użyć także operatora negacji, po wyliczeniu bowiem relacji UAłćtczy i AAłączy trzeba policzyć ich różnicę, a więc pojawia się problem uwarstwienia.

1)    WITH

2)    Trójki AS SF.LEC7 linia, z, do FROM Rejsy,

3)    RECURSIVE Dostępne(linia, z, do) AS

4)    Trójki

5)    UNION

6)    (SELECT Trójki . linia,

Trójki.z, Dostępne.do

7)    FROM Trójki, Dostępne

8)    W HF. RE Trój ki. do = Dostępno z AND

Trójki.linia = Dostępne.linia

9)    }

10)    {SELECT z, do FROM Dostępne WHERE linia = 'UA'

11)    EXCEPT

12)    (SELECT z, do FROM 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 Datalogu, trzeba tylko uprzednio zastąpić postać nieliniową rekurencji postacią lewo- lub prawostronnie liniową, tak jak to zrobiono w przykładzie 5.53. Jednakże, aby opisać różnice w sposobie wykonywania, zdefiniujemy rckuren-cyjnic nic tylko pojedynczą relację Dostępne O ir.ia, z, do), której krotki (/, r, d) oznaczają, że można dolecieć z miasta z do miasta d rejsami linii lotniczych /. Określimy także relację Trójki (linia, z, do}, która jest rzutem relacji Rejsy na trzy odpowiednie składowe. Zapytanie zostało przedstawione 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ójki, określona w wierszu 4). Term indukcyjny został przedstawiony jako zapytanie w w ierszach 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łączone krotki (/, z, d), które znaczą, że z miasta z do miasta d można dolecieć jednym lub kilkoma, ale rejsami tylko linii lotniczych /.

Samo zapytanie zostało zapisane w wierszach od 10) do 12). Po przetworzeniu 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. Wynikiem jest różnica tych dwóch zbiorów połączeń.

□

PRZYKŁAD 5.56

Na rysunku 5.24 negacja została zapisana za pomocą EXCEPT w wierszu II) i jest ona uwarstwiona, ponieważ jest wykonywana dopiero po zakończeniu rckurcncji występującej w wierszach od 3) do 9). Natomiast w przykładzie 4.40 negacja nic była uwarstwiona, jej bezpośrednie tłumaczenie na SQL3 zostało przedstawione na rys. 5.25. Tutaj f.xcf,pt występuje wewnątrz definicji rekurencyjnej. Tak zapisane zapytanie dotyczy tylko wartości P, mimo że trzeba pytać także o wartość Q oraz pew^rne przekształcone wartości

zP'\Q.
i)	WITH
2)	RECURS1VE P(x) AS
3)	(SELECT *	FROM	R)
4)	F.XCEP?
5}	(SELECT *	FROM	0),
6)	RECURSIVE Q(x) AS
7)	(SELECT *	FROM	R>
8)	EXCEPT
9)	(SELECT *	FROM	P)
10)	SELECT * FROM P;

RYSUNEK 5.25

Zapytanie nic warstwo we, niedozwolone w SQI,3

Sposób korzystania z EXC£PT, który został przedstawiony na rys. 5.25 w w ierszach od 4) do 8), nie jest dopuszczalny w $QL3, 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-