• Anzeigen
• Bearbeiten
• Versionen
• Druckansicht

Das einfache Graph-Modell

Das einfache Graph-Modell ist ein Untertyp des Graphenmodells und bildet das zugrundeliegende Modell einer Graphendatenbank.

Ein Graph wird durch ein Tupel zweier Mengen beschrieben, der Knotenmenge V (engl. vertices) und der Kantenmenge E (engl. edges). Der oben aufgeführte Graph wird mathematisch beschrieben durch:

G = (V,E), V = {1,2,3}, E = V x V = (1,2), (2,3), (3,1)

Hierbei werden gerichtete und ungerichtete Kanten unterschieden (der Graph in der Abbildung ist ungerichtet). Eine gerichtete Kante beschreibt eine einseitige Beziehung, während eine ungerichtete Kante eine beidseitige Beziehung darstellt. Die Entfernung zweier Städte zueinander wird durch eine ungerichtete Kante ausgedrückt, da die Entfernung in beide Richtungen gleich bleib. Möchte man allerdings eine Route planen, wird der Graph durch gerichtete beschrieben, da eine Straße eventuell nur in eine Richtung befahrbar ist (Einbahnstraßen). Für die Darstellung des Verlaufs eines Flusses und seiner Uferstädte wird ein gerichteter Graph benötigt, da das Wasser nur in eine Richtung fließen kann.

Ein Graph kann in der Regel nur gerichtete oder ungerichtete Kanten besitzen, eine Kombination beider in einem Graphen ist nicht möglich. Möchte man in einem gerichteten Graphen eine Verbindung in beide Richtungen abbilden, so werden zwischen den beiden Knoten zwei Kanten modelliert und die Verbindung ist in beide Richtungen lesbar. Man spricht hier von Mehrfachkanten bzw. Multigraphen. Eine gerichtete Kante wird durch eine Linie mit einem Pfeil in Leserichtung modelliert, während ungerichtete Kanten durch Linien ohne Pfeil gekennzeichnet werden. Oft werden aus Gründen der Übersichtlichkeit Mehrfachkanten durch eine Linie mit zwei Pfeilenden dargestellt. Intern wird diese Darstellung allerdings in zwei verschiedenen Kanten gespeichert, wie rechts in der Abbildung zu sehen ist.

Von einem gewichteten Graphen spricht man, wenn in den Kanten numerische Werte gespeichert werden. Die Entfernung zweier Städte wird direkt in der Kante gespeichert und ein Navigationssystem kann entscheiden, welcher Weg kürzer ist. Dieses Gewicht wird auch als Label oder Property bezeichnet. Möchte man mehr als einen Wert in einer Kante speichern oder zusätzliche Informationen in den Knoten ablegen, wird das Property-Graph-Modell benötigt.

Quellen:

• Edlich, Friedland, Hampe, Brauer: "NoSQL – Einstieg in die Welt der nichtrelationalen Web2.0- Anwendungen", Hanser-Verlag, 2010, ISBN 978-3-446-42355-8

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