🌔 🤞🏽 🎚️ Um guia de estudo para a implementação de um gráfico direcionado com arestas unitárias usando PL / pgSQL 🙆🏾 🏌️ 👨🏾‍🍳

Este artigo fornece idéias gerais e esboços para a implementação de um gráfico direcionado no PostgreSQL.

O gráfico foi usado para implementar a subordinação entre os funcionários, substituindo o método ancestral-filho usado anteriormente na tabela de departamento.

A experiência acabou sendo um sucesso, talvez seja útil para alguém e ajude a economizar tempo. Certa vez, eu estava procurando uma implementação no pqSQL, mas aparentemente estava mal. Eu tive que implementá-lo sozinho. O que, em geral, é até para o melhor, a tarefa é interessante, é sempre bom fazer algo com as próprias mãos, para que o tempo não seja perdido.

Dados de entrada

Em geral, existe uma tabela padrão "posição do funcionário" com o ID da chave primária . Os cargos têm uma hierarquia de subordinação "chefe-empregado". A ideia é que os links entre as postagens sejam armazenados em um gráfico de entidade separado .

O algoritmo de Dijkstra foi usado para encontrar um caminho no gráfico, uma descrição geral pode ser encontrada, por exemplo, aqui

Resultado

Lista de funcionários subordinados para este
Lista de chefes para este funcionário
O funcionário é um subordinado para este
Lista de funcionários subordinados para isso (caminho do chefe para o funcionário)

Implementação usando PL / pgSQL

Armazenar um gráfico como uma tabela de arestas

Os vértices são os valores de id da tabela de destino.

CREATE TABLE graph
(  
  vertex integer NOT NULL ,         --id    
  edge integer NOT NULL ,           --id 
  vertex_order integer NOT NULL --  ( 0 , 1 )
);

Para gerar o id da borda, use a sequência

CREATE SEQUENCE enge_seq OWNED BY graph.edge;

Preenchendo a mesa lateral

Duas operações INSERT são usadas para inserir uma nova aresta (vértices id0, id1 )

--  id 
new_id = nextval('enge_seq');

-- 
INSERT INTO  graph (vertex  , edge , vertex_order  ) VALUES ( id0 , new_id , 0  );

-- 
INSERT INTO  graph (vertex  , edge , vertex_order  ) VALUES ( id1 , new_id , 1  );

Recuperando uma lista de funcionários subordinados para um determinado current_id

SELECT 
  id 
FROM 
  graph
WHERE 
  vertex_order  = 1 AND 
  edge IN (SELECT edge FROM graph WHERE vertex  = current_id AND vertex_order = 0  );

Obtendo a lista de chefes para um determinado current_id

SELECT 
  id 
FROM 
  graph
WHERE 
  vertex_order  = 0 AND 
  edge IN (SELECT edge FROM graph WHERE vertex  = current_id AND vertex_order = 1  );

Geração de uma matriz de disponibilidade (algoritmo de Dijkstra) a partir de um determinado vértice start_id

Criação de uma tabela temporária tmp_matrix

CREATE TEMPORARY TABLE tmp_matrix
AS
(
  SELECT 
    DISTINCT vertex  , 
    FALSE AS label ,
    999999 AS distance ,
    FALSE AS is_finish 
  FROM 
   graph
);

População inicial da tabela tmp_matrix

UPDATE tmp_matrix 
SET label = TRUE , distance = 0 
WHERE vertex = current_id ; 

current_id = start_id ;

SELECT 
  distance
INTO 
  current_distance
FROM 
  tmp_matrix
WHERE 
  vertex = current_id;

SELECT 
  EXISTS (SELECT 1 FROM tmp_matrix WHERE label = FALSE )
INTO
  not_visit;

Preenchendo a matriz de disponibilidade

WHILE not_visit 
LOOP
  FOR v_rec IN
    SELECT 
      *
   FROM 
     tmp_matrix
  WHERE
     NOT label AND 
    --    
     vertex IN ( SELECT 
                       id 
                     FROM 
                      graph
                    WHERE 
                      vertex_order  = 1 AND 
                      edge IN (SELECT 
                                     edge 
                                    FROM 
                                      graph 
                                    WHERE 
                                      vertex  = current_id AND vertex_order = 0  ))
  LOOP    
    --  
    IF v_rec.distance > (current_distance +1)
    THEN 
      UPDATE tmp_matrix SET distance = (current_distance +1) WHERE vertex = v_rec.vertex;
    END IF ;
    
   --  
   IF SELECT 
        NOT EXISTS 
        (
          SELECT 1 FROM graph WHERE vertex = v_rec.vertex AND vertex_order = 0 
        )
   THEN
     UPDATE tmp_matrix SET label = TRUE , is_finish = TRUE WHERE vertex = v_rec.vertex;
   END IF ;   
  END LOOP;  

  UPDATE tmp_matrix SET label = TRUE WHERE vertex = current_id ;

  -- 
  SELECT 
    vertex
  INTO
    current_id 
  FROM 
    tmp_matrix 
  WHERE 
    NOT label AND
    distance < 999999 ;

  SELECT 
    distance
  INTO 
    current_distance
  FROM 
    tmp_matrix 
  WHERE 
     vertex = current_id ;

  SELECT 
    EXISTS (SELECT 1 FROM tmp_matrix  WHERE label = FALSE )
  INTO
   not_visit ;

  IF current_id IS NULL 
  THEN
     not_visit = FALSE ; 
  END IF;
END LOOP;

Retorne a matriz de disponibilidade resultante

SELECT
   vertex ,
   label , 
   distance ,
   is_finish
FROM 
  tmp_matrix 
WHERE 
  distance != 999999 ;

Se o funcionário com check_id é um subordinado para determinado start_id

Obtenha a matriz de disponibilidade para start_id (veja acima).

IF EXISTS 
  ( SELECT distance FROM tmp_matrix WHERE vertex = check_id  )
THEN 
   RETURN TRUE;
ELSE
   RETURN FALSE;
END IF;

Lista de funcionários subordinados para este (caminho do chefe start_id para o funcionário finish_id)