Dieser Artikel wurde maschinell übersetzt.

CLR

Graphbasierte Analyse des kürzesten Pfads mithilfe einer CLR-gespeicherten Prozedur

James McCaffrey

Graph-Analyse wird in Software-Anwendungen immer wichtiger.Hier ist ein Diagramm, eine Auflistung von Knoten und Kanten, kein Daten-Visualisierung wie z. B. ein Balkendiagramm.Dieser Artikel stellt eine Demonstration der kürzeste Pfad-Analyse mithilfe einer gespeicherten SQL-CLR-Prozedur durchführen.Die hier vorgestellten Techniken können auch für viele andere Daten-Access-Programmierung-Aufgaben verwendet werden.

Shortest-Path-Graph-Analyse umfasst wirklich zwei eng miteinander verbundene Probleme.Der erste ist den kürzesten Pfad von einem Startknoten angegebene Diagramm zu einem Endknoten in Bezug auf die Anzahl der Hops zu bestimmen.Das zweite Problem ist die Bestimmung die Länge des kürzesten Pfads Graph Verbindungen eine Art Gewicht besitzen.Nehmen wir beispielsweise an die Knoten in einem Graphen stellen Menschen und die Kanten zwischen den Knoten dar eine E-mail-Kommunikation.Sie könnte die kürzeste Anzahl der Hops zwischen zwei Menschen interessieren wo Sie implizit angenommen sind, dass jedem Hop hat ein Gewicht von 1.Dies ist vergleichbar mit dem "six Degrees of Kevin Bacon"-Spiel oder die Erdös-Nummer für Forscher.Wenn jede Kante des Graphen eine Gewicht hat — z. B., eine gewisse Bedeutung einer Beziehung darstellt — vielleicht möchten Sie den kürzesten Weg zwischen zwei Menschen, die dabei die Bedeutung der Gewicht Rechnung zu bestimmen.

Aber warum verwenden eine gespeicherte CLR-Prozedur?Traditionelle shortest-Path-Algorithmen wird davon ausgegangen, dass die Problem-Diagramm-Darstellung komplett Maschine, in der Regel in einer Matrix oder Nachbarschaft Liste gespeichert werden kann.Für große Grafiken — z. B. Diagramme, die soziale Netzwerke darstellt – dieser Ansatz ist oft nicht möglich.Große Graphen können bequem in einer SQL-Datenbank gespeichert werden.Ein Ansatz für shortest-Path Analysen von Graphen, die in einer SQL-Datenbank gespeichert ist, eine systemeigene SQL Sprache gespeichert Prozedur zu schreiben.Das MSDN Magazine Artikel, "Graph-basierten Shortest-Path Analysis mit SQL" (msdn.microsoft.com/magazine/jj863138), wird dieser Ansatz im Detail erläutert.Allerdings kann mithilfe einer CLR gespeicherte Prozedur anstelle von einem reinen SQL-Ansatz erheblich bessere Leistung und viel Flexibilität für die Anpassung bieten.

Schauen Sie sich die Pseudo-Grafik-Darstellung in Abbildung 1.Der Graph hat acht Knoten.Die Zahlen neben jedem Pfeil darstellen eine Gewicht.Ist der kürzeste Weg zwischen 222 und Knoten 444 222 -> 555 -> 666 -> 777 -> 444, die eine gewichtete Entfernung 1.0 + 1.0 + 1.0 + 2.0 = 5.0 hat.Beachten Sie, dass 222 -> 333 -> 666 -> 777 -> 444 ist auch der kürzeste Pfad von 222 auf 444.

Abbildung 1: Dummy-Grafik für Shortest-Path Analysis

Abbildung 2 zeigt ein Screenshot eines Aufrufs eine CLR gespeicherte Prozedur mit dem Namen Csp_ShortestPath, die den kürzesten Weg zwischen 222 und Knoten 444 bestimmt.In diesem Fall ist der kürzeste Pfad als eine durch Semikolons getrennte Zeichenfolge in umgekehrter Reihenfolge angezeigt.Die Ausgabe ist am unteren Rand des Bildes.Der obere Teil des Bildes enthält SQL-Anweisungen zum Erstellen von einem Diagramm entspricht in Abbildung 1.

Abbildung 2 aufrufen eine Shortest-Path/CLR gespeicherte Prozedur

Dieser Artikel setzt voraus, dass Sie c# Programmierkenntnisse und grundlegende Kenntnisse SQL erweitert haben.Präsentiere ich den SQL-Code um das Dummy-Diagramm zu erstellen und alle der c#-Code zum Erstellen der CLR gespeicherte Prozedur, und ich auch beschreiben verschiedene Möglichkeiten zum Aufrufen der gespeicherten CLR-Prozedur.Der Code für diesen Artikel ist abrufbar unter archive.msdn.microsoft.com/mag201305Graph.

Erstellen der Datenbank

Um das Dummy-SQL-basierten Diagramm zu erstellen, ich Microsoft SQL Server Management Studio (SSMS) gestartet und mit einer Instanz von einer SQL Server 2008-Datenbank verbunden.CLR-gespeicherte Prozeduren werden unterstützt durch SQL Server 2005 und höher.Zuerst habe ich eine Datenbank namens DbShortPathWithCLR mit den folgenden Befehlen:

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

Ich empfehle das Experimentieren mit einer Dummy-Datenbank nicht mit einer Produktionsdatenbank. Die Befehle zum Erstellen einer Tabelle, die Knoten und Edge-Daten enthalten sind:

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

Knoten-IDs werden als SQL Datentyp Bigint, gespeichert, etwa c# Typ long entspricht. Die Rand-Gewichte werden als Datentyp real, gespeichert, die ein Synonym für SQL-Typ float(24), die etwa c# Typ double entspricht. In vielen Situationen werden Sie nicht mit einem Rand-Gewicht und die EdgeWeight-Spalte kann weggelassen werden.

Die 14-Anweisungen in Abbildung 3 definieren Sie das Diagramm.

Abbildung 3 definieren das Diagramm

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

Vergleicht man die Anweisungen im Abbildung 3 mit dem Bild in Abbildung 1 du wirst sehen, dass jede Anweisung eine Kante zwischen Knoten entspricht.

Als nächstes ist die Datenbank für Analyse des kürzesten Wegs vorbereitet:

create nonclustered index idxTblGraphFromNode 
  on tblGraph(fromNode)
go
create nonclustered index idxTblGraphToNode 
  on tblGraph(toNode)
go
create nonclustered index idxTblGraphEdgeWeight 
  on tblGraph(edgeWeight)
go
alter database dbShortPathWithCLR set trustworthy on 
go
select is_trustworthy_on from sys.databases
  where name = 'dbShortPathWithCLR'
go

Die ersten drei Anweisungen erstellen Indizes Spalten FromNode, ToNode und EdgeWeight. Indizes sind fast immer notwendig, um angemessene Leistung geben, bei der Arbeit mit großen Graphen. Die nächsten beiden Anweisungen ändern Sie die Datenbank so dass die trustworthy-Eigenschaft auf "on" festgelegt ist Der Standardwert der Eigenschaft ist "aus." Ich werde erklären, warum die trustworthy-Eigenschaft kurz auf "on" festgelegt sein muss.

An dieser Stelle wird das Dummy-SQL-basierten Diagramm erstellt. Der nächste Schritt ist, mithilfe von Visual Studio erstellt eine CLR gespeicherte Prozedur um shortest-Path-Analyse durchzuführen.

Erstellen der CLR-gespeicherten Prozedur

Um die CLR shortest-Path gespeicherte Prozedur zu erstellen, startete ich Visual Studio 2010. CLR Erstellen gespeicherter Prozeduren, die Ihre Entwicklungsumgebung umfaßt die Microsoft .NET Framework 3.5 oder höher. Aus der Datei | Neu | Im Projektmenü wählte ich die Datenbank | SQL Server Projektgruppe Vorlage und dann die Visual c# SQL CLR-Datenbankprojekt-Option gewählt, wie in Abbildung 4. Ich nannte das Projekt CreateStoredProc.

Abbildung 4 neue CLR-Projekt in Visual Studio 2010

Beachten Sie, dass das .NET Framework 3.5 in der neues Projekt Dialogfeld Dropdown-Steuerelement ausgewählt ist. Die Version von Framework zum Ziel muss die Version des Frameworks auf dem SQL Server hostet die Datenbank übereinstimmen. Da die Pseudo-Datenbank auf eine Instanz von SQL Server 2008 ist, gezielt ich .NET Framework 3.5. Wenn die Pseudo-Datenbank auf eine Instanz von SQL Server 2005 gewesen wäre, würde ich .NET Framework 2.0 gezielt habe. Die gespeicherten CLR-Prozedur-Dokumentation ist ein bisschen trübe beschreibt die Zusammenhänge zwischen der Framework-Versionen auf der Entwicklungsumgebung auf dem SQL Server und c# gespeicherte Prozedur erstellen Projekt. Sie möglicherweise ein bisschen von Versuch und Irrtum zurückzugreifen.

Klicken Sie auf OK, um das CLR-Prozedur-Erstellung-Projekt erstellen, Visual Studio werden aufgefordert, mit der Bitte um Informationen zum Namen und Authentifizierung Modell der Zieldatenbank (siehe Abbildung 5). Nach dem Klicken auf OK im Dialogfeld neue Datenbank-Referenz, Visual Studio lädt ein neues Projekt aber nicht direkt eine Vorlage erstellen. Um eine Vorlage zu erzeugen, der rechten Maustaste auf den Projektnamen — CreateStoredProc in diesem Fall — und wählen Sie hinzufügen | Neuheit aus dem Kontextmenü (siehe Abbildung 6).

Abbildung 5 neue Datenbank Referenz für das Projekt

Abbildung 6 neue gespeicherte Element Prozedur

Das gespeicherte Prozedur-Element ausgewählt, und nannte sie csp_ShortestPath.cs. Dieser Name, ohne die Erweiterung CS werden die Namen der gespeicherten Prozedur in der Zieldatenbank. Als eine Frage des Stils voranstellen ich generell gespeicherten CLR-Prozedur-Namen mit Csp, um sie von gespeicherten Systemprozeduren (sp), erweiterte gespeicherte Prozeduren (Xp) und benutzerdefinierte gespeicherte Prozeduren (Usp) zu unterscheiden. Nach dem Klicken auf die Schaltfläche hinzufügen, generiert Visual Studio eine leichte Vorlage einer partiellen Klasse mit dem Namen gespeicherten Prozeduren:

using System;
using System.Data;
using System.Data.SqlClient;
using System.Data.SqlTypes;
using Microsoft.SqlServer.Server;
public partial class StoredProcedures
{
  [Microsoft.SqlServer.Server.SqlProcedure]
  public static void csp_ShortestPath()
  {
    // Put your code here
  }
};

Ein armer Mann Vorrangwarteschlange

In diesem Artikel vorgestellten shortest-Path-Algorithmus erfordert eine random-Access-Priorität Warteschlange-Datenstruktur. .NET Framework liefern keine eingebauten priorisierten Warteschlange, die genau die Bedürfnissen des shortest-Path-Algorithmus gerecht werden, so dass Sie Ihre eigenen Vorrangwarteschlange code müssen.

Eine Priority-Queue ist vergleichbar mit einer normalen First in First Out (FIFO) Warteschlange mit ein paar unterschieden. Die Elemente in einer priorisierten Warteschlange werden angenommen, dass man irgendeine Art von Feld "Priority" neben einem Datenfeld. Beispielsweise kann ein Warteschlangenelement Priorität für eine Gruppe von Kunden technischen Support warten bestehen, der Name des Kunden und die Länge der Zeit, die der Kunde für den Dienst gewartet hat.

Priority-Queues unterstützen eine Dequeue-Operation, die immer das Element mit der höchsten Priorität entfernt. Hier die Bedeutung der höchsten hängt vom Problem-Kontext und kann eine größten oder kleinsten Wert. Ein random-Access-Vorrangwarteschlange unterstützt eine Operation, die ändert die Priorität eines Elements mit der angegebenen ID.

Dieser Artikel stellt ein armer Mann Vorrangwarteschlange — einer, der bekommt des Job zu erledigen, aber viel Raum für Verbesserungen. Der shortest-Path-Algorithmus arbeitet auf einer priorisierten Warteschlange, wo Elemente in der Warteschlange zwei Felder haben: eine Knoten-ID (z. B. 111 oder 222) und ein Feld Abstand. Distanz-Feld wird vom Algorithmus verwendet, um die besten (kürzeste) bekannte Entfernung zwischen dem Start und der Element-Knoten zu einem bestimmten Zeitpunkt während der Ausführung des Algorithmus zu speichern. Feld Abstand fungiert als das Element Vorrang, und kleinere Werte für Abstand höheren Priorität.

Also, um eine random-Access-Priority-Queue zu unterstützen, die c#-Vorlage gespeicherte Prozedur benötigt eine zusätzliche using-Anweisung, die der System.Collections.Generic-Namespace und zwei zusätzliche Programm definierten Klassendefinitionen verweist unterhalb der StoredProcedures Teilklasse platziert:

public class NodeDistance
{
  // Definition here
}
public class MyPriorityQueue
{
  // Definition here
}
Class NodeDistance is simple:
public class NodeDistance
{
  public long nodeID;
  public double distance;
  public NodeDistance(long nodeID, double distance)
  {
    this.nodeID = nodeID;
    this.distance = distance;
  }
}

Ich benutze öffentlichen Bereich für die Klassenfelder für Einfachheit. Die Priority-Queue ist im Wesentlichen eine Liste von NodeDistance-Elementen:

public class MyPriorityQueue
{
  public List<NodeDistance> list;
  public MyPriorityQueue()
  {
    this.list = new List<NodeDistance>();
  }

Auch hier verwende ich öffentlichen Bereich nur der Einfachheit. Die Dequeue-Operation entfernt das NodeDistance-Element mit dem kleinsten Abstandwert:

public NodeDistance Dequeue()
{
  int i = IndexOfSmallestDist();
  NodeDistance result = this.list[i];
  this.list.RemoveAt(i);
  return result;
}

Dequeue-Methode ruft eine Hilfsmethode um den Speicherort des Elements zu suchen, das ist der kleinsten Abstand, speichert einen Verweis auf das Element und dann die integrierte List.RemoveAt-Methode verwendet, um das Element zu entfernen.

Hilfsmethode IndexOfSmallestDist ist definiert als:

private int IndexOfSmallestDist() {
  double smallDist = this.list[0].distance;
  int smallIndex = 0;
  for (int i = 0; i < list.Count; ++i) {
    if (list[i].distance < smallDist) {
      smallDist = list[i].distance;
      smallIndex = i;
    }
  }
  return smallIndex;
}

Die Methode hat eine einfache lineare Suche durch die zugrunde liegende Liste-Auflistung. Beachten Sie, dass dieser Ansatz bedeutet, dass Dequeue O(n) Leistung hat.

Der Enqueue-Vorgang wird folgendermaßen definiert:

public void Enqueue(NodeDistance nd)
{
  list.Add(nd);
}

Der Änderungspriorität Vorgang wird folgendermaßen definiert:

public void ChangePriority(long nodeID, double newDist)
{
  int i = IndexOf(nodeID);
  list[i].distance = newDist;
}

Methode ChangePriority Ruft Hilfsmethode IndexOf, die die Position des ein NodeDistance Element, da die Element-ID sucht und ist definiert als:

private int IndexOf(long nodeID)
{
  for (int i = 0; i < list.Count; ++i)
    if (list[i].nodeID == nodeID)
      return i;
  return -1;
}

Auch beachten Sie, dass da die IndexOf-Methode eine lineare Suche durchführt, seine Leistung o (n ist).

Der kürzeste Pfad-Algorithmus muss die Anzahl der Elemente in der Prioritätswarteschlange zu jedem Zeitpunkt zu wissen:

public int Count()
{
  return this.list.Count;
}

Um zusammenzufassen, des armen Mannes Direktzugriff Priorität unterstützt Warteschlange definiert hier eine Enqueue-Operation; eine Count-Eigenschaft; eine Dequeue-Operation, die das NodeDistance-Element mit dem kleinsten Abstand entfernt; und eine ChangePriority-Operation, die die Entfernung eines angegebenen Elements ändert. Operationen Dequeue und ChangePriority haben eine o (n) Leistung.

Für große Grafiken ist die Leistung des shortest-Path Algorithmus stark abhängig von der Effizienz der die Priority-Queue verwendet. Während O(n) Leistung oft akzeptabel ist, ist es möglich eine Prioritätswarteschlange implementiert wird, die wesentlich leistungsfähiger ist O (Log n) hat. Solche Implementierungen in der Regel verwenden Sie eine binäre Heaps-Datenstruktur und sind ziemlich schwierig. Ich beschreibe eine effiziente Vorrangwarteschlange in meine Visual Studio Magazine-Artikel "Priority Queues mit c#" abrufbar unter bit.ly/QWU1Hv.

Erstellen der gespeicherten Prozedur

Mit der benutzerdefinierten Vorrangwarteschlange definiert kann der Algorithmus shortest-Path implementiert werden. Ist die Methodensignatur ist:

public static void csp_ShortestPath(System.Data.SqlTypes.SqlInt64
  startNode, SqlInt64 endNode, SqlInt32 maxNodesToCheck,
  out SqlString pathResult, out SqlDouble distResult)
{

Methode Csp_ShortestPath drei Eingabeparameter akzeptiert und hat zwei out-Ergebnis-Parameter. Parameter StartNode hält die Knoten-ID des Knotens auf der Suche zu beginnen. Daran erinnern Sie, dass in der Definition der SQL-Tabelle Spalten FromNode und ToNode als SQL Datentyp Bigint, definiert sind, lange c# Datentyp entspricht. Beim Definieren einer CLR-Prozedur, verwenden die Prozedurparameter ein Modell im System.Data.SqlTypes-Namespace definiert. Diese Typen sind in der Regel ziemlich leicht zu SQL und c# Typen zuordnen. Hier geben Sie Bigint Karten in SqlInt64. Input-Parameter EndNode ist auch erklärt, wie SqlInt64 zu geben.

Input-Parameter MaxNodesToCheck wird verwendet, um die gespeicherte Prozedur von Spinnen außer Kontrolle auf extrem großen Graphen zu verhindern. Hier MaxNodesToCheck als Typ SqlInt32, deklariert ist, entspricht in c# Datentyp int.

Wenn Sie neu gespeicherte SQL-Prozeduren sind, sind Sie möglicherweise überrascht zu erfahren, dass sie keine explizite Rückgabewert verfügen können, oder können einen Int-Wert zurückgeben, aber sie können nicht ausdrücklich einem anderen Datentyp zurückgeben. Also in Situationen, wo eine Prozedur SQL gespeicherte, müssen zwei oder mehrere Werte zurückgeben, oder eines Wertes zurückgeben, das ein Int-Typ ist, ist der Ansatz, out-Parameter zu verwenden. Hier wird die gespeicherten CLR-Prozedur den kürzesten Pfad als Zeichenfolge, wie z. B. "444; 777 666; 333; 222," und auch die totale Entfernung des kürzesten Pfads als numerischer Wert, z. B. 5.0 gibt. Also out-Parameter PathResult als SqlString Typ und out-Parameter DistResult deklariert ist als Sql-Typ­Double, c#-Typen String und Double, entspricht.

Die Definition die gespeicherten CLR-Prozedur weiter durch die Einrichtung von vier Datenstrukturen:

Dictionary<long, double> distance = new Dictionary<long, double>();
Dictionary<long, long> previous = new Dictionary<long, long>();
Dictionary<long, bool> beenAdded = new Dictionary<long, bool>();
MyPriorityQueue PQ = new MyPriorityQueue();

Wie der shortest-Path-Algorithmus, zu einem bestimmten Zeitpunkt führt muss der Algorithmus die aktuelle beste (kürzeste) bekannte Gesamtstrecke vom Startknoten zu allen anderen Knoten zugreifen. Die Dictionary-Auflistung mit dem Namen "Distanz" hält diese Informationen. Das Wörterbuchschlüssel ist eine Knoten-ID und der Wörterbuch-Wert ist die kürzeste bekannte Gesamtstrecke. Die SlovoEd-Wörterbuchsammlung benannt "vorherige" speichert die unmittelbaren Vorgänger-Knoten-ID einer wichtigen Knoten-ID in den kürzesten Weg. Z. B. in dem Beispiel in Abbildung 2, der Endknoten ist 444. Seine unmittelbaren Vorgänger in den kürzesten Pfad ist 777. Also zurück [444] = 777. Im Wesentlichen umfasst die frühere Kollektion den kürzesten Pfad in codierter Form.

Die Dictionary-Auflistung mit dem Namen "BeenAdded" enthält Informationen, die angibt, ob der Algorithmus Vorrangwarteschlange ein Graphknoten hinzugefügt wurde. Der boolesche Wert ist ein Dummy-Wert, denn es ist nicht wirklich notwendig, um festzustellen, ob ein Knoten in der Auflistung ist. Vielleicht möchten eine Hashtable anstelle einer Wörterbuchauflistung verwenden. Die benutzerdefinierte Priority-Queue mit dem Namen "PQ" wurde definiert und im vorherigen Abschnitt dieses Artikels erklärt.

Definition die gespeicherten Prozedur fährt fort:

SqlConnection conn = null;
long startNodeAsLong = (long)startNode;
long endNodeAsLong = (long)endNode;
int maxNodesToCheckAsInt = (int)maxNodesToCheck;

Das SqlConnection-Objekt ist die einzige Verbindung in die Zieldatenbank Graph. Ich erkläre es hier, so dass ich später seinen Zustand überprüfen können, wenn eine Ausnahme auftritt. Obwohl nicht unbedingt erforderlich, beim Schreiben von CLR ich bevorzuge explizit lokalen c# Erstellen gespeicherter Prozeduren eingegeben typisierte Variablen, die die SQL-Anweisungen entsprechen, Parametervariablen.

Die Definition geht weiter:

distance[startNodeAsLong] = 0.0;
previous[startNodeAsLong] = -1;
PQ.Enqueue(new NodeDistance(startNodeAsLong, 0.0));
beenAdded[startNodeAsLong] = true;

Diese Zeilen Code initialisieren den Startknoten. Der Wert in der Ferne Wörterbuch wird auf 0,0 festgelegt, da die Entfernung vom Startknoten zum selbst NULL ist. Der unmittelbare Vorgänger der Startknoten existiert nicht, so dass ein Wert von-1 verwendet wird, um dies anzugeben. Die Priority-Queue wird mit Startknoten initialisiert, und die BeenAdded-SlovoEd-Wörterbuchsammlung wird aktualisiert.

Die Definition geht weiter:

try
{
  string connString = "Server=(local);Database=dbShortPathWithCLR;" +
    "Trusted_Connection=True;MultipleActiveResultSets=True";
  conn = new SqlConnection(connString);
  conn.Open();
  double alt = 0.0;  // 'Test distance'

Beim Schreiben von CLR-Prozeduren gespeicherte ich bevorzuge explizite Try-Catch-Blöcke eher als die elegantere using-Anweisung. Beim Einrichten der Verbindungszeichenfolge haben Sie zwei Möglichkeiten. In vielen Fällen, da die gespeicherte Prozedur, auf dem gleichen Computer wie die SQL-Datenbank ausgeführt wird, können Sie einfach die Verbindungszeichenfolge auf festlegen "Context Connection = True." Eine Kontextverbindung theoretisch liefern bessere Leistung als eine Standardverbindung. Eine Kontextverbindung hat jedoch einige Einschränkungen. Eine Einschränkung ist, dass es nur einen einzigen SQL-Datenleser unterstützen kann. Wie Sie bald sehen werden, erfordert shortest-Path-Analyse oft (aber nicht immer) zwei SQL-Daten-Leser.

Da diese gespeicherten CLR-Prozedur zwei Leser erfordert, wird eine standard-Verbindungszeichenfolge, die eine Klausel enthält, die die MultipleActiveResultSets-Eigenschaft auf True verwendet. Diese Klausel wird derzeit von SQL-Kontext-Verbindungen nicht unterstützt. Da die gespeicherte Prozedur eine Standardverbindung, anstatt eine Kontextverbindung verwendet wird, die Datenbank-Berechtigungsstufe für das Visual Studio die gespeicherte Prozedur erstellen Projekt festgelegt werden müssen extern, wie in Abbildung 7. Um diese Eigenschaft legen Sie die SQL Datenbank müssen jedoch ihre vertrauenswürdige-Eigenschaft auf "on", wie gezeigt in Abbildung 2.

Abbildung 7 einstellen-Database-Berechtigung Stufe

Um zusammenzufassen, wenn die Graph-Datenbank erstellen, wird die Datenbankeigenschaft trustworthy auf "on" festgelegt. Dadurch wird das Visual Studio -Projekt Datenbank Berechtigungsstufe zu externen festzulegende Eigenschaft. Dies ermöglicht die Definition die gespeicherten Prozedur eine Standardverbindung anstelle einer Kontextverbindung verwendet. Dadurch die Verbindung MultipleActiveResultSets festzulegende Eigenschaft auf true fest. Und auf diese Weise können zwei SQL-Daten-Leser in der gespeicherten Prozedur.

Definition die gespeicherten Prozedur fährt fort:

while (PQ.Count() > 0 && 
  beenAdded.Count < maxNodesToCheckAsInt)
{
  NodeDistance u = PQ.Dequeue();
  if (u.nodeID == endNode) break;

Der hier verwendete Algorithmus ist eine Variation des kürzesten Weg von Dijkstra, einer der berühmtesten in der Informatik. Obwohl kurz, wird der Algorithmus ist sehr subtil und kann in vielerlei Hinsicht geändert werden. Das Herz des Algorithmus ist eine Schleife, die wird beendet, wenn die Prioritätswarteschlange leer ist. Hier wird eine zusätzliche Sanity-Check basiert auf der Gesamtzahl der Graph Knoten verarbeitet hinzugefügt. In der Hauptschleife zurückgegeben Priorität Warteschlange Dequeue Aufruf den Knoten in der Warteschlange, die die besten (kürzeste) bekannte Gesamtstrecke der Startknoten hat. Wenn der Knoten nur entfernt von der Priorität Warteschlange ist der Endknoten, dann der kürzeste Weg gefunden wurde und die Schleife beendet.

Die Definition geht weiter:

SqlCommand cmd = new SqlCommand(
  "select toNode from tblGraph where fromNode=" + u.nodeID);
cmd.Connection = conn;
long v;  // ID of a neighbor to u
SqlDataReader sdr = cmd.ExecuteReader();
while (sdr.Read() == true) {
  v = long.Parse(sdr[0].ToString());
  if (beenAdded.ContainsKey(v) == false) {
    distance[v] = double.MaxValue;
    previous[v] = -1;
    PQ.Enqueue(new NodeDistance(v, double.MaxValue));
    beenAdded[v] = true;
  }

Diese Codezeilen erhalten alle Nachbarn zu den aktuellen Knoten u. Beachten Sie, dass hierfür eine erste SQL-Daten-Leser. Jeder Nachbar Knoten V wird überprüft, um festzustellen, ob es der erste Auftritt des Knotens im Algorithmus ist. Wenn ja, wird ein NodeDistance-Element mit v als seiner NodeID instanziiert und die Priority Queue hinzugefügt. Statt Knoten auf die Priority Queue hinzufügen, wie sie aufgetreten sind, ist ein neuartiger Bauweise zunächst alle Knoten im Graphen die Priority Queue hinzu. Allerdings könnte dies für sehr großen Graphen erfordern eine sehr große Speichermenge Maschine und sehr lange dauern.

Die innere Schleife lesen-All-Nachbarn fährt fort:

SqlCommand distCmd =
  new SqlCommand("select edgeWeight from tblGraph where fromNode=" +
  u.nodeID + " and toNode=" + v);
distCmd.Connection = conn;
double d = Convert.ToDouble(distCmd.ExecuteScalar());
alt = distance[u.nodeID] + d;

Dieser Code fragt die Datenbank, um die Entfernung aus dem aktuellen Knoten erhalten Sie die aktuellen Nachbarn Knoten V. Beachten Sie, dass ein zweiter Datenleser erforderlich ist, dies zu tun. Die Existenz der zweiten Datenleser erfordert mehrere Änderungen an Eigenschaften, einschließlich die Datenbankeigenschaft trustworthy und das Visual Studio -Projekt Permission-Eigenschaft. Wenn Ihre shortest-Path-Analyse einen ungewichteten Graphen verwendet — d. h. eine wo alle Edge-Gewichte gelten als 1 — Sie können vereinfachen, durch den Wegfall des zweiten Leser und ersetzen

alt = distance[u.nodeID] + 1;

diesen

double d = Convert.ToDouble(distCmd.ExecuteScalar());
alt = distance[u.nodeID] + d;

Variable Alt ist ein Test Abstand vom Startknoten zu der aktuellen Nachbarn Knoten V. Wenn Sie die Zuweisungsanweisung sorgfältig untersuchen, sehen Sie, dass diese Alt die kürzeste bekannte Entfernung vom Start Knoten zu Knoten u plus die tatsächliche Entfernung der Knoten Sie Knoten v ist. Dies entspricht einem potentiellen neuen kürzeren Abstand von den Start-Knoten zu Knoten-V.

Die innere Schleife lesen-All-Nachbarn und der wichtigste Algorithmus-Schleife fortgesetzt mit:

if (alt < distance[v])
    {
      distance[v] = alt;
      previous[v] = u.nodeID;
      PQ.ChangePriority(v, alt);
    }
  }  // sdr Read loop
  sdr.Close();
} // Main loop
conn.Close();

Wenn der Test Abstand vom Startknoten zu v kleiner als die kürzeste bekannte Entfernung vom Startknoten zu V (gespeichert in der Ferne Wörterbuch) ist, eine neue kürzere Entfernung vom Start bis v gefunden wurde, und lokale Daten Strukturen Entfernung zurück und die Priority Queue werden entsprechend aktualisiert.

Die Logik der gespeicherten Prozedur bestimmt nun, ob die wichtigsten Algorithmus-Schleife beendet, weil ein kürzester Pfad war in der Tat gefunden oder wurde beendet, da kein Pfad zwischen Startknoten und Ende gefunden wurde:

pathResult = "NOTREACHABLE";
distResult = -1.0;
if (distance.ContainsKey(endNodeAsLong) == true) {
  double sp = distance[endNodeAsLong];
  if (sp != double.MaxValue) {
    pathResult = "";
    long currNode = endNodeAsLong;
    while (currNode != startNodeAsLong) {
      pathResult += currNode.ToString() + ";";
      currNode = previous[currNode];
    }
    pathResult += startNode.ToString();
    distResult = sp;

Daran erinnern Sie, dass es wirklich zwei Ergebnisse dieser shortest-Path-Implementierung gibt: den kürzesten Weg, ausgedrückt als ein Semikolon -­getrennte Zeichenfolge in umgekehrter Reihenfolge und der kürzeste Weg durch die Summe der Gewichte Rand zwischen Knoten in den kürzesten Weg gemessen. Die gespeicherte Prozedur verwendet Standardwerte von "NOTREACHABLE" und 1,0 für Situationen, wo der Endknoten nicht vom Startknoten aus erreichbar ist. Die While Schleife extrahiert die shortest-Path-Knoten aus dem vorherigen Wörterbuch und Stiche sie zusammen Endknoten Knoten mit Zeichenfolgenverkettung zu starten. Wenn du ehrgeizig bist können Sie verwenden einen Stapel und konstruieren die Ergebniszeichenfolge Startknoten zum Endknoten. Daran erinnern Sie, dass die beiden Ergebnisse über Parameter PathResult und DistResult zurückgegeben werden.

Definition die gespeicherten Prozedur schließt mit der Fehlerprüfung:

} // Try
  catch(Exception ex)
  {
    pathResult = ex.Message;
    distResult = -1.0;
  }
  finally
  {
    if (conn != null && conn.State == ConnectionState.Open)
      conn.Close();
  }
}  // csp_ShortestPath()

Wenn eine Ausnahme aufgetreten ist – in der Regel wenn der SQL Server nicht genügend Arbeitsspeicher wegen ein extrem großes Diagramm oder ein SQL-Verbindungs-Timeout läuft — der Code versucht, die SQL-Verbindung zu bereinigen und Zurückgeben von Ergebnissen, die einige Bedeutung haben.

Erstellen, bereitstellen und Aufruf der gespeicherten Prozedur

Trustworthy-Eigenschaft auf "on" und die Datenbank-Berechtigungsstufe zu externen, wählen Sie nach dafür, dass Sie die Datenbank eingestellt haben bauen CreateStoredProc Visual Studio erstellen im Menü. Wenn der Build erfolgreich ist, wählen Sie erstellen bereitstellen­GespProz Menü erstellen, kopieren Sie die CLR gespeicherte Prozedur aus dem Entwicklungscomputer zu den SQL Server , die SQL-basierte Grafik hostet.

Es gibt mehrere Möglichkeiten zum Aufrufen der gespeicherten CLR-Prozedur. Das Visual Studio -Projekt enthält eine Testvorlage, die Sie verwenden können. Oder rufen Sie die gespeicherte Prozedur direkt von SSMS als gewiesen Abbildung 2. Beispiel:

declare @startNode bigint
declare @endNode bigint
declare @maxNodesToCheck int
declare @pathResult varchar(4000)
declare @distResult float
set @startNode = 222
set @endNode = 444
set @maxNodesToCheck = 100000
exec csp_ShortestPath @startNode, @endNode, @maxNodesToCheck,
  @pathResult output, @distResult output
select @pathResult
select @distResult

Eine andere Möglichkeit ist, rufen Sie die gespeicherte CLR-Prozedur aus einer c#-Anwendung, die mithilfe von ADO.NETnach dem Vorbild der Abbildung 8.

Oder wenn Sie ein echtes Vielfraß für Strafe sind, rufen Sie die gespeicherte CLR-Prozedur mithilfe von LINQ -Technologie.

Abbildung 8 Aufrufen einer gespeicherten Prozedur von in c# unter Verwendung ADO.NET

SqlConnection sc = null;
string connString = "Server=" + dbServer + ";Database=" +
  database + ";Trusted_Connection=True";
sc = new SqlConnection(connString);
SqlCommand cmd = new SqlCommand("csp_ShortestPath", sc);
cmd.CommandType = System.Data.CommandType.StoredProcedure;  
// sp signature: (System.Data.SqlTypes.SqlInt64 startNode, SqlInt64 endNode,   SqlInt32 maxNodesToCheck, out SqlString path)
cmd.CommandTimeout = commandTimeout;  // Seconds
SqlParameter sqlStartNode = cmd.Parameters.Add("@startNode",
  System.Data.SqlDbType.BigInt);
sqlStartNode.Direction = ParameterDirection.Input;
sqlStartNode.Value = sn;
// ...<cmd.ExecuteNonQuery();
string result = (string)cmd.Parameters["@pathResult"].Value;
distResult = (double)cmd.Parameters["@distResult"].Value;

Mehr als nur kürzeste Wege

Sowie die Erklärung, die hier vorgestellten sollten Sie gegen shortest-Path-Graph-Analyse mithilfe einer gespeicherten CLR-Prozedur zulassen. Darüber hinaus können Sie das Design-Konzept im Allgemeinen hilfreich sein. Statt Abrufen von Daten aus SQL auf eine Client-Anwendung und dann zu tun, Filterung und komplexe Verarbeitung auf dem Client, verwenden Sie eine gespeicherte CLR-Prozedur zu holen, Filter und Prozess auf dem Server — und dann Ergebnisse an den Client übertragen. Ich habe diesen Ansatz äußerst nützlich in Situationen mit großen Datenbanken und Anforderungen für Echtzeit-Performance.

Dr.James McCaffrey  funktioniert bei Microsoft Research in Redmond, Washington Er arbeitete an mehreren wichtigen Microsoft-Produkten, einschließlich Internet Explorer und Bing. Er hat einen Abschluss von der University of California in Irvine und der University of Southern California. Seinem persönliche Blog ist bei jamesmccaffrey.wordpress.com. Er kann erreicht werden unter jammc@microsoft.com.

Unser Dank gilt dem folgenden technischen Experten für die Durchsicht dieses Artikels: Darren Gehring (Microsoft)
Darren Gehring ist ein TestManager bei Microsoft Research in Redmond, Washington  Vor der Arbeit bei Microsoft Research, arbeitete er 10 Jahre in der Microsoft SQL Server -Produktgruppe. Seine Webseite ist auf research.microsoft.com/people/darrenge/.