Kapitel 15: Deduktive Datenbanken Flashcards
Grundkonzept deduktiver Datenbanken
IDB intensionale Datenbasis (hergeleitete Relationen)
- z.B. Expertensystem wie Siri oder Wolfram Alpha
- Die intensionale Datenbasis (IDB), die aus einer Menge von hergeleiteten Relationen(Ausprägungen) besteht. Die IDB wird durch Auswertung des Datalog-Programms aus der EDB generiert.
<– Regeln als Datalog Programm
- Logikprogramm
- Die Deduktionskomponente, die aus einer Menge von (Herleitungs-)Regeln besteht. Die Regelsprache heißt Datalog – abgeleitet von dem Wort Data und dem Namen der Logikprogrammiersprache Prolog.
<– EDB extensionale Datenbasis (Basis-Relationen)
- Die extensionale Datenbasis (EDB), die manchmal auch Faktenbasis genannt wird. Die EDB besteht aus einer Menge von Relationen(Ausprägungen) und entspricht einer „ganz normalen“ relationalen Datenbasis.
Datalog Regeln
- Grundbausteine der Regeln sind atomare Formeln oder Literale: q(A1…Am) –> professoren(S, „Sokrates“,R,Z )
- Jedes qj (…) ist eine atomare Formel. Die qj werden oft als Subgoals bezeichnet.
- X1, …,Xm sind Variablen, die mindestens einmal auch auf der rechten Seite des Zeichens :- vorkommen müssen.
Eigenschaften von Datalog-Programmen
- Ein Datalog-Programm ist rekursiv, wenn der Abhängigkeitsgraph einen (oder mehrere) Zyklen hat
- Unser Beispielprogramm ist rekursiv wegen aufbauen → aufbauen
*
Sicherheit von Datalog-Regeln
- Es gibt unsichere Regeln, wie z.B. ungleich(X, Y) :- X ≠ Y. Diese definieren unendliche Relationen.
- Eine Datalog-Regel ist sicher, wenn alle Variablen im Kopf beschränkt (range restricted) sind. Dies ist für eine Variable X dann der Fall, wenn:
- die Variable im Rumpf der Regel in mindestens einem normalen Prädikat – also nicht nur in eingebauten Vergleichsprädikaten – vorkommt oder
- ein Prädikat der Form X = c mit einer Konstante c im Rumpf der Regel existiert oder
- ein Prädikat der Form X = Y im Rumpf vorkommt, und man schon nachgewiesen hat, dass Y eingeschränkt ist.
Beispiel: nahe verwandte Vorlesungen
Wir wollen diese Vorgehensweise nochmals am Beispiel demonstrieren:
(r1) nvV(N1,N2) :- gV(N1,N2).
(r2) nvV(N1,N2) :- gV(M1,M2),vs(M1,N1),vs(M2,N2).
Dieses Beispielprogramm baut auf dem Prädikat gV auf und ermittelt nahe verwandte Vorlesungen, die einen gemeinsamen Vorgänger erster oder zweiter Stufe haben. Für die erste Regel erhält man folgenden Algebra-Ausdruck:
Was bedeutet stratifiziert?
Stratifizierte Datalog-Programme
Eine Regel mit einem negierten Prädikat im Rumpf, wie z.B. r ≡ p (…) :- q1 (…), …, ¬qi (…), …, qn (…).
kann nur dann sinnvoll ausgewertet werden, wenn Qi schon vollständig materialisiert ist. Also müssen zuerst alle Regeln mit Kopf qi (…) :- … ausgewertet sein. Das geht nur, wenn qi nicht abhängig von p ist.
Also darf der Abhängigkeitsgraph keine Pfade von qi nach p enthalten. Wenn das für alle Regeln der Fall ist, nennt man das Datalog-Programm stratifiziert.
Gegeben das folgende Schema der EDB1:
Product(maker, model, type). PC(model, speed, ram, hd, price). Laptop(model, speed, ram, hd, screen, price). Printer(model, color, type, price).
Beantworten Sie in Datalog und testen Sie unter (http://datalog.db.in.tum.de/):
a) What PC models have a speed of at least 3.00 GHz?
b) Which manufacturers make laptops with a hard disk (hd) of at least 100 GB?
c) Find the model number and price of products (of any type) made by manufacturer B.
d) Find the model numbers of all color laser printers.
e) Find those manufacturers that sell Laptops, but not PC’s.
f) Find those hard-disk sizes that occur in two or more PC’s.
g) Find those pairs of PC models that have both the same cpu speed and RAM. A pair should be listed only once, e.g., list (i,j) but not (j,i).
- a)
fast_pc(X,Y,P) :- pc(X,Y,_,_,P), Y>3.0. - b)
manuf(M) :- laptop(P,_,_,D,_,_), D > 100, product(M,P,laptop). - c)
b_prod(M,P) :- product(b, M, pc), pc(M,_,_,_,P). b_prod(M,P) :- product(b, M, laptop), laptop(M,_,_,_,_,P). b_prod(M,P) :- product(b, M, printer), printer(M,_,_,P). - d)
(M,color,laser,_) - e)
laptop_manuf(M) :- product(M,_,laptop), not(product(M,_,pc)).
- f)
pop_sizes(D) :- pc(M1,_,_,D,_), pc(M2,_,_,D,_), M1=M2. - g)
sim_pc(M1,M2) :- pc(M1,S,R,_,_), pc(M2,S,R,_,_), M1<m2.>
</m2.>
Gegeben sei die nachfolgende KindEltern-Auspra ̈gung fu ̈r den Stammbaum-Ausschnitt der griechischen Go ̈tter und Helden:
ke(zeus,leto,apollon). ke(zeus,leto,artemis). ke(kronos,rheia,hades). ke(zeus,maia,hermes). ke(koios,phoebe,leto). ke(atlas,pleione,maia). ke(kronos,rheia,poseidon). ke(kronos,rheia,zeus)
a) Bestimmen Sie alle Geschwisterpaare.
b) Ermitteln Sie Paare von Cousins und Cousinen beliebigen Grades. Die Definition finden Sie auf Wikipedia.
c) Geben Sie alle Verwandtschaftspaare an. U ̈berlegen Sie sich eine geeignete Definition von Verwandtschaft und setzen Sie diese in Datalog um.
d) Bestimmen Sie alle Nachfahren von Kronos. Formulieren Sie die Anfrage auch in SQL, so dass sie unter PostgreSQL ausfu ̈hrbar ist (online testen unter: http://sqlfiddle. com mit der Datenbank PostgreSQL statt MySQL, das Schema Textfeld ko ̈nnen sie leer lassen, mu ̈ssen aber trotzdem auf ’Build Schema’ dru ̈cken). Sie ko ̈nnen die Daten als Common Table Expression definieren und dann nutzen:
- a)
parent(P,K) :- kindEltern(P,_,K).
parent(P,K) :- kindEltern(_,P,K).
sibling(A,B) :- parent(P,A),parent(P,B),A=B.
- b)
cousin(A,B) :- parent(PA,A), parent(PB,B), sibling(PA,PB).
cousin(A,B) :- parent(PA,A), parent(PB,B), cousin(PA,PB). - c)
related(A,B) :- sibling(A,B).
related(A,B) :- related(A,C),parent(C,B).
related(A,B) :- related(C,B),parent(C,A). - d)
WITH RECURSIVE kindEltern(vater,mutter,kind) as (
VALUES 2
(‘Zeus’, ‘Leto’, ‘Apollon’), (‘Zeus’, ‘Leto’, ‘Artemis’), (‘Kronos’, ‘Rheia’, ‘Hades’), (‘Zeus’, ‘Maia’, ‘Hermes’), (‘Koios’, ‘Phoebe’, ‘Leto’), (‘Atlas’, ‘Pleione’, ‘Maia’)
(‘Kronos’, ‘Rheia’, (‘Kronos’, ‘Rheia’,),
parent(eltern ,kind) as (select vater, kind from kindEltern UNION select mutter, kind from kindEltern) select * from parent where eltern = ‘Zeus’
Datalog:
nachfahr(P,N) :- parent(P,N).
nachfahr(P,N) :- nachfahr(P,X),nachfahr(X,N).
Anfrage fürr die Nachfahren von Kronos
nachfahr(kronos ,X).
- SQL
WITH RECURSIVE kindEltern(vater,mutter,kind) as (
VALUES
(’Zeus’, ’Leto’, ’Apollon’), (’Zeus’, ’Leto’, ’Artemis’), (’Kronos’, ’Rheia’, ’Hades’), (’Zeus’, ’Maia’, ’Hermes’), (’Koios’, ’Phoebe’, ’Leto’), (’Atlas’, ’Pleione’, ’Maia’), (’Kronos’, ’Rheia’, ’Poseidon’), (’Kronos’, ’Rheia’, ’Zeus’)
),
parent(eltern , kind) as(
select vater , kind from kindEltern
select mutter , kind from kindEltern ),
nachfahren(person , nachfahre) AS ( SELECT * from parent
UNION
UNION ALL
SELECT n.person, p.kind FROM nachfahren n, parent p WHERE p.eltern = n.nachfahre
)
select * from nachfahren WHERE person=’Kronos’
Ist folgendes Datalog-Programm stratifiziert?
p(X,Y) :– q1(Y,Z),¬q2(Z,X),q3(X,P).
q2(Z, X) :– q4(Z, Y ), q3(Y, X).
q4(Z, Y ) :– p(Z, X), q3(X, Y ).
Ist das Programm sicher – unter der Annahme, dass p, q1, q2, q3, q4 IDB- oder EDB- Prädikate sind?
Nicht stratifiziert, da q2(X) :- ¬q3(Y,X) ungleich q3(X,P)
Überprüfe: Graph = Zyklus?
Definieren Sie das Prädikat sg(X,Y) das für “same generation” steht. Zwei Personen ge- hören zur selben Generation, wenn Sie mindestens je ein Elternteil haben, das derselben Generation angehört.
Verwenden Sie beispielsweise die folgende Ausprägung einer ElternKind Relation. Das erste Element ist hier das Kind, das Zweite ein Elternteil.
parent(c,a).
parent(d,a).
parent(d,b).
parent(e,b).
parent(f,c).
parent(g,c).
parent(h,d).
parent(i,d).
parent(i,e).
parent(f,e).
parent(j,f).
parent(j,h).
parent(k,g).
parent(k,i).
a) Definieren Sie das Prädikat in Datalog.
b) Demonstrieren Sie die naive Ausführung des Prädikats.
c) Erläutern Sie das Vorgehen bei der seminaiven Auswertung.
- sg(X,Y) :- parent(Z,X), X = Y.
- sg(X,Y) :- parent (X,Z), X = Y.
- sg(X,Y) :- sg(U,V), parent(X,U), parent(Y,V).
Eine Ausprägung von sg enthält zum einen alle Tupel von identischen Paaren (a,a), (b,b)… da jede Person auch mit sich selbst in derselben Generation ist. Allerdings kann man die Regel dazu nicht einfach mit “sg(X,X) angeben, da die Variable X dann nicht gebunden ist. X, d.h. die jeweilige Person, kann zum einen als Elternteil oder als Kind auftreten. Da die Datenbasis unter Umständen nicht vollständig ist, d.h. zu manchen Personen ggf. keine Eltern-Informationen abgelegt sind, benötgt man die Regeln (1) und (2), um alle Personen X zu “finden”.
Folgend werden die Ausprägungen sg mit S und EDB von parent mit P abgekürzt.
Naive Auswertung:
Gegeben sei die folgende Segler-Boots-Reservierung Datenbank:
%segler(SID,SNAME,EINSTUFUNG,ALTER) %boot(BID,BNAME,FARBE) %reservierung(SID,BID,DATUM)
Beantworten Sie die folgenden Anfragen in Datalog und testen Sie unter (http://datalog. db.in.tum.de/, Examples => Segler-Boots-Reservierung):
- Geben Sie die Farben aller Boote, die von ’Lubber’ reserviert wurden aus.
- Geben Sie alle Segler aus, die eine Einstufung von mindestens 8 oder das Boot 103 reserviert haben.
- Geben Sie die Namen aller Segler aus, die mindestens zwei Boote reserviert haben.
- Geben Sie alle Segler aus, die noch nie ein rotes Boot reserviert haben.
- Geben Sie alle Segler aus, die mehr als 20 Jahre alt sind und kein rotes Boot reserviert haben.
- Geben Sie die Ids der Segler aus, deren Einstufung besser als die eines Seglers mit Namen ’Horatio’ ist.
- Geben Sie die Ids der Segler aus, deren Einstufung besser als die aller Segler mit Namen ’Horatio’ ist.
- Geben Sie den Namen und Alter des a ̈ltesten Seglers aus.
- Geben Sie die Farben aller Boote, die von ’Lubber’ reserviert wurden aus.
lubber_farbe(F) :- segler(SID,’Lubber’,_,_), reservierung(SID,BID,_), boot(BID, _, F). - Geben Sie alle Segler aus, die eine Einstufung von mindestens 8 oder das Boot 103 reserviert haben.
a2(SID,N) :- segler(SID,N,R,_), R>=8.
a2(SID,N) :- segler(SID,N,_,_), reservierung(SID,103,_). - Geben Sie die Namen aller Segler aus, die mindestens zwei Boote reserviert haben.
doppelBoot(S) :- segler(SID,S,_,_), reservierung(SID,BIDA,_), reservierung(SID,BIDB,_), BIDA=BIDB . - Geben Sie alle Segler aus, die noch nie ein rotes Boot reserviert haben.
rotReserviert(SID) :- segler(SID,_,_,_), reservierung(SID,BID,_), boot(BID,_,red).
nichtRot(SID,S) :- segler(SID,S,_,_), not(rotReserviert(SID)). - Geben Sie alle Segler aus, die mehr als 20 Jahre alt sind und kein rotes Boot reserviert haben.
rotReserviert(SID) :- segler(SID,_,_,_), reservierung(SID,BID,_), boot(BID,_,red).
nichtRotAlt(SID,S,A) :- segler(SID,S,_,A), A>20, not(rotReserviert(SID)). - Geben Sie die Ids der Segler aus, deren Einstufung besser als die eines Seglers mit Namen ’Horatio’ ist.
nichtSchlecht(SID) :- segler(SID,_,R,_), segler(_,’Horatio’,RH,_), R > RH. - Geben Sie die Ids der Segler aus, deren Einstufung besser als die aller Segler mit Namen ’Horatio’ ist.
dochSchlecht(SID) :- segler(SID,_,R,_), segler(_,’Horatio’,RH,_), R=<rh. nochbesser :- segler not>
<li>Geben Sie den Namen und Alter des a ̈ltesten Seglers aus.<br></br> junger(SID) :- segler(SID,_,_,A), segler(_,_,_,AO), A<ao. alter :- segler not>
</li>
</ao.>
</li></rh.>
