🥢 🎵 👋🏼 Una guía de estudio para implementar un gráfico dirigido con aristas unitarias usando PL / pgSQL 🎂 🕊️ ♌️

Este artículo proporciona ideas generales y bocetos para implementar un gráfico dirigido en PostgreSQL.

El gráfico se utilizó para implementar la subordinación entre empleados, en lugar del método antepasado-hijo utilizado anteriormente en la tabla de departamentos.

La experiencia resultó ser exitosa, tal vez sea útil para alguien y ayude a ahorrar tiempo. En un momento, estaba buscando una implementación en pqSQL, pero aparentemente tenía mal aspecto. Tuve que implementarlo yo mismo. Lo que, en general, es incluso lo mejor, la tarea es interesante, siempre es bueno hacer algo con tus propias manos, para que no se pierda el tiempo.

Los datos de entrada

En general, existe una tabla estándar "posición de empleado" con la identificación de la clave principal . Los puestos tienen una jerarquía de subordinación "jefe-empleado". La idea es que los enlaces entre publicaciones se almacenen en un gráfico de entidad separado .

Para encontrar una ruta en el gráfico, se utilizó el algoritmo de Dijkstra, se puede encontrar una descripción general, por ejemplo, aquí

Salida

Lista de empleados subordinados para esto
Lista de jefes de este empleado
¿Es el empleado un subordinado para esto?
Lista de empleados subordinados para este (ruta de jefe a empleado)

Implementación usando PL / pgSQL

Guardar un gráfico como tabla de aristas

Los vértices son los valores de identificación de la tabla de destino.

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

Para generar la identificación del borde, use la secuencia

CREATE SEQUENCE enge_seq OWNED BY graph.edge;

Llenar la mesa del borde

Se utilizan dos operaciones INSERT para insertar una nueva arista (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  );

Recuperar una lista de empleados subordinados para un current_id determinado

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

Obtener la lista de jefes para un current_id determinado

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

Generación de una matriz de disponibilidad (algoritmo de Dijkstra) a partir de un vértice dado start_id

Creando una tabla temporal tmp_matrix

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

Población inicial de la tabla 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;

Cumplimentación de la matriz de disponibilidad

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;

Devuelve la matriz de disponibilidad resultante

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

Si el empleado con check_id es un subordinado para el start_id dado

Obtenga la matriz de disponibilidad para start_id (ver arriba).

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

Lista de empleados subordinados para este (ruta desde boss start_id hasta employee finish_id)