Graphenmodell
Ein Graph und sein zugrunde liegendes Graphenmodell besteht aus einer Menge an Knoten und Kanten. Kanten verbinden die Knoten untereinander und bilden die Beziehungen der Knoten ab. Graphendatenbanken wenden diese Modelle als Speicherstruktur an.
Graphen werden genutzt, um eine Vielfalt an Problemen durch Knoten, Kanten und ihren Beziehungen darzustellen. Ein Beispiel dafür ist ein Navigationssystem, bei dem die Straßenkarten in Form eines Graphen gespeichert werden. Die Struktur des Internets mit Verlinkungen der Seiten kann ebenfalls mit einem Graphenmodell abgebildet werden. Weitere Einsatzgebiete sind unter Graphendatenbanken erläutert.
Aber auch rekursive Abfragen auf relationale Datenmodelle können durch einfache Graph-Traversal ersetzt werden. Während in einem relationalen Modell eine Vorgesetzter-Mitarbeiter-Struktur in einer Tabelle mit rekursiven Abfragen abgebildet werden muss, kann diese Struktur in einem Graphenmodell in eine einfache Breitensuche ohne Rekursion umgewandelt werden.
Unterschied RDBS vs. Graphenmodell, o. RDBS mit rekursiver Abfrage, u. Graphenmodell
Es existieren allerdings auch Anwendungsfälle, für die Graphenmodelle eher ungeeignet sind, nämlich immer dann, wenn die Konsistenz im Vordergrund stehen muss. In einer Lagerverwaltung ist es wichtig, dass immer die aktuellen Stückzahlen vorliegen, um evtl. zeitnah eine Neubestellung abzuschließen.
Ebenfalls ungeeignet für Graphenmodelle sind große Tabellen, die als Speichercontainer dienen. Hier würde für jeden Tabelleneintrag ein neuer Knoten entstehen, wodurch eine Traversierung relativ lange dauern würde. Weiterhin wären die Knoten hier nicht oder nur selten miteinander verbunden und es müssen bei einer Abfrage alle Knoten ohne Start und Ende iteriert werden, was ebenfalls längere Zeit in Anspruch nimmt.
Graphenmodelle
Es werden grundsätzlich zwei Arten von Graph-Modellen unterschieden, das einfache Graph-Modell und das Property-Graph-Modell, wobei letzteres eine Erweiterung des einfachen Graphenmodells darstellt. Ein sogenannter Hypergraph ist ein weiterer spezieller Typ, bei dem eine Kante mehrere Knoten miteinander verbindet.
Skalierung eines Graphen
Wenn der Umfang der zu verwaltenden Knoten und Kanten die Leistungsfähigkeit eines Servers übersteigt, existieren zwei Arten der Skalierung, um die Last zu verteilen. Wann eine Skalierung sinnvoll ist, hängt in der Regel von der zugrundeliegenden Hardware ab (Festplattenplatz, Arbeitsspeicher) und muss je nach Art der Anwendung entschieden werden.
Es existieren zwei grundlegende Skalierungsarten:
Quellen:
- Edlich, Friedland, Hampe, Brauer: "NoSQL – Einstieg in die Welt der nichtrelationalen Web2.0- Anwendungen", Hanser-Verlag, 2010, ISBN 978-3-446-42355-8
- Prof. Dr. Peter Sanders, Dipl.-Inform. Johannes Singler: "Berechnung kürzester Wege", http://algo2.iti.kit.edu/singler/algorithmus-der-woche/Kuerzeste%20Wege.pdf, Stand Mai 2011
- Prof. Dr. Bernhard Schiefer: "Algorithmische Graphentheorie", http://www.informatik.fh-kl.de/~schiefer/lectures/download/GT_7.pdf, Stand Mai 2011
- Thomas Hofmeister: "Randomisierte Algorithmen", http://www14.informatik.tu-muenchen.de/lehre/2006WS/ra/Hofmeister.pdf, 2006, Stand Mai 2011
- Alexander Esser: "Der Dijkstra-Algorithmus zur Berechnung kürzester Wege in Graphen",1. Auflage, GRIN Verlag, 2009, ISBN 978-3-640-39550-7
Weiterführende Literatur:
- Prof. Dr. rer. nat. Peter Tittman: "Graphentheorie", Fachbuchverlag Leipzig im Carl Hanser Verlag, 2003, ISBN 3-446-22343-6
- Prof. Dr. Volker Turas: "Algorithmische Graphentheorie", 3. Auflage, Oldenburg Wissenschaftsverlag, 2009, ISBN 978-3-486-59057-9
- Bucher Gruppe: "Graphentheorie: Wege, Pfade, Zyklen und Kreise in Graphen, Durchlaufbarkeit Von Graphen, Vier-Farben-Satz, Zusammenhang Von Graphen", General Books LLC, 2010, ISBN 978-1-159-11215-8
- Steffi Meier: "Graphentheoretische Modelle zur Optimierung und Simulation", 1. Auflage, GRIN Verlag, 2006, ISBN 978-3-640-32530-6
Kategorie: Neue DB-Entwicklungen, NoSQL, Graphen-DB, G,