Vorlesung Datenbanksysteme vom 3.12.2007

Deduktive Datenbanken

GrundideeRekursionDatalogAuswertung von Datalog-RegelnAusdruckskraft von Datalog

Grundidee

• EDB / IDB

3

Grundidee einer deduktiven Datenbank

IDBintensionale Datenbasis(hergeleitete Relationen)

Regeln als Datalog Programm

EDBextensionale Datenbasis

(Basis-Relationen)

4

TerminologieDie extensionale Datenbasis (EDB):

besteht aus einer Menge von Relationenentspricht einer "ganz normalen" relationalen Datenbasis.

Die Deduktionskomponente: besteht aus einer Menge von (Herleitungs-)Regeln . Die Regelsprache heißt Datalog (= Data + Prolog).

Die intensionale Datenbasis (IDB):Besteht aus einer Menge von hergeleiteten Relationen. Die IDB wird durch Auswertung des Datalog-Programms aus der EDB generiert.

Rekursion

• Transitive Hülle• Beispiele• Rekursion in SQL

6

Transitive HülleDefinition: Transitive Hülle der 2-stelligen Relation R(A,B):

trans(R)= {(a,b) | ∃k ∈ N, ∃Γ1, ..., Γk ∈ R, Γ1.A= a ÆΓ1.B= Γ2.A ÆM

Γk-1.B= Γk.A Æ

Γk.B= b}Problem in der relationalen Algebra (und SQL-92):

Die Tiefe k der Rekursion ist a priori nicht bekannt.Beliebig tiefe Rekursion lässt sich in der relationalen Algebra (und in SQL-92) nicht ausdrücken.

7

Beispiel: Pfad in einem Graph5

1 2 3 4 kante(1,2).6 7 kante(2,3).

kante(3,4).kante(3,6).kante(4,5).kante(4,6).kante(6,7).

8

Beispiel: Pfad in einem Graph5

1 2 3 4 kante(1,2).6 7 kante(2,3).

kante(3,4).kante(3,6).kante(4,5).kante(4,6).kante(6,7).

Datalog Programm: Intensionale Relation "pfad":pfad(V,N) :- kante(V,N).pfad(V,N) :- kante(V,Z), pfad(Z,N).

9

Weitere Beispiele:Relationale Uni-DB:

EDB-Relation: voraussetzen (Vorgänger, Nachfolger)

IDB-Relation: aufbauend (Vorl1, Vorl2), d.h.:

Vorl2 setzt Vorl1 entweder "direkt" oder "indirekt" voraus.

Komponenten eines Produkts: EDB-Relation: enthaelt (Artikel, Teil)

IDB-Relation: komponenten (Teil1, Teil2), d.h.:

Teil1 enthält Teil2 entweder "direkt" oder "indirekt".

Problem: Diese IDB-Relationen erfordern beliebig tiefe Rekursion=> Solche Anfragen lassen sich in der relationalen Algebra (und in SQL-92) nicht ausdrücken!

10

Rekursion in SQL

select Vorgängerfrom voraussetzen, Vorlesungenwhere Nachfolger= VorlNr and

Titel= `Der Wiener Kreis´

21374Die 3 Kritiken4630

21342Glaube und Wissen5022

21332Der Wiener Kreis5259

gelesenVon

SWSTitelVorlNr

21374Grundzüge5001

21262Bioethik5216

21263Wissenschaftstheorie5052

21254Logik4052

21252Mäeutik5049

21263Erkenntnistheorie5043

21254Ethik5041

Vorlesungen

NachfolgerVorgänger50415001

52595052

50525041

50525043

52165041

50495001

50435001

voraussetzen

11

Der Wiener Kreis 5259

Wissenschaftstheorie 5052

Bioethik 5216

Erkenntnistheorie

5043

Ethik 5041

Mäeutik5049

Grundzüge

5001

12

Rekursion in SQL: Tiefe 2select v1.Vorgänger

from voraussetzen v1, voraussetzen v2, Vorlesungen v

where v1.Nachfolger= v2.Vorgänger and

v2.Nachfolger= v.VorlNr and

v.Titel=`Der Wiener Kreis´

21374Die 3 Kritiken4630

21342Glaube und Wissen5022

21332Der Wiener Kreis5259

gelesenVon

SWSTitelVorlNr

21374Grundzüge5001

21262Bioethik5216

21263Wissenschaftstheorie5052

21254Logik4052

21252Mäeutik5049

21263Erkenntnistheorie5043

21254Ethik5041

Vorlesungen

NachfolgerVorgänger50415001

52595052

50525041

50525043

52165041

50495001

50435001

voraussetzenNachfolgerVorgänger

50415001

52595052

50525041

50525043

52165041

50495001

50435001

voraussetzen

13

select v1.Vorgängerfrom voraussetzen v1

M

voraussetzen vn_minus_1voraussetzen vn,Vorlesungen v

where v1.Nachfolger= v2.Vorgänger andM

vn_minus_1.Nachfolger= vn.Vorgänger andvn.Nachfolger = v.VorlNr andv.Titel= `Der Wiener Kreis´

Rekursion in SQL: Tiefe n

14

SELECT Vorgaenger, Nachfolger FROM voraussetzenSTART WITH Nachfolger =

( SELECT VorlNrFROM VorlesungenWHERE Titel = 'Der Wiener Kreis' )

CONNECT BY PRIOR Vorgaenger = Nachfolger;

Bemerkungen:Die "voraussetzen"-Tabelle stellt keinen Baum dar sondern einen DAG (directed acyclic graph). Hierarchische Anfragen kommen mit beliebigen Graphen (die Zyklen enthalten können) nicht zurecht!

Rekursion in Oracle 10g

15

Graph-Erreichbarkeitsproblem in Oracle 10g (1)

5

1 2 3 4 6 7

CREATE TABLE Kante(von INTEGER,nach INTEGER,CONSTRAINT kantePK PRIMARY KEY(von,nach));

SELECT LEVEL as pfadlaenge, nachFROM KanteSTART WITH von = 2CONNECT BY PRIOR nach = von;

16

Graph-Erreichbarkeitsproblem in Oracle 10g (2)

5

1 2 3 4 6 7

SELECT LEVEL as pfadlaenge, nachFROM KanteSTART WITH von = 2CONNECT BY PRIOR nach = von;

Bemerkung: Diese hierarchische Anfrage scheitert in Oracle, weil der Graph nun zyklisch ist.

Datalog

• Datalog-Regeln• Abhängigkeitsgraph

18

Datalog-Regeln

Jedes qj (...) ist eine atomare Formel: q ist dabei

der Name einer Basisrelation,

der Name einer abgeleiteten Relation oder

ein eingebautes Prädikat: <,=,>,…

X1, ...,Xm sind Variablen, die mindestens einmal auch im Rumpf vorkommen müssen.

Logisch äquivalente Form der obigen Regel:p(...) ∨ ¬q1 (...) ∨... ∨ ¬qn (...)

).,...,(),...,,...,( -: ),...,( 111111 1 nnmnnmm AAqAAqXXp

Kopf (head) Rumpf (body)

19

Datalog-Regelnp, q, … : Prädikate.

EDB-Prädikate: kommen nur im Rumpf von Regeln vor.IDB-Prädikate: kommen (auch) im Kopf von Regeln vor.

Beispiel: Vorlesungen von Sokrates mit mehr als 2 SWSsokLV(T,S) :- vorlesungen(V,T,S,P ),

professoren(P, 'Sokrates',R,Z ), >(S,2).

Äquivalenter Domänenkalkül-Ausdruck:{[t,s] | ∃v,p ([v,t,s,p] ∈ Vorlesungen ∧

∃n,r,z ([p,n,r,z] ∈ Professoren ∧n = 'Sokrates' ∧ s > 2))}

20

Beispiel Datalog-ProgrammgeschwisterVorl(N 1, N 2) :- voraussetzen(V, N 1),

voraussetzen(V, N 2), N 1 < N 2.

geschwisterThemen(T 1, T 2) :- geschwisterVorl(N 1, N 2),vorlesungen(N 1, T 1, S 1, R 1),vorlesungen(N 2, T 2, S 2, R 2).

aufbauen(V,N ) :- voraussetzen(V,N )aufbauen(V,N ) :- aufbauen(V,M ), voraussetzen(M,N ).

verwandt(N,M ) :- aufbauen(N,M ).verwandt(N,M ) :- aufbauen(M,N ).verwandt(N,M ) :- aufbauen(V,N ), aufbauen(V,M ).

Basis-Relationen: voraussetzen: {[Vorgänger, Nachfolger]}vorlesungen: {VorlNr, Titel, SWS, gelesenVon]}

21

Abhängigkeitsgraph

geschwisterThemen

vorlesungenvoraussetzen

geschwisterVorlaufbauen

verwandt

Abhängigkeitsgraph: = "wird verwendet von"Ein Datalog-Programm ist rekursiv, wenn der Abhängigkeitsgraph einen (oder mehrere) Zyklen hat

Unser Beispielprogramm ist rekursiv wegen des Zyklusaufbauen → aufbauen

Auswertung von Datalog-Regeln

• nicht-rekursive Regeln• rekursive Regeln• Negation im Regel-Rumpf

23

Nicht-rekursive Regeln

Auswertung der IDB-RelationengeschwisterVorl(N 1, N 2)geschwisterThemen(T 1, T 2)

mit Hilfe der Basisrelationenvorlesungen(N 2, T 2, S 2, R 2).voraussetzen(V, N 2)

geschwisterThemen

vorlesungenvoraussetzen

geschwisterVorl

24

Auswertung nicht-rekursiver Datalog-Programme

1. Topologische Sortierung der Relationen, z.B.: voraussetzen, geschwVorl, vorlesungen, geschwThemen

2. Für jede Regel mit dem Kopf p(...), alsop(...) :- q1(...), ..., qn(...).

bilde eine Relation, in der alle im Regel-Rumpf vorkommenden Variablen als Attribute vorkommen, z.B.: GV(N1, N2, V).

3. Diese Relation wird im wesentlichen durch einen natürlichen Verbund der Relationen Q1, ..., Qn, die den Relationen der Prädikate q1, ..., qn entsprechen, gebildet.

4. Projektion auf die Variablen, die im Regel-Kopf vorkommen.5. Das Prädikat p kann durch mehrere Regeln definiert sein.

=> Die Relationen aus den vorigen Schritten werden vereinigt.

25

Auswertung von geschwisterVorl

Ausdruck der relationalen Algebra für die Relation GV:

σN1<N2 (Vs1(V, N1) A Vs2(V, N2))

Vs1(V, N1) := ρV←$1(ρN1 ←$2 (ρVs1(Voraussetzen)))

Die dadurch definierte Relation enthält Tupel [v, n1, n2] mit:

Das Tupel [v, n1] ist in der Relation Voraussetzen enthalten,

das Tupel [v, n2] ist in der Relation Voraussetzen enthalten

und n1 < n2.

Formel zur Berechnung der Relation GV:

GV(N1, N2) := ΠN1, N2 (σN1<N2(Vs1(V, N1) A Vs2(V, N2)))

26

Rekursive Regeln

Auswertung der IDB-Relationaufbauen(V,N )

mit Hilfe der Basisrelationvoraussetzen(V, N 2)

voraussetzen

aufbauen

27

(Naive) Auswertung durch Iteration

A := {}: /*Initialisierung auf die leere Menge */repeat

until A' = Aoutput A;

)),(),((),(),( , NMVsMVANVVsNVA NV AΠ∪=

/* Regel zweite* /));,(),('(:/* Regel erste * /);,(:

;:'

, NMVsMVAAANVVsA

AA

NV AΠ∪===

d.h.: A = kleinster Fixpunkt

28

(Naive) Auswertung durch Iteration

wie in Schritt 3 (keine Veränderung, also Terminierung

des Algorithmus

4

[5001,5041], [5001,5043], [5001,5049], [5041,5216], [5041,5052], [5043,5052],

[5052,5259][5001,5216], [5001,5052], [5041,5259], [5043,5259],

[5001,5259]

3

[5001,5041], [5001,5043], [5001,5049], [5041,5216], [5041,5052], [5043,5052],

[5052,5259][5001,5216], [5001,5052], [5041,5259], [5043,5259],

2

[5001,5041], [5001,5043], [5001,5049], [5041,5216], [5041,5052], [5043,5052],

[5052,5259]

1ASchritt

NachfolgerVorgänger

50415001

52595052

50525041

50525043

52165041

50495001

50435001

voraussetzen

29

Regeln mit Negation im Rumpf

indirektAufbauen(V,N) :- aufbauen(V,N), ¬voraussetzen(V,N)

Stratifizierte Datalog-Programme:Eine Regel mit einem negierten Prädikat im Rumpf, wie z.B.p (...) :- q1 (...), ..., ¬qi (...), ..., qn (...).kann nur dann sinnvoll ausgewertet werden, wenn die Relation Qi schon vollständig materialisiert ist. Also müssen zuerst alle Regeln mit Kopf qi (...) :- ...ausgewertet sein. Das geht nur, wenn qi nicht von p abhängt.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.

30

( ) ( )

( ) ( ) ( )( )( ) ( )

( ) i

malk

i

NV

QDOMDOMQ

BildungKomplement

NVVsNVANVVsNVANViA

NVvsNVaNViA

−××=

−

−=

Π=

¬−

−444 3444 21 ...:

,,,,,

).,(,,:,

, A

Regeln mit Negation im Rumpf

Ausdruckskraft von Datalog

• Datalog mit/ohne Negation und Rekursion• relationale Algebra-Operatoren in Datalog

32

Ausdruckskraft von Datalog

Die Sprache Datalog mit Negation, aber eingeschränkt auf nicht-rekursive Programme, wird auch als Datalog ¬

non-recbezeichnet.

Diese Sprache Datalog ¬non-rec hat genau die gleiche

Ausdruckskraft wie die relationale Algebra. => Damit hat sie auch die gleiche Ausdruckskraft wie der relationale Tupel- und Domänenkalkül.

Datalog mit Negation und Rekursion geht natürlich über die Ausdruckskraft der relationalen Algebra hinaus, z.B.: man kann in Datalog die transitive Hülle einer Relation definieren.

33

Datalog-Formulierung der relationalen Algebra-Operatoren

( )( ) ( )( ) ( ).,,"",:,,

.3,,,,:,,,

,3

RSMäeutikVnvorlesungeRSVquerySRSTVnvorlesungeRSTVquery

nVorlesungeSWSσ

−>−

>

Selektion

Projektion).,,,(:),( RaumRangNamePersNrnprofessoreRangNamequery −

Join(

( ) ( ) ( ).,,,,,,,:,

,

RaRgNRnprofessoreRSTVnvorlesungeNTquery

ProfessorennVorlesunge A gelesenVon=gelesenVonNameTitel

−

Π )

34

Datalog-Formulierung der relationalen Algebra-Operatoren

Kreuzprodukt

nVorlesunge n Professore

).4,3,2,1( ),4,3,2,1(:)4,3,2,1,4,3,2,1(

×

−PPPPnprofessoreVVVVnvorlesungePPPPVVVVquery

Vereinigung

( ) ( )

).,,,(:),().,,,(:),(

,

RaRgNamePersNrnprofessoreNamePersNrqueryBFNamePersNrnassistenteNamePersNrquery

nProfessorenAssistente PersNr,NameNamePersNr

−−

Π∪Π

35

Datalog-Formulierung der relationalen Algebra-Operatoren

Mengendifferenz

( ) ( )

( ) ( )( ) ( )

( ) ( ) ( ).,:.,:

.,,,:

VgrundlagenVvorlNrVqueryNVenvoraussetzVgrundlagen

RSTVnvorlesungeVvorlNr

enVoraussetznVorlesunge VorgängerVorlNr

¬−−

−

Π−Π