Partitionierung eines Graphen
Die Partitionierung ist eine Art der horizontalen Skalierung eines Graphen. Wenn der Graph zu groß für ein bestehendes Hardwaresystem wird, wird mit der Partitionierung versucht, den Graph aufzuteilen, so dass dieser auf mehrere Systeme verteilt liegt.
Es wird versucht, den Graphen in kleinere Teilgraphen zu unterteilen. Der Graph wird horizontal über mehrere Systeme skaliert. Allerdings ist es nicht immer einfach, eine entsprechende Stelle für eine Teilung im Graphen zu finden. Selbst bei einer gleichverteilten Relevanz aller Knoten im Graph, existiert keine mathematisch exakte Methode, um die Anzahl der durchschnittenen Kanten zu minimieren. Es existieren ein paar heuristische Algorithmen (z.B. Clustering-Algorithmen), die stark vernetzte Teilgraphen zu abstrakten Knoten zusammenziehen. Diese "neuen" Knoten bilden die Teilgraphen.
Kann der Graph nicht komplett geteilt werden, können Knoten in zwei oder mehreren Teilgraphen existieren. Man sprich hier von einer sich überlappenden Partitionierung. Die Konsistenz dieser replizierten Knoten muss durch verteilte Sperr- und Transaktionsmechanismen sichergestellt werden.
Aber auch gerade durch die dynamischen und sich ständig verändernden Abfragen sollte ein Graph regelmäßig neu partitioniert werden, bei der die Anzahl der zu verschiebenden Knoten minimiert werden sollte.
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. Bernhard Schiefer: "Algorithmische Graphentheorie", http://www.informatik.fh-kl.de/~schiefer/lectures/download/GT_7.pdf, Stand Mai 2011
Weiterführende Literatur:
- Prof. Dr. rer. nat. Peter Tittman: "Graphentheorie", Fachbuchverlag Leipzig im Carl Hanser Verlag, 2003, ISBN 3-446-22343-6
- Steffi Meier: "Graphentheoretische Modelle zur Optimierung und Simulation", 1. Auflage, GRIN Verlag, 2006, ISBN 978-3-640-32530-6
Kategorie: Neue DB-Entwicklungen, NoSQL, P, Graphen-DB,