👨🏿‍🏫 💎 🈹 使用PL / pgSQL实现带有单元边的有向图的学习指南 🚴🏾 🥘 ♨️

本文提供了在PostgreSQL中实现有向图的一般思路和草图。

该图用于实现员工之间的从属关系，而不是以前在部门表中使用的祖先子代方法。

经验证明是成功的，也许对某人有用并有助于节省时间。有一次，我在寻找一种在pqSQL上的实现，但是显然我很糟糕。我必须自己实施。通常，哪怕是最好的，任务也很有趣，用自己的双手做某事总是很高兴的，这样就不会浪费时间。

输入数据

通常，存在具有主键id的标准表“员工职位”。职位具有从属的“首席雇员”等级。这个想法是帖子之间的链接存储在单独的实体图中。 Dijkstra的算法用于在图中找到路径，例如，可以在此处找到一般描述

输出量

下属员工名单
该员工的老板名单
员工是这个的下属吗
为此的下属员工列表（从老板到员工的路径）

使用PL / pgSQL的实现

将图形存储为边表

顶点是目标表的ID值。

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

要生成边缘的id，请使用以下序列

CREATE SEQUENCE enge_seq OWNED BY graph.edge;

填充边桌

两个INSERT操作用于插入新边（顶点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  );

获取给定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  );

获取给定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  );

从给定顶点start_id生成可用性矩阵（Dijkstra算法）

创建一个临时表tmp_matrix

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

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;

填写可用性矩阵

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;

返回结果可用性矩阵

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

具有check_id的员工是否是给定start_id的下属

获取start_id的可用性矩阵（请参见上文）。

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

此员工的下属员工列表（从上司start_id到员工finish_id的路径）