Execução de teste

Artigo
06/29/2015

Análise do caminho mais curto baseado em gráfico com o SQL

Nesta coluna, explico como implementar uma análise do caminho mais curto baseado em gráfico em situações em que você tem dados gráficos armazenados em um banco de dados SQL e quer usar processamento de linguagem nativa T-SQL. As abordagens tradicionais de caminho mais curto supõem que a representação gráfica seja armazenada em uma estrutura de dados na memória da máquina. Porém, gráficos maiores, como aqueles que representam redes sociais, muitas vezes, não se encaixam na memória, de modo que armazená-los e processá-los usando SQL é uma opção. A melhor maneira de entender onde estou indo é dar uma olhada no exemplo de gráfico na Figura 1 e na captura de tela de uma demonstração feita na Figura 2.

Figura 1 Gráfico de demonstração para análise de caminho mais curto

Figura 2 Análise de caminho mais curto com o T-SQL

O gráfico mostrado na Figura 1 é artificialmente pequeno e tem oito nós (às vezes chamados de vértices) com IDs de 111 a 888. Você pode imaginar que os nós representam pessoas ou computadores. As setas direcionais (geralmente chamadas de bordas) entre os nós são relações. Você pode imaginar que uma seta entre dois nós representa uma troca de emails. Nesse exemplo, as bordas do gráfico têm pesos indicados pelos valore 1.0 ou 2.0. Os pesos das bordas podem ter diferentes significados, de acordo com seu cenário de problema específico. Por exemplo, os pesos podem representar alguma medida de afinidade social ou um indicador de quando uma mensagem foi enviada.

O termo "caminho mais curto" pode ter diferentes significados. Suponha que você esteja interessado no caminho mais curto entre o usuário 222 e o usuário 444. Isso pode significar que o menor número de saltos para ir do 222 ao 444 seria 4 (222 para 333 para 666 para 777 para 444). Ou o caminho mais curto poderia significar a menor soma de pesos entre 222 e 444, que seria 5.0 (1.0 + 1.0 + 1.0 + 2.0).

Na janela esquerda da Figura 2, você pode ver que estou trabalhando com um banco de dados chamado dbShortPathDemo no SQL Server Management Studio. Na janela superior direita tenho um script T-SQL denominado ShortestPath.sql, que define e popula o banco de dados de demonstração com informações que correspondem ao gráfico na Figura 1 e o código que define um procedimento armazenado denominado usp_ShortestPath. O procedimento armazenado foi chamado apenas para analisar o caminho mais curto entre o usuário 222 e o usuário 444. Na janela inferior direita, você poder ver os resultados. O caminho mais curto é fornecido pela cadeia "444;777;666;333;222". O caminho mais curto em termos de peso é 5.0 (exibido sem o decimal). A parte inferior direita da imagem mostra o estado final de uma tabela denominada tblAlgorithmData, que é a chave para implementar o código do caminho mais curto.

Nas seções a seguir, passarei pelo código T-SQL que gerou a captura de tela na Figura 2, assim, você poderá adaptar o código para atender aos seus próprios cenários de problema. Estou supondo que você não é um desenvolvedor de SQL (o que significa que frequentemente você usa C# ou alguma outra linguagem de programação de procedimento), mas que tem algum conhecimento básico de SQL. Apresento todo o código T-SQL explicado neste artigo; o código também está disponível em archive.msdn.microsoft.com/mag201212TestRun.

Configurando o banco de dados de demonstração

Para criar um banco de dados de demonstração, iniciei o SQL Server Management Studio e me conectei ao meu servidor. Usei o SQL Server 2008, mas o código apresentado aqui, com modificações secundárias, deve funcionar com a maioria das versões antigas e todas as novas versões do SQL Server. Após a conexão, cliquei em Arquivo | Nova Consulta para obter uma janela de edição; digitei o código T-SQL para criar meu banco de dados fictício:

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

Aqui usei todos os valores de parâmetro padrão para criar a instrução de banco de dados. Em muitos cenários, você trabalhará com um banco de dados existente com dados reais, mas é recomendável experimentar com um banco de dados de demonstração pequeno. Prefiro usar código T-SQL em letras minúsculas para grande parte, o que pode ofender os puristas do SQL. Usei o mouse para selecionar essas nove linhas de código e pressionei a tecla F5 para executá-las. Após verificar se o banco de dados de demonstração foi criado, salvei o script como ShortestPath.sql.

Em seguida, criei uma tabela dentro do banco de dados de demonstração para manter os dados que definem o gráfico a ser analisado:

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

Usei o mouse para realçar apenas essas sete linhas de código (assim eu não terei que executar novamente as linhas anteriores) e pressionei F5 para criar a tabela. Uso o tipo bigint para IDs de nó. Outros tipos comuns de ID de nó que você pode executar incluem int para uma ID de funcionário relativamente simples e varchar(11) para um número de Previdência Social no formato xxx-xx-xxxx. Uso o tipo real para a coluna edgeWeight. O tipo real T-SQL é apenas um alias conveniente para float(24), que é semelhante ao tipo C# duplo. Em muitos cenários, você pode não ter uma borda explícita entre os nós, bem como pode omitir a coluna edgeWeight.

Em seguida, populei a tabela tblGraph inserindo, realçando e executando estas 15 linhas 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

Ao consultar a Figura 1, você verá que cada instrução insert corresponde a uma das setas no gráfico.

Em seguida, criei índices nas colunas fromNode e toNode em tblGraph para aumentar o desempenho quando o procedimento armazenado de caminho mais curto acessar os dados do gráfico:

    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

Uma tabela apenas de IDs de nós não é obrigatória para análise de caminho mais curto, mas é útil se você quiser executar a verificação de erros nos parâmetros de entrada dos nós inicial e final para o procedimento armazenado de caminho mais curto. Ao aplicar a cláusula de chave primária à coluna nodeID, implicitamente crio um índice clusterizado nessa coluna. A instrução union do SQL, usado com duas ou mais instruções select-distinct, é uma maneira conveniente de buscar uma lista de valores exclusivos em uma tabela.

A tabela de dados de algoritmo

A chave para entender e modificar o procedimento armazenado de caminho mais curto apresentado neste artigo é entender uma tabela de informações denominada tblAlgorithmData. Você pode criar a tabela executando estas instruções 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

A tabela terá (no máximo) uma linha para cada nó exclusivo no gráfico, de modo que no exemplo deste artigo, a tabela terá (no máximo) oito linhas. Como nodeID é um identificador exclusivo, eu poderia tê-lo definido como uma coluna de chave primária. A coluna dist é a distância atual do nó inicial até o nó que tem nodeID. Esse valor dist muda à medida que o procedimento armazenado é executado, mas mantém a distância final quando o procedimento armazenado é concluído. Ao observar a Figura 2, você poderá ver que o valor dist para o nó 444, o nó final, é 5.0 unidades quando o procedimento armazenado é concluído.

A coluna pred mantém o predecessor imediato para o nó com nodeID do caminho mais curto, do nó inicial ao nó final do parâmetro. Por exemplo, na Figura 2, o nó final é 444. Seu predecessor é 777. O predecessor de 777 é 666. O predecessor de 666 é 333. O predecessor de 333 é 222, o nó inicial. Colocar esse valores juntos resulta no caminho mais curto do nó final ao nó inicial: 444 a 777 a 666 a 333 a 222. Observe que o algoritmo que uso fornece apenas um caminho mais curto, mesmo em situações em que há dois ou mais caminhos com a mesma distância total mais curta; nesse exemplo, o caminho 444 para 777 para 666 para 555 para 222 também tem uma distância total de 5.0 unidades.

A coluna inQueue mantém um valor bit (funcionalidade semelhante a C# tipo Booliano) que indica se o nó associado deve ser examinado novamente como parte do caminho mais curto. Em outras palavras, se o valor de inQueue for 1, o nó associado precisará ser examinado pelo algoritmo como um vizinho do nó atual no algoritmo. Se o valor de inQueue for 0, o nó associado não precisa ser examinado como um vizinho. O nome da coluna inQueue é, de certa forma, equivocado, pois o algoritmo não usa realmente uma fila explícita, de modo que pode ser conveniente considerar o uso de um nome como isActive. Uso o nome inQueue porque nas implementações da linguagem de programação de procedimento dos algoritmos do caminho mais curto, muitas vezes, é usada uma fila explícita. Sendo assim, o nome é um tanto tradicional.

O algoritmo

O algoritmo que apresento neste artigo é uma variação do algoritmo Dijkstra’s Shortest Path (DSP). No pseudocódigo não SQL, a variação do algoritmo DSP que uso é apresentada na Figura 3.

Figura 3 Algoritmo do caminho mais curto

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

O algoritmo DSP é um dos algoritmos mais famosos na ciência da computação e você pode encontrar muitas explicações exageradamente detalhadas na Internet, mas bem poucas completam as implementações que usam SQL. Embora curto, o algoritmo DSP é bastante complicado, e a única forma de entendê-lo completamente foi rastreando vários exemplos usando papel e caneta. A essência do algoritmo é que em um determinado nó u, você saberá a distância atual mais curta do nó inicial ao u. Em seguida, você encontrará todos os vizinhos de u. Para cada nó vizinho, v, você sabe a distância atual do nó inicial ao v. Você pode pesquisar a distância de u a v. Se a distância do nó inicial ao u, mais a distância de u ao v for mais curta que a distância atual do nó inicial ao v, você sabe que encontrou um caminho mais curto do nó inicial ao v. A variável inQueue impede que o algoritmo revisite um nó, uma vez que é sabido que revisitar esse nó não encontrará um caminho mais curto.

O procedimento armazenado

Implementei o caminho mais curto como um procedimento armazenado T-SQL. A definição do procedimento armazenado começa:

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

Acrescentei "usp" (procedimento armazenado definido pelo usuário) ao nome do procedimento armazenado usp_ShortestPath para diferenciá-lo dos procedimentos armazenados ("sp") do sistema, procedimentos armazenados estendidos ("xp") e procedimentos armazenados CLR ("csp"). Os parâmetros @startNode e @endNode são parâmetros de entrada. O procedimento armazenado tem dois parâmetros de saída, @path e @totDist. O @path á arbitrariamente definido como tipo varchar(5000) - talvez você precise aumentar o tamanho máximo de 5.000, dependendo do tipo de ID do nó que estiver usando e do caminho máximo que espera.

Em seguida, inicializo a tabela tblAlgorithmData com informações para o nó inicial:

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

A instrução truncate apaga o conteúdo de tblAlgorithmData de qualquer chamada anterior a usp_ShortestPath. Lembre-se de que as colunas de tblAlgorithmData são nodeID, dist, pred e inQueue. A distância do nó inicial até ele mesmo é 0.0, o predecessor do nó inicial é definido como -1 para indicar indefinido e o bit inQueue é definido como 1 para indicar true.

Esse código supõe que tblAlgorithmData já foi criada no banco de dados atual como uma tabela permanente. Em algumas situações, você pode não ter as permissões de segurança necessárias para criar a tabela; nesses casos, você pode solicitar ao administrador do banco de dados apropriado para fazer isso para você ou pode criar tblAgorithmData dentro do procedimento armazenado como uma tabela temporária ou, possivelmente, uma variável de tabela.

Esse código também supõe que os valores de @startNode e @endNode sejam válidos. Se você tiver uma tabela de todas as IDs de nó, será possível verificar isso pelas linhas de:

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

Em seguida, preparo o loop de processamento principal:

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

Aqui, @u é a ID do nó atual no algoritmo. A variável @d é uma conveniência e mantém a distância de @startNode ao nó @u (conforme armazenado em tblAlgorithmData). A variável @done é uma variável de controle de loop fictício. Talvez seja conveniente colocar outros critérios explícitos de interrupção no loop, como um número máximo de iterações, contagem máxima de salto ou distância total máxima do caminho.

Dentro do loop de processamento principal, a primeira etapa é encontrar o valor de @u, a ID do nó atual. Esse é o nó que tem o menor valor da coluna dist em tblAlgorithmData e também tem inQueue = 1:

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

Nesse ponto, o procedimento armazenado verifica se há duas condições de saída de loop:

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

Se a distância do nó inicial ao @u (armazenado em @d) for igual ao valor, de certa forma, de aparência enigmática 2147483647.0, isso significa que o nó final não pode ser atingido a partir do nó inicial. O valor de 2147483647.0 é um substituto da infinidade. Você pode usar qualquer valor maior que não possa realmente aparecer como uma distância. Escolhi 2147483647.0 porque 2147483647 (sem o decimal) é o maior valor para o tipo int do SQL. A outra condição de interrupção simplesmente verifica se o nó final foi atingido. Devido à forma pela qual o algoritmo pesquisa o gráfico usando uma abordagem "primeiro a largura", se o nó final for atingido, o caminho mais curto foi encontrado.

Em seguida, o procedimento armazenado verifica cada vizinho do nó atual @u e, se um vizinho não tiver sido visto antes, ele será inicializado em tblAlgorithmData:

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

Esse código SQL é um pouco sutil se você for um codificador que raramente usa o SQL. A instrução insert é condicional mediante a instrução not exists, que pode ser interpretada como "se a ID do nó do vizinho (valor toNode) ainda não estivesse em tblAlgorithmData (como nodeID)". Para cada nó vizinho onde a condicional é true, a instrução insert inicializa tblAlgorithmData com o nodeID do vizinho, um valor dist de infinidade (como 2147483647.0), um predecessor de indefinido (como -1) e um inQueue de true (como 1). Trabalhar com instruções SQL que operam em conjuntos de dados, em vez de iterar por meio de um conjunto usando um loop, como você faria com uma linguagem de programação de procedimento, pode ser um paradigma difícil de dominar.

Nesse algoritmo, os nós são inicializados quando eles aparecem pela primeira vez como nós vizinhos. Uma abordagem alternativa significativa é inicializar todos os nós gráficos logo no início do algoritmo. O problema com essa abordagem é que para gráficos maiores, popular tblAlgorithmData com possivelmente milhões de nós pode demorar muito.

Nesse ponto, o procedimento armazenado marca o nó atual como processado:

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

Em seguida, o procedimento armazenado verifica cada vizinho para o nó atual a fim de saber se foi encontrado um caminho novo e mais curto para o vizinho e, em caso afirmativo, atualiza as entradas em tblAlgorithmData para esse nó vizinho:

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

Essa é, de longe, a parte mais traiçoeira da implementação do caminho mais curto. A tabela tblGraph é reunida a tblAlgorithmData, de modo que todos os dados possam ser usados na instrução update. A ID do nó atual é armazenada em @u e esse valor é compatível com o fromNode em tblGraph. Os vizinhos de @u são armazenados em toNode, em tblGraph, que é vinculado ao nodeID de tblAlgorithmData. Lembre-se de que @d mantém a distância do nó inicial ao nó @u atual. O valor na coluna edgeWeight manterá a distância de @u até o vizinho. A soma dessas duas distâncias é um possível novo caminho mais curto da distância atual do nó inicial até o vizinho, que é armazenado na coluna dist. Se uma nova distância mais curta for encontrada, a coluna dist será atualizada com essa nova distância mais curta e o predecessor do nó vizinho será registrado como @u, o nó atual. Em situações onde você define o caminho mais curto para o meio do menor número de saltos entre o nó inicial e o nó final, você substitui dist = @d + tblGraph.edgeWeight por dist = @d + 1.

Nesse ponto, o loop de processamento principal foi encerrado e a causa do encerramento pode ser verificado:

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

Se o valor em @u for a ID do nó final, o nó final foi encontrado; se @u for algum outro valor diferente da ID do nó final, o loop foi encerrado antes de encontrar o nó final. Nesse caso, defino a cadeia de caracteres do caminho como "NÃO ACESSÍVEL" e atribuo uma distância total arbitrária de caminho mais curto de -1.0 para indicar que não pode ser atingido. Se o nó final foi, de fato, encontrado, inicializo a cadeia de caminho mais curto para a cadeia vazia e configuro a variável local @currNode para iterar pela tblAlgorithmData, de modo a construir a cadeia de caminho mais curto.

O código da definição do procedimento armazenado é concluído pela construção da cadeia do caminho mais curto e pela atribuição da distância total do caminho mais curto:

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

Aqui uso o operador "+" de concatenação da cadeia T-SQL. Uso varchar(19) porque o maior valor possível para meu tipo nodeID de bigint é 9,223,372,036,854,775,807, que tem 19 dígitos.

Com o procedimento armazenado criado, posso encontrar o caminho mais curto entre dois nós quaisquer, por exemplo:

    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

Conclusão

A análise de gráfico do caminho mais curto provavelmente ganhará mais importância conforme as empresas reunirem mais dados e os armazenarem em um ambiente em nuvem. O código e a explicação apresentados neste artigo devem fornecer uma base sólida para começar a executar a análise do caminho mais curto em seus dados. Uma alternativa importante para a abordagem de linguagem T-SQL nativa descrita neste artigo é usar um procedimento armazenado CLR. Com base nas minhas experiências, uma análise de caminho mais curto usando um procedimento armazenado CLR pode fornecer aumento de desempenho à custa do aumento da complexidade. Apresentarei uma abordagem de procedimento armazenado CLR para análise do caminho mais curto baseado em gráfico em um artigo futuro.

Dr. James McCaffrey trabalha para a Volt Information Sciences Inc., onde gerencia o treinamento técnico de engenheiros de software que trabalham no campus de Washington da Microsoft Redmond. Ele trabalhou em vários produtos da Microsoft, como o Internet Explorer e o MSN Busca. McCaffey é autor do livro “.NET Test Automation Recipes” (Apress, 2006). Entre em contato com ele pelo email jammc@microsoft.com.

Agradecemos ao seguinte especialista técnico pela revisão deste artigo: Shane Williams