Transcript
Graphmanagement in Datenbanken Thema: Warshall-Algorithmus in der Datenbank Seminar im WS 2005/06 Dozenten: Professor Ulf Leser, Silke Trißl Referentin: Ayşegül Gündoğan
1
Gliederung Einführung Warshall Algorithmus Modifizierter Warshall Algorithmus Blocked Warshall Lu Zusammenfassung 2
1
Einführung Es werden Algorithmen vorgestellt, um die transitive Hülle einer Datenbankrelation zu berechnen (gerichtete) Graphen als Relationen vorhanden
3
Warshall Algorithmus Bevor wir beginnen… …einige Definition:
Ein Graph G = (V,E) besteht aus einer Menge von Knoten V (Vertices) und einer Menge von Kanten E (Edges). Zwei Knoten, die durch eine Kante verbunden sind, heissen adjazent Der Grad eines Knotens ist die Anzahl der adjazenten Knoten
4
2
Weitere Definitionen Datenstrukturen für Graphen
Adjazenzmatrix: Boolesche Matrix, bei der ein Eintrag a[i,j] wahr ist, falls eine Kante (i,j) existiert. Adjazenzliste: Zu jedem Knoten v wird eine Liste der von v aus erreichbaren Knoten gespeichert.
Gerichtete Graphen
Bei einem gerichteten Graphen haben alle Kanten eine Richtung:Vorgänger, Nachfolger.
5
Weitere Definitionen Die transitive Hülle (transitive closure)
für jeden gerichteten Pfad von a nach b im Graphen G wird eine Kante (a,b) in G* eingefügt D.h. existiert so ein Pfad, findet je nach Algorithmus entweder Eintrag in einer Matrix, oder z ein Listeneintrag statt z
6
3
Warshall Algorithmus Eingabe: n x n-Adjazenzmatrix A eines Graphen G Ausgabe: n x n-Adjazenzmatrix A* des Graphen G* mit A*i,j = 1, falls es einen Weg von Knoten i nach Knoten j gibt und A*i,j = 0 sonst
7
Warshall Algorithmus: Beispiel Graph G: G*:
Für k = 1; i = 2; j = 5; Für k = 1; i = 5; j = 5; 0
Adjazenmatrix A: A*: j 0 0
5
i 4
2 3
1
1
1
2
1
2
3
4
5
1
1
1
1
1
1
1
1
1
1
1
1
3 4 5
1
for (k=0; k
2
foreach(tєL and t.A > t.B) do
L´ = [(0,0), (0,5), (1,5), (2,1), (2,4), (5,1)]
L´ 1.foreach
begin
3 4
findall t´ in L where t.B = t´.A;
5
insert{(t.A,t´.B)}into L;
7
foreach(tєLand t.A
