Graphen
Zu Beginn dieses Abschnitts möchte ich Sie mit einigen wichtigen Begriffen vertraut machen, die in Zusammenhang mit Graphen benötigt werden, um über diese Datenstruktur unmissverständlich sprechen zu können.
Die Graphentheorie ist ein Teilgebiet der Mathematik, welches sich mit abstrakten Strukturen befasst, die als Graphen bezeichnet werden. Dabei handelt es sich nicht um Präsentationsgrafiken, wie sie beispielsweise mithilfe von Tabellenkalkulationen erstellt werden. In erster Annäherung ist ein Graph ein Diagramm aus Knoten (Nodes) und Kanten (Edges), die diese verbinden. Die Kanten können gerichtet oder ungerichtet sein. Den Kanten können Werte zugeordnet sein, wie Entfernungen zwischen zwei Orten oder die Kosten eines Produktionsprozesses. Wir bezeichnen dies Werte als Gewichte oder Kosten, unabhängig davon, welche Semantik ihnen konkret zukommt.
Ein gerichteter Graph modelliert einen „Fluss“ entlang der Kanten in der Richtung, in welcher diese verweisen. Bei einem ungerichteten Graphen ist der Fluss in beide Richtungen möglich.
Es gilt die Konvention, das eine Kante genau zwei Knoten miteinander verbindet. Dadurch kann eine Kante als geordnetes Knotenpaar, zum Beispiel (A, B), dargestellt werden, wenn diese Kante die Knoten A und B miteinander verbindet. In einem gerichteten Graphen wird so implizit auch die Richtung der Kante angegeben. (B, A) ist folglich ungleich (A, B). In einem gerichteten Graphen sind (A, B) und (B, A) dagegen identisch.
Ein Knoten kann alleinstehen, also keinerlei Verbindung zu anderen Knoten haben. Er kann aber ebenso beliebig viele Verbindungen zu anderen Knoten besitzen. Ein Knoten kann auch selbstreferenzierend sein, wie in (A, A).
Je nach Autor werden die verschiedenen Begriffe, die ich im Folgenden vorstelle, leicht unterschiedlich definiert. Je stärker dabei die Nähe zur Mathematik ist, umso differenzierter wird mit ihnen umgegangen. Für uns, in diesem Seminar, sollen folgende Begriffsdefinitionen gelten:
- Ordnung eines Graphen: Anzahl der Knoten im Graphen.
- Grad: Anzahl der Kanten an einem Knoten, unabhängig davon, ob der Graph gerichtet oder ungerichtet ist.
- Ausgangsgrad: Anzahl der Kanten, die in einem gerichteten Graphen einen Knoten verlassen.
- Eingangsgrad: Anzahl der Kanten, die in einem gerichteten Graphen in einen Knoten eingehen.
- Teilgraph: Ein Graph, der eine Teilmenge der Kanten und Knoten eines anderen Graphen ist.
- Weg: Ein Teilgraph aus sich abwechselnden Kanten und Knoten, die so miteinander verbunden sind, dass man sie ohne Unterbrechung ablaufen kann.
- Pfad: Ein Weg, der sich nicht selbst kreuzt. Es handelt sich um einen Sonderfall eines Weges.
- Zyklus: Ein Weg, der eine Schleife bildet.
- Verbundener Graph: Ein Graph, in dem alle Knotenpaare durch einen Pfad
Es gibt noch viele weitere Begriffe in der Graphentheorie, die sich zudem alle mittels mathematischer Formeln exakt beschreiben lassen. Ich verzichte hier sowohl auf weitere Begriffe zur Differenzierung spezieller Graphen als auch auf die mathematische Exaktheit. Mein Thema ist es, Graphen mit Hilfe von SQL zu modellieren und zu zeigen, welche Operationen auf Graphen mithilfe von SQL wie umgesetzt werden können.
Modellierung von Graphen
Es existieren verschiedene Möglichkeiten, Graphen in relationalen Datenbankmanagementsystemen zu modellieren. Die prominentesten Modellierungen sind:
- Adjacency List Model (Adjazenzlisten-Modell)
- Nested Sets (Verschachtelte Mengen)
- Enumerated Path Model (Enumerierte Pfade)
- Closure Tables
Closure Tables mit Schließtabellen zu übersetzen, klingt seltsam. Ich verzichte daher darauf.