Ejecución de pruebas

Análisis del camino mínimo basado en grafos con SQL

James McCaffrey

Descargar el ejemplo de código

En este artículo explico cómo implementar un análisis del camino mínimo basado en grafos para situaciones donde tenemos datos en forma de grafo almacenados en una base de datos SQL y queremos emplear procesamiento nativo en el lenguaje T-SQL. Los métodos de camino mínimo tradicionales presuponen que la representación del grafo está almacenada en una estructura de datos en la memoria de la máquina. Pero los grafos de gran tamaño, como los que se usan para representar redes sociales, frecuentemente no caben en memoria, así que una opción posible es almacenarlos y procesarlos con SQL. La mejor forma de entender a lo que voy es que echemos una mirada al grafo de la figura 1 y la captura de pantalla de una ejecución de prueba en la figura 2.

Figura 1 Grafo de ejemplo para el análisis del camino mínimo

Figura 2 Análisis del camino mínimo con SQL

El grafo que aparece en la figura 1 es artificialmente pequeño y tiene ocho nodos (también llamados a veces vértices) con identificadores que van desde el 111 al 888. Podemos imaginar que estos nodos representan personas o equipos. Las flechas direccionales (llamadas generalmente aristas) entre los nodos son las relaciones. Podemos imaginar que una flecha entre dos nodos representa el intercambio de mensajes de correo electrónico. En este ejemplo, las aristas del grafo tienen ponderaciones, que se indican con los valores 1,0 o 2,0. Las ponderaciones de las aristas pueden tener diferentes significados, según el caso puntual del problema. Las ponderaciones pueden representar, por ejemplo, alguna medida de afinidad social o un indicador de cuándo se envió un mensaje.

El término “camino mínimo” puede tener diferentes significados. Supongamos que estamos interesados en el camino más corto entre el usuario 222 y el usuario 444. Esto podría significar la menor cantidad de pasos para llegar de 222 a 444, lo que sería 4 (222 a 333 a 666 a 777 a 444). Pero también podría ser la suma mínima de ponderaciones entre 222 y 444, lo que sería 5,0 (1,0 + 1,0 + 1,0 + 2,0).

En la ventana izquierda en la figura 2 vemos que estoy trabajando con una base de datos llamada dbShortPathDemo en SQL Server Management Studio. En la ventana superior derecha, tengo un script en T-SQL llamado ShortestPath.sql, que define y rellena la base de datos de ejemplo con información que corresponde al grafo de la figura 1, junto con código que define un procedimiento almacenado, llamado usp_ShortestPath. Se acaba de llamar el procedimiento almacenado para analizar el camino más corto entre el usuario 222 y el usuario 444. Los resultados aparecen en la ventana inferior derecha. El camino mínimo se representa con la cadena “444;777;666;333;222”. El camino mínimo en términos de ponderación es 5,0 (y se muestra sin la decimal). La parte inferior derecha de la imagen muestra el estado final de una tabla llamada tblAlgorithmData, que es la clave para la implementación del algoritmo del camino mínimo.

En las siguientes secciones recorreremos el código T-SQL que generó la captura de pantalla de la figura 2, para que usted pueda adaptar el código a sus propios problemas. Sobreentiendo que es un desarrollador que no se especializa en SQL (lo que significa que la mayor parte del tiempo usa C# u otro lenguaje de programación por procedimientos), pero que tiene conocimientos básicos de SQL. Presento todo el código T-SQL que aparece en este artículo; el código también está disponible en archive.msdn.microsoft.com/mag201212TestRun.

Configuración de la base de datos de ejemplo

Para crear una base de datos de ejemplo, inicié SQL Server Management Studio y me conecté a la máquina del servidor. Usé SQL Server 2008, pero el código que se presenta aquí también debería funcionar, con algunas modificaciones menores, en las versiones anteriores y más actuales de SQL Server. Después de conectarme, hice clic en Archivo | Consulta nueva para abrir una ventana de edición, luego escribí el código T-SQL para crear la base de datos de ejemplo:

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

Aquí usé los valores predeterminados para los parámetros de la instrucción create database. En muchas situaciones trabajaremos con una base de datos con datos reales, pero siempre recomiendo realizar primero algunos experimentos con una pequeña base de datos de ensayo. Por lo general, prefiero escribir el código de T-SQL en minúsculas, lo que podría ofender a los puristas de SQL. Usé el mouse para seleccionar estas nueve líneas de código y luego presioné la tecla F5 para ejecutarlas. Después de comprobar que la base de datos se había creado, guardé el script como ShortestPath.sql.

Luego, creé una tabla dentro de la base de datos de ejemplo para contener los datos que definen el grafo que se va a analizar:

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

Usé el mouse para resaltar solo estas siete líneas de código (para que no se volvieran a ejecutar las líneas anteriores) y presioné F5 para crear la tabla. Uso el tipo bigint para los identificadores de los nodos. Otros identificadores comunes para los nodos con los que nos podríamos topar en la práctica son int, para el identificador relativamente sencillo de un empleado, y varchar(11), para los números de la seguridad social con el formato xxx-xx-xxxx. Empleo el tipo real para la columna edgeWeight. El tipo real de T-SQL no es más que un alias conveniente para float(24), que es similar al tipo double de C#. Frecuentemente puede darse la situación que no exista ninguna ponderación de arista explícita entre los nodos, en cuyo caso podremos omitir la columna edgeWeight.

Luego, rellené la tabla tblGraph, para lo cual escribí, resalté y ejecuté estas 15 líneas de código:

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

Si revisamos la figura 1, vemos que cada instrucción insert corresponde a una de las flechas del grafo.

Luego, creé índices en las columnas fromNode y toNode de la tabla tblGraph, para mejorar el rendimiento cuando el procedimiento almacenado para el camino mínimo accede a los datos del grafo:

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

La tabla que contiene únicamente los identificadores de los nodos no es estrictamente necesaria para el análisis del camino mínimo, pero resulta útil cuando queremos realizar pruebas de error en los parámetros del nodo inicial y nodo final del procedimiento almacenado del camino mínimo. Al aplicar la cláusula primary key a la columna nodeID, creo de manera implícita un índice clúster en esa columna. La instrucción union de SQL que se usa con dos o más instrucciones select-distinct es una forma conveniente para recuperar una lista de valores únicas de una tabla.

La tabla con los datos del algoritmo

La clave para entender y modificar el procedimiento almacenado del camino mínimo que se presenta en este artículo es comprender la tabla llamada tblAlgorithmData. Para crear la tabla, podemos ejecutar estas instrucciones T-SQL:

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

Esta tabla tendrá (a lo más) una fila para cada nodo único del grafo, así que en el ejemplo de este artículo la tabla tendrá (a lo más) ocho filas. Como nodeID es un identificador único, lo podría haber usado como clave primaria de la tabla. La columna dist representa la distancia actual desde el nodo inicial al nodo que tiene el nodeID. Este valor cambia durante la ejecución del procedimiento almacenado, pero contiene la distancia final una vez que finaliza el procedimiento almacenado. Si examinamos la figura 2, vemos que el valor dist del nodo final 444 es 5,0 unidades al terminó del procedimiento almacenado.

La columna pred contiene el antecesor inmediato del nodo con el nodeID del camino mínimo desde el parámetro del nodo inicial al nodo final. Por ejemplo, en la figura 2 el nodo final es 444. Su antecesor es 777. El antecesor de 777 es 666. El antecesor de 666 es 333. Y el antecesor de 333 es 222, el nodo inicial. Al juntar estos valores pred se obtiene el camino mínimo entre el nodo final y el nodo inicial: de 444 a 777 a 666 a 333 a 222. Observe que el algoritmo que empleo aquí entrega un solo camino mínimo, incluso en las situaciones donde existen dos o más caminos con la misma distancia mínima total; en este ejemplo, el camino 444 a 777 a 666 a 555 a 222 también tiene una distancia total de 5,0 unidades.

La columna inQueue se define con el tipo bit (funcionalmente parecido al tipo Boolean de C#), que indica si el nodo asociado se debe reexaminar como parte del camino mínimo o no. Dicho de otra forma, si el valor de inQueue es 1, el algoritmo debe reexaminar el nodo correspondiente como vecino del nodo actual en el algoritmo. Si el valor de inQueue es 0, el nodo correspondiente no se debe examinar como vecino. El nombre de la columna inQueue puede resultar engañoso, ya que el algoritmo realmente no usa una cola explícita, así que podríamos reemplazarlo por un nombre parecido a isActive. Usé el nombre inQueue, ya que en las implementaciones en lenguajes de programación por procedimientos de los algoritmos de camino mínimo se usa frecuentemente una cola explícita, así que este nombre tiene cierta tradición.

El algoritmo

El algoritmo que presento en este artículo es una variante del algoritmo del camino mínimo de Dijkstra. En seudocódigo diferente de SQL, la variación del algoritmo de Dijkstra que empleo aquí se muestra en la figura 3.

Figura 3 Algoritmo del camino mínimo

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

El algoritmo de Dijkstra es uno de los algoritmos más famosos de las ciencias de la computación, y en Internet se encuentran muchísimas explicaciones enormemente detalladas, pero pocas implementaciones completas que usen SQL. A pesar de ser corto, el algoritmo de Dijkstra es bastante difícil, para entenderlo completamente tuve que trazar varios ejemplos con papel y lápiz. La esencia del algoritmo es que dado un nodo u, sabremos cuál es la distancia mínima actual desde el nodo inicial al nodo u. Luego encontramos todos los vecinos de u. Para cada vecino v, conocemos la distancia actual desde el nodo inicial a v. Podemos consultar la distancia de u a v. Si la distancia desde el inicio a u más la distancia desde u a v es más corta que la distancia actual desde el inicio a v, sabemos que encontramos un camino más corto desde el inicio a v. La variable inQueue evita que el algoritmo vuelva a visitar un nodo cuando ya se sabe que no conducirá a un camino más corto.

El procedimiento almacenado

Implementé el camino mínimo como procedimiento almacenado en T-SQL. La definición del procedimiento almacenado comienza del siguiente modo:

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

Antepongo “usp” (user-defined stored procedure, procedimiento almacenado definido por el usuario) al nombre del procedimiento almacenado usp_ShortestPath, para distinguirlo de los procedimientos almacenados del sistema (“sp”), procedimientos almacenados extendidos (“xp”) y procedimientos almacenados del CLR (“csp”). Los parámetros @startNode y @endNode son parámetros de entrada. El procedimiento almacenado tiene dos parámetros de salida de resultado, @path y @totDist. El parámetro @path se configura como varchar(5000) en forma arbitraria, usted podría tener que aumentar el tamaño máximo 5000, según el tipo de identificador de nodo que use y el camino máximo que espere.

Luego, inicializo la tabla tblAlgorithmData con la información del nodo inicial:

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

La instrucción truncate borra el contenido de tblAlgorithmData de todas las llamadas anteriores de usp_ShortestPath. Recuerde que las columnas de tblAlgorithmData son nodeID, dist, pred e inQueue. La distancia desde el nodo inicial consigo mismo es 0,0; el antecesor del nodo inicial se establece en -1 para indicar que está indefinido y el bit inQueue se establece en 1 para indicar verdadero.

Este código supone que tblAlgorithmData ya se creó en la base de datos en forma de tabla permanente. En algunas situaciones podría darse que no tengamos los permisos de seguridad necesarios para crear la tabla. En estas situaciones podemos pedirle al administrador de la base de datos que la cree por nosotros o podemos crear tblAgorithmData dentro del procedimiento almacenado como una tabla temporal o quizás como una variable de tabla.

Este código también supone que los valores de @startNode y @endNode son válidos. Si tiene una tabla con los identificadores de todos los nodos, podría comprobar esto más o menos del siguiente modo:

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

A continuación, preparo el bucle de procesamiento:

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

Aquí @u es el identificador del nodo actual en el algoritmo. La variable @d es una conveniencia que contiene la distancia desde @startNode al nodo @u (tal como se encuentra en tblAlgorithmData). La variable @done es una variable de control de bucle artificial. Podríamos poner otros criterios de detención explícitos en el bucle, como por ejemplo el número máximo de iteraciones, el número máximo de pasos o la distancia máxima del camino total.

Dentro del bucle de proceso principal, el primer paso es encontrar el valor de @u, el identificador del nodo actual. Este es el nodo que tiene el menor valor de dist en tblAlgorithmData y que también tiene inQueue = 1:

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

Llegados a este punto, el procedimiento almacenado comprueba dos condiciones de detención del bucle:

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

Si la distancia desde el nodo de inicio a @u (almacenada en @d) es igual al misterioso valor 2147483647,0, significa que el nodo final no se puede alcanzar desde el nodo inicial. El valor 2147483647,0 se usa para representar el infinito. Podemos usar cualquier valor grande que en la práctica no pueda aparecer como distancia. Elegí 2147483647,0, porque 2147483647 (sin la decimal) es el mayor valor del tipo int posible en SQL. La otra condición de término simplemente revisa si se alcanzó el nodo final. Debido a la forma en que el algoritmo realiza la búsqueda dentro del grafo por extensión primero, si se llega al nodo final, se encontró el camino mínimo.

Luego, el procedimiento almacenado comprueba cada vecino del nodo actual @u; si un vecino no se había visto antes, se agrega a tblAlgorithmData y se inicializa:

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

Este código SQL es bastante sutil para los programadores con poca experiencia en SQL. La instrucción insert está sujeta a la condición de la instrucción not exists, lo que se puede interpretar como “si el identificador del nodo vecino (valor toNode) no se encuentra aún en tblAlgorithmData (como nodeID)”. Para cada nodo vecino donde se cumple la condición, la instrucción insert inicializa la tabla tblAlgorithmData con el identificador nodeID del vecino, con un valor infinito (2147483647,0) para dist, un antecesor indefinido (-1) y un valor verdadero (1) para inQueue. El uso de instrucciones SQL que operan con conjuntos de datos, en vez de iterar por una colección con un bucle, como lo haríamos en un lenguaje de programación por procedimientos, puede ser un paradigma bastante difícil de dominar.

En este algoritmo, los nodos se inicializan cuando aparecen por primera vez como nodos vecinos. En un método alternativo importante, todos los nodos del grafo se inicializan al inicio del algoritmo. El problema con ese método es que en los grafos grandes (posiblemente con millones de nodos) se puede perder mucho tiempo en rellenar tblAlgorithmData.

Llegados a este punto, el procedimiento almacenado marca el nodo actual como procesado:

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

Luego, el procedimiento almacenado comprueba cada vecino con el nodo actual para ver si se encontró un camino nuevo más corto y, en caso afirmativo, actualiza los registros en tblAlgorithmData para ese nodo vecino:

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
...

Esta es lejos la parte más difícil de la implementación del camino mínimo. La tabla tblGraph se combina con tblAlgorithmData para poder usar todos los datos en la instrucción update. El identificador del nodo actual se almacena en @u, y este valor se hace coincidir con fromNode de tblGraph. Los vecinos de @u se almacenan en la columna toNode de tblGraph, que está vinculada a la columna nodeID de tblAlgorithmData Recuerde que @d contiene la distancia del nodo inicial al nodo actual @u. El valor de la columna edgeWeight contendrá la distancia de @u al vecino. La suma de estas dos distancias es un posible nuevo camino más corto que la distancia actual desde el nodo inicial al vecino que está almacenado en la columna dist. Si se encontró una nueva distancia más corta, la columna dist se actualiza con ese valor y el antecesor del nodo vecino se registra como @u, el nodo actual. En aquellas situaciones donde definimos que el camino mínimo significa la cantidad menor de pasos entre el nodo inicial y el nodo final, reemplazamos dist = @d + tblGraph.edgeWeight por dist = @d + 1.

Llegados a este punto, el bucle de proceso principal terminó y puedo comprobar la causa del término:

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

Si el valor en @u es el identificador del nodo final, entonces se encontró el nodo final; si @u es cualquier cosa distinta del identificador del nodo final, entonces el bucle terminó antes de encontrar el nodo final. En este caso, establezco la cadena del camino en ‘NOT REACHABLE’ y asigno -1,0 a la distancia del camino mínimo total, para indicar que el nodo no se puede alcanzar. Si el nodo final se encontró, inicializo la cadena shortest-path con la cadena vacía y configuro una variable local @currNode que recorrerá tblAlgorithmData para construir la cadena shortest-path.

El código de la definición del procedimiento almacenado termina con la construcción de la cadena shortest-path y la asignación de la distancia total del camino mínimo:

...
    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

Aquí uso el operador de concatenación “+” de T-SQL. Uso varchar(19), ya que el mayor valor posible (9.223.372.036.854.775.807) del tipo bigint de nodeID tiene 19 dígitos.

Ahora que creé el procedimiento almacenado, puedo encontrar el camino mínimo entre dos nodos arbitrarios; por ejemplo:

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

En resumen

Es posible que la importancia del análisis grafos de camino mínimo aumente en la medida que las empresas acumulen más datos y los almacenen en un entorno de nube. El código y la explicación que se presenta en este artículo deberían servirle como fundamento sólido para que pueda comenzar a realizar análisis de caminos mínimos con sus propios datos. Una alternativa importante para el método nativo en el lenguaje T-SQL que se describe en este artículo es usar un procedimiento almacenado del CLR. En mi experiencia, el análisis del camino mínimo con un procedimiento almacenado del CLR puede mejorar el rendimiento, a costa de una complejidad mayor. En un futuro artículo presentaré un método con un procedimiento almacenado del CLR para el análisis basado en grafos del camino mínimo.

El Dr. James McCaffrey trabaja en Volt Information Sciences Inc., donde está a cargo del entrenamiento técnico de los ingenieros informáticos que trabajan en el campus de Microsoft en Redmond, Washington. Ha colaborado en el desarrollo de varios productos de Microsoft como, por ejemplo, Internet Explorer y MSN Search. McCaffrey es el autor de “.NET Test Automation Recipes” (Apress, 2006). Puede ponerse en contacto con él en jammc@microsoft.com.

Gracias al siguiente experto técnico por su ayuda en la revisión de este artículo: Shane Williams