Wie kann man mit SQL-Mitteln in einem Graphen eine mögliche Route finden? Dieser Artikel zeigt, dass es verblüffend einfach sein kann und nur wenige Zeilen T-SQL benötigt werden.

"Suche Denkanstoß bzw. Lösung für folgende Aufgabenstellung"

So war das Posting in der Newsgroup bzw. zeitgleich im Forum überschrieben. Die Aufgabenstellung las sich dann erst mal relativ einfach und erste Ideen waren schnell gefunden. Aber das Beispiel hatte so seine Besonderheiten...

Aufgabenstellung

Gegeben war eine Liste von Routern, die teilweise miteinander verbunden sind und gesucht war die Route zwischen zwei Punkten. Die folgende Grafik soll dies verdeutlichen.

Die Verbindungen sind in einer Tabelle t_connection gespeichert.
CREATE TABLE t_connection (Start CHAR(1), Ziel CHAR(1)); INSERT INTO t_connection VALUES('A','B'); INSERT INTO t_connection VALUES('B','C'); INSERT INTO t_connection VALUES('B','D'); INSERT INTO t_connection VALUES('B','E'); INSERT INTO t_connection VALUES('C','F'); INSERT INTO t_connection VALUES('C','K'); INSERT INTO t_connection VALUES('E','F'); INSERT INTO t_connection VALUES('E','G'); INSERT INTO t_connection VALUES('G','K');

Schnell stellte sich dann heraus, dass die Definition als gerichteter Graph so eigentlich nicht sein konnte. Vielmehr war ein ungerichteter Graph gesucht, der zudem auch noch zyklisch ist.

Dies war nun relativ einfach durch ein UNION über die gedrehten Verbindungen zu erreichen:
SELECT Start, Ziel FROM t_Connection  UNION   SELECT Ziel AS Start, Start AS Ziel FROM t_connection;

Dieser Umstand, war nun auch die Ursache dafür, dass man dieses Problem nicht über eine CTE lösen konnte, da es zu einer unendlichen Rekursion kommt und das Abbruchkriterium schwierig zu definieren ist.
Siehe hierzu auch: Rekursive Abfragen mithilfe von allgemeinen Tabellenausdrücken

Verarbeitung

Der Trick besteht nun darin, sich eine Tabelle mit den möglichen Wegen zu definieren und diese sukzessive zu füllen. Hierbei wird nicht nur die Länge der Route mitgeführt (Hops), sondern neben Anfang und Endpunkt auch die komplette Route im Klartext. Diese Route wird dann entsprechend erweitert, wenn ein weiterer Verbindungspunkt hinzugefügt wird.
CREATE TABLE t_Wege ( Start      CHAR(1), Ziel       CHAR(1), Hops       INT, Route      VARCHAR(30) CONSTRAINT XPK_t_Wege PRIMARY KEY (Start, Ziel, Route) );
Da es zwischen zwei Punkten mehrere Routen geben kann, muss der Primary Key diese auch beinhalten.

Anschliessend wird eine View definiert, die alle Routen in der Tabelle t_Wege um einen weiteren Schritt aus der Tabelle t_Connection (bzw. der UNION-Abfrage darüber) ergänzt, falls der Endpunkt der Route als Startpunkt vorhanden ist. Damit dies nicht endlos so weitergeht, werden in einem Zyklus nur Routen abgespeichert, für deren Start und Ziel noch keine Routen existieren. Falls aber auf der gleichen Stufe zwei verschiedene Routen zwischen zwei Punkten gefunden werden, werden auch beide übernommen.
Die folgende Grafik zeigt die alternativen Routen zwischen den Punkten (C,E). Die rot markierte Route wird im folgenden Schritt nicht mehr berücksichtigt, da es bereits bessere Routen dazu gibt.

Initiale Befüllung

Zuerst werden alle Wege mit der Schrittweite 1 in der Tabelle hinterlegt. Bei 9 Verbindungen gibt dies 18 Wege, da sie ja in beiden Richtungen zu verwenden sind. Der Inhalt der Tabelle sieht dann wie folgt aus:

Start	Ziel	Hops	Route
A	B	1	A,B
B	A	1	B,A
B	C	1	B,C
B	D	1	B,D
B	E	1	B,E
usw.

Iterative Verarbeitung

Im folgenden werden in einer Schleife immer weitere und längere Wege in die Tabelle eingefügt, bis es keine neuen Wege mehr gibt, da es zu der gefundenen Kombination aus Start und Ziel bereits einen Weg gab. Hierzu werden die bereits vorhandenen Wege mit den möglichen Verbindungen (UNION über t_Connection) gejoined, die Anzahl der Hops um 1 erhöht und die Route um das Ziel aus der gefundenen neuen Verbindung erweitert.

Nach dem ersten Schleifendurchgang sind folgende Routen hinzugekommen:

Start	Ziel	Hops	Route
A	C	2	A,B,C
A	D	2	A,B,D
A	E	2	A,B,E
...
C	E	2	C,B,E
C	E	2	C,F,E
usw.

Entstanden sind diese Daten aus der Route (A,B) und den definierten Verbindungen von B, die nicht zu A zurückführen.
Die beiden (grünen) Routen (C,E) sind gleich lang und werden in der gleichen Iteration gefunden. Längere Routen zwischen (C,E) werden nicht mehr berücksichtigt, da es zu der Kombination (C,E) bereits Routen gibt.
INSERT INTO t_Wege (Start, Ziel, Hops, route)
       SELECT Start,Ziel,hops,route         FROM v_nexthop v        WHERE NOT EXISTS (SELECT * FROM t_Wege t WHERE t.Start = v.Start AND t.Ziel = v.Ziel);

Abschliessende Auswertung

Nachdem alle Routen bereitgestellt wurden, können diese einfach ausgewertet werden. In meinem Beispiel habe ich hierzu eine Tabelle mit den Parametern für Abfragen definiert, dies kann aber natürlich auch je nach Anforderung direkt in einer Prozedur über Parameter oder hart codiert im T-SQL erfolgen.

Zusammenfassung

Dieser Artikel zeigt wie man ein recht kniffliges Routenproblem mit wenigen aber mächtigen T-SQL-Befehlen lösen kann. Hier wurden keine unterschiedlichen Kosten für die Verbindungen berücksichtigt, was aber sicherlich noch eine Erweiterungsmöglichkeit wäre, die sich in der Tabelle t_Wege durch Addition der Einzelkosten ergeben könnte. Das Abbruchkriterium für die Suche wäre dann nicht das Vorhandensein einer Route, sondern Vorhandensein einer preiswerteren Route.
Abschliessend wäre eine grafische Darstellung der gefundenen Route anhand von Koordinaten wünschenswert. Die im Beispiel verwendete Dimensionierung der Felder ist für den Praxis-Einsatz zu gering. Für die Knoten und die Routen wird man sicher deutlich grössere Werte benötigen. Bei der Route sollte aber varchar(max) wohl selten gesprengt werden.

  Routerproblem.sql