ullman182 (2)

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.

□

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

W przykładzie 5.56 można było zauważyć, żc użycie EXCE?T wewnątrz definicji rckurencyjnej narusza wymagania SQL3 dotyczące uwarstwienia negacji. Istnieją jeszcze inne postacie zapytali, w których co prawda nie korzysta się z EXCE?T, 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 ?(x) AS

SSLECT X FROM R WIIERE x NOT IN Q

Taki zapis nic zmienia jednak warstwowości rckurcncji i jest ona tutaj w dalszym ciągu niewarstwowa, a zatem niedozwolona w SQI-3.

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 $QL można dopuścić do definiowania relacji rekurencyjnych w SQL3?

W zasadzie, żeby rekurencja była dopuszczalna w SQL3, należy tak określać relację rekurcncyjną /?, aby jej definicja zawierała tytko takie użycie funkcji wzajemnie rckurencyjnej S (S może być po prostu relacją R), której użycie w S jest monotoniczne. Użycie S nazywa się monofonicznym wówczas, gdy dołączenie nowej krotki do S może spowodować dołączenie nowych krotek do R lub pozostawienie R bez zmian, ale nic spowoduje usunięcia jakiejkolwiek 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 1DB rozpoczynamy od relacji pustej, a potem iteracyjnic dołączamy do niej nowe krotki, które spełniają podane warunki. Jeśli algorytm dopuszcza taką możliwość, żc krotka dodana w pewnym kroku iteracji zostanie w którymś kolejnym kroku usunięta, to trzeba się liczyć z ryzykiem wystąpienia oscylacji i z tym, żc proces obliczeniowy nie będzie zbieżny. W następnych przykładach pokażemy zapytania, które zawierają struktury- niemonotoniczne, a zatem takie, które są niedozwolone w $QL3. ¹

PRZYKŁAD 5.57

Na rysunku 5.25 przedstawiono implementację reguł Datalogu z przykładu 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ć definicje P i O z rys. 5.25 nie są monotoniczne. Zobaczmy na przykład definicję P w wierszach od 2) do 5). Relacja P zależy od relacji Q, jest z nią wzajemnie rckurcncyjna, ale dołączenie krotki do Q może spowodować, że zostanie usunięta jakaś krotka z P. Dlaczego tak się może stać? Otóż załóżmy, że R składa się z dwóch krotek: (a) i (b), a do Q należą krotki (a) oraz (c). Wówczas P ~ {(/>)}. 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 niedozwoloną strukturą.

Brak monotoniczności prowadzi wprost do zachowań oscylacyjnych występujących podczas próby wyliczenia relacji R i O przez algorytm minimalnego punktu stałego¹. Załóżmy na przykład, że do relacji R należą dwie krotki: {(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ść {(«), (&)}. W wierszach od 7) do 9) jest wyliczana wartość Q, która będzie taka sama jak wartość P_y ponieważ korzysta się w obliczeniach z wartoś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ść {<//), (£)}. 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), (/>)}. Ten proces będzie trwał nieprzerwanie, generując relacje puste w iteracjach parzystych, a relacje równe {(a), (Z))} w iteracjach o numerach nieparzystych. A więc nigdy nie dojdzie do wyliczenia wartości P i O na podstawie „definicji” przedstawionej na rys. 5.25.

PRZYKŁAD 5.58

Także agregacja może prowadzić do niemonotonicznośei, chociaż na pierwszy rzut oka nic jest to wcale oczywiste. Załóżmy, że zdefiniowano dwie unarnc (jednoargumentowe) relacje P i O, podając następujące warunki:

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

2.    O zawiera ty lko jedną krotkę, która stanowi sumę elementów relacji P.

1

Mimo ze rekurencja nieliniowa nic jest dopuszczalna w standardzie SQ1.3, to w dokumentacji SQL3 zawarto obietnicę dołączenia rckurencji nieliniowej w SQL4. Jednakże w tym miejscu staramy się przedstawić pewne niejednoznaczności i paradoksy związane z rckurcncją. a nie postacie, których nic akceptuje standard SQL3.

Ody 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 rekurencja jest monotoniczna, to wynik nic zależy od porządku przetwarzania. W przykładzie bieżącym i następnych zakładamy, że relacje P i Q są obliczane .. równolegle”. To znaczy, zc wartości wyliczone są używane w kolejnych iteracjach w obu relacjach.