Seminar
Indizieren und Anfragen von Graphen in Datenbanken
WS 2007/2008
Thema
Transitive Hülle mit geometrischem Ansatz
Habib Muhammad Shakhawat
2
Transitive Hülle mit geometrischem Ansatz
ÜbersichtMotivationZiel definierenMögliche ProblemeGraphentheoretische DefinitionenKurzer Überblick in bisherige Lösungen Vorschlag mit geometrischem AnsatzLeistungsvergleich
3
Transitive Hülle mit geometrischem Ansatz Motivation
• Daten als gerichteter Graph• Bio-Informatik• Semantic Web• Computer Vision• usw.
• Hauptaufgabe einer Datenbank besteht darin die Beziehungen zwischen verschiedene Datenobjekte zu finden und analysieren.
4
Transitive Hülle mit geometrischem Ansatz Motivation
• u und v sind zwei Datenobjekte
Stehen u und v in einer Beziehung ?
5
Transitive Hülle mit geometrischem Ansatz Zielformulierung
GegebenEin gerichteter Graph G = (V,E)u, v V
Ziel: Schnelle Antwort auf der Frage
Gibt es einen Pfad von u nach v in G?
6
Transitive Hülle mit geometrischem Ansatz Wo sind die Probleme ?
Erreichbarkeitsinformation über den gesamten Graph notwendig
Reale Graphen sind groß
Preprocessing notwendig
Höhe Speicher- und Zeitbedarf
7
Transitive Hülle mit geometrischem Ansatz Einige Definitionen
Graph: Ein Graph G=(V,E) besteht aus eine endliche Menge von Knoten V und Kanten E .
0
1 2
34 Ungerichtet
G Gerichtet
0
1 2
34
8
Transitive Hülle mit geometrischem Ansatz Einige Definitionen
Pfad: Ein Weg indem kein Knoten mehrfach vorkommt.
Kreis: Ein geschlossener Kantenzug, in dem kein Knoten mehrfach vorkommt.
Starke Zusammenhangskomponente (SZK): Für jede bel. u und v in V gilt: es ex. ein Pfad aus u nach v in G.
0
1 2
34
0
1 2
34
0
1 2
34
5
9
Transitive Hülle mit geometrischem Ansatz Einige Definitionen
Transitive Hülle: H(G)=(V, E´) ist transitive Hülle von G=(V, E) gdw. E´={(u,v)|u,vV und Pfad von v nach w in E}
0
1 2
34
1 0 1 1 1
1 1 1 1 1
0 0 1 1 1
0 0 1 1 1
0 0 1 1 1
n x n Erreichbarkeitsmatrix
Nach
Von
10
Transitive Hülle mit geometrischem Ansatz Einige Definitionen
)( 2nO
Problematik bei Transitive Hülle
• Sehr hoher Zeitaufwand bei der Berechnung
• Warshall
• Sehr hoher Speicherbedarf• Worst-Case
)( 3nO
11
Transitive Hülle mit geometrischem Ansatz Kurzer Überblick: Bisherige Lösungen
2-hop cover (Cohen et al, 2002)Pfade als Konkatenation je zweier
Pfadteilstücke zu repräsentierenTeilstücke werden an so genannten
Hop – Knoten zusammengefügt
C = Hop-Knoten
a b c d e f
12
Transitive Hülle mit geometrischem Ansatz Kurzer Überblick: Bisherige Lösungen
Beispiel: 2-hop cover
a c
b c
c c
a b c d e f
c c
c d
c e
c f
a c
a d
a e
a f
b c
b d
b e
b b
c c
c d
c e
c fcin
⋈ =
cout
Überdeckte Kanten in TC
13
Transitive Hülle mit geometrischem Ansatz Kurzer Überblick: Bisherige Lösungen
Vorteil: 2-Hop Cover
Statt der ganzen transitiven Hülle speichert man nur die Pfade zu den Hop-Knoten
Größe der 2-hop cover ist kleiner als die Transitive Hülle
Antwortzeiten sind konstant
14
Transitive Hülle mit geometrischem Ansatz Kurzer Überblick: Bisherige Lösungen
Nachteile: 2-Hop Cover
Transitive Hülle muss vor der Überdeckung durch Hop-Knoten zunächst vollständig materialisiert werden
- Transitive Hülle als Grundmenge für 2-hop cover
Schlechte Laufzeit bei der Berechnung der Hop-Knoten
15
Transitive Hülle mit geometrischem Ansatz Kurzer Überblick: Bisherige Lösungen Beispiel:
Konstruktionszeit und Speicherbedarf
Eingabe: Ein Teilgraph von DBLP mit 344,992,370 Verbindungen
System: SUN-Fire 15000 mit 64 Prozessoren und 180 GB RAM
Große 2-hop cover: 1,289,930 Einträge
Speicherverbrauch: 80 GB RAM
Zeit: 45 Stunden und 23 Minuten
16
Transitive Hülle mit geometrischem Ansatz
Kurzer Überblick: Bisherige Lösungen
Wünschenswert
Ohne aufwendige Berechnung der Transitive Hülle auszukommen
Möglich viele Informationen im Speicher halten
17
Transitive Hülle mit geometrischem Ansatz MaxCardinality-G (Cheng et al.)
Wünsche werden erfüllt durch geometrischen Ansatz nach Cheng et al.
Berechnung der Transitive Hülle nicht otwendig
Bestimmung der 2-Hop Cover durch Rechteckoperationen
Visualisierung der Erreichbarkeitsmatrix durch Rechtecke in einem 2-dim. Gitter
18
Transitive Hülle mit geometrischem Ansatz Maxcardinality-G (Cheng et al.)
Gegeben: Ein gerichteter Graph G Maxcardinatily-G berechnet 2-Hop
Cover in 3 Schritten
1) Konstruiere aus G einen gerichteten kreisfreien Graph G
2) Bestimme 2-Hop Cover für G
3) Bestimme 2-Hop Cover für G aus dem 2-Hop Cover von G
19
Transitive Hülle mit geometrischem Ansatz Maxcardinality-G: Konstruktion eines kreisfreien
Graph
Finde alle starken Zusammenhangs-komponenten (SZK) in G.
0
12
3
78
64
1
10
5
9
11
G
Ersetze SZK mit einen zufällig ausgesuchten Knoten v´aus dem SZK
Füge alle ein- und ausgehende Kanten von SZK zu v´hin.
G
20
Transitive Hülle mit geometrischem Ansatz Maxcardinality-G: Konstruktion eines kreisfreien
Graph
Vorteile:
G hat weniger Knoten und Kanten als G (ausgenommen, G hat keine SZK)
Mit zunehmender Kantenanzahl steigt die Wahscheinlichkeit der SZK Je mehr SZK desto kleiner ist G
Alle Knoten in einem SZK haben den selben Hop-Knoten. Vermeidung unnötiger
Berechnungen
0
123
84
1
5
11
9
G
21
Transitive Hülle mit geometrischem Ansatz Maxcardinality-G: Intervall Labeling
Gwird zerlegt in Spannenden Baum T Nicht-Baumkanten EN
Jeder Knoten v in T bekommt min. ein Intervall [s, e]
e: Postorder Nummer des Knotens Vergabe bei Postorder Traversal
s: Kleinste Postorder Nummer seiner Nachfolger
0
123
84
1
5
11
9
G
2
5
67
4
3
1
9
8
[1,1]
[3,3]
[3,4]
[3,5]
[1,6]
[7,7]
[1,9]
[8,8]
[2,2]
22
Transitive Hülle mit geometrischem Ansatz Maxcardinality-G: Intervall Labeling
Nicht-Baumkanten EN
Ist u, v EN, so bekommt u alle Intervalle von v und alle Vorgänger von u ebenso
Intervalle können zusammengefügt werden
.z.B. [5, 9] und [10,15] zusammengefügt in [5, 15]
Falls ein Intervall in einem Anderen enthalten ist, kann eliminiert werden
0
123
84
1
5
11
9
G
2
5
67
4
3
1
9
8
[1,1]
[3,3]
[3,4]
[3,5]
[1,6]
[7,7]
[1,9]
[8,8]
[2,2]
[3,3]
[3,3]
[1,1][3,3]
[1,1]
23
Transitive Hülle mit geometrischem Ansatz Maxcardinality-G: Reachability Table
Konstruiere aus G (V, E) einen zusätzlichen Graph G (V, E), so dass
| V|=| V|(v, u) ist eine Kante in E, falls (u, v) eine
Kante in E ist
Berechne Postorder Nr. und die Intervall Labels für G
Speichere die Informationen in einer Reachability Table
24
Transitive Hülle mit geometrischem Ansatz Maxcardinality-G: Reachability Table
0
123
84
15
11
9
0
12
9
1
4 85
11
3
G G
25
Transitive Hülle mit geometrischem Ansatz Maxcardinality-G: Reachability Map
Virtuelle Darstellung der Reachability Table als Reachability Map M durch n x n Gitter
• x-Achse: Postorder Nr. in G• y-Achse: Postorder Nr. in G
26
Transitive Hülle mit geometrischem Ansatz Maxcardinality-G: Reachability Map
Wenn po(w) I(v), dann
M(po(w), po(v))=true
Beispiel:po(9) ∈ I(5) M(4,6)=true
x
27
Transitive Hülle mit geometrischem Ansatz Maxcardinality-G: Reachability Map
Funktion f zuordnet jedes Knotenpaar u, v in Gin einer Zelle (x(v), y(u)) in M, wobei x(w)=po(w)- po: Postorder Nr. in G y(w)=po(w)- po: Postorder in G
f(u,v) = 1, falls v aus u erreichbar ist, sonst 0
Erreichbarkeit: aus 3 zu 9
f(3,9)=(x(9),y(3))=(4,5)=1x
28
Transitive Hülle mit geometrischem Ansatz Maxcardinality-G: Algorithmus
Algorithmus Schritt 1: Suche max. Fläche
Von Knoten w Noch nicht überdeckt
Schritt 2: w wird neuer Hop-Knoten Erzeuge 2-Hop Labeling für w Speichere w als Hop-Knoten
Schritt 3: Weiter mit Schritt 1, solange w noch vorhanden ist.
29
Transitive Hülle mit geometrischem Ansatz Maxcardinality-G: Algorithmus
Konstruktion: Recheck für w als Hop-Knoten
Beispiel: w=1
I(1)=((s1, e1)=[1,1]), (s2, e2)=[3,3])I(1)=(s1´, e1´)=[1,5]Bilde die Rechtecke durch kombinationen aus I(w) und I(w).
Rechtecke:((s1, s1´), (e1, e1´))=((1,1), (1,5))((s2, s1´), (e2, e1´))=((3,1), (3,5))
30
Transitive Hülle mit geometrischem Ansatz Maxcardinality-G: Rechteckoperationen
Rect(BC1 BC2
) = Rect(BC1) Rect(BC2
) Rect(BC1
BC2) = Rect(BC1
) Rect(BC2)
Rect(BC1 − BC2
) = Rect(BC1) − Rect(BC2
)
31
Transitive Hülle mit geometrischem Ansatz Maxcardinality-G: Algorithmus
Algorithmus Schritt 1: Suche max. Fläche
Von Knoten w Noch nicht überdeckt
Schritt 2: w wird neuer Hop-Knoten Erzeuge 2-Hop Labeling für w Speichere w als Hop-Knoten
Schritt 3: Weiter mit Schritt 1, solange w noch vorhanden ist.
32
Transitive Hülle mit geometrischem Ansatz Maxcardinality-G: Algorithmus
33
Transitive Hülle mit geometrischem Ansatz Maxcardinality-G: Algorithmus
Gefundene 2-hop cover
0 3
5 9
8 1
12
1
0 8
0 12
1 11
3 1
3 4
3 5
3 9
3 11
9 11
0
123
84
15
11
9
In Out
2-hop cover
34
Transitive Hülle mit geometrischem Ansatz Leistungsvergleich
Fazit: Gefundene 2-hop cover sind ähnlich
Cohen
Cheng
Messung am generierten und reale Daten Cohen´s Algorithmus gegen Cheng´s
35
Transitive Hülle mit geometrischem Ansatz Leistungsvergleich
Messung am generierten und reale Daten Cohen´s Algorithmus gegen Cheng´s
Cohen
Cheng
Fazit: Cheng´s Algorithmus ist schneller als Cohen´s
36
Transitive Hülle mit geometrischem Ansatz Literatur
Cheng, J., Yu, J.X., Lin, X., Wang, H. & Yu, P.S. Fast Computation of Reachability Labeling for Large Graphs. EDBT Conference 2006
R. Agrawal, A. Borgida, and H. V. Jagadish. Efficient management of transitive relationships in large data and knowledge bases. In Proc. of SIGMOD’89, 1989.
E. Cohen, E. Halperin, H. Kaplan, and U. Zwick. Reachability and distance queries via 2-hop labels. In Proc. of SODA’02, 2002
37
Transitive Hülle mit geometrischem Ansatz
Fragen ?
Danke für die Aufmerksamkeit