Добрый день!
Задача следующая. В базе данных хранится некий двудольный (два типа вершин) ориентированный граф.
Структура графа такова, что вершины типа 2 (квадратик) связывают вершины типа 1 (кружочек)
всегда с соотношением 2 к 1. На рисунке я отобразил граф в минимальном варианте, но предполагается,
что он может состоять из сотен (может быть тысяч) элементов, которые каким-либо образом связаны.
Прикладываю картинку графа.
Схема тестовой базы данных.
create schema test;
create table test.node1 (
id integer,
nodename character varying(32),
primary key(id));
create table test.node2 (
id integer,
nodename character varying(32),
primary key(id));
create table test.linknode (
id integer,
id_left integer,
id_right integer,
id_type integer,
id_result integer,
primary key(id),
constraint fk_left_node1 foreign key (id_left) references test.node1 (id),
constraint fk_right_node1 foreign key (id_right) references test.node1 (id),
constraint fk_result_node1 foreign key (id_result) references test.node1 (id),
constraint fk_link_node2 foreign key (id_type) references test.node2 (id));
insert into test.node1(id, nodename) values (1, '1_1');
insert into test.node1(id, nodename) values (2, '1_2');
insert into test.node1(id, nodename) values (3, '1_3');
insert into test.node1(id, nodename) values (4, '1_4');
insert into test.node1(id, nodename) values (5, '1_5');
insert into test.node1(id, nodename) values (6, '1_6');
insert into test.node1(id, nodename) values (7, '1_7');
insert into test.node1(id, nodename) values (8, '1_8');
insert into test.node1(id, nodename) values (9, '1_9');
insert into test.node1(id, nodename) values (10, '1_10');
insert into test.node1(id, nodename) values (11, '1_11');
insert into test.node2(id, nodename) values (1, '2_1');
insert into test.node2(id, nodename) values (2, '2_2');
insert into test.linknode (id, id_left, id_right, id_type, id_result) values (1, 1, 2, 1, 7);
insert into test.linknode (id, id_left, id_right, id_type, id_result) values (2, 3, 4, 2, 8);
insert into test.linknode (id, id_left, id_right, id_type, id_result) values (3, 5, 6, 1, 9);
insert into test.linknode (id, id_left, id_right, id_type, id_result) values (4, 7, 8, 2, 10);
insert into test.linknode (id, id_left, id_right, id_type, id_result) values (5, 10, 9, 1, 11);
create view test.node1_input as
select distinct id
from (select id_left id from test.linknode union all select id_right id from test.linknode) subq;
comment on view test.node1_input is 'ИД вершин, которые участвуют во входе';
create view test.node1_output as
select distinct id_result id
from test.linknode;
comment on view test.node1_output is 'ИД вершин, которые участвуют в выходе';
create view test.node1_inputonly as
select id
from test.node1_input where
id not in (select id from test.node1_output);
comment on view test.node1_inputonly is 'ИД вершин, которые участвуют ТОЛЬКО во входе';
create view test.node1_outputonly as
select id
from test.node1_output where
id not in (select id from test.node1_input);
comment on view test.node1_outputonly is 'ИД вершин, которые участвуют ТОЛЬКО в выходе';
Проблема с составлением рекурсиваного запроса при движении от листьев к корню.
Собственно рекурсивный запрос:
with recursive graph(id, left_id, left_name, right_id, right_name, type_id, type_name, result_id, result_name, depth) as
(select
l.id,
l.id_left left_id,
(select nodename from test.node1 n where n.id=l.id_left) left_name,
l.id_right right_id,
(select nodename from test.node1 n where n.id=l.id_right) right_name,
l.id_type type_id,
(select nodename from test.node2 n where n.id=l.id_type) type_name,
l.id_result result_id,
(select nodename from test.node1 n where n.id=l.id_result) result_name,
1 depth
from
test.linknode l
where
l.id_left in (select id from test.node1_inputonly) and l.id_right in (select id from test.node1_inputonly)
union
select
l.id,
l.id_left left_id,
(select nodename from test.node1 n where n.id=l.id_left) left_name,
l.id_right right_id,
(select nodename from test.node1 n where n.id=l.id_right) right_name,
l.id_type type_id,
(select nodename from test.node2 n where n.id=l.id_type) type_name,
l.id_result result_id,
(select nodename from test.node1 n where n.id=l.id_result) result_name,
depth+1 depth
from
graph g, test.linknode l
where
l.id_left = g.result_id or l.id_right = g.result_id
)
select * from graph order by id;
Результат
| id | left_id | left_name | right_id | right_name | type_id | type_name | result_id | result_name | depth | | 1 | 1 | "1_1" | 2 | "1_2" | 1 | "2_1" | 7 | "1_7" | 1 | | 2 | 3 | "1_3" | 4 | "1_4" | 2 | "2_2" | 8 | "1_8" | 1 | | 3 | 5 | "1_5" | 6 | "1_6" | 1 | "2_1" | 9 | "1_9" | 1 | | 4 | 7 | "1_7" | 8 | "1_8" | 2 | "2_2" | 10 | "1_10" | 2 | | 5 | 10 | "1_10" | 9 | "1_9" | 1 | "2_1" | 11 | "1_11" | 2 | | 5 | 10 | "1_10" | 9 | "1_9" | 1 | "2_1" | 11 | "1_11" | 3 |
|
Как видно, происходит дублирование элемента с идентификатором 5.
Вот с этим дуболированием я и пытаюсь бороться.
Я понимаю, почему это происходит. В офф. доке доходчиво написано
как реализован рекурсивный запрос в PG и как он выполняется.
Если этот запрос переписать от корня, то проблем нет.
Но при движении от корня неправильно вычисляются номера уровней (depth),
которые далее необходимы для последующего анализа структуры такого графа.
Если убрать depth, то тоже все в порядке (от листьев к корню).
Но depth нужен, опять же для последующего анализа.
Собственно вопрос:
Сталкивался ли кто-либо с такой задачей?? И не могли бы вы направить
решение в праивльное русло?? Что почитать?? Что посмотреть??
Я уже всю голову сломал, но никак не могу придумать, как бы составить
такой рекурсивный запрос.
Попытки что либо выудить из гугля приводили к примерам, но без полной
аналогии представления дерева и соответственно практически не приблизили меня к ответу.
Опыт составления запросов у меня есть, но возможно не такой прокаченный,
чтобы осилить задачу. В примерах мне попадались "крутые" рекурсвиные запросы
с двумя и тремя подзапросами в WITH, но я еще не пришел для себя к решению,
как это поможет для моей схемы данных. Сейчас "колдую" над вариантом,
когда через итерацию протаксиваются агрегаты идентификаторов уже пройденных вершин
(id_result), чтобы пытаться убирать дубликаты, но пока не очень выходит,
ибо движение по дереву идет от листьев к корню.
Кстати сама схема хранения может быть произвольно изменена, если
это позволит решить проблему с рекурсивным запросом.
Спасибо