🕤 💞 💮 Panduan studi untuk mengimplementasikan graf berarah dengan tepi-tepi unit menggunakan PL / pgSQL 👨🏿‍🎓 ☠️ 🤴

Artikel ini memberikan ide dan sketsa umum untuk mengimplementasikan grafik terarah di PostgreSQL.

Grafik tersebut digunakan untuk mengimplementasikan subordinasi antar karyawan, bukan metode leluhur-anak yang sebelumnya digunakan dalam tabel departemen.

Pengalaman tersebut ternyata berhasil, mungkin akan berguna bagi seseorang dan membantu menghemat waktu. Pada suatu waktu saya mencari implementasi di pqSQL, tetapi ternyata saya mencari yang buruk. Saya harus menerapkannya sendiri. Yang, secara umum, bahkan untuk yang terbaik, tugasnya menarik, selalu menyenangkan untuk melakukan sesuatu dengan tangan Anda sendiri, sehingga waktu tidak terbuang percuma.

Memasukan data

Secara umum, ada tabel standar "posisi karyawan" dengan id kunci utama . Posisi memiliki hierarki subordinasi "kepala-karyawan". Idenya adalah bahwa tautan antar posting disimpan dalam grafik entitas yang terpisah .

Algoritma Dijkstra digunakan untuk mencari jalur pada grafik, gambaran umum dapat ditemukan, misalnya di sini

Keluaran

Daftar karyawan bawahan untuk ini
Daftar bos untuk karyawan ini
Apakah karyawan itu bawahannya
Daftar karyawan bawahan untuk ini (jalur dari atasan ke karyawan)

Implementasinya menggunakan PL / pgSQL

Menyimpan grafik sebagai tabel tepi

Simpul adalah nilai id dari tabel target.

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

Untuk menghasilkan id dari sebuah edge, gunakan sequence

CREATE SEQUENCE enge_seq OWNED BY graph.edge;

Mengisi meja tepi

Dua operasi INSERT digunakan untuk memasukkan tepi baru (simpul 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  );

Mengambil daftar karyawan bawahan untuk current_id tertentu

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

Mendapatkan daftar bos untuk current_id tertentu

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

Pembuatan matriks ketersediaan (algoritme Dijkstra) dari simpul start_id tertentu

Membuat tabel sementara tmp_matrix

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

Populasi awal tabel 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;

Mengisi matriks ketersediaan

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;

Kembalikan matriks ketersediaan yang dihasilkan

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

Apakah karyawan dengan check_id adalah bawahan untuk start_id tertentu

Dapatkan matriks ketersediaan untuk start_id (lihat di atas).

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

Daftar karyawan bawahan untuk yang satu ini (jalur dari bos start_id ke karyawan finish_id)