Регистрация

[PostgreSQL] Этюд по реализации ориентированного графа с единичными ребрами, используя PL/pgSQL

Ответить на тему
Автор Сообщение
news_bot ®

Стаж: 6 лет 9 месяцев
Сообщений: 27286

Создавать темы news_bot ® написал(а)
21-Июл-2020 16:36
Цитировать

В статье описаны общие идеи по реализации ориентированного графа в PostgreSQL.
Граф был использован для реализации подчинения между сотрудниками, взамен использованного ранее метода «предок-потомок» в таблице отделов.
Опыт оказался успешным, может быть кому-то пригодится и поможет сэкономить время. Я в свое время искал реализации именно на pqSQL, но видимо плохо искал. Пришлось реализовывать самому. Что в общем-то даже к лучшему, задача интересная, всегда приятно что-то сделать своими руками, так, что время потрачено не зря.
Входные данныеВ общем случае имеется стандартная таблица «должность сотрудника» c первичным ключом id. Должности имеют иерархию подчинения «начальник-сотрудник». Идея в том, что связи между должностями хранятся в отдельной сущности граф.
Выходные данные
  • Список подчиненных сотрудников для данного
  • Список начальников для данного сотрудника
  • Является ли сотрудник подчиненным для данного
  • Список подчиненных сотрудников для данного(путь от начальника к сотруднику)

Реализация, используя 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;

Заполнение таблицы ребер
Для вставки нового ребра(вершины id0, id1) используется две операции INSERT
--Генерация нового 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

Создание временной таблицы tmp_matrix

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

Первоначальное заполнение таблицы tmp_matrix

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

Заполнение матрицы доступности

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

Выдать результирующую матрицу доступности

SPL
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)
Получить матрицу доступности для start_id (см. выше).

Заполнить таблицу пути между таблицами start_id и finish_id

SPL
current_id = finish_id ;
result[1] = finish_id ;
WHILE current_id != start_id
LOOP
  SELECT
    par.id
  FROM
   ( SELECT
       id
     FROM
      graph
    WHERE
      vertex_order  = 0 AND
      edge IN (SELECT
                     edge
                    FROM
                      graph
                    WHERE
                      vertex  = current_id AND vertex_order = 1  )) par
  JOIN  tmp_matrix m ON ( par.id = m.vertex  )
  INTO
    parent_id
  LIMIT 1 ;
  SELECT
    array_append( result , parent_id )
  INTO
    result ;
 --Следующая итерация
current_id = parent_id ;
END LOOP;

В результате в массиве result сформируется путь в виде набора id в обратном порядке. Для удобства просмотра массив можно реверсировать любым способом.
 ===========
 Источник:
habr.com
===========
Похожие новости: Теги для поиска: #_postgresql, #_postgresql, #_grafy (графы), #_graphs, #_pgsql, #_postgresql
Профиль  ЛС 
Показать сообщения:     
Ответить на тему

Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы

Текущее время: 22-Ноя 23:57
Часовой пояс: UTC + 5