😁 👳🏿 🐔 Eine Studienanleitung zur Implementierung eines gerichteten Graphen mit Einheitskanten unter Verwendung von PL / pgSQL 💿 💛 🚘

Dieser Artikel enthält allgemeine Ideen und Skizzen zur Implementierung eines gerichteten Diagramms in PostgreSQL.

Das Diagramm wurde verwendet, um die Unterordnung zwischen Mitarbeitern anstelle der zuvor in der Abteilungstabelle verwendeten Vorfahren-Kind-Methode zu implementieren.

Die Erfahrung hat sich als erfolgreich erwiesen, vielleicht ist sie für jemanden nützlich und hilft, Zeit zu sparen. Einmal suchte ich nach einer Implementierung in pqSQL, aber anscheinend sah ich schlecht aus. Ich musste es selbst implementieren. Was im Allgemeinen sogar das Beste ist, die Aufgabe ist interessant, es ist immer schön, etwas mit eigenen Händen zu tun, damit die Zeit nicht verschwendet wird.

Eingabedaten

Im Allgemeinen gibt es eine Standardtabelle "Mitarbeiterposition" mit der Primärschlüssel- ID . Positionen haben eine Hierarchie der Unterordnung "Chefangestellter". Die Idee ist, dass die Verknüpfungen zwischen Posts in einem separaten Entitätsdiagramm gespeichert werden .

Um einen Pfad in der Grafik zu finden, wurde der Dijkstra-Algorithmus verwendet. Eine allgemeine Beschreibung finden Sie beispielsweise hier

Ausgabe

Liste der nachgeordneten Mitarbeiter hierfür
Liste der Chefs für diesen Mitarbeiter
Ist der Mitarbeiter dafür ein Untergebener?
Liste der dafür untergeordneten Mitarbeiter (Weg vom Chef zum Mitarbeiter)

Implementierung mit PL / pgSQL

Speichern eines Diagramms als Randtabelle

Die Eckpunkte sind die ID- Werte der Zieltabelle.

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

Verwenden Sie die Sequenz, um die ID der Kante zu generieren

CREATE SEQUENCE enge_seq OWNED BY graph.edge;

Randtabelle füllen

Zwei INSERT-Operationen werden verwendet , um eine neue Kante einzufügen (Eckpunkte 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  );

Abrufen einer Liste untergeordneter Mitarbeiter für eine bestimmte 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  );

Abrufen der Liste der Bosse für eine bestimmte 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  );

Erzeugung einer Verfügbarkeitsmatrix (Dijkstra-Algorithmus) aus einem gegebenen Scheitelpunkt start_id

Erstellen einer temporären Tabelle tmp_matrix

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

Anfangspopulation der Tabelle 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;

Ausfüllen der Verfügbarkeitsmatrix

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;

Geben Sie die resultierende Verfügbarkeitsmatrix zurück

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

Gibt an, ob der Mitarbeiter mit check_id der angegebenen start_id untergeordnet ist

Holen Sie sich die Verfügbarkeitsmatrix für start_id (siehe oben).

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

Liste der untergeordneten Mitarbeiter für diesen (Pfad von Chef start_id zu Mitarbeiter finish_id)