Seminar Indizierung von Graphen
Indizieren und Anfragen von Graphen in Datenbanken
Seminar im Wintersemester 2007/08
Silke Trißl
Übersicht
Inhalt
In diesem Seminar werden Arbeiten zum Indizieren und Anfragen von
Graphen in Datenbanken besprochen. Dabei werden Themen wie die
Indizierung von Graphen zur Beantwortung von Erreichbarkeits-, aber
auch Distanz und Pfadanfragen besprochen. Dazu ist in der Literatur in
den letzten Jahren einiges erschienen. Stehen Indexe zur Verfügung, mit
denen solche Anfragen schnell zu beantworten sind, dann kann man auch
Anfrageoptimierung betreiben, wie sie aus der Datenbankforschung
bekannt ist.
Ein etwas anderes Thema ist die Indizierung von vielen kleinen Graphen,
um nach homologen Subgraphen zu suchen. Auch darüber gibt es einige
kürzlich erschiene Arbeiten. Wenn wir solche Graphen gefunden haben,
möchten wir bestimmen, welche Graphen sich am ähnlichsten sind. Dazu
gibt es einige Arbeiten, die eine 'Edit-Distanz' für Bäume und Graphen
definieren. Auch diese Arbeiten werden wir uns während des Seminars
ansehen.
Zeit und Ort
Das Seminar findet im Wintersemester als Blockseminar statt.
Der Termin für die Einführungsveranstaltung mit Vergabe der Themen ist
der 23.10.2007 um 9 Uhr c.t. in RUD25, Raum 3.101. Dieser
Termin ist eine Pflichtveranstaltung.
An diesem Termin wird auch der Termin für die Blockveranstaltung
besprochen, die voraussichtlich am 12. und 19. Februar 2008 stattfinden
wird.
Eine weitere Veranstaltung findet am 30.10.2007 um 9 Uhr c.t.
ebenfalls in RUD25, Raum 3.101 statt. In dieser Veranstaltung gibt es
auch eine Einführung in LaTeX.
Zusätzlich zur Blockveranstaltung gibt es auch noch eine
Kurz-Präsentation der Themen, voraussichtlich am 08. Januar 2008.
Themen
Die Themen werden bei der Einführungsveranstaltung vergeben. Die Themen im Einzelnen sind (Literaturliste):
| Allgemeine Literatur | ||||
|---|---|---|---|---|
| Einführungsveranstaltung | [Folien] | |||
| LaTeX | [Folien] | |||
| 0 | GraphDB, Complex Networks | Alle | - | |
| Erreichbarkeitsanfragen | ||||
| 1 | Transitive Hülle in der Datenbank | - | - | |
| 2 | Nummerierungsschema - Pre- und Postorder Labeling | Ganzer | - | |
| 3 | Dual Labeling | - | - | |
| 4 | Transitive Hülle mit geometrischem Ansatz | Shakhawat | [Ausarbeitung] | |
| Distanzanfragen | ||||
| 5 | Distanz-Orakel | Serediouk | - | |
| 6 | Index für Distanzen mit Update-Problematik | - | - | |
| 7 | Straßennetzwerk - Hierarchie-Ansatz | Wickert | [Ausarbeitung] | |
| 8 | Straßennetzwerk - Transit-Knoten-Ansatz | Kibanov | - | |
| Anfrageoptimierung | ||||
| 9 | Twig-Query Processing auf Bäumen | Schulze | - | |
| 10 | XML Query Optimierung | Sax | [Ausarbeitung] | |
| Suche nach Graphen | ||||
| 11 | Closure-Trees: Ähnlichkeit von häufigen Subgraphen | - | - | |
| 12 | Indizierung von Graphen durch häufige Subgraphen (1) | Hellwig | [Ausarbeitung] | |
| 13 | Indizierung von Graphen durch häufige Subgraphen (2) | Tsitiridou | [Ausarbeitung] | |
| Graphen & Biologie | ||||
| 14 | Graphanfragen - Sprachen und Umsetzung | - | - | |
| 15 | QPath - Suche nach Pfaden | - | - | |
| 16 | Biologische Netzwerke vergleichen | Kunath | - | |
Teilnahmevoraussetzungen
Teilnahmeberechtigt sind alle Studenten der Informatik im Hauptstudium, die Interesse an dem Thema haben. Die Anmeldung zum Seminar erfolgt ausschließlich über Goya.
Scheinerwerb
Die Teilnehmer/innen des Seminars können am Ende einen Schein
erhalten. Voraussetzungen dafür sind die aktive Teilnahme am Seminar,
die Präsentation eines ausgewählten Themas, sowie die Anfertigung einer
schriftlichen Ausarbeitung über dieses Thema (10-15 Seiten).
Verpflichtend ist die Teilnahme bei der Themenvergabe, an der
Vorbesprechung sowie die Anwesenheit bei allen Vorträgen. Jeder Vortrag
wird ca. 45 Minuten dauern und muss selbstständig erstellt sein. Ein
Kurzvortrag soll etwa 5 Minuten dauern.
Das Thema ist mit dem Betreuer vor dem 07. Dezember 2007 und die
Vortragsfolien etwa eine Woche vor dem Blockseminar zu besprechen.
Termine für beide Vorbesprechungen (Thema & Folien) bitte
rechtzeitig mir abklären. Die Anmeldung zum Seminar erfolgt
ausschließlich über Goya.
Die Ausarbeitung ist ausschließlich mit LateX zu erstellen, die
LateX-Vorlage ist unter 'Zusätzliches
Material' zu finden.
Vorträge und Ausarbeitung können mit dem jeweiligen Betreuer der
Arbeit nachbesprochen werden. Termine hierfür bitte individuell
vereinbaren.
Vorträge
Das Blockseminar findet am Dienstag, den 19.02.2008 in der Zeit von 10 - 15 Uhr in RUD25, Haus 3, Raum 113.
| Erreichbarkeitsanfragen | |||
|---|---|---|---|
| 4 | Transitive Hülle mit geometrischem Ansatz | Shakhawat | [Vortrag] |
| Anfrageoptimierung | |||
| 10 | XML Query Optimierung | Sax | [Vortrag] |
| Distanzanfragen | |||
| 7 | Straßennetzwerk - Hierarchie-Ansatz | Wickert | [Vortrag] |
| Suche nach Graphen | |||
| 12 | Indizierung von Graphen durch häufige Subgraphen (1) | Hellwig | [Vortrag] |
| 13 | Indizierung von Graphen durch häufige Subgraphen (2) | Tsitiridou | [Vortrag] |
Kontakt
Bei Fragen wenden Sie sich bitte an Silke Trißl, RUD25, IV.116.