🎵 ♑️ 🚷 Essai sur l'implémentation d'un graphe dirigé avec des arêtes d'unité à l'aide de PL / pgSQL 🌈 🐂 🏧

Cet article fournit des idées générales et des croquis pour l'implémentation d'un graphe dirigé dans PostgreSQL.

Le graphique a été utilisé pour implémenter la subordination entre les employés, au lieu de la méthode ancêtre-enfant précédemment utilisée dans la table de service.

L'expérience s'est avérée fructueuse, peut-être qu'elle sera utile à quelqu'un et aidera à gagner du temps. À un moment donné, je cherchais une implémentation sur pqSQL, mais apparemment, je cherchais mal. J'ai dû le mettre en œuvre moi-même. Ce qui, en général, est même pour le mieux, la tâche est intéressante, il est toujours agréable de faire quelque chose de ses propres mains, pour ne pas perdre de temps.

Des données d'entrée

En général, il existe une table standard «poste d'employé» avec l' identifiant de la clé primaire . Les postes ont une hiérarchie de subordination «chef-employé». L'idée est que les liens entre les publications sont stockés dans un graphique d' entité distinct .

Pour trouver un chemin dans le graphique, l'algorithme de Dijkstra a été utilisé, une description générale peut être trouvée, par exemple - ici

Production

Liste des employés subalternes pour cela
Liste des patrons de cet employé
L'employé est-il un subordonné pour cela
Liste des employés subalternes pour cela (chemin du patron à l'employé)

Implémentation avec PL / pgSQL

Stockage d'un graphique sous forme de tableau d'arêtes

Les sommets sont les valeurs id de la table cible.

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

Pour générer l' id de l' arête, utilisez la séquence

CREATE SEQUENCE enge_seq OWNED BY graph.edge;

Remplir la table de bord

Pour insérer une nouvelle arête (sommets id0, id1 ), deux opérations INSERT sont utilisées

--  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  );

Récupération d'une liste d'employés subordonnés pour un current_id donné

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

Obtenir la liste des boss pour un current_id donné

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

Génération d'une matrice de disponibilité (algorithme de Dijkstra) à partir d'un sommet donné start_id

Créer une table temporaire tmp_matrix

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

Population initiale de la table 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;

Remplir la matrice de disponibilité

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;

Renvoie la matrice de disponibilité résultante

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

Si l'employé avec check_id est un subordonné pour le start_id donné

Obtenez la matrice de disponibilité pour start_id (voir ci-dessus).

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

Liste des employés subordonnés pour celui-ci (chemin du boss start_id à l'employé finish_id)