Início / dba / Perguntas / 278567
Accepted
Christophe
Asked: 2020-10-24 05:54:18 +0800 CST

Determinar nós na rede com PostgreSQL

  • 772

Eu tenho uma tabela onde cada entrada é um nó e a tabela contém as conexões diretas de cada nó com outros nós. Estou procurando criar uma exibição com uma coluna para cada nó contendo todos os nós da cadeia, não apenas os nós aos quais o próprio nó está conectado.

Um exemplo seria gerar a coluna Nodes in Chain a partir das duas primeiras colunas da tabela a seguir:

CREATE TABLE example
(
    node text,
    connections text[],
    nodes_in_chain text[]
)

INSERT INTO example VALUES
('a', ARRAY['a','b'],         null),
('b', ARRAY['a','b','c','d'], null),
('c', ARRAY['b','c'],         null),
('d', ARRAY['b','d'],         null),
('e', ARRAY['e','f'],         null),
('f', ARRAY['e','f'],         null);

Node   Connections    Nodes in Chain
"a"    "{a,b}"        "{a,b,c,d}"
"b"    "{a,b,c,d}"    "{a,b,c,d}"
"c"    "{b,c}"        "{a,b,c,d}"
"d"    "{b,d}"        "{a,b,c,d}"
"e"    "{e,f}"        "{e,f}"
"f"    "{e,f}"        "{e,f}"

Essa é uma pequena versão simplificada do problema real. Se eu puder resolver o exemplo, a tabela completa não deve ser problema.

Os dados desta tabela podem ser visualizados da seguinte forma:

dados

Eu olhei em vários métodos diferentes para resolver este problema. Eu olhei para CTEs recursivos, mas não consegui fazê-los funcionar.

Cada nó está conectado a si mesmo atualmente no banco de dados. Não é um problema remover a conexão para si mesmo no banco de dados, se necessário.

Provavelmente antecedentes desnecessários para o problema :

A origem desse problema vem da tentativa de identificar veículos no trânsito. O banco de dados original contém a localização e a velocidade dos veículos a cada passo de tempo t em uma determinada área. O objetivo é determinar o tempo gasto em um semáforo. Para solucionar este problema foi identificada uma área de parada para o semáforo. Cada veículo nesta área com uma velocidade abaixo de um determinado limite é considerado como aguardando o semáforo. Devido a uma longa fila de fila, os veículos podem, no entanto, fazer fila fora desta área. Portanto, é feita uma linha de tráfego ("Cadeia de Nós") com todos os veículos que estão a uma certa distância uns dos outros e possuem uma velocidade baixa abaixo. Partida de um veículo dentro da área de fila identificada. O problema faz parte da pesquisa científica sobre os tempos de táxi das aeronaves.

Primeiro realizei o cálculo para identificar veículos em uma área com Python e pandas. No entanto, o código demorou 10x mais para ser executado, o que o tornou proibitivo para o projeto. O código era muito simples sem loops introduzidos manualmente e, portanto, não poderia ser acelerado (acredito). Também vou comparar a velocidade de execução do algoritmo de enfileiramento em Python versus PostgreSQL.

postgresql postgresql-11

1 respostas

  1. Best Answer

    Abordagem 1:

    À primeira vista, parece que eu poderia aplicar uma solução básica porque, de acordo com seus dados de exemplo, cada conexão está incluída em outra conexão.

    SELECT 
    e1.node, 
    e1.connections, 
    COALESCE(e2.connections, e1.connections) nodes_in_chain
FROM
    example e1
LEFT JOIN 
    example e2
    ON e2.node <> e1.node
    AND e1.connections <@ e2.connections;

    nó | conexões | nodes_in_chain
:--- | :---------- | :-------------
um | {a,b} | {a,b,c,d}     
b | {a,b,c,d} | {a,b,c,d}     
c | {b,c} | {a,b,c,d}     
d | {b,d} | {a,b,c,d}     
e | {e,f} | {e,f}         
f | {e,f} | {e,f}

    Abordagem 2:

    Mas, como @ypercube apontou, essa solução não funciona se houver 3 ou mais pontos lineares seguidos.

    Ex: e -> f -> g -> h

    Como referência para resolver esta questão, usei as respostas em outra questão relacionada:

    Ele usa um método chamado fechamento transitivo para resolver o problema.

    Fechamento transitivo

    Em matemática, o fechamento transitivo de uma relação binária R em um conjunto X é a menor relação em X que contém R e é transitiva.

    Por exemplo, se X é um conjunto de aeroportos e xRy significa "há um voo direto do aeroporto x para o aeroporto y" (para x e y em X), então o fechamento transitivo de R em X é a relação R+ tal que x R+ y significa "é possível voar de x para y em um ou mais voos". Informalmente, o fechamento transitivo lhe dá o conjunto de todos os lugares que você pode chegar a partir de qualquer ponto de partida.

    Primeiro, deixe-me alterar seus dados de amostra adicionando uma conexão linear de 4 nós.

    DELETE FROM example WHERE node = 'f';
INSERT INTO example VALUES
('f', ARRAY['e','f','g'],     null),
('g', ARRAY['f','g','h'],     null),
('h', ARRAY['g','h'],         null);

    Agora aplicando a matemática:

    WITH RECURSIVE al (dst, src) AS --adjacent list or list of all related nodes
(
  SELECT e1.node, e2.node
  FROM   example e1
  JOIN   example e2
         ON e1.node = any(e2.connections)   
), tc (dst, src) AS
   (
     SELECT dst, src FROM al -- transitive closure
     UNION
     SELECT a1.dst, a2.src
     FROM   al as a1 
     JOIN   tc as a2 
            ON a1.src = a2.dst
   )
   SELECT   src, array_agg(DISTINCT dst ORDER BY dst) AS nodes_in_chain
   FROM     tc
   GROUP BY src;

    Dê-nos este resultado:

    src | nodes_in_chain
:-- | :-------------
a   | {a,b,c,d}     
b   | {a,b,c,d}     
c   | {a,b,c,d}     
d   | {a,b,c,d}     
e   | {e,f,g,h}     
f   | {e,f,g,h}     
g   | {e,f,g,h}     
h   | {e,f,g,h}

    db<>fique aqui

    NOTA : A relação original possui apenas as conexões imediatas, que podem ser vistas como caminhos de comprimento 1 (2 nós cada). A abordagem 1 encontra todos os caminhos de comprimento 2 (3 nós), pois aplica um método de conexão uma vez. Para encontrar caminhos de comprimento N, você deve aplicar os métodos N-1 vezes. Para encontrar todos os caminhos de comprimentos arbitrários (como o fechamento transitivo), você precisa de uma solução recursiva ou um loop while. Isso não pode ser feito com SQL simples. (ou seja: uma consulta sem CTEs.)

    @ypercube

    • 6

relate perguntas