🚺 🤣 ♈️ 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;

エッジテーブルを埋める

2つの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へのパス）