Test Run

Graphbasierte Analyse des kürzesten Pfads mit SQL

James McCaffrey

In diesem Artikel erläutere ich, wie Sie eine graphbasierte Analyse des kürzesten Pfads implementieren, wenn die Graphdaten in einer SQL-Datenbank gespeichert sind und Sie die systemeigene T-SQL-Sprachverarbeitung verwenden möchten. Traditionelle Ansätze zur Berechnung des kürzesten Pfads setzen voraus, dass die Darstellung des Graphen in einer Datenstruktur im Arbeitsspeicher gespeichert ist. Aber umfangreiche Graphen, wie beispielsweise solche, die soziale Netzwerke darstellen, passen häufig nicht in den Arbeitsspeicher. Eine Möglichkeit ist daher, sie mithilfe von SQL zu speichern und zu verarbeiten. Um besser zu verstehen, worum es dabei geht, können Sie sich den Beispielgraphen in Abbildung 1 und den Screenshot einer Demoausführung in Abbildung 2 ansehen.

Abbildung 1: Beispielgraph für die Analyse des kürzesten Pfads

Abbildung 2: Analyse des kürzesten Pfads mit T-SQL

Der Graph in Abbildung 1 ist unnatürlich klein und hat acht Knoten (manchmal als Scheitel- oder Eckpunkte bezeichnet) mit den IDs 111 bis 888. Sie können sich vorstellen, dass die Knoten Personen oder Computer darstellen. Die Richtungspfeile (normalerweise als Kanten bezeichnet) zwischen den Knoten sind Beziehungen. Sie können sich vorstellen, dass ein Pfeil zwischen zwei Knoten einen E-Mail-Austausch darstellt. In diesem Beispiel haben die Kanten des Graphen Gewichtungen, die durch die Werte 1,0 und 2,0 angegeben werden. Kantengewichtungen können unterschiedliche Bedeutungen haben, die vom jeweiligen Problemszenario abhängen. Die Gewichtungen können beispielsweise ein Maß von sozialer Affinität darstellen oder einen Indikator für den Zeitpunkt, zu dem die Nachricht gesendet wurde.

Der Begriff des kürzesten Pfads kann verschiedene Bedeutungen haben. Angenommen, Sie möchten den kürzesten Pfad zwischen Benutzer 222 und Benutzer 444 wissen. Das könnte die kleinste Anzahl Hops sein, um von 222 zu 444 zu gelangen, nämlich 4 (von 222 zu 333 zu 666 zu 777 zu 444). Der kürzeste Pfad könnte aber auch die kleinste Summe an Gewichtungen zwischen 222 und 444 bedeuten, nämlich 5,0 (1,0 + 1,0 + 1,0 + 2,0).

In Abbildung 2 sehen Sie im Fenster links meine dbShortPathDemo-Datenbank in SQL Server Management Studio. Im Fenster oben rechts habe ich das T-SQL-Skript „ShortestPath.sql“, das die Demodatenbank definiert und mit Informationen auffüllt, die dem Graphen in Abbildung 1 entsprechen. Außerdem ist Code enthalten, der eine gespeicherte Prozedur namens „usp_ShortestPath“ definiert. Die gespeicherte Prozedur wurde gerade aufgerufen, um den kürzesten Pfad zwischen Benutzer 222 und Benutzer 444 zu analysieren. Im Fenster unten rechts sehen Sie die Ergebnisse. Der kürzeste Pfad wird in der Zeichenfolge „444;777;666;333;222“ angegeben. Der kürzeste Pfad, was die Gewichtung betrifft, ist 5,0 (wird ohne die Dezimalstelle angezeigt). Im unteren rechten Teil der Abbildung wird der endgültige Status der tblAlgorithmData-Tabelle angezeigt, die wichtig ist, um den Code für den kürzesten Pfad zu implementieren.

In den folgenden Abschnitten beschreibe ich schrittweise den T-SQL-Code, mit dem der Screenshot in Abbildung 2 erzeugt wurde, sodass Sie den Code für Ihre eigenen Problemszenarios anpassen können. Ich gehe dabei davon aus, dass Sie zwar hauptsächlich kein SQL-Entwickler sind, also am häufigsten C# oder eine andere prozedurale Programmiersprache verwenden, aber über grundlegende SQL-Kenntnisse verfügen. Ich zeige den gesamten T-SQL-Code, den ich in diesem Artikel erläutere.

Einrichten der Demodatenbank

Zum Erstellen einer Demodatenbank habe ich SQL Server Management Studio gestartet und eine Verbindung zu meinem Servercomputer hergestellt. Ich habe SQL Server 2008 verwendet, aber der hier dargestellte Code sollte mit geringen Änderungen mit den meisten früheren und allen neueren Versionen von SQL Server funktionieren. Nach dem Herstellen der Verbindung habe ich auf „Datei“ | „Neue Abfrage“ geklickt, um ein Bearbeitungsfenster zu öffnen, und dann T-SQL-Code eingegeben, um meine Dummydatenbank zu erstellen:

    use master
    go
    if exists(select * from sys.sysdatabases 
      where name='dbShortPathDemo')
    drop database dbShortPathDemo
    go
    create database dbShortPathDemo
    go
    use dbShortPathDemo
    go

Hier habe ich all die Standardparameterwerte für die create database-Anweisung verwendet. In vielen Szenarios werden Sie mit einer vorhandenen Datenbank mit echten Daten arbeiten, aber zum Experimentieren empfehle ich eine kleine Demodatenbank. Ich verwende zumeist T-SQL-Code in Kleinbuchstaben, was SQL-Puristen verärgern könnte. Ich habe diese neun Zeilen mit der Maus markiert und dann F5 gedrückt, um sie auszuführen. Nachdem ich geprüft habe, dass die Demodatenbank erstellt wurde, habe ich das Skript unter dem Namen „ShortestPath.sql“ gespeichert.

Zum Speichern der Daten, die den zu untersuchenden Graphen definieren, habe ich als Nächstes eine Tabelle in der Demodatenbank erstellt:

    create table tblGraph
    (
    fromNode bigint not null,
    toNode bigint not null,
    edgeWeight real not null
    )
    go

Ich habe nur diese sieben Zeilen mit der Maus markiert, um nicht die vorhergehenden Zeilen erneut auszuführen, und dann F5 gedrückt, um die Tabelle zu erstellen. Für die Knoten-IDs verwende ich den bigint-Typ. Zu den häufigen Knoten-ID-Typen, die auftreten können, zählen „int“ für eine relativ einfache Mitarbeiter-ID und „varchar(11)“ für eine Sozialversicherungsnummer im Format xxx-xx-xxxx. Für die edgeWeight-Spalte verwende ich den real-Typ. Der T-SQL-Typ „real“ ist einfach ein bequemer Alias für „float(24)“, der dem C#-Typ „double“ ähnelt. In vielen Szenarios haben Sie möglicherweise keine explizite Kantengewichtung zwischen den Knoten und können die edgeWeight-Spalte auslassen.

Ich habe als Nächstes diese 15 Codezeilen eingegeben, markiert und ausgeführt, um die tblGraph-Tabelle aufzufüllen:

    insert into tblGraph values(111,222,1.0)
    insert into tblGraph values(111,555,1.0)
    insert into tblGraph values(222,111,2.0)
    insert into tblGraph values(222,333,1.0)
    insert into tblGraph values(222,555,1.0)
    insert into tblGraph values(333,666,1.0)
    insert into tblGraph values(333,888,1.0)
    insert into tblGraph values(444,888,1.0)
    insert into tblGraph values(555,111,2.0)
    insert into tblGraph values(555,666,1.0)
    insert into tblGraph values(666,333,2.0)
    insert into tblGraph values(666,777,1.0)
    insert into tblGraph values(777,444,2.0)
    insert into tblGraph values(777,888,1.0)
    go

Wenn Sie Abbildung 1 vergleichen, sehen Sie, dass jede insert-Anweisung einem der Pfeile des Graphen entspricht.

Anschließend habe ich Indizes für die fromNode- und toNode-Spalten in der tblGraph-Tabelle erstellt, um die Leistung zu verbessern, wenn die gespeicherte Prozedur für den kürzesten Pfad auf die Graphdaten zugreift:

    create nonclustered index idxTblGraphFromNode on tblGraph(fromNode)
    go
    create nonclustered index idxTblGraphToNode on tblGraph(toNode)
    go
    I then created and populated a table to hold a list of unique node IDs:
    create table tblNodes
    (
    nodeID bigint primary key
    )
    go
    insert into tblNodes
    select distinct fromNode from tblGraph
    union
    select distinct toNode from tblGraph
    go

Eine Tabelle, die nur Knoten-IDs enthält, ist für die Analyse des kürzesten Pfads nicht erforderlich. Sie ist aber nützlich, wenn Sie eine Fehlerprüfung für die Start- und Endknoten-Eingabeparameter für die gespeicherte Prozedur des kürzesten Pfads ausführen möchten. Indem ich die primary key-Klausel auf die nodeID-Spalte anwende, erstelle ich implizit einen gruppierten Index für diese Spalte. Mit der union-Anweisung in SQL, verwendet mit zwei oder mehr select distinct-Anweisungen, nutze ich eine komfortable Möglichkeit, um eine Liste eindeutiger Werte aus einer Tabelle abzurufen.

Die Algorithmusdatentabelle

Die tblAlgorithmData-Datentabelle muss verstanden werden, um die gespeicherte Prozedur für den kürzesten Pfad zu verstehen und sie ändern zu können. Sie können die Tabelle erstellen, indem Sie die folgenden T-SQL-Anweisungen ausführen:

    create table tblAlgorithmData
    (
    nodeID bigint not null,
    dist real not null,
    pred bigint not null,
    inQueue bit not null
    )
    go
    create index idxTblAlgorithmDataNodeID on tblAlgorithmData(nodeID)
    create index idxTblAlgorithmDataDist on tblAlgorithmData(dist)
    create index idxTblAlgorithmDataPred on tblAlgorithmData(pred)
    create index idxTblAlgorithmDataInQueue on tblAlgorithmData(inQueue)
    go

Die Tabelle enthält (höchstens) eine Zeile für jeden eindeutigen Knoten im Graphen. Die Tabelle für das Beispiel in diesem Artikel enthält also (höchstens) acht Zeilen. Da „nodeID“ ein eindeutiger Bezeichner ist, hätte ich „nodeID“ als eine Primärschlüsselspalte definieren können. Die dist-Spalte ist die aktuelle Distanz vom Startknoten zu dem Knoten mit „nodeID“. Der dist-Wert ändert sich, während die gespeicherte Prozedur ausgeführt wird, enthält aber die endgültige Distanz, wenn die Prozedur abgeschlossen ist. In Abbildung 2 sehen Sie, dass der dist-Wert für Knoten 444, den Endknoten, nach Abschluss der gespeicherten Prozedur 5,0 Einheiten beträgt.

Die pred-Spalte enthält den unmittelbaren Vorgänger des Knotens mit dem nodeID-Bezeichner des kürzesten Pfads vom Parameter Startknoten zum Endknoten. In Abbildung 2 ist der Endknoten zum Beispiel 444. Dessen Vorgänger ist 777. Der Vorgänger von 777 ist 666. Der Vorgänger von 666 ist 333. Der Vorgänger von 333 ist 222, der Startknoten. Diese pred-Werte ergeben zusammen den kürzesten Pfad vom Endknoten zum Startknoten: 444 zu 777 zu 666 zu 333 zu 222. Der von mir verwendete Algorithmus ergibt nur einen kürzesten Pfad, auch in Situationen, in denen zwei oder mehr Pfade mit derselben kürzesten Gesamtdistanz vorhanden sind. In diesem Beispiel hat auch der Pfad 444 zu 777 zu 666 zu 555 zu 222 die Gesamtdistanz von 5,0 Einheiten.

Die inQueue-Spalte enthält einen bit-Wert (in funktioneller Hinsicht dem booleschen Typ in C# ähnlich), der angibt, ob der zugeordnete Knoten als Teil des kürzesten Pfads neu untersucht werden soll. Anders ausgedrückt, wenn der Wert von „inQueue“ 1 ist, muss der zugeordnete Knoten vom Algorithmus als Nachbar des derzeitigen Knotens im Algorithmus untersucht werden. Ist der Wert von „inQueue“ 0, muss der zugeordnete Knoten nicht als Nachbar untersucht werden. Der Spaltenname „inQueue“ ist ein wenig irreführend, da der Algorithmus keine explizite Warteschlange verwendet. Sie können vielleicht besser einen Namen wie „isActive“ verwenden. Ich verwende den Namen „inQueue“, da in prozeduralen Programmiersprachen für Implementierungen von Algorithmen des kürzesten Pfads häufig eine explizite Warteschlange verwendet wird und der Name daher in gewisser Hinsicht gebräuchlich ist.

Der Algorithmus

Der Algorithmus, den ich in diesem Artikel zeige, ist eine Variation vom Dijkstra-Algorithmus für den kürzesten Pfad. Abbildung 3 zeigt die verwendete Variation des Dijkstra-Algorithmus in Nicht-SQL-Pseudocode.

Abbildung 3: Algorithmus des kürzesten Pfads

set dist of startNode to 0.0
set pred of startNode to undefined
set inQueue of startNode to true
while there are any nodes with inQueue = true
  set u = node with smallest dist and inQueue = true
  if dist of u is infinity break
  if u = endNode break
  fetch all neighbors of u
  foreach neighbor v that has inQueue = true
    if v has not been seen before then
      set dist of v to infinity
      set pred of v to undefined
      set inQueue of v to true
    end if
  end foreach
  set inQueue of u = false
  foreach neighbor v of u
    if ((dist from startNode to u) + (dist from u to v) <
      curr dist to v) then
        set dist of v to (dist from startNode to u) + (dist from u to v)
        set pred of v to u
    end if
  end foreach
end while
if (u != endNode) then
  path from startNode to endNode is unreachable
else
  retrieve path using pred values
  shortest path distance = dist of endNode
end if

Der Dijkstra-Algorithmus ist einer der bekanntesten Algorithmen in den Computerwissenschaften, und Sie können dazu im Internet viele sehr detaillierte Erklärungen finden, aber nur wenige vollständige Implementierungen, die SQL verwenden. Der Algorithmus ist zwar kurz, aber sehr kompliziert. Um ihn vollständig zu verstehen, habe ich einige Beispiele mit Papier und Bleistift nachvollzogen. Das Wesentliche des Algorithmus ist, dass Sie an einem gegebenen Knoten u die aktuelle kürzeste Distanz vom Startknoten zu u kennen. Dann finden Sie alle Nachbarn von u. Für jeden Nachbarknoten v kennen Sie die aktuelle Distanz vom Startknoten zu v. Sie können die Distanz von u zu v nachsehen. Wenn die Distanz vom Start zu u plus die Distanz von u zu v kürzer ist als die Distanz vom Start zu v, wissen Sie, dass Sie einen kürzeren Pfad vom Start zu v gefunden haben. Die inQueue-Variable verhindert, dass der Algorithmus einen Knoten erneut aufsucht, sobald ermittelt wurde, dass ein erneutes Aufsuchen dieses Knoten keinen kürzeren Pfad ergibt.

Die gespeicherte Prozedur

Ich habe den kürzesten Pfad als gespeicherte T-SQL-Prozedur implementiert. Die Definition der gespeicherten Prozedur beginnt wie folgt:

    create procedure usp_ShortestPath
      @startNode bigint,
      @endNode bigint,
      @path varchar(5000) output,
      @totDist real output
    as
    begin
      ...

Ich versehe den Namen der gespeicherten Prozedur „usp_ShortestPath“ mit dem Präfix „usp“ (für benutzerdefinierte gespeicherte Prozedur, user-defined stored procedure), um die Prozedur von systemgespeicherten Prozeduren (system stored procedures, „sp“), erweiterten gespeicherten Prozeduren (extended stored procedures, „xp“) und gespeicherten CLR-Prozeduren (CLR stored procedures, „csp“) zu unterscheiden. Die @startNode- und @endNode-Parameter sind Eingabeparameter. Die gespeicherte Prozedur hat zwei Ergebnisausgabeparameter, „@path“ und „@totDist“. Für den @path-Parameter wurde willkürlich der varchar(5000)-Typ festgelegt. Je nach Typ der Knoten-ID, die Sie verwenden, und dem maximal erwarteten Pfad müssen Sie möglicherweise die Maximalgröße von 5000 erhöhen.

Als Nächstes initialisiere ich die tblAlgorithmData-Tabelle mit Informationen für den Startknoten:

    truncate table tblAlgorithmData
    insert into tblAlgorithmData
    values (@startNode, 0.0, -1, 1)
    ...

Die truncate-Anweisung löscht die Inhalte der tblAlgorithmData-Tabelle aus allen vorherigen Aufrufen von „usp_ShortestPath“. Wie bereits erwähnt, hat die tblAlgorithmData-Tabelle die Spalten „nodeID“, „dist“, „pred“ und „inQueue“. Die Distanz vom Startknoten zu sich selbst ist 0,0. Der Vorgänger vom Startknoten wird auf -1 gesetzt, um „undefined“ anzugeben, und das inQueue-Bit wird auf 1 gesetzt, um „true“ anzugeben.

Dieser Code setzt voraus, dass die tblAlgorithmData-Tabelle bereits in der aktuellen Datenbank als permanente Tabelle erstellt wurde. In manchen Situationen verfügen Sie möglicherweise nicht über die erforderlichen Sicherheitsberechtigungen zum Erstellen der Tabelle. In diesem Fall können Sie den entsprechenden Datenbankadministrator um die Erstellung bitten, oder Sie können „tblAgorithmData“ in der gespeicherten Prozedur als temporäre Tabelle oder möglicherweise Tabellenvariable erstellen.

Der Code setzt auch voraus, dass die @startNode- und @endNode-Werte gültig sind. Wenn Sie eine Tabelle mit allen Knoten-IDs haben, könnten Sie dies ungefähr folgendermaßen überprüfen:

    if not exists(select nodeID from tblNodes where @startNode = nodeID)
      // Error out in some way //

Ich bereite als nächsten Schritt die Hauptverarbeitungsschleife vor:

    declare @u bigint
    declare @d real = 0.0
    declare @done bit = 0
    while @done = 0
    begin
    ...

„@u“ ist hier die Knoten-ID des aktuellen Knotens im Algorithmus. Die Hilfsvariable „@d“ enthält die Distanz von „@startNode“ zum @u-Knoten (wie in „tblAlgorithmData“ gespeichert). Die @done-Variable ist eine Dummyvariable zur Schleifensteuerung. Sie sollten der Schleife weitere explizite Kriterien zum Beenden hinzufügen, beispielsweise eine maximale Anzahl Iterationen, eine maximale Anzahl Hops oder eine maximale Distanz für den gesamten Pfad.

In der Hauptverarbeitungsschleife ist der erste Schritt, den Wert von „@u“ zu ermitteln, der Knoten-ID des aktuellen Knotens. Das ist der Knoten mit dem kleinsten Wert in der dist-Spalte in „ tblAlgorithmData“ und mit „inQueue“=1:

    select top 1 @u = nodeID, @d = dist from tblAlgorithmData
    where inQueue = 1
    order by dist asc
    ...

An diesem Punkt prüft die gespeicherte Prozedur zwei Bedingungen zum Beenden der Schleife:

    if @d = 2147483647.0 break
    if @u = @endNode break
    ...

Wenn die Distanz vom Startknoten zu „@u“ (gespeichert in „@d“) gleich dem etwas rätselhaften Wert 2147483647,0 ist, heißt das, dass der Endknoten vom Startknoten aus nicht erreichbar ist. Der Wert 2147483647,0 steht für unendlich. Sie können einen beliebigen großen Wert verwenden, der nicht tatsächlich eine Distanz sein kann. Ich habe 2147483647,0 ausgewählt, da 2147483647 (ohne Dezimalstelle) der größte Wert für den SQL-Typ „int“ ist. Die andere Abbruchbedingung prüft einfach nur, ob der Endknoten erreicht wurde. Da der Algorithmus den Graphen zuerst der Breite nach durchsucht, wird der kürzeste Pfad gefunden, wenn der Endknoten erreicht wird.

Als Nächstes prüft die gespeicherte Prozedur alle Nachbarn des aktuellen @u-Knotens. Wurde ein Nachbar vorher nicht gesehen, wird er in „tblAlgorithmData“ initialisiert:

    insert into tblAlgorithmData
    select toNode, 2147483647.0, -1, 1 from tblGraph where fromNode = @u
    and not exists (select * from tblAlgorithmData where nodeID = toNode)
    ...

Dieser SQL-Code ist ein bisschen schwierig, falls Sie selten SQL-Code schreiben. Die insert-Anweisung hängt von der not exists-Anweisung ab, die durch „wenn die Nachbarknoten-ID (toNode-Wert) nicht bereits in ‚tblAlgorithmData‘ vorhanden ist (als ‚nodeID‘)“ interpretiert werden kann. Für jeden benachbarten Knoten, für den die Bedingung wahr ist, initialisiert die insert-Anweisung „tblAlgorithmData“ mit der „nodeID“ des Nachbarn, einem unendlichen Distanzwert (wie 2147483647,0), einem Vorgänger, der „undefined“ angibt (wie -1), und einem inQueue-Wert, der „true“ angibt (wie 1). Es kann ein schwieriges Paradigma sein, mit SQL-Anweisungen zu arbeiten, die für Datensätze ausgeführt werden, anstatt eine Auflistung mithilfe einer Schleife zu durchlaufen, wie Sie es in einer prozeduralen Programmiersprache tun würden.

In diesem Algorithmus werden die Knoten bei ihrem ersten Auftreten als Nachbarknoten initialisiert. Ein wichtiger alternativer Ansatz ist die Initialisierung aller Knoten des Graphen ganz am Anfang des Algorithmus. Das Problem dabei ist, dass es bei umfangreichen Graphen recht lange dauern kann, „tblAlgorithmData“ mit möglicherweise Millionen von Knoten aufzufüllen.

An dieser Stelle markiert die gespeicherte Prozedur den aktuellen Knoten als verarbeitet:

    update tblAlgorithmData set inQueue = 0
    where nodeID = @u
    ...

Als Nächstes überprüft die gespeicherte Prozedur jeden Nachbar des aktuellen Knoten darauf, ob ein neuer, kürzerer Pfad zum Nachbarn gefunden wurde. Wenn dies der Fall ist, aktualisiert die Prozedur die Einträge für diesen Nachbarknoten in „tblAlgorithmData“:

    update tblAlgorithmData
      set dist = @d + tblGraph.edgeWeight, pred = @u
      from tblAlgorithmData inner join tblGraph on 
        tblAlgorithmData.nodeID = tblGraph.toNode
      where tblGraph.fromNode = @u and tblAlgorithmData.inQueue = 1
        and (@d + tblGraph.edgeWeight) < tblAlgorithmData.dist
    end -- loop
    ...

Dies ist mit Abstand der schwierigste Teil der Implementierung des kürzesten Pfads. Die tblGraph-Tabelle wird mit „tblAlgorithmData“ verknüpft, sodass alle Daten in der update-Anweisung verwendet werden können. Die ID des aktuellen Knotens wird in „@u“ gespeichert, und dieser Wert wird „fromNode“ in „tblGraph“ zugeordnet. Die Nachbarn von „@u“ werden in „toNode“ in „tblGraph“ gespeichert und hierfür wird eine Verknüpfung mit „nodeID“ in „tblAlgorithmData“ hergestellt. Wie Sie sich erinnern, enthält „@d“ die Distanz vom Startknoten zum aktuellen @u-Knoten. Der Wert in der edgeWeight-Spalte enthält die Distanz von „@u“ zum Nachbarn. Die Summe dieser zwei Distanzen ist ein möglicher neuer kürzerer Pfad von der aktuellen Distanz vom Startknoten zum Nachbarn, die in der dist-Spalte gespeichert ist. Wenn eine neue kürzere Distanz gefunden wurde, wird die dist-Spalte mit dieser neuen kürzeren Distanz aktualisiert, und der Vorgänger des Nachbarknotens als „@u“ erfasst, der aktuelle Knoten. In Situationen, in denen Sie den kürzesten Pfad als die geringste Anzahl von Hops zwischen Start- und Endknoten definieren, ersetzen Sie „dist = @d + tblGraph.edgeWeight“ durch „dist = @d + 1“.

An dieser Stelle wurde die Hauptverarbeitungsschleife beendet, und der Grund für die Beendigung kann überprüft werden:

    if (@u != @endNode)
      begin
        set @path = 'NOT REACHABLE'
        set @totDist = -1.0
      end
      else
      begin
        set @path = ''
        declare @currNode bigint
        set @currNode = @endNode
      ...

Wenn der Wert in „@u“ die ID des Endknotens ist, wurde der Endknoten gefunden. Ist „@u“ irgendetwas anderes als die ID des Endknotens, wurde die Schleife beendet, bevor der Endknoten gefunden wurde. In diesem Fall lege ich für die Pfadzeichenfolge „NOT REACHABLE“ fest und ordne eine willkürliche Gesamtdistanz des kürzesten Pfads von -1,0 zu, um anzugeben, dass der Endknoten nicht erreichbar ist. Wenn der Endknoten tatsächlich gefunden wurde, initialisiere ich die Zeichenfolge für den kürzesten Pfad mit einer leeren Zeichenfolge, und ich richte die lokale @currNode-Variable dazu ein, „tblAlgorithmData“ zu durchlaufen, um die Zeichenfolge für den kürzesten Pfad zu erstellen.

Der Definitionscode der gespeicherten Prozedur endet mit dem Erstellen der Zeichenfolge für den kürzesten Pfad und dem Zuordnen der Gesamtdistanz für den kürzesten Pfad:

    ...
        while @currNode != @startNode
        begin
          set @path = @path + cast(@currNode as varchar(19)) + ';'
          set @currNode = (select pred from tblAlgorithmData 
            where nodeID = @currNode)
        end
        set @path = @path + cast(@startNode as varchar(19))
        select @totDist = dist from tblAlgorithmData 
          where nodeID = @endNode
      end -- else
    end -- usp_ShortestPath definition
    go

Hier verwende ich den T-SQL-Verkettungsoperator für Zeichenfolgen „+“. Ich verwende „varchar(19)“, da der größte mögliche Wert für den nodeID-Typ „bigint“ der Wert „9,223,372,036,854,775,807“ ist, der 19 Stellen hat.

Mit der erstellten gespeicherten Prozedur kann ich den kürzesten Pfad zwischen zwei beliebigen Knoten finden, zum Beispiel:

    declare @startNode bigint
    declare @endNode bigint
    declare @path varchar(5000)
    declare @totDist real
    set @startNode = 222
    set @endNode = 444
    exec usp_ShortestPath @startNode, @endNode, 
      @path output, @totDist output
    select @path
    select @totDist

Zusammenfassung

Da die Unternehmen mehr Daten sammeln und diese in einer Cloud-Umgebung speichern, wird die graphbasierte Analyse des kürzesten Pfads voraussichtlich immer wichtiger werden. Mit dem Code und der Erläuterung in diesem Artikel erhalten Sie eine solide Grundlage, um Analysen des kürzesten Pfads für Ihre Daten auszuführen. Eine wichtige Alternative zu dem hier beschriebenen Ansatz in systemeigener T-SQL-Sprache ist die Verwendung einer gespeicherten CLR-Prozedur. Meiner Erfahrung nach kann eine Analyse des kürzesten Pfads mithilfe einer gespeicherten CLR-Prozedur zu einer verbesserten Leistung führen, ist dabei aber komplexer. In einem zukünftigen Artikel gehe ich auf die graphbasierte Analyse des kürzesten Pfads mithilfe einer gespeicherten CLR-Prozedur ein.

Dr. James McCaffrey ist für Volt Information Sciences Inc. tätig. Er leitet technische Schulungen für Softwareentwickler, die auf dem Campus von Microsoft in Redmond, USA arbeiten. Er hat an verschiedenen Microsoft-Produkten mitgearbeitet, unter anderem an Internet Explorer und MSN Search. McCaffrey ist der Autor von „.NET Test Automation Recipes“ (Apress, 2006). Sie erreichen ihn unter jammc@microsoft.com.

Unser Dank gilt dem folgenden technischen Experten für die Durchsicht dieses Artikels: Shane Williams.