Universität Bonn
Institut für Informatik III
A. Behrend, R. Manthey


Übungen + Lösungen
Deduktive Datenbanken II

Blatt 2



Aufgabe 1 (alternierende Fixpunktiteration*)

    Regeln R:

    t(X) b(X)
    s(X) t(X), q(X)
    t(X) c(X,Y), ¬t(Y)
    c(X,Y) r(X,Y)
    q(X,Y) c(X,Y)
    q(X,Y) c(X,Z), q(Z,Y)

    Fakten F:

    r(a,b) , r(b,c) , r(c,d)
    r(d,e) , r(c,b) , b(c) , b(w)

1. Bestimmen Sie die Regelklassen Ro,R+ und R*.

    Lösung:

    Abhängigkeitsgraph:



    prinzipiell: Jede beliebige Schichteneinteilung (keine Stratifikation) möglich, z.B.:

    [r,b,q/1], [c], [q], [t], [s]  -->  maximale Schichtung
    [r,b,q/1], [c,q], [t], [s]
    [r,b,q/1], [c], [q,t], [s]
    [r,b,q/1], [c], [t], [q,s]
    [r,b,q/1], [q], [c,t], [s]
    [r,b,q/1], [c], [q], [s,t]
    [r,b,q/1], [c,q,t], [s]
    [r,b,q/1], [c], [q,t,s]
    [r,b,q/1], [q], [c,t,s]
    [r,b,q/1], [c,q,t,s]  -->  minimale Schichtung

    Für weitere Berechnung (Geschmacksache):

    [c,q],  [t], [s],
    R0 = {c}
    R+ = {q}
    R* = Ø    		 R0 = Ø
    R+ = Ø
    R* = {t}    		 R0 = {s}
    R+ = Ø
    R* = Ø

2. Bestimmen Sie die Herbrand-Basis und das Herbrand-Universum.

    Lösung:

    UD = { a,b,c,d,e,w }  <-- Universum

    HD =
    t(a) t(b) t(c) t(d) t(e) t(w)
    s(a) ... s(w)
    c(a,a) ... c(a,w)
    .
    .
    c(w,a) ... c(w,w)

    q(a,a) ... q(a,w)
    .
    .
    q(w,a) ... q(w,w)
    		 H-Basis
    (Wahrheitswerte nicht festgelegt!)


3. Bestimmen Sie die Bedeutung der deduktiven Datenbank $ F^{*}=\langle F^{*}_{+}, F^{*}_{-} \rangle $

    Lösung:

    1. Schritt:  Schichtung [c,q]1, [t]2, [s]3

    Bestimmung F1* für [c,q]  -->
    :
    F1*=F  { c(a,b), c(b,c), c(c,b), c(c,d), c(d,e) }
    { q(a,b), q(a,c), q(a,d), q(a,e), q(b,b), q(b,c), q(b,d), q(b,e), q(c,b), q(c,c), q(c,d), q(c,e), q(d,e) }

    2. Schritt: [t]2  -->

    t(X) b(X)   ( <--  Diese Regel leitet auf jeden Fall pos. d-Fakten her!)
    t(X) c(X,Y), ¬t(Y)



    Abbruchbedingung:  

    3. Schritt: [s]  -->  s(X) t(X), q(X)  -->  Ø

    HD =

    F-* F+* F?*
    ¬t(b) ¬t(e)

    ¬c(a,a) ¬c(a,c)
    ...
    ¬c(w,w)

    ¬q(a,a) ...

    ¬b(a) ¬b(b)
    ¬b(d) ¬b(d)    		 t(a) t(w) t(c) t(d)

    c(a,b) c(b,c) c(c,d)
    c(d,e) c(c,b)


    q(a,b) ... q(c,e)

    b(c) b(w)

    		   Ø  


Aufgabe 2 (nichtstratifizierbare Regelmengen)


1. 
Lesen Sie den Artikel von Phokion Kolaitis: The Expressive Power of Stratified Logic Programs in 'Information and Computation 90(1)', Januar 1991, zur Frage, ob nichtstratifizierbare Regelmengen tatsächlich ausdrucksstärker als stratifizierbare Regelmengen sind.
(Der Artikel kann bei mir zum Kopieren ausgeliehen werden!)

2. 
Überlegen Sie sich ein Beispiel für eine mehrdeutige Semantik mit mindestens 3 Modellen für eine gegebene Regelmenge. Muß diese Regelmenge nichtstratifizierbar sein?

Lösung:

a(X) r(X), ¬b(X), ¬c(X)  
b(X) r(X), ¬a(X), ¬c(X)  
c(X) r(X), ¬a(X), ¬b(X)  		   +   r(1)
r(2)
r(3)

3 mögliche Modelle:



allgemein: 3 Modelle (oder mehr als 1) =>  muß nichtstratifizierbar sein, wenn nur minimale Modelle betrachtet werden (dieses wäre sonst eindeutig!)

hier gemeint: stabiles Modell

z.B.:

p ¬q
q ¬p

==> stabile Modelle {p} v {q}

Nicht jede Regelmenge hat ein stabiles Modell:  z.B.: p ¬p

Zusammenfassung:



3. 
Gegeben sei folgende Regel- und Faktenmenge:

Regeln R:

o(X,Y) p(Y,X)
p(X,Y) b(X,Y)
p(X,Y) p(Y,X)
p(X,Y) b(X,Z), p(Z,Y), ¬o(X,Y)

Fakten F:

b(a,b) b(b,c) b(c,d)

(a) 
Ist die Regelmenge stratifizierbar bzw. lokal stratifizierbar?

Lösung:

Regelmenge ist nicht stratifizierbar => nicht lokal stratifizierbar

Aber es gilt: stratifizierbar => lokal stratifizierbar

(b) 
Bestimmen Sie die Bedeutung dieser Regelmenge mittels der alternierenden Fixpunktiteration von Van Gelder.

Lösung:



Aufgabe 3 (strat. Regelmengen und AFPI)

    Regeln R:

    p(X) s(X,Y), ¬q(Y)
    q(X) s(X,Y), r(X)
    r(X) b(X,Y)

    Fakten F:

    b(a,b) b(b,c) b(d,a)
    s(a,a) s(b,b) s(c,c)

1. 
Geben Sie eine Stratifikation für die Regelmenge an.

    Lösung:


2. 
Ist die Regelmenge lokal stratifizierbar?

    Lösung:

    Ja, weil: stratifizierbat => lokal stratifizierbar

3. 
Bestimmen Sie die Bedeutung dieser Regelmenge mittels der alternierenden Fixpunktiteration von Van Gelder und vergleichen Sie das Ergebnis mit dem des iterierten Fixpunktoperators.

    Lösung:

    Iterierter Fixpunkt:

    F0 =  F
    F1 = F0 { r(a), r(b), r(d) }
    F2 = F1 { q(a), q(b) }
    F3 = F2 { p(c) }
    F4 = F3 (Fixpunkt!)