DATALOG I NEGACJA
5. SEMANTYKA DOBRZE UFUNDOWANA
1. SEMANTYKI DATALOGU:
(A) SEMANTYKA TEORIOMODELOWA:
- instancja bazy – zbiór Ri(uk), gdzie Ri należy do sch(P) (sch(P) – schemat programu P – edb(P)Èidb(P) ), a uk jest ustaloną krotką o dopowiedniej arności
- związanie reguł i zdań logicznych:
z regułą p: R1(u1) ¬ R2(u2), ...,Rn(un) wiążemy zdanie logiczne:
" x1,...xm (R1(u1) ¬ R2(u2)Ù ...ÙRn(un) ), gdzie x1,...xm są zmiennymi występującymi w regule
- instancja I spełnia p, jeśli dla dowolnego wartościowania zmiennych v t, że
R2(v(u2)), ...,Rn(v(un)) należą do I, to również R1(v(u1) ) należy do I
- åP – koniunkcja zdań związanych z regułami programu P
- model P – instancja spełniająca åP
uwaga: może być wiele modeli P, w szczególności instancja pełna (zawierająca dla poszczególnych relacji wszystkie krotki z dziedziny) jest modelem
- interesuje nas model najmniejszy
P(I) – najmniejszy model P zawierający I
Def. Dla danych P oraz I: B(P,I) – instancja nad sch(P) t, że:
1. "RÎedb(P): R(u)ÎB(P,I) wtw gdy R(u)ÎI
2. "RÎidb(P): R(u) ze stałymi z adom(P)Èadom(I) należy do B(P,I)
Fakt: B(P,I) jest modelem P zawierającym I
Algorytm liczenia P(I) dla danych P oraz I:
a) rozważamy wszystkie instancje będące podzbiorami B(P,I)
b) zostawiamy tylko te, które są modelami P i zawierają I
c) liczymy ich przecięcie – najmniejszy model P
Interpretacja programu – najmniejsza relacja będąca logiczną konsekwencją programu P.
Def. Fakt A jest bezpośrednią konsekwencją programu P i zbioru faktów I Í sch(P), jeśli A należy do pewnej relacji z edb(P) lub też istnieje pewna instancja reguły postaci
A ¬ A1,...,An taka, że A1,...,An Î I.
Def. Operator bezpośredniej konsekwencji TP to funkcja, która dla każdego programu P i zbioru faktów I przyporządkowuje zbiór wszystkich faktów będących bezpośrednimi konsekwencjami P i I.
1. monotoniczność (" I,J jeśli I Í J, to T(I) Í T(J))
2. każdy punkt stały TP jest modelem dla åP
Dla każdego P i I, TP ma najmniejszy punkt stały zawierający I, równy P(I).
Algorytm obliczania P(I):
A:=I;
while A ¹ TP(A) do A := TP(A);
2. DATALOG Z NEGACJĄ
Składnia datalogu z negacją (datalogØ): taka sama jak zwykłego datalogu + możliwość wprowadzania do programów reguł zawierających w ciele negacje relacji z edb i idb.
Przykład:
Chcemy wyliczyć wszystkie pary nie połączonych ze sobą ścieżką wierzchołków w grafie. Oznacza to, że poszukujemy dopełnienia tranzytywnego domknięcia grafu danego jako relacja G reprezentująca jego krawędzie. Można by to zapisać w nastepujący sposób:
T(x,y) ¬ G(x,y)
T(x,y) ¬ G(x,z), T(z,y)
CT(x,y) ¬ ØT(x,y).
W przypadku datalogu, dla każdego programu P semantyką stałopunktową dla P i danych I jest najmniejszy punkt stały operatora TP zawierający I. Operator bezpośredniego wynikania TP dla programu P może być rozszerzony dla programów w dataloguØ w następujacy sposób: dla każdego I nad sch(P) AÎ TP(I) jesli:
(a) A Î I|edb(P), lub:
(b) istnieje instancja reguły A ¬ A1,...,An programu P, dla której:
* jeśli Ai jest pozytywnym literałem to Ai Î I
* jeśli Ai = ØBi , gdzie Bi jest pozytywnym literałem, to Bi Ï I.
2. TP może mieć wiele minimalnych punktów stałych , np.: P =
{ p ¬
Øq
, q ¬
Øp
}. Istnieją dwa punkty stałe: {p} i {q}.
3. Rozpatrzmy ciąg { TPi(Æ) }i>0 dla danego programu P. W datalogu ciąg ten jest rosnący i zbiega do najmniejszego punktu stałego TP. W przypadku dataloguØ sytuacja jest bardziej skomplikowana:
(1) ciąg nie zawsze ma granicę, nawet jesli TP ma najmniejszy punkt stały, np:
P = { p ¬ Ør; r ¬ Øp; p ¬ Øp, r }
najmniejszy punkt stały TP = {p}, ale { TPi(Æ) }i>0 waha się pomiędzy Æ i {p,r}
(2) nawet jesli wspomniany ciag ma granicę, nie zawsze jest ona najmniejszym punktem stałym TP , nawet jeśli on istnieje, np:
P = { p ¬ p; q ¬ q; p ¬ Øp, q ¬ Øp }
{ TPi(Æ) }i>0 zbiega do {p,q}, ale najmniejszy punkt stały TP = {p}
Tak więc podejście datalogowe bazujące na punktach stałych TP nie jest dobre w przypadku dataloguØ . Z podobnych powodów nie nadaje się tez semantyka teoriomodelowa . Dlatego zaszła potrzeba poszukiwania innych rozwiązań.
3. PROGRAMY SEMI-POZYTYWNE
Programy semi-pozytywne to programy, w których negacja wystepuje tylko przed relacjami z edb. Np.: różnica R i R’ może być zdefiniowana nastepująco:
Diff(x) ¬ R(x), ØR’(x).
Semantykę dla ØR’(x) otrzymujemy używając reguły CWA (closed world assumption): ØR’(x) zachodzi wtw gdy xÏR’. R’ jest relacją z edb, więc semantyka programu jest jasna. Negację z programów semi-pozytywnych można by usunąć dodając dla każdej relacji R’ z edb nową relację R’’ utrzymującą dopełnienie R’ i zastępując ØR’(x) przez R’’(x).
TW.
Niech P – semi-pozytywny program w dataloguØ . Dla każdej instancji I nad edb(P):
a) åp ma najmniejszy model J spełniający J|edb(P) = I
b) Tp ma najmniejszy punkt stały J spełniający J|edb(P) = I
c) najmniejszy model w a) i najmniejszy punkt stały w b) są sobie równe, a ponadto równe granicy ciągu { TPi(Æ) }i>0 (oznaczamy je przez Psemipos(I) ).
4. PROGRAMY STRATYFIKOWANE
Rozpatrzmy teraz naturalne rozszerzenie programów semi-pozytywnych. Gdy relacja zostaje zdefiniowana przez jakiś program, inne mogą ją traktować jakby była relacją z edb i stosować do niej negację. To rozumowanie stoi u podstaw zdefiniowania programów stratyfikowanych. Stratyfikacją programu PÎdatalogØ jest ciąg P1,...,Pn programów (zwanych warstwami) takich, że:
1) {P1,...,Pn }– podział P;
2) istnieje odwzorowanie s: relacja z idb(P) ® [1,...,n] takie, że:
* dla kazdej relacji R wszystkie reguły definiujące R są w Ps(R)
* R(u) ¬ ...,R’(v),... jest regułą P i R’Îidb(P) , to s(R’) £ s(R)
* R(u) ¬ ...,ØR’(v),... jest regułą P i R’Îidb(P) , to s(R’) < s(R)
zakładamy, że P0 = edb(P)
Nie wszystkie programy dają się podzielic na warstwy, np:
P = { p ¬ Øq , q ¬ Øp } lub
P = { p ¬ Øp}
Jeśli program jest stratyfikowalny, to podział nie musi być jednoznaczny, np:
P = {
r1 S(x) ¬ R1’(x), ØR(x)
r2 T(x) ¬ R2’(x), ØR(x)
r3 U(x) ¬ R3’(x), ØT(x)
r4 V(x) ¬ R4’(x), ØS(x), ØU(x)
{r1}, {r2}, {r3}, {r4}
{r2}, {r1}, {r3}, {r4}
{r2}, {r3}, {r1}, {r4}
{r1,r2}, {r3}, {r4}
{r2}, {r1,r3}, {r4}
Kiedy program PÎdatalogØ jest stratyfikowalny?
Def.
P – program w datalogØ . Grafem zależności Gp programu P nazywamy graf etykietowany, którego wierzchołkami są relacjami z idb(P), ponadto:
jesli R(u) ¬ ...R’(v).. jest regułą P, to <R’,R> jest krawędzią w Gp z etykietą + (krawędź pozytywna)
jesli R(u) ¬ ...ØR’(v).. jest regułą P, to <R’,R> jest krawędzią w Gp z etykietą - (krawędź negatywna)
Lemat:
P – program statyfikowalny. Jeśli istnieje ścieżka z R’ do R w Gp , to s(R’) £ s(R); jeśli istnieje ścieżka z R’ do R zawierająca krawędź negatywną, to s(R’) < s(R).
TW.
Program PÎdatalogØ jest stratyfikowalny wtw gdy jego graf zależności Gp nie zawiera cyklu z krawędzią negatywną.
TW.
P – program datalogØ i startyfikowalny. Wszystkie stratyfilacje P są sobie równoważne.
Semantyka programów stratyfikowanych:
Niech I będzie instancją edb(P). Zdefiniujmy ciąg instancji:
- I0 = I
- Ii = Ii-1ÈPi(Ii-1), 0<i £n
Ii rozszerza Ii-1 wprowadzając wartości z relacji zdefiniowanych w Pi (w kolejnych warstwach). Pza tym Pi(Ii-1) jest semantyką semi-pozytywnego programu Pi zastosowanego do wartości dostarczonych przez Ii-1 (tak jakby stanowiących dla niego edb). Semantyką programu jest instancja In . Zauważmy, że dla programów semi-pozytywnych ta semantyka pokrywa się z semantyką przedstawioną wcześniej. Mając dany stratyfikowalny program PÎdatalogØ i I – instancję edb(P) jako semantykę przyjmiemy semantykę dowolnego podziału i oznaczymy ją jako Pstrat(I).
Tw.
Dla każdego stratyfikowalnego programu PÎdatalogØ i I – instancji edb(P):
a) Pstrat(I) jest minimalnym modelem åp , którego ograniczenie do edb(P) równa się I
b) Pstrat(I) jest minimalnym punktem stałym Tp, którego ograniczenie do edb(P) równa się I
5. SEMANTYKA DOBRZE UFUNDOWANA
Do tej pory wymagaliśmy, aby dla każdego faktu odpowiedź obliczona była prawdą lub fałszem. Dobrze ufundowana semantyka bazuje na pomyśle, że dany program nie musi dawać takich odpowiedzi dla wszystkich faktów. Wartość logiczna niektórych faktów może być nieznana. Wyliczane muszą być zbiory zarówno informacji prawdziwych jak i nieprawdziwych, ponieważ nie można w tym wypadku wnioskować, że coś jest nieprawdziwe tylko dlatego, że nie znalazło się w zbiorze odpowiedzi dających wynik pozytywny. W tym wypadku należy rozważać 3-wartościowe instancje.
Rozważmy grę pomiędzy dwoma graczami. Gracze poruszają się pomiędzy pewnymi stanami, a mozliwe ruchy trzymane są w relcji moves. Krotka moves(a,b) mówi nam, że ze stanu a gracz może wykonać ruch do stanu b. Gracz przegrywa jesli ze stanu, w którym się znajduje nie może wykonać ruchu. Naszym celem jest wyliczyć unarną relację win – zbiór stanów wygrywających (takich, w których istnieje strategia wygrywająca dla gracza, który w tym stanie się znajduje). Niech przykładowe dane dla relacji moves będą nastepujące:
K(moves) = { <b,c> , <c,a> , <a,b> , <a,d> , <d,e> , <d,f> , <f,g> }
Widać, że istnieją strategie wygrywające w stanach d i f. W żadnym ze stanów a, b, c takiej strategii nie ma. gracz może się ustrzec od porażki wykonując ruch z a do b , co w rezultacie prowadzi do nieskończonej pętli. Relację win mozna wyliczyć przy pomocy niestratyfikowalnego programu Pwin:
win(x) ¬ moves(x,y), Øwin(y)
Następujący 3-wartościowy model J okaże się być dobrze ufundowaną semantyką dla danych K:
J(moves) = K(moves), oraz następujące wartości relacji win dla poszczególnych stanów:
true: win(d), win(f)
false: win(e), win(g)
unknown: win(a), win(b), win(c)
Def.
3-wartościowa instancja I nad sch(P) jest to odwzorowanie z B(P) do {0, ½, 1}}. Przez I1, I1/2, I0 oznaczymy zbiory atomów z B(P) ( B(P) – fakty postaci R(a1,...ak) gdzie R – relacja a a1,...ak to stałe występujące w P) , których wartość jest odpowiednio równa 1, ½ i 0. I jest totalna, lub 2-wartościowa, jeśli I1/2 = Æ . Naturalny porządek „<” zdefiniowany jest na 3-wartościowych instancjach nad sch(P) naastępująco:
I < J wtw, gdy dla każdego A Î B(P), I(A) £ J(A).
Jest to równoważne temu, żeby I1Í J1 oraz I0 Ê J0 .
3-wartościowe instancje mozna też reprezentować poprzez wypisanie pozytywnych i negatywnych faktów oraz ominięcie nieznanych. Np. instancja I, gdzie I(p) = 1, I(q) = 1, I(r) = ½, I(s) = 0 może być równie dobrze zapisana jako I = { p, q , Øs}.
Wartość logiczną kombinacji boole’owskich określamy następująco:
I(bÙg) = min{ I(b), I(g) }
I(bÚg) = max{ I(b), I(g) }
I(Øb) = 1 – I(b)
I(b¬g) = 1 I(g) £ I(b) i 0 wpp.
Uwaga – nie wszystkie fakty znane dla logiki 2-wartościowej zachodzą w tym samym przypadku trójwartościowej. Np wartośc logiczna dla p¬q nie zawsze równa jest wartości pÚØq
3-wartościowa instancja I nad sch(P) spełnia kombinację boole’owską a atomów z B(P)wtw gdy I(a) = 1.
3-wartościowym modelem åp jest 3-wartościowa instancja nad sch(P) spełniająca zbiór implikacji odpowiadający regułom w ground(P) (ustalone instancje reguł programu).
Datalog
Rozszerzymy semantykę programów w datalogu by obejmowała też przypadek
3-wartościowy. Pomimo, że programy datalogowe nie zawierają negacji teraz będzie można wnioskować z nich informacje pozytywne, negatywne i nieznane. Składnia 3-rozszerzonych programów w datalogu jest taka sama jak datalogu, z wyjatkiem tego, że w ciele reguł mogą wystąpić 3 wartości logiczne: 0, ½ i 1.
a) 1, jesli istnieje reguła A¬ body w ground(P) taka, że I(body) = 1
b) 0, jeśli dla każdej reguły A¬ body w ground(P) , I(body) = 0 (lub jesli nie ma reguły z A w nagłówku)
c) ½ wpp
Przykład:
Rozpatrzmy 3-rozszerzony program w datalogu:
P = { p ¬ ½ ; p ¬ q, 1/2 ; q ¬ p,r ; q ¬ p,s ; s ¬ q ; r ¬ 1 }
Kolejne iteracje 3-Tp:
3-Tp({Øp, Øq, Ør, Øs}) = {Øq, r, Øs}
3-Tp({Øq, r, Øs}) = { r, Øs}
3-Tp({r, Øs}) = { r}
3-Tp({r}) = {r}
Porządkiem używanym dalej jest „<” opisany wcześniej. Minimalną instancją ze względu na ten porządek jest instancja,w której wszystkie atomy są fałszywe (a nie nieznane). Jest ona oznaczana przez ^.
Lemat.
Niech P – 3-rozszerzony program w datalogu. Wtedy:
a) 3-Tp jest monotoniczny, a ciag {3-Tpi(^)}i>0 rosnący – zbiega do najmniejszego punktu stałego 3-Tp
b) P ma najmniejszy 3-wartościowy model równy najmniejszemu punktowi stałemu 3-Tp
Semantyką rozszerzonego programu w datalogu jest minimalny 3-wartościowy model P, oznaczany przez P(^).
Niech I będzie 3-wartościową instancją nad sch(P). Pozytywną ustaloną wersją P dla I, oznaczaną przez pg(P,I), jest 3-rozszerzony program w datalogu otrzymany z ground(P) poprzez zamianę każdej negatywnej przesłanki ØA przez I(ØA). Jej najmniejszy punkt stały, pg(P,I)(^) zawiera wszystkie fakty, które są konsekwencjami P z wartościowaniem negatywnych przesłanek danym przez I. pg(P,I)(^) oznaczamy przez conseqp(I).
Niech P będzie programem w dataloguØ. 3-wartościowa instancja I nad sch(P) jest 3-wartościowym stabilnym modelem P wtw, gdy conseqp(I) = I.
Przykład:
1) I1 = { p , q, t, Ør, Øs, Øu }
2) I2 = { p , q, s, Ør, Øt, Øu }
3) I3 = { p , q, Ør }
Def.
P – program w dataloguØ . Dobrze ufundowaną semantyką P , oznaczaną przez Pwf(Æ) lub po prostu Pwf jest 3-wartościowa instancja składająca się z pozytywnych i negatywnych faktów należących do wszystkich 3-wartościowych stabilnych modeli P. Gdy dana jest instancja wejściowa I, PIwf(Æ) oznaczamy przez Pwf (I).
Dla przedstawionego powyżej programu Pwf(Æ) = { p , q, Ør }.
Każdy program PÎDatalogØ ma przynajmniej jeden 3-wartościowy stabilny model (więc semantyka dobrze ufundowana jest zawsze określona). Ponadto przecięcie wszystkich takich modeli również jest 3-wartościowym stabilnym modelem. Dla każdego programu stratyfikowanego semantyki stratyfikowana i ufundowana są sobie równoważne, tzn dla każdej 2-wartościowej instancji I nad edb(P) Pwf(I) = Pstrat(I).
6. PODSUMOWANIE
Semantyka stratyfikowana wymaga ograniczeń syntaktycznych, ale jest dość naturalna i stosunkowo łatwa do zrozumienia. Semantyka dobrze ufundowana nie wymaga od programów ograniczeń, ale wprowadza logikę trójwartościową.
Semantyka stratyfikowana: łatwe wyliczanie semantyki, ale nie każdy program da się podzielić na warstwy i za pomocą tych programów nie da się wyrazić wszystkich zapytań. Semnatyka dobrze ufundowana zapewnia semantykę dla każdego programu PÎDatalogØ i umożliwia wyrażenie każdego zapytania. Dla programów stratyfikowalnych obie te semantyki sobie odpowiadają.
Autor: Daria Nowicka