Transcript
Page 1: Seminar Indizieren und Anfragen von Graphen in Datenbanken WS 2007/2008 Thema Transitive Hülle mit geometrischem Ansatz Habib Muhammad Shakhawat shakhawa@informatik.hu-berlin.de

Seminar

Indizieren und Anfragen von Graphen in Datenbanken

WS 2007/2008

Thema

Transitive Hülle mit geometrischem Ansatz

Habib Muhammad Shakhawat

[email protected]

Page 2: Seminar Indizieren und Anfragen von Graphen in Datenbanken WS 2007/2008 Thema Transitive Hülle mit geometrischem Ansatz Habib Muhammad Shakhawat shakhawa@informatik.hu-berlin.de

2

Transitive Hülle mit geometrischem Ansatz

ÜbersichtMotivationZiel definierenMögliche ProblemeGraphentheoretische DefinitionenKurzer Überblick in bisherige Lösungen Vorschlag mit geometrischem AnsatzLeistungsvergleich

Page 3: Seminar Indizieren und Anfragen von Graphen in Datenbanken WS 2007/2008 Thema Transitive Hülle mit geometrischem Ansatz Habib Muhammad Shakhawat shakhawa@informatik.hu-berlin.de

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.

Page 4: Seminar Indizieren und Anfragen von Graphen in Datenbanken WS 2007/2008 Thema Transitive Hülle mit geometrischem Ansatz Habib Muhammad Shakhawat shakhawa@informatik.hu-berlin.de

4

Transitive Hülle mit geometrischem Ansatz Motivation

• u und v sind zwei Datenobjekte

Stehen u und v in einer Beziehung ?

Page 5: Seminar Indizieren und Anfragen von Graphen in Datenbanken WS 2007/2008 Thema Transitive Hülle mit geometrischem Ansatz Habib Muhammad Shakhawat shakhawa@informatik.hu-berlin.de

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?

Page 6: Seminar Indizieren und Anfragen von Graphen in Datenbanken WS 2007/2008 Thema Transitive Hülle mit geometrischem Ansatz Habib Muhammad Shakhawat shakhawa@informatik.hu-berlin.de

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

Page 7: Seminar Indizieren und Anfragen von Graphen in Datenbanken WS 2007/2008 Thema Transitive Hülle mit geometrischem Ansatz Habib Muhammad Shakhawat shakhawa@informatik.hu-berlin.de

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

Page 8: Seminar Indizieren und Anfragen von Graphen in Datenbanken WS 2007/2008 Thema Transitive Hülle mit geometrischem Ansatz Habib Muhammad Shakhawat shakhawa@informatik.hu-berlin.de

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

Page 9: Seminar Indizieren und Anfragen von Graphen in Datenbanken WS 2007/2008 Thema Transitive Hülle mit geometrischem Ansatz Habib Muhammad Shakhawat shakhawa@informatik.hu-berlin.de

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

Page 10: Seminar Indizieren und Anfragen von Graphen in Datenbanken WS 2007/2008 Thema Transitive Hülle mit geometrischem Ansatz Habib Muhammad Shakhawat shakhawa@informatik.hu-berlin.de

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

Page 11: Seminar Indizieren und Anfragen von Graphen in Datenbanken WS 2007/2008 Thema Transitive Hülle mit geometrischem Ansatz Habib Muhammad Shakhawat shakhawa@informatik.hu-berlin.de

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

Page 12: Seminar Indizieren und Anfragen von Graphen in Datenbanken WS 2007/2008 Thema Transitive Hülle mit geometrischem Ansatz Habib Muhammad Shakhawat shakhawa@informatik.hu-berlin.de

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

Page 13: Seminar Indizieren und Anfragen von Graphen in Datenbanken WS 2007/2008 Thema Transitive Hülle mit geometrischem Ansatz Habib Muhammad Shakhawat shakhawa@informatik.hu-berlin.de

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

Page 14: Seminar Indizieren und Anfragen von Graphen in Datenbanken WS 2007/2008 Thema Transitive Hülle mit geometrischem Ansatz Habib Muhammad Shakhawat shakhawa@informatik.hu-berlin.de

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

Page 15: Seminar Indizieren und Anfragen von Graphen in Datenbanken WS 2007/2008 Thema Transitive Hülle mit geometrischem Ansatz Habib Muhammad Shakhawat shakhawa@informatik.hu-berlin.de

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

Page 16: Seminar Indizieren und Anfragen von Graphen in Datenbanken WS 2007/2008 Thema Transitive Hülle mit geometrischem Ansatz Habib Muhammad Shakhawat shakhawa@informatik.hu-berlin.de

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

Page 17: Seminar Indizieren und Anfragen von Graphen in Datenbanken WS 2007/2008 Thema Transitive Hülle mit geometrischem Ansatz Habib Muhammad Shakhawat shakhawa@informatik.hu-berlin.de

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

Page 18: Seminar Indizieren und Anfragen von Graphen in Datenbanken WS 2007/2008 Thema Transitive Hülle mit geometrischem Ansatz Habib Muhammad Shakhawat shakhawa@informatik.hu-berlin.de

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

Page 19: Seminar Indizieren und Anfragen von Graphen in Datenbanken WS 2007/2008 Thema Transitive Hülle mit geometrischem Ansatz Habib Muhammad Shakhawat shakhawa@informatik.hu-berlin.de

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

Page 20: Seminar Indizieren und Anfragen von Graphen in Datenbanken WS 2007/2008 Thema Transitive Hülle mit geometrischem Ansatz Habib Muhammad Shakhawat shakhawa@informatik.hu-berlin.de

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

Page 21: Seminar Indizieren und Anfragen von Graphen in Datenbanken WS 2007/2008 Thema Transitive Hülle mit geometrischem Ansatz Habib Muhammad Shakhawat shakhawa@informatik.hu-berlin.de

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]

Page 22: Seminar Indizieren und Anfragen von Graphen in Datenbanken WS 2007/2008 Thema Transitive Hülle mit geometrischem Ansatz Habib Muhammad Shakhawat shakhawa@informatik.hu-berlin.de

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]

Page 23: Seminar Indizieren und Anfragen von Graphen in Datenbanken WS 2007/2008 Thema Transitive Hülle mit geometrischem Ansatz Habib Muhammad Shakhawat shakhawa@informatik.hu-berlin.de

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

Page 24: Seminar Indizieren und Anfragen von Graphen in Datenbanken WS 2007/2008 Thema Transitive Hülle mit geometrischem Ansatz Habib Muhammad Shakhawat shakhawa@informatik.hu-berlin.de

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

Page 25: Seminar Indizieren und Anfragen von Graphen in Datenbanken WS 2007/2008 Thema Transitive Hülle mit geometrischem Ansatz Habib Muhammad Shakhawat shakhawa@informatik.hu-berlin.de

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

Page 26: Seminar Indizieren und Anfragen von Graphen in Datenbanken WS 2007/2008 Thema Transitive Hülle mit geometrischem Ansatz Habib Muhammad Shakhawat shakhawa@informatik.hu-berlin.de

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

Page 27: Seminar Indizieren und Anfragen von Graphen in Datenbanken WS 2007/2008 Thema Transitive Hülle mit geometrischem Ansatz Habib Muhammad Shakhawat shakhawa@informatik.hu-berlin.de

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

Page 28: Seminar Indizieren und Anfragen von Graphen in Datenbanken WS 2007/2008 Thema Transitive Hülle mit geometrischem Ansatz Habib Muhammad Shakhawat shakhawa@informatik.hu-berlin.de

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.

Page 29: Seminar Indizieren und Anfragen von Graphen in Datenbanken WS 2007/2008 Thema Transitive Hülle mit geometrischem Ansatz Habib Muhammad Shakhawat shakhawa@informatik.hu-berlin.de

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))

Page 30: Seminar Indizieren und Anfragen von Graphen in Datenbanken WS 2007/2008 Thema Transitive Hülle mit geometrischem Ansatz Habib Muhammad Shakhawat shakhawa@informatik.hu-berlin.de

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

)

Page 31: Seminar Indizieren und Anfragen von Graphen in Datenbanken WS 2007/2008 Thema Transitive Hülle mit geometrischem Ansatz Habib Muhammad Shakhawat shakhawa@informatik.hu-berlin.de

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.

Page 32: Seminar Indizieren und Anfragen von Graphen in Datenbanken WS 2007/2008 Thema Transitive Hülle mit geometrischem Ansatz Habib Muhammad Shakhawat shakhawa@informatik.hu-berlin.de

32

Transitive Hülle mit geometrischem Ansatz Maxcardinality-G: Algorithmus

Page 33: Seminar Indizieren und Anfragen von Graphen in Datenbanken WS 2007/2008 Thema Transitive Hülle mit geometrischem Ansatz Habib Muhammad Shakhawat shakhawa@informatik.hu-berlin.de

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

Page 34: Seminar Indizieren und Anfragen von Graphen in Datenbanken WS 2007/2008 Thema Transitive Hülle mit geometrischem Ansatz Habib Muhammad Shakhawat shakhawa@informatik.hu-berlin.de

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

Page 35: Seminar Indizieren und Anfragen von Graphen in Datenbanken WS 2007/2008 Thema Transitive Hülle mit geometrischem Ansatz Habib Muhammad Shakhawat shakhawa@informatik.hu-berlin.de

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

Page 36: Seminar Indizieren und Anfragen von Graphen in Datenbanken WS 2007/2008 Thema Transitive Hülle mit geometrischem Ansatz Habib Muhammad Shakhawat shakhawa@informatik.hu-berlin.de

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

Page 37: Seminar Indizieren und Anfragen von Graphen in Datenbanken WS 2007/2008 Thema Transitive Hülle mit geometrischem Ansatz Habib Muhammad Shakhawat shakhawa@informatik.hu-berlin.de

37

Transitive Hülle mit geometrischem Ansatz

Fragen ?

Danke für die Aufmerksamkeit


Recommended