Il presente articolo è stato tradotto automaticamente.

CLR

Analisi del percorso più breve basato su grafico mediante una stored procedure CLR

James McCaffrey

Scarica il codice di esempio

Grafico analisi sta diventando sempre più importante nelle applicazioni software. Qui un grafico è un insieme di nodi e di spigoli, non una visualizzazione dei dati, come ad esempio un grafico a barre. Questo articolo presenta una dimostrazione di come eseguire l'analisi del percorso più breve utilizzando una SQL stored procedure CLR. Le tecniche qui presentate possono essere utilizzate anche per molte altre attività di programmazione dati-accesso.

Analisi del percorso più breve grafico davvero comporta due problemi strettamente correlati. Il primo è quello di determinare il percorso più breve da un nodo di inizio grafico specificato a un nodo finale in termini di numero di hop. Il secondo problema è quello di determinare la lunghezza del percorso più breve se connessioni grafico hanno un qualche tipo di peso. Si supponga, ad esempio, i nodi di un grafo rappresentano persone e i bordi tra nodi rappresentano una comunicazione di posta elettronica. You might be interested in minor numero di passaggi tra due persone, dove si sta implicitamente assumendo che ciascun hop ha un peso di 1. Questo è simile al gioco "sei gradi di Kevin Bacon" o il numero di Erdos per un ricercatore. Se ogni bordo grafico ha un peso — per esempio, che rappresenta una misura dell'importanza di un rapporto — è possibile determinare il percorso più breve tra due persone che assumono l'importanza del peso in considerazione.

Ma perché utilizzare una stored procedure CLR? Algoritmi più corto percorso tradizionali si assumono che la rappresentazione del grafico di problema può essere completamente memorizzata nella memoria della macchina, in genere in una lista matrice o adiacenza. Per grandi grafici — per esempio, i grafici che rappresentano le reti sociali — questo approccio spesso non è fattibile. Grafici di grandi dimensioni possono essere convenientemente memorizzati in un database SQL. Un approccio per l'esecuzione di analisi di percorso più breve dei grafici archiviati in un database SQL è scrivere una routine di lingua memorizzato SQL nativa. Articolo di MSDN Magazine, "Graph-Based Shortest-Path Analysis con SQL" (msdn.microsoft.com/magazine/jj863138), spiega che l'approccio in dettaglio. Tuttavia, utilizzando un oggetto CLR stored procedure anziché un approccio puro SQL può fornire prestazioni notevolmente migliori e maggiore flessibilità per la personalizzazione.

Date un'occhiata alla rappresentazione grafico fittizio in Figura 1. Il grafico presenta otto nodi. I numeri accanto a ciascuna freccia rappresentano un peso. Il percorso più breve tra nodo 222 e 444 è 222 -> 555 -> 666 -> 777 -> 444, che ha una distanza ponderata 1.0 + 1.0 + 1.0 + 2.0 = 5.0. Si noti che 222 -> 333 -> 666 -> 777 -> 444 è anche un percorso più breve da 222 a 444.

Figura 1 manichino grafico per l'analisi del percorso più breve

Figura 2 mostra uno screenshot di una chiamata a un oggetto CLR stored procedure denominata csp_ShortestPath che determina il percorso più breve tra nodo 222 e 444. In questo caso il percorso più breve è visualizzato come una stringa delimitata da punto e virgola in ordine inverso. L'uscita è nella parte inferiore dell'immagine. La parte superiore dell'immagine contiene istruzioni SQL che crea un grafico corrispondente a quello di Figura 1.

Figura 2 chiamando un percorso più breve CLR Stored Procedure

Questo articolo presuppone che si sono avanzate competenze di programmazione c# e una base familiarità con SQL. Ho presente tutto il codice SQL per creare il grafico fittizio e tutto il codice c# per creare i CLR stored procedure, e descriverò anche diversi modi per chiamare le stored procedure CLR. Tutto il codice per questo articolo è disponibile presso archive.msdn.microsoft.com/mag201305Graph.

Creazione del Database

Per creare il dummy grafico basato su SQL, lanciato Microsoft SQL Server Management Studio (SSMS) e collegato a un'istanza di un SQL Server 2008 database. Stored procedure CLR sono supportati da SQL Server 2005 e versioni successive. In primo luogo, ho creato un database denominato dbShortPathWithCLR utilizzando i seguenti comandi:

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

Suggerisco vivamente di sperimentare con un manichino database piuttosto che con un database di produzione. I comandi per creare una tabella che contengono dati nodo ed edge sono:

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

ID nodo vengono memorizzati come SQL tipo bigint, che corrisponde approssimativamente a C# tipo long. I pesi di bordo vengono memorizzati come tipo reale, che è sinonimo di float(24) di tipo SQL, che corrisponde approssimativamente a C# tipo double. In molte situazioni non sarà interessato con un peso del bordo e la colonna di edgeWeight può essere omessi.

14 Istruzioni di Figura 3 definire il grafico.

Figura 3 definizione di grafico

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

Se si confrontano le dichiarazioni in Figura 3 con l'immagine in Figura 1 vedrai che ogni istruzione corrisponde ad uno spigolo tra i nodi.

Successivamente, il database viene preparato per l'analisi del percorso più breve:

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

Le prime tre istruzioni creano indici per le colonne fromNode, toNode ed edgeWeight. Quando si lavora con grandi grafici, gli indici sono quasi sempre necessari dare prestazioni ragionevoli. Le prossime due istruzioni alterano database così la proprietà trustworthy è impostata su "on". Il valore predefinito della proprietà è "off". Ti spiego perché la proprietà trustworthy deve essere impostata su "on" poco.

A questo punto viene creato il manichino grafico basato su SQL. Il prossimo passo è utilizzare Visual Studio per creare un oggetto CLR stored procedure per eseguire l'analisi del percorso più breve.

Creazione di CLR Stored Procedure

Per creare la stored procedure CLR percorso più breve, ho lanciato Visual Studio 2010. Per creare stored procedure CLR il vostro sviluppo ambiente deve includere il Microsoft .NET Framework 3.5 o versione successiva. Dal File | Nuovo | Dal menu progetto, ho selezionato il Database | SQL Server gruppo di modelli di progetto e poi selezionato l'opzione di progetto di Database SQL CLR di Visual c#, come mostrato Figura 4. Ho chiamato il progetto CreateStoredProc.

Figura 4: nuovo progetto CLR in Visual Studio 2010

Si noti che il .NET Framework 3.5 è selezionato nel controllo elenco a discesa di dialogo nuovo progetto. La versione del framework di destinazione deve corrispondere alla versione di framework su SQL Server che ospita il database. Poiché il database fittizio è su un'istanza di SQL Server 2008, mirato .NET Framework 3.5. Se il database fittizio era stato su un'istanza del SQL Server 2005, sarebbe aver mirato .NET Framework 2.0. La documentazione di CLR stored procedure è un po ' torbida nel descrivere le correlazioni tra le versioni di framework per l'ambiente di sviluppo, SQL Server e nel progetto di creazione del stored procedure C#. Potrebbe essere necessario ricorrere a un po' di tentativi ed errori.

Dopo aver cliccato su OK per creare il progetto di creazione di stored procedure CLR, Visual Studio richiede con una richiesta di informazioni sul modello di autenticazione e il nome del database di destinazione (vedere Figura 5). Dopo aver cliccato OK nella finestra di dialogo nuovo riferimento al Database, Visual Studio carichi un nuovo progetto ma non direttamente creare un modello. Per generare un modello, fare clic destro sul nome del progetto — CreateStoredProc in questo caso — e selezionare Aggiungi | Nuovo elemento dal menu contestuale (vedere Figura 6).

Figura 5 nuovi riferimento di database per il progetto

Figura 6 nuova voce Stored Procedure

Selezionata la voce di Stored Procedure e la chiamò csp_ShortestPath.cs. Questo nome, senza l'estensione. cs, diventerà il nome della stored procedure nel database di destinazione. Come una questione di stile, generalmente anteporre CLR stored procedura nomi con csp per distinguerli dalla stored procedure di sistema (sp), extended stored procedure (xp) e definiti dall'utente stored procedure (usp). Dopo aver fatto clic sul pulsante Aggiungi, Visual Studio ha generato un modello leggero di una classe parziale denominata StoredProcedures:

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
  }
};

Coda di priorità di un uomo povero

L'algoritmo del percorso più breve presentato in questo articolo richiede una struttura di dati di coda di priorità di accesso casuale. Il Framework .NET non fornisce una coda di priorità integrato che sarà esattamente le esigenze dell'algoritmo del percorso più breve, quindi è necessario codificare la propria coda di priorità.

Una coda di priorità è simile a una normale coda di (FIFO) first-in-first-out con alcune differenze. Si presuppone che gli elementi in una coda di priorità hanno una sorta di campo priorità oltre a un campo dati. Ad esempio, un elemento della coda di priorità per un gruppo di clienti in attesa per il supporto tecnico potrebbe consistere del nome di un cliente e il periodo di tempo che il cliente è stato in attesa per il servizio.

Code di priorità sostengono un'operazione di Dequeue sempre rimuove l'elemento con la massima priorità. Qui, il significato di massima dipende dal contesto problema e può essere un valore più grande o un valore più piccolo. Una coda di priorità di accesso casuale supporta un'operazione che modifica il campo priorità di un elemento con un ID specificato.

Questo articolo presenta coda di priorità di un povero uomo — uno che ottiene il lavoro fatto, ma ha molto margine di miglioramento. L'algoritmo del percorso più breve opera su una coda di priorità dove gli elementi nella coda hanno due campi: un ID di nodo (ad esempio 111 o 222) e un campo di distanza. Il campo di distanza è utilizzato dall'algoritmo per memorizzare la migliore distanza nota (più breve) tra il nodo iniziale e nodo elemento in qualsiasi momento durante l'esecuzione dell'algoritmo. Il campo distanza agisce come priorità dell'elemento, e più piccoli valori per distanza rappresentano una priorità più elevata.

Così, per supportare una coda di priorità di accesso casuale, necessita un ulteriore modello C# stored procedure utilizzando l'istruzione che fa riferimento a due definizioni di classe aggiuntiva definita dal programma e lo spazio dei nomi System.Collections.Generic collocato sotto la classe StoredProcedures parziale:

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;
  }
}

Io uso ambito pubblico per i campi di classe per semplicità. La coda di priorità è essenzialmente un elenco di NodeDistance elementi:

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

Ancora una volta, io uso ambito pubblico per semplicità solo. L'operazione di Dequeue rimuove l'elemento NodeDistance con il valore più piccolo della distanza:

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

Metodo Dequeue chiama un metodo di supporto per individuare la posizione dell'elemento che ha la più piccola distanza, salva un riferimento a tale elemento e quindi utilizza il metodo RemoveAt incorporato per rimuovere l'elemento.

Metodo di supporto IndexOfSmallestDist è definito come:

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;
}

Il metodo esegue una ricerca lineare semplice attraverso l'insieme dell'elenco sottostante. Si noti che questo approccio significa che Dequeue ha prestazioni o (n).

L'operazione Enqueue è definita come:

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

L'operazione di cambiamento di priorità è definito come:

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

Metodo ChangePriority chiama il metodo IndexOf che individua la posizione di un elemento NodeDistance, dato l'ID dell'elemento di supporto ed è definito come:

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

Ancora una volta, si noti che poiché il metodo IndexOf esegue una ricerca lineare, le sue prestazioni è o (n).

L'algoritmo del percorso più breve ha bisogno di conoscere il numero di elementi nella coda di priorità in qualsiasi momento:

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

Per riassumere, priorità di accesso casuale il povero coda definito qui supporta un'operazione di Enqueue; una proprietà Count; un'operazione di Dequeue che rimuove l'elemento NodeDistance con la più piccola distanza; e un'operazione ChangePriority che modifica la distanza di un elemento specificato. Operazioni Dequeue e ChangePriority hanno prestazioni o (n).

Per i grafici di grandi dimensioni, le prestazioni dell'algoritmo shortest path dipende fortemente l'efficienza della coda di priorità utilizzata. Mentre le prestazioni o (n) sono spesso accettabile, è possibile implementare una coda di priorità che è molto meglio O (log n) le prestazioni. Tali implementazioni in genere utilizzano una struttura di dati di heap binario e sono abbastanza difficile. Descrivo una coda di priorità efficiente nel mio articolo del Magazine Visual Studio , "Priority code con C#," disponibile presso bit.ly/QWU1Hv.

Creazione di Stored Procedure

Con la coda di priorità personalizzato definita, può essere implementato l'algoritmo del percorso più breve. La firma del metodo è:

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

Metodo csp_ShortestPath accetta tre parametri di input e ha due parametri di risultato. Parametro NodoIniziale contiene l'ID del nodo del nodo per iniziare la ricerca. Ricordiamo che nella definizione di tabella SQL, toNode e colonne fromNode sono definiti come SQL tipo bigint, che corrisponde al tipo C# lungo. Quando si definisce un oggetto CLR stored procedure, i parametri della procedura utilizzano un modello di tipo definito nello spazio dei nomi System.Data.SqlTypes. Questi tipi sono di solito abbastanza facili mappare i tipi SQL e c#. Qui, tipo bigint mappato a SqlInt64. Parametro di input endNode inoltre è dichiarato come tipo SqlInt64.

MaxNodesToCheck parametro di input viene utilizzato per impedire la stored procedure di filatura fuori controllo sui grafici estremamente grandi. Qui, maxNodesToCheck è dichiarato come tipo SqlInt32, che corrisponde a C# tipo int.

Se siete nuovi alla stored procedure SQL, potreste essere sorpresi di apprendere che essi non possono avere nessun valore restituito esplicito, o può restituire un valore Integer, ma esplicitamente non può restituire qualsiasi altro tipo di dati. Quindi in situazioni dove una stored procedure SQL deve restituire due o più valori, o restituire un valore che non è un tipo int, l'approccio adottato è quello di utilizzare parametri out. Qui, la stored procedure CLR restituisce il percorso più breve come una stringa, come ad esempio "444; 777; 666; 333; 222," e restituisce anche la distanza totale del percorso più breve come un valore numerico, ad esempio 5.0. Così fuori parametro pathResult è dichiarato come tipo SqlString e fuori parametro distResult è dichiarato come tipo Sql­doppio, corrispondente a C# tipi string e double, rispettivamente.

La definizione di procedure CLR stored continua mediante l'istituzione di strutture di quattro dati:

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();

Come si esegue l'algoritmo del percorso più breve, in un dato punto, l'algoritmo deve accedere la corrente migliore (più breve) totale distanza nota dal nodo di inizio per tutti gli altri nodi. La collezione di dizionario denominata «distanza» detiene queste informazioni. La chiave del dizionario è un ID di nodo e il valore del dizionario è la più breve distanza totale conosciuta. L'insieme Dictionary denominato negozi "precedente" l'ID del nodo predecessore immediato a un ID di nodo chiave nel percorso più breve. Ad esempio, nell'esempio mostrato Figura 2, nodo fine è 444. Suo immediato predecessore nel percorso più breve è 777. Quindi precedente [444] = 777. In sostanza la precedente raccolta detiene l'effettivo percorso più breve in modo codificato.

L'insieme Dictionary denominato "beenAdded" contiene informazioni che indicano se un nodo grafico è stato aggiunto alla coda di priorità dell'algoritmo. Il valore booleano è un valore fittizio, perché esso non è davvero necessaria per determinare se un nodo è nell'insieme. È possibile utilizzare un oggetto Hashtable invece un insieme Dictionary. La coda di priorità personalizzato denominata "PQ" è stata definita e spiegata nella sezione precedente di questo articolo.

Continua la definizione della stored procedure:

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

L'oggetto SqlConnection è l'unica connessione con il database di destinazione grafico. Io dichiaro qui che posso controllare il suo stato più tardi se si verifica un'eccezione. Anche se non strettamente necessario, quando la scrittura CLR stored procedure che preferisco creare esplicitamente locale C# digitato variabili che corrispondono al SQL tipizzati variabili di parametro.

La definizione continua:

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

Queste linee di codice di inizializzano il nodo iniziale. Il valore in lontananza dizionario è impostato su 0.0 perché la distanza dal nodo iniziale al sé è zero. L'immediato predecessore del nodo di inizio non esiste quindi un valore di -1 è utilizzato per indicare questo. La coda di priorità viene inizializzata con il nodo di inizio, e viene aggiornato l'insieme del dizionario di beenAdded.

La definizione continua:

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

Quando scrivendo CLR stored procedure io preferisco usare blocchi try-catch esplicita piuttosto rispetto il più elegante l'istruzione using. Quando si imposta la stringa di connessione hai due opzioni. In molti casi, perché la stored procedure è in esecuzione sulla stessa macchina come database SQL, è possibile semplicemente impostare la stringa di connessione su "context connection = true." Una connessione di contesto in teoria offrirà prestazioni migliori rispetto a una connessione standard. Tuttavia, una connessione di contesto ha diverse limitazioni. Una limitazione è che può supportare solo un singolo lettore di dati SQL. Come vedrà a breve, analisi del percorso più breve, spesso (ma non sempre) richiede due lettori di dati SQL.

Perché questa stored procedure CLR richiede due lettori, viene utilizzata una stringa di connessione standard che include una clausola che imposta la proprietà MultipleActiveResultSets su true. Questa clausola non è attualmente supportata da connessioni SQL contesto. Poiché la stored procedure è utilizzando una connessione standard anziché una connessione di contesto, il livello di autorizzazione di Database per il progetto di creazione di stored procedure Visual Studio deve essere impostato esterno, come mostrato Figura 7. Tuttavia, al fine di impostare questa proprietà SQL database deve avere la proprietà trustworthy impostata su "on" come mostrato indietro nel Figura 2.

Figura 7 impostazione livello di autorizzazione Database

Per riassumere, durante la creazione del database grafico, la proprietà del database trustworthy è impostata su "on". Questo permette al progetto di Visual Studio della proprietà livello di autorizzazione di Database esterni. Questo permette la definizione di stored procedure utilizzare una connessione standard anziché una connessione di contesto. Questo permette di proprietà della connessione MultipleActiveResultSets essere impostata su true. E questo permette due lettori di dati SQL nella stored procedure.

Continua la definizione della stored procedure:

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

L'algoritmo utilizzato qui è una variante del percorso più breve di Dijkstra, uno dei più famosi nella scienza dei computer. Anche se breve, l'algoritmo è molto sottile e può essere modificato in molti modi. Il cuore dell'algoritmo è un ciclo che termina quando la coda di priorità è vuota. Qui, viene aggiunto un ulteriore sanity check sulla base del numero totale di nodi del grafo elaborati. All'interno del ciclo principale, la priorità coda Dequeue chiamata restituisce il nodo nella coda che ha il migliore conosciuta (più breve) totale distanza dal nodo iniziale. Se il nodo appena rimosso dalla priorità la coda è il nodo finale, poi è stato trovato il percorso più breve e il ciclo termina.

La definizione continua:

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;
  }

Queste linee di codice ottenere tutti i vicini a u nodo corrente. Si noti che questo richiede un primo lettore dati SQL. Ogni prossimo nodo v è controllato per vedere se è la prima apparizione del nodo nell'algoritmo. Se è così, un elemento NodeDistance con v come sua nodeID è istanziato e aggiunti alla coda di priorità. Invece di aggiungere nodi alla coda di priorità come stai incontrarono, un design alternativo è inizialmente aggiungere tutti i nodi nel grafo alla coda di priorità. Tuttavia, per grafici molto grandi questo potrebbe richiedere una quantità elevata di memoria macchina e prendere un tempo molto lungo.

Il ciclo di lettura-tutti-i vicini interno continua:

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;

Questo codice esegue una query al database per ottenere la distanza dal nodo corrente si al prossimo nodo v corrente. Notare che un secondo lettore di dati è necessario per fare questo. L'esistenza del secondo lettore dati necessita di molteplici cambiamenti di proprietà, tra cui la proprietà del database trustworthy e il progetto di Visual Studio Proprietà Permission. Se il percorso più breve analisi utilizza un grafo non ponderato — che è, uno dove si presuppone che tutti i pesi di bordo siano 1 — è possibile semplificare eliminando il secondo lettore e sostituendo

alt = distance[u.
nodeID] + 1;

for

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

Alt variabile è una test distanza dal nodo iniziale al prossimo nodo v corrente. Se si esamina attentamente l'istruzione di assegnazione, vedrai che alt è la distanza più breve conosciuta dal inizio da nodo a nodo u plus la distanza effettiva dal nodo al nodo v. Questo rappresenta una potenziale nuova corta distanza dal inizio da nodo a nodo v.

Il ciclo interno di lettura-tutti-i vicini e il loop principale algoritmo continua con:

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

Se la distanza dal nodo iniziale test v è minore la distanza più breve conosciuta dal nodo iniziale a v (memorizzati nella distanza dizionario), poi è stata trovata una nuova distanza più breve dall'inizio a v e distanza di strutture dati locali, precedente e la coda di priorità vengono aggiornati di conseguenza.

La logica della stored procedure ora determina se l'algoritmo principale ciclo terminato perché un percorso più breve è stato infatti trovato o terminato perché è stato trovato alcun percorso tra il nodo di inizio e fine:

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;

Ricordo che ci sono realmente due risultati a questa implementazione del percorso più breve: il percorso più breve, espresso come un punto e virgola -­delimitata da stringa in ordine inverso, e il percorso più breve misurato dalla somma dei pesi di bordo tra i nodi del percorso più breve. La stored procedure utilizza impostazioni predefinite di "NOTREACHABLE" e -1,0 per situazioni dove il nodo finale non è raggiungibile dal nodo iniziale. While loop estrae i nodi del percorso più breve dal precedente dizionario e li cuce insieme dal nodo finale per iniziare a nodo tramite la concatenazione di stringhe. Se sei ambizioso è possibile utilizzare una pila e costruire la stringa di risultato dal nodo iniziale al nodo finale. Ricordiamo che i due risultati vengono restituiti tramite le distResult e pathResult i parametri.

La definizione della stored procedure si conclude mediante il controllo di errori:

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

Se si è verificata un'eccezione — in genere se il SQL Server esaurisce la memoria a causa di un grafico estremamente grande o una connessione SQL time-out — il codice tenta di ripulire la connessione SQL e restituire risultati che hanno un qualche significato.

La costruzione, la distribuzione e la chiamata alla Stored Procedure

Dopo essersi assicurati che hai impostato il database trustworthy proprietà su "on" e il livello di autorizzazione di Database esterni, selezionare CreateStoredProc costruire dal menu Build Visual Studio . Se la compilazione ha esito positivo, selezionare creazione di distribuire­stored procedure dal menu Genera per copiare il CLR stored procedure dal computer di sviluppo a SQL Server che ospita il grafico basato su SQL.

Ci sono diversi modi per chiamare le stored procedure CLR. Il progetto Visual Studio contiene un modello di test che è possibile utilizzare. Oppure è possibile chiamare la stored procedure direttamente da SQL Server Management Studio, come mostrato Figura 2. Ad esempio,

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

Un'altra opzione consiste nel chiamare le stored procedure CLR all'interno di un'applicazione c# utilizzando ADO.NET, lungo le linee di Figura 8.

O, se sei un vero mangione per punizione, è possibile chiamare la stored procedure CLR utilizza la tecnologia LINQ .

Figura 8 chiamare una Stored Procedure all'interno di C# utilizzando 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;

Più di appena Shortest Path

Il codice e spiegazione qui presentato dovrebbe consentire di affrontare l'analisi del percorso più breve grafico utilizzando una stored procedure CLR. Inoltre, si potrebbe trovare il paradigma di progettazione utile in generale. Invece di recupero di dati da SQL a un'applicazione client e poi facendo filtro ed elaborazione complessa sul client, utilizzare una stored procedure CLR a fetch, filtro e processo sul server — e poi trasferire i risultati al client. Ho trovato questo approccio per essere estremamente utile in diverse situazioni con database di grandi dimensioni e requisiti per le prestazioni in tempo reale.

Dr. James McCaffrey lavora per la ricerca di Microsoft a Redmond, Washington. Ha lavorato su diversi prodotti Microsoft chiave tra cui Internet Explorer e Bing. Ha conseguito i gradi dall'Università della California a Irvine e la University of Southern California. Il suo blog personale è al jamesmccaffrey.wordpress.com. Può essere raggiunto a jammc@microsoft.com.

Grazie all'esperto tecnica seguente per la revisione di questo articolo: Darren Gehring (Microsoft)
Darren Gehring è un test manager presso Microsoft Research in Redmond, Wash.  Prima di lavorare in Microsoft Research, ha lavorato nel gruppo merceologico Microsoft SQL Server per 10 anni. La sua pagina Web è a research.microsoft.com/people/darrenge/.