Navigation in Graphen mit Oracle SQL

Pfadfinder
Kommentare

Wir alle sind schon häufiger über die Ecken und Kanten der Graphentheorie gestolpert, bewusst oder unbewusst. Ob wir ein „Navi“ benutzen, in einem Social Network die Freunde unserer Freunde besuchen, oder mit der Münchner U-Bahn von Hasenbergl nach Neuperlach-Süd fahren. Auch diesmal fragen wir einfach nach dem Weg

Die Problemstellungen der Graphentheorie und die damit verbundenen Algorithmen zählen schon zu den Klassikern der Programmierung. Ein typisches Beispiel ist die Suche nach dem kürzesten Pfad zwischen zwei Knoten eines Graphen, deren wohl bekannteste Lösung, der Dijkstra-Algorithmus, von seinem Namensgeber bereits 1959 veröffentlicht wurde. Er und weitere Algorithmenväter wie Bellman/Ford und Floyd/Warshall erdachten vor etwa 50 Jahren die Lösungswege, die wir heute als Standard verwenden. Alle diese Wege haben den imperativen Ansatz gemein. Sie lassen sich daher leicht in imperative Programmiersprachen wie Pascal, C(++) oder Java übersetzen. Im Gegensatz dazu beschreibt der deklarative Ansatz das Problem bzw. die gewünschte Lösung, ohne auf den Weg der Problemlösung einzugehen. Mit SQL als weitverbreitetem Vertreter der deklarativen Programmiersprachen fragen wir das Orakel von Redwood nach den gewünschten Wegen durch unseren Beispielgraphen (Abb. 1).

Abb. 1: Gerichteter und gewichteter Graph

Gerichtete Graphen in der Datenbank

Wir verwenden anfangs noch einen gerichteten Graphen, werden uns darauf aber nicht beschränken.  Um einen gerichteten und gewichteten Graphen in einer Oracle-Datenbank abzubilden, ist im einfachsten Fall nur eine einzige Tabelle notwendig. Sie enthält die Kanten des Graphen, definiert durch den Ausgangspunkt (Spalte Von), den Zielpunkt (Spalte Nach), und eine Gewichtung (Spalte Gewichtung). Auf eine weitere Tabelle mit den Eigenschaften der Knoten verzichten wir, da sie nichts zur Problemlösung beiträgt (Tabelle 1).

Die Menge der Kanten lässt sich mit einem einfachen

SELECT * FROM kanten

abfragen. Die Reihenfolge der Ausgabe ist ohne vorgegebene Sortierung zufällig und enthält keinerlei Aussage. (In diesem Fall ist es die Eingabereihenfolge einer neuen Tabelle, auf der keine weiteren Änderungen ausgeführt wurden. Aber auch darauf kann man sich nicht verlassen.) Die vollständigen Pfade dieses Graphen können wir aus der Kantenmenge nicht ohne Weiteres ablesen. Wir benötigen eine Möglichkeit, die Tabelle rekursiv zu durchsuchen, oder besser formuliert, durchsuchen zu lassen. Wir fragen nach dem Weg, nicht danach, wie er gefunden wird. Oracle SQL verfügt über eine spezielle Abfrageklausel für diese Problemstellungen, die connect by prior-Klausel. Mit dieser Klausel beschreiben wir, wie die in den Zeilen der Tabelle abgelegten Kanten zusammenhängen. Zusätzlich geben wir noch den Startknoten A an. Ohne diese Option werden alle möglichen Pfade von allen Knoten ausgehend zurückgeliefert, mit dieser Option alle von Knoten A ausgehenden Pfade.

SELECT *
FROM   kanten 
CONNECT BY PRIOR nach = von
START WITH von = 'A'

Die Abfrage verbindet die Zeilen der Tabelle über die Gleichsetzung der Spalte nach in der vorangehenden (prior) Zeile mit der Spalte von in der aktuellen Zeile, beginnend bei von =  ‚A‘, und liefert über die Sortierung der Zeilen die Pfade zurück (Tabelle 2).

Da wir bei von=‘A‘ beginnen, gibt es aus Sicht der ersten Zeile keine Vorgängerzeile. Aus Sicht von Zeile 2 entspricht der Wert in der Spalte Nach aus der vorangehenden Zeile dem Wert in der Spalte Von aus der aktuellen Zeile. Für einen Wert D in der Spalte Nach gibt es keinen Wert D in der Spalte Von irgendeiner Zeile, also ist mit D ein Endknoten erreicht, von dem keine weitere Kante mehr ausgeht.

Pfade von A zu D

Wir beginnen unsere Suche nach dem kürzesten Pfad von A zu D mit der Überprüfung, ob überhaupt Pfade zwischen den beiden Knoten existieren. Durch die Angabe von

START WITH von = 'A'

in der vorhergehenden Abfrage hatten wir Knoten A als Startpunkt aller Pfade festgelegt. Aus der damit erzeugten Treffermenge (Tabelle 2) filtern wir nun mit einer WHERE-Bedingung nur die Kanten heraus, die an Knoten D enden:

SELECT *
FROM   kanten 
WHERE nach = 'D'
CONNECT BY PRIOR nach = von
START WITH von = 'A'

Diese Abfrage liefert uns drei Treffer, also gibt es drei Verbindungen von A nach D (Tabelle 3).

Die kompletten drei Pfade von A nach D können wir uns über eine spezielle Funktion anzeigen lassen, die nur im Kontext von connect by prior funktioniert: sys_connect_by_path. Als Parameter geben wir an, welche Attribute der Kanten wir im Pfad sehen wollen, und das gewünschte Trennzeichen.

SELECT sys_connect_by_path(von||nach,'/') pfade
FROM   kanten 
WHERE  nach = 'D'
CONNECT BY PRIOR nach = von
START WITH von = 'A'

Diese Abfragen beweisen nicht, dass D der Endpunkt dieser Pfade ist, sondern nur, dass es drei Verbindungen zwischen A und D gibt (Tabelle 4). Die reine Anzahl der Verbindungen erhalten wir durch Abfrage der Funktion count(*) anstelle der Pfade:

SELECT count(*)
FROM   kanten 
WHERE  nach = 'D'
CONNECT BY PRIOR nach = von
START WITH von = 'A'

[ header = Kürzester Pfad nach Anzahl der Kanten ]

Kürzester Pfad nach Anzahl der Kanten

In einer Abfrage mit connect by prior steht uns zusätzlich die Pseudospalte level zur Verfügung, die uns zur Anzeige der Suchtiefe dient und damit auch die Anzahl der Kanten bis zum Ziel liefert:

SELECT level, von, nach, sys_connect_by_path(von||nach,'/') 
                               AS pfad 
FROM   kanten 
CONNECT BY PRIOR nach = von
START WITH von = 'A'

Unser Ziel ist Knoten D, also suchen wir uns aus dieser Ergebnismenge wieder die relevanten Zeilen heraus (Tabelle 5 und 6). Die Attribute Von und Nach den letzten Kanten des Pfads sind für die Ausgabe (nicht für die where-Bedingung) irrelevant und können hier entfallen:

SELECT level AS entfernung,
      sys_connect_by_path(von||nach,'/') AS pfad
FROM   kanten k
WHERE  nach = 'D'
CONNECT BY PRIOR nach = von
START WITH von = 'A'

Aus dieser Treffermenge suchen wir jetzt die Zeile und damit den Pfad mit der geringsten Entfernung zum Ziel. Dazu vergleichen wir die gelieferte Entfernung mit der minimalen Entfernung aus dieser Treffermenge. Die hierbei verwendete Schachtelung der Abfrage mit einer Unterabfrage auf dieselbe Tabelle ist ein Standardverfahren beispielsweise für die Suche in Tabellen mit historisierten Einträgen, um den letzten Eintrag für einen fachlichen Schlüssel zu erhalten (Listing 1, Tabelle 7).

SELECT level AS entfernung, sys_connect_by_path(von||nach,'/') AS pfad
FROM   kanten k
WHERE  nach = 'D'
AND    level = (SELECT min(level)
                FROM   kanten k
                WHERE  nach = 'D'
                CONNECT BY PRIOR nach = von
                START WITH von = 'A'
               )
CONNECT BY PRIOR nach = von
START WITH von = 'A'

Kürzester Pfad nach Gewichtung

Um den kürzesten Pfad zwischen den Knoten A und D nach Gewichtung der Kanten zu finden, müssen wir die einzelnen Kantengewichte nur addieren. Leider gibt es keine Funktion sys_connect_by_sonstwas oder Pseudospalte, die uns diese Arbeit abnimmt. Natürlich gibt es bei Oracle eine Summenfunktion, aber diese bezieht sich entweder auf alle Zeilen einer Tabelle, oder sie benötigt eine Gruppierung. Wir brauchen daher ein Gruppierungsmerkmal, das für alle Kanten eines Pfads identisch ist und jeden Pfad eindeutig kennzeichnet. Dazu benutzen wir die Pseudospalte Rownum, die alle Ergebniszeilen einer Abfrage durchnummeriert, die schon bekannte Pseudospalte Level, und die Funktion Lag. An dieser Stelle ist es wichtig, den deskriptiven Charakter einer SQL-Abfrage zu verstehen. Die Abfrage beschreibt das Ergebnis, und die Datenbank liefert das Ergebnis vollständig zurück. Es wird nicht eine Zeile nach der anderen zurückgeliefert, sondern eine Treffermenge. Auch wenn Ihr Client sich die Daten stückweise vom Server abholt, so stehen sie doch als logische Gesamtheit zur Verfügung. So wie Sie in Excel von jeder Zeile aus auf Zellen anderer Zeilen Bezug nehmen können, ist es mit den Oracle-SQL-Funktionen Lag und Lead auch möglich, von jeder Zeile aus auf die Vorgänger- und Nachfolgerzeilen zuzugreifen. Wir verwenden an dieser Stelle Lag, um Level-1 Zeilen und greifen dort auf die Rownum zu. So erhalten wir für jede in einer Zeile dargestellte Kante eines Pfads die Zeilennummer der ersten Kante. Damit haben wir für alle Kanten eines Pfads ein identisches Merkmal, nach dem wir anschließend gruppieren können (Listing 2, Tabelle 8).

SELECT rownum, level, von, nach, gew,
      LAG(rownum,level-1,0) OVER (ORDER BY rownum) AS pfadnr,
      sys_connect_by_path(von||nach,'/') pfad
FROM   kanten 
CONNECT BY PRIOR nach = von
START WITH von='A'

Jetzt gruppieren wir nach der künstlich erzeugten Pfadnr und addieren dabei die Gewichtung der Kanten entlang jedes Pfads (Tabelle 7). Durch Angabe der Filterbedingung WHERE  von != ‚D‘ stellen wir sicher, dass die Pfade nur bis Knoten ‘D’ ausgewertet werden, auch wenn das für diesen Beispielgraphen nicht nötig wäre, da Knoten D ein Endknoten ist. Der von sys_connect_by_prior gelieferte Pfad verlängert sich von Kante zu Kante, was uns praktischerweise erlaubt, mit max(pfad)  den vollständigen Pfad bis zum Ziel zu selektieren. Die having-Klausel stellt sicher, dass nur Pfade berücksichtigt werden, die an Knoten D enden (Listing 3, Tabelle 9).

SELECT count(*)  as anzahl_kanten
,      sum(gew)  as gesamtgewichtung
,      max(pfad) as pfad
FROM
(
  SELECT rownum, level, von, nach, gew
  , LAG(rownum,level-1,0) OVER (ORDER BY rownum) AS pfadnr
  , sys_connect_by_path(von||nach,'/') pfad
  FROM   kanten
  WHERE  von != 'D' 
  CONNECT BY PRIOR nach = von
  START WITH von='A'
)
GROUP BY pfadnr
HAVING substr(max(pfad),-1,1) = 'D'
ORDER BY pfadnr

Aus dieser übersichtlichen Treffermenge müssen wir nur noch die Zeile und damit den Pfad mit der geringsten Gesamtgewichtung heraussuchen, was unser SQL-Statement leider etwas unübersichtlicher macht (Tabelle 8). Wir verwenden dazu, wie beim kürzesten Pfad nach Anzahl der Kanten, eine weitere Schachtelung, um innen die geringste Gesamtgewichtung herauszusuchen und außen die Gesamtgewichtung mit der innen ermittelten geringsten Gesamtgewichtung gleichzusetzen. Wenn wir diese Abfrage auf einen Graphen anwenden, bei dem mehrere kürzeste Pfade mit gleicher Gesamtgewichtung existieren, werden alle kürzesten Pfade zurückgeliefert (Listing 4 und Tabelle 10).

SELECT anzahl_kanten, gewichtung, pfad
FROM
(
  SELECT count(*)  AS anzahl_kanten
  ,      sum(gew)  AS gewichtung
  ,      max(pfad) AS pfad
  FROM
  (
    SELECT rownum, level, von, nach, gew
    , LAG(rownum,level-1,0) OVER (ORDER BY rownum) AS pfadnr
    , sys_connect_by_path(von||nach,'/') AS pfad
    FROM   kanten
    WHERE  von != 'D' 
    CONNECT BY PRIOR nach = von
    START WITH von='A'
  )
  GROUP BY pfadnr
  HAVING substr(max(pfad),-1,1) = 'D'
  ORDER BY pfadnr
)
WHERE gewichtung = 
(
  SELECT min(gewichtung)
  FROM
  (
    SELECT count(*)  AS anzahl_kanten
    ,      sum(gew)  AS gewichtung
    ,      max(pfad) AS pfad
    FROM
    (
      SELECT rownum, level, von, nach, gew
      , LAG(rownum,level-1,0) OVER (ORDER BY rownum) AS pfadnr
      , sys_connect_by_path(von||nach,'/') pfad
      FROM   kanten
      WHERE  von != 'D' 
      CONNECT BY PRIOR nach = von
      START WITH von='A'
    )
    GROUP BY pfadnr
    HAVING substr(max(pfad),-1,1) = 'D'
    ORDER BY pfadnr
  )
)

Dieses kleine Monster-Statement ist nicht der eleganteste Weg zum Ziel. So wie man beim prozeduralen Programmieren eine mehrfach verwendete Programmlogik in eine Prozedur oder Funktion packt, verpacken wir die doppelt verwendete Abfragelogik in eine Vordefinition, was die Hauptlogik der Abfrage dann wieder sehr übersichtlich macht (Listing 5). Das Ergebnis dieser Abfrage finden Sie ebenfalls in Tabelle 10.

WITH pfadliste AS
(
  SELECT count(*)  AS anzahl_kanten,
      sum(gew)  AS gewichtung,
      max(pfad) AS pfad
  FROM
  (
    SELECT rownum, level, von, nach, gew
    , LAG(rownum,level-1,0) OVER (ORDER BY rownum) AS pfadnr
    , sys_connect_by_path(von||nach,'/') AS pfad
    FROM   kanten
    WHERE  von != 'D' 
    CONNECT BY PRIOR nach = von
    START WITH von='A'
  )
  GROUP BY pfadnr
  HAVING substr(max(pfad),-1,1) = 'D'
  ORDER BY pfadnr
)
SELECT anzahl_kanten, gewichtung, pfad
FROM pfadliste p1
WHERE gewichtung = (
                     SELECT min(gewichtung)
                     FROM pfadliste p2
                   ) 


[ header = Ungerichtete Graphen ]

Ungerichtete Graphen

In der Datenbank als Tabelle abgelegte gerichtete Graphen (Tabelle 1) lassen sich so nicht als ungerichtete Graphen verwenden. Es ist zwar möglich, alle Kanten in umgekehrter Richtung zu verwenden, wenn in der Abfrage die Spalten Von und Nach vertauscht werden und Knoten D als Startpunkt gewählt wird, aber einen Pfad von Knoten G zu Knoten E findet man damit nicht. Wir müssen den ungerichteten Graphen in einer Datenbanktabelle als symmetrischen (gerichteten) Graphen abbilden (Abb. 2).

Wir verwenden dazu die Tabelle kanten_s und füllen sie durch zweimaliges Lesen aus der Tabelle Kanten, einmal unverändert und einmal mit Vertauschung des Inhalts der Spalten Von und Nach:

CREATE TABLE kanten_symmetrisch AS
SELECT von, nach, gew FROM kanten
UNION ALL
SELECT nach, von, gew FROM kanten

In Kanten_symmetrisch haben wir jetzt für jede Kante eine Entsprechung in Gegenrichtung mit gleicher Gewichtung (Tabelle 11).

In diesem Graphen kann eine rekursive Suche natürlich endlos unterwegs sein. Oracle merkt das auch und quittiert unsere beim gerichteten Graphen verwendeten Statements mit einer Fehlermeldung. Wir fügen daher nach dem connect by noch das Schlüsselwort nocycle ein, und schon führt Oracle das Statement wieder aus – nur die Navigation ist weniger zielgerichtet. Neben den „vernünftigen“ Pfaden sind noch welche hinzugekommen, in denen die Suche an einer Anfangskante hin und wieder zurückverläuft, nur um anschließend woanders weiterzusuchen (Tabelle 12):

SELECT sys_connect_by_path(von||nach,'/') pfade
FROM   kanten_symmetrisch 
WHERE  nach = 'D'
CONNECT BY NOCYCLE PRIOR nach = von
START WITH von = 'A'

Wir können diese Pfade wieder ausblenden, indem wir den Ausgangsknoten des ersten Schritts mit dem Zielknoten des zweiten Schritts vergleichen (Listing 6 und Tabelle 13).

SELECT * FROM
(
  SELECT sys_connect_by_path(von||nach,'/') pfade
  FROM   kanten_symmetrisch 
  WHERE  nach = 'D'
  CONNECT BY NOCYCLE PRIOR nach = von
  START WITH von = 'A'
)
WHERE    substr(pfade,2,1) != substr(pfade,6,1)

Die Suche nach dem kürzesten Pfad, gemessen an der Anzahl der Sprünge, funktioniert auch im ungerichteten Graphen, mit nocycle als einziger Änderung. Wir suchen zur Abwechslung den kürzesten Pfad von Knoten G zu Knoten E, und erhalten zwei richtige Treffer (Listing 7, Tabelle 14).

SELECT level AS entfernung, sys_connect_by_path(von||nach,'/') AS pfad
FROM   kanten_symmetrisch k
WHERE  nach = 'E'
AND    level = (SELECT min(level)
                FROM   kanten_symmetrisch k
                WHERE  nach = 'E'
                CONNECT BY NOCYCLE PRIOR nach = von
                START WITH von = 'G'
               )
CONNECT BY NOCYCLE PRIOR nach = von
START WITH von = 'G'

Fazit

Die Erzeugung der Gruppierungsmerkmale als Voraussetzung für die kürzeste Suche nach Gewichtung funktioniert aufgrund der etwas umständlichen Navigation des connect by im ungerichteten Graphen nicht wie gehabt. Für diesen Teil der Suche werden wir die oben verwendete WITH-Klausel rekursiv einsetzen – zu einem späteren Zeitpunkt. Wenn Sie in der Münchner U-Bahn mit einem connect by prior nach dem Weg fragen, müssen Sie allerdings damit rechnen, dass Ihre Abfrage mit einem „Wos wuist?“ quittiert wird, der bayrischen Entsprechung für „ORA-0900: Ungültige SQL-Anweisung“.

Unsere Redaktion empfiehlt:

Relevante Beiträge

Meinungen zu diesem Beitrag

X
- Gib Deinen Standort ein -
- or -