Optymalizacja Datalogu

1. Wprowadzenie.

Przypomnienie:

• IDB - intensjonalna baza danych
• EDB - ekstensjonalna baza danych

Kilka pojęć:

• predykaty wbudowane - predykaty o standardowej interpretacji (np. X < Y)
• predykaty zwykłe - predykaty bez standardowej interpretacji
• bezpieczna reguła - reguła, w której każda zmienna z nagłówka występuje także w ciele w zwykłych oraz nie zanegowanych predykatach

W regułach dopuszczamy obecność symboli funkcyjnych (czyli działamy na rozszerzonym Datalogu).

2. Podstawowe algorytmy obliczania zapytań.

Podstawowe algorytmy obliczania zapytań dzielą się na algorytmy wstępujące (ang. bottom-up) oraz algorytmy zstępujące (ang. top-down). Algorytmy wstępujące budują (niejawnie) drzewo dowodu zaczynając od liści (relacje z EDB) i idąc w górę aż do korzenia (danego zapytania). Algorytmy zstępujące zaczynają od zapytania i rozważają œcieżki, które mogą doprowadzić do sukcesu - dowodu.

2.1 Algorytmy wstępujące

Najprostszym i od razu narzucającym się algorytmem jest algorytm naiwny:

1. Dla każdej reguły dla predykatu p obliczamy relację P używając poprzednio obliczonych relacji oraz relacji z EDB.
2. Sumujemy wszystkie relacje dla p - w wyniku otrzymujemy P'.
3. Porównujemy P z P'. Jeśli P=P' dla wszystkich predykatów, to znaleźliśmy najmniejszy punkt stały - koniec. Jeśli natomiast jakieś P jest podzbiorem P' to powtarzamy proces obliczając kolejne przybliżenie relacji (przy P zastąpionym przez P').

• dla każdego predykatu p z IDB tworzymy predykat Δp reprezentujący zmianę p w jednym cyklu obliczania (czyli relacja dla Δp jest różnicą P'-P z algorytmu naiwnego).
• zamieniamy regułę:
  H <- G₁, ..., G_n
  na serię reguł różnicowych - po jednej dla każdego predykatu G_i z IDB:
  ΔH <- G₁, ..., G_i-1, ΔG_i, G_i+1, ..., G_n.
• początkowe ΔP inicjalizujemy jednym przebiegiem algorytmu naiwnego, ale wykonując go tylko dla tych reguł, w których ciele nie ma predykatów z IDB.

1. jeśli wszystkie ΔP są puste - koniec.
2. zamieniamy wszystkie relacje P z IDB przez sumę P z ΔP.
3. dla każdego predykatu p z IDB obliczamy nową relację różnicową ΔP' dla każdej z reguł różnicowych (czyli z Δp w nagłówku) używając relacji z EDB, bieżących relacji P, oraz bieżących relacji różnicowych. Następnie sumujemy relacje dla każdego z Δp.
4. dla każdej relacji z IDB obliczamy ΔP = ΔP' - P. Wracamy do (1).

2.2 Algorytmy zstępujące

Podstawowym algorytmem zstępującym jest SLD-rezolucja, która została omówiona na poprzednim referacie.

2.3 Porównanie algorytmów

Obliczanie zapytań ma za zadanie wyprodukować pewną relację bądź część relacji, która jest potrzebna by odpowiedzieć na zapytanie. W przypadkach zapytań, które potrzebują niepełnych relacji SLD-rezolucja działa przeważnie szybciej niż algorytmy naiwne oraz potrzebuje mniej pamięci. Jest też jednak mniej stabilna - może wpaść w nieskończoną pętlę, podczas gdy algorytmy naiwne kończą się sukcesem. Okazuje się, że przy zastosowaniu najlepszych technik w obu przypadkach metody zstępujące nigdy nie są lepsze od wstępujących.

3. Algorytmy ciekawsze niż podstawowe.

Największymi mankamentami SLD-rezolucji jest chyba możliwość zapętlenia się na dobrych programach oraz niepełność wyników obliczeń w takim wypadku. Drzewa reguł/celów to próba stworzenia metody zstępującej, która nie miałaby tych niepożądanych cech, a zarazem posiadała zalety SLD-rezolucji.

3.1 Drzewa reguł/celów.

Drzewa reguł/celów mają dwa rodzaje węzłów: węzły reguł i węzły celów. Drzewo reguł/celów dla danego zapytania G₀ konstruuje się następująco:

1. Korzeń jest węzłem celu dla zapytania G₀.
2. Jeśli węzeł n jest węzłem celu dla celu G, oraz G zawiera predykat p, to dla każdej reguły r dla p unifikujemy nagłówek r z G. Jeśli operacja się powiedzie, tworzymy węzeł reguły dla zmodyfikowanej wersji r, która staje się synem n.
3. Synami węzła reguły są węzły celów odpowiadające poszczególnym podcelom reguły.

3.2 Grafy reguł/celów.

Grafy reguł/celów służą reprezentacji zbioru klauzul Horna. W porównaniu do drzew reguł/celów nie mają struktury warstwowej oraz posiadają dodatkowe elementy: szablony związania:

• Szablony związania dla węzłów celu: napisy składające się z liter b i f. Jeśli i-tą literą jest b to znaczy, że i-ty argument predykatu jest związany (znamy jakieś podstawienia dla niego). Jeśli natomiast i-tą literą jest f to znaczy to, że i-ty argument jest wolny.
• Szablony związania dla węzłów reguł mówią o tym, które zmienne w regule są związane, a które wolne:
  • Zmienna występująca w związanym argumencie nagłówka jest związana przed rozważaniem podcelów.
  • Zmienna jest związana po rozważeniu podcelu G_i jeśli była związana przed rozważaniem G_i lub jeśli występuje w G_i.
  Fakt, że zmienne X_i są związane a Y_i wolne oznaczamy przez [X₁,...,X_m|Y₁,...,Y_n].

• r₀ oznacza regułę r przed rozpatrzeniem podcelów, r₁ po rozpatrzeniu pierwszego itd...

1. węzeł celu z predykatem z EDB nie ma następników;
2. węzeł celu z predykatem p z IDB posiadającym szablon związania a ma następniki odpowiadające wszystkim regułom dla p. Jeśli r jest taką regułą, to p^a ma następnik:
   
   r₀^{[X₁,...,X_n|Y₁,...,Y_m]}
   
   gdzie X₁,...,X_n to wszystkie zmienne występujące w związanych argumentach nagłówka r według szablonu a, a Y₁,...,Y_m to pozostałe zmienne.
3. Rozważmy węzeł reguły r_i^{[X₁,...,X_n|Y₁,...,Y_m]}, i >= 0. Niech q(t₁,...,t_k) będzie (i+1)-szym podcelem r.
   1. Pierwszym następnikiem jest węzeł celu q^b. b jest szablonem, który oznacza j-ty argument z q jako związany jeśli wszystkie zmienne w t_j są zwišzane (X₁,...,X_n). W przeciwnym przypadku j-ty argument jest oznaczony jako wolny.
   2. Jeśli i+1 jest mniejsze od liczby podcelów w r (czyli q(t₁,...,t_k) nie jest ostatnim podcelem w r) to następnikiem jest węzeł:
      
      r_i+1^{[X₁,...,X_n,U₁,...,U_j|V₁,...,V_l]}
      
      gdzie U₁,...,U_j są zmiennymi spośród Y₁,...,Y_m, które występują w q, a V₁,...,V_l są pozostałymi zmiennymi spośród Y₁,...,Y_m.

3.2.1. Unikalne szablony związania.

Korzystając z grafu reguł/celów łatwo wskazać szablony związania, z którymi poszczególne predykaty są używane. Mając tę informację możemy "rozdzielić" predykaty tak, aby każdy miał unikalny szablon związania:

• Dla każdego szablonu a dla predykatu p (z IDB) takiego, że p^a pojawia się w grafie, tworzymy nowy predykat p_a.
• Dla każdej z reguł dla p tworzymy zmodyfikowaną kopię reguły - r_a z p_a w nagłówku.
• Węzeł reguły dla r₀ (następnik węzła celu p^a) jest początkiem łańcucha węzłów r₁,...,r_k. Węzły te mają następników - węzły celów odpowiadające podcelom reguły r.
  1. Jeśli q^b jest takim węzłem oraz q jest predykatem wbudowanym lub z EDB, odpowiedni podcel w r_a pozostaje taki sam jak w r.
  2. Jeśli q jest predykatem z IDB to zamieniamy predykat w odpowiednim podcelu r_a na q_b.

• rozważamy podcel, w którym jakaś zmienna występuje więcej niż raz lub w którym występują stałe.

1. Tworzymy nowy predykat p'(Y₁,...,Y_m) i podstawiamy go w miejsce p(X₁,...,X_k) - Y₁,...,Y_m to wszystkie zmienne występujące pośród X₁,...,X_k (m<k).
2. Dla reguł dla p tworzymy odpowiadające reguły dla p' wykonując odpowiednie podstawienia analogicznie jak w poniższym przykładzie.

Przykład.

4. Algorytm magic-set.

Algorytm magic-set służy do przekształcenia reguł programu w nowy zbiór reguł, lecz dający tę samą odpowiedź na zapytanie. Algorytm oczekuje na wejściu zbioru reguł o unikalnych szablonach związania.

4.1 Algorytm przekształcania reguł.

• Dla każdego predykatu p z IDB tworzymy "magiczny" predykat m_p, którego argumentami są związane argumenty z p (szablony powiązań dla predykatów z IDB są różne).
• Dla każdej reguły r_j, z k podcelami tworzymy predykaty uzupełniające sup_j.i, dla i=0,1,...,k-1.
• Argumentami predykatów uzupełniających tworzonych w punktach 2 i 3 poniższego algorytmu są zmienne, które
  1. Są związane w nagłówku (według szablonu związania).
  2. Występują w pierwszych i podcelach r oraz w dalszej części reguły lub w nagłówku (dla sup_r.i).

1. Reguły dla predykatów "magicznych". Rozważamy reguły zawierające w ciele predykat p z IDB. Niech p występuje w r_j w i-tym podcelu postaci p(t₁,...,t_n), argumentami (i-1)-szej relacji uzupełniającej są zmienne U₁,...,U_l, oraz związanymi argumentami z p według szablonu powiązań są argumenty i₁,...,i_m. Tworzymy regułę:
   
   m_p(t_i1,...,t_im) <- sup_j.i-1(U₁,...,U_l).
2. Reguły dla zerowych predykatów uzupełniających. Niech nagłówek reguły rj postaci p(t₁,...,t_n) ma związane argumenty i₁,...,i_m. Niech X₁,...,X_l będą zmiennymi występującymi wśród t_i1,...,t_im. Tworzymy regułę:
   
   sup_j.0(X₁,...,X_l) <- m_p(t_i1,...,t_i1,...,t_im).
3. Reguły dla pozostałych predykatów uzupełniających. Dla każdej reguły r_j o k podcelach i dla każdego i=1,2,...,k-1 tworzymy regułę definiującą sup_j.i. Niech zmiennymi - atrybutami (i-1)-szej relacji uzupełniającej dla r_j będą U₁,...,U_l oraz niech zmiennymi - atrybutami i-tej relacji uzupełniającej będą V₁,...,V_m. Niech p(t₁,...,t_n) będzie i-tym podcelem r_j. Tworzymy regułę:
   
   sup_j.i(V₁,...,V_m) <- sup_j.i-1(U₁,...,U_l),p(t₁,...,t_n).
4. Reguły dla predykatów z IDB. Niech reguła r_j ma k>=1 podcelów, k-tym podcelem będzie p(v₁,...,v_m), U₁,...,U_l zmiennymi - atrybutami (k-1)-szej relacji uzupełniającej, a h(t₁,...,t_n) nagłówkiem r_j. Tworzymy predykat:
   
   h(t₁,...,t_n) <- sup_j.k-1(U₁,...,U_l),p(v₁,...,v_m).
   
   W przypadku, gdy k=0 predykat ma postać:
   
   h(t₁,...,t_n) <- sup_j.0(U₁,...,U_l).
5. Reguła inicjująca. Niech q(s₁,...,s_n) będzie danym zapytaniem oraz i₁,...,i_m będą związanymi argumentami zapytania. Tworzymy nowe zapytanie:
   
   <- m_q(s_i1,...,s_im).

Przykład.

4.2 Uproszczenie reguł algorytmu magic-set.

Jeśli reguły dla pewnego predykatu p z IDB nie zawierają w ciele p, to można każdy podcel zawierający p zastąpić przez podstawienie w jego miejsce ciała reguł dla p. Nowe reguły mogą być mniej ogólne od starych, lecz relacje pozostają takie same.

Przykład.

1. jest tylko jedna reguła dla p i p występuje tylko w jednym podcelu lub.
2. jest tylko jedna reguła dla p i w ciele tej reguły jest tylko jeden podcel.

1. zerowe predykaty uzupełniające (po jednej regule długości 1).
2. predykaty uzupełniające sup_i.j dla i-tej reguły, jeśli j-tym podcelem jest predykat z EDB.

4.3 Uogólniony algorytm magic-set.

Dużą zaletą metod zstępujących jest to, że potrafią liczyć dokładnie to, co trzeba aby osiągnąć cel (dowód). Na przykład cel p(X,X,3) mówi, że dwa pierwsze argumenty są równe. SLD-rezolucja potrafi to wykorzystać, natomiast algorytm magic-set nie potrafi. Uogólniony algorytm magic-set przechowuje informacje nie tylko o argumentach związanych, ale o wszystkich. To wystarczy aby wykorzystać dodatkowe właściwości argumentów. Pojawia się jednak problem: niektóre "magiczne" reguły przestają być bezpieczne przy zapytaniach zawierających zmienne. Można rozwiązać ten problem dość łatwo wstawiając zmienne do krotek. Trzeba przy tym uważać na sytuacje, w których dwie krotki z różnymi zmiennymi tak naprawdę oznaczają tę samą krotkę (np. (A, 3) i (B, 3)), lub jedna jest bardziej ogólna (np. (A, A, 3) i (B, C, 3)).

5. Bibliografia.

Jeffrey D. Ullman, "Principles of Database and Knowledge-Base Systems, Volume II", Computer Science Press 1989, rozdziały 12 i 13 (str. 734-876)