Startseite » Datenbank Lexikon » Graphdatenbanken

Graphdatenbanken

Die Entwicklung von Graphdatenbanken rührt von dem Bedürfnis her, reale Sachverhalte in Datenbanken zu speichern, ohne künstliche Konstrukte zu erzeugen (z. B. Primär-Fremdschlüssel, Relationstabellen) oder die Informationen aufzuteilen (z. B. in die Dritte Normalform).

Mit Graphdatenbanken sollen Objekte und deren Beziehungen untereinander in „natürlicher“ Art und Weise zusammengehörig gespeichert werden.

Dabei entsteht eine Vernetzung der Daten, die unserem Denken ähnlich ist, in dem Objekte (z. B. Personen, Mitarbeiter) in Beziehung zu uns anderen bekannten Objekten (z. B. Familie, Firma) gesetzt werden.

Graphdatenbanken im Vergleich zu herkömmlichen Datenbankmodellen

Die Verwendung von Graphen zur Darstellung und Vernetzung von Informationen ist ein weit erforschtes Feld und bietet ausgereifte Algorithmen, um diese in spezialisierte Datenbanken umzusetzen. Nichtsdestotrotz können Graphen auch in relationalen Datenbanken oder durch Key-Value-Paare abgebildet werden. Die Wiederherstellung der ursprünglichen Informationen ist jedoch sehr aufwändig, da die Graphen nur implizit gespeichert werden.

Eine eigenständige Graphdatenbank hingegen, speichert das Graphenmodell explizit. Hierfür werden Operationen, die von Graph-Algorithmen hergeleitet sind, verwendet. Diese haben vergleichbare Aufgaben wie herkömmliche Datenbankoperationen (z. B. Abfrage, Manipulation, Erzeugung mittels SQL).

Aufbau von Graphen

Ein Graph besteht aus einer Reihe von Knoten und Kanten, die jede für sich bestimmte Informationen speichern können. Hierbei stellen die Knoten das Objekt und die Kanten die Beziehung zwischen den Objekten dar.

Graphdatenbank Definition & Erklärung| Datenbank LexikonEin Graph G kann als Tupel in der Form G = (V, E) beschrieben werden. Hierbei steht das V für die Knotenmenge und das E für die Kantenmenge im Graphen G.

Die Beziehungen in einem Graph können einseitig, durch gerichtete Kanten, oder beidseitig, durch ungerichtete Kanten, dargestellt werden.

Besitzt der Graph Kantengewichte, wird er als gewichteter Graph bezeichnet. Dieser speichert bspw. die Information wie groß die Distanz oder die Transportdauer zwischen zwei Objekten über eine spezielle Kante ist.

Property-Graphen

In Graphdatenbanken werden sogenannte Property-Graphen verwendet. Dieser ist gewichtet, beschriftet und besitzt Attribute. Beschriftungen auch Labels genannt, beschreiben die verschiedenen Typen von Kanten und Knoten im Graph. Durch die Attribute werden Kanten und Knoten um zusätzliche Eigenschaften erweitert. Dies geschieht durch die Integration von Schlüssel-Wert-Paaren.

Datenstrukturen und Traversierungsverfahren

Um Graphen in ihrer Gesamtheit speichern zu können, braucht es spezielle Datenstrukturen. In Graphdatenbanken können Adjazenzmatrizen für stark vernetzte Graphen eingesetzt werden. Indizenzmatrizen eigenen sich für schwach vernetzte Graphen und Kantenlisten für große Graphen, da diese sehr gut skalieren können.

Um innerhalb der Graphdatenbank Informationen zu suchen, werden Traversierungsverfahren eingesetzt. Die gängigsten Verfahren sind hierbei die Tiefensuche, bei der zunächst die nächst tieferen Knoten besucht werden. Das zweite sehr bekannte Verfahren ist die Breitensuche, bei dieser werden zunächst alle Nachbarknoten einer Ebene durchsucht und anschließend die nächst tieferen Ebenen verwendet.

Weiterführende Artikel

Autor: Mandy
4 Bewertungen 1 Stern2 Sterne3 Sterne4 Sterne5 Sterne
Loading...
0