ullman180 (2)

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 Rl odpowiada x z reguły 2), a druga składowa R2 jest odpowiednikiem y. Zmiennej z odpowiadają druga składowa Rl 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) SF.LECT do

FROM Dostępne WHERE z = 'DEN';

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

5.10.2. Rekurencja liniowa

W związku z przykładem 5.52 wspomnieliśmy, że istnieją pewne techniczne uwarunkowania przedstawianych rozwiązań, ponieważ standard SQL3 dopuszcza tylko rckurencję liniową. Od strony formalnej rekurencja jest liniowa, jeśli w definicji relacji w klauzuli FROK relacja rekurencyjna występuje tylko jednokrotnie. Najczęściej w klauzuli FROM występuje definiowana relacja, ale może się również zdarzyć, żc 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) Rejsy 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ć dodatkowy relację Pary, która jest rzutem relacji Rejsy na atrybuty z i dc, a następnie użyć tej relacji w obu składnikach sumy.

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

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

1)    WITH

2)    Pary AS SELECT 2, do FROM Rejsy,

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

4)    Pary

5)    UNION

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

7)    FROM    Pary, Dostępne

8)    WHERE    Pary.do = Dostępne.z)

9)    SELECT * FROM Dostępne;

RYSUNEK 5.23

Zapytanie liniowo-rckurcncyjnc 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 Rejsy. 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 przykład (SF, CHI). W następnym kroku do relacji Dostępne nie dołącza się już żadnych nowych krotek. Natomiast w przypadku ogólnym do relacji Dostępne w /-tym kroku iteracji dołącza się te pary miast (*, y), między którymi najkrótsza droga ma długość i rejsów.

□

5.10.3. Instrukcja WITII 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 VIEW w przypadku określania perspektyw.

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 FROM 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życiem składowych krotek relacji Rejsy.

□